hexatlas

Nothing but Functions - Numbers and Math

In our last episode, we built the foundation of boolean logic in lambda calculus using a limited subset of JavaScript. (Read that entry first.) Now, let's build numbers and do some math. There are several ways one could choose to represent numbers using functions, but the most typical method is called Church numerals. That's what we'll use.

A "number" will be a function that applies some other function that many times to some value. In JavaScript, this looks like number(fn)(value). So, the number "zero" is a function that takes some other function and a value, applies the other function zero times to the value, and then returns the result — the original value. The number "one" applies that function once, like fn(value). The number "two" applies that function twice, like fn(fn(value)). Because JavaScript doesn't allow identifiers to start with a digit, we'll prefix number values with N. Here are a few examples:

var N0 = f => x => x;              // apply "f" zero times; N0(f)(x) == x
var N1 = f => x => f(x);           // apply "f" once;       N1(f)(x) == f(x)
var N2 = f => x => f(f(x));        // apply "f" twice;      N2(f)(x) == f(f(x))
var N3 = f => x => f(f(f(x)));     // and so on.
var N4 = f => x => f(f(f(f(x))));

This might seem like a weird way to define a number, but it turns out to be both convenient and useful in a land where everything is a function.

If we cheat for a moment, imagine a function, wrap(str), that wraps its argument in angle brackets and returns the new string; calling wrap("x") would produce <x>. We could use our number functions to wrap a string that many times: N3(wrap)("x") would produce <<<x>>>, and N0(wrap)("x") would produce x.

The simplest math we can do with a number is to add one (called "increment" in programming and "successor" in mathematics). A successor function should return a number one higher than the number given. Given our definition of numbers, our successor function should produce a new function which takes some function (f) and some value (x) and applies that function one additional time to that value. For example, the successor of two is three — the successor of "a function which applies another function twice" is "a function which applies another function three times".

This is also the point at which we first see a difference between "take a bunch of arguments all at once" like normal JavaScript (f(a, b, c, d)) and "take one argument and then produce a new function to take the next one" seen in lambda calculus (f(a)(b)(c)(d)). Because a number is a function that eventually takes two arguments (the function to apply and the value on which it should operate), any operation we do with numbers should ultimately return a number — a function that takes those same two arguments. Therefore, some of these functions, like the successor function, look like they take more arguments than they should; they're returning a "number", a thing that takes two arguments, and there's no difference between doing that and taking those arguments immediately.

At last, here's the successor function:

var SUCC   = n => f => x => f(n(f)(x));
//                \-- "new number" --/

Imagine it as taking a single argument, n, the number to increment. It returns a new number — a thing that takes f and x and returns something. In this case, though, the "number" it returns has different guts than our normal numbers that we defined above. Instead of simply applying f to x some number of times, when it's finally invoked, it applies f to x exactly n times (by calling n(f)(x), since that's exactly what a number function does). Then, it applies f one additional time, by simply just passing the previous result to f(...). So, it's a number that applies f one more time than n would have on its own.

In a very similar way, we can implement addition. Addition is an operation that takes two numbers and produces the sum of those numbers. In lambda calculus terms, our addition function needs to take two numbers ("functions that apply some other function some number of times to some value") and invoke them, making sure they both use the same "other function" and operate on the same value. To achieve this, it needs to take the two numbers to "add", m and n, and produce a new number (a function that takes f and x) which applies f to x that many times:

var PLUS   = m => n => f => x => m(f)(n(f)(x));
//                     \---- "new number" ---/

The guts of our addition function applies f() n times (n(f)(x)), and then applies f() again m times to the result (m(f)(...)).

Multiplication becomes slightly more complicated. This time, instead of applying f() n times and then m times, we need to apply n itself m times. That is, instead of having to increase zero by one n times and then by one m times, we need to repeat the whole operation of "increase zero by n" itself m times. This is written as follows:

var MULT   = m => n => f => x => m(n(f))(x);
// or, equivalently,
var MULT   = m => n => f =>      m(n(f));

Finally, exponentiation takes the process one step further; the act of applying the base (b) itself becomes the "other function" used by the exponent (e), building a new "number" function unrelated to the other arguments f and x. It then uses that new number function to apply the original f to x the appropriate number of times:

var POW    = b => e => f => x => e(b)(f)(x);
// or, equivalently,
var POW    = b => e =>           e(b);

To demonstrate these functions, we first need a way to turn lambda calculus numbers back into real numbers:

function l2js_uint(uint) {
  return uint(x => x+1)(0);
}

This function takes one number function (uint, since our integers are unsigned) and asks it to apply "add one" to 0 that many times.

Then:

output(["n","succ","plus","mult","pow"].join("\t")+"\n");
[N0, N1, N2, N3, N4].forEach(function(n){
  output([
    l2js_uint(n),
    l2js_uint(SUCC(n)),
    l2js_uint(PLUS(n)(n)),
    l2js_uint(MULT(n)(n)),
    l2js_uint(POW(n)(n)),
  ].join("\t")+"\n");
});

This produces:

n       succ    plus    mult    pow
0       1       0       0       1
1       2       2       1       1
2       3       4       4       4
3       4       6       9       27
4       5       8       16      256

Predecessor (subtract one) and full subtraction are much simpler if we take a quick detour, so we'll pause for a moment to cover data structures next.

Advent of Code - Graphs

Here are some graphs of data from Advent of Code!

total users

Total users over December 2015. I expected 70 users or so, maybe. By Day 2, almost 10,000 were signed up, which caused quite a bit of panic on the server capacity end of things.

minutes to solve both parts for first 100 solvers each day

The number of minutes it took the first 100 solvers each day to solve both parts of the puzzle. The three slowest days were Day 1 (red), which had a lot fewer users working on it at first than any other day, and Days 19 (green) and 22 (blue), which were two of the hardest puzzles.

solvers per minute for first 240 minutes of each day

The number of solvers each minute for the first 240 minutes after each puzzle unlocked. The days aren't labeled, because it's just a blob at this scale. Makes a nice curve, though; almost a Poisson distribution?

cumulative solvers for first 240 minutes of each day

The number of cumulative solvers for the first 240 minutes after each puzzle unlocked. The two days with the most solvers in that timespan were Days 4 (green) and 10 (blue).

users with solving both parts on the day the puzzle unlocked

The number of users that solved both parts of a puzzle within 24 hours of the puzzle unlocking. Even though Day 1 was a "slow" day in the graphs above, by the time the whole 24 hours is finished, Day 1 still comes out as the most-solved-on-that-day puzzle.

users with at least one wrong answer on the day the puzzle unlocked

The number of users with at least one wrong answer on a puzzle within 24 hours of the puzzle unlocking. Day 2 is the highest here, which I suspect is from the difficulty increasing to something that filtered out most of the non-programmers.

users with no wrong answers on the day the puzzle unlocked

The number of users that solved both parts of a puzzle with no wrong answers within 24 hours of the puzzle unlocking. This isn't quite the difference of the above two graphs, as the above "wrong answers" graph is all users, whereas this one only subtracts users with wrong answers that also solved both parts. The number of perfect solves on Days 19 and 22 was very low.

Nothing but Functions - Logic

Most programmers have heard of Turing machines, an oversimplified model of computation as capable (algorithmically) as any programming language. They're useful for studing the capabilities of computers in a formal, no-frills setting. However, there exists a second, lesser-known model of computation which came slightly before Turing machines and is equally powerful: lambda calculus. (Don't panic — this isn't the kind of "calculus" found in most math classes.)

Anything that a Turing machine can do, so can lambda calculus. Instead of procedural things, like memory and instructions, lambda calculus models universal computation using nothing but functions. No variables, no numbers, no booleans, no conditionals, no loops, not even multiple-argument functions.

Like Turing machines, lambda calculus isn't immediately practical. Without any of the features found in modern languages, even normally-simple tasks can be cumbersome. However, it's a useful model for thinking about programming, and so it's still a valuable topic for modern programmers to understand. If you like, think of it as a game — what can we build using only functions?

Let's build something in JavaScript following the rules of lambda calculus. To preserve our sanity, we'll use ECMAScript 6 Arrow Functions (see MDN or the spec itself), which are available in Firefox 22 or Chrome 45. In this syntax, writing a => b is the same as writing (function(a){ return b; }).

Here are the rules:

  1. Functions can only take exactly one argument and contain exactly one statement.
  2. Closures are allowed — you can refer to arguments of functions in higher lexical scopes.
  3. Aliases can be created with var to help with legibility, but variables cannot be reassigned or used in a way that the original function could not, like passing it to itself.

Based on these rules, here is the most simple value, the identity function:

var IDENT = x => x;

This function returns whatever is passed to it, much like (function IDENT(x) { return x; }). We'll use a convention of all-capitals names for things that are aliases for lambda calculus functions that are following the rules. We'll use single-letter lowercase letters for arguments to be consistent with argument naming in lambda calculus.

You can also make functions that make other functions to collect more than one argument. For example:

var RETURN_FIRST_ARG  = a => b => a;
var RETURN_SECOND_ARG = a => b => b;

// which is like writing, for example,
var RETURN_FIRST_ARG = function (a) {
  return function(b) {
    return a;
  };
}

// then, later
RETURN_FIRST_ARG("first")("second");  // "first"
RETURN_SECOND_ARG("first")("second"); // "second"

These functions store an argument and then immediately return another function awaiting another argument. When you call them, you pass each argument individually as a new function call. While this seems silly, it allows lambda calculus to stay as simple as possible. It also permits powerful capabilities such as partial application, wherein you pass only one argument and wait to pass the other until later. We'll rely on that more later.

Now, we have one of the often-used capabilities found in lambda caluclus — selecting from multiple values. With this, we can build logic. Let's call the function that chooses its first argument "TRUE", and the function that chooses its second argument "FALSE".

var TRUE  = x => y => x;
var FALSE = x => y => y;

Now, we can write things like this:

TRUE("value_if_true")("value_if_false"); // "value_if_true"

some_boolean("it's true")("it's false"); // tells us whether some_boolean is true or false

...which seems silly until you consider that we've implemented the equivalent of the ternary operator:

some_boolean ? "it's true" : "it's false"; // *also* tells us whether some_boolean is true or false

Now that we have conditional logic, we can implement other operators:

var AND   = p => q => p(q)(p);
var OR    = p => q => p(p)(q);

Each of these functions takes two boolean values and produces a boolean value.

AND returns q (whatever it is) if p is true, and p otherwise (which must then be false). So, if p is false, false is returned. Otherwise, q is returned: if it's true, the result is true, and if it's false, the result is false. So, both p and q must be true for the result to be true.

OR returns p if p is true (that is, if p is true, true is returned), and otherwise returns q (whatever it is). So, if p is false, q is returned: if it's true, the result is true, and if it's false, the result is false. So, both p and q must be false for the result to be false.

We can also produce NOT:

var NOT   = p => x => y => p(y)(x);

NOT looks like it takes three arguments, but think of it like it only takes one, p. It produces "a function which takes two things (x and y) and returns one of them" — a boolean value, like our TRUE and FALSE. The thing it returns is the result of p(y)(x), that is, calling p but with the argument order swapped. So now, we have a function where if p is true, it picks the second value, and if it's false, it picks the first value, just like if p were the opposite of whatever it is. So, NOT is a function that inverts the order of arguments for a boolean, turning TRUE into FALSE and vice-versa.

Sometimes, we really just want to use the boolean like a ternary operator, but we want to make it clear we're doing that explicitly:

var IF    = p => x => y => p(x)(y);

This function takes a boolean and calls it with the given arguments, which doesn't really do much, but it lets us write code that is a little easier to read:

IF(condition)
  (true_value)
  (false_value);

We can combine some of these functions to produce another function core to most modern computers:

var NAND  = p => q => NOT(AND(p)(q));

So, let's try out our new functions. First, we need a way to turn a boolean function back into something we can use in normal-land JavaScript:

function l2js_bool(bool) {
  return bool("TRUE")("FALSE");
}

This function is our lambda-to-javascript function for booleans. It expects a boolean and asks it to choose between string representations of its value. We can use it to print out the result of boolean computations:

output(["x","y","and","or","nand"].join("\t")+"\n");

[TRUE, FALSE].forEach(function(x){
  [TRUE, FALSE].forEach(function(y){
    output([
      l2js_bool(x),
      l2js_bool(y),
      l2js_bool(AND(x)(y)),
      l2js_bool(OR(x)(y)),
      l2js_bool(NAND(x)(y)),
    ].join("\t")+"\n");
  })
});

This gives us a nice truth table:

x       y       and     or      nand
FALSE   FALSE   FALSE   FALSE   TRUE
FALSE   TRUE    FALSE   TRUE    TRUE
TRUE    FALSE   FALSE   TRUE    TRUE
TRUE    TRUE    TRUE    TRUE    FALSE

Now, we have boolean logic using nothing but functions! In the next article, we'll build numbers and do some math. Stay tuned!