Emulating Goto in Scheme with Continuations(terezi.pyrope.net)
terezi.pyrope.net
Emulating Goto in Scheme with Continuations
https://terezi.pyrope.net/ccgoto/
25 comments
Here's my very funny implementation of delimited continuation in plain C with zero ASM usage (with help from a specific compiler built-in)
https://gist.github.com/Trung0246/8f801058212d3bbbef82690a31...
Demo (old version with outdated compile flag but still works): https://godbolt.org/z/n9ch4TM3s
It works for gcc/clang/msvc with -O0, -O1, -O2, and even -O3
https://gist.github.com/Trung0246/8f801058212d3bbbef82690a31...
Demo (old version with outdated compile flag but still works): https://godbolt.org/z/n9ch4TM3s
It works for gcc/clang/msvc with -O0, -O1, -O2, and even -O3
If you are into continuations, check Friedman's papers on ReadScheme.
https://github.com/schemedoc/bibliography/blob/master/page6....
In particular look at "Programming with Continuations", "Engines Build Process Abstractions" and "Continuations and Coroutines".
https://github.com/schemedoc/bibliography/blob/master/page6....
In particular look at "Programming with Continuations", "Engines Build Process Abstractions" and "Continuations and Coroutines".
I confess I like Common Lisp's TAGBODY far more than I feel like I should. Having constrained GOTO semantics to a short section of the codebase is surprisingly useful.
Following the recommendations of Knuth, the language Mesa, which was implemented at Xerox during the seventies, and which was a source of inspiration for various later languages, including Modula, Ada and Python, included a form of "restricted GOTO" which is the most useful kind of GOTO in my opinion.
The Mesa restricted GOTO allowed jumping forwards, but not backwards, and it allowed jumping towards an outer block, but not towards an inner block.
These 2 restrictions eliminate all the "harmful" features of the traditional GOTO, while retaining its advantages for handling exceptional conditions or for terminating multiple levels of nested program structures.
The Common Lisp TAGBODY appears to be only partially restricted, by allowing backward jumps, so it does not prevent the kind of hard-to-understand program structures for which GOTO was criticized.
GOTOs in random directions may be used to implement state machines, but such state machines can still be implemented in a language with restricted GOTO by not using GOTO, but by using mutually recursive procedures, if tail-call optimization is guaranteed.
The Mesa restricted GOTO allowed jumping forwards, but not backwards, and it allowed jumping towards an outer block, but not towards an inner block.
These 2 restrictions eliminate all the "harmful" features of the traditional GOTO, while retaining its advantages for handling exceptional conditions or for terminating multiple levels of nested program structures.
The Common Lisp TAGBODY appears to be only partially restricted, by allowing backward jumps, so it does not prevent the kind of hard-to-understand program structures for which GOTO was criticized.
GOTOs in random directions may be used to implement state machines, but such state machines can still be implemented in a language with restricted GOTO by not using GOTO, but by using mutually recursive procedures, if tail-call optimization is guaranteed.
In Common Lisp's tagbody, labels must be immediate children of the form; they cannot be anywhere in the enclosed syntax.
The go form identifies the tagbody which is the immediate parent of the selected label. It then performs a control transfer which selects that form as the exit point; every form in between is abandoned with all the unwinding. Then that tagbody passes control to the selected label.
We can imagine every tabody to be a kind of case statement which selects the first case on entry, and subsequent cases are selected by go forms; each go says "break up to the top of the tagbody, and then go to this case".
So for instance you can't have shenanigans like two loops or conditionals buried in the same tagbody, where one jumps into the middle of the other.
Jumping out of a lambda /is/ possible, but only if the tagbody within which the lambda was captured has not yet terminated. (In other words, the lambda isn't an escapee from the tagbody it's trying to use.)
The go form identifies the tagbody which is the immediate parent of the selected label. It then performs a control transfer which selects that form as the exit point; every form in between is abandoned with all the unwinding. Then that tagbody passes control to the selected label.
We can imagine every tabody to be a kind of case statement which selects the first case on entry, and subsequent cases are selected by go forms; each go says "break up to the top of the tagbody, and then go to this case".
So for instance you can't have shenanigans like two loops or conditionals buried in the same tagbody, where one jumps into the middle of the other.
Jumping out of a lambda /is/ possible, but only if the tagbody within which the lambda was captured has not yet terminated. (In other words, the lambda isn't an escapee from the tagbody it's trying to use.)
I'm not clear that jumping backwards is that tough to reason with. Notably, Knuth's algorithms do that quite commonly, right?
I do think they need to be somewhat constrained to not jump to places that need new things initialized. Which, it is truly mind blowing to know folks used to just jump straight into other functions. Mid function. Because why not.
I do think they need to be somewhat constrained to not jump to places that need new things initialized. Which, it is truly mind blowing to know folks used to just jump straight into other functions. Mid function. Because why not.
Knuth's algorithms do that because they are written in assembly language.
In assembly language you must use backwards jumps to implement loops.
However, good assembly language programmers do not use arbitrary backwards jumps, but they use only a certain number of patterns, which correspond to the various kinds of loops that are also encountered in high-level programming languages.
Many programming languages are somewhat incomplete, because they do not have all the kinds of loops that exist in other programming languages. When programming in an assembly language, a good programmer will not restrict the loops to only the kinds of loops that are available in C/C++, but the non-nested loops that are possible with arbitrary GOTO will not be used.
The best practice in assembly programming is to not use explicit backwards jumps, but to define macros for different kinds of loops, then use the macros, which make the code look exactly like in a high-level programming language.
Knuth's algorithms do not use macros, like in real assembly programming, because their purpose is to show you an actual implementation, not a higher-level abstraction.
In assembly language you must use backwards jumps to implement loops.
However, good assembly language programmers do not use arbitrary backwards jumps, but they use only a certain number of patterns, which correspond to the various kinds of loops that are also encountered in high-level programming languages.
Many programming languages are somewhat incomplete, because they do not have all the kinds of loops that exist in other programming languages. When programming in an assembly language, a good programmer will not restrict the loops to only the kinds of loops that are available in C/C++, but the non-nested loops that are possible with arbitrary GOTO will not be used.
The best practice in assembly programming is to not use explicit backwards jumps, but to define macros for different kinds of loops, then use the macros, which make the code look exactly like in a high-level programming language.
Knuth's algorithms do not use macros, like in real assembly programming, because their purpose is to show you an actual implementation, not a higher-level abstraction.
I am not talking about the implementations in assembly, I'm talking about the way he lists them in prose.
I can accept that he lists them the way he does because of familiarity to a style of assembly, but that doesn't change the fact that his prose can be easier to read than some of the alternative schemes people have used. In particular, I have found them to be far more illuminating to what is happening. With some odd challenges on finding ways to convert them to the standard control structure of modern languages.
You don't have to make a larger explanation of the argument for the more common control structures we use today. I am largely bought off on them and I am not trying to argue for a return to "only using jumps."
I can accept that he lists them the way he does because of familiarity to a style of assembly, but that doesn't change the fact that his prose can be easier to read than some of the alternative schemes people have used. In particular, I have found them to be far more illuminating to what is happening. With some odd challenges on finding ways to convert them to the standard control structure of modern languages.
You don't have to make a larger explanation of the argument for the more common control structures we use today. I am largely bought off on them and I am not trying to argue for a return to "only using jumps."
jumping backward creates all the non-linear issues I assume
Fair that it can create some. But just allowing of nested loops already creates some of these. And, I know folks have tried to disallow loops, but that feels extreme.
Again, I would point to many of Knuth's descriptions as already allowing jumps forward and backward in steps as evidence that they can be useful.
Again, I would point to many of Knuth's descriptions as already allowing jumps forward and backward in steps as evidence that they can be useful.
When backward jumps are allowed you can create loops that are much more tangled and incomprehensible than when you are nesting the loop structures of modern languages.
With backward jumps, you can make multiple loops that are not nested, but you could visualize them as a complex graph that has sequences of instructions in the nodes and which has multiple cycles through which the execution may or may not pass and which intersect each other. Good luck to understand how the code works, because you cannot separate parts of it that can be understood independently, like when using the "structured programming" that is ubiquitous in modern programming languages.
Such indecomposable complex multiple loops were not uncommon before 1970 in languages like FORTRAN or COBOL, and precisely this kind of control structures were the reason why the use of GOTO was criticized and considered harmful.
With backward jumps, you can make multiple loops that are not nested, but you could visualize them as a complex graph that has sequences of instructions in the nodes and which has multiple cycles through which the execution may or may not pass and which intersect each other. Good luck to understand how the code works, because you cannot separate parts of it that can be understood independently, like when using the "structured programming" that is ubiquitous in modern programming languages.
Such indecomposable complex multiple loops were not uncommon before 1970 in languages like FORTRAN or COBOL, and precisely this kind of control structures were the reason why the use of GOTO was criticized and considered harmful.
I said that that was a fair claim. My only point on loops is you can already get some hairy explosions with "easy" to understand loops. Since those are effectively backwards jumps already.
That said, I disagree with your idea that you can't reason about it. You are just describing a flowchart that has several arrows going in different directions. Is it as easy as a flow chart that only has arrows in one direction? Of course not. But it is doable. In fact, if you allow jumping forward out of a loop, you already have most of this.
Now, can you make one that is so complicated that it can't be understood that well? Of course you can.
That said, I disagree with your idea that you can't reason about it. You are just describing a flowchart that has several arrows going in different directions. Is it as easy as a flow chart that only has arrows in one direction? Of course not. But it is doable. In fact, if you allow jumping forward out of a loop, you already have most of this.
Now, can you make one that is so complicated that it can't be understood that well? Of course you can.
I agree with your point that you can already get some hairy explosions with "easy" to understand loops.
I also agree with you that even if have not use the word "flowchart" that was what I meant, i.e. the use of unrestricted GOTO results in the most general kind of flowchart, without any constraints. I also agree that with more or less effort any flowchart, i.e. any program can be understood, but the goal of a programmer is to never make a program harder to understand than strictly necessary for solving the given problem.
My main point however, is that allowing backwards GOTO and allowing loops is not the same thing, which is the reason why Knuth in his recommendations of how to combine GOTO with structured programming and the language MESA allowed loops, but not backwards GOTO.
A loop is terminated by a backwards GOTO, but the pairs formed by the implicit label from the beginning of a loop and the backwards GOTO from the end of a loop behave like pairs of parentheses, i.e. they may only be nested and they may not be interleaved.
An arbitrary backwards GOTO does not have this restriction, i.e. it can jump in the middle of an earlier loop, which is why it can create much more complex flowcharts.
On the other hand, unlike with backwards GOTO the use of forwards GOTO makes a program more clear than any alternatives that have been proposed. For example, several languages use loop labels to enable the termination of multiple nested loops.
This is worse than with GOTO. The loop termination statement must include the label of the loop that must be terminated, e.g. it must look like "break LABEL_7" or "exit LABEL_7. This is no improvement over "goto LABEL_7".
Moreover when you try to follow the flow of control in such a program, from the loop terminating instruction you must go back, frequently to another page, because you have several levels of loops, and then from the label you must scan forward for a matching end of loop. This is significantly slower than just going from the loop terminating instruction to the point where it actually transfers the control.
I also agree with you that even if have not use the word "flowchart" that was what I meant, i.e. the use of unrestricted GOTO results in the most general kind of flowchart, without any constraints. I also agree that with more or less effort any flowchart, i.e. any program can be understood, but the goal of a programmer is to never make a program harder to understand than strictly necessary for solving the given problem.
My main point however, is that allowing backwards GOTO and allowing loops is not the same thing, which is the reason why Knuth in his recommendations of how to combine GOTO with structured programming and the language MESA allowed loops, but not backwards GOTO.
A loop is terminated by a backwards GOTO, but the pairs formed by the implicit label from the beginning of a loop and the backwards GOTO from the end of a loop behave like pairs of parentheses, i.e. they may only be nested and they may not be interleaved.
An arbitrary backwards GOTO does not have this restriction, i.e. it can jump in the middle of an earlier loop, which is why it can create much more complex flowcharts.
On the other hand, unlike with backwards GOTO the use of forwards GOTO makes a program more clear than any alternatives that have been proposed. For example, several languages use loop labels to enable the termination of multiple nested loops.
This is worse than with GOTO. The loop termination statement must include the label of the loop that must be terminated, e.g. it must look like "break LABEL_7" or "exit LABEL_7. This is no improvement over "goto LABEL_7".
Moreover when you try to follow the flow of control in such a program, from the loop terminating instruction you must go back, frequently to another page, because you have several levels of loops, and then from the label you must scan forward for a matching end of loop. This is significantly slower than just going from the loop terminating instruction to the point where it actually transfers the control.
On those points, I never intended a disagreement.
My only point was that in some cases it can be easier to reason with the structured steps that go to each other. Specifically, it was far easier than I expected when I started playing with that style later in life.
It was funny, as I originally put in some labeled breaks in a tight java event loop at a big company. Every wave of new employees would try to refactor into something that didn't need that. Every wave introduced a crap ton of bugs before reverting to the labeled break.
At least in that case, I granted that it was a slightly difficult part of the program to reason about. Was doable, but still difficult. What was a huge surprise to me was how much easier it was to put together a set of steps if I wasn't trying to bend them into the control structures of most programming languages.
I suspect the big thing that made this easier for me, was that you are encouraged to have the steps such that they don't jump from the middle of the step. You have what you are going to do, then you have a choice of what to do next. If you find that you wanted to jump out from the middle of a step, you break that into two steps.
My only point was that in some cases it can be easier to reason with the structured steps that go to each other. Specifically, it was far easier than I expected when I started playing with that style later in life.
It was funny, as I originally put in some labeled breaks in a tight java event loop at a big company. Every wave of new employees would try to refactor into something that didn't need that. Every wave introduced a crap ton of bugs before reverting to the labeled break.
At least in that case, I granted that it was a slightly difficult part of the program to reason about. Was doable, but still difficult. What was a huge surprise to me was how much easier it was to put together a set of steps if I wasn't trying to bend them into the control structures of most programming languages.
I suspect the big thing that made this easier for me, was that you are encouraged to have the steps such that they don't jump from the middle of the step. You have what you are going to do, then you have a choice of what to do next. If you find that you wanted to jump out from the middle of a step, you break that into two steps.
From John Cowan:
TAGBODY doesn't actually require continuations, delimited or undelimited, just proper tail calling. A macro can rewrite each section of the TAGBODY into a procedure nested within a `let` that tail-calls its successor, and the body of the `let` tail-calls the first procedure. (GO tag) is then equivalent to just (tag). This is a great way of doing state machines. Chicken has a tagbody egg, I think.
TAGBODY doesn't actually require continuations, delimited or undelimited, just proper tail calling. A macro can rewrite each section of the TAGBODY into a procedure nested within a `let` that tail-calls its successor, and the body of the `let` tail-calls the first procedure. (GO tag) is then equivalent to just (tag). This is a great way of doing state machines. Chicken has a tagbody egg, I think.
Constrained GOTO semantics sounds a lot like delimited continuations. Indeed I think Scheme continuations are a little too powerful for regular use by having the possibility of global effect (like longjmp). Delimited continuations make the effect more local.
Delimited continuations always bounced off of me. In theory, they should be a lot like coroutines? I think, in practice, I just never really internalized all that goes into managing the current "environment" for a piece of code that is managed by the call state.
Like, I have a few partial mental models for everything that they pull together. I haven't really tried to build on that, though. Should put some time to that.
Like, I have a few partial mental models for everything that they pull together. I haven't really tried to build on that, though. Should put some time to that.
You could implement coroutines with deliminated continuations, which is probably the best way to use deliminated continuations.
Effect handlers would like to have a word.
If you'll excuse the self-post, here's a blog post on goto with delimited continuations.
https://rd.nz/2009/03/goto-in-scala.html
It uses an experimental compiler plugin for the Scala compiler. It's typesafe at compile time. At runtime unfortunately it relies on exceptions for control flow.
https://rd.nz/2009/03/goto-in-scala.html
It uses an experimental compiler plugin for the Scala compiler. It's typesafe at compile time. At runtime unfortunately it relies on exceptions for control flow.
Do you use it mostly as "labeled breaks" or to throw the values out of closures?
I haven't used it much at all, to be clear. I just found it surprisingly fun the last few times I played with it.
The specific thing it made a lot easier was implementing algorithms the way that Knuth writes them down. Which is very much a set of steps with specific calls on what step to go to next.
I think the reason I found it fun to play with was that I found that style of laying out what needed to be done was easier to work with than the standard breakdown that making everything a function or an object seems to require. For me, it was a lot easier.
Edit: I have one of the times I used this here: https://taeric.github.io/many_sums.html I did not put any effort into cleaning up that code, though. So it can probably work as an argument in either direction. :D
The specific thing it made a lot easier was implementing algorithms the way that Knuth writes them down. Which is very much a set of steps with specific calls on what step to go to next.
I think the reason I found it fun to play with was that I found that style of laying out what needed to be done was easier to work with than the standard breakdown that making everything a function or an object seems to require. For me, it was a lot easier.
Edit: I have one of the times I used this here: https://taeric.github.io/many_sums.html I did not put any effort into cleaning up that code, though. So it can probably work as an argument in either direction. :D
[deleted]
[deleted]
will only terminate if pasted into a REPL, not if invoked from a file.
This is because every top-level form in the REPL has an implicit continuation "return to the REPL and read more input".
So after "continuation called" is printed, we go back to the prompt and await more input.
However, if this code is saved in a file and you run it (e.g. "guile my-script.scm") then the continuation of the top-level `displayln` call is the top-level `begin` form, and we enter an infinite loop.