[closer-devel] Adding dynamic-wind to ContextL

[Pascal Costanza]

Hi everybody,

I hope you all had a nice Christmas. And all the best for 2009! ;)

I have spent the last couple of weeks on designing an interface for  
supporting first-class dynamic environments. This appears to be more  
complex than I initially thought - recording the values of (special)  
symbols representing dynamic variables is clearly not enough.

I have stumbled over the following problem: In ContextL, the  
activation of layers amounts to roughly something like the following.  
There is a global *current-context* variable that records all the  
active layers as a list. So each layer activation corresponds to  
something like the following (strongly simplified).

(let ((*current-context* (cons activated-layer *current-context*)))
   ...)

Since I want to ensure that ContextL plays nice with the various  
Common Lisp frameworks for supporting first-class continuations, and  
since they actually implement partial continuations, I need a way to  
mark a position in the current control flow, and when I capture the  
current dynamic environment, I should actually only record those layer  
activations that were activated since a certain given mark. [1] I  
could theoretically record the mark in the *current-context* - so  
whenever a mark is set, I should also ensure that this is triggered  
for *current-context*:

(let ((*current-context* (cons some-mark *current-context*)))
   ...)

I could then search for that mark when capturing dynamic environments  
and only capture the "lower" part of the *current-context*. However,  
this doesn't work for deactivating layers. Deactivating layers looks  
roughly as follows:

(let ((*current-context* (remove deactivated-layer *current-context*)))
   ...)

There may be a way to mingle the layers and the marks in such a way  
that I can still get the right result, but this gets really messy. (I  
would have to record layer deactivations explicitly, by storing some  
kind of deactivation record in the current context, or so.)

After some more thought about this whole problem, I came to the  
conclusion that providing a form of dynamic-wind, like in Scheme, is  
the better generalisation of dynamic environments. [2] So I plan to  
add the following to ContextL:


+ A with-dynamic-mark macro, that allows delimiting potential dynamic  
environments. The macro can be used like this:

(with-dynamic-mark (some-mark-variable)
    some code)

with-dynamic-mark delimits the current dynamic environment with a  
mark, and binds the some-mark-variable to a first-class representation  
of that mark (of unspecified type). Some-mark-variable can be  
lexically or dynamically scoped, which gives you static or dynamic  
delimited environments (corresponding to static or dynamic delimited  
continuations).


+ A dynamic-wind macro that allows setting up code that gets executed  
whenever a dynamic environment is (re)established. It is very roughly  
like Scheme's dynamic-wind, except that it isn't a function but a  
macro, that it doesn't provide the unwind-protect functionality (that  
would be redundant), and that it doesn't provide the set-up, main  
body, and tear-down code as separate thunks. The macro can be used  
like this:

(dynamic-wind
   (let ((*current-context* (cons something *current-context*)))
     (proceed
       some code)))

The code that is captured by dynamic-wind will just be executed as  
normal, but whenever a dynamic environment is reestablished that  
captures this dynamic-wind, the code here is re-executed up until the  
proceed form, which is then replaced with the continuation of  
reestablishing that dynamic environment. Proceed is like a progn,  
except that it marks the variable part of a dynamic-wind.

You can combine this with unwind-protect:

(let ((cell 42))
   (dynamic-wind
     (let ((*some-variable* cell))
       (unwind-protect
            (proceed with-something)
         (setq cell *some-variable*)))))

This example ensures that *some-variable* is always bound to a given  
value in some dynamic environment, and also ensures that side effects  
to *some-variable* are handled correctly.

A Scheme dynamic-wind, like this:

(dynamic-wind set-up body tear-down)

corresponds to a ContextL dynamic-wind as follows:

(dynamic-wind
   (funcall set-up)
   (unwind-protect
       (proceed (funcall body))
     (funcall tear-down)))

[An advantage of this design of dynamic-wind is that I can completely  
remove the recording of dynamic-wind contexts if a client sets a flag  
that it doesn't want support for first-class dynamic environments.]


+ A capture-dynamic-environment function that allows capturing the  
current dynamic environment, either completely or up unto a certain  
dynamic mark. The function can be used like this:

(capture-dynamic-environment mark)

This returns a first-class representation of the dynamic environment  
up until the mark. If you want the complete dynamic environment, you  
can leave out the mark:

(capture-dynamic-environment)

The dynamic environment basically consists of a list of dynamic-wind  
thunks that can be reestablished with the with-dynamic-environment  
macro below.


+ Finally, a with-dynamic-environment macro that allows reestablishing  
a dynamic environment. You can use with-dynamic-environment as follows:

(with-dynamic-environment (environment)
   ...)

It calls all the dynamic-wind thunks in environment (leaving out the  
proceed parts), and then continues execution with the body of with- 
dynamic-environment.


If you want to have support for dynamic-wind in a call/cc library, you  
can use with-dynamic-mark whenever you start a call/cc context, use  
dynamic-wind everywhere, use capture-dynamic-environment in  
conjunction with call/cc, and use with-dynamic-environment when you  
invoke a continuation (or put it in the continuation yielded by call/ 
cc so that this happens automatically).

I will furthermore make sure that all dynamically scoped binding forms  
in ContextL (like with-active-layers, with-inactive-layers, etc.) are  
re-implemented using dynamic-wind.


Any comments on this design? Are there any holes you can notice that I  
might have missed? Most of the functionality is provided as macros -  
do you think that's ok, or should I rather go for functional versions?  
(I would strongly prefer dynamic-wind as a macro, to have better  
optimization opportunities, but for the other operators, I am willing  
to negotiate. ;)


Please let me know what you think. I'm not online for the next few  
days, but will hopefully have time again next week to implement this...



Best,
Pascal

P.S.: I now know what bothered me in Scheme's dynamic-wind / call/cc  
approach: Dynamic-wind is a feature to support dynamic environments,  
whereas call/cc is a feature to support continuations. The combination  
overloads one construct with two different semantic concepts. It's  
true that most of the time you want both combined, but the combination  
seems forced to me. Dynamic-wind should be part of a library for  
supporting dynamic scoping, and call/cc should be left untouched. This  
should also resolve the controversy around dynamic-wind in the Scheme  
community. Not that I really care that much... ;-)



[1] For a better explanation of this, see the excellent paper about  
Delimited Dynamic Binding at http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding 
  - especially the sections 4.2.1 to 4.2.3.

[2] So Attila was right. ;)

-- 
Pascal Costanza, mailto:pc at p-cos.net, http://p-cos.net
Vrije Universiteit Brussel, Programming Technology Lab
Pleinlaan 2, B-1050 Brussel, Belgium