Lambda Calculus for the Uninitiated Part I

I’ve figured it out, the essential nature of programming languages. The kernel is smaller and more eloquent than I could ever imagine. You see, all programming is about three things only: Variables, functions, and applying functions. Everything else is syntactic sugar.

We’ll get there but it’s not that simple you see. First let me show you what I mean, all JavaScript can be built from these three building blocks:

It’s simple: Numbers are functions!

I will show you how, but first we need to get some preliminaries out of the way.

One of the most basic things a programmer might want is variables, we want to write for instance const x = 10. This is not allowed in REJS, but it turns out that variable assignment is actually a function in disguise. Instead of writing

const x = 10
console.log(x)

we can write

(x =>
  console.log(x)
)(10)

In both cases the variable x refers to the value 10, but in the second example we have done so without using const, let or var! Variable assignment is nothing more than syntactic sugar for functions.

Well yes and no, REJS doesn’t support the “.” in console.log, but of course record access is just syntactic sugar for functions, but we haven’t gotten there yet. Also we need to actually define console and log in terms of REJS which is totally possible, but a bit ahead of us. For now, whenever I use things like console.log or number and string literals, just imagine that they are stand-ins for something arbitrary we don’t really care about.

You fail to see that this “trick” is the very first hint of a significant truth: We don’t need all of this JS bloat when we have functions! But as to your question, I’d like to ask how you would do it.

You certainly are heading in the right direction, but remember that rule (2) in the definition of REJS stipulates that only functions of one argument are allowed! We get around that restriction like this

(baz =>
  (bar =>
    (foo =>
      ...
    )("foo")
  )("bar")
)("baz")

or when we have many variables we might do it in a more compact style

(baz => (bar => (foo =>
  ...
)("foo")
)("bar")
)("baz")

But I already hear your voice in my mind: “How can one do ANYTHING with this one-argument restriction” you object. This segues us neatly into the second “trick” as you might call it.

If we want to find an equivalent for 1 + 2 in REJS we face two immediate problems: What are numbers and what is “+”. For the problem of “+” it’s at least clear that it should be a function that takes two numbers and returns a number, instead of writing 1 + 2 we may write add(1, 2). Here we run into the problem of the single-argument restriction again, but this time it’s not only inconvenient, it may be devastating. However, the solution is simple. Instead of writing

const add = (x, y) => ...

we write

const add = x => (y => ...)   // or without parenthesis x => y => ...

and instead of add(1, 2) we write add(1)(2). So now add isn’t a function that takes two numbers and returns a number, it’s a function that takes one number and returns another function that takes one number and returns a number. To help you get a grasp of this I’ve written an example of how this trick is used. Please compare the code in the three tabs, they all do the exact same thing.

(first => (second =>
  second(1)(first(2)(3))
)(x => y => y) // second
)(x => y => x) // first

// Given two arguments x and y, returns x.
const first = x => y => x

// Given two arguments x and y, returns y.
const second = x => y => y

second(1)(first(2)(3))

// Given two arguments x and y, returns x.
const first = (x, y) => x

// Given two arguments x and y, returns y.
const second = (x, y) => y

second(1, first(2, 3))

In fact — and Schönfinkel from the JS meetup showed me this — not only does this trick work, it gives us the power of partial application², for instance I can now write this:

const add = x => y => x + y
const add3 = add(3) // same as: const add3 = y => 3 + y
add3(2)             // same as: (y => 3 + y)(2) -> 5

I’m afraid this does take some time, but I promise you it’s worth it! We’ll get to numbers, but first can I show you how booleans and if-statements can be expressed in REJS?

Before we begin with booleans I want to explain something. The overall claim I am making is this:

Now this quite a big bite to chew, and I fear we might not finish before lunch is over, but I have already shown you that whenever we come across a piece of JavaScript that uses const foo = ... or defines a function with many arguments, that those things are just syntactic sugar for things that are in REJS. Soon I will show that true, false and if { ... } else { ... } are also just syntactic sugar. Are you following?

My point exactly, it’s called syntactic sugar for a reason. For convenience we shall use this syntactic sugar of variable assignment and functions with many arguments. But just so that there is never any shadow of a doubt that everything really can be done in REJS, I will whenever appropriate present up to three versions of the same idea:

1. The JS version.
2. The high-level REJS version with const and multiple arguments.
3. The pure REJS version where everything is always made explicit!

Will you accept this?

Of course the values true and false must be functions! But what functions? Let’s start by examining the primary use-case for booleans: if-statements. We are of course not allowed to write if (...) { ... } else {...} in REJS, but by looking at the “shape” of the if statement we can imagine that it’s actually a function

const ifThenElse = (x, ifTrue, ifFalse) => ...

If x is true we return ifTrue, if x is false we return ifFalse. Now, consider this

const ifThenElse = (x, ifTrue, ifFalse) => x(ifTrue, ifFalse)

does this make any sense to you?

Excellent. Now that we have the basics of boolean logic we can simply define !, && and || in terms of it.

(True => (False => (ifThenElse => (not => (and => (or =>
  or(not(True))(and(True)(False))
)(x => y =>                                     // or
  ifThenElse(x)
    (True)
    (ifThenElse(y)(True)(False)))
)(x => y =>                                     // and
  ifThenElse(x)
    (ifThenElse(y)(True)(False))
    (False))
)(x => ifThenElse(x)(False)(True))              // not
)(x => ifTrue => ifFalse => x(ifTrue)(ifFalse)) // ifThenElse
)(ifTrue => ifFalse => ifFalse)                 // False
)(ifTrue => ifFalse => ifTrue)                  // True

const True = (ifTrue, ifFalse) => ifTrue
const False = (ifTrue, ifFalse) => ifFalse
const ifThenElse = (x, ifTrue, ifFalse) => x(ifTrue, ifFalse)

const not = x => ifThenElse(x, False, True)
const and = (x, y) =>
  ifThenElse(x,
    ifThenElse(y, True, False),
    False)

const or = (x, y) =>
  ifThenElse(x,
    True,
    ifThenElse(y, True, False))


or(not(True), and(True, False))

const not = x => { if (x) { return false } else { return true } }
const and = (x, y) => {
  if (x)
    { if (y) { return true } else { return false } }
    else { return false }
}
const or = (x, y) => {
  if (x)
    { return true }
    else { if (y) { return true } else { return false } }
}

or(not(true), and(true, false))

When I said earlier that “numbers are functions! I didn’t mean it metaphorically, numbers are literal functions. For instance, 10 is mere syntactic sugar for a function that takes two arguments f and x and returns f(f(f(f(f(f(f(f(f(f(x)))))))))). 0 is a function that given f and x always returns x as it is. Can you generalize this pattern?

Let’s start with addition.. in fact let’s start even simpler, how can we implement const add1 = n => n + 1 in REJS?

Very good, but can you refactor this using zero, one, two, three, four and five defined earlier?

Excellent, now we have numbers and addition. There are for sure many more things one might want to do with numbers, like subtraction for instance (which is more involved than one might think). However, I want to immediately move on to for-loops because — and this I find so exciting — numbers give rise to a notion of for-loops. In other words, some for-loops in JS can now be seen a syntactic sugar for REJS, I will show you how.

This is a snippet of code that we see quite a lot in our day to day work

let x = <initial value>
for (let i = 0; i < n; i++) {
    ...
    x = ...
}

Yes and no. We’ll show in the future how mutation can always be seen as syntactic sugar for some REJS, but that’s in the future, here I am only making a claim about how a very specific for-loop pattern has a counterpart in REJS.

So imagine, that the body of the for-loop can be refactored into a function f. The function f takes the current value of x, does something and then returns the new value of x, so we rewrite the for-loop like this

let x = <initial value>
for (let i = 0; i < n; i++) {
    x = f(x)
}

Refactoring the body into a function f means that the for-loop body can’t contain any references to the variable i, and it cannot use break or continue. Imposing these restrictions makes my argument easier to follow, but they all have workarounds.

Suppose for the sake of argument that n = 3. Now we unroll the loop, and so we get this piece of code that does the same thing⁶

let x = <initial value>
let i = 0;

// first iteration
x = f(x)
i++

// second iteration
x = f(x)
i++

// third iteration
x = f(x)
i++

Of course the variable i is never used so we may omit it

let x = <initial value>
x = f(x)
x = f(x)
x = f(x)

Finally we can compress these four lines into a single line

const x = f(f(f(<initial value>)))

Now this looks like numbers! We can rewrite it to this

const x = three(f, <initial value>)

Of course the reason we ended up with three f’s is because we assumed for the sake of argument that n == 3 == three, so in the general for-loop with any value of n we have

const x = n(f, <initial value>)

Now we simply refactor it into a forLoop function that takes an initialValue, the number of iterations n, and the for-loop body f.

const forLoop = (initialValue, n, f) => n(f, initialValue)

This is very cool, it means that any for-loop like the one above is just syntactic sugar for REJS. Here is for instance an implementation of multiply using for-loops

(zero => (one => (two => (three => (four => (five => (add => (forLoop => (multiply =>
  multiply(two)(three)
)(n => m => forLoop                             // multiply
  (zero)
  (n)
  (x => add(x)(m)))
)(initialValue => n => f => n(f)(initialValue)) // forLoop
)(n => m => f => x => m(f)(n(f)(x)))            // add
)(f => x => f(f(f(f(f(x))))))                   // five
)(f => x => f(f(f(f(x)))))                      // four
)(f => x => f(f(f(x))))                         // three
)(f => x => f(f(x)))                            // two
)(f => x => f(x))                               // one
)(f => x => x)                                  // zero

const zero  = (f, x) => x
const one   = (f, x) => f(x)
const two   = (f, x) => f(f(x))
const three = (f, x) => f(f(f(x)))
const four  = (f, x) => f(f(f(f(x))))
const five  = (f, x) => f(f(f(f(f(x)))))
const add = (n, m) => (f, x) => m(f, n(f, x))

const forLoop = (initialValue, n, f) => n(f, initialValue)
const multiply = (n, m) => forLoop(
  zero,
  n,
  (x => add(x, m)),
)

multiply(two, three)

const multiply = (n, m) => {
  let x = 0
  for (let i = 0; i < n; i++) {
    x = x + m
  }
  return x
}
multiply(2, 3)

Well, a while-loop would correspond to the so-called Y-combinator, which is also the thing that enables recursive functions. But the Y-combinator is also what lets you write programs that go on in infinite loops, and personally I’m only interested in programs that work, so neither while-loops, recursion nor the Y-combinator interests me.

If you really want to learn how to shoot yourself in the foot then I will teach you in exchange for your attention. It’s a deal.

But before then, I want to pose three exercises that makes use of all the things we’ve learned thus far:

• Exercise 1. How would you implement a function isEven that takes a number and returns True if it’s an even number. I will give you a hint but you need to fill in the blanks.

  (True => (False => (ifThenElse => (not =>
  (zero => (one => (two => (three => (four => (five => (forLoop =>
  (isEven =>
    isEven(five)
  )(n => forLoop                                  // isEven
      (True)
      (n)
      (x => /* Fill in this blank */))
  )(initialValue => n => f => n(f)(initialValue)) // forLoop
  )(f => x => f(f(f(f(f(x))))))                   // five
  )(f => x => f(f(f(f(x)))))                      // four
  )(f => x => f(f(f(x))))                         // three
  )(f => x => f(f(x)))                            // two
  )(f => x => f(x))                               // one
  )(f => x => x)                                  // zero
  )(x => ifThenElse(x)(False)(True))              // not
  )(x => ifTrue => ifFalse => x(ifTrue)(ifFalse)) // ifThenElse
  )(ifTrue => ifFalse => ifFalse)                 // False
  )(ifTrue => ifFalse => ifTrue)                  // True
  

  const True = (ifTrue, ifFalse) => ifTrue
  const False = (ifTrue, ifFalse) => ifFalse
  const ifThenElse = (x, ifTrue, ifFalse) => x(ifTrue, ifFalse)
  const not = x => ifThenElse(x, False, True)
  const zero  = (f, x) => x
  const one   = (f, x) => f(x)
  const two   = (f, x) => f(f(x))
  const three = (f, x) => f(f(f(x)))
  const four  = (f, x) => f(f(f(f(x))))
  const five  = (f, x) => f(f(f(f(f(x)))))
  

  const forLoop = (initialValue, n, f) => n(f, initialValue)
  const isEven = n => forLoop(
    True,
    n,
    (x => /* Fill in this blank */)
  )
  
  isEven(five)
  

  const isEven = n => {
    let x = true
    for (let i = 0; i < n; i++) {
      // Fill in this blank
    }
    return x
  }
  isEven(5)
  

• Exercise 2. Implement a function isZero that takes a number and returns True if that number is zero. I will not give you any help except for the knowledge that if you can solve exercise 1 then you can definitely solve this one.

  const True = (ifTrue, ifFalse) => ifTrue
  const False = (ifTrue, ifFalse) => ifFalse
  const ifThenElse = (x, ifTrue, ifFalse) => x(ifTrue, ifFalse)
  const zero  = (f, x) => x
  const one   = (f, x) => f(x)
  const two   = (f, x) => f(f(x))
  const three = (f, x) => f(f(f(x)))
  const four  = (f, x) => f(f(f(f(x))))
  const five  = (f, x) => f(f(f(f(f(x)))))
  

• Exercise 3. If you look at the definitions of False and zero, you see that they actually are the exact same functions apart from the names of their arguments. Can numbers be seen as a generalization of booleans? Can True, False and ifThenElse be implemented in terms of numbers and for-loops?