2

So, I have been learning about lambda calculus at university and it seems too abstract and theoretical for me.

Is lambda calculus used anywhere practically?

P.S. I tried searching Haskell compiler code for anything related to lambda calculus but couldn't find anything...

  • 2
    A large part of Field and Harrison Functional Programming is devoted to the implementation of compilers for functional programming languages. This part starts off with a section on lambda calculus, because understanding of lambda calculus and its variations are crucial to the implementation strategies – MJD Aug 22 '21 at 21:55
  • 1
    Programming languages like Haskell and ML include a typed version of the $\lambda$-calculus. Lisp includes the full (untyped) $\lambda$-calculus. As a vi user, I hate to say this, but the huge popularity of emacs totally destroys your suggestion that the $\lambda$-calculus has no practical value. Go learn! – Rob Arthan Aug 22 '21 at 22:55

1 Answers1

6

I highly disagree that the lambda calculus is too abstract and theoretical. The lambda calculus is far simpler than any other model of computation I know of. The only concept needed to understand what's going on is the concept of applying a function with a known definition to a value. Contrast the definition of the untyped lambda calculus with the definition of a Turing machine.

But that's not the question OP asked.

Some applications of lambda calculus include:

  1. Providing a foundational understanding of computation

Lambda calculus was the first formalism of "computability" in which what is now known as the "halting problem" was proved undecidable (by Alonzo Church, who mentored the more famous Alan Turing).

Lambda calculus is used as the foundation for many of the most powerful and elegant programming languages, including Haskell and dialects of Lisp. Functional languages tend to be particularly friendly to lambda.

Even languages which originally rejected lambda have now come around - even C++ and Java now include syntax inspired by that of the lambda calculus. Almost every modern language has support for defining a function using lambda.

  1. Understanding Cartesian Closed Categories

Cartesian closed categories are categories with a notion of "Cartesian product" and a notion of "exponential objects" (which are the analogue of the set $\{f : A \to B\}$). All Cartesian closed categories have models of the simply typed lambda calculus. This includes important categories like the category of Sets and the category of directed graphs as well as other, more advanced examples like categories of sheaves on a site, which are highly useful in algebraic geometry and related fields.

Other examples of a Cartesian Closed Category include any Heyting algebra, the algebras used to interpret (possibly non-classical) propositional logic. This is the origin of the "propositions as types" Curry-Howard-Lambek correspondence.

Simply typed lambda calculus is the "internal language" of these categories.

  1. Modelling "unusual" kinds of computation

When researchers set out to prove that Rust's safety guarantees actually meant that all code with no Unsafe blocks was safe, they developed a variant of the lambda calculus to do it.

There are also variants of the lambda calculus which model safe parallel programming, linear types, and many other intriguing concepts which are making their way into modern languages. Researchers will develop variants of the lambda calculus to model the behaviour of real-world languages and then prove certain desirable properties hold about these versions of lambda calculus.

  1. Understanding partial combinatory algebras

Partial combinatory algebras allow one to develop all kinds of interesting models of set theory which have computational semantics. The untyped lambda calculus is the language of PCAs and allows one to simply prove many results about them.

  1. Homotopy Type Theory

Homotopy Type Theory, and dependent type theory in general, is an extension of simply typed lambda calculus. It provides powerful tools for the study of homotopy theory and homotopy types. It also serves as a powerful new foundation of mathematics in its own right. It's one of the most fascinating new fields of study in math to emerge over the last 3 decades in my opinion.

  1. Abstract Stone Duality

Abstract Stone Duality is basically a lambda-calculus for topology. I don't know much about it, but it appears to provide a powerful set of tools for topology.

Mark Saving
  • 31,855
  • ... and, of course, it's a vital part of some really useful programming languages. See my comment on the question for more on this. – Rob Arthan Aug 22 '21 at 22:57
  • @RobArthan Definitely! I threw in a reference to Lisp (and I personally use Emacs as my main text editor for coding, LaTeX, and in general) – Mark Saving Aug 23 '21 at 01:43
  • 1
    @MarkSaving Thank you very much for your answer. I have to say, since I don't come from maths background, points 1-5 are quite hard to understand for me. But regarding point 0, you mentioned that "Lambda calculus is used as the foundation for many of the most powerful and elegant programming languages, including Haskell and dialects of Lisp.". Can you elaborate how it is used as the foundation for these languages e.g. are compilers actually a set of lambda terms? – Nick Scriabin Aug 23 '21 at 09:17
  • 1
    @NickScriabin A compiler is a program that takes a program written in language $A$ and writes an equivalent program in language $B$. When you're studying languages at a high level, what the compiler actually does is not too relevant to thinking about the language. The point of Haskell is that when you're writing Haskell, you're using a highly abstract language with patterns of thought based on typed lambda calculus and other concepts. The compiler takes this high-level program and completely rewrites it. So how the compiler actually works is not relevant for gaining initial understanding. – Mark Saving Aug 26 '21 at 18:41