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
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
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
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:
(let ((p (A p)))
(let ((p (B p)))
(let ((p (C p)))
Let's call this "nested let" form. It is related to single
assignment form and administrative normal form. 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.
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.