What makes lambda calculus relevant to study?

Question

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?

Answer 1

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.

Answer 2

strangely a lot of books talk about $\lambda$ calculus without mentioning Lisp or Scheme, modern programming languages based on it, leaving students unfortunately with the idea that its old and abstract and mostly theoretical. studying Lisp or Scheme can be a great angle to immensely help understand $\lambda$ calculus.

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

there are many advantages to using Lisp or functional programming and calculating algorithm run time is just one possibility (although it would be helpful if you cited a ref for that). since its already in functional notation sometimes determining the formulas for run time via induction or recurrence relations may have a stronger or more obvious relationship to the original code. other types of analysis of the algorithm are simplified also.

another main advantage is syntactical simplicity. parsers for other languages are very complex but the Lisp parsers are very simple. so Lisp is a great language to study the theory of parsing in.

another key aspect is analyzing software more from a logical or mathematical lens/view rather than a "computer-scientific" perspective.

as the other answer points out, Lisp is all about recursion instead of iteration and recursion is very much at the heart of CS.

more advocation for a "$\lambda$-view" and detail can be found in [1], a free online and semifamous ref.

[1] Structure & Interpretation of computer programs, by Abelson & Sussman