Road to the Y Combinator, Part II

02.04.2023 — Code — 3 min read

In Part I, we introduced a model for computation based on pure, anonymous functions, and started our journey to the Y Combinator. In this episode, we'll take a look at some functional refactorings to equip ourselves for the journey.

Sophistry and Parlour Tricks

In order to complete this transformation, we'll have to do a number of refactorings. Please note that some of these superpowers will only work in our sandbox because we are only playing with certain toys.

Change of name

Probably the simplest refactoring is to just change a name, and since all our names will be from function signatures, changing foo to bar will look like the following, in which all instances of the name foo which are not bound to a different foo will be changed to bar:

(foo) => (
    (baz) => (
        (foo) => (foo(foo))
    )
)('aFoo')

(bar) => (
    (baz) => (
        (foo) => (foo(foo))
    )
)('aFoo')

Note that the inner function expression with its own argument foo was not updated, since that variable shadows the outer one with the same name. We will avoid shadowing outer names in this exercise.

Tennent Function

Any expression <expr> may be substituted with a function that returns <expr> and is immediately invoked. For example:

2 + 3

(() => 2 + 3)()

It should be noted that, as with any other refactoring, the inverse of this refactoring, ie. removing a Tennent Function by replacing it with the expression it returns, is just as valid.

Add Binding

Simply add a parameter name to a function, and supply a value within the parentheses where it is invoked. Since the parameter isn't used yet, the value of the argument doesn't matter.

((foo) => { some: 'expr' })('aFoo')

((foo, bar) => { some: 'expr' })('aFoo', 'aBar')

Note that bar is a legal name, as long as there are no instances of bar in the function body which are free with respect to the function that receives the new binding. For our purposes, it will be fine to just pick a new name that doesn't occur in the program.

Wrap Function

Sometimes it is useful to compute something, but only when it is needed. This is called lazy evaluation. Wrap an expression whose value is a function, with a function that takes and passes the same number of arguments to that expression:

(x) => 1

(v) => ((x) => 1)(v)

Inline Value

Anywhere a name is used, the value to which the name is bound can be substituted for that name:

(cheese) => (
    (olives, sauce) =>
        makePizza(
            sauce,
            olives,
            cheese
        )
)('Cheddar')

(cheese) => (
    (olives, sauce) =>
        makePizza(
            sauce,
            olives,
            'Cheddar'
        )
)('Cheddar')

Now cheese is an unused binding; it could be removed or renamed as needed. We'll do the inverse of this refactoring also.

Summary

In this episode, we covered some functional refactorings in order to equip ourselves to derive the Y Combinator. In Part III, we'll express our recursion in pure anonymous functions, or lambdas.