Day 3

Class: CSE 114A Subject: computer-science Date: 2026-01-12 Teacher: **Prof. Miller

Lambda Calculus

Syntax of terms

$\lambda x\to x$: this is an identity function.

• i.e. $(\lambda x\to x)114\Rightarrow 114$

Notation

Alpha Equivalence

1. e[x := 5] means to replace all free occurrences of x with v in e
2. $\alpha$ equivalence
   1. You can rename parameters. i.e $\lambda x\to x\Rightarrow \alpha$ $\lambda y\to y$ $\lambda f\to f(\lambda z\to z)$ $\Rightarrow \alpha$ $\lambda f\to f(\lambda w\to w)$

Beta Reduction

$(\lambda x\to e)$ v $\Rightarrow \beta$ $e[x:=v]$

Example

$(\lambda xy\to x)$ 1 2 = $((\lambda x\to \lambda y\to x)1)2$ $\Rightarrow \beta$ $\lambda y\to x[x:=1]2$ = $(\lambda y\to 1)2$ $\Rightarrow \beta$ 1[y := 2] = 1

Terminology:

• $(\lambda x\to e)$ v is called a $\beta$-redex(reducible expression)
• An expression is normalized if it has no redexes

Question: is this normlized? $(\lambda y\to (\lambda x\to x)y)$ 114