14

Does anyone know if call/cc can be implemented with just lambdas and closures?

It seems that call/cc interrupts the program's flow (like an exception) but lambdas and closures can't do that. Therefore I think call/cc can't be implemented via lambdas and closures.

Any more ideas?

bodacydo
  • 75,521
  • 93
  • 229
  • 319
  • 3
    No, for full continuation support (iow not single shot ones) you will need stack and heap capturing. This all happens on a very low level. – leppie Sep 28 '10 at 09:39
  • 1
    @leppie I'd be happy to upvote that as an answer. – Frank Shearar Sep 28 '10 at 11:03
  • @Frank Shearar: I would iff I had actually successfully implemented them :) Continuations are hard, let's go shopping! – leppie Sep 28 '10 at 11:05
  • The Seaside people (pre-3.0) cheated: having access to the stack, they simply walked the activation records and swizzled them to a stream. On reactivation of the continuation, they unswizzled the stream and carried on. – Frank Shearar Sep 28 '10 at 11:21
  • http://stackoverflow.com/questions/6512/how-to-implement-continuations – Vijay Mathew Sep 28 '10 at 11:44

2 Answers2

12

The question is not particularly clear, since what exactly does "implemented with just lambdas and closures" mean?

In any case, continuations can be used in any language with closures by manually writing in continuation passing style. Then automatic translation into this form can be implemented by extending the compiler, which Lisps typically allow on user level through macros. For example see cl-cont, a library implementing continuations for Common Lisp, which is a language that doesn't have them built in.

Efficient pervasive continuations like in Scheme are likely to be implemented on a lower level directly dealing with the program stack, but this is not a requirement, just an optimization.

Ramarren
  • 2,510
  • 1
  • 15
  • 11
  • 1
    CPS will only work if the underlying language supports tail calls (which it should, in the case of Scheme). – leppie Sep 28 '10 at 11:27
  • 4
    Generally true, but you can in principle wipe the stack frame manually by returning the continuation and arguments upward to some "CPS-driver" loop. – Ramarren Sep 28 '10 at 11:40
  • 3
    CPS will work, but the problem is that it works *only* for code that you control (and can CPS). For example, dealing with libraries becomes difficult, since you need to treat them as foreign calls, even if they're in your language. (And BTW, those "SPC-driver loops" are usually referred to as tampolining.) – Eli Barzilay Oct 05 '10 at 04:49
  • does the common lisp `with-call/cc` really offer the full power of scheme's continuations? This page suggests it's limited/restricted: http://common-lisp.net/project/bese/docs/arnesi/html/Automatically_Converting_a_Subset_of_Common_Lisp_to_CPS.html – hasen Oct 21 '11 at 16:56
  • From my understanding, no. It's really just a syntactic abstraction, but you would not be able to implement something like true coroutines on top of it. – andrew Nov 06 '12 at 19:12
11

In Scheme you can implement call/cc using lambdas when converting to continuation passing style (CPS). When converting into CPS, every occurrence of call/cc can be replaced with the following equivalent:

(lambda (f k) (f (lambda (v k0) (k v)) k))

where k is the continuation to be saved, and (lambda (v k0) (k v)) is the escape procedure that restores this continuation (whatever continuation k0 that is active when it is called, is discarded).

So, to answer your question for Scheme: yes, it can be done.

eljenso
  • 16,789
  • 6
  • 57
  • 63
  • Is this how call/cc is usually implemented on a tail-call optimizing language like Scheme? As a macro? – Byte Jul 04 '17 at 00:37
  • @Byte No, it is not implemented like a macro, but in low level interpreter, by duplicating the stack at the moment of calling call/cc. For more details, see how to implement continuations as first class objects. This is what `call/cc` does. – alinsoar Jun 16 '21 at 09:07