Sat Jan 23 11:45:17 CET 2010

Relational lenses and partial evaluation (generating VMs)

Is it possible or feasible to formulate the specification of a machine
such that different optimizations can be described and implemented by
an automated procedure?

I.e.  A straightforward example is to use a cons list as a value rib
during the evaluation of the expressions in a `let' form.  This has
the advantage of maximal sharing in the case a continuation is
captured during the evaluation of one of the expressions, i.e. in <*>

(let ((a e_a)
      (b e_b)   ;; <*>
      (c e_c))

Using a vector to represent a value rib imperatively is more
efficient, but requires a copying operation on let/cc to avoid the
mutation to have observable side-effects.

The value rib is conceptually a part of the environment.  The same
argument goes for the activation stack.

I think I ran into this before, and the pattern is called "lazy stacks".

I guess the advantage of a CPS representation is then that there is
only one kind of stack: the environment stack.