Also available as a pdf or markdown file

Programming with nothing

An (brief) Intro to the `λ`-calculus

I'm Professor Michael Selsky

iOS Developer on MNE NextGen

[@MichaelSelsky](https://twitter.com/michaelselsky)

`λ`-Calculus

`λ`-calculus ≠ ∫ calculus

^ here calculus just means a system of calculation/computation. Because Math names are weird

`λ`-Calculus

Turing complete
Based entirely around functions
Invented in the 1930s, before the Turing Machine

Alonzo Church

Invented it to try to solve the Entscheidungsproblem
Published a paper proving it to be impossible

While λ-calculus is really cool, it can be difficult to read so instead we'll use

Disclaimers

This is not software engineering advice
Don't do this in production
No seriously, I'll reject that PR
This is a learning exercise and a game
I am not an expert at this

Game means Rules

Rules

You can create functions
You can call functions
Functions can only take one argument and return one value
Can't use the def keyword
That's it

That's it


                def fact(n):
                if n == 0:
                return 1
                else:
                return n * fact(n-1)

                print(fact(6))

720


                def fact(n):
                if n == 0:
                return 1
                else:
                return n * fact(n-1)

                print(fact(6))


ONE = 1

                def fact(n):
                if n == 0:
                return ONE
                else:
                return n * fact(n-1)

                print(fact(6))


ONE = 1
IS_ZERO = lambda x: x == 0

                def fact(n):
                if IS_ZERO(n):
                return ONE
                else:
                return n * fact(n-1)

                print(fact(6))

fst = λx. λy. x
snd = λx. λy. y


ONE = 1
IS_ZERO = lambda x: x == 0

                def fact(n):
                if IS_ZERO(n):
                return ONE
                else:
                return n * fact(n-1)

                print(fact(6))


ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1

                def fact(n):
                if IS_ZERO(n):
                return ONE
                else:
                return n * fact(SUB_1(n))

                print(fact(6))


ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1
MULT = lambda x, y: x * y

                def fact(n):
                if IS_ZERO(n):
                return ONE
                else:
                return MULT(n, fact(SUB_1(n)))

                print(fact(6))

720


ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1
MULT = lambda x, y: x * y

                def fact(n):
                if IS_ZERO(n):
                return ONE
                else:
                return MULT(n, fact(SUB_1(n)))

                print(fact(6))


ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1
MULT = lambda x, y: x * y
IF = lambda cond, t_val, f_val: t_val if cond else f_val

                def fact(n):
                return IF(IS_ZERO(n),
              ONE,
              MULT(n, fact(SUB_1(n))))

                print(fact(6))

(ノಥ,_｣ಥ)ノ彡┻━┻

RecursionError: maximum recursion depth exceeded in comparison


ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1
MULT = lambda x, y: x * y
IF = lambda cond, t_val, f_val: t_val if cond else f_val

                def fact(n):
                return IF(IS_ZERO(n),
              ONE,
              MULT(n, fact(SUB_1(n))))

                print(fact(6))

But, we can fix this


ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1
MULT = lambda x, y: x * y
IF = lambda cond, t_func, f_func: t_func(None) if cond else f_func(None)

                def fact(n):
                return IF(IS_ZERO(n),
                lambda _: ONE,
                lambda _: MULT(n, fact(SUB_1(n))))

                print(fact(6))

720

┬──┬ ノ( ゜-゜ノ)


ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1
MULT = lambda x, y: x * y
IF = lambda cond, t_func, f_func: t_func(None) if cond else f_func(None)

                def fact(n):
                return IF(IS_ZERO(n),
                lambda _: ONE,
                lambda _: MULT(n, fact(SUB_1(n))))

                print(fact(6))

Let's get rid of that def


fact = lambda n:
          IF(IS_ZERO(n),
                lambda _: ONE,
                lambda _: MULT(n, fact(SUB_1(n))))

                print(fact(6))

Except we can't use a name in it's own definition.
That's just weird.

So we can just pass it in instead


fact =  lambda fact, n:
          IF(IS_ZERO(n),
                lambda _: ONE,
                lambda _: MULT(n, fact(fact, SUB_1(n))))

                print(fact(fact, 6))


fact =  lambda myself, n:
            IF(IS_ZERO(n),
                lambda _: ONE,
                lambda _: MULT(n, myself(myself, SUB_1(n))))

                print(fact(fact, 6))

Remember Rule 3

Rule 3

Functions can only take one argument


MULT = lambda x, y: x * y
IF = lambda cond, t_func, f_func: t_func(None) if cond else f_func(None)
fact =  lambda myself, n: ...

These take 2 or 3 arguments

But, we can fix this

^ But first we need to talk about

Higher Order Functions

Functions that take and/or return other functions

Math

lim_{x → ∞}f(x)

∫_a^bx²dx

$$ \sum_{n=1}^{\infty} 2^{-n} $$

Functional Programming

[1, 2, 3, 4].map(square) # => [1, 4, 9, 16]

[1, 2, 3, 4].filter(isEven) # => [2, 4]


[1, 2, 3, 4].reduce(0, +) # => 10

Currying

Schönfinkelisation

Technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. -- Wikipedia

Haskell Curry

Traced back to 1893
Curry-Howard correspondence


add = lambda x, y = x + y
add(2, 3) # => 5

add = lambda x: lambda y: x + y
add(2)(3) # => 5

add2 = add(2)
add2(6) # => 8

ONE = 1
IS_ZERO = lambda x: x == 0
SUB_1 = lambda x: x - 1
MULT = lambda x: lambda y: x * y
IF = lambda cond: lambda t_func: lambda f_func: f_func: t_func(None) if cond else f_func(None)

fact =  lambda myself: lambda n:
      IF(
        IS_ZERO(n)
      )(
                lambda _: ONE
      )(
                lambda _: MULT(n)(myself(myself)(SUB_1(n)))
      )

                print(fact(fact)(6))

Cool, so everything is a function

Except


ONE = 1

But, we can fix this

filtered

Numbers

Alonzo Church figured this out for us

Church Numerals

Church Numerals

Just another way to represent positive integers

Think "Roman Numerals" but with functions

Work by applying the same function over and over

A number n is defined as the function f applied n times to a based value of x

0 = x 1 = f(x) 2 = f(f(x)) 3 = f(f(f(x))) ... n = f(f(f(... n times ...(x))))

ZERO = lambda f: lambda x: x ONE = lambda f: lambda x: f(x) TWO = lambda f: lambda x: f(f(x))

Conversion

TWO(lambda x: x + 1)(0) # => 2

THREE(lambda: x * 2)(1) # => 8

Addition

So let's build this up through a few simple cases

Simplest Case

Adding 0
AKA Identity

IDENTITY = lambda n: lambda f: lambda x: n(f)(x)

Take in a number n and return a function that takes in a f and x and then passes those into the number n

We can think of any function that takes in a f and x as a number

Simple Case

Add 1
AKA Successor

Remember what how we define a number

A number n is defined as the function f applied n times to a based value of x

So adding one is just calling f one more time

SUCC = lambda n: lambda f: lambda x: f(n(f)(x))

Take in a number n and return another number

lambda f: lambda x:

Apply f one more time to number n

TWO = lambda f: lambda x: f(f(x)) SUCC = lambda n: lambda f: lambda x: f(n(f)(x)) THREE = SUCC(TWO) # => f(f(f(n)))

Addition

Remember what how we define a number

A number n is defined as the function f applied n times to a based value of x

m + n = m(SUCC)(n)

We apply add 1 m times to n

ADD = lambda n: lambda m: n(SUCC)(m)

We're also going to need predecessor aka SUB_1

PRED = lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f))) (lambda u: x)(lambda u: u)

This applies f one less time.

It's a little too confusing to explain.

MULT = ( lambda n: lambda m: n(lambda x: ADD(x)(m)) (ZERO) )

And that's Numbers

That will be on the quiz

That will be on the quiz

😁

Another data type

Booleans

So what are booleans?

# Booleans = Choice

NIL = lambda x: x TRUE = lambda t_func: lambda f_func: t_func(NIL) FALSE = lambda t_func: lambda f_func: f_func(NIL) IF = lambda cond: lambda t_func: lambda f_func: cond(t_func)(f_func) IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE)

# Now we have all the pieces to do this

NULL = lambda x: x TRUE = lambda t: lambda f: t(NULL) FALSE = lambda t: lambda f: f(NULL) IF = lambda cond: lambda t: lambda f: cond(t)(f) ZERO = lambda f: lambda x: x ADD1 = lambda n: (lambda f: lambda x: f(n (f)(x))) ADD = lambda n: lambda m: n(ADD1)(m) ONE = ADD1(ZERO) IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE) SUB1 = ( (lambda n: lambda f: lambda x: n (lambda g: lambda h: h(g(f))) (lambda u: x) (lambda u: u)) ) MULT = ( lambda n: lambda m: n(lambda x: ADD(x)(m)) (ZERO) ) SIX = ADD1(ADD1(ADD1(ADD1(ADD1(ADD1(ZERO))))))

FACT = ( lambda myself: ( lambda n: ( IF( IS_ZERO(n) )( lambda _: ONE )( lambda _: MULT(n)(myself(myself)(SUB1(n))) ) ) ) ) print(FACT(FACT)(SIX))

<function __main__.<lambda>.<locals>.<lambda>>

Cool it works

print(FACT(FACT)(SIX)(lambda x: x + 1)(0))

720

def fact(n): if n == 0: return 1 else: return n * fact(n-1) print(fact(6))

NULL = lambda x: x TRUE = lambda t: lambda f: t(NULL) FALSE = lambda t: lambda f: f(NULL) IF = lambda cond: lambda t: lambda f: cond(t)(f) ZERO = lambda f: lambda x: x ADD1 = lambda n: (lambda f: lambda x: f(n (f)(x))) ADD = lambda n: lambda m: n(ADD1)(m) ONE = ADD1(ZERO) IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE) SUB1 = ( (lambda n: lambda f: lambda x: n (lambda g: lambda h: h(g(f))) (lambda u: x) (lambda u: u)) ) MULT = ( lambda n: lambda m: n(lambda x: ADD(x)(m)) (ZERO) ) SIX = ADD1(ADD1(ADD1(ADD1(ADD1(ADD1(ZERO)))))) FACT = ( lambda myself: ( lambda n: ( IF( IS_ZERO(n) )( lambda _: ONE )( lambda _: MULT(n)(myself(myself)(SUB1(n))) ) ) ) ) print(FACT(FACT)(SIX))

So we're done

Except

^ Look at all those assignments. That's not allowed in the rules.

NULL = lambda x: x TRUE = lambda t: lambda f: t(NULL) FALSE = lambda t: lambda f: f(NULL) IF = lambda cond: lambda t: lambda f: cond(t)(f) ZERO = lambda f: lambda x: x ADD1 = lambda n: (lambda f: lambda x: f(n (f)(x))) ADD = lambda n: lambda m: n(ADD1)(m) ONE = ADD1(ZERO) IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE) SUB1 = ( (lambda n: lambda f: lambda x: n (lambda g: lambda h: h(g(f))) (lambda u: x) (lambda u: u)) ) MULT = ( lambda n: lambda m: n(lambda x: ADD(x)(m)) (ZERO) ) SIX = ADD1(ADD1(ADD1(ADD1(ADD1(ADD1(ZERO)))))) FACT = (

But, we can fix this

NULL = lambda x: x TRUE = lambda t: lambda f: t(NULL) FALSE = lambda t: lambda f: f(NULL) IF = lambda cond: lambda t: lambda f: cond(t)(f) ZERO = lambda f: lambda x: x ADD1 = lambda n: (lambda f: lambda x: f(n (f)(x))) ADD = lambda n: lambda m: n(ADD1)(m) ONE = ADD1(ZERO) IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE) SUB1 = ( (lambda n: lambda f: lambda x: n (lambda g: lambda h: h(g(f))) (lambda u: x) (lambda u: u)) ) MULT = ( lambda n: lambda m: n(lambda x: ADD(x)(m)) (ZERO) ) SIX = ADD1(ADD1(ADD1(ADD1(ADD1(ADD1(ZERO)))))) FACT = (

print( (lambda myself: (lambda n: ((lambda cond: lambda t: lambda f: cond(t)(f))((lambda n: n(lambda x: lambda t: lambda f: f(lambda x: x))(lambda t: lambda f: t(lambda x: x)))(n))(lambda _: (lambda n: (lambda f: lambda x: f(n (f)(x))))(lambda f: lambda x: x))(lambda _: (lambda n: lambda m: n(lambda x:(lambda n: lambda m: n(lambda n: (lambda f: lambda x: f(n (f)(x))))(m))(x)(m)) (lambda f: lambda x: x))(n)(myself(myself)(((lambda n:lambda f:lambda x: n (lambda g: lambda h: h(g(f)))(lambda u: x)(lambda u: u)))(n)))))))(lambda myself: (lambda n: ((lambda cond: lambda t: lambda f: cond(t)(f))((lambda n: n(lambda x: lambda t: lambda f: f(lambda x: x))(lambda t: lambda f: t(lambda x: x)))(n))(lambda _: (lambda n: (lambda f: lambda x: f(n (f)(x))))(lambda f: lambda x: x))(lambda _: (lambda n: lambda m: n(lambda x:(lambda n: lambda m: n(lambda n: (lambda f: lambda x: f(n (f)(x))))(m))(x)(m)) (lambda f: lambda x: x))(n)(myself(myself)(((lambda n:lambda f:lambda x: n (lambda g: lambda h: h(g(f)))(lambda u: x)(lambda u: u)))(n)))))))( (lambda n: (lambda f: lambda x: f(n (f)(x))))((lambda n: (lambda f: lambda x: f(n (f)(x))))((lambda n: (lambda f: lambda x: f(n (f)(x))))((lambda n: (lambda f: lambda x: f(n (f)(x))))((lambda n: (lambda f: lambda x: f(n (f)(x))))((lambda n: (lambda f: lambda x: f(n (f)(x))))(lambda f: lambda x: x))))))) (lambda x: x + 1)(0) )

720

So why the f**k would you do this? -- You, the audience member

1. It's fun

2. It gives perspective

Like isn't it cool how functions can represent the basic building blocks of programming

3. This is where functional programming stems from

^ C is to turing machines what Haskell is to lambda calculus

4. A simple alternative to Turing Machines

^ Turing machines are powerful but defining algorithms for it is like programming assembly. This is much more like a high level language.

^ We spend most of our time thinking about how to make great software. Lambda calculus is a simple abstraction over every model of computation.

Programming with nothing

An (brief) Intro to the λ-calculus

λ-Calculus

λ-calculus ≠ ∫ calculus

λ-Calculus

Alonzo Church

Disclaimers

Game means Rules

Rules

That's it

720

720

​(ノಥ,_｣ಥ)ノ彡┻━┻

RecursionError: maximum recursion depth exceeded in comparison

720

┬──┬ ノ( ゜-゜ノ)

Let's get rid of that def

Remember Rule 3

Rule 3

Functions can only take one argument

Higher Order Functions

Math

Functional Programming

Currying

Schönfinkelisation

Haskell Curry

Cool, so everything is a function

Except

Church Numerals

Church Numerals

Conversion

Addition

Simplest Case

Adding 0AKA Identity

Simple Case

Add 1AKA Successor

Addition

And that's Numbers

Booleans

720

Except

720

1. It's fun

2. It gives perspective

3. This is where functional programming stems from

4. A simple alternative to Turing Machines

An (brief) Intro to the `λ`-calculus

`λ`-Calculus

`λ`-calculus ≠ ∫ calculus

`λ`-Calculus

(ノಥ,_｣ಥ)ノ彡┻━┻

Adding 0
AKA Identity

Add 1
AKA Successor