Editing Combinatory logic (section)

==== Implementing lazy evaluation ====
The most important subtask to achieve this goal is to implement the algorithm of lazy evaluation.
I confess I simply lack almost any knowledge on algorithms for implementing lazy evaluation.  In my Haskell programs, when they must implement lazy evaluation, I use the following hand-made algorithm.

Functions of increasing number of arguments pass the term tree to each other during analyzing it deaper and deaper. The functions are <hask>eval</hask>, <hask>apply</hask>, <hask>curry</hask> and <hask>lazy</hask>, but I renamed <hask>curry</hask>, because there is also a Prelude function (and a whole concept behind it) with the same name. So I chose Schönfinkel's name for naming the third function in this scheme -- it can be justified by the fact that [http://www.csse.monash.edu.au/~lloyd/tildeProgLang/Curried/ Curry himself attributed the idea of currying to Moses Schönfinkel] (but the idea is [http://www.andrew.cmu.edu/user/cebrown/notes/vonHeijenoort.html#Schonfinkel anticipated by Frege too]).
----
<haskell>
 module Reduce where
 
 import Term
 import Tree
 import BaseSym
 
 eval :: Term -> Term
 eval (Branch function argument) = apply function argument
 eval atom = atom
 
 apply :: Term -> Term -> Term
 apply (Branch f a) b = schonfinkel f a b
 apply atom argument = strictApply atom argument
 
 schonfinkel :: Term -> Term -> Term -> Term
 schonfinkel (Leaf K) f x = eval f
 schonfinkel (Branch f a) b c = lazy f a b c
 schonfinkel s a b = strictSchonfinkel s a b
 
 lazy :: Term -> Term -> Term -> Term -> Term
 lazy (Leaf S) c f x = schonfinkel c x (Branch f x)
 lazy k_or_compound x y z = schonfinkel k_or_compound x y `apply` z
 
 strictApply :: Term -> Term -> Term
 strictApply f a = f `Branch` eval a
 
 strictSchonfinkel :: Term -> Term -> Term -> Term
 strictSchonfinkel f a b = strictApply f a `strictApply` b
</haskell>
----
<haskell>
 module Term where
 
 import BaseSym
 import Tree

 type Term = Tree BaseSym
 type TermV = Tree (Either BaseSym Var)
</haskell>
----
<haskell>
 module Tree where
 
 data Tree a = Leaf a | Branch (Tree a) (Tree a)
</haskell>
----
<haskell>
 module BaseSym where
 
 data BaseSym = K | S
 type Var = String
</haskell>
----     
and it seems hard to me hard to implement in CL.
Almost all of these functions  are mutual recursive definitions, and it looks hard for me to formulate the fixpont.
Of coure I could find another algorithm. The main problem is that reducing CL trees is not so simple: the <math>\mathbf S</math> rule requires lookahead in 2 levels. Maybe once I find another one with monads, arrows, or [[attribute grammar]]s...