“Flow control is usually straightforward: sequence, selection, iteration. And many programmers, having been raised on these primary control structures, have a difficult time seeing what other kinds of flow control might be necessary. This article introduces continuations and teaches you to think about flow control in radically new ways.”
That article jumps from trivial to incomprehensible in the middle of one paragraph.
Is it possible to know Scheme well enough to have a clue what’s going on here (say, postdoc level), without knowing all about it already?
You’re partly right; anyone who has taken even an upper-level undergraduate course in programming languages will probably know enough about continuations that this article is redundant. And on the other hand, if you’re a Java programmer and you just want to know what these continuation things are all about, the article is needlessly complex.
I think the article is targeting “enthusiasts”, i.e. smart people who work for a company (say, IBM) where they do a lot of development in Java, but are interested enough in CS that they don’t want to limit themselves to the techniques they’re used to. Someone might teach themselves how to write basic recursive programs in Scheme, and it might never occur to them that something like continuations actually exist. Or someone might be vaguely aware that they exist, but not realize that exceptions are a special case of continuations.
I have to say, it’s somewhat amusing to see all of these developerWorks articles get posted to Slashdot/OSAlert/etc. in between “So-and-so product released” and “Interview with random guy” and “Random guy’s opinion” and “OMG Linux/BeOS!” (full disclosure: I use both) I mean, I’m certainly not complaining… and there are other technical articles on here… but I don’t think that most of the OSAlert readership jumps on these articles (thus the lack of comments).
Fundementally, continuations are actually quite simple. CALL-WITH-CURRENT-CONTINUATION does two things. First, it captures the current continuation. This involves recording the current instruction pointer and the current stack to an object. Second, it passes the continuation object to another function. When later code calls the continuation as a function, passing it a parameter, control returns to the statement right after the CALL-WITH-CURRENT-CONTINUATION call, with the parameter being returned as the return value of the CALL-WITH-CURRENT-CONTINUATION function call. One thing to note is that continuations in Scheme have indefinate extent. That means that you can jump back to a specific instance of a function call, with the stack state preserved, at any time. Scheme implementations accomplish this by allocating stack frames on the heap. Normally, the stack frame is freed when the function returns, just like with C and Java. However, if a continuation is captured that refers to an instance of a function call, a pointer to the stack frame of that instance will be stored in the continuation object. That way the stack frame sticks around, as long as the continuation object does (the GC won’t free the stack from as long as the continuation holds a pointer to it).
It’s helpful to think of continuations as being related to GOTO. Like a GOTO, a continuation allows you to jump to a location in the program. Unlike a GOTO, continuations are structured, so you can only jump to locations where you had previously already captured a continuation, and furthermore continuations respect the organization of the program stack and all scoping rules.
Like GOTO, continuations are primitive, in that they can be used to create all the other control structures that you’re familiar with (and more). The article does a good job in showing how some more familiar control structures map to continuations, though it does hide it behind some advanced Scheme concepts. Specifically, the ‘define-syntax’ stuff uses Scheme’s macro capabilities. A discussion of macros is impossible in this space, but basically, a macro allows you to define some syntax that maps to a larger body of Scheme code. For example, the ‘do’ loop in Scheme is often not built-in. Rather, it’s usually a macro that expands to some Scheme code that implements a do loop using lambdas and recursive function calls.
Yes, it’a pity that the article is so poor, it’s start made me hope that for once it would be comprehensible but as soon as it explains the real thing, it’s garbage once more.
IMHO explaining that continuation are GOTO + a stack frame snapshot copy would be easier to understand..
When you used BASIC you can easily GOTO everywhere as all variable were globals but when variables are stored into a stack, to have non-local GOTOs, you must also store snapshot copys of the stack so that your can continue with the local variables in the same state as before: the continuation is a goto-like function call which restore the stack as it was from the snapshot copy.
Basically, the gist of the article is this:
Feiofoewjewjiphui oijior iojrewuioreow ioio ioio ioewrjoiejrio ioejro iojqw iow io ioio. Rewroi oeriuewhrui uiehruiew uieruiewhew oeiwjr, irewiew!
I hope that clears it up for everyone.
Why mention Linus as a proponent of gotos, when Don Knuth wrote “Structured Programming Using Goto Statements” before Linus was in grade school?
(The paper is sometimes claimed to have been subtitled “‘Goto statement considered harmful’ considered harmful.” it was published in ACM Computing Surveys 6, 4 (1974).)
As far as discussing continuations, what bibliography on that subject would be complete without “Structure and Interpretation of Computer Programs” By Abelson, Sussman, et al?
Even the wikipedia article http://en.wikipedia.org/wiki/Continuation is a better introduction to continuations than this work.
Edited 2006-05-30 23:00
Eh, that’s not entirely fair. The Wikipedia article goes into a lot less detail (and lumps stuff like setcontext in with continuations which I don’t really buy), and doesn’t show you why you’d want to use continuations in the first place.
At least the article in question makes an attempt to show how continuations might be used.
Slip of the pen maybe, but twas Edsger Dijkstra who wrote the Goto/Hamful paper in 1968.
http://www.acm.org/classics/oct95/
Knuth cites Dijkstra several times in his SPUGS paper.
Knuth cites Dijkstra several times in his SPUGS paper.
indeed. It is usual in a formal refutation to cite the paper being refuted.
This is why, when mentioning proponents of GOTO, one cites Knuth, rather than Dykstra.
Slip of the pen maybe, but twas Edsger Dijkstra who wrote the Goto/Hamful paper in 1968.
Yes, which is why the Knuth paper was subtitled “Goto considered harmful considered harmful”… it was in favor of goto (in some cases).
Actually the “Goto considered harmful” was a title choosen by the editor, not by Dijkstra; talk about catchy