Clarence1898 wrote:

> Since I am unfamiliar with lambda calculus, not being taught in the FORTRAN
> class I took at college, I looked it up on wikipedia.  After a few paragraphs,
> my eyes glazed over and could no longer focus.

In seriousness now...

A Turing machine (as you may or may not know) is a "computer" simplified 
down to the barest essentials. It turns out, the simpler a machine 
becomes, the harder it becomes to program it.

[Strictly, a *universal* Turing machine is a simplified programmable 
computer, if you want to nitpick.]

Similarly, the Lambda calculus is sort of the simplest possible 
programming language. And again, it turns out the simpler the language 
is, the harder it is to program anything with it!

The Lambda calculus is a programming language with 1 datatype and 1 
operator. And it's Turing-complete. That's a pretty impressive result!

The only datatype is "function", and the only operator is "function 
call". You pass each function an argument (which must be a function, 
since there aren't any other datatypes), and it returns a result (which, 
again, has got to be another function).

It's like binary. Binary isn't "complicated" - actually it's extremely 
simple. The confusing thing is that you need *a lot* of binary digits to 
actually "say" anything. And 0010010101100100110111010111010110 makes 
you go dizzy after a while.

Similarly, the Lambda calculus isn't "complicated", it's just that the 
whole "function takes a function and yields a function" seems a little 
confusing initially.

Many people speak of the "enriched lambda calculus", which is lambda 
calculus with more datatypes and operators so it's not *quite* so insane 
to use. The enriched lambda calculus really is quite simple. For example,

   λx· 3*x + 5

is a lambda function. It does roughly the same thing is

   function NONAME(x)
   {
     return 3*x + 5;
   }

in JavaScript. The difference - obviously - is that lambda functions 
don't have names.

The freaky part about the "pure" lambda calculus is that you use 
functions to represent things that aren't functions. For example, you 
say that any 2-argument function that throws away the first argument and 
returns the second one represents "true", and any 2-argument function 
that throws away the second argument and returns the first represents 
"false".

You can represent numbers as functions, and then write a function that 
takes two of these functions-that-represent-numbers and constructs a 
function that represents the number you get when you add these two 
numbers together.

...which is a really confusing way of waying you can perform 
mathematical addition in the pure lambda calculus. Instead of taking two 
numbers, converting them to binary and putting them through some digital 
circuitry, you take two numbers and convert them to functions, and 
convert the resulting function back into a number. Same deal, just more 
perplexing.



Now if you REALLY WANT TO MAKE YOUR HEAD FRIGGIN HURT... Try the SKI 
combinator calculus.

The lambda calculus says: If you can construct a function with any 
possible shape, then you can represent any kind of data and perform any 
algorithm on that data.

The SKI combinator calculus says: You can construct any shape of 
function from just 3 functions, named "S", "K" and "I".

For example, the "true" function becomes K, and the "false" function 
becomes KI. The "2" function is S(S(KS)K)I, and so forth.

...in other words, you write entire programs out of lots of S's, K's, 
I's and brackets!



IF YOU WANT TO TOTALLY BREAK YOUR MIND, you may try the Iota calculus.

SKI calculus says: You can make any function from just S, K and I.

Iota calculus says: You can make S, K and I from the X function.

In other words, the Iota calculus means you write whole programs that 
just consist of X's and brackets. That's all! Basically, the shape of 
the parse tree is the program! o_O

Somewhere I had a printout for the Iota calculus program to compute 2+2. 
Suffice it to say, it's 4 lines long, and looks something like

   X(X(XX)X(X)X(XXX)X(X)X(X(XX)))X(X(X))))X(X)...

So when I said that the lambda calculus is the "simplest" programming 
language, actually I lied. The Iota calculus is. If you write

   X(XX)

as

   *X*XX

instead (the "*" being a prefix application operator), then every Iota 
program becomes something like

  ****X*X**XX*X**X*XXX*X*XXX...

and you have a programming language that contains only two symbols - "X" 
and "*" - that is Turing-complete, and hence can express any possible 
algorithm.

The only real way to top that would be to convert the symbols to 1s and 
0s, encode the whole program as a binary integer, and then convert it to 
a unary integer. That way, your program would be a line of (several 
billion) 1s. But even I'm not *that* crazy!

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message