[Solved]: What makes lambda calculus relevant to study?

Problem Detail: 

I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based on this definition from the Stanford Encyclopedia of Philosophy, it's just another notation for functions.

If it is just that, why is it advantageous to use λ-calculus over regular function notations to calculate algorithm run time?

Asked By : Jules

Answered By : mhelvens

In computer science we want to analyze and understand source-code with mathematical rigour. That's the only way to prove interesting properties (such as termination) with absolute certainty. For that we need a language with a very well-defined meaning for every construct.

In theory this could be any language with a good formal semantics. But to make things less complicated and less prone to error, it's best to use a language that is as simple as possible but still able to express any program (i.e. is Turing complete). For reasoning about imperative code, there are Turing machines. But for reasoning about functional programming, there is the $\lambda$-calculus.

The basic $\lambda$-calculus is like a functional programming language, but with a lot of 'baggage' taken out. It's not important that this be a nice language to actually write programs in, nor that it be an efficient language. Just that it is simple and expressive. For example, we don't need loops, because we can simulate them with recursion. And we don't need functions with multiple parameters, since we can simulate them with Currying.

Now, at some point you may want to prove properties about constructs that are not part of the basic (untyped) $\lambda$-calculus. That's why computer scientists have extended it in different directions over the years. For example, to reason about type-systems there are a great many variations of typed $\lambda$-calculi.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11448