[Haskell-cafe] Language semantics

[Stefan O'Rear]

On Sun, Jul 01, 2007 at 05:06:10PM +0100, Andrew Coppin wrote:
> Stefan O'Rear wrote:
> >This is *much* easier expressed as a bottom-up traversal.
> >
> >compile = transform optimize . transform eliminate
> >
> >eliminate (Lam v e) = transform (abstract v) e
> >eliminate x = x
> >
> >abstract v (Var v') | v == v'   = I
> >abstract v (a :@ b) = S :@ a :@ b
> >abstract v x = x
> >
> >optimize (S :@ (K :@ x) :@ (K :@ y)) = K :@ (x :@ y)
> >optimize (S :@ (K :@ x) :@ I) = x
> >optimize x = x
> >
> >(Here using Uniplate, mostly because it is the freshest in my mind of
> >all of them).
> >  
> 
> Um... shouldn't that read
> 
>  abstract v (a :@ b) = S :@ (transform (abstract v) a) :@: (transform 
> (abstract v) b)

No, because the whole point of transform is that it handles recursion
for you.  (However, there is a bug!  abstracting an unrecognized form
(that is, a primitive combinator) should add a K.)

Stefan