Home » forums » LtU Forum

Background of call/cc

Trying to get to grips with continuations I was looking at Scheme's call/cc (not being a Scheme programmer). I think I have a sufficient idea what a continuation is, I think of it as a snapshot of the current call stack. My question now is specifically, why do I have to provide a function argument to call/cc, what is the rational for this design? Why doesn't call/cc just return the current continuation as a value, so I could do whatever I please with it (store it, call it, pass it around, etc.)? On this page, it talks about "Essentially it's just a clean way to get the continuation to you and keep out of the way of subsequent jumps back to the saved point.", but I'm not getting it. It seems unnecessarily complicated. Can anybody enlighten me?

By thomash at 2009-09-13 02:03 | LtU Forum | previous forum topic | next forum topic | other blogs | 10737 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

What you want can easily be

What you want can easily be gotten in Scheme with (call/cc id) (where id is (lambda (x) x)). However, if you think of the type of that, e.g. call/cc usually has the type ((a -> b) -> a) -> a, you find that the type is infinite; you end up with a -> b = a. This can be demonstrated in a trivial example. The type of call/cc, not incidentally, corresponds to Pierce's law from classical propositional logic.

(call/cc (lambda (c) (c 4))) is equivalent to 4

Now what would that look like for a putative get/cc defined as follows:
(define (get/cc) (call/cc id))

Well if we just did,
(let ((c (get/cc))) (c 4))
we get a type error. c is a continuation when get/cc first returns and then when we apply c it is bound to 4 on its second return and we get (4 4) which is a type error. Indeed, if we ever apply c to anything but a procedure type, we'll get a type error using get/cc (modulo intensional type analysis). So get/cc will rarely ever work. As an aside, (let ((c (get/cc))) (c c)) is type correct and is an infinite loop.

Here's a more systematic "get/cc".

(define (em) 
  (call/cc 
    (lambda (c)
      (cons 'right (lambda (x) (c (cons 'left x)))))))

The trivial example above would be written:

(let ((c (em)))
  (if (eq? (car c) 'right) ((cdr c) 4) (cdr c)))

This will work.

In Haskell-like notation, the type of em is Either a (a -> b), this happens to correspond to the law of the excluded middle from classical propositional logic. The definition above of em in terms of call/cc is a proof that Pierce's law implies Excluded Middle. The implication goes the other way as well, we could define call/cc in terms of em.

(define (call/cc f)
  (let ((c (em)))
    (if (eq? (car c) 'right)
        ((cdr c) (f (cdr c)))
        (cdr c))))

So each is equipotent, but call/cc is quite a bit more perspicuous and is usually the pattern that is desired. You can see exactly how call/cc allows you to "keep out of the way." 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. Basically, call/cc keeps the use of the continuation out of the continuation, whereas with get/cc or em, the continuation contains its use and so (usually) you need to add a test to the beginning of the continuation (i.e. immediately following get/cc / em) to separate the "using the continuation parts" from the "rest of the continuation" parts.

Occassionally em is what you want but not usually. Simply use em or get/cc from above for a while and you'll quickly find why call/cc was the chosen primitive. And just to beat a hobby horse of mine, I think call/cc wasn't the best choice and a closely related operator usually called "control" is a better choice (not counting delimited continuations.) The key difference is (E (control (lambda (_) 1))) evaluates to 1 regardless of what E is, as opposed to (E (call/cc (lambda (_) 1))) which evaluates to (E 1).

By Derek Elkins at Sun, 2009-09-13 02:50 | login or register to post comments

Thanks, this looks really

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

By thomash at Sun, 2009-09-13 12:43 | login or register to post comments

the setjmp/longjmp analogy

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

By Thomas Lord at Sun, 2009-09-13 17:43 | login or register to post comments

Thanks for making the

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.

By thomash at Sun, 2009-09-13 20:50 | login or register to post comments

What you write about

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.

By thomash at Mon, 2009-09-14 22:09 | login or register to post comments

Originally in Scheme ...

... there was a special form catch, with the syntax (catch identifier form form ...). This looked like MacLisp or Common Lisp catch or later languages' try ... catch syntax, but was much more general, because the identifier was bound to a procedure to be invoked to escape the catch rather than a value to be thrown, and this procedure (like all procedures) had indefinite scope. It was then noted by implementers that flexibility was gained if the body forms were packed up into a procedure instead which took the escape procedure as its argument.

You can recover the traditional Scheme catch thus:

(define-syntax catch
  (syntax-rules ()
    ((catch id form . forms) (call/cc (lambda (id) form . forms)))))

By johnwcowan at Sun, 2009-09-13 04:01 | login or register to post comments

A Better API for First-Class Continuations

Marc Feeley wrote a paper called A Better API for First-Class Continuations that may be relevant.

By Manuel J. Simoni at Sun, 2009-09-13 15:08 | login or register to post comments

Thanks for the pointer,

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.

By thomash at Sun, 2009-09-13 21:02 | login or register to post comments

Analogy with 'let'

One way to think of it is by analogy to 'let': you can express let in terms of lambda, i.e.

  (let ((x expr)) body) == ((lambda (x) body) expr)

Similarly, 'let/cc' (a let which binds the current continuation to a variable) can be expressed in terms of call/cc and lambda:

  (let/cc x body) == (call/cc (lambda (x) body))

This hints that call/cc should be considered a kind of primitive, rather than something you usually use directly. As a primitive, its design makes some sense (although there are certainly alternatives), even though it's not what you'd normally want for direct use.

By Anton van Straaten at Sun, 2009-09-13 18:41 | login or register to post comments

Yes, thinking of letcc and

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?

By Ehud Lamm at Sun, 2009-09-13 19:07 | login or register to post comments

Primitive attraction

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.

By Anton van Straaten at Sun, 2009-09-13 21:51 | login or register to post comments

I was hoping that the

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 ;-)

By Ehud Lamm at Sun, 2009-09-13 23:50 | login or register to post comments

I can easily follow your

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?!

By thomash at Mon, 2009-09-14 20:26 | login or register to post comments

Burrowing

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.

By Anton van Straaten at Tue, 2009-09-15 08:33 | login or register to post comments

You haven't explained why

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.

By thomash at Tue, 2009-09-15 17:11 | login or register to post comments

CPS-conversion makes it less strange

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

By Thomas Lord at Mon, 2009-09-14 00:12 | login or register to post comments

I forwarded this page

to David Madore.

Anyway, the best source of information on this subject is Hayo Thielecke's paper, An Introduction to Landin’s “A Generalization of Jumps and Labels”. This gives you insight into the basic idea of introducing control to functional programming. You can also read Olivier Danvy's papers Defunctionalization at Work and Refunctionalization at Work, which described John Reynolds later contributions in hindsight.

By Z-Bo at Tue, 2009-09-15 19:49 | login or register to post comments

Thanks for the pointers, the

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

By thomash at Tue, 2009-09-15 21:03 | login or register to post comments