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.

Hello Arc

There has been quite some ruckus on the blogosphere about Arc. I have just downloaded it and finished reading through the tutorial. I like it. I am sure that features like Unicode will get added. However, I would like to see the standard library. How can I do FFI? Database interfaces? May be they are already there but I still don't see them yet. In the meanwhile, here is an interesting snipped of Arc for everybody who is pondering about Life, Universe and Everything.

arc> (reduce + (cons 6 (map [* 4 _] (keep odd '(1 2 3 4 5)))))
42

Keep coding.

Lisp Tutorial

Following Peter Seibel's request, anybody looking for a Lisp Tutorial should read Practical Common Lisp. It is the best Common Lisp resource for beginners currently available online.

Update: Made the post title a link and point it to the book.