Sat May 9 11:02:51 CEST 2009

Michael Thyer's Thesis about Lazy Specialization

At page 18 of [1] there is a ``knot-tying'' version of the
interpreter.  This fully lazy technique seems to be the key to lazy
partial evaluation.  Time to get familiar with it.

The evaluator from page 18:

 evalProg prog env = (lookup "main" prog') env where
     prog' = map (\(label,stmts) -> (label,evalStmt stmts)) prog
     evalStmt [] env = env
     evalStmt (stmt:stmts) env =
         case stmt of
           SAssign var exp -> evalStmt stmts (update (var, evalExp exp env) env)
           SGoto label -> (lookup label prog') env
           SIf cond yes no -> if evalExp cond env /= 0
                              then evalStmt yes env
                              else evalStmt no env

Here prog' is the dictionary of evaluated expressions which is built
in terms of evalStmt which in turn refers back to prog' in the
interpretation of SGoto.  If there is some sequence of reductions that
will build the datastructure lazy evaluation will find it.  See also

[1] http://thyer.name/phd-thesis/
[2] http://calculist.blogspot.com/2005/07/circular-programming-in-haskell.html