And a Functional Implementation of dynamic-wind

Previously I showed a functional implementation of dynamically scoped parameters. Here I continue with a functional implementation of dynamic-wind, with code in

Primitive Continuations

The are many ways to implement continuations.

Perhaps the most straightforward approach is to transform your program into continuation passing style (CPS).

In CPS, rather than returning a value from a function call, instead you pass an additional parameter, a function to be called with the return value. Thus

  (prn (+ 3 4))


  (+ 3 4 (fn (v)
           (prn v halt)))

This transformation can be done automatically by a compiler. You get to write your program in the usual way (the “before” code in the example above), and the compiler converts it to CPS (the “after” code in the example above).

Matt Might has a terrific article showing how to implement such a CPS-conversion compiler phase: How to compile with continuations.

In a parallel article By example: Continuation-passing style in JavaScript, Matt Might also describes how implementing ccc in CPS becomes very simple:

  (def ccc (f k1)
    (f (fn (v k2)
         (k1 v))

It’s easy to see the “goto” nature of ccc here. Usually a function like (fn (v k2) ...) above would call its k2 argument to pass its return value on to its caller. However invoking a continuation doesn’t return! The return continuation k2 is abandoned, and the captured continuation k1 is called instead.


The definition of ccc I gave above is a primitive form of ccc, one that ignores dynamic-wind.

Arc3.1 doesn’t expose dynamic-wind directly, but it does make use of it.

Consider for example w/outfile which opens a file for output, executes its body with a port to write to the file, and automatically closes the file when the body exits. It does this by calling after, which is similar to the try ... finally clause in other languages.

The file will be closed automatically regardless of how the body exits, whether it simply returns, or if an error is thrown, or if the body is exited with a continuation. (catch ... throw is implemented using a continuation, so a throw that exits the body will close the file too).

after is implemented using protect, which in implemented in ac.scm via dynamic-wind. dynamic-wind lets you intervene when a continuation is passing in to or out of a body of code.

The primitive form of ccc doesn’t do any of that. Invoking a primitive continuation is an unconditional goto. In the CPS implementation of ccc I showed above, (k1 v) doesn’t stop along the way to close files or anything else, it just continues execution in k1.

Implementing dynamic-wind

The usual story for implementing dynamic-wind goes like this.

Once we have a primitive form of ccc (whether by transforming code into CPS style or in some other way), we can then implement a full version of ccc which cooperates with dynamic-wind. (See for example the implementation given in the Chez Scheme manual).

And, the usual implementation story continues, once we have full continuations and dynamic-wind, we can then use those to implement parameters. (See for example parameter objects).

In A Functional Implementation of Dynamic Scope I complained that I found the imperative implementation hard to follow.

To implement dynamically scoped parameters in a functional way, I wrote a compilation pass which added a hidden dynamic parameter to every function call and function definition.

    L0  --------------->  L1  ------------------>  L2
        macro expansion       implicit expansion

The L2 language implements dynamically scoped parameters, but still relies on the target runtime to support continuations.

By using Matt Might’s CPS conversion code, I can extend my compiler with another pass:

  L2  --------------> L3
      CPS conversion

The L3 language has dynamically scoped parameters and primitive continuations, but doesn’t yet have dynamic-wind or full continuations.

A functional implementation

The usual implementation of dynamic-wind can’t use parameters because parameters haven’t been implemented yet -- they’re usually implemented on top of dynamic-wind. But with L3 I have parameters already.

So with parameters, I wondered if I could implement a functional version of dynamic-wind?

Looking at the sample implementation of dynamic-wind Chez Scheme manual, it looks like a lot of the work being done is manipulating the dynamic state of the winders. For example, the code for dynamic-wind (converted to Arc) looks like:

  (= winders (cons (cons in out) winders))
  (let ans (body)
    (= winders (cdr winders))

first winders is extended, and then body is called, and then winders is restored to its previous value. If winders were a parameter, this could be:

  (let ans (parameterize winders (cons (cons in out) (winders))

In the implementation of call/cc (ccc in Arc), one of the things that the call to do-wind does by the end is set winders to save, that is, to reset winders to the value they had at the time the continuation was captured.

But we know that invoking a continuation already resets the dynamic environment. If winders is a parameter, it will automatically be reset when the continuation is invoked. So whatever else do-wind might need to do, it doesn’t need to reset winders for ccc.

do-wind does a couple things. It finds the common tail between the old winders and the new winders, and walks from the old winders to the tail calling the out functions, and walks back from the tail to the beginning of the new winders calling the in functions.

Along the way it resets winders to the value it has when in and out are called inside of dynamic-wind, so that in each call to in and out, winders has the value it had at the time dynamic-wind was called. (This is important in case the in or out code itself captures a continuation).

Now, in the usual implementation where parameters are implemented on top of dynamic-wind, parameters will also be reset to the values they had at the time the dynamic-wind was called when the in and out thunks are executed.

So, if I reset the dynamic environment in calls to in and out, that will get dynamic-wind to work the same way with parameters, and, with winders implemented as a parameter, will also get the winders correctly reset -- without do-wind having to do it.

Fortunately I just happen to have a function to capture the dynamic environment :-)

With capture-dyn, my implementation of dynamic-wind now looks like:

  (def dynamic-wind (in body out)
    (with (xin  (capture-dyn in)
           xout (capture-dyn out))
      (let r
           (parameterize winders (cons (cons xin xout) (winders))

And the implementation of do-wind is simplified because it no longer needs to manipulate winders.

Here’s my final version: ccc.arc

And a demo with the CPS conversion pass can be found here:

(The demo runs very slowly, as I was also experimenting with how error handling could be defined in Arc (and thus how Racket errors thrown from runtime functions such as car could be forwarded to the Arc layer), and I needed an extra layer of indirection for callable Arc objects such as tables. All of which probably would be faster in a runtime that supported the CPS language directly, instead of a emulation layer running on top of Arc. But, sufficient to run tests and see what works).

So is my functional implementation of dynamic-wind correct? I’m not entirely sure! I did write some tests, and they do run the same in my implementation as they do in Arc3.1 (i.e. using Racket’s interpretation of the interaction of continuations, dynamic-wind, and parameters)... but naturally there may be some more subtle interaction that I didn’t think of and so didn’t write a test for. Bug reports are welcome! :)