Does call/cc in Scheme the same thing with yield in Python and JavaScript?

Question

Does call/cc in Scheme the same thing with yield in Python and JavaScript?

I am not clear about generators. In my opinion, yield gives a language the ability to generate iterators without pain. But I am not sure whether I am right.

Does call/cc in Scheme has something related to yield in other languages? If so, are they the same thing, or what is the difference?

Thanks!

This question is extremely broad and probably not fit for the SO format. It’s worth saying that `yield` *is* equivalent in expressive power to a restricted form of *delimited* continuations. However, continuations are more general than generators. — Alexis King, Jun 13 '17 at 08:09

Sylwester · Accepted Answer · 2017-06-14T22:26:50.180

call/cc is a much more general language feature than generators. Thus you can make generators with call/cc, but you cannot make call/cc with generators.

If you have a program that computes values and use those values in other places its basically a step machine.. One might think of it as a program that have one function for each step and a continuation for the rest of the steps. Thus:

(+ (* 3 4) (* 5 6))

Can be interpreted as:

((lambda (k)
  (k* 3 4 (lambda (v34)
            (k* 5 6 (lambda (v56)
                      (k+ v34 v56 k)))))
 halt)

The k-prefix just indicate that it's a CPS-version of the primitives. Thus they call the last argument as a function with the result. Notice also that the order of evaluation, which is not defined in Scheme, is in fact chosen in this rewrite. In this beautiful language call/cc is just this:

(define (kcall/cc kfn k)
  (kfn (lambda (value ignored-continuation)
         (k value))
       k))

So when you do:

(+ (* 3 4) (call/cc (lambda (exit) (* 5 (exit 6))))) 
; ==> 18

Under the hood this happens:

((lambda (k)
  (k* 3 4 (lambda (v34)
            (kcall/cc (lambda (exit k)
                        (exit 6 (lambda (v6)
                                 (k* 5 v6 k)))
                      k))))
 halt)

By using the substitution we can prove that this actually does exactly as intended. Since the exit function is invoked the original continuation is never called and thus the computation cancelled. In contrast to call/cc giving us this continuation that doesn't seem obvious it's no magic in CPS. Thus much of the magic of call/cc is in the compiler stage.

(define (make-generator procedure)
  (define last-return values)
  (define last-value #f)
  (define (last-continuation _) 
    (let ((result (procedure yield))) 
      (last-return result)))

  (define (yield value)
    (call/cc (lambda (continuation)
               (set! last-continuation continuation)
               (set! last-value value)
               (last-return value))))

  (lambda args
    (call/cc (lambda (return)
               (set! last-return return)
               (if (null? args)
                   (last-continuation last-value)
                   (apply last-continuation args))))))

(define test 
 (make-generator
   (lambda (collect)
     (collect 1)
     (collect 5)
     (collect 10)
     #f)))

(test) ; ==> 1
(test) ; ==> 5
(test) ; ==> 10
(test) ; ==> #f (procedure finished)

One might make a macro to make the syntax more similar, but it's just sugar on top of this.

For more examples I love Matt Mights page with lots of examples on how to use continuations.

With chicken-4.9 at least (I have not used more recent versions) the lambda expression which initializes 'last-continuation' has to invoke 'last-return' on completing, as otherwise on completion of 'procedure' control would return to the continuation of the first invocation of the generator, not the last. It is also an idea to catch any exception raised by 'procedure' and then return a lambda which re-raises the exception in the environment of 'last-return' in order to have the exception emerge from the last invocation of the generator, and not from the first. — Chris Vine, Jun 14 '17 at 20:55
@ChrisVine Amazingly I never catched this because my continuations were delimited, but I did get a loop when wrapping it in a `let`. Thanks! — Sylwester, Jun 14 '17 at 22:28
Yes for schemes which have delimited continuations (guile and racket, possibly others) they are much easier to use for this particular purpose. When using full continuations (chicken, chez and others) you have to delimit the continuations by hand with a second one, and it is easy to slip up when doing so, as here. Anyway, I ended up with the code I referred to in my separate answer. — Chris Vine, Jun 15 '17 at 10:19
By the way, I still don't think that your revised code deals with exceptions correctly. Change your test code to replace '(collect 10)' with '(raise 'x)' and put a 'guard' block around the first call to '(test)' and be surprised. — Chris Vine, Jun 15 '17 at 10:46

score 1 · Answer 2 · answered Jun 13 '17 at 13:02

Here's code to define a generator:

(define-syntax define-generator
  (lambda (x)
    (syntax-case x (lambda)
      ((stx name (lambda formals e0 e1 ...))
         (with-syntax ((yield (datum->syntax (syntax stx) 'yield)))
           (syntax (define name
             (lambda formals
               (let ((resume #f) (return #f))
                 (define yield
                   (lambda args
                     (call-with-current-continuation
                      (lambda (cont)
                        (set! resume cont)
                        (apply return args)))))
                 (lambda ()
                   (call-with-current-continuation
                    (lambda (cont)
                      (set! return cont)
                      (cond (resume (resume))
                      (else (let () e0 e1 ...)
                            (error 'name "unexpected return"))))))))))))
        ((stx (name . formals) e0 e1 ...)
          (syntax (stx name (lambda formals e0 e1 ...)))))))

There are examples of the use of generators at my blog. Generators use call-with-current-continuation, in a manner similar to yield in Python, but are much more general.

score 1 · Answer 3 · answered Jun 13 '17 at 22:33

1

You can implement generators with call/cc. Here is an example:

coroutines.ss

They work in a similar way to python and ECMAScript generators.

answered Jun 13 '17 at 22:33

Chris Vine

677
3
7

Does call/cc in Scheme the same thing with yield in Python and JavaScript?

3 Answers3