Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!uwvax!daffy!cat9.cs.wisc.edu!schaut
From: schaut@cat9.cs.wisc.edu (Rick Schaut)
Newsgroups: comp.lang.scheme
Subject: Re: call/cc
Keywords: continuations
Message-ID: <4459@daffy.cs.wisc.edu>
Date: 14 Mar 90 07:49:20 GMT
References: <1990Mar8.064319.28399@brutus.cs.uiuc.edu>
Sender: news@daffy.cs.wisc.edu
Distribution: comp
Organization: U of Wisconsin CS Dept
Lines: 111

In article <1990Mar8.064319.28399@brutus.cs.uiuc.edu> sane@clitus.cs.uiuc.edu (Aamod Sane) writes:
| Beginners question:
| 
| 	I tried to understand the operation of call/cc from Dybvigs text
| and the R3.99 without success. Can someone give a good explanation here or
| a reference? It is said that the interepreter uses continuations which are 
| not visible normally  etc. but I dont quite get this.

Most respondants have answered this portion, so I'll not add to the foray.

| I would also like examples/references on the Continuation
| Passing style (just building of lambdas, not the call/cc variety). 
| I know of examples such as gcd of a list where you can escape
| if a 1 is encountered without doing any computation, by building lambdas
| and using them only if 1 is not found.

But, noone has answered this yet, so here goes.  The following is a function
that maps a function to a "tree" where a list represents a node in the
tree.  The top level list is the root node, and intermediate level lists
are intermediate nodes (and are the children of the list which contains
them), and any atoms are the leaves.  For example, (1 (2 3) (4 (5 6)) 7)
is one such tree.

The catch is that the mapped function may return a value indicating that
the value that was passed to it was not acceptable (for whatever reason).
The tree-map function, then, should return a list of the form

	('not-yet <unacceptable input value>).

If the map was applied successfully, then the return sould be

	('done <mapped tree>).

The code that implements this is:


(define (tree-map filter tree)
  (let ((result (tree-mapc filter tree (lambda(x)x))))
    (if (and (not (null? result)) (list? result) (equal? 'not-yet (car result)))
      result
      (list 'done (revall result)))))

(define (tree-mapc filter tree cont)
  (cond
    ((null? tree) (cont '()))
    ((atom? tree)
      (let ((result (filter tree)))
	(if (equal? result '*not-acceptable*)
	  (list 'not-yet tree)
	  result)))
    (else
       ; first, map the car of the tree using a fresh continuation
       ; i.e. build a continuation for the sublist
      (let ((result (tree-mapc filter (car tree) (lambda(x)x))))
	(if (and
	      (not (null? result))
	      (list? result)
	      (equal? 'not-yet (car result)))
	  result ;<- stop the recursion here, we've found an error
	   ;else cons the result onto the current continuation and map the cdr
	  (tree-mapc filter (cdr tree) (lambda(x)(cons result (cont x)))))))))

(define (revall l)
  (cond ((atom? l) l)
        ((null? l) l)
	(else
          (let ((e  (if (list? (car l)) (revall (car l)) (car l))))
            (append (revall (cdr l)) (list e))))))


This is _very_ ugly code, and sufficient reason to understand and use
call/cc.  The equivalent code that uses call/cc is:


(define (tree-map filter tree)
  (let ((result (call/cc (lambda(return)(tree-mapc filter tree return)))))
    (if (and (not (null? result)) (list? result) (equal? 'not-yet (car result)))
      result
      (list 'done result))))

(define (tree-mapc filter tree return)
  (cond
    ((null? tree) '())
    ((atom? tree)
      (let ((result (filter tree)))
	(if (equal? result '*not-acceptable*)
	  (tree-mapc 
	    filter
	    (call/cc (lambda(context)(return (list 'not-yet tree context))))
	    return)
	  result)))
    (else (cons
            (tree-mapc filter (car tree) return)
	    (tree-mapc filter (cdr tree) return)))))


Note also that this version uses call/cc to return control to the top-level
tree-map function.  This allows the calling routine to provide a substitute
value back to tree-map, and tree-map will continue the original computation
using the substituted value.  As you mentioned, interpreters use this same
construct when they encounter an error.  They use a call/cc to invoke a
debugging routine which, in turn, allows the user to correct the data/code.
The corrections are then dropped back into the computation in which the
error occurred and the computation is restarted where it left off.  If your
interpreter has a continue option in its break package, then it is using
a call/cc in the error trap.

--
Rick (schaut@garfield.cs.wisc.edu)

"I'm a theory geek; we use Turing machines!"--Gary Lewandowski