Sat Sep 28 09:17:49 EDT 2013
State machine transformer
The basic tasks:
- environment capture for all yield points.
- liveness analysis: does life-time cross yield points?
How much of this can be done with abstract interpretation? Probably a
lot. The interesting part is going to be how to do loops.
- identify all variables (e.g. flatten)
- identify all control paths
It doesn't fit in the standard rai template since it needs to capture
variable bindings. Or does it? Let's just give it a try.
It seems that this is really not so hard to do once the right
representation has been found. What about avoiding control structures
in a first iteration and just concentrating on the idea of
The existing SSA transformer can be used to build nested environments.
However, it's not really in an abstract reusable form, and it doesn't
directly abstract `let' forms, only as side effects..
It might be best to solve the problem in isolation first: build a
minimalistic scheme interpreter / compiler.
A simple example program: with
- named let
- ordinary let*
- primitive invocation
- tail call
- non-tail calls
(let next ((a 0))
(let* ((a (inc a)))
It seems best to focus on let* instead of let, as it allows sequential
operation, which maps better to low-level code.
Named let is a bit annoying, but it's the only way to make loops
without explicit loop statements and explicit lambdas. The language
is not supposed to be higher-order.
Interesting is that `yield' is the only non-tail position call in a
body. ( let* rhs could have a proper non-tail call, which we ignore
for now )
From this it might make sense to make `yield' into function semantics,
i.e. always returning a value. This leads to the program:
'(let next ((a 0))
(let* ((a (inc a))
(_ (yield a)))
Where we currently ignore yield's rv.
Now, a compilation would involve walking the tree and splitting each
- what came before
-> treat yield as the inner expression / break off
- what comes after
-> reconstruct the environment = main problem
So this is the same as "representing the continuation". The context
needs to be restored. This includes control context.
Waiting for that flash to happen...
Where is the difficulty?
Not thinking properly about the control structures.
Reconstructing the environment is easy.
The difficulty is in implementing the "variable update" behind the tail-recursive call.
So what about doing this all in a dumb way:
* rename each variable to a unique name and store them in a flat name
space. optimize later for accessibility
* implement next in terms of set! and goto
This seems really simple and solves the whole problem. The rest is