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
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)))

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)
    (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