Now on another topic which I find interesting, consider how the abstraction algorithm (conversion to combinators) can be simplified with the use of two helper functions L and R:
\L = (\x\y\z (x z) y) # send z to left side only
\R = (\x\y\z x (y z)) # send z to right side only
Of course these can be defined in terms of S and C but I just implement them directly in the interpreter for efficiency.Now let's abstract the Q definition using L and R in addition to S and C where possible:
\Q = (\x\y x (y y))
\Q = (\x R x (\y y y))
\Q = (\x R x (S I I))
\Q = (L (\x R x) (S I I))
\Q = (L R (S I I))
That's much more compact than just using S and C alone.
Now let's use the abstraction algorithm to convert Q into combinators step by step, removing the variables:
OK that was kind of fun but all I did was demonstrate that Q can be defined in terms of S and C. That's actually somewhat irrelevant. The main point is to demonstrate that when you apply the Y combinator to an arbitrary function, you can in effect get recursion. So let's follow the reduction sequence: Now let's show how you can actually remove self-reference from a recursive function. Consider this recursive definition of the function which appends two lists: Now as it turns out, the "==" in Fexl is merely a short-hand which does this for you: That's actually a non-recursive definition of append there. Consider the body of the function by itself: There are no free variables in that. The inner call to "append" actually refers to the \append when encloses it. So you actually have a fully closed form function there which calls itself.You can look at it this way, separating that inner function out and calling it F:
So if we actually apply that function to two lists, it goes like this: And then it proceeds from there depending on what x is. It's amazing stuff, being able to defined a fully closed-form function which somehow manages to reach out and call itself. :)