[<<][staapl-blog][>>][..]

Sun Apr 26 17:19:47 CEST 2009

## Forth is already CPS / ANF / SSA

( Background: I've been skimming some papers by Oleg Kiselyov about
metaprogramming[4].
Some of the recent papers are about avoiding CPS or monads for
writing generators, and instead using delimited continuations to
hide side-effects so they won't mess up guarantees made by the type
system.
However, in a concatenative language, there is no need to do
anything else than CPS. Maybe there is something interesting to
find there? )
I've been re-examining the way RPN code gets compiled to Scheme after
having trouble with the lexical variables in the Coma macro language.
Basicly I was mixing forward (CPS-style) and backward (expression
style) nesting.
A concatenative function in CPS has two parameters: 'p' the parameter
stack and 'k' the continuaton. In Scheme syntax the composition of
CPS functions (A B C) is written as:
(lambda (p k)
(A p (lambda (p)
(B p (lambda (p)
(C p k))))))
Alternatively concatenative code can be represented quite directly
with p -> p functions and implicit continuations as:
(lambda (p)
(let ((p (A p)))
(let ((p (B p)))
(let ((p (C p)))
p))))
Let's call this "nested let" form. It is related[2] to single
assignment form[3] and administrative normal form[1]. This is what the
previous CPS form gets optimized to in PLT Scheme. Look at the output
of "mzc --decompile" to see this.
To see that these two are closely related, think of the invocation of
a continuation as the assignment to a viariable and a jump to the code
label / execution of next primitive.
The above is nested let equivalent to the following nested expression.
(lambda (p)
(C
(B
(A p))))
Which is _backwards_ from the perspective of the concatenative code.
This backward notation together with forward nesting of let
expressions lead to a lexical variable form which i couldn't get to
nest properly. However, in the nested let form local bindings are
introduced quite naturally, binding to the right.
[1] http://en.wikipedia.org/wiki/Administrative_normal_form
[2] http://chak.web.cse.unsw.edu.au/~patrykz/papers/ssa-lambda/
[3] http://en.wikipedia.org/wiki/Static_single_assignment_form
[4] http://okmij.org/ftp/Computation/Generative.html

[Reply][About]

[<<][staapl-blog][>>][..]