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.

Statistics is important

This is important.


The population of india - 1.148 Billion
The population growth rate - 1.58%
Number of people that will be added this year - 1.8 Million
Population of chennai - 4.34 Mio

So we will add almost half of chennai in the next year. In this rate, the number of years it will take for us to double our population is approximately 45 years. Think about it. Do you really want to have children? We do not have enough resources to feed the entire country at this point.