Differences between version 2 and predecessor to the previous major change of LambdaCalculus.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 2 | Last edited on Friday, October 24, 2003 12:04:47 pm | by PerryLorier | Revert |
| Older page: | version 1 | Last edited on Friday, October 24, 2003 11:49:11 am | by StuartYeates | Revert |
@@ -1,3 +1,27 @@
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.
