Re: Continuations

On 7/13/2024 10:16 AM, EricP wrote:

Lawrence D'Oliveiro wrote:

Has there ever been a hardware architecture that managed the flow of control via “continuations”?
>
That is, you do away with the hardware concept of a stack. Instead, you have call frames that, while defined to some extent by the architecture, can be located anywhere in memory (allocation managed by the OS, runtime etc as part of the ABI). A call frame has a current program counter, and maybe some other context like local variables and a static link for lexical binding. Instead of a “return from subroutine” instruction, you have a “load new call frame” instruction.

 This is not really a hardware ISA issue and is mostly what you do with it.
 If an ISA uses a Branch-and-link style subroutine call then it does not
have the concept of a push/pop stack embedded in it.
 

Branch-and-link with no push/pop in my case.
Early on in the design, there were push/pop, but they got dropped after realizing that they had no real advantage (and some disadvantages) vs just using load/store instructions.

On x86 which does have a defined stack pointer register,
that user mode SP can point wherever you want the caller PC saved.
There is also the PUSH and POP instructions but just don't use them.
The only other hardware embedded stack concept would be the frame pointer.
But FP is only manipulated by the ENTER and LEAVE instructions and pretty
much no one uses them.
 Everything else is about how memory is allocated and at what cost.
 

The memory allocation is the killer.
   ADD SP, N, SP / SUB SP, N, SP
Is simple and cheap...
A free-list and possibly needing to resort to some other memory allocator, is much less so; and creates a bit of an issue as to where one stores their data until they can perform the allocation.
If one has a task-state, one can put a free-list in there; but if the free-list can become empty, there is a problem.

Each current local context could be allocated from a heap.
But be careful what you wish for.
We were playing with an IBM R6000 around 1990 which was supposed to
be this fast risc machine but we found it ran slower than our VAX.
We disassembled the code and found out that instead of a normal
decrement/increment stack it used a linked list of heap allocated objects.
Every call did a malloc and every return did a free. All the hardware speed
improvement had been squandered on this completely unnecessary ABI overhead.
 

Yeah, pretty much.

You might have a location defined in a call frame for a “pointer to parent call frame” field, in which case “return from subroutine” just loads this pointer into the current-call-frame register. But you could just as easily have pointers to other call frames defining other kinds of interrelationships between them. And note that transferring to a different call frame does not automatically invalidate the previous one. If it stays valid, then there is no reason why you couldn’t, at some point, come back to it and resume execution from where it left off.
>
The beauty of continuations is that they are a single generalized control construct that can be used to implement specific language features like regular routine calls, loops, exceptions and coroutines, all built from the same common abstraction. One thing that is difficult to do with them is arbitrary gotos. (I consider that a feature, not a bug.)
>
Very few high-level languages (outside of the Lisp family, anyway) seem to have implemented continuations as an explicit language concept. This is an integral part of Scheme, not so much it seems of non-Scheme Lisps. I implemented it in my PostScript revival language
<https://bitbucket.org/ldo17/gxscript/>, and I am still trying to come up with a useful example, like for instance an implementation of coroutines, that doesn’t do my head in. ;)

 I had not heard the term “continuation” until John Levine used it
in a recent post. I looked it up on Wikipedia and found it is
what I call a "callback state machine".
 https://en.wikipedia.org/wiki/Continuation
 This is the basic mechanism used by IO device drivers in RSX, VMS and WinNT.
I have used it for async I/O and transaction processing.
 Those IO subsystems still have regular push/pop call stacks,
as well as each IO context, called an IRP or IO request Packet,
also has a deferred callback stack.
 Used in device drivers the mechanism is very efficient but also somewhat
difficult to program and each driver function must be broken up into a
series of subroutine calls separated by wait states, leaving a trail of
callback bread crumbs behind as it travels so it can find its way home.
 

I had used a similar structure for some amount of real-time code, where a function pointer and some data was put in a queue until a specific time or condition arrives (and the main execution loop basically spun waiting for the conditions to execute things to come up, or potentially performing lower priority "busywork tasks" while waiting if there was a big enough chunk of time until the next event).
I consider this to be very different from an ABI supporting Scheme-style continuations though, which effectively allow one to potentially perform a non-local return from any point in the program (after the continuation is made), to the point where the continuation was made, potentially an indefinite number of times. There is no real "good" way to pull this off short of heap-allocating all of the stack frames (which then become "permanent" if/when a call/cc happens).
The poor man's version might be to attempt to make a copy of the stack and then restore this stack copy each tome the continuation is invoked (like longjmp but with stack-copying).
Drawback is that this will only capture local variables as they were at the moment they were captured, whereas continuations typically preserved the "identity" of the variables (such that modifying a variable when invoking a continuation would see the same changes to the same variables in subsequent runs).
Actually, it is a similar feature with lambda's in Scheme, but many other languages have instead settled on "capture by value". Where, once the lambda is made, its copy of the variable is independent of the value that exists in the parent function. Some languages also make this captured value read-only, but I had not usually done this in my languages.
Also lambdas (in the latter form) are a lot cheaper to implement.
...