sane@clitus.cs.uiuc.edu (Aamod Sane) (03/08/90)
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. 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. Thanks , Aamod Sane sane@cs.uiuc.edu
harlan@silver.ucs.indiana.edu (Pete Harlan) (03/10/90)
sane@cs.uiuc.edu (Aamod Sane) writes: | 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. Chapters 16 and 17 of _Scheme and the Art of Programming_, by Springer/Friedman, McGraw-Hill/MIT Press, gives a thorough introduction to understanding call/cc. It includes many examples of its use, and many exercises for practicing. I highly recommend it. --- Pete Harlan harlan@silver.ucs.indiana.edu
bobg+@andrew.cmu.edu (Robert Steven Glickstein) (03/11/90)
When I was first trying to grok continuations as a Scheme novitiate, I found the sequence below very enlightening. Try to understand what's going on here; I'll post a detailed description in a day or two. > (define (identity-fn x) x) > (define (current-continuation) (call/cc identity-fn)) > (define foo (current-continuation)) > foo #[Continuation] > (foo 10) > foo 10 ______________ Bob Glickstein | Internet: bobg@andrew.cmu.edu Information Technology Center | Bitnet: bobg%andrew@cmuccvma.bitnet Carnegie Mellon University | UUCP: ...!harvard!andrew.cmu.edu!bobg Pittsburgh, PA 15213-3890 | (412) 268-6743 | Sinners can repent, but stupid is forever
schaut@cat9.cs.wisc.edu (Rick Schaut) (03/14/90)
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
dorai@hedera.rice.edu (Dorai Sitaram) (03/17/90)
In article <4459@daffy.cs.wisc.edu> schaut@cat9.cs.wisc.edu (Rick Schaut) writes: >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: > [cps-style code deleted] > >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. The above is OK, but schleps around too many arguments (filter, return) for no good reason. Tweaking a bit (and making do without the 'done tag): (define tree-map (lambda (filter tree) (call/cc (lambda (return) (let loop ([tree tree]) (cond [(null? tree) '()] [(atom? tree) (let ([result (filter tree)]) (if (eq? result 'not-acceptable) (call/cc (lambda (context) (return (list 'not-yet tree context)))) result))] [else (cons (loop (car tree)) (loop (cdr tree)))])))))) Ach, the above is _also_ unsatisfactory code: _two_ call/cc's; the first continuation-grab only contributes towards identifying the entry-point; the second grab doesn't need to be the whole continuation, just the difference between the entry and break points. The so-far best solution, based on one by Felleisen for a similar tree-walk problem in the paper "Theory and Practice of First-class Prompts", uses prompt (P) and the functional-continuation analog of call/cc (F). It certainly is more efficient and IMHO less sledgehammer-like than the call/cc version: (define tree-map (lambda (filter tree) (let loop ([tree tree]) (cond [(null? tree) '()] [(atom? tree) (let ([result (filter tree)]) (if (eq? result 'not-acceptable) (F (lambda (context) (list 'not-yet tree context)))))] [else (cons (loop (car tree)) (loop (cdr tree)))])))) A sample session: > (set! result (P (tree-map double-if-not-0 '(1 2 (3 0 (4 0 5)))))) (not-yet 0 #<procedure>) > (set! result (P ((caddr result) 'debug-insert))) (not-yet 0 #<procedure>) > (set! result (P ((caddr result) 'debug-insert-2))) (2 4 (6 debug-insert (8 debug-insert-2 10))) --dorai ps: (define double-if-not-0 (lambda (n) (if (zero? n) 'not-acceptable (* 2 n)))) ps2: For details about P and F, read the paper, or contact 'most anybody (once) from Indiana (except maybe the veep). Regular Scheme doesn't have them, though it should :-]. -- ------------------------------------------------------------------------------- It may be that the gulfs will wash us down; It may be we shall touch the Happy Isles. -------------------------------------------------------------------------------
dorai@hedera.rice.edu (Dorai Sitaram) (03/17/90)
In article <5832@brazos.Rice.edu> dorai@hedera.rice.edu, I perpetrate a typo:
$
$(define tree-map
$ (lambda (filter tree)
$ (let loop ([tree tree])
$ (cond [(null? tree) '()]
$ [(atom? tree)
$ (let ([result (filter tree)])
$ (if (eq? result 'not-acceptable)
$ (F (lambda (context)
$ (list 'not-yet tree context))))
result ;<-- was left out in the original
;^^^^^^
$ )]
$ [else (cons (loop (car tree))
$ (loop (cdr tree)))]))))
--dorai
--
-------------------------------------------------------------------------------
It may be that the gulfs will wash us down;
It may be we shall touch the Happy Isles.
-------------------------------------------------------------------------------even@idt.unit.no (Even A. Karlsson) (06/30/90)
I have problem concerning call/cc. I want to pass some extra parameter along with the current continuation to a continuation, and I don't see how that is possible with call/cc. This is useful when modelling the coroutine aspect of classes in Simula where detach implicitly returns an environment (the class object) and a continuation (the rest of the body). Even-Andre Karlsson, IDT, NTH, NORWAY, even@idt.unit.no
raja@silver.ucs.indiana.edu (Raja Sooriamurthi) (06/30/90)
In comp.lang.scheme you write: >I have problem concerning call/cc. I want to pass some extra parameter >along with the current continuation to a continuation, and I don't see >how that is possible with call/cc. This is useful when modelling >the coroutine aspect of classes in Simula where detach implicitly >returns an environment (the class object) and a continuation (the rest >of the body). I don't know if I understand your question clearly, but will the below outline solve your problem? (define receiver (lambda (x) (lambda (current-cont) . body .))) (call/cc (receiver extra-param)) - Raja raja@silver.ucs.indiana.edu
krulwich@ils.nwu.edu (Bruce &) (07/03/90)
In article <1990Jun30.113103.5377@idt.unit.no>, even@idt (Even A. Karlsson) writes: >I have problem concerning call/cc. I want to pass some extra parameter >along with the current continuation to a continuation, and I don't see how >that is possible with call/cc. This is useful when modelling the coroutine >aspect of classes in Simula where detach implicitly returns an environment >(the class object) and a continuation (the rest of the body). Can you be more specific? It seems to me that you should be able to do this by lexically capturing other variables in the closure you give to CALL/CC. Can you give an example of the behavior you want? Bruce Krulwich krulwich@ils.nwu.edu