[<<][compsci][>>][..]
Tue Oct 25 13:22:11 EDT 2011

Zipper: data structure derivatives.

I need an inverted tree for the syntax representation of a simple
flowchart language with lexical scope for primitive data bindings and
mutually recursive functions (only tail recursion, no call stack).

data Expr = Let     Bind Expr
          | LetRec  [Fun [Var] Expr] Expr
          | If      Var Expr Expr
          | App     Fun [Var]

How to systematically derive?  Each recursive Expr node needs to be
turned around.



Writing this as a polynomial with variable:

 x = Expr

And coefficients:

 b = Bind
 f = Fun [Var]   -- no recursion here, so can be combined in 1 term
 v = Var
 a = App         -- same

We get for the constructors in the order above:

   b x
 + (f x)^n x
 + v x^2
 + a

The derivative of the polynomial is:

   b
 + (n+1) (f x)^n
 + 2 v x

The 2 numeric constants that appear distinguish between the different
branches of the LetRec and If trees.  I'm puzzled that Bind is just a
value though.  Let's try to reconstruct a type from the polynomial.
Hmm.. there's too much information lost.  The numeric constants refer
to different constructors, and the x seem to refer both to original
trees and inverted trees.  But the general idea seems to work out: If
has 2 choices, one for each branch, and LetRec has a couple for which
of the branch we're at.  Let has no selector, meaning there is only
one constructor that refers to the inverted Let list.

So let's do it manually.

EDIT: It appears to not be necessary.  The trick is to use delimited
continuations (which are zippers implicitly).  In [1] this takes the
form of a state-continuation monad, which in my Haskell implementation
looks like this:

makeVar :: TypeOf (Code t) => (Code t) -> MCode (Code t)
makeVar term@(Code sterm) = SC c where
  c (CompState n) k =
    Let var sterm (k state' ref) where
      state' = CompState $ n+1
      ref = Code $ Ref $ var
      var = Var typ nam 0
      typ = typeOf term
      nam = regPrefix ++ (show $ n)


[1] http://en.wikipedia.org/wiki/Zipper_(data_structure)
[2] http://www.cs.rice.edu/~taha/publications/conference/pepm06.ps



[Reply][About]
[<<][compsci][>>][..]