0026 Email Tutorials Haskell For Beginners ‐ Lambda (λ) Calculus Primer

Video: https://youtu.be/9MtE5ONrQyk?si=yOZVmPRse1zKuDsF

Table of Contents

1. Why Learn the Lambda Calculus?
2. What Is the Lambda Calculus?
3. Variants of the Lambda Calculus
4. Lambda Abstraction vs Ordinary Functions
5. The General Form: λx. expression
6. Anonymous Functions and Naming
7. Function Application by Juxtaposition
8. Prefix Application (e.g. + x 1)
9. Lambda Calculus as “Assembly Language” for FP
10. Summary of the Primer
11. Glossary
12. Multiple Choice Questions (with Answers)

1. Why Learn the Lambda Calculus?

The goal of this primer is to give you a basic understanding of the theoretical foundations of functional programming.

Why it helps:

• It shows you how functions and computation can be described with a tiny core language.
• It gives intuition for what’s happening under the hood when you write Haskell or other functional code.
• Students who see lambda calculus before diving deep into functional programming often find the later material easier.

In later videos/modules you’ll see more about:

• Evaluation rules (β-reduction, etc.)
• Reduction orders (normal order, applicative order)
• Church–Rosser theorems (about confluence)

This video focuses on the core idea: what the lambda calculus is and how lambda abstractions and applications work.

2. What Is the Lambda Calculus?

The Lambda Calculus is a formal system for expressing computation, originally developed by Alonzo Church.

Key points:

• It’s formal: Everything is defined via precise syntax and rules.
• It’s about computation: It shows how to compute purely via functions.
• It uses the Greek letter λ (lambda) to introduce functions, hence the name.

Historically and practically:

• Many functional languages (Haskell, OCaml, etc.) can be understood as “fancy front ends” that eventually compile down to some form of lambda calculus.
• You can think of lambda calculus as a kind of “assembly language for functional languages”.

3. Variants of the Lambda Calculus

There are many variants, each adding more structure (especially types):

• Simple untyped lambda calculus – Just terms and functions, no types. (This is what we focus on here.)
• Simply typed lambda calculus – Adds basic types and type annotations.
• System F (polymorphic lambda calculus) – Adds universal quantification / polymorphism.
• System Fω (F-omega) – Extends System F with type operators (types of types).

For this course:

• We only need the simple untyped lambda calculus.

• If you want to go deeper later, look up:

  • Hindley–Milner type system
  • System F

You do not need those to follow this course; they’re just pointers for the curious.

4. Lambda Abstraction vs Ordinary Functions

Let’s start with a familiar, mathematical-style function:

• Function name: f
• Parameter: x
• Body: x + 1

We might write:

( f(x) = x + 1 )

Examples:

• ( f(1) = 2 )
• ( f(2) = 3 )

Here:

• f has a name, which we use to call it: f(1), f(2).

The Lambda Abstraction Equivalent

In lambda calculus, we write the same idea as a lambda abstraction:

λx. x + 1

This has three main pieces:

1. λ – introduces a lambda abstraction (a function).
2. x – the formal parameter (the variable bound by the lambda).
3. . – separates the parameter(s) from the body.
4. x + 1 – the function body (expression to compute).

This lambda abstraction means:

“A function which, given an x, returns x + 1.”

Important distinction:

• The mathematical version f(x) = x + 1 gives the function a name (f).
• The lambda version λx. x + 1 has no name; it is an anonymous function.

5. The General Form: λx. expression

Every lambda abstraction in the simple untyped lambda calculus looks like this:

λ variable . expression

For example:

• λx. x – the identity function (returns whatever you give it).
• λx. x + 1 – increment function.
• λy. y y – applies y to itself (not type-safe in the typed world, but valid in untyped lambda calculus).

You can think of it as:

λx. E = a function that takes an argument x and produces the result of expression E.

6. Anonymous Functions and Naming

In pure lambda calculus, functions are anonymous:

• The lambda abstraction λx. x + 1 is itself the function.
• There is no built-in mechanism for names like f. Names are an extra layer we add when we embed lambda calculus into a programming language.

In practice (in actual languages):

• We do usually bind lambda abstractions to names for convenience:

  f = \x -> x + 1

• But in the pure calculus itself, the basic building blocks are variable names and lambda abstractions, not named functions like f.

Variables:

• The function itself is unnamed.
• The parameter (like x) does have a name inside the function body – we call it a bound variable in that context.

7. Function Application by Juxtaposition

In normal math notation, we apply functions like:

• f(1)
• f(2)

In lambda calculus, we apply a lambda abstraction to an argument by placing them next to each other (this is called juxtaposition):

(λx. x + 1) 1

Read as:

“Apply the lambda function λx. x + 1 to the argument 1.”

This corresponds to:

• f(1) in the usual style.
• Result: 1 + 1 = 2.

Similarly:

(λx. x + 1) 2   -- corresponds to f(2)

Result:

• 2 + 1 = 3.

We often add parentheses around the lambda abstraction to remove ambiguity:

• (λx. x + 1) 1
• (λx. x + 1) 2

This “just put them next to each other” style is what “application by juxtaposition” means.

You can even apply lambdas to other lambdas, e.g.:

(λx. x x) (λy. y)

…but that’s for later; the video keeps it simple at this stage.

8. Prefix Application (e.g. + x 1)

In the lambda calculus, function application is always written in prefix form:

• Instead of x + 1 (infix),
• You use something like + x 1 (prefix).

The key idea:

• + is just another function.
• In prefix notation, the function comes first, followed by its arguments.

So, in a more “pure lambda calculus” style, the body might be something like:

+ x 1

instead of:

x + 1

The position of the operator (+) is just a convention:

• Infix: x + 1
• Prefix: + x 1
• Postfix: x 1 +

The lambda calculus chooses prefix for uniformity: every function application looks like:

f arg1 arg2

regardless of whether f is “+” or any other function.

9. Lambda Calculus as “Assembly Language” for FP

One of the most useful mental models from this video:

Think of the lambda calculus as a kind of assembly language for functional programming languages.

• Languages like Haskell, OCaml, etc. often compile to some intermediate representation that’s based on a variant of the lambda calculus.
• High-level constructs (let bindings, pattern matching, etc.) can be lowered down to lambda abstractions and applications.

So, by understanding the lambda calculus, you:

• Gain insight into how functional languages implement functions and expressions.
• Get intuition for what’s going on when your code is evaluated and optimized.

10. Summary of the Primer

From this primer, you should now understand:

1. What the lambda calculus is: A formal system developed by Alonzo Church to express computation via functions.

2. Why it matters:

   • It underpins many functional languages.
   • It provides a minimal “core” to reason about programs.

3. Basic syntax:

   • Lambda abstraction: λx. expression
   • Function application: by juxtaposition – (λx. x + 1) 1

4. Anonymous functions:

   • Functions themselves are unnamed (anonymous); only variables are named.

5. Prefix application:

   • Function symbol first, then arguments — e.g. + x 1.

Later modules will build on this:

• Defining the simple untyped lambda calculus rigorously.
• Evaluation rules (especially β-reduction).
• Different reduction orders.
• The Church–Rosser theorems, which say (roughly) that evaluation order doesn’t affect the final result if it exists.

11. Glossary

• Lambda Calculus A formal system for expressing computation using functions, developed by Alonzo Church.

• Lambda Abstraction (λx. expression) A function definition in lambda calculus: given x, compute expression.

• Formal Parameter The variable introduced by a lambda (x in λx. x + 1).

• Function Body The expression after the dot in a lambda abstraction (x + 1 in λx. x + 1).

• Anonymous Function A function with no name; in lambda calculus, every function is a lambda abstraction like λx. ... rather than a named f.

• Application / Function Application Using a function on an argument; written as juxtaposition in lambda calculus, e.g. (λx. x + 1) 3.

• Juxtaposition Placing expressions next to each other to denote application: f x means “apply f to x”.

• Prefix Notation Notation where the function/operator appears before its arguments: + x 1 instead of x + 1.

• Simple Untyped Lambda Calculus The variant of lambda calculus without types; terms can be combined freely.

• System F / System Fω More advanced typed lambda calculi adding polymorphism and type operators.

12. Multiple Choice Questions (with Answers)

Use these to test your understanding of Part 26.

1. What is the lambda calculus primarily used for?

A. Rendering graphics on a screen B. Formally expressing computation using functions C. Managing operating system processes D. Defining SQL queries

Answer: B

2. Who developed the lambda calculus?

A. Alan Turing B. Alonzo Church C. John von Neumann D. Haskell Curry

Answer: B

3. Why is it called the “lambda” calculus?

A. It was invented in a lab named LAMBDA. B. It uses the Greek letter λ to define functions. C. It only works with exponential growth functions. D. It is an acronym.

Answer: B

4. Which of the following is a correct lambda abstraction?

A. λ. x + 1 B. x. λx + 1 C. λx. x + 1 D. x λ. x + 1

Answer: C

5. In the lambda abstraction λx. x + 1, what is x?

A. A constant B. A function name C. The formal parameter (bound variable) D. The result of the function

Answer: C

6. How is function application written in the lambda calculus?

A. f(x) B. x f C. (λx. x + 1) 3 D. apply(λx. x + 1, 3)

Answer: C (Option C is the lambda calculus style: juxtaposition of function and argument.)

7. In the expression (λx. x + 1) 2, what does this correspond to in ordinary math notation?

A. 2(λx. x + 1) B. x + 1(2) C. f(λx. 2) D. f(2) where f(x) = x + 1

Answer: D

8. What does “juxtaposition” mean in the context of lambda calculus?

A. Placing a type annotation next to a term B. Placing the argument next to the function to indicate application C. Putting two lambdas side by side to form a pair D. Writing multiple function definitions on the same line

Answer: B

9. In the lambda calculus, functions are:

A. Always named (like f, g) B. Always recursive C. Anonymous lambda abstractions like λx. ... D. Only allowed to have numeric parameters

Answer: C

10. Why can we think of the lambda calculus as an “assembly language” for functional programming?

A. Because it is compiled directly to machine code. B. Because it handles memory management. C. Because high-level functional languages can be translated to lambda-calculus-like intermediate forms. D. Because it uses registers and jumps.

Answer: C

COMPLETE TWO QUIZZES BELOW:

A-Quiz and Onchain Progress NFT

B-Quiz and Onchain Progress NFT