x x as well as Haskell syntax: \x -> x x . Here are the reduction rules for B and C.C f g x = ((f x) g) f g x((f x) g) B f g x = (f (g x)) f g x(f (g x))We could extend babs to cover B and C. But the most common way is to run a second optimization pass over the SKI-expression. In the following diagram I have marked the members of this stack with -> arrows:-> @ / \ / \ / @ / / \ / @ 2 -> @ / \ / \ ADD 3 -> @ I / \ -> S MULThe following function spine computes this left ancestors’ stack by traversing all application nodes to the left:-- we simply represent the stack as a list of references to graph nodes type LeftAncestorsStack s = [ STRef s ( Graph s)] s (s)] spine :: STRef s ( Graph s) -> ST s ( LeftAncestorsStack s) s (s)s (s) = spine' graph [] spine graphspine' graph [] where spine' :: STRef s ( Graph s) -> LeftAncestorsStack s -> ST s ( LeftAncestorsStack s) s (s)s (s) = do spine' graph stack g <- readSTRef graph readSTRef graph case g of :@: _r) -> spine' l (graph : stack) (l_r)spine' l (graphstack) _ -> return (graph : stack) (graphstack)Using this spine function we can implement a function step that performs a single reduction step on a Graph node:step :: STRef s ( Graph s) -> ST s () s (s)s () = do step graph : stack) <- spine graph (topstack)spine graph <- readSTRef top nodereadSTRef top case node of node ( Comb k) -> reduce k stack k)reduce k stack _ -> return () ()If a combinator is found in redex position, reduce is called to perform the actual reduction work according to the combinator specific reduction rules. normalForm just applies step in a loop while the graph has not been reduced to a combinator or an integer:normalForm :: STRef s ( Graph s) -> ST s ( STRef s ( Graph s)) s (s)s (s (s)) = do normalForm graph step graph g <- readSTRef graph readSTRef graph case g of :@: _rP -> normalForm graph _lP_rPnormalForm graph Comb _com -> return graph _comgraph Num _n -> return graph _ngraphUsing a helper function reduceGraph that computes the normal-form of a graph while staying entirely in the ST -Monad, we can finally reduce our tiny toy graph:reduceGraph :: ST s ( STRef s ( Graph s)) -> ST s ( STRef s ( Graph s)) s (s (s))s (s (s)) = do reduceGraph graph <- graph gPgraph normalForm gP > runST $ mToString graph ghcirunSTmToString graph "(((S :@: MUL) :@: I) :@: ((ADD :@: 3) :@: 2))" > runST $ mToString $ reduceGraph graph ghcirunSTmToStringreduceGraph graph "25"Recursionλ-calculus does not directly support recursion using self-referential functions (see this nice exposition). This self-reproducing pattern becomes even more visible when looking at the graph-structure of the reduction of (Y g) :__ @ ==> @ ==> @ ==> ... @ \ / \ / \ / \ / \__ / \__ Y g g @ g @ g g g / \ / \ Y g g @ g g / \ Y gOne can see how at each application of (4) another copy of (Y g) is generated and incorporated into the graph as an argument of g.The last step of the diagram shows that - in the graph - self-reproduction can be achieved by simply bending the argument pointer back to the application node.