Delimited continuations in lone Lisp(matheusmoreira.com)
matheusmoreira.com
Delimited continuations in lone Lisp
https://www.matheusmoreira.com/articles/delimited-continuations-in-lone-lisp
27 comments
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.
Nice project. I'm learning zig as well.
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.
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.
https://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.
https://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.
Project page says it runs on top of the kernel. What is the intended use case? Embedded?
It's often said that Linux user space is unstable. It's my hope that a language that runs directly on top of the kernel will help improve the status quo. The idea is to create executables written in lisp that talk directly to the kernel.
Also it's my shot at creating the fabled lisp operating system. Those projects tend to run out of steam sooner or later due to the sheer enormity of the task. I'm hoping that building on top of Linux will help keep the scope manageable. I'm taking advantage of the fact Linux is the only kernel that actually allows complete user space replacement. Even if lone fails at this, I want to inspire others to try it. Maybe it's the Rust folks who will succeed at rewriting Linux user space in Rust.
Ideologically, it's about Linux maximalism. I've been using Linux for over a decade now and I increasingly believe it should be used everywhere. I know it has lots of great features that people generally avoid because of portability concerns. I want to build a language that encourages people to use Linux to the fullest. Lone is supposed to enable programmers to easily use things like sendfile instead of read/write wherever it makes sense. I'm also thinking about making signalfd the default for signals handling. I want to make Linux systems programming as comfortable as possible.
In practical terms, my long term goal is to get lone to a state where it can power my website. I want to make it powerful enough that it's viable to rewrite my static site generator in lone. I believe its power and usefulness will increase immensely once I start working on a real standard library like Ruby's.
Also it's my shot at creating the fabled lisp operating system. Those projects tend to run out of steam sooner or later due to the sheer enormity of the task. I'm hoping that building on top of Linux will help keep the scope manageable. I'm taking advantage of the fact Linux is the only kernel that actually allows complete user space replacement. Even if lone fails at this, I want to inspire others to try it. Maybe it's the Rust folks who will succeed at rewriting Linux user space in Rust.
Ideologically, it's about Linux maximalism. I've been using Linux for over a decade now and I increasingly believe it should be used everywhere. I know it has lots of great features that people generally avoid because of portability concerns. I want to build a language that encourages people to use Linux to the fullest. Lone is supposed to enable programmers to easily use things like sendfile instead of read/write wherever it makes sense. I'm also thinking about making signalfd the default for signals handling. I want to make Linux systems programming as comfortable as possible.
In practical terms, my long term goal is to get lone to a state where it can power my website. I want to make it powerful enough that it's viable to rewrite my static site generator in lone. I believe its power and usefulness will increase immensely once I start working on a real standard library like Ruby's.
Looks like this other article goes into the details. https://www.matheusmoreira.com/articles/self-contained-lone-...
It's powerful, but is anyone actually using it other than in hobby projects that is, in any language?
Java's new green threads are built on delimited continuations.
Delimited continuations have been implemented in the de-facto standard Haskell runtime system, the GHC runtime system [0]. The goal was to make effect systems more performant [1], but I believe that work has stalled due to the maintainer shifting priorities.
[0]: https://github.com/ghc-proposals/ghc-proposals/blob/master/p...
[1]: https://blog.poisson.chat/posts/2023-01-02-del-cont-examples...
[0]: https://github.com/ghc-proposals/ghc-proposals/blob/master/p...
[1]: https://blog.poisson.chat/posts/2023-01-02-del-cont-examples...
Well the delimited continuation primops are there in ghc for anyone to use. But even with the proliferation of effects libraries in Haskell, I haven't heard a whisper of any of them using the delimited continuation primitives in ghc. There was one very expwrimental extension to Bluefin from memory, but that's it.
That's Bluefin Algae, which isn't as such an extension to Bluefin, but a library that wraps delimited continuations in a Bluefin-style API. As far as I know, no one has really used it yet.
[1] https://hackage.haskell.org/package/bluefin-algae
[1] https://hackage.haskell.org/package/bluefin-algae
By "it" do you mean delimited continuations? If so, my understanding is that they are the standard mode of interruption in Racket — all error-raising/handling and other continuation forms (call/cc, etc) are implemented in terms of delimited continuations because they're a more general abstraction than the older primitives. You can read about Racket's continuation model and where they're used in §10.4 of the Racket Reference [1].
[1] https://docs.racket-lang.org/reference/cont.html
[1] https://docs.racket-lang.org/reference/cont.html
I may be incorrect, but isn't call/cc+state equivalent to delimited continuations?
I.e. one can be implemented with the other (and IIRC Racket does have state)
Oleg covers this on his page "An argument against call/cc" (which is linked). The long-and-short of it is: only in a toy-like way; in practice even call/cc + state are insufficient primitives.
https://okmij.org/ftp/continuations/against-callcc.html#trap...
https://okmij.org/ftp/continuations/against-callcc.html#trap...
Thanks!
[deleted]
>delimited continuations?
Yes, sorry typed this up on the run.
Yes, sorry typed this up on the run.
No worries, just wanted to clarify to make sure my response was on-topic!
The Ocaml 5 effect system is based on delimited continuations, and its new effect-based IO library, Eio, seems to be getting more and more popular all the time.
Exceptions with throw/catch are 90% of the way to delimited continuations so in a sense everyone is already using a close subset of it!
They could be useful in typical exception handling contexts where the operation could be retried. An operation involving a file read that fails due to file not being found could be body could be resumed with dummy data or data sourced from alternative locations. Lisps also like to show a REPL and allow the programmers to plug in the value themselves.
They could be useful in typical exception handling contexts where the operation could be retried. An operation involving a file read that fails due to file not being found could be body could be resumed with dummy data or data sourced from alternative locations. Lisps also like to show a REPL and allow the programmers to plug in the value themselves.
They are required for any compliant Scheme implementation.
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.
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.
> TXR Lisp
I remember.
https://news.ycombinator.com/item?id=34740581
Nice to see you again!
> you would not want that to be based on delimited continuations, or certainly not ones based on this implementation technique
Yes. If I implemented exceptions on top of this, the continuation would be captured and then immediately thrown away. Needlessly wasteful.
I don't really subscribe to Scheme's idea of implementing less powerful primitives in terms of more powerful ones. Conceptually it's amazing but I won't shy away from making new primitives in C if needed. I plan to add additional primitives for exceptions and generators at the very least.
> 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.
I think I get it... How did you implement this on your system?
I implemented lone as a fully interruptible machine that can stop and yield control in between any computation step. I imagined that might come in handy for concurrency and parallelism someday. Wasn't sure how at first. The original idea was to run a separate machine per thread, or to multiplex numerous machines on a set of Linux threads.
Now I'm playing with the idea of making the machine suspend execution by creating another machine with an independent stack, cycling it until it returns a value and then resuming. A machine subordinate to another machine. This concept would implement generators, coroutines...
Does this make sense? Is this similar to what you implemented?
I've read a lot about the complexity and difficulty of finalizers... I'm not sure how I'll implement them yet.
I remember.
https://news.ycombinator.com/item?id=34740581
Nice to see you again!
> you would not want that to be based on delimited continuations, or certainly not ones based on this implementation technique
Yes. If I implemented exceptions on top of this, the continuation would be captured and then immediately thrown away. Needlessly wasteful.
I don't really subscribe to Scheme's idea of implementing less powerful primitives in terms of more powerful ones. Conceptually it's amazing but I won't shy away from making new primitives in C if needed. I plan to add additional primitives for exceptions and generators at the very least.
> 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.
I think I get it... How did you implement this on your system?
I implemented lone as a fully interruptible machine that can stop and yield control in between any computation step. I imagined that might come in handy for concurrency and parallelism someday. Wasn't sure how at first. The original idea was to run a separate machine per thread, or to multiplex numerous machines on a set of Linux threads.
Now I'm playing with the idea of making the machine suspend execution by creating another machine with an independent stack, cycling it until it returns a value and then resuming. A machine subordinate to another machine. This concept would implement generators, coroutines...
Does this make sense? Is this similar to what you implemented?
I've read a lot about the complexity and difficulty of finalizers... I'm not sure how I'll implement them yet.
Abscond is really jut a crude hack: it's exactly like a dynamic block return in that it has a block symbol as its target. It finds the dynamic exist point by walking the dynamic frames looking for the block type with the right symbol. Only when it finds it, it simply jumps there without doing any unwinding.
Jumping without unwinding is more primitive than with; e.g. C setjmp/lonjmp is more primitive than exceptions, right?
It required a shift in attitude: in a Lisp with unwind-protect, we regard the unwinding as a Holy Cow. A dynamic control transfer guarantees that all unwinds are performed on penalty of the run-time implementor being struck by lightning.
I had to convince myself that this heresy was beneficial.
It's like threads. When the system switches from one thread to another, it doesn't unwind the resources of the thread left behind! With continuations, you can simulate coroutines, and as you go between them, you can't be unwinding and re-establishing resources. Not all resources can work that way. E.g. say there is a local variable holding a socket connection. You don't want to tear down and re-connect.
Stuff has to stay intact.
So how do you use the "abscond"? For instance to implement yield. yield works with obtain. obtain creates a dynamic block that is captured as a function. That function returns the yielded items. To continue the computation in the obtain block, you call the function again, to step it to the next yield. You can pass it an argument, which pops out of its yield call.
This yield back and forth is facilitated by the "abscond" dynamic control transfers which don't unwind.
The neat thing is that if, say, the yield process sis a recursive function with unwind protects, they all happen in its context undisturbed by the yield exchanges; it's like an exchange of virtual particles through a quantum tunnel.
Jumping without unwinding is more primitive than with; e.g. C setjmp/lonjmp is more primitive than exceptions, right?
It required a shift in attitude: in a Lisp with unwind-protect, we regard the unwinding as a Holy Cow. A dynamic control transfer guarantees that all unwinds are performed on penalty of the run-time implementor being struck by lightning.
I had to convince myself that this heresy was beneficial.
It's like threads. When the system switches from one thread to another, it doesn't unwind the resources of the thread left behind! With continuations, you can simulate coroutines, and as you go between them, you can't be unwinding and re-establishing resources. Not all resources can work that way. E.g. say there is a local variable holding a socket connection. You don't want to tear down and re-connect.
Stuff has to stay intact.
So how do you use the "abscond"? For instance to implement yield. yield works with obtain. obtain creates a dynamic block that is captured as a function. That function returns the yielded items. To continue the computation in the obtain block, you call the function again, to step it to the next yield. You can pass it an argument, which pops out of its yield call.
This yield back and forth is facilitated by the "abscond" dynamic control transfers which don't unwind.
The neat thing is that if, say, the yield process sis a recursive function with unwind protects, they all happen in its context undisturbed by the yield exchanges; it's like an exchange of virtual particles through a quantum tunnel.
I think I got a bit confused by terminology. By unwinding, do you mean stuff like Scheme's dynamic-wind which is supposed to free and reacquire resources over the course of non-local jumps?
In the "against call/cc" article, it's said that dynamic-wind condemns call/cc by its very existence. Undelimited continuations leak memory and resources and thus this thing was created to free them on exit and reacquire them on reentry. I concluded that delimited continuations have less need of it due to their, well, delimited nature.
> It finds the dynamic exist point by walking the dynamic frames looking for the block type with the right symbol. Only when it finds it, it simply jumps there without doing any unwinding.
That's essentially what lone is doing. It doesn't free any resources when control is transferred. It just copies stack frames to a heap allocated continuation value, then unwinds the stack to the frame introduced by the control primitive.
In the "against call/cc" article, it's said that dynamic-wind condemns call/cc by its very existence. Undelimited continuations leak memory and resources and thus this thing was created to free them on exit and reacquire them on reentry. I concluded that delimited continuations have less need of it due to their, well, delimited nature.
> It finds the dynamic exist point by walking the dynamic frames looking for the block type with the right symbol. Only when it finds it, it simply jumps there without doing any unwinding.
That's essentially what lone is doing. It doesn't free any resources when control is transferred. It just copies stack frames to a heap allocated continuation value, then unwinds the stack to the frame introduced by the control primitive.
By unwinding I mean performing registered clean-ups associated with dynamic controus (e.g. such as that set up by unwind-protect), whose effect is understood to be permanent, on the hypothesis that the contexts being abandoned cannot be returned to.
Scheme's dynamic-wind is a kind of academic attempt to repair uwinding for situations when contexts can be returned to.
It doesn't pass my smell test. If we are following a control flow that leaves a context in such a way that there is a possibility to resume there, we should simply. not touch anything.
On this topic, I didn't mention dynamically scoped variables. Continuations capture their dynamic context. So that is to say, suppose *print-base* is set to 16 for printing integers in hex. Or ruppose *stdout* is redirected to a file. What happens if we capture a delimited continuation, and then resume it? Part of the resumption will be the reinstatement of the dynamic scope, so those variables are effectively captured. And I think that the capture of the dynamic scope goes beyond the prompt; i.e. it doesn't obey the delimiting, which is probably the least surprising requirement.
> That's essentially what lone is doing.
So that is good and you can think of unwinding (e.g. in an exception-related permanent control transfer) as separate from that.
Scheme's dynamic-wind is a kind of academic attempt to repair uwinding for situations when contexts can be returned to.
It doesn't pass my smell test. If we are following a control flow that leaves a context in such a way that there is a possibility to resume there, we should simply. not touch anything.
On this topic, I didn't mention dynamically scoped variables. Continuations capture their dynamic context. So that is to say, suppose *print-base* is set to 16 for printing integers in hex. Or ruppose *stdout* is redirected to a file. What happens if we capture a delimited continuation, and then resume it? Part of the resumption will be the reinstatement of the dynamic scope, so those variables are effectively captured. And I think that the capture of the dynamic scope goes beyond the prompt; i.e. it doesn't obey the delimiting, which is probably the least surprising requirement.
> That's essentially what lone is doing.
So that is good and you can think of unwinding (e.g. in an exception-related permanent control transfer) as separate from that.
> By unwinding I mean performing registered clean-ups
I understand now. By unwinding I meant simply moving the stack pointer backwards. I never considered that the word could carry more meaning than that.
> If we are following a control flow that leaves a context in such a way that there is a possibility to resume there, we should simply. not touch anything.
Agreed. The dynamic-wind situation seems somewhat insane. I hope to avoid it altogether.
This weekend I'm planning to work on more control flow primitives, including a lightweight exception mechanism which doesn't capture the continuation. I think a finally/ensure function will be useful for cleanup in the case of non-resumable exceptions.
> dynamically scoped variables
My language doesn't have them. It's very much like Scheme with its nested environments.
I understand now. By unwinding I meant simply moving the stack pointer backwards. I never considered that the word could carry more meaning than that.
> If we are following a control flow that leaves a context in such a way that there is a possibility to resume there, we should simply. not touch anything.
Agreed. The dynamic-wind situation seems somewhat insane. I hope to avoid it altogether.
This weekend I'm planning to work on more control flow primitives, including a lightweight exception mechanism which doesn't capture the continuation. I think a finally/ensure function will be useful for cleanup in the case of non-resumable exceptions.
> dynamically scoped variables
My language doesn't have them. It's very much like Scheme with its nested environments.
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.