Wednesday, November 29, 2006

Prompts - Their Interaction with Dynamic Wind

Delimited Continuations in MzScheme

A Tour - Part 1

Prompts
  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
           (dynamic-wind
            (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)))
;=>
;pre
;value/before
;post
;inside let v= #<continuation>
;pre
;value/after= result
;post
;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 source.schemekeys.net. Check it out, by the time you read this today's code will likely be available for download.

--kyle

Wednesday, November 22, 2006

Control Delimiters and Their Hierarchies

If you haven't heard, PLT has released DrScheme version 360.

See Jens Axel Søgaard's recent post for an exhaustive overview.

One of the exciting new features is that of prompts (or runs) and marks for call-with-continuation. To get a good introduction to these terms and what it brings to the table of your desktop DrScheme, please read Sitaram and Felleisen ( Lisp and Symbolic Computation ) Control Delimiters and Their Hierarchies , from 1990. That's right, we're just now realizing the foresight of these two academics, some sixteen years after they published. I've only browsed the paper once, but it really motivates me to tackle the new constructs we've been handed by the PLT team. Sometimes new constructs come to a language and everyone's excited for a while, but they just amount to syntactic sugar candy. What Sitaram and Felleisen proposed, and we now have implemented is most definitely not sugar candy.

Dorai Sitaram is author of the highly acclaimed introductory text on Scheme,

Teach Yourself Scheme in Fixnum Days, 1998-2004. If somehow you've stumbled upon this blog and want to know what all the fuss is about check it out online. Matthias Felleisen teaches at Northeastern, and his principle area of research is summed up by the title of a book for which he is first author, How to Design Programs, 2003. This is another excellent resource, not just for learning Scheme, but for learning the art of programming. For those of you, who like myself grew up writing c and then c++, you may prefer the K&R style taken by Kent Dybvig in his classic text, The Scheme Programming Language, 3rd ed., also available online. When I was a kid you actually had to go to a store and buy these things made principally of paper with pages, they called them books.

We'll be back on topic next posting. --kyle

Monday, November 13, 2006

In search of robust Scheme comments

Ever since I got bitten by the Scheme bug, I've been trying out different styles of documentation within the comments of the code. Currently I use block style comments #| .. comment .. |#, within which I place XML code. A typical source file of mine starts off like this:

#|
<header>
<name>source.scm</name>
<author>Kyle Smith</author>
<created date="2006-11-13"/>
<description>
Source.scm is designed ...
</description>
</header>
|#

The advantage to this is that I can save my source.scm to source.xml, and use standard XML tools to process the document. The downside is that once I've got myself into a thousand line source file, heavily documented with XML, there are countless cases where I've forgotten to close an element, made a typo on one of the elements or forgotten the slash in the closing element. All this adds up to a very long boring session with Stylus Studio, correcting my silly mistakes.

So, I went in search of a new way to do things. What I've come up with I call Active Comments, because they don't reside inside Scheme comments, they are live Scheme code. Because they are active code, and because most of my comments occur around the definitions of functions and syntax, they have been designed such that their expansion does not break definition context. They have some similarity to sxml, except that there is no @ sign before attributes. There is, however, an @ sign that introduces an Active Comment. They look like this:

(@ function)
(@ name fact)
(@ author Kyle Smith)
(@ created ((date "2006-11-13")))
(@ description compute factorial of number? -> n)
(@code
(define fact
  (lambda (n)
    (or (and (= n 0) 1)
        (* n (fact (- n 1))))))
)

Most Active Comments are simply expanded to:

(begin (define name (lambda () '(e1 e2 ...))))

Since the element @code actually encloses a definition it is defined as:

(define-syntax @code
  (syntax-rules ()
    ((_ ((i1 v1) ...) e1 e2 ...)
      (begin (define 'i1 'v1) ... e1 e2 ...))))

What do I get for all this trouble? The formatting of the date attribute is enforced by the syntax from which the created element is defined. All the element names must be spelled correctly. Closing a comment is just a matter of balancing parentheses. All of these things happen each time I write a comment, by the native Scheme syntax checker.

Well, that's just the start of the story. In my next post I discuss my efforts to design syntax for Active Comments that allows them to be arbitrarily nested within other Active Comments. Let me just say that it can be done, but it comes at a price.

--kyle