Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Notes

Call with Current Continuation

This discussion is about continuations. We have them built into our language, calc, and also Scheme. Wouldn't it be cool if we could reach in and grab one?!

Yes! In Scheme, continuations are first-class objects.

Hy Lisp Review

  • Hy doesn't use continuations
  • Hy uses a stack (Python's)
  • Is really just "syntactic sugar" for Python
  • They could implement Hy like we did Calc in Python
  • Hy does have a limited closures (Python's closures)

Scheme Review

For this discussion we need to remember a couple of functions from Scheme:

  • map
  • for-each

Recall that map takes a function $f$ and applies it to each item in a list:

In [1]:
(map (lambda (s) (string-append s "!")) '("hello" "there" "little" "bunny"))
Out[1]:
("hello!" "there!" "little!" "bunny!")

for-each does the same, but doesn't return the list:

In [2]:
(for-each (lambda (s) (string-append s "!")) '("hello" "there" "little" "bunny"))

So, what is for-each good for? It is good for when you are interested in a function's side-effects rathern than its return value. For example, you might have a function that makes a robot move:

In [49]:
(define move
  (lambda (motion)
    (printf "Robot is moving ~s~%" motion)))
In [50]:
(for-each move '("backward" "forward" "up and down" "right" "left"))

Robot is moving "backward"
Robot is moving "forward"
Robot is moving "up and down"
Robot is moving "right"
Robot is moving "left"

Call with Current Continuation

Consider this simple function below:

In [34]:
(define f
 (lambda (return)
    (return 2)
    3))

What will the following give?

In [35]:
(f (lambda (x) x))
Out[35]:
3

In fact, it doesn't really matter what return does, it can only compute something, which is ignored.

But, if we pass f into call-with-current-continuation then something surprising happens:

In [36]:
(call-with-current-continuation f)
Out[36]:
2

Let's look at a couple more examples:

In [51]:
(call-with-current-continuation
    (lambda (return)
      (begin
        (print "One")
        (return #t)
        (print "Two")
        #f)))

"One"
Out[51]:
#t
In [6]:
(call-with-current-continuation
    (lambda (exit)
      (map (lambda (x)
                  (if (eq? x 'blue)
                      (exit x)
                      (symbol->string x)))
                '(this is a blue bunny in your yard))))
Out[6]:
blue
In [ ]:
(call-with-current-continuation
    (lambda (exit)
      (map (lambda (x)
                  (if (eq? x 'blue)
                      (exit exit)
                      (symbol->string x)))
                '(this is a blue bunny in your yard))))
In [29]:
(define generator
  (lambda (lst)
 
  ;; Hand the next item from a-list to "return" or an end-of-list marker
  (define control-state
   (lambda (yield)
    (for-each 
     (lambda (element)
               (set! yield (call-with-current-continuation
                              (lambda (resume-here)
                                  ;; Grab the current continuation
                                  (set! control-state resume-here)
                                  (yield element)))))
     lst)
    (yield '())))
 
  ;; This is the actual generator, producing one item from a-list at a time
  (define start-generator
    (lambda ()
      (call-with-current-continuation control-state)))
 
  ;; Return the generator 
  start-generator))
 
(define next
  (generator '(0 1 2)))
In [30]:
(next) ;; 0
Out[30]:
0
In [31]:
(next) ;; 1
Out[31]:
1
In [32]:
(next) ;; 2
Out[32]:
2
In [33]:
(next)
Out[33]:
()

call-with-current-continuation is a lot of typing! You can abbreviated it to call/cc

Consider this:

In [71]:
(call/cc (lambda (k) (k k)))
Out[71]:
#<procedure>

Time travel, again

In [8]:
(define cont #f)

(begin 
  (print 1)
  (print 2)

  (set! cont (call/cc (lambda (k) (k k))))

  (print 3)
  (print 4)
 )

1
2
3
4
In [9]:
(cont cont)

3
4
In [10]:
(cont cont)

3
4
In [11]:
(cont (lambda (i) i))

3
4
In [12]:
(cont (lambda (i) i))
Out[12]:
#<procedure>
In [57]:
(+ 1 (call/cc
       (lambda (k)
         (+ 2 (k 3)))))
Out[57]:
4
In [58]:
(define redo #f)

(+ 1 (call/cc
       (lambda (k)
         (set! redo k)
         (+ 2 (k 3)))))
Out[58]:
4
In [59]:
(redo 42)
Out[59]:
43
In [60]:
(redo 100)
Out[60]:
101

Implementing amb, fail

In [4]:
; current-continuation : -> continuation
(define (current-continuation) 
  (call-with-current-continuation 
   (lambda (cc)
     (cc cc))))

; fail-stack : list[continuation]
(define fail-stack '())

; fail : -> ...
(define (fail)
  (if (not (pair? fail-stack))
      (error fail "back-tracking stack exhausted!")
      (begin
        (let ((back-track-point (car fail-stack)))
          (set! fail-stack (cdr fail-stack))
          (back-track-point back-track-point)))))

; amb : list[a] -> a
(define (amb choices)
  (let ((cc (current-continuation)))
    (cond
      ((null? choices)      (fail))
      ((pair? choices)      (let ((choice (car choices)))
                              (set! choices (cdr choices))
                              (set! fail-stack (cons cc fail-stack))
                              choice)))))

; (assert condition) will cause
; condition to be true, and if there
; is no way to make it true, then
; it signals and error in the program.
(define (assert condition)
  (if (not condition)
      (fail)
      #t))

We're looking for dimensions of a legal right triangle using the Pythagorean theorem:

$ a^2 + b^2 = c^2 $

And, we want the second side (b) to be the shorter one:

$ b < a $

In [5]:
(let ((a (amb (list 1 2 3 4 5 6 7)))
      (b (amb (list 1 2 3 4 5 6 7)))
      (c (amb (list 1 2 3 4 5 6 7))))
    
  (assert (= (* c c) (+ (* a a) (* b b))))
  (assert (< b a))

  ; Print out the answer:
  (display (list a b c))
  (newline))

(4 3 5)

How would you implement call/cc?