02 September 2013

Lambda

Playing with λ-calculus is fascinating. That everything we do with computers can be represented simply with unary functions is mind-blowing.

But when I think about it too much, I begin to doubt the applicability of λ-calculus to what we actually do in practice. We don’t use Church numerals. We use two’s compliment binary integers and IEEE floating-point and—when necessary—various arbitrary precision numbers. Our conditionals aren’t based on Church Booleans but on conditional instructions built into our microprocessors. Our lists may be built out of pairs, but our pairs aren’t functions. We don’t use the Y-combinator to express recursion; we simply give our functions names, which get turned into jumps.

Granted, closures in Scheme—much like functions in the λ-calculus—are used to build higher level features. (And, of course, the keyword for creating closures is “lambda” in reference to the λ-calculus.) But lots of the lower level stuff isn’t built from closures because it wouldn’t be efficient enough. (Could it be if the effort was made to design hardware for it?)

Edit: Here’s some example code.

4 comments:

Anonymous said...

http://en.wikipedia.org/wiki/Lisp_machine

Robert said...

@Anonymous

o_O I've read a lot about Lisp machines over the years, and I don’t ever remember them using Church numerals or being lambda-calculus machines. Could you elaborate, Anonymous?

Anonymous said...

Thought they might be relevant but I was out of my depth. Sorry. :-)

Robert said...

@Anonymous

^_^ Ah. No problem. Thanks for the thought.