Penguin
Note: You are viewing an old revision of this page. View the current version.

A conceptual model of computers based on defining and evaluating functions. Of current ProgrammingLanguages?, LISP, Scheme and Haskell best expose this conceptual model.

One of the fundamental proofs in ComputerScience is that any result calculatable in LambdaCalculus is calculatable on a FiniteStateMachine.

(From memory:)

LambdaCalculus is based on the idea that you have two types of rewrite rules, one where you change the names of variables, and one where you replace a variable with it's expansion. And thats it.

For instance, if we define "one" as a function which outputs it's argument once, we have
one = \x(x)

then the successor function might be defined as

successor = \x.y(x y y)

so "successor one" is

two = successor one two = \x.y(x y y) \x(x)

now we do an alpha reduction (rename some variables)

two = \x.y(x y y) \z(z)

now we do a beta reduction (replace x with it's value (\z(z))

two = \y(\z(z) y y)

and a beta reduction on z

two = \y(y y)

we now have a function that outputs it's argument twice.

And so on.