The Seasoned Schemer

 Posted on January 31, 1996  |  5 min  |  904 words  |  Daniel P. Friedman  |  Matthias Felleisen
Friedman, Daniel P. and Felleisen, Matthias and Bibby, Duane, 1996. The Seasoned Schemer. 2nd edition, The MIT Press,

Abstract: The notion that "thinking about computing is one of the most exciting things the human mind can do" sets both The Little Schemer (formerly known as The Little LISPer) and its new companion volume, The Seasoned Schemer, apart from other books on LISP. The authors' enthusiasm for their subject is compelling as they present abstract concepts in a humorous and easy-to-grasp fashion. Together, these books will open new doors of thought to anyone who wants to find out what computing is really about. The Little Schemer introduces computing as an extension of arithmetic and algebra; things that everyone studies in grade school and high school. It introduces programs as recursive functions and briefly discusses the limits of what computers can do. The authors use the programming language Scheme, and interesting foods to illustrate these abstract ideas. The Seasoned Schemer informs the reader about additional dimensions of computing: functions as values, change of state, and exceptional cases. The Little LISPer has been a popular introduction to LISP for many years. It had appeared in French and Japanese. The Little Schemer and The Seasoned Schemer are worthy successors and will prove equally popular as textbooks for Scheme courses as well as companion texts for any complete introductory course in Computer Science.

Call with current continuation: the letcc macro

The fundamental macro letcc in the form

(letcc k body ...)
binds k to the current continuation [1][2][3][4] in body... expressions; for the sake of clarity, it expands to
(continuation-capture
  (λ (cont) (let1 (k (λ (arg) (continuation-return cont arg))) body ...)))
where continuation-capture and continuation-return are defined in [5] and based on [6] by Marc Feeley, respectively.

Implementation

(module
  (aux continuation)
  *
  (import scheme (chicken base) (chicken continuation) (aux base))
  (define-syntax-rule
    (letcc/call hop body ...)
    (call-with-current-continuation (λ (hop) body ...)))
  (define-syntax-rule
    (letcc hop body ...)
    (continuation-capture
      (λ (cont)
          (let1 (hop (λ (arg) (continuation-return cont arg))) body ...))))
  (define (callcc f) (letcc k (f k)))
  (define-syntax-rule
    (letcc* next ((v exp) ...) body ...)
    (letcc success
           (let* ((v (letcc next (success exp))) ... (next success))
             body
             ...)))
  (define-syntax-rule
    (literal else)
    (trycc (next exp ...) (else body ...))
    (letcc* hop ((v (let1 (next (τ (hop (void)))) exp)) ...) body ...)))

Tests

test/letcc/multiarg: pass

(define (test/letcc/multiarg _) (⊦= 'a (letcc k (k 'a))))

((eta 0.0) (memory #(6291456 2041488 1048576)) (stdout "") (stderr ""))

test/letcc*: pass

The frame in [7] is of inspiration of the letcc* macro.

(continuation-capture
  (λ (cont)
      (let1 (success (λ (arg) (continuation-return cont arg)))
            (let* ((v (letcc ⤶ (success vexpr))) (⤶ success)) body ...))))

(define (test/letcc* _)
  (⊦= '(1) (letcc* ⤶ ((v (cons 1 '())) (w (cons 2 v))) (cons 4 w)))
  (⊦= '(2 1)
        (letcc* ⤶ ((v (cons 1 (⤶ '(1)))) (w (cons 2 v))) (cons 4 w)))
  (⊦= '(4 3 1)
        (letcc*
          ⤶
          ((v (cons 1 (⤶ '(1)))) (w (cons 2 (⤶ (cons 3 v)))))
          (cons 4 w)))
  (⊦= '(1 2) (letcc* ⤶ ((v (cons 3 (⤶ '(2))))) (cons 1 v)))
  (⊦= '(3 2) (letcc* ⤶ ((v (cons 1 (⤶ '(2))))) (⤶ (cons 3 v))))
  (⊦= '(2) (letcc* ⤶ ((v (cons 3 (⤶ '(2))))) (cons 1 (⤶ v))))
  (⊦= '(4 2)
        (letcc* ⤶ ((v (cons 3 (⤶ '(2))))) (cons 1 (⤶ (cons 4 v))))))

((eta 0.001) (memory #(6291456 2043600 1048576)) (stdout "") (stderr ""))

test/trycc: pass

(define (test/trycc _)
  (⊦= 5 (trycc (✗ (+ 1 (✗)) (+ 2 3)) (else (cons 3 '()))))
  (⊦= 3 (trycc (✗ (+ 1 2) (+ 2 (✗))) (else (cons 3 '()))))
  (⊦= '(3) (trycc (✗ (+ 1 (✗)) (+ 2 (✗))) (else (cons 3 '())))))

((eta 0.0) (memory #(6291456 2044640 1048576)) (stdout "") (stderr ""))

test/letcc/dfs: pass

(define (test/letcc/dfs _)
  (define t1 '(a (b (d h)) (c e (f i) g)))
  (define t2 '(1 (2 (3 6 7) 4 5)))
  (letrec ((*saved* '())
           (col '())
           (witness (gensym))
           (dft-node
             (lambda (tree)
               (cond ((null? tree) (restart))
                     ((not (pair? tree)) tree)
                     (else
                      (letcc cc
                             (push! (τ (cc (dft-node (cdr tree)))) *saved*)
                             (dft-node (car tree)))))))
           (restart
             (τ (if (null? *saved*)
                   witness
                   (let1 (cont (pop! *saved*)) (cont)))))
           (dft-comb
             (lambda (another)
               (lambda (tree)
                 (let1 (node1 (dft-node tree))
                       (if (eq? node1 witness)
                         witness
                         (list node1 (dft-node another)))))))
           (dft2 (lambda (v)
                   (if (eq? v witness)
                     (reverse col)
                     (begin (push! v col) (restart))))))
    (⊦= '(a b d h c e f i g) (dft2 (dft-node t1)))
    (set! col '())
    (⊦= '((a 1)
            (a 2)
            (a 3)
            (a 6)
            (a 7)
            (a 4)
            (a 5)
            (b 1)
            (b 2)
            (b 3)
            (b 6)
            (b 7)
            (b 4)
            (b 5)
            (d 1)
            (d 2)
            (d 3)
            (d 6)
            (d 7)
            (d 4)
            (d 5)
            (h 1)
            (h 2)
            (h 3)
            (h 6)
            (h 7)
            (h 4)
            (h 5)
            (c 1)
            (c 2)
            (c 3)
            (c 6)
            (c 7)
            (c 4)
            (c 5)
            (e 1)
            (e 2)
            (e 3)
            (e 6)
            (e 7)
            (e 4)
            (e 5)
            (f 1)
            (f 2)
            (f 3)
            (f 6)
            (f 7)
            (f 4)
            (f 5)
            (i 1)
            (i 2)
            (i 3)
            (i 6)
            (i 7)
            (i 4)
            (i 5)
            (g 1)
            (g 2)
            (g 3)
            (g 6)
            (g 7)
            (g 4)
            (g 5))
          (dft2 ((dft-comb t2) t1)))))

((eta 0.0) (memory #(6291456 2053256 1048576)) (stdout "") (stderr ""))
References
[1] https://docs.scheme.org/schintro/schintro_141.html
[2] https://en.wikipedia.org/wiki/Call-with-current-continuation
[3] https://ds26gte.github.io/tyscheme/index-Z-H-15.html
[4] Continuations by example
[5] Module (chicken continuation)
[6] A Better API for First-Class Continuations
[7] The Seasoned Schemer: page 89, see rember1* definition.
callcc 

See also