Talk:Call-with-current-continuation

"function" vs. "procedure"

What is in most programming languages called a function, is called a procedure in Scheme; yet the article uses the word "function". Should this not be changed/fixed? 217.10.109.18 (talk) 13:29, 26 February 2017 (UTC)

Cyclic reference

The "Yin Yang Puzzle" uses a (dead) reference to Yin Wang's blog. In Web Archive, it refereed to a Stack Overflow question, and that question referred Wikipedia.

So this is a cyclic reference. We don't know when this puzzle was invented, and who invented this. --137.147.203.50 (talk) 06:14, 23 May 2015 (UTC)

Rationale

This article does not address the issue of why call/cc was created, and what for... -- Karada 15:37, 5 March 2006 (UTC)

The rationale should be found in Continuation. --Kanjy 11:38, 7 March 2006 (UTC)

Inaccuracies and false claims

I have removed several inaccuracies and false claims, plus some awkward writing from this page.

I intend to elaborate on the logical implications of call/cc when I have time.

Matthias.f 15:06, 27 July 2007 (UTC)Matthias.f

Logging call/cc

It took me a while to figure out what was happening in the second example, leaving me with the impression that continuations are both:

a) A really clever idea that has expanded my understanding of what a program is.

b) Perhaps the most powerful program-obfuscation technique since self-modifying code.

In order to better understand them, I wrote the following. The first is a modification of call/cc that logs what is happening, and the second is a heavily annotated variant of the list-iteration example, in which I tried to separate each aspect of its use of continuations. I'm no Scheme programmer, and my experience of Lisp has been limited to a few weeks some years ago, but if they help, feel free to use them.

; A convenience function to apply 'display' to a list of items.

(define (displayList . items) (for-each display items))


; call-cc does what call/cc does, but displays what's going on before and after.

; 'toBeCalled' is the function that is to be called by call-with-current-continuation.

; If given, 'id' is a string (or whatever) that appears in every line that is
; displayed, so you can use it to tag each use of call-cc with a unique identifier,
; and therefore distinguish between them in the log.

(define (call-cc toBeCalled . id)
  ; The lambda expression allows me to display the continuation that is created here
  ; (the 'current continuation') before actually calling 'toBeCalled' with that
  ; continuation as its argument.

  ; 'return-value' captures the value that call-with-current-continuation returns, 
  ; so I can display it before returning it to the original caller.

  (let* (
	 (tag (if (> (length id) 0) (car id) "?")) ; for when no id is given.
	 
	 (return-value (call-with-current-continuation 
			(lambda (continuation) 
			  (displayList "call-cc of '" toBeCalled "' at '" tag 
				       "' creates continuation " continuation "\n")
			  (toBeCalled continuation))))) ; the actual call-with-cc

    (displayList "\tcall-cc returned " return-value " to '" tag "'\n")
    return-value))

; Function make-yielding-iterator creates a closure such that each time function get-next
; is called, it returns the next element in the iteration over the given list.

; Get-next interacts with function yield, which is called in each pass of the  iteration.
; Yield stores the current list element in yielded-value, then calls a continuation that
; resumes in get-next; this then takes the saved value and returns it to its caller. When
; get-next is next called, it calls a continuation that resumes the iteration from where
; yield jumped out.

(define (make-yielding-iterator list)
  ; The initial values of these two variables are unimportant, as they are both reset
  ; before use.

  (define yielded-value #f)       ; The next element to be returned.
  (define return-to-get-next #f)  ; A continuation for returning control to get-next.



  ; resume-iteration (below) is the procedure to be called, by get-next, in order to
  ; resume iterating over the list. On all but the first use, we will want to resume
  ; from where we last yielded a value, but on the first call, we want to 'resume'
  ; by starting the iteration. Therefore, resume-iteration is initially defined as a 
  ; function for performing the iteration. Thereafter, each time yield returns control
  ; to get-next, resume-iteration is set to a continuation for resuming from where 
  ; the loop yielded, i.e. a continuation representing the remainder of the iteration.

  ; The first call of resume-iteration (via call/cc) also initializes return-to-get-next
  ; so that yield will return control to get-next.

  (define (resume-iteration get-next-continuation)
    (set! return-to-get-next get-next-continuation)
    (for-each yield list) ; The iteration itself.
    (yield #f))           ; Yield 'false' after we fall off the end of the list.
    


  ; The  functions get-next and yield call/cc each other alternately. They depend on
  ; the fact that when you call call/cc with a continuation as its argument, execution
  ; resumes where that continuation was created, and the thing returned there is a 
  ; continuation for resuming from where you came.

  (define (yield current-list-element)
    (set! yielded-value current-list-element) ; Save it, for get-next to return to the caller.

    ; Resume in get-next, giving it a continuation to come back here for the next iteration.
    ; When get-next returns here, it gives us a new continuation for going back to it next time.

    (set! return-to-get-next (call-cc return-to-get-next "yield")))



  (define (get-next)
    ; Resume in yield, giving it a continuation to come back here after the next iteration.
    ; When yield returns here, it gives us a new continuation for going back to it next time.

    (set! resume-iteration (call-cc resume-iteration "get-next"))

    yielded-value) ; Return the last-yielded value to the caller.



  ; 'Export' get-next by returning it from make-yielding-iterator
  ; (nothing else of this closure will be visible outside it.)

  get-next)   ; end of make-yielding-iterator



(define get-next-digit (make-yielding-iterator `(0 1 2 3 4 5 6 7 8 9)))
(define get-next-alpha (make-yielding-iterator `("a" "b" "c" "d" "e")))

(get-next-alpha) ; a
(get-next-digit) ;     0
(get-next-digit) ;     1
(get-next-alpha) ; b
(get-next-alpha) ; c
(get-next-digit) ;     2
(get-next-alpha) ; d
(get-next-digit) ;     3
(get-next-alpha) ; e
(get-next-digit) ;     4
(get-next-alpha) ; false
(get-next-digit) ;     5
(get-next-alpha) ; false

Raybo0 13:35, 19 September 2007 (UTC)

(call/cc (lambda (x) x)) is a no-op, right?

Mathias.f added the call to the first example: http://en.wikipedia.org/w/index.php?title=Call-with-current-continuation&oldid=147459612

And I took it out just now because I'm pretty sure it's redundant and not helpful in explaining the concept.

I'm a Lisp/Scheme n00b, but as I read it, it forms an anonymous function which invokes its only arg, then calls that anonymous function with the current continuation. The function invokes that continuation causing execution to continue where it 'left off'. If I'm wrong, the surrounding text should be edited to explain that line. Crag (talk) 02:35, 9 January 2008 (UTC)

Actually, in the line (display (call-with-current-continuation (lambda (x) x))) the lambda expression does not invoke the continuation, it simply returns it. However, I don't see what this line adds to the example, and I agree that this line should have been removed from the example. — Tobias Bergemann (talk) 07:41, 9 January 2008 (UTC)

as said above, it isn't a no-op. and it is demonstrating that you can get your hands on the continuation, as a first class, displayable object that you can sort of look at, which is something impossible in most languages. also, if you don't know what code does, and can't execute it to find out, you probably shouldn't be editing pages about it. so i put it back. —Preceding unsigned comment added by 67.177.213.111 (talk) 20:34, 21 January 2008 (UTC)

I don't see what this line adds to the example as the example doesn't show how the continuation is displayed, and the way continuations are displayed isn't specified in the Scheme standards anyway. Worse, it breaks the flow between the definition of f in the example and its use. Frankly, I find the line more confusing than enlightening and am tempted to remove it again or at least move it. —Tobias Bergemann (talk) 07:52, 22 January 2008 (UTC)

please move it - it's very confusing! I would do it myself, but I don't know what to say about it (and I don't want to just delete it because somebody tried that already and was undone). 149.159.72.139 (talk) 04:07, 30 January 2008 (UTC)

It is true that (call/cc (lambda (x) x)) doesn't have any side effects, but it certainly does return a value, and that value has interesting properties when you call it. That's the point. 64.81.85.44 (talk) 22:41, 6 August 2009 (UTC)

It is just an identity function. i.e. a neutral element

(define (id x)x defines id as (lambda(x)x). If you compose any function f with id, it is like multiplying by 1 or adding 0.

(f (id x))=(id (f x))=(f x) for all x.

you are confused because you are not seeing pure functional examples. Continuations allow us to program in a pure functional style which has an algebra of programs. That allow us to do things elegantly without confusing side effects. Scheme has imperative features, but that should be avoided whenever it is possible. This article could benefit a lot if more pure functional examples could be chosen. See the proposed change to the first example below to understand how it is evaluated. I only showed how it is evaluated, but I don't like because of the side effects, that are confusing. — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 08:29, 25 March 2018 (UTC)

dynamic-wind, call-with-values, call-with-input-file etc.

The semantics of call/cc where changed with the move from R⁴RS to R⁵RS. Should the article explain the interaction between call/cc and dynamic-wind, call-with-values, call-with-input-file etc. (see e.g. Revised⁶ Report on the Algorithmic Language Scheme - Non-Normative Appendices - 11.9 Control features) or would this be too much detail? —Tobias Bergemann (talk) 09:41, 4 February 2008 (UTC)

IMO the article should be language-agnostic, considering that continuations aren't specific to Scheme. Obviously the fact that Scheme's call/cc was the original means that some implementation details might be interesting from a historical point of view, but otherwise I think it's irrelevant. Hairy Dude (talk) 23:50, 8 May 2008 (UTC)

Agree in part. Personally I hate that cancer that makes more an more complex a programming language each successive version. R⁴RS is simple and beautiful. To explain something it is always better to use the most simple example that makes the concept clear, sticking to R⁴RS to explain the concept is fine from my point of view. However, many readers will be starting with some RⁿRS, for n>4 version, each with more and more bells and whistles. Being call/cc essentially Scheme, the article should include the variants that you mentioned. However not to explain the main concept, but to explain how it evolved in later Scheme versions. — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 08:05, 25 March 2018 (UTC)

Continuations as a generic control mechanism

Anecdotally, it's possible to code any pure Haskell monad using Cont (the continuation monad). Quick googling turned up this set of slides on the topic, though a proper paper would be nice. Hairy Dude (talk) 23:47, 8 May 2008 (UTC)

Generator example

Hi, I'm a little confused about the (define generate-one-element-at-a-time ...) example. It doesn't appear that (set! return ...) is ever going to change the value of return because the computation will always be cut short when (return element) is executed. I tested the full code snippet without the (set! return ...) and it seemed to behave exactly the same. I'm new to call/cc so I didn't want to change it incase I was mistaken. thoughts? --Marty.neal (talk) 20:26, 2 March 2009 (UTC)

I've restored (set! return ...). When call/cc returns, as it does when the saved continuation is invoked, it's important that the *new* return fails. If your return continuations are virtually identical, you'll never see the problem, but if they are different, then there's a problem. Removing the set! has return never change, and so each invocation of the cursor only returns to the continuation of the *first* call. 64.81.85.44 (talk) 22:08, 6 August 2009 (UTC)

The explanation why (set! return ..) is important is not convincing, especially in this case where digits are generated regardless of whether (set! return ..) is there or not. Therefore I'm opting to change the generator code to be minimalistic. That said I regard it as very much irrelevant whether this generator could be applied on any collection, that has conceptually nothing to do with call/cc. Ultraxs (talk) 14:00, 29 July 2011 (UTC)

Without this construct, "return" is bound only at first application, so subsequent use of the generator will be for *that* continuation. This will result in undesired behavior. A simple example will suffice: simply first use a generator you defined in an expression like (* 10 (mygenerator)), followed by (* 1 (mygenerator)). Without set! on the return symbol, the second application will use the continuation of the first application, resulting in (* 10 ...) instead of the desired (* 1 ...). Heycarnut (talk) 01:58, 14 January 2012 (UTC)

Hi, I'm also a little new to lisp and am also confused with the second example, namely the generator stuff. Surely, since the control-state variable is assigned the continuation, this continuation cannot accept an argument as input? This should be make clearer for non-lisp programmers such as myself. 81.98.101.31 (talk) 16:53, 6 July 2009 (UTC)

Continuations are invoked with arguments, and the arguments are the return values of the call/cc call which created the continuation. 64.81.85.44 (talk) 22:08, 6 August 2009 (UTC)

Why is there an (return 'you-fell-off-the-end) as last statement in procedure control-state? Why not simply 'you-fell-off-the-end? Ultraxs (talk) 14:00, 29 July 2011 (UTC)

Why introducing a name for procedure generator? This name is never used. Again, examples should be minimalistic and free of clutter. Propose to change example to

 (define (generate-one-element-at-a-time lst)
   ...
   ;; (-> X u 'you-fell-off-the-end)
   ;; This is the actual generator, producing one item from a-list at a time
   (lambda ()
     (call-with-current-continuation control-state))
  )

Ultraxs (talk) 14:00, 29 July 2011 (UTC)

What happens exactly in the second invocation of (generate-digit)? There will be a (call-with-current-continuation resume-here), where resume-here is the inner and previously saved state. Then it appears that the inner call to call/cc just returns with a ... well .. continuation object. But where is this object coming from? Which one is it?. According to explanations above, it must be the outer continuation object, but why? Ultraxs (talk) 14:00, 29 July 2011 (UTC)

Simpler example

I just posted a simpler example to Talk:Continuation of implementing threading with call/cc. The problem with the example in this article is that its hard to read: it mashes up (confuses) the job-dispatching queue with the fork/yield concepts. The Talk:Continuation separates the two, making the code both easier to read, and also making it clear how to write a general job scheduler, (which has nothing at all to do with call/cc). linas (talk) 17:24, 23 August 2009 (UTC)

Exception handling

This aricle should also provide an example of implementing exception handling with call/cc. linas (talk) 17:24, 23 August 2009 (UTC)

Why? Does something very special or useful happen? David Spector (user/talk) 15:07, 27 February 2013 (UTC)

Continuation passing is an elegant solution to exception handling. See Mitchell's programming languages book for an example. — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 07:42, 25 March 2018 (UTC)

Implementation of call/cc

Would anyone care to add to the article some code showing how call/cc is implemented? How does it do what it does? Nothingist (talk) 09:29, 14 May 2010 (UTC)

If the underlying implementation is based on continuations, the procedure simply does what its name says: it calls the argument with the current continuation as an argument.

If the implementation does not maintain continuations, the effect has to be faked. This is generally impossible to do fully in stack-based implementations because program state is lost when the stack is unwound. Tasty monster (=TS ) 10:58, 14 May 2010 (UTC)

Let's assume the former; could you please show how call/cc is implemented? This will help people like me that are trying to implement call/cc in other languages that allow closures and CPS but don't have a native implementation of call/cc. Thank you. Nothingist (talk) 11:40, 14 May 2010 (UTC)

Sure. It would be implemented as follows:

call-with-current-continuation(c) is

 let k be the current continuation
 return c(k)

end

Tasty monster (=TS ) 17:54, 14 May 2010 (UTC)

Er, not intended for prime time, by the way. The current continuation is of course an ambiguous term, and in this instance it refers to the continuation of the procedure call to call-with-current-continuation. The term "return" which I so quaintly use to express the notion that call-with-current-continuation may return a value, refers to the action of calling the current continuation with the return value as an argument. And now I must go and lie down for a while until my garbage collector completes its essential work. Tasty monster (=TS ) 14:09, 15 May 2010 (UTC)

Google Groups broke

I hate this Google Groups can you change it to a proper Usenet link rather than a web page? --Zzo38 (talk) 08:51, 25 August 2012 (UTC)

C-like semantics

For people that have a background in other programming languages, it might be best to explain call/cc mechanics using classic programming terminology.

Perhaps something like this:

call/cc can be thought of as supplying a mechanism which duplicates the current thread in a cooperative multi-tasking environment. We call this mechanism "the current continuation". In this model of computation, each time the continuation is used, we are instantiating a new cooperative thread, and transferring control to it -- the value passed to the continuation will be the result of call/cc in that thread.

For example, in (call/cc (lambda (return-in-cloned-thread) ...)) the name return-in-cloned-thread can be thought of as a routine that creates a new thread which is a copy of the thread that the call/cc appeared in, and in that thread the value passed to return-in-cloned-thread will be the return value from call/cc.

When the stack is deep and the computations leading to use of the continuation are complex, an efficient implementation probably implements lazy stack copying and we need to rely on our garbage collector to reclaim threads which can no longer be accessed. In restricted cases, static analysis and/or full stack copying may be a sufficient replacement for these mechanisms.

In other words, explaining call/cc in terms of threading concepts may be useful for people that already understand those threading concepts. (The exact wording was not the point -- I am sure my suggested wording here can be improved on.)

It may be important to draw a distinction between this "threading model" and any "native thread implementation" because they would typically not be the same. But I think this analogy could be useful for some people. Do others (especially frequent users of call/cc) agree? — Preceding unsigned comment added by 173.73.2.10 (talk) 23:14, 31 October 2012 (UTC)

I agree, I came here looking for a coroutines example. Which can be written by threads, but with setjmp/longjmp too among other ways. — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 07:38, 25 March 2018 (UTC)

English

There are several problems with the english in this page, but I don't understand the page's subject well enough to correct them: "he obtained a scheme program that known as the yin-yang puzzle"; " It was then being customary [2] to show while discussing call/cc"; "Every statements". Masonmilan (talk) 11:12, 29 December 2016 (UTC)

First example revisited

I don't remember well and I do not have Scheme at hand now. But I rewrote the first example as follows:

(define (id x) x)

(define (f return)
  (do (return 2)
      3))

(display (f id)) ; displays 3 returning 3
; (display (do (lambda(r)((r 2)3))) id) ; definition of f
; (display (do (id 2) 3)                ; apply f to 2
; (display (do 2 3))                    ; apply id to 2
; (display 3)                           ; (do 2 3) reduces to 3
; 3                                     ; display 3 and return 3

(display (call/cc f)) ; displays 2 returning 3
; (f (lambda (c)(display c)))           ; apply f to the cc of display
; (do ((lambda (c)(display c))) 2) 3)   ; definition of f 
; (do (display 2) 3)                    ; substitute c by 2
; 3                                     ; display 2 then reduce to 3

I am not sure of the (do ...) statement, could anyone check it, please.

I do not think that this example elucidate the use of call/cc because it is based on side effects. That is not the key advantage of a functional language. Although the use of monad composition to explain continuation composition is not easy to write for non pure functional programmers.

I didn't change it in the article, not just because I am not sure of the syntax, but I am also not sure that it is an example that really elucidate the use of call/cc. — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 07:33, 25 March 2018 (UTC)

Second example rewritten without call/cc

The second example can be rewritten as follows:

;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end)
(define (generate-one-element-at-a-time lst)

  ;; Hand the next item from a-list to "return" or an end-of-list marker
  (define (control-state return)
    (for-each 
     (lambda (element)
               (set! return (call-with-current-continuation
                              (lambda (resume-here)
                                ;; Grab the current continuation
                               (set! control-state resume-here)
                               (return element)))))
     lst)
    (return 'you-fell-off-the-end))
  
  ;; (-> X u 'you-fell-off-the-end)
  ;; This is the actual generator, producing one item from a-list at a time
  (define (generator)
    (call-with-current-continuation control-state))

  ;; Return the generator 
  generator)

(define generate-digit
  (generate-one-element-at-a-time '(0 1 2)))

(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (generate-one-element-at-a-time lst)
  (define (control-state return)
  (define (generator) (call/cc control-state))
  (define (fun element)
      (set! return (call/cc (lambda (resume-here)
                                    (set! control-state resume-here)
                                    (return element) )
  )   )            )

    (for-each fun lst)
    (return 'you-fell-off-the-end))
  

  generator)

(define generate-digit (generate-one-element-at-a-time '(0 1 2)))

(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (generate-one-element-at-a-time lst)
  (define (control-state return)
      (define (generator) (call/cc control-state))
      (define (fun element)
         (define (resume resume-here)
            (set! control-state resume-here)
            (return element) 
         )
        (set! return (call/cc resume))
      )

     (for-each fun lst)
     (return 'you-fell-off-the-end) 
  )
  generator
)

(define generate-digit (generate-one-element-at-a-time '(0 1 2)))

(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (generate-one-element-at-a-time lst)
  (define (control-state return)
      (control-state (lambda (k)(define (generator) k)))
      (define (fun element)
         (define (resume resume-here)
            (set! control-state resume-here)
            (return element) 
         )
        (resume (lambda(k)(set! return k)))
      )
     (for-each fun lst)
     (return 'you-fell-off-the-end)
  )
  generator
)

(define generate-digit (generate-one-element-at-a-time '(0 1 2)))

(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

It seems to work like setjmp/longjmp coroutines in C. But is hard to understand. If someone could transform it into one without side effects, i.e. without set! and more clear code for human beings, that would be an improvement for the article. — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 16:37, 25 March 2018 (UTC)

Ying Yang example is clearer, it can be transformed as follows

The example yin-yang can be transformed as follows

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

replacing (lambda(c)c) by id, this is shorter:

(define (id c) c)

(let* ((yin  ((lambda (k) (display #\@) k) (call/cc id)))
       (yang ((lambda (k) (display #\*) k) (call/cc id))) )
    (yin yang) 
)

the meaning of call/cc is:

(define (id c) c)

(let* ((id (lambda(cc)(yin  ((lambda (k) (display #\@) k) cc))))
       (id (lambda(cc)(yang ((lambda (k) (display #\*) k) cc)))) )
    (yin yang)
)

Although it has the side effects with of calls to display it is a clear example of coroutines. Should we replace the example with the (call/cc id) version above?

I would prefer to rewrite the example building an stream instead of making display calls. Any volunteer to do it? — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 17:13, 25 March 2018 (UTC)

Please extend the Curry-Howard section

Continuations are related with negation in intuitionist logic, but the specific relation with call/cc is not clear enough in this article. Could anyone extend that section, please. — Preceding unsigned comment added by 2806:107E:4:9B98:218:DEFF:FE2B:1215 (talk) 17:56, 25 March 2018 (UTC)

The second example in introduction is wrong

(e1 (call/cc f)) is claimed to be equivalent to (f (lambda (c) (e1 c))), but that only holds when f does call the continuation it receives from call-cc. f can also return a value v normally, in which case the example's final value will be (e1 v). Vincent Semeria (talk) 19:52, 20 August 2021 (UTC)