Thu Oct 20 11:18:48 EDT 2011

Tail recursion

Maybe it's time to look at a representation in terms of mutually
recursive functions.

If there is no recursion, only tail recursion, then all function
parameters can be allocated globally, and a function call is
assignment to those variables followed by a jump.

What about something like this.  It's not very general, but it can
probably represent all loops I need.

    // loop context, constants
    const int a = ... ;
    const int b = ... ;

    // fallthrough: first call defines arguments
    // variables are assigned on subsequent function calls.
    int fun_a1 = ... ;
    int fun_a2 = ... ;
    // recursive tail call
    fun_a1 = ...;
    fun_a2 = ...;
    const int c = ...;
    const int d = ...;
    goto fun;


Corresponds to a named let in a lexical context.

(let ((a ...)
      (b ...))

 fun ((a1 ...) (a2 ...))
     (let ((c ...)
           (d ...))
       (fun ... ...))))

I think I finally got it.  Looks like this is one of the most
important "obvious" insights I had in quite a while.  It was there all
along but had to jump in front of my face somehow.  It's really
described almost exactly in [1] and [2].

See next post for cleaned up version.

[1] http://www.cs.princeton.edu/~appel/papers/ssafun.ps
[2] http://wingolog.org/archives/2011/07/12/static-single-assignment-for-functional-programmers