The magic of Y

I have always been a fan of lisp. I spent my fair deal of time with emacs and emacs lisp. Scheme and Dr.Scheme have always fascinated me. I am searching for a good excuse to put Clojure into action. However, I am sometimes blinded by the awesomeness of Ruby which I do a lot as a part of my day job. But Lisp is too beautiful for my mind to ignore. One of those things that interest a lisp hacker is this concept of fixed point combinator.

A fixed point combinator (or fixed-point operator) is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that f(x) = x. For example, 0 and 1 are fixed points of the function f(x) = x², because 0² = 0 and 1² = 1. Whereas a fixed-point of a first-order function (a function on "simple" values such as integers) is a first-order value, a fixed point of a higher-order function f is another function p such that f(p) = p. A fixed point combinator, then, is a function g which produces such a fixed point p for any function f:

p = g(f), f(p) = p

or, alternately:

f(g(f)) = g(f).

Shamelessly ripped from Wikipedia

One of the best papers I had read so far is the Why of Y(pdf). This derives the Y combinator and I thought it was beautiful derivation. However, the author uses terms like currying which is interpreted by my indian mind as a tasty gravy rather than a technique to break down a series of arguments to multiple function calls. But then I read Peter Krumin's derivation of Y combinator. This is just magical. He takes small baby steps with working scheme code and does not mix up terms used in indian recipes. This is by far the best derivation of Y-combinator I read in years.





Disclaimer: I haven't read The Little Schemer yet. I am now looking for a good excuse to use scheme/clojure for my next project.