Previously I showed a
functional
implementation of dynamically scoped parameters.
Here I continue with a functional implementation of
dynamic-wind, with code in
github.com/awwx/arc-cps.
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))
becomes
(+ 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))
k1))
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.
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.
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))
(out)
ans)
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))
(body))
(out)
ans)
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))
(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 winders.
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 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! :)