Sat Jul 5 21:25:02 CEST 2008

rewrite rules for HOFs

 Q: What is the essence of the 7 deforestation rules in the Wadler
    paper? (page 8)

(1) variables are left alone
(2) distribute over type constructors
(3) function application: substitute terms in parameterized body, and
    recurse transformation
(4) distribute over case (variable)
(5) given constructor, pick one branch and substitute terms
(6) case of function application: substitute argument
(7) case of case: push inner case through to the branches

The case statements are there to handle pattern matching for union
types. You need those to be able to stop recursion! The rest is really
just term substitution and elimination of constructors through rule

Translating this to what I want to build: either I find a way to use
this representation together with a final step that optimizes data
recursive constructors to use arrays, or I use a special set of data

The higher order macros are interesting. (Wadler mentions OBJ btw. I
probably got it from there.) 'where' terms are introduced, a kind of
'let' for local function definitions. Macros are then like functions
whos variables can reference function names, but cannot be
recursive. Lack of recursion guarantees they can be expanded
out. First order recursion is still allowed using 'where' clauses.

 Q: Make a summary of what the OBJ system is about.

Rewriting + first order equational logic + ordered sorts (types).
Quite elegant, but I'm not sure whether I can use any of this in my
untyped ad-hoc approach.. Theories are quite surprising: an ability to
define properties of operations.

 Q: Algebra of programs?

The Backus paper really seems to be seminal for all this work in
functional programming about program transformation.. Nobody seems to
call it algebra of programs though..

 Q: "Functional Programming with Bananas, Lenses, Envelopes and Barbed

    "We develop a calculus for lazy functional programming based on
    recursion operators associated with data type de nitions. For
    these operators we derive various algebraic laws that are useful
    in deriving and manipulating programs."

Seems to be about moving from basic, low-level recursion to
transformation on a higher level: using combinators.