[fexl]

Also, you'd be surprised at how self-application can actually mean something. Consider how a recursive function is defined using the Y combinator, which is governed by this rule:

  Y F = F (Y F)

OK now that's not exactly self-application yet, but now let's dig into the Y combinator a bit and see how it can be defined in terms of a Q combinator:

  Y = S Q Q

Now what is Q you ask? It can be defined as a lambda expression this way:

  \Q = (\x\y x (y y))

Aha! There's a self-application for you. See how y is applied to itself there.

Now let's use the abstraction algorithm to convert Q into combinators step by step, removing the variables:

  \Q = (\x\y x (y y))
  \Q = (\x S (\y x) (\y y y))
  \Q = (\x S (C x) (S (\y y) (\y y)))
  \Q = (\x S (C x) (S I I))
  \Q = (S (\x S (C x)) (\x S I I))
  \Q = (S (S (\x S) (\x C x)) (C (S I I))
  \Q = (S (S (C S) C)) (C (S I I))

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:

  : Y F
  = S Q Q F
  = (Q F) (Q F)
  = Q F (Q F)
  = F ((Q F) (Q F))
  = F (S Q Q F)
  = F (Y F)

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:

  \append == (\x\y x y \h\t cons h; append t y)

Now as it turns out, the "==" in Fexl is merely a short-hand which does this for you:

  \append = (Y \append \x\y x y \h\t cons h; append t y)

That's actually a non-recursive definition of append there. Consider the body of the function by itself:

  (Y \append \x\y x y \h\t cons h; append t y)

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:

  \F = (\append \x\y x y \h\t cons h; append t y)
  \append = (Y F)

So if we actually apply that function to two lists, it goes like this:

  : append x y
  = Y F x y
  = F (Y F) x y
  = F append x y
  = (\x\y x y \h\t cons h; append t y) x y
  = x y \h\t cons h; append t y

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. :)

[fexl]

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.