From: Jim Pryor Date: Wed, 15 Sep 2010 14:23:28 +0000 (-0400) Subject: more damn write-up X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=ec653e52b3de86a9d2b2b2311e28281b9041dbe8 more damn write-up Signed-off-by: Jim Pryor --- diff --git a/damn.mdwn b/damn.mdwn index 0b1f1f31..de391d32 100644 --- a/damn.mdwn +++ b/damn.mdwn @@ -198,63 +198,147 @@ So the demonstration we tried in class was pedagogically flawed. It didn't prope So a better demonstration would do without any device like `print` that already incorporates continuations implicitly. Any continuation-manipulation should be fully explicit. +Instead of representing the side-issue expressive contribution by printing "bad", let's instead try to build a pair of side-effect contributions and main-issue assertion. Then what we want would be something like: + ((side-effect . bad) . ((the . man) . (read . (the . (id . book))))) +Only we want to get this from the evaluation of: + (cons (cons 'the 'man) + (cons 'read + (cons 'the + (cons (damn) + 'book)))) + +where `(damn)` doesn't have widest scope. And we don't want to have to recruit all the other semantic material into accepting and passing along a possible expressive argument. + +How to do this? + +It's not immediately clear how to do it with "undelimited" continuations, of the sort captured by `call/cc`. This is the natural first thing to try: + + + (define damn (lambda () (call/cc (lambda (k) (cons (cons 'side-effect 'bad) (k 'id)))))) + + +The idea here is we capture the continuation that the thunk `(damn)` has when it gets evaluated. This continuation is bound to the variable `k`. We supply `'id` as an argument to that continuation. When the main-issues tree is all built, then we return a pair `((side-effect bad) MAIN-ISSUE-TREE)`. + +However, this doesn't work. The reason is that an undelimited continuation represents the future of the evaluation of `(damn)` *until the end of the computation*. So when `'id` is supplied to `k`, we go back to building the main-issue tree until we're finished *and that's the end of the computation*. We never get to go back and evaluate the context `(cons (cons 'side-effect 'bad) ...)`. + +The straightforward way to fix this is to use, not undelimited continuations, but instead a more powerful apparatus called "delimited continuations." These too will be explained in due course, don't expect to understand all this now. + +A delimited continuation is captured not by using `call/cc`, but instead by using a variety of other operators. We'll use the operator `shift`. This substitutes for `call/cc`. The syntax in Scheme is slightly different. Whereas we wrote: + + (call/cc (lambda k ...)) + +we instead write: + + (shift k ...) + +but the behavior is the same. It's just that now our continuation doesn't stretch until the end of the computation, but only up to some specified limit. The limit of the continuation is specified using the syntax: + + (reset ...) + +This is a kind of continuation-scope-marker. There are some interesting default behaviors if you don't explicitly specify where the limits are. But we'll be fully explicit here. + +If a block `...` never invokes a shift, then `(reset ...)` will evaluate just the same as `...`. So for uniformity, we can designate our continuation-scopes even on computations that don't capture and manipulate continuations. + +Going back to the beginning, then. We start with: + + (define damn (lambda () 'id)) + +We evaluate: + + (reset (cons (cons 'the 'man) + (cons 'read + (cons 'the + (cons (damn) + 'book))))) + +Remember, the reset isn't actually *doing* anything. It's not a function that's taking the other material as an argument. It's instead a scope-marker. Here it's not even needed (and in fact in the interactive interpreter, it wouldn't even be needed when we invoke continuations, because of the default position it takes). But we're inserting it to be explicit and uniform. + +Evaluating that gives us: + + ((the . man) . (read . (the . (id . book)))) + + +Now to pair that with an expressive side-issue content, we'd instead define `damn` as: + + (require racket/control) ; this tells Scheme to let us use shift and reset + (define damn (lambda () (shift k (cons (cons 'side-effect 'bad) (k 'id))))) +And voila: + ((side-effect bad) ((the . man) . (read . (the . (id . book))))) ------ End forwarded message ----- +So that's the straightforward way of repairing the strategy we used in class, without using `print`. We also have to switch to using delimited continuations. +Ken Shan, however, pointed out a lovely way to get to the same end-point still using only undelimited continuations (`call/cc`). + +(let ((pragma + ; An ordered pair whose first component is the assertion + ; operator, a unary function, and whose second component + ; is the meaning of "damn", a thunk. + (call/cc (lambda (k) + (cons (lambda (p) p) + (lambda () (k (cons (lambda (p) (cons (cons 'side-effect 'bad) p)) + (lambda () 'id))))))))) + (let ((assert (car pragma)) ; this binds assert to the first element of the pair pragma + (damn (cdr pragma))) ; this binds damn to the second element of the pair pragma + (assert (cons (cons 'the 'student) (cons 'read (cons 'the (cons (damn) 'book))))))) + +We won't do much to explain this. We'll just leave it for you to chew on. -#lang racket -;(define damn (lambda () 'id)) -(define damn (lambda () (call/cc (lambda (k) - ; (k 'id) - (print "Something's bad") - (k 'id) - )))) -(list (list 'the (list (damn) 'man)) - (list 'read - (list 'the (list (damn) 'book)))) + #lang racket + ;(define damn (lambda () 'id)) + (define damn (lambda () (call/cc (lambda (k) + ; (k 'id) + (print "Something's bad") + (k 'id) + )))) + (list (list 'the (list (damn) 'man)) + (list 'read + (list 'the (list (damn) 'book)))) -#lang racket -(require racket/control) -(define damn0 (lambda () - 'id)) -(define damn1 (lambda () - (cons '("side effect" bad) - 'id))) -(define damn2 (lambda () (shift k - (cons '("side effect" bad) - (list (k 'id)))))) + #lang racket + (require racket/control) -(define damn3 (lambda () (shift k - (list (k 'id) - '("side effect" bad))))) + (define damn0 (lambda () + 'id)) + + (define damn1 (lambda () + (cons '("side effect" bad) + 'id))) + + (define damn2 (lambda () (shift k + (cons '("side effect" bad) + (list (k 'id)))))) + + (define damn3 (lambda () (shift k + (list (k 'id) + '("side effect" bad))))) ; Now if we use damn0, our compositional semantics will work OK but ; we don't yet have any expressive contribution: -(list "main content" 'i (list 'like (list 'the (damn0) 'boy))) -; '("main content" i (like (the id boy))) + (list "main content" 'i (list 'like (list 'the (damn0) 'boy))) + ; '("main content" i (like (the id boy))) ; If we use damn1, we've added in the expressive side-effect: -(list "main content" 'i (list 'like (list 'the (damn1) 'boy))) -; '("main content" i (like (the (("side effect" bad) . id) boy))) + (list "main content" 'i (list 'like (list 'the (damn1) 'boy))) + ; '("main content" i (like (the (("side effect" bad) . id) boy))) ; However, the context (list 'the ... 'boy) is now being asked to operate ; on an element (("side effect" bad) . id), and it may complain it doesn't @@ -263,20 +347,20 @@ So a better demonstration would do without any device like `print` that already ; have something different here. ; To get what we want we need to use (delimited) continuations: -(reset (list "main content" 'i (list 'like (list 'the (damn2) 'boy)))) -; '(("side effect" bad) ("main content" i (like (the id boy)))) + (reset (list "main content" 'i (list 'like (list 'the (damn2) 'boy)))) + ; '(("side effect" bad) ("main content" i (like (the id boy)))) ; or to get the side effect at the end: -(reset (list "main content" 'i (list 'like (list 'the (damn3) 'boy)))) -; '(("main content" i (like (the id boy))) ("side effect" bad)) + (reset (list "main content" 'i (list 'like (list 'the (damn3) 'boy)))) + ; '(("main content" i (like (the id boy))) ("side effect" bad)) ; If you're working in the interactive interpreter, the outermost "reset" here ; is already in its default position, so it doesn't need to be explicitly ; specified: -(list "main content" 'i (list 'like (list 'the (damn2) 'boy))) -; '(("side effect" bad) ("main content" i (like (the id boy)))) + (list "main content" 'i (list 'like (list 'the (damn2) 'boy))) + ; '(("side effect" bad) ("main content" i (like (the id boy)))) ; However, if you're executing this as a file, you would need to include explicit resets. @@ -287,29 +371,9 @@ So a better demonstration would do without any device like `print` that already ; explicit continuation, but as Chris said, that's because "print" already ; represents an implicit continuation. -(define damn4 (lambda () (begin (print "bad") 'id))) -(list "main content" 'i (list 'like (list 'the (damn4) 'boy))) -; "bad"'("main content" i (like (the id boy))) + (define damn4 (lambda () (begin (print "bad") 'id))) + (list "main content" 'i (list 'like (list 'the (damn4) 'boy))) + ; "bad"'("main content" i (like (the id boy))) ; - - -#lang racket - -; thanks to Ken! - -(let ((pragma - ; An ordered pair whose first component is the assertion - ; operator, a unary function, and whose second component - ; is the meaning of "damn", a thunk. - (call-with-current-continuation - (lambda (k) - (cons (lambda (prop) prop) - (lambda () (k (cons (lambda (prop) (list 'bad prop)) - (lambda () 'id))))))))) - (let ((assert (car pragma)) - (damn (cdr pragma))) - (assert (list 'the 'student 'read 'the (damn) 'book)))) - -