{{ message }}

Instantly share code, notes, and snippets.

# iamvery/.gitignore

Last active Jul 30, 2019
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 .ipynb_checkpoints/ node_modules/

# The Lambda Calculus!

Lambda calculus can be used to encode any program. Fundamentally it's the idea that everything can be build from a function of one argument. By using functions, data can be encoded.

## Booleans

Start with a little bit of binary logic. Booleans are a common abstraction in programming languages which are easily expressed in lambda calculus. A boolean can be thought of as a binary construct that chooses between two values. When true, it chooses one value, and when false it chooses another.

```troo = x => y => x
falz = x => y => y```

Add a little helper function to display the boolean as a value.

```to_bool = b => b('TRUE')('FALSE')

to_bool(troo)
// TRUE
to_bool(falz)
// FALSE```

## Boolean Operators

With such an encoding for booleans, you can start to develop some expressions of boolean logic. How about unary `not` (`!`), the boolean flipping operator?

```not = b => b(falz)(troo)

to_bool(not(troo))
// FALSE
to_bool(not(falz))
// TRUE```

Neat! Now, take a shot at a couple binary operators, `and` and `or`. Here are the truth tables for reference.

### AND

b1 b2 result
true true true
true false false
false true false
false false False

### OR

b1 b2 result
true true true
true false true
false true true
false false False

With that, encode their meaning.

```and = b1 => b2 => b1(b2)(b1)
or = b1 => b2 => b1(b1)(b2)

to_bool(and(troo)(falz))
// FALSE
to_bool(or(troo)(falz))
// TRUE```

It works! Now that we have some boolean logic, it shouldn't be too hard to implement everyone's favorite conditional operation: if/then/else.

```// if(condition)(truecase)(falsecase)
iff = c => thn => els => c(thn)(els)

// cheating a bit with strings here...
iff(and(troo)(falz))('ya')('no')
// no
iff(or(troo)(falz))('ya')('no')
// ya```

Not bad for a bunch of one argument functions. What else can we do?

## Numbers

Another fun topic to explore is numbers and arithmetic. Like booleans (and everything for that matter), there must be an encoding for numbers as functions. This so-called "Church encoding" is based on counting function applications.

Consider zero.

`zero = f => x => x`

Zero applies a function, `f`, zero times to the value. Similarly one applies the function once, two twice, and so on.

```one = f => x => f(x)
two = f => x => f(f(x))
//...```

It's convenient to define a helper function that counts the function applications for visualization.

```to_int = n => n(i => i+1)(0)

to_int(zero)
// 0
to_int(one)
// 1
to_int(two)
// 2```

Also, if you look closely, you'll recognize that each successive number if based on its predecessor. It's just one more application of `f` on the result of the preceding number.

```zero = f => x => x
one = f => x => f(zero(f)(x))
two = f => x => f(one(f)(x))
// ...```

In fact, this routine of determining the successor of a number can be generalized. Do you see the pattern? The predecessor is hard-coded in the encoding of each number. Extract that value as an argument to another function that produces the successor.

```succ = n => f => x => f(n(f)(x))
three = succ(two)
four = succ(three)

to_int(three)
// 3
to_int(four)
// 4```

### Basic Arithmetic

Alright, numbers are a matter of counting function applications. So it's pretty easy to imagine some basic arithmetic. Addition, for example, is `m` applications followed by `n` more applications. Multiplication would be `m` applications repeated `n` times.

```add = m => n => f => x => n(f)(m(f)(x))

to_int(res)
// 5; whoa! that hadn't event be defined yet as a known number :mindblown:

mul = m => n => f => x => n(m(f))(x)
// Interestingly, since `x` is the last value applied, it can be dropped and the expression
// reduced to:
//   mul = m => => f => x => n(m(f))

res = mul(two)(three)
to_int(res)
// 6```
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters