[This has been written as informal introduction to Lambda Calculus. If you are a student of Programming Languages, consider a formal introduction instead. Beyond the second para, this post may not be suitable for kids. Rating: PG13.]
Turing Machine is a well known concept in computer science. It's an abstract machine, capable of implementing any computable function. It's impressive because the machine itself is extremely simple, having only a few instructions. But Turing Machine is more like hardware (a machine) and less like a programming language.
Lambda Calculus is a similar concept (that is, you can define any computable function in it) proposed by Alonzo Church in 1930. The difference form Turing Machine is that it is a programming language; an extremely simple one. There are only two constructs: function definition and function application. The functions themselves are anonymous (i.e., no names are given to functions) but the parameters are named.
Since nothing exists other than these two constructs, everything is represented as a function, even natural numbers. For example, the number 0 can be a function that takes a parameter (actually another function) and returns it. The number 1 can be represented by a function that takes a function and applies the given function to a parameter once. The function for the number 2 can apply the given function to the result of applying the same function to an argument. Obviously, the results of computations are also functions.
[Sideline: Though this definition of natural numbers may seem weird but what exactly is a number, say 1? 1 is something which is different from 0 and 2 (and other numbers as well). There is no other definition. I tried to do a search on this claim of mine and found this excellent piece of argument: What is a number? that quotes Bertrand Russell as, "A number is the class of all classes similar to a given class."]
As you can probably guess, much of the power of Lambda Calculus comes from recursion and our ability to think abstractly. Why is lambda calculus important? Firstly, it is extremely mathematical in nature (why is that a desirable property is discussed next). Secondly, it has resulted in the development of functional programming languages like Lisp, ML, Scheme and later Haskell. Why functional programming is important isn't discussed here (see, Von Neumann Bottleneck, a term coined by John Backus in his Turing award lecture in favor of Functional Programming.)
So I said that Mathematical basis is an important property of any programming language. When we think of something, our thought is unbounded. But when we say the same thing, we have to filter out ambiguity and inconsistency from our thought. Next, when we write the same thing, we have to follow some rules of grammar and (due non-interactive nature of discussion and also because of lack of body language) we have to be even more prcise. Inspite of that, natural language is ambiguous. Consider this sentence, "I can't dance." Does this mean you can't dance now or does it mean that you don't know how to dance?
Mathematics is the most precise language we know to describe things. Programming languages that have foundations in Mathematics are more precise and more importantly, we can argue about their properties formally (e.g., we could try to prove that a given program always terminates). Proving properties of non-formal languages is an extremely daunting task.
You can read more about Lambda Calculus and Formal Semantics of Programming Languages, both on Wikipedia. But don't overdo it - if you are a regular programmer, it's important to know that these things are there; learn and use them when you need them. Hopefully never :)
Turing Machine is a well known concept in computer science. It's an abstract machine, capable of implementing any computable function. It's impressive because the machine itself is extremely simple, having only a few instructions. But Turing Machine is more like hardware (a machine) and less like a programming language.
Lambda Calculus is a similar concept (that is, you can define any computable function in it) proposed by Alonzo Church in 1930. The difference form Turing Machine is that it is a programming language; an extremely simple one. There are only two constructs: function definition and function application. The functions themselves are anonymous (i.e., no names are given to functions) but the parameters are named.
Since nothing exists other than these two constructs, everything is represented as a function, even natural numbers. For example, the number 0 can be a function that takes a parameter (actually another function) and returns it. The number 1 can be represented by a function that takes a function and applies the given function to a parameter once. The function for the number 2 can apply the given function to the result of applying the same function to an argument. Obviously, the results of computations are also functions.
[Sideline: Though this definition of natural numbers may seem weird but what exactly is a number, say 1? 1 is something which is different from 0 and 2 (and other numbers as well). There is no other definition. I tried to do a search on this claim of mine and found this excellent piece of argument: What is a number? that quotes Bertrand Russell as, "A number is the class of all classes similar to a given class."]
As you can probably guess, much of the power of Lambda Calculus comes from recursion and our ability to think abstractly. Why is lambda calculus important? Firstly, it is extremely mathematical in nature (why is that a desirable property is discussed next). Secondly, it has resulted in the development of functional programming languages like Lisp, ML, Scheme and later Haskell. Why functional programming is important isn't discussed here (see, Von Neumann Bottleneck, a term coined by John Backus in his Turing award lecture in favor of Functional Programming.)
So I said that Mathematical basis is an important property of any programming language. When we think of something, our thought is unbounded. But when we say the same thing, we have to filter out ambiguity and inconsistency from our thought. Next, when we write the same thing, we have to follow some rules of grammar and (due non-interactive nature of discussion and also because of lack of body language) we have to be even more prcise. Inspite of that, natural language is ambiguous. Consider this sentence, "I can't dance." Does this mean you can't dance now or does it mean that you don't know how to dance?
Mathematics is the most precise language we know to describe things. Programming languages that have foundations in Mathematics are more precise and more importantly, we can argue about their properties formally (e.g., we could try to prove that a given program always terminates). Proving properties of non-formal languages is an extremely daunting task.
You can read more about Lambda Calculus and Formal Semantics of Programming Languages, both on Wikipedia. But don't overdo it - if you are a regular programmer, it's important to know that these things are there; learn and use them when you need them. Hopefully never :)
No comments:
Post a Comment