Wednesday, November 29, 2006

Prompts - Their Interaction with Dynamic Wind

Delimited Continuations in MzScheme

A Tour - Part 1

  1. Their Interaction with dynamic-wind
  1. What does dynamic-wind protect and how?

This is the beginning of a series of posts on the new delimited continuation operators offered by PLT MzScheme v360. We are going to discuss prompts first, but before we get to prompts I thought it best that we all have a firm foundation in dynamic-wind. Dynamic-wind has got to be among the more complex control structures we have in R5RS Scheme, and it gets its complexity through the use of continuations. To put us all on the same page, I selected an example from section 6.4 of the PLT MzScheme Language Manual and tweaked it a bit for purposes of illustration. You are encouraged to try out the examples in the next few posts on your own copy of DrScheme, and read the short sections 6.4 and 6.5. I use various helper functions and syntax for debugging purposes and will make these available to you in the posts as they come up.

With today's post I've included two debug print syntactic forms that facilitate shorthand methods of printing multiple expressions followed by a newline. Their names are cout and couta. cout writes the expressions, while couta displays the expressions to the (current-output-port), which by default is set to your display monitor. Just paste these in above today's code and everything should run as advertised.

Debug Printing Syntax

 (define-syntax cout
  (lambda (stx)
    (syntax-case stx ()
      ((_ e1 e2 ...)
        #'(begin (printf "~s " e1) (cout e2 ...)))
      ((_ e1 ) #'(printf "~s~n" e1))
      ((x ) (identifier? #'x) #'(newline)))))

 (define-syntax couta
  (lambda (stx)
    (syntax-case stx ()
      ((_ e1 e2 ...)
        #'(begin (printf "~a " e1) (cout e2 ...)))
      ((_ e1 ) #'(printf "~a~n" e1))
      ((x ) (identifier? #'x) #'(newline)))))

Escape by means of let/ec and call/cc

(let ([v (let/ec out
            (lambda () (couta "pre "))
            (lambda ()
              (couta "value/before ")
              (let ([retval (call/cc out)])
                (couta "value/after=" retval) #f))
            (lambda () (couta "post "))))])
  (couta "inside let v=" v)
  (and v (v 'result)))
;inside let v= #<continuation>
;value/after= result
;inside let v= #f

The value of this snippet of code is in discerning the nature of dynamic-wind's behavior in the face of adversity. The author has arranged for both an escape from, and an escape into the value-thunk. Note first that the majority of code occurs within the value expression for the variable v being bound by a let statement. The let statement's body has only two expressions: one prints the value of v and the other conditionally applies (v 'result) if v is not #f. The wording on the example as presented in the manual doesn't correspond with the language used to describe the three (3) different thunks of dynamic-wind, so I changed them to match, and I added my own code to display the value-thunk both before and after the (call/cc out) is invoked. I think overall it makes it easier to explain the behavior.

Speaking of which, here are the take home points to remember regarding dynamic-wind's behavior when stressed by continuations that either escape from or into the value-thunk. No special handling is given for escapes that might occur inside the pre and post-thunks. It protects the value-thunk by its continuation that enforces the following three (3) rules. First, its normal continuation is for pre-thunk to be called before value-thunk, which is called before post-thunk, and finally to return the value of the evaluation of value-thunk as the value of the entire dynamic-wind expression. Second, if an escape is made out of the value-thunk, dynamic-wind guarantees that the post-thunk will be called before the escape occurs. Third, if an escape is made into the value-thunk, it guarantees that the pre-thunk will be called before control is returned to the place of initial escape in the value-thunk, and finally the post-thunk is called.

With these three rules in mind the behavior of the code at hand is easily explained. Initially, control enters the let where its continuation to bind the value of v is assigned to out by let/ec. Subsequently, dynamic-wind is entered and due to its own continuation it enters the pre-thunk, where pre is displayed. Next, dynamic-wind causes control to pass to the value-thunk where value/before is displayed. Next, while still in the value-thunk we have an escape caused by out being assigned to the continuation of dynamic-wind, at which point dynamic-wind passes control to the the post-thunk, where post is displayed before allowing the escape to occur. Having escaped, v is bound to the continuation stored in the value of out via the let/ec and we enter the body of the let statement. The first expression within the body of the let statement displays, inside let v= #<continuation>. But we have set a trap for v, so as v is evaluated in the and expression, being itself non-false, it is applied to, and thus assigned the value of the symbol result.

Since v is a continuation, having been assigned the value result also triggers a transfer of control back to the origin of that continuation. This results in an escape back into the body of the value-thunk. However, dynamic-wind, due to its own native continuation forces control to pass first through the pre-thunk, where pre is displayed. Now control continues with the initial continuation of dynamic-wind and it passes through the remainder of the value-thunk, where value/after= result is displayed. Finally the value-thunk ends with the expression #f. Dynamic-wind then insures that the post-thunk will be called after the value-thunk, so post is displayed. Now, the continuation of dynamic-wind ends by binding the value of the value-thunk (#f) to v, and we enter the body of the let once again, where inside let v= #f is displayed. The final expression of the let body is evaluated, and since this time v is #f, the evaluation of (and #f ...) is #f and we have the value #f as the value of the entire expression. If you have your code within a module as I did when writing this post, that's it. For those of you who simply load the code in at top-level you will see and additional #f, which is simply the value of the entire expression being echoed by the REPL.

That's dynamic-wind in a nutshell. If you tackle every dynamic-wind bug with the same three rules in hand you should be able to explain about every standard R5RS scenario that you might encounter. In the next section of this part of our tour, we'll see our old friend dynamic-wind again, but this time it will have to deal with call-with-continuation-prompt and company. The story gets quite a bit more interesting.

All of the code, including utility functions and syntax that might come in handy in any Scheme project, discussed as we go along on this tour will be available for download soon at Check it out, by the time you read this today's code will likely be available for download.