Lambda the Ultimate

Thanks, this looks really helpful, but I have to consider it for a while.

The page you are learning the gist of continuations from creates confusion by making the setjmp / longjmp analogy.

Here is how you could make call/cc work more like setjmp / longjmp (untested code):

(define-syntax setjmp!
  (syntax-rules ()
    ((_ buffer)
     (call/cc (lambda (k) (set! buffer k) #f)))))

(define (longjmp buffer value)
  (if (not value)
      (buffer #t)
      (buffer value)))

;; So, now you can write something like:

(let (buffer result)
  (set! result (setjmp! buffer))
  (if result
      (...someone longjmped back...)
      (...buffer is the newly captured continuation...)))

That gives you an interface very much like the C interface with one big difference: the setjmp! buffer created remains value even after returning beyond where the variable 'buffer' is created.

Like the C functions, Scheme versions of setjmp!/longjmp have an annoying problem: longjmp *can not* cause the return value of setjmp! to be #f. So, this is a less general way of handling continuations.

This is roughly the same trick Derek is showing with his "right/left" but I thought it might be helpful to relate that more closely to C's setjmp/longjmp.

-t

Thanks for making the effort. I wasn't very happy about the setjmp/longjmp analogy myself, I just quoted this page because it makes an explicit (albeit vague) remark about the rational behind call/cc.

What you write about "keeping out of the way" makes the most sense to me: "With em or get/cc you need to do some kind of test to determine if you have a back-jump or just the initial call."

I also get your argument about the type error in (let ((c (get/cc))) (c 4)), where the extra stack frame introduced into the continuation by calling get/cc is re-instantiated when applying the continuation. (You lost me a bit on those type signatures at the beginning). But this only shows that a naive implementation of get/cc in terms of call/cc would fail; a built-in get/cc wouldn't have this problem.

Your excursion about em, equipotency with call/cc and Pierce's law sounds interesting, and I take from it that you could have either em or call/cc, but you have to make a choice, and there is a slight advantage on the side of call/cc. (I'd rather have em as the basic function, and an additional call/cc defined in terms of it, but hey...). In any case your argument holds about the necessity to test after a call to em. call/cc avoids this as it gets the continuation processing code out of the way.

Thanks for the pointer, though on first glance the paper focusses more on discussing applications of call/cc (and then better approaches to continuations), rather than motivating the existing semantics. I'll have a closer look.

Yes, thinking of letcc and capturing the continuation as a binding construct is helpful. I am not certain about the history of this though.

The claim as a primitive, its [call/cc] design makes some sense surely needs some unpacking, no?

The claim as a primitive, its [call/cc] design makes some sense surely needs some unpacking, no?

I was hoping that the intuition of thinking of lambda as primitive and 'let' as derived would be enough to give the general idea.

But one simple way in which call/cc can be convenient is that macros or functions that use it often take functions as arguments — e.g. typical exception macros, which take exception handler functions as arguments. In the implementation of these macros, the handler functions can often be passed more or less directly to call/cc, using something like (call/cc f) rather than (let/cc k (f k)). In such cases at least, call/cc seems more primitive, since it doesn't force the introduction of a variable that otherwise isn't needed, and which can't be optimized away within Scheme.

This extra variable has the feel of an eta-expansion that is required and can't be reduced (if let/cc is primitive). There's a reason for that: if you define let/cc in terms of call/cc, then (let/cc k (f k)) reduces to (call/cc (lambda (k) (f k))), which reveals the eta expansion that was irreducible in the let/cc version. This can now be eta-reduced away, giving (call/cc f). That makes for a more attractive primitive, I think.

I was hoping that the intuition of thinking of lambda as primitive and 'let' as derived would be enough to give the general idea.

I think the extra explanation is worth it ;-)

I can easily follow your argument comparing let/cc and call/cc, taking "primitive" to mean less high-level (rather than simpler). I could easily see that call/cc might be the older construct of the two.

I'm not so sure concerning the rational you give for call/cc itself. Are you basically saying that call/cc is the way it is, in order to better support common use cases like exception macros?! Though, yes, it might make writing these use cases a bit easier, do you really think call/cc was tailored that way because of them?!

As John Cowan pointed out in his comment entitled "Originally in Scheme ...", Scheme originally had a "catch" construct. 'Catch' is equivalent to let/cc (and has also been known as 'escape').

My explanation was intended to show why it can make sense to move from a form like 'catch' or let/cc to call/cc - essentially, to allow the body of the construct to be parameterized.

Are you basically saying that call/cc is the way it is, in order to better support common use cases like exception macros?! Though, yes, it might make writing these use cases a bit easier, do you really think call/cc was tailored that way because of them?!

More or less, yes, although I'm saying the "more primitive" aspect was probably part of it, too. I don't have references handy that support any of this as the actual reasons for the change in Scheme, but it's consistent with other design decisions in Scheme, which treat lambda as a primitive on which other features are built.

You haven't explained why you find this surprising enough to use repeated ?!s. If it's because you find the call/cc interface unintuitive, that's most likely due to lack of familiarity. It's straightforward enough - the actual semantics of continuations are more complex, and they're largely unaffected by the interface, other than the control delimiter issue which Derek Elkins covered.

Another reason for the shift to call/cc may be that call/cc is a procedure, whereas catch is syntax, which may have been more attractive before Scheme had a standard macro system.

There may also have been some influence from Landin's work - his continuation-capturing J operator was published in 1965, in A Generalization of Jumps and Labels (1998 version), a decade before Scheme's invention. By the time Scheme switched to call/cc, some of this, along with Reynolds' work relating J to escape in Definitional interpreters for higher order programming languages, may have been noticed. J took a lambda argument and passed a continuation to it, so bears some resemblance to call/cc. See Danvy & Millikin's A Rational Deconstruction of Landin's J Operator for some detail about this.

You haven't explained why you find this surprising enough to use repeated ?!s. If it's because you find the call/cc interface unintuitive, that's most likely due to lack of familiarity. It's straightforward enough - the actual semantics of continuations are more complex, and they're largely unaffected by the interface, other than the control delimiter issue which Derek Elkins covered.

I was surprised to think the language designers wanted to save the macro developer an extra (f k), and wanted to find out whether you think that was an original motivation, or more of an "after-the-fact" rational. Also, it seemed more natural to me to have a straight-forward built-in get/cc, saying "here is the continuation, now it's up to you", and put more of the burden on the app developer. But, yes, I'm too unfamiliar with Scheme development to really judge common use cases and idioms. But Derek's argument with the test drove it all home for me.

There may also have been some influence from Landin's work - his continuation-capturing J operator was published in 1965, in A Generalization of Jumps and Labels (1998 version), a decade before Scheme's invention. By the time Scheme switched to call/cc, some of this, along with Reynolds' work relating J to escape in Definitional interpreters for higher order programming languages, may have been noticed. J took a lambda argument and passed a continuation to it, so bears some resemblance to call/cc. See Danvy & Millikin's A Rational Deconstruction of Landin's J Operator for some detail about this.

Thanks for all the additional background material.

A better primitive would be if call/cc worked more like apply:

(apply-with-continuation proc arg2 ... rest-args)

so that we understand (p a1 ... an) to be the same thing as (apply p a1 ... an '()) and then apply-with-continuation to be a variant of apply that happens to copy the implicit and anonymous continuation argument into arg1.

Some (as yet not clearly written) intro for new-comers to Scheme who are comfortable with something like C would be an intro which talks about Scheme data types, code as data, a machine with a small number of registers (like: env, store, code, continuation, i/o-monad) -- various options and trade-offs in instructions sets for that kind of machine -- an assembly language that looks like CPS-converted and closure-converted scheme -- a macro-assembly language -- an expression language on top of that -- the eerie resemblance of the expression language to lambda calculus except for the nagging issues of applicative rather than normal order reduction along with side effects -- the problematics of building an l.c. model of the low-level abstract machine -- then the concept of a least fixed-point. In another track, the pragmatics of using (roughly) standard scheme as a "multi-paradigm" programming language that can reasonably encode the concepts of most other major programming languages.

SICP is the best approximation I've seen so far but it doesn't go nearly far enough because it aims to double as an intro for people who don't have any very well developed intuitions about real-world computers in the first place.

-t

Thanks for the pointers, the papers seem to be pretty much in line with those Anton suggested.