Interestingly Wat implements a callstack in a userland VM, to implement it's delimited continuations. Ergonomically it would be good to implement algebraic effects on top, but the basis is there, along with demos of exception handling, branching, fibres etc.
In TXR Lisp, I made delimited continuations by copying delimited sections of the native stack ("C stack").
Intrinsic functions in the Lisp runtime are not "foreign"; capturing continuations across those is allowed. Just not across true foreign functions and certain library routines that interface with host functions, an example being ftw (file tree walk, wrapper for POSIX ftw).
I have made it possible to throw exceptions out of the lambda callback invoked by ftw, but not to capture delimited continuations from there up across ftw itself.
Speaking of exceptions (in the Blub language sense of "dynamic control transfers"), you would not want that to be based on delimited continuations, or certainly not ones based on this implementation technique.
The pragmatic reason is that exceptions are bread-and-butter that you need in almost any everyday
program, and that have to perform, whereas delimited continuations are boutique.
Making exceptions work within delimited continuation contexts was also a little bit of an extra challenge/chore. When a saved continuation is resumed (blasted to the top of the current and reinstated) the exception-related wiring/plumbing inside that stack segment has to be surgically connected into that of the destination stack, for a correct graft. Basically the last/outermost exception handling frame of the grafted continuation segment has to fixed up to properly hook it into the exception frame linkage. In other words, there is a parallel exception stack consisting of linked frames, which runs through the native stack. A splice is needed there.
To support the front-and-centre use case for delimited continuations, which is the ability to have yields with two-way communication (e.g. a recursive procedure can yield an item to a controlling procedure, which can then reply to it with a different item and resume it) I had to invent a new kind of dynamic control construct called "absconding".
An abscond is exactly like a dynamic long return, except that it performs no unwinding! When a procedure yields, it is not unwinding. It needs to jump out to the context which is interested in the yielded item, but it must not dispose of its resources. There is the expectation that control will jump back in, and everything will need to be intact. Files that the procedure was working with must not be closed, etc.
Absconding is an elegant solution which completely eliminates the need to even think about Scheme's dynamic-wind or similar.
In situations in which absconding would lead to resource leakage, two mechanisms take care of it. Firstly, the program an explicitly "kill" a continuation by resuming it, and passing it a special "poison" value. When a continuation receives a poison value, it resumes as usual, and then immediately begins to unwind all the way to its prompt (top of its stack segment). After this unwinding is complete, the saved continuation object on the heap is marked as poisoned and cannot be resumed again.
If that mechanism is not used, then we rely on the garbage collector to collect the resources in abandoned delimited continuations.
The garbage collector does not automatically do the poisoning call on continuations. However, the application can use finalization for that; i.e. given a delimited continuation C, it could register a finalizer which calls (sys:cont-poison C). The obtain/yield implementation (stdlib/yield.tl) uses this trick.
I also based my Zig Lisp interpreter on delimited continuations and had a great time implementing async, resumable exceptions, dynamically scoped variables, and so on, on top of that.
The single-stepping continuation-shuffling evaluation paradigm also made it really easy to expose evaluations as objects and stepping as a function. A simple form like
(set! e (run (+ 1 1))
stores an evaluation—whose continuation and lexical environment can both be inspected and serialized—and
(step! e)
does a single evaluation step. This lets you implement not just yield-based cooperative concurrency in "user space" but something like green threads with a preemptive scheduler.
Here you can see how the delimited continuation control allows binding to JavaScript's Promise API in a way that lets you treat promises as blocking computations:
Wow that's an awesome idea. I never thought of that. Never occurred to me to expose the machine cycling mechanism.
Send-with-default also seems useful. I was thinking about how to handle the case where the bottom of the stack is reached. Other languages just error out if that happens. I suppose returning a value is just as reasonable.
7 comments
[ 2.8 ms ] story [ 22.2 ms ] threadhttps://github.com/manuel/wat-js
Obviously with forths the callstack is already in userland to implement these things, might be a bit brain-bending in forth.
Intrinsic functions in the Lisp runtime are not "foreign"; capturing continuations across those is allowed. Just not across true foreign functions and certain library routines that interface with host functions, an example being ftw (file tree walk, wrapper for POSIX ftw).
I have made it possible to throw exceptions out of the lambda callback invoked by ftw, but not to capture delimited continuations from there up across ftw itself.
Speaking of exceptions (in the Blub language sense of "dynamic control transfers"), you would not want that to be based on delimited continuations, or certainly not ones based on this implementation technique.
The pragmatic reason is that exceptions are bread-and-butter that you need in almost any everyday program, and that have to perform, whereas delimited continuations are boutique.
Making exceptions work within delimited continuation contexts was also a little bit of an extra challenge/chore. When a saved continuation is resumed (blasted to the top of the current and reinstated) the exception-related wiring/plumbing inside that stack segment has to be surgically connected into that of the destination stack, for a correct graft. Basically the last/outermost exception handling frame of the grafted continuation segment has to fixed up to properly hook it into the exception frame linkage. In other words, there is a parallel exception stack consisting of linked frames, which runs through the native stack. A splice is needed there.
To support the front-and-centre use case for delimited continuations, which is the ability to have yields with two-way communication (e.g. a recursive procedure can yield an item to a controlling procedure, which can then reply to it with a different item and resume it) I had to invent a new kind of dynamic control construct called "absconding".
An abscond is exactly like a dynamic long return, except that it performs no unwinding! When a procedure yields, it is not unwinding. It needs to jump out to the context which is interested in the yielded item, but it must not dispose of its resources. There is the expectation that control will jump back in, and everything will need to be intact. Files that the procedure was working with must not be closed, etc.
Absconding is an elegant solution which completely eliminates the need to even think about Scheme's dynamic-wind or similar.
In situations in which absconding would lead to resource leakage, two mechanisms take care of it. Firstly, the program an explicitly "kill" a continuation by resuming it, and passing it a special "poison" value. When a continuation receives a poison value, it resumes as usual, and then immediately begins to unwind all the way to its prompt (top of its stack segment). After this unwinding is complete, the saved continuation object on the heap is marked as poisoned and cannot be resumed again.
If that mechanism is not used, then we rely on the garbage collector to collect the resources in abandoned delimited continuations.
The garbage collector does not automatically do the poisoning call on continuations. However, the application can use finalization for that; i.e. given a delimited continuation C, it could register a finalizer which calls (sys:cont-poison C). The obtain/yield implementation (stdlib/yield.tl) uses this trick.
The single-stepping continuation-shuffling evaluation paradigm also made it really easy to expose evaluations as objects and stepping as a function. A simple form like
stores an evaluation—whose continuation and lexical environment can both be inspected and serialized—and does a single evaluation step. This lets you implement not just yield-based cooperative concurrency in "user space" but something like green threads with a preemptive scheduler.Here you can see how the delimited continuation control allows binding to JavaScript's Promise API in a way that lets you treat promises as blocking computations:
https://github.com/mbrock/wisp/blob/master/web/js.wisp
You might be interested in seeing e.g. the implementation of SEND-WITH-DEFAULT! which is one of the control control primitives:
https://github.com/mbrock/wisp/blob/b8e29dba0ea61ebaf2db5e3e...
The evaluator itself is in core/step.zig if you want to check it out.
Send-with-default also seems useful. I was thinking about how to handle the case where the bottom of the stack is reached. Other languages just error out if that happens. I suppose returning a value is just as reasonable.
Nice project. I'm learning zig as well.