Continuations

As one learns to program Keykos one soon discovers that there is no system stack and that these “resume keys” allow the callee to reply to the caller. Continuations can be arguments and parameters and thus be passed. This pattern was discovered long ago and the reply ability was named “continuation” and papers on “continuation passing style” are legion.

The stack is an extraordinary convenient place to put stack variables for the callee. Continuation passing style never caught on much. When the caller and callee have different different security perspectives there may be problems with the stack. Few systems guaranty a clean stack or limit the program to its own stack frame within the stack. Also Keykos had already decided to account for all storage and this did not fit with stacks. Among modern systems seL4 has the same dilemma; they call their continuation a “reply capability” which is a better name.

This a terrible idea for a square root object however. Square root needs a word or two of scratch and the obvious way to do this provides an object which if widely used means that two CPU’s in the same system cannot be taking square root at once. Even without this flaw the Keykos key invocation probably dominates the time to take square root The Keykos answer was to merely use the square root routine in the standard language library which can be shared across trust boundaries. We found few if any desired objects that were purely reentrant like square root and we do not support them well!

When we talk to language designers they justifiably rebel at the two similar concepts of calling a reentrant routine and calling an object. We have no answer for them.

Except when compiled code it used to define objects in systems like Keykos it is vital for the programmer to know the difference between calling local routines, which he probably wrote, and invoking other objects, where capability discipline is dynamically enforced. When you “bring your own compiler” you commit to finding a compiler suitable for people who will want to understand your code to be sure of its correctness. Ultimately I hope for compilers that include “correctness proofs” in their output where upon the problem recedes.