Google Sheets and Microsoft Excel support LAMBDA functions, which allow users to define reusable, lazily-evaluated abstractions with in arbitrary parameters. There’s just one problem: these formulae cannot be stored as the output of a cell, making it difficult to construct objects under the functional programming model.

Thankfully, Google Sheets supports the new LET statement, which allows us to bind constants of any type to a name, which can be referenced in order to produce a program output:

=LET(
    plus_one, LAMBDA(x, x + 1),

    starting_value, 5,
    CONCATENATE(starting_value, " + 1 = ", plus_one(starting_value))
)

While it’s already challenging to write entire programs within a single spreadsheet cell, we can take the idea of turing completeness further: what if we completely got rid of all the other datatypes and variables, and wrote our entire program using only lambda expressions?

Removing all the existing functions from an already-limiting system forces us to completely reimagine the nature of computation, and adopt an entirely different “functional” approach to programming, taking us to one of the roots of computer science — Lambda Calculus.

Pure Functional Programming

Doing this means that we have to perform all calculations using functions and single-variable function applications — there’s no such thing as TRUE, FALSE, 1, or 0 in lambda calculus. We can’t even do iteration or recursion like we’re used to in Java and Python, because the value of any variable in our system must be constant, explicit, closed-form. Variables cannot refer to variables that haven’t yet been defined, including itself, so they offer nothing more than a simple code substitution to improve readability. We have to invent all the basic primitives ourselves using raw symbolic manipulation.

Rederiving the Basics

One of the most obvious limitations of our system is that functions can only operate on one argument at a time. Even if we could derive an AND operation, we would have to figure out how to link it to two boolean inputs. Fortunately, we can implement this using currying, where we apply inputs one after the other the returned intermediary function:

=LET(
    true_l, ...,
    false_l, ...,
    and_l, LAMBDA(a, LAMBDA(b, ...)),

    and_l(true_l)(false_l)
)

That solves the first problem. Now, we need a way to actually implement booleans so that they can meaningfully interact with a program. We have no way to directly test the equality of any expression, so the true/false booleans must differentiate themselves based on some sort of functionality.

Since booleans are always of one of two possible values, we can identify them based on how they select two supplied inputs. By convention, we define the “true” boolean as a two-argument function that returns the first argument, and the “false” boolean as a two-argument function returning the second argument.

=LET(
    true_l,  LAMBDA(a, LAMBDA(b, a)),
    false_l, LAMBDA(a, LAMBDA(b, b)),
)

Everything is a Lambda

Because there are no raw literals available in our pure functional world, the best we can do is derive functions that simulate their behavior. The choice to define booleans as selector functions results in surprisingly emergent behavior — we can put anything, including more booleans, inside of this selection. This allows us to define our logic gates using boolean mappings:

=LET(
    true_l,  LAMBDA(a, LAMBDA(b, a)),
    false_l, LAMBDA(a, LAMBDA(b, b)),
    not_l,   LAMBDA(a, a (false_l) (true_l)),
    and_l,   LAMBDA(a, LAMBDA(b, a (b) (false_l))),
)

The implementation of the remaining gates, such as OR and XOR, is left as a challenge to the reader.

The fact that we can implement computer logic through a series of function calls and substitutions suggests that turing-completeness is not just a property of logical cells or transistors — Lambda Calculus demonstrates that emergent and nontrivial behavior can be achieved with only the composition and application of deterministic pure functions.

Implementing Numbers

Boolean operations are nice, but we want to be able to do math in our system. Unlike booleans, natural numbers can hold infinite possible values, and we need to be able to treat different numbers using the same interface. This means that numbers should be testable and usable using the same amount of input arguments, and it should be easy to do basic numerical operations, such as incrementing.

Church encoding achieves this by defining a number as a function which can map an inputted function f as its n-fold composition. This means that the number zero maps inputted functions to the identity function, not applying the given function at all. The number one will apply the function once, the number two applying the function twice, etc…

Church numerals map a function f to its n-fold composition.

That means that the successor to a number is just a new function that maps the inputted function one time more than the previous number. Conveniently, the addition function just needs to apply that successor function n times on the operand m:

=LET(
    zero_l,  LAMBDA(f, LAMBDA(x, x)),
    one_l,   LAMBDA(f, LAMBDA(x, f(x))),
    two_l,   LAMBDA(f, LAMBDA(x, f(f(x)))),
    three_l, LAMBDA(f, LAMBDA(x, f(f(f(x))))),
    succ_l,  LAMBDA(n, LAMBDA(f, LAMBDA(x, f((n)(f)(x))))),
    plus_l, LAMBDA(m, LAMBDA(n, n(succ_l)(m))),
)

With this system, multiplication and exponentiation are just different orders of application of a function. The multiplication function must apply the outer function m times to the composed function n of f, and the exponent function raises a base n times before receiving a target function f:

=LET(
    times_l, LAMBDA(m, LAMBDA(n, LAMBDA(f, m(n(f))))),
    exp_l, LAMBDA(b, LAMBDA(n, n(b))),
)

Unfortunately, there’s no easy way to undo a function call for subtraction — the rules of lambda calculus don’t permit this type of reflection. However, we can use clever (but slow) function chaining to define the more complex functions:

=LET(
    pred_l, LAMBDA(n, LAMBDA(f, LAMBDA(x, n(LAMBDA(g, LAMBDA(h, h(g(f)))))(LAMBDA(u, x))(LAMBDA(u, u))))),
    minus_l, LAMBDA(m, LAMBDA(n, n(pred_l)(m))),
    is_zero_l, LAMBDA(n, n(LAMBDA(any, false_l))(true_l)),
)

The Factorial Function

With a basic framework for integer arithmetic complete, we can attempt to implement some more complex mathematical operations. The factorial function is often defined recursively: n! is defined as n * (n-1)!, going all the way down to the base case, 0! = 1. Unfortunately, direct recursion isn’t technically allowed in lambda calculus — a recursive call would not fit in a closed-form, finite expression, and only works due to the existence of variable names.

We can supply the function that our code needs to call when it needs to recurse, effectively taking a first parameter as the callback function. That callback function, being of the same form as the original function, passes itself as a callback. The overall function is just this base function, with the first parameter already supplied:

=LET(
    SUPPLIER_THROWAWAY_KEY, "input for lazy supplier lambda",
    base_case_supplier, LAMBDA(_, one_l),
    factorial_bootstrap, LAMBDA(f, LAMBDA(x, 
        (is_zero_l(x)
            (base_case_supplier)
            (LAMBDA(_, times_l(x)((f)(f) (minus_l(x)(one_l)))))
        )(SUPPLIER_THROWAWAY_KEY))
    ),
    factorial, (factorial_bootstrap) (factorial_bootstrap),
)

We have to produce values through an indirect supplier and a useless argument to prevent infinite loops, because google sheet formulae are not lazily evaluated.

Putting the overall system together with some simple functions to convert our representations into actual functions, we get this code, producing this program output:

6! = 720

A Better Factorial Function

Although our factorial implementation works and is portable to other languages such as Lisp and Haskell, google sheets can only calculate 6! before exceeding the computation limit. This is largely due to the inefficiencies with our number system — we have to iterate through the entire system just to subtract one for the recursion. We can avoid the recursion entirely by taking advantage of the specific implementation of Church numerals with function composition, by passing around pairs of numbers that determine the next state dynamically:

=LET(
    BEGIN_LIB_BOOL, "standard boolean library",
    identity_l, LAMBDA(x, x),
    true_l, LAMBDA(a, LAMBDA(b, a)), 
    false_l, LAMBDA(a, LAMBDA(b, b)), 
    not_l, LAMBDA(a, a(false_l)(true_l)),
    and_l, LAMBDA(a, LAMBDA(b, a(b)(false_l))), 
    bool_to_literal, LAMBDA(b, b(TRUE)(FALSE)),
    literal_to_bool, LAMBDA(a, IF(a, true_l, false_l)),


    BEGIN_LIB_NUMERAL, "church encoding for natural numbers",
    zero_l, LAMBDA(f, LAMBDA(x, x)),
    one_l, LAMBDA(f, LAMBDA(x, f(x))),
    two_l, LAMBDA(f, LAMBDA(x, f(f(x)))),
    three_l, LAMBDA(f, LAMBDA(x, f(f(f(x))))),
    succ_l, LAMBDA(n, LAMBDA(f, LAMBDA(x, f((n)(f)(x))))),
    plus_l, LAMBDA(m, LAMBDA(n, n(succ_l)(m))),
    times_l, LAMBDA(m, LAMBDA(n, LAMBDA(f, m(n(f))))),
    pred_l, LAMBDA(n, LAMBDA(f, LAMBDA(x, n(LAMBDA(g, LAMBDA(h, h(g(f)))))(LAMBDA(u, x))(LAMBDA(u, u))))),
    minus_l, LAMBDA(m, LAMBDA(n, n(pred_l)(m))),
    exp_l, LAMBDA(b, LAMBDA(n, n(b))),
    is_zero_l, LAMBDA(n, n(LAMBDA(any, false_l))(true_l)),
    num_to_literal, LAMBDA(n, n(LAMBDA(l, l+1))(0)),
    literal_to_num, LAMBDA(l, pred_l(REDUCE(zero_l, SEQUENCE(l+1), LAMBDA(num, i, succ_l(num))))),


    BEGIN_LIB_TUPLE, "functions for pairs and tuples",
    make_pair, LAMBDA(a, LAMBDA(b, LAMBDA(f, f(a)(b)))),
    pair_first, LAMBDA(a, LAMBDA(b, a)),
    pair_second, LAMBDA(a, LAMBDA(b, b)),


    BEGIN_USER_CODE, "user code for this program cell",
    input, literal_to_num(E17),

    base_case, make_pair(zero_l)(one_l),
    factorial_next, LAMBDA(state, make_pair(succ_l(state(pair_first)))(times_l(succ_l(state(pair_first)))(state(pair_second)))),
    factorial, LAMBDA(n, n(factorial_next)(base_case)(pair_second)),

    RETURN_VALUE, "the output of this program cell",
    CONCATENATE(num_to_literal(input), "! = ", num_to_literal(factorial(input)))
)

This way, no boolean logic or subtraction is needed! Each state pair “evolves” n times to the next factorial, allowing us to compute numbers as large as 8! = 40320. If you think about it, this is technically a platform-specific optimisation that uses implementation-defined behavior of numbers, rather than explicitly recursing to evolve the state. But it works here, and the code is cleaner in any case.

Conclusion

The behavior of Lambda Calculus is surprisingly emergent and chaotic, despite operating without any built-in definitions for primitives such as numbers and booleans. Although the simple composition and application of functions is very limiting, we can actually re-create many of our programming practices from simple developments of this structure.