Monday, October 16, 2006

The birth of recursion from self-application in lambda calculus

Reading Many faces of the fixed-point combinator and Y overriding self-application by Oleg Kislyov (oleg-at-pobox.com), I came to understand how to express recursive functions in lambda calculus in an elegant way. Oleg's code was written in Scheme, but it was clear that it was easily translated in pure lambda calculus. I used the Lambda calculator by Carl Burch to do this for the (recursive) factorial function:
(λf.f f) (λf.λn.if (= n 0) 1 (* n (f f (- n 1))))
Example: ((λf.f f) (λf.λn.if (= n 0) 1 (* n (f f (- n 1)))) 5)
Afterwards, I found on the CLiki Factorial page a Common Lisp translation of the above:
((lambda (f) #'(lambda (n) (funcall f f n)))
#'(lambda (f n) (if (= n 0) 1 (* n (funcall f f (- n 1))))))
This would probably look much better in Scheme, and I am beginning to understand why Scheme is regarded as a "better Lisp" than Lisp.

Just when I was contemplating "porting" the lambda expression to Ruby, here it is... well, almost. Actually, the Y combinator is used here, instead of the U combinator used by Oleg in the above articles. So, here is the true Ruby translation (actually a sample call of it):
p lambda { |f|
f.call(f)
}.call(
lambda { |recurse|
lambda { |n|
if n == 0 then
1
else
n * recurse.call(recurse).call(n-1)
end
}
}).call(5)

No comments: