Thursday, December 14, 2006

An Introduction to the Prompt Primitives

Delimited Continuations in MzScheme

A Tour - Part 1

Prompts
  1. An Introduction to the Primitives

;In this installment of our tour we're going to digress from dynamic wind to take a long look at the primitive functions available to mzscheme programmers for delimited continuation. It will tuck nicely in when we take up their interaction with dynamic wind in a future post, so no effort will have been lost. Also, beginning with this post you will notice that the paragraphs all start with semicolons, as if this were a source file. Well you would be correct. In an effort to keep the code in these discussions as real as possible, the entire post starts off life as a scheme source file. Further, every effort is made such that you can merely cut and paste this entire post, text and all, into your favorite editor or directly into DrScheme and you should get precisely the same results as I show in the text. This also allows you to play with the examples, which you are encouraged to do, to get a better feel for what these functions are all about.

  (require (planet "78.ss" ("soegaard" "srfi.plt" 1 1)))

  (check-set-mode! 'report-failed)
  

;Before I began this post I made every effort to assure myself that these functions were in fact the most primitive interface to delimited continuations that programmers had access to. A grep through http://svn.plt-scheme.org/plt/trunk/src/mzscheme/src/startup.ss for call-with-continuation-prompt brings up nothing, as well as searches for define\sclall-with-contintinuation and define-syntax\sclall-with-contintinuation. So, it is almost a certainty that these functions originate within the mzscheme kernel (written in c.) And as such they represent for the scheme programmer the most primitive access to the system that is available, without hacking into mzscheme itself.

;As it turns out, and this was confirmed with an e-mail to Jay McCarthy, these function are all that are necessary to implement all four classes of delimited continuation operators that exist, and mzscheme has them all. These classes are referred to as -F-, -F+, +F- and +F+. Dybvig et al. describes them as "a classification of control operators in terms of four variants of F that differ according to whether the continuation-capture operator (a) leaves behind the prompt on the stack after capturing the continuation and (b) includes the prompt at the base of the captured subcontinuation." That is a plus sign before the F means that the operator does leave behind the prompt on the stack after capturing the continuation and a minus sign before the F means that it doesn't. Likewise, a plus sign after the F means that the prompt will be included at the base of the captured subcontinuation, and a minus sign means that it won't be.

;There were some undefined terms in that paragraph, namely: F, prompt and subcontinuation. Dybvig was speaking of the operator F like that of (Felleisen et al. 1987), that captures a continuation, but unlike it, in that it does not abort, is composable, and can capture subcontinuations. A prompt is an extension to a continuation that further describes or delimits it from other continuations. Finally, quoting again from Dybvig, "delimited continuations are also referred to as subcontinuations, since they represent the remainder of a subcomputation rather than of a computation as a whole."

;So now that everything is as clear as mud lets explore our new primitive functions from an empirical and practical point of view, as in what can they do for us? I have prepared some out-takes from the PLT MzScheme Language Manual below that gives us the names of these functions, and their respective usage information. You will also note that I have taken the liberty of renaming all of them in the spirit of call/cc, as they are rather long function names, and I'm a lazy typist. Without any discussion on the matter I will hence forth refer to all of these functions by their shorter names as defined below. You will see later in this post that I further shorten the names of some functions to a character or two, giving them the appearance of operators, and from a purely practical stand point, making the coding flow in a nice composable manner not unlike a let statement.

; Short-hand notations for these long-winded names of delimited continuation functions, in the spirit of call/cc

  ;(call-with-continuation-prompt thunk [prompt-tag handler-proc-or-false]
  (define call/cc/prompt call-with-continuation-prompt)
  ;(default-continuation-prompt-tag)
  (define default/prompt/tag default-continuation-prompt-tag)
  ;(make-continuation-prompt-tag [symbol]
  (define make/prompt/tag make-continuation-prompt-tag)
  ;(abort-continuation-prompt prompt-tag obj ...)
  ;prompt-tag is the target of the abort and obj'(s)
 ; are arguments to prompt-tag's handler-proc
  (define abort/cc abort-current-continuation)
  ;call-with-composable-continuation proc [prompt-tag])
  ;installs NO new prompts, just extends them, 
 ;error is raised if a continuation barrier exists 
 ;between the continuation and the closed prompt-tag.
  (define call/wcc call-with-composable-continuation)
  ;(continuation-prompt-available? prompt-tag [cont]) 
 ;returns #t if cont includes a prompt tagged by prompt-tag, 
 ;#f otherwise. cont defaults to current-continuation.
  (define prompt/available? continuation-prompt-available?)

;The first thing that should surprise you is that we have yet another undefined term, the prompt tag. This is a PLT extra, and not at all required to implement the four versions of the F function described above. Those functions all use the default/prompt/tag, which you can get at any time by evaluating (default/prompt/tag). However, PLT has given us a mechanism whereby we can tag our prompts with any name we choose, and this comes in handy when analyzing the workings of these functions, as well as providing a means of extending our control over our target prompt by specifying its tag name, instead of simply using the default-prompt-tag.

;So, you see you've already learned the purpose and usage of one of the primitives listed above. We can get another one under our belt quite handily with the function prompt/available?. This is a predicate function which returns true if the continuation, an optional second (2nd) argument, includes the specified prompt-tag, its first (1st) argument. Here the prompt-tag is not optional, but the continuation will default to the current continuation if not otherwise specified. You might be asking what it means for a prompt-tag to be included. To answer this question I think a few examples are in order.

;You will notice through out my examples, whenever possible I will use the check function of srfi-78, which has the usage symantics:

;(check expr => expected-valued)

;It is a terse test protocol, that suites my taste, and can easily be extended to have all the bells and whistles of more sophisticated testing protocols. When the need arises, I will supply the extended syntax. There are two other things to know about srfi-78 and how I use it. First, it can be set to report errors in different modes. I will always use the mode which only reports errors; so when you run the code and nothing prints that means that the expected value, which you can find after the '=>' symbol, was the actual result. The other thing know about this mode is that it prints the number of checks that were correct and the number that failed at the end of the run. Thus, if everything is in working order, there will be no failed checks, as all examples have been run from the very source that makes up this post. In fact, this entire post is actually a Scheme source file. This will be my habit throughout the series.

;This demonstrates that there is always a default-prompt-tag included in the current continuation.

  (check (prompt/available? (default/prompt/tag)) => #t)
 

;This demonstrates that call/cc leaves a default-prompt-tag included in the continuation it passes to the lambda form after it.

  (call/cc (lambda (k)
  (check (prompt/available?
   (default/prompt/tag) k)
   => #t)))

;So when is a prompt-tag not included in a continuation? For that we will need to create our own prompt tag. We can do that with the next function we will meet, make/prompt/tag. It takes a single symbol as an argument, and returns a prompt tag which we can use in place of the default-prompt-tag. Lets try it.

;Our brand new prompt-tag is not included in the current continuation, or any other continuation for that matter.

  (let ([tag (make/prompt/tag '=1)]) 
 (check (prompt/available? tag) 
 => #f))

;To get our tag to be included in a continuation were going to have to call in some help from our next function to meet, namely call/cc/prompt. call/cc/prompt takes a thunk as its first (1st) argument, and then two optional arguments, a prompt-tag, and a handler-proc-or-false. For now, we're just trying to explore our new prompt tag, so will use #f as the value for the handler procedure, which will install the default handler.

;The thunk requires some explanation. When we evaluate call/cc/prompt, control is going to be passed to thunk, and provided it doesn't try to escape on us by invoking a continuation, the value of the evaluation of thunk will be the value of the evaluation of the entire call/cc/prompt expression. So lets arrange for the value of thunk to be the evaluation of our question; (prompt/available? tag). We can code it like this.

  (let ([tag (make/prompt/tag '=1)])
  (check
   (call/cc/prompt (lambda () 
  (prompt/available? tag)) tag #f)
   => #t))

;I hope it's a little bit clearer about what call/cc/prompt just did. You noticed we used tag in two (2) places. Once inside the thunk to check to see if it was included within the thunk's current continuation. But we also used it as that optional argument to call/cc/prompt. Why did we do that? Because by specifying the prompt tag, call/cc/prompt included that prompt as part of the continuation of the call to thunk. If we had not specified it we would get the following behavior.

  (let ([tag (make/prompt/tag '=1)])
  (check
   (call/cc/prompt (lambda ()
   (prompt/available? tag)))
    => #f))

;This time the only thing call/cc/prompt included was the default-prompt. One other thing we should probably mention at this point so it doesn't catch up with us later is that although the names call/cc and call/cc/prompt seem quite similar, notice that control was passed to a thunk, not a function of one argument that received the current continuation. The two functions do quite different things. We're now going to introduce our next function that works hand and hand with call/cc/prompt, namely abort/cc. abort/cc takes a prompt tag, and one (1) or more arguments that will be passed to call/cc/prompt's handler when abort/cc is evaluated. Lets see the order of events when we evaluate abort/cc within the thunk of a call/cc/prompt. This time will use our own handler so we can tell what's going on inside the function.

  (let ([tag (make/prompt/tag '=1)])
  (check 
  (call/cc/prompt (lambda ()
   (abort/cc tag 'success))
   tag (lambda (x) x))
    => 'success))

;Our handler was the identity function, so it merely reflected the argument that abort/cc gave it; 'success. Note that the handler's evaluation value became the value of the call/cc/prompt expression. This sound familiar. It ought to, because that's what happens when the continuation passed on from a call/cc expression does when it is applied to a value. Only here were using prompt tags instead of the continuations they delimit.

;Up till now we've been using a single prompt tag. Now you've just got to believe that things get more interesting when you have more than one tag. Before we look at some examples, let me introduce some new syntax which will make the coding much cleaner looking, and hopefully easier to comprehend. Lets define some syntax to put the body of the prompt in tail position with regard to the other optional arguments, and lets further shorten the names of the functions so they start to look and feel like operators. In addition will add a few helper syntactic forms some of which you've seen before.

  (define-syntax @@
    (lambda (stx)
      (syntax-case stx ()
        ((_ tag handler . body)
         #'(call-with-continuation-prompt 
     (lambda () . body) tag handler)))))
  
  (define-syntax !!
    (lambda (stx)
      (syntax-case stx ()
        ((_ tag . args)
     #'(abort-current-continuation tag . args)))))
  
  (define-syntax @
    (lambda (stx)
      (syntax-case stx ()
        ((_ ) #'(default-continuation-prompt-tag)))))

  (define-syntax ++
    (syntax-rules ()
      ((_ n) (begin (set! n (add1 n)) n))
      ((_ n x) (begin (set! n (+ n x)) n))))

  (define-syntax cout
    (λ (stx)
      (syntax-case stx ()
        ((_ e1 e2 ...)
         #'(begin (printf "~s " e1) (cout e2 ...)))
        ((_ e1 ) #'(printf "~s~n" e1))
        ((x ) (identifier? #'x) #'(newline)))))
  
 (define-syntax cp
  (lambda (stx)
    (syntax-case stx ()
      ((_ str e)
    (with-syntax ([val (datum->syntax-object stx 'val)])
        #'(let ([val e])
           (cout str val)
            val))))))

 (define (hr) (cout '______________________________________________))
  
  (check
   (let ([tag1 (make/prompt/tag '=1)]
         [tag2 (make/prompt/tag '=2)])
     (cp tag1
       (@@ tag1 (lambda (x) (cout 'handler-tag1 x) x)
         (cp tag2
           (@@ tag2 (lambda (x) (cout 'handler-tag2 x) x) 
             (!! tag1 'success))))))
   => 'success)
  (hr)
  ;handler-tag1 success 
  ;#<continuation-prompt-tag:=1> success 
  ;______________________________________________
  
  (check
   (let ([tag1 (make/prompt/tag '=1)]
         [tag2 (make/prompt/tag '=2)])
     (cp tag1
       (@@ tag1 (lambda (x) (cout 'handler-tag1 x) x)
         (cp tag2
           (@@ tag2 (lambda (x) (cout 'handler-tag2 x) x)
             (!! tag2 'success))))))
   => 'success) 
  (hr)
  ;handler-tag2 success 
  ;#<continuation-prompt-tag:=2> success 
  ;#<continuation-prompt-tag:=1> success 
  ;______________________________________________
 

;Do you see whats happening? When abort/cc targets tag1, everything in between is skipped on its way to the target. When it targets tag2, it ripples up, just as you would expect. In both cases you'll note that the target prompt-tag's handler was called, but we had arranged for the handler to simply pass along the argument passed to it by abort/cc. Taken in whole, this means that the fate of the continuation of tag2's call/cc/prompt is entirely in the hands of abort/cc, and what tag it decides to target. Once you can switch the flow off a process through the code, you have yourself a control structure. Just add a little syntactic sugar and people may actually start to use it.

;By the way, the function cp you see sprinkled about is just another one of my debugging syntactic forms that allows for the printing of a label, in this case the actual prompt-tag, and the value of its enclosing expression without getting in the way of the dynamics of what's going on.

;Notice in this next example how we can get the handler to do computation for us through the use of call/cc as an argument to the handler.

  (check
   (let ([tag1 (make/prompt/tag '=1)]
         [tag2 (make/prompt/tag '=2)])
     (cp tag1
       (* 100
         (@@ tag1 (lambda (k n) (k (lambda (c) (c n))))                                             
           (cp tag2
             (* 10
               (@@ tag2 
               (lambda (k n) (k (lambda (c) (c (* n n)))))
                   (!! tag1 call/cc 5))))))))
   => 500)
  (hr)
  ;#<continuation-prompt-tag:=1> 500 
  ;______________________________________________ 
  
  (check
   (let ([tag1 (make/prompt/tag '=1)]
         [tag2 (make/prompt/tag '=2)])
     (cp tag1
       (* 100
         (@@ tag1 (lambda (k n) (k (lambda (c) (c n))))
           (cp tag2
             (* 10
               (@@ tag2 
            (lambda (k n) (k (lambda (c) (c (* n n)))))
                 (!! tag2 call/cc 5))))))))
   => 25000)
  (hr)
  ;#<continuation-prompt-tag:=2>250 
  ;#<continuation-prompt-tag:=1>25000 
  ;______________________________________________

;Of course, we could have simply put the computation within the function passed to the handler, but I wanted to show the flexibility of the interface between abort/cc and its handler.

;This would be a good time to show the behavior of the default handler. To illustrate we're going to setup a contrived example of nested calls to call/cc/prompt followed by abort/cc. See if you can understand the outcome before reading the following discussion.

  (check 
    (@@ (@) #f
      (!! (@) (@@ (@) #f
         (!! (@) (@@ (@) #f
            (!! (@) (@@ (@) #f
               (!! (@) (lambda () 
       (lambda ()
       (lambda () 
       (lambda () 
       'success))))))))))))
        =>
  'success)
  (hr) 
  ;______________________________________________

;And here will define an analogous default-handler so we can see when, and how often the default-handler is called.

  (define default-handler
    (let ([cnt 0])
      (lambda (x)
        (cout 'default-handler-called (++ cnt))
        (@@ (@) default-handler (x)))))
  
  (check
    (@@ (@) default-handler
      (!! (@) (@@ (@) default-handler
        (!! (@) (@@ (@) default-handler
          (!! (@) (@@ (@) default-handler
            (!! (@) (lambda ()
       (lambda () 
       (lambda () 
       (lambda () 
       'success))))))))))))
        =>
  'success)
  (hr)
  ;default-handler-called 1 
  ;default-handler-called 2 
  ;default-handler-called 3 
  ;default-handler-called 4  
  ;______________________________________________  

;What we did in this example was to successively install the default-handler on the default-prompt four times in a row, punctuated after each installation with an immediate targeted abort to the same default-prompt, and passed the default-handler an expression that caused the installation of another prompt and handler. Except for the last time when we again target our abort to the default-prompt, but this time pass a function that is actually a four level deep nested lambda form culminating in the symbol success. And what we get back is simply the symbol success. An explanation is in order.

;Each prompt installed a handler that will receive the arguments of the abort that targeted it. Since it is the default handler it will re-install the targeted prompt and then call the thunk it was passed by abort in tail position of the targeted prompt, in this case the default-prompt. You may be saying to yourself, but we didn't pass it a thunk we passed it a call/cc/prompt with arguments, and you would be correct. But handler will only see what that call/cc/prompt evaluates to, and because of the nested structure, its evaluation isn't known until the final abort which assigns the nested thunk form. So each handler will see a thunk, and peel off another layer of the nested structure, until the final handler gets a thunk that evaluates to 'success, which then becomes the value of the entire expression.

;I think it's about time we figured out what happens to the prompt once it's been targeted and captured by abort/cc. To help illustrate the fate of the prompt we'll setup two scenarios. The first will use a custom handler and the second will use the default-handler.

  (let ([tag1 (make/prompt/tag '=1)]
        [tag2 (make/prompt/tag '=2)])
    (@@ tag1 (lambda (x) (x) 
      (@@ tag2 #f (cout tag1 (prompt/available? tag1))))
        (cout 'in-body-of-tag1)
        (!! tag1 (lambda () 
           (cout tag1 (prompt/available? tag1))))))
  (hr)
  ;in-body-of-tag1 
  ;#<continuation-prompt-tag:=1> #f 
  ;#<continuation-prompt-tag:=1> #f 
  ;______________________________________________ 
  (let ([tag1 (make/prompt/tag '=1)])
    (@@ tag1 #f
        (cout 'in-body-of-tag1)
        (!! tag1 (lambda () 
           (!! tag1 (lambda () 
              (cout tag1 (prompt/available? tag1))))))))
  (hr)
  ;in-body-of-tag1 
  ;#<continuation-prompt-tag:=1> #t 
  ;______________________________________________  

;We get two (2) different results depending on whether we use the default-handler or a custom handler. This is because, you may remember, the first thing the default-handler does is re-install the targeted prompt. So the answer to the initial question of whether the targeted prompt remains installed after being targeted is a resounding no.

;There remains one function on our list that we have yet to discuss, namely call/wcc. call/wcc takes a procedure as a first (1st) argument and an optional prompt-tag as a second (2nd.) It, unlike call/cc, installs no new prompt, but merely extends the specified prompt. Lets setup some examples to try and understand the behavior of this new function. While were at it, lets go ahead and create syntax that places the optional prompt-tag first (1st) in the argument order, so like @@ and call/cc/prompt, it will compose and play well with other functions. And since this function passes on a continuation, we'll save us the trouble of setting up a lambda form around the body.

  (define-syntax let/wcc
    (lambda (stx)
      (syntax-case stx ()
        ((_ k tag . body )
         #'(call-with-composable-continuation
            (lambda (k) . body) tag)))))
  
  (check
   (let ([tag1 (make/prompt/tag '=1)]
         [tag2 (make/prompt/tag '=2)]
         [tag3 (make/prompt/tag '=3)])
     (@@ tag1 #f
       (cp tag1
         (* 256
           (@@ tag2 #f
             (cp tag2
               (* 16
                 (@@ tag3 #f
                   (cp tag3
                     (* 4
                       (let/wcc k tag3
                         (!! tag2 (lambda () (k 2))))))))))))))
   =>
  2048)
  (hr)
;#<continuation-prompt-tag:=3> 8 
;#<continuation-prompt-tag:=1> 2048 
;______________________________________________
  
  (check
   (let ([tag1 (make/prompt/tag '=1)]
         [tag2 (make/prompt/tag '=2)]
         [tag3 (make/prompt/tag '=3)])
     (@@ tag1 #f
       (cp tag1
         (* 256
           (@@ tag2 #f
             (cp tag2
               (* 16
                 (@@ tag3 #f
                   (cp tag3
                     (* 4
                       (let/cc k
                         (!! tag2 (lambda () (k 2))))))))))))))
   =>
  32768)
  (hr)
;#<continuation-prompt-tag:=3> 8 
;#<continuation-prompt-tag:=2> 128 
;#<continuation-prompt-tag:=1> 32768  
;______________________________________________ 

;This is quite extraordinary behavior. The second version, where we use let/cc to obtain the current-continuation acts perfectly normal. That is to say, when its continuation in K is applied to 2, which happens in the default handler of prompt-tag2, 2 is immediately returned as the value of the continuation of let/cc, and then bubbles up, being multiplied by 4, then 16, and 256 to yield 32768.

;However when we use let/wcc to obtain the current-continuation, k must certainly be applied to 2 in prompt-tag2's handler as above, and it does in fact return immediately to become to value of the continuation of let/wcc. It even begins to bubble up, as it goes through prompt-tag3's body to be multiplied by 4. But then, it completely bypasses the body of prompt-tag2, goes on directly to tag1 where it is multiplied by 256 to yield 2048.

;The explanation for this behavior will come in the next installment of this series. But I'll leave you with a bit of a tease. We are no longer dealing with the behavior of the primitive functions in isolation, but have in fact, through our natural investigation of the primitive functions managed to duplicate the behavior of one of the functions upon which mzscheme's delimited continuations are fashioned.

2 comments:

Anonymous said...

I've just begun to read your posting, but it seems that it escaped to you that the slash ("/") in "call/cc" is an abbreviation for "with". So using "make/prompt/tag" as a shorthand for "make-continuation-prompt-tag" is somewhat disturbing for readers used to this convention.

Kyle Smith said...

I agree that in the case of call/cc the `/' has the effect of taking the place of the word `with'. But certainly there are many examples of using a / in other contexts where it means something else. For instance, commonly functions that either return a value `or' false use the convention `proc/#f'. You may be right, though, in this case a dash might have been more appropriate. You'll see later on in the tutorial that we'll dispense with most of these shortcuts for even shorter symbolic names, that are more like the `%' which stands for prompt in Sitaram's paper, on which DrScheme's delimited continuations were based.

Thanks for your comment. Hope you enjoy the series.

--kyle