tools (7) programming (5) cluj (4) misc (4) rails (4) productivity (3) startups (3) internet (2) meetup (2) software (2) emberjs (1) hack (1) science (1) zencash (1)

Saturday, November 24, 2012

Numbers and other delights in pure lambda calculus

In pure lambda calculus there aren't any numbers. There's this 3 things and that's it: variables, function definitions and function application

That's all you've got.

No objects, no numbers, no if statements, no true or false.
So... how can you build anything with lambda calculus?

Express it as functions:

0 := λ f x. x
1 := λ f x. f x
2 := λ f x. f (f x)
3 := λ f x. f (f (f x))
PLUS := λ m n f x. n f (m f x)
MULT := λ m n f. n (n f)
TRUE := λ x y. x
FALSE := λ x y. y
AND := λ p q. p q p
OR := λ p q. p q p
NOT := λ p a b. p b a
IFTHENELSE := λ p a b. p a b
PAIR := λ x y f. f x y
FIRST := λ p. p TRUE
SECOND := λ p. p FALSE
NIL := λ x. TRUE
NOTNIL := λ p. p (λx y. FALSE)

Taken from André Peng's talk on Foundations Of Objective-C
Transcript of the slides is available here.