Previously I showed a
implementation of dynamically scoped parameters.
Here I continue with a functional implementation of
dynamic-wind, with code in
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
Matt Might also describes how implementing
ccc in CPS
becomes very simple:
(def ccc (f k1) (f (fn (v k2) (k1 v)) k1))
It’s easy to see the “goto” nature of
Usually a function like
(fn (v k2) ...) above would
k2 argument to pass its return value on to its
caller. However invoking a continuation doesn’t return! The return
k2 is abandoned, and the captured
k1 is called instead.
The definition of
ccc I gave above is a primitive form
ccc, one that ignores
Arc3.1 doesn’t expose
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
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. (
... throw is implemented using a continuation, so
throw that exits the body will close the file too).
after is implemented using
in implemented in
dynamic-wind lets you
intervene when a continuation is passing in to or out of a body of
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
The usual story for implementing
dynamic-wind goes like
Once we have a primitive form of
by transforming code into CPS style or in some other way), we can
then implement a full version of
ccc which cooperates
dynamic-wind. (See for example the implementation
given in the
And, the usual implementation story continues, once we have full
dynamic-wind, we can then use those
to implement parameters. (See for example
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
The usual implementation of
dynamic-wind can’t use
parameters because parameters haven’t been implemented yet --
they’re usually implemented on top of
But with L3 I have parameters already.
So with parameters, I wondered if I could implement a functional
Looking at the sample implementation of
Scheme manual, it looks like a lot of the work being done is
manipulating the dynamic state of the winders. For example, the
dynamic-wind (converted to Arc) looks like:
(= winders (cons (cons in out) winders)) (let ans (body) (= winders (cdr winders)) (out) ans)
winders is extended, and then
is called, and then
winders is restored to its previous
winders were a parameter, this could be:
(let ans (parameterize winders (cons (cons in out) (winders)) (body)) (out) ans)
In the implementation of
Arc), one of the things that the call to
by the end is set
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
winders is a parameter, it will
automatically be reset when the continuation is invoked. So
do-wind might need to do, it doesn’t need
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
Along the way it resets
winders to the value it has
out are called inside
dynamic-wind, so that in each call
the value it had at the time
dynamic-wind was called.
(This is important in case the
code itself captures a continuation).
Now, in the usual implementation where parameters are implemented on
dynamic-wind, parameters will also be reset to
the values they had at the time the
dynamic-wind was called when the
out thunks are executed.
So, if I reset the dynamic environment in calls to
out, that will get
work the same way with parameters, and, with
implemented as a parameter, will also get the
correctly reset -- without
do-wind having to do it.
Fortunately I just happen to have a function to capture the dynamic environment :-)
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)) (xin) (let r (parameterize winders (cons (cons xin xout) (winders)) (body)) (xout) r))))
And the implementation of
do-wind is simplified because
it no longer needs to manipulate
Here’s my final version: ccc.arc
And a demo with the CPS conversion pass can be found here: github.com/awwx/arc-cps
(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
correct? I’m not entirely sure! I did write
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,
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! :)