Saturday, December 23, 2006

Priorities for a New Year

Priorities for a New Year

Sorting out projects in the fire form projects on fire

Happy Holidays to everyone! I hope you are all able to spend some time with your families. and have that singular joy of watching a kid's face as he opens a present that knocks their socks off. If that doesn't put a smile on your face, then I afraid nothing will. When I was a kid it was all about whether the next package under the tree had my name on it or not. I'm afraid its come full circle now. My recommendation to those without children is to get in good with friends that do so you can give their kids toys at the holidays. Nothing beats it.

It's about this time of year, when I've been stuffed with too many pieces of turkey, pumpkin pie and egg nog and had my fill of the ubiquitous work related social gatherings that I'm obliged to attend that I begin to sort through what I've been doing for this last year and start to prioritize what I'd like to get done this coming year. I suspect this is pretty much the natural order of things. Some people call them New Years resolutions, but I find that giving a goal that title condemns it to the fate of exercise and weight loss programs, which inevitably fail. So I keep it less dramatic and simply give some time to considering my options, reflecting on my past efforts and coming up with a strategy for the coming year.

With regard to Scheme I'm actually quite pleased with how things have come along this last year. To understand the progress that I've made you need to know a little about my background. I have a BS and MS in computer science and an MD specializing in Radiology. I'm retired now, and at the beginning of 2006 had only a minimal exposure to Lisp as a graduate student. My passion for Scheme came directly out of a massive read-a-thon of books, I had, primarily on XML technologies. Along the way I figured I needed to learn some of the more popular languages of the day, since I had programmed almost exclusively in C an C++ both as a student and as an independent computer consultant, which is how I supported myself before entering medicine. So I read books on Pearl and PHP, and then, as luck would have it, I choose to read about Scheme before Python. Well I never did get to Python. A small, unassuming book titled, The Scheme Programming Language (TSPL), 3rd ed., by Kent Dybvig really captured my attention. I almost put it down after the first chapter because it seemed to be basically Lisp the way I remembered it from school, with car and cdr and the lot. But as I continued with it I realized I was up against a worthy adversary, with the introduction of syntactic extensions to the language and this funny concept of call-with-current-continuation. Now I don't suggest that TSPL is the right choice for ever student of Scheme to start with, as it is prone to introducing concepts in examples before they've been discussed in the text. But for my taste it was just what the doctor ordered. The exercises often appear trivial until attempted, and then you learn that Dybvig expects that previous exercises will have been completed as he progress through the text. It should also be pointed out that he places the answers to many of the exercises in the back of the book. However, as I learned, simply having the answer was typically not enough to continue, I really had to understand how the answer was derived to understand discussions later in the text; but I suspect this is true with any introductory text you would settle on to learn Scheme.

Being used to mature IDE's in the C++ world, I was disappointed at my early attempts to find a reasonable Scheme system to program in; they all seemed to be about twenty years behind the times with regard to debugging tools and development environments. That's until I found PLT's DrScheme, which really can't be beat for anyone attempting to learn the language. Coming in second on my list was Dybvig's own Petite-Chez Scheme, which sports an excellent debugger (in many ways better than DrScheme's until recently), but lacked the integration with the source, so that one was relegated to checking line numbers in error messages against line numbers in your editor to try and figure out where things had gone wrong. Today, I am aware of several different approaches, all utilizing Emacs (a long-toothed unix editor with a Lisp scripting language built in) that allow the kind of integration I was looking for, and had I been aware of them at the time things might have turned out differently, but from where I sat at the time DrScheme had no competition. Till this day I occasionally surf around looking at other implementations of Scheme to see if I would now be better off with a different flavor, but DrScheme is very much a living implementation, with updates coming out nightly, if you are so inclined. So I can still say to anyone that wants to build applications in Scheme that DrScheme is your best bet for a development environment, and if you ever need the speed of a compiled version the PLT group always has mzscheme, which is the command line implementation of Scheme upon which DrScheme is built, and which produces very fast executable compiled binaries. And if you really must have the ultimate speed provided by xyz's super Scheme compiler, then you can always develop it in DrScheme using the strict R5RS language, restricting yourself to purely portable libraries, and then compile them on what ever implementation you like.

Now that you've learned a little bit about how I came to Scheme, and heard my song and dance about the virtues of DrScheme it's time to return to my priorities for the upcoming year. The first project I undertook after doing my homework in Scheme, because of my intense interest in XML technology, was the development of a native XML database written entirely in Scheme that sported both an SQL and XQuery front-end. That project has become a very large undertaking, turning into several sub-system projects along the way, one of which I've posted about previously, that being Active Comments. The projects name is xmlServer, and my thoughts on its future are that I'm likely to take several of the subsystems, polish them off as systems in their own right, and place them on PlaneT. They include a structured symbol table, a multithreaded messaging system and a Red-Black Tree data structure that have all been written in DrScheme and all very useful subsystems. As for xmlServer as a whole, I have an XQuery syntax subsystem, and a multi-threaded database process subsystem to complete before it will show signs of life. It is already quite capable of storing and retrieving data in native XML format using a pseudo-SQL syntax from a single database. Truth be told however, it was a learning project, and the world has quite a sufficient number of database options already, so this project as a whole will remain on the back burner, as I have more interesting projects to pursue.

Next on the list is building a Scheme implementation from the ground up. I've seen few different models of methodology, everything from break out the c compiler and start writing to compiling a certain core of functionality from an existing implementation and building the rest as syntactic extensions to the language. My purpose, I suppose, needs some explanation given my song of praise I gave to DrScheme earlier. I'm not out to create a Scheme implementation that will necessarily attract anyone's attention as far as using it for developing applications. What I'm after is the deep understanding of Scheme that I'm quite certain will follow from having to make the engineering trade-off decisions between performance, standards compliance and features. I fully expect that this will be a multi-person year project, so this initial phase of deciding on methodology could take a few months and I wouldn't be surprised. This project is definitely off the back burner but is nowhere near the flame yet.

Then we get back to Active Comments, who's epilogue I wrote about a couple of posts back. The fact is this is a high priority item for me to complete, even if not in the fashion I had originally envisioned. The project entails writing a tool, as they are called in DrScheme speak, that becomes part of the DrScheme IDE. This particular tool would allow for a user specified syntax, with Active Comments being the default syntax, to govern their comments. The user would be free to completely ignore the tool by either not installing it or simply not employing it to check the syntax of their comments. They would also be free to use their own syntax if they had something else in mind regarding the manner in which they wanted to document source files. For those who decided to buy into the entire idea, the tool would come complete with a functioning syntax that can trivially be transformed into an XML document where the comments are the XML entities and attributes and the source code is simply preformatted text, in the sense of an XHTML document. This project is very much a front burner project, and has been delayed somewhat as the new unit system on which tools are built in DrScheme was just now overhauled, so it didn't make sense to get started on a system using an underlying library I knew was about to fundamentally change. But now that the change is in place I will begin work on this project with ernest.

Finally, another top priority of mine is my ongoing dialogue on Scheme From the Florida Keys, and especially my tour of the Delimited Continuation Operators that I've been writing about. If your ever out at my web site, I keep a bibliography there of journal articles related to the topic. I think once you read a few of these articles you'll realize how significant the operators are to DrScheme. They also supply a wealth of very interesting topics for blog posts. It is quite impressive the number of ways people have come up with to utilize these new tools. I'm going to be selecting just those examples that most clearly demonstrate the advantage of using delimited over non-delimited continuations. From a purely Turing machine perspective, you can get the job done with either, but there are times when its not so clear how you would get it done without delimited continuations.

Putting the tour to the side, the blog will be my outlet for my public progress notes as I take on all of the projects I've talked about, and I'm sure others I haven't thought of yet. Programming is, by its nature, an intensely introspective process. The blog serves the purpose of exposing those introspective thought processes to other peers, so it will remain a front burner item for me for the foreseeable future.

--kyle

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.

Sunday, December 03, 2006

Epilog to Active Comments

Jumping back for a moment, I' ld like to finish, for the time being, the story on Active Comments. I had made great progress in the area of raising all Active Comments to first class comments, in that they could nest one within the other, arbitrarily deep, just as you would want from an XML document with no schema to govern the order of entries, nor to say who can be a parent of whom. The following is a somewhat modified version of the syntax I used to test the final version of the draft of nested Active Comments.

(define-syntax @
(lambda (stx)
(syntax-case stx (author attribution
                  comment created
                  description function
                  goal code header
                  modified name note
                  param predecessor
                  return section stx
                  TODO url key0)
  ((_ key0)
   #'())
  ((_ key0 text ...(@ k a ...))
   #'(@ key0 text ...)(@ k a ...)))
  ((_ key0 text ...)
   #'(text ...))
  ((_ key)
   #'(key))
  ((_ key ())
   #'(key))
  ((_ key ((a b) ...))
   #'(key '(a ...) '(b ...)))
  ((_ key ((a b) ...) c ...)
   #'(begin (key '(a ...) '(b ...))
            (@ key0 c ...)))
  ((_ key (@ k a ...) ...)
   #'(begin (key)
            (@ k a ...) ...))
  ((_ key text ...(@ k a ...))
   #'(begin (key k )
            (@ key0 text ...)(@ k a ...)))
  ((_ key text ...) #'(key '(text ...)))
  ((_ a ...)
   (raise-syntax-error #f
    "Invalid Entity for Active Comment"
    stx #'(list 'a ...)))))

And when I say test, I mean test. I wrote a program to generate 1000 Active Comment phrases, each containing a random number of Active Comments from one (1) to fifteen (15), and each of those comments randomly had or did not have text and attributes. Even the number of attributes was randomly varied, as well as using gensym to randomize id's, value strings and text within the Active Comments. Not since my days as a graduate student at UCSC when I also worked at Borland in their Database Engine QC department had I written such an exhaustive randomized test. Each clause of syntax when activated bumped a counter in a vector of rules, that was then dumped at the end of the test to generate a histogram of rule usage over the entire test set to insure proper coverage. In short I had done my homework on this one, as I wanted to get it right. And indeed it ate up the entire test set without a single syntax error.

Unfortunately, from the vary start I had made a fatal mistake. You can see it even in the stripped down version (minus all the testing apparatus) of the syntax I show above. The flaw is that, although elegant in its recursive design, the recursion by its nature introduces expressions within the transformer environment. Under most situations, for most applications of syntactic forms this is not an issue, but for Active Comments its death. Because in the beginning, and as I mentioned in the previous post on this topic, a design imperative was that Active Comments would not break definition context, and that is exactly what an expression does. So, it took a little while to get over all that lost time, but then again, I thought, at least I've built an excellent parser for nested Active Comments even if they can't be actually active.

The solution I'm guessing is to utilize this syntax within comments, and then to regain the purpose for their existence, I'll need to build a DrScheme tool that can, in a generalized way, parse comments on command against any syntax a user might prefer. In other words, my solution would be to have two languages within a single source file. One that governed the Scheme, that is already provided, and another to reign in the structure of comments, if a user were so inclined, to make exporting the document for use as an API source file a pain free experience. One could dream up all manner of pre and post-processing programs to do the same thing, but they would be doing it long after the syntax errors in the comments had been made, and would supply no added benefit over simply exporting the source document to any XML editor of your choice and cleaning the entire document all in one tiresome session. That's why I'm committed to the tool solution.

One of the niceties of DrScheme is that it allows you to enter boxes of non-textual information within your source program. They can be as elaborate as a slide show or as simple as a comment box. However, as has been recently discussed with some frequency on the PLT discussion list, it is difficult to parse these files since the format is not well documented and until recently no one has pushed for methods to parse these files. As you can imagine I have been following the discussions with a great deal of interest, and have even found rudimentary ways to parse .scm files that contain non-textual information for its text data, which is all that I need access to. Based on these routines I've been successful at parsing the text out of all sorts of .scm files from within DrScheme, where my tool would be based. Flatt has even indicated that the command line based mzscheme, the underlying scheme upon which DrScheme is built may soon have facilities for parsing text data from arbitrary .scm files.

All of this is good news when stacked up against my blunder with nested Active Comments. So, there still may be a day when I stop commenting my source files in raw XML within block comments, and start using Active Comment syntax within the comments of my source files. If and when that day comes, I'll at least have the syntax to parse it waiting in the wings.

--kyle