Whither the Stack?

A computation involving many objects in Keykos usually conforms to the early Fortran pattern where each involved object is at any instant, waiting, running, or available. See this. The waiting domains are linked together by return caps into what might be seen as a stack. This pattern precludes an object appearing twice on the chain. Modern computing patterns are full of recursive algorithms. Keykos has its share of recursive algorithms. They appear in these forms:

• Within the code obeyed by a domain where the recursion involves only matched calls and returns of objects.
• Code in the kernel which allows recursion in servicing recursively defined objects such as segments or meters. In the kernel case the kernel used no stack for it was adapted to the 360 instruction set which delivered no special advantage to stack oriented code. Another reason was the “no space allocation in kernel” rule. The kernel had arbitrary depth counts to enforce as well to limit the duration of atomic operations.
• Once or twice we needed the recursive paradigm involving several ‘stack frames’ of objects of the same type. The object paradigm demands that the code represented multiply on the stack appear there as separate objects, obeying the same code. Recursion as enabled by Algol 60 involved merely bumping a stack pointer to allocate storage for what would amount to object creation in the ocap paradigm. In Keykos this means that object creation is part of the recursive algorithm. Object creation is somewhat expensive in Keykos (10⁴ clock cycles?). That was not a problem the few times we needed it in Keykos.