Functional Programming and Scheme
CMPSC 461
Programming Language Concepts Penn State University
Fall 2020
Church Encoding Natural numbers
Church numerals: n ≜ λ𝑓 𝑧. 𝑓! 𝑧 Note: n is the encoding of number n
0≜ λ𝑓𝑧.𝑓”𝑧=λ𝑓𝑧.𝑧
1≜ λ𝑓𝑧.𝑓#𝑧=λ𝑓𝑧.(𝑓𝑧) 2≜ λ𝑓𝑧.𝑓$𝑧=λ𝑓𝑧.(𝑓(𝑓𝑧)) …
𝑛-fold composition
2
Church Encoding Natural numbers
n≜ λ𝑓𝑧.𝑓!𝑧
Encoding of “+ 1”?
Goal:
Definition
SUCC 𝑛 =λ𝑓𝑧.𝑓!&#𝑧 SUCC≜ λ𝑛𝑓𝑧. (𝑓(𝑛𝑓𝑧))
3
Church Encoding Natural numbers
n≜ λ𝑓𝑧.𝑓!𝑧
Encoding of “+”?
Goal:
Definition
PLUS 𝑛# 𝑛$ =λ𝑓𝑧.𝑓!!&!” 𝑧 PLUS ≜ λ𝑛# 𝑛$. (𝑛# SUCC 𝑛2)
4
Church Encoding: Example Natural numbers
n≜ λ𝑓𝑧.𝑓!𝑧
PLUS ≜ λ𝑛# 𝑛$. (𝑛# SUCC 𝑛2) Check that PLUS 1 2 =3 (Note 2)
Definition
5