This blog post is homage to Jim Weirich and his contribution to the FP community in general - and the Ruby community in particular. Jim was a skilled and effective communicator, and his video helped me get started on grokking the Y-combinator.

I dedicate this blog post to Prof. Neeldhara Misra whose friendship and encouragement I have come to rely on! Thank you for re-igniting a passion to learn, explore, and teach! Keep walking!

• 1. Introduction
• 2. First steps
• 3. It’s continuations all the way down
  • 3.1 Mind the first step, it’s a doozy!
  • 3.2 Oh look, a rabbit hole!
  • 3.3 Please Repeat Yourself!
• 4 The Lambda Calculus
  • 4.1 Lambda Calculus (The Absolute Shortest Ever Explanation)
  • 4.2 The Javascript Version
  • 4.3 Looping back to recursion
  • 4.4 The Fixed Point Generator
  • 4.5 Whoa, Nelly!
• 5 Curing Schizophrenia
• 6 Lifting Heavy Things…
  • 6.1 Logging and Tracing
  • 6.2 Memoization
• 7. Conclusion

1. Introduction

When I was taught programming back in my high school and undergraduate days, goto, for-loops and while-loops were taught as a fundamental building blocks for control-flow. It was unthinkable to me in those early days that one could have a programming language that had none of these primitives in it; and I humbly posit that things haven’t really changed much in introductory programming courses these days.

Of course, once we were taught that you could have a function which called another function, then the natural question to ask was “can a function call itself”. I’m old enough to have encountered languages where this was not possible, but modern languages like Pascal and C allowed a function to call itself, and that led to very elegant implementations of self-referential data structures like linked lists and graphs. So recursion was introduced as a language feature.

Later, in my undergraduate days, we were introduced to LISP and LISP-like languages which primarily used recursion for control-flow; for- and while- loops were actually syntactic sugar over forms of recursion, offering a glimpse of an insight that recursion was somewhat more fundamental than we’d recognized that far. I invite you to dive into a secondary rabbit hole of expressivity in languages at your leisure.

In the software development industry, where I made most of my career, there is an ill-founded reticence to use recursion - allegedly for performance reasons, but really because recursion is more feared than understood. Some advanced algorithms like graph and tree traversals are painstakingly written out iteratively because there’s a laughably naive notion that this way is somehow better, belying the true power and elegance of recursion. I’ve addressed some of these misconceptions and FP remedies before.

So, let’s accept that recursion is beautiful and elegant, and actually more fundamental than other control structures (although perhaps not the most fundamental of all).

But where does it come from? And can we somehow derive it from first principles? That is what this blog post is about.

I strongly recommend reading this post in conjuction with Jim Weirich’s video and an open F# Interactive Window, working through the individual steps. The “a-ha” moment is well-worth working towards! It is not coincidental that this blog post follows the video closely, and I gladly acknowledge Jim’s efforts in trying to make this tricky concept clear. All I’ve done is try to put it into the F# context and address some of the mechanics of adapting to a strongly-typed language!

2. First steps

At some point in your F# coding - possibly very early on - you’ll encounter a let rec binding, because without the rec, the function being defined can’t be called within its definition. So this code compiles:

let rec fact =
    function
    | 0 -> 1
    | n -> n * fact (n - 1)

I use this example with reticence - I agree with Dr. Shriram Krishnamurti that this isn’t the best way to teach recursion - but given that it is 1) easily understandable - if not relatable - and 2) doesn’t have any associated data structures, it makes the mechanical steps we are going to perform a little easier.

In fact, you can invoke this function and it will eventually return the required factorial:

fact 10 // returns 3628800

Now, let rec is clearly a language construct: it’s a way to tell the F# compiler that the binding should be deferred until the definition is complete, so that the function can invoke itself. But that’s not really a good explanation of how recursion itself is derived. So let’s dig a little further and see if we can derive a way to do recursion without let rec.

3. It’s continuations all the way down

Well, functions can call functions, and functions are first-class items so they can be passed in as function arguments, so why not just pass in the function we want to call as an argument and just call that?

3.1 Mind the first step, it’s a doozy!

let f omega =
    (fun x -> 
        match x with
        | 0 -> 1
        | n -> n * (omega (n - 1)))

Let’s unpack this carefully here: f is a function, which takes omega as a single argument, and returns an anonymous function which takes one integer argument and has the recursive form of the factorial function as its body - except that it calls omega instead of itself. omega here is a continuation, which, loosely, is just a fancy way of saying “here, call this function when you want to move on”!

Now this only syntactically looks like a recursive function - there’s no recursion happening here. In fact, since the only restriction on omega is that it should be invoked with a single integer argument, we can actually pass in any old function that fulfils that requirement.

let error x = failwith $"{x} goes Boom!"

Here, error is a function that takes an argument and just throws an exception. We can pass it in to f, and this happens:

let fact0 = f (error)
fact0 0 // returns 1
fact0 1 // "0 goes Boom!"

Let us carefully understand why it works like this: f error (aka fact0) is a function which takes a single integer argument and matches it against 0 (returning 1), or anything else (where it tries to multiply its argument with the result of omega invoked on the next smaller number).

So when we invoke fact0 with 0, the match condition triggers a valid return; but when we invoke it with 1, the match condition triggers a call to omega. In our case, the omega passed in is error, which ignores whatever argument is passed in and throws an exception instead.

(It’s worth pointing out that functional programmers love total functions, and so eschew exceptions because functions which throw don’t return a value for all arguments like well-behaved functions do. I’m deliberately throwing an exception here to violently jar us from a state of complacence - to show that something undesirable needs to be dealt with. We’ll get rid of this behaviour soon, so just excuse it for now!)

3.2 Oh look, a rabbit hole!

Now that we’ve understood why there’s no mystery at all to this behaviour, let’s take the next step:

Remember that fact0, just like error, is a function that takes a single argument. So why can’t we pass that into f instead?

let fact1 = f fact0
fact1 0 // returns 1
fact1 1 // returns 1
fact1 2 // "0 goes Boom!"

And indeed, because we’re on a roll here, let’s go one further:

let fact2 = f fact1
fact2 0 // returns 1
fact2 1 // returns 1
fact2 2 // returns 2
fact2 3 // "0 goes Boom!"

I encourage you to actually try this to see that it actually seems to be starting to calculate the factorial. Then come back and see if this explanation of why it works is reasonable:

Given:

let f omega = (fun x -> match x with | 0 -> 1 | n -> n * omega (n - 1))

let error x = failwith $"{x} goes Boom!"

let fact0 = f (error)
let fact1 = f (fact0)
let fact2 = f (fact1)

We can expand out the fact2 definition:

let fact2 = 
    (f fact1) // textually replace fact2 with its expression
    => (fun x -> match x with | 0 -> 1 | n -> n * fact1 (n - 1)) // textually replace f with its expression and replace the omega argument with fact1
    => (fun x -> match x with | 0 -> 1 | n -> n * (f fact0) (n - 1)) // textually replace fact1 with its expression
    => (fun x -> match x with | 0 -> 1 | n -> n * (fun x' -> match x' with | 0 -> 1 | n' -> n' * fact0 (n'-1)) (n - 1)) // textually replace f with its expression, renaming n to n', and replace the omega argument with fact0
    => (fun x -> match x with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * fact0 (n'-1)) // textually replace the x' argument with (n - 1)
    => (fun x -> match x with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * (f error)(n'-1)) // textually replace fact0 with its expression
    => (fun x -> match x with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * (fun x' -> match x' with | 0 -> 1 | n'' -> n'' * error(n'' - 1))(n'-1)) // // textually replace f with its expression, renaming n to n'', and replace the omega argument with error
    => (fun x -> match x with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1)) // textually replace the x' argument with (n'' - 1)

These are basically mechanical rewrites - replacing function names with their bodies possibly with renaming formal parameters to avoid name collisions, and replacing formal parameters in function definitions with the arguments passed in.

When we consider the expression fact2 0, we evaluate:

fact2 0
    => (fun x -> match x with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1)) (0)
    => (match 0 with | 0 -> 1| n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (match 0 with | 0 -> 1 (*| n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1)*))
    => 1

Let’s see what happens with fact2 2:

fact2 2
    => (fun x -> match x with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1)) (2)
    => (match 2 with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (2 * match (2 - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (2 * (* match (2 - 1) with | 0 -> 1 | n' -> *) (2 - 1) * match ((2 - 1) - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (2 * 1 * match (1 - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (2 * 1 * match 0 with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (2 * 1 * match 0 with | 0 -> 1 (* | n'' -> n'' * error(n'' - 1)*))
    => (2 * 1 * 1)
    => 2

Now, when we do the same thing with fact2 3, something interesting happens

fact2 3
    => (fun x -> match x with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1)) (3)
    => (match 3 with | 0 -> 1 | n -> n * match (n - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (3 * match (3 - 1) with | 0 -> 1 | n' -> n' * match (n' - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (3 * (* match (3 - 1) with | 0 -> 1 | n' -> *) (3 - 1) * match ((3 - 1) - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (3 * 2 * match (2 - 1) with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (3 * 2 * match 1 with | 0 -> 1 | n'' -> n'' * error(n'' - 1))
    => (3 * 2 * (* match 1 with | 0 -> 1 | n'' -> *) 1 * error(1 - 1))
    => (3 * 2 * 1 * error (0))
    => failwith "0 goes Boom!"

There’s something tantalizing about this approach: one the one hand, we can actually see the composition of the factorial working out nicely, but on the other hand, we have the write fact3 in terms of fact2, and we only get the result when we call the appropriate factN with exactly n otherwise the computation "goes Boom!".

3.3 Please Repeat Yourself!

Let’s consider fact0 0, which as we have seen expands to f (error) 0, and insert the definition of f as an anonymous function. (Note that I have replaced the explicit match expression with the more succinct, but completely equivalent, F# syntax)

The following expression should evaluate to 1

(fun omega ->
    function
    | 0 -> 1
    | n -> n * omega(n - 1)
) (error) 0

Let us put a wrapper function around this, which curries in error but takes the anonymous function as its argument. Again, this rewrite is entirely equivalent.

(fun x -> x error)
    (fun omega ->
        function
        | 0 -> 1
        | n -> n * omega(n - 1)
    )
    0

What we’ve done here is created a “runner function” which takes a function x and then calls it with error. We then pass in a “workload function” to compute the factorial in as the value of x.

The behaviour before and after the rewrite is identical. Both these functions work for 0 and blow up for 1 just as we expect.

Now, instead of explicitly writing out fact0, fact1, fact2 and so on as before, we could just do repeated invocations of x in the runner function:

(fun x -> x(x(x(x(error)))))
    (fun omega ->
        function
        | 0 -> 1
        | n -> n * omega(n - 1)
    )
    3 // succeeds
    // 4 // fails

This is actually a kind of cool rewrite. We’re passing in the behaviour we want to be repeatedly performed as an argument to some runner function that does the repetition. That is, we’ve separated out the concerns of doing repetition and computing the factorial into two separate pieces.

Now we observe that factN - or its anonymous equivalent - produces the correct value when it is invoked with N. By seeing how the functions get evaluated, we realize that this is the only way to get to fact0 0, in which case the terminal branch of the match occurs and the error function is not called.

Now all we need to do is to invoke x the correct number of times automatically, and since we’ve separated out concerns, we may only need to do this once for any and all repetitive work we want to do!

Before we figure out how to do that, let’s step back and learn a few more concepts, and then return to this problem!

4 The Lambda Calculus

Because we’ve been working so far with F#, which is a Turing-complete language with recursion primitives, it would seem that it is completely fair to criticise our efforts as unnecessary. Recursion already exists in the language.

So let’s actually learn a tiny little language that has none of these conveniences and get a better sense of the power of this approach. Let’s consider the most foundational of such languages - Lambda Calculus - which has none of the various concepts that traditionally seem inseparably linked to programming and programming languages, such as:

• [❌] Variables
• [❌] Names and Assignment
• [❌] Increment/Decrement
• [❌] Test-and-Branch
• [❌] GOTO
• [❌] Loops
• [❌] Booleans, Integers, Strings or any Types

Anyone who’s starting programming with something close to silicon - say on a microprocessor - would, justifiably, be entirely skeptical that a useful, if not Turing-Complete, language could be possibly be built without any of these primitives.

However, the Lambda Calculus is provably Turing Complete even though it only includes the following two concepts:

• [✅] Function Definition
• [✅] Function Application

Let’s work with just these two concepts and try to synthesize recursion before returning to expressing it in F#.

4.1 Lambda Calculus (The Absolute Shortest Ever Explanation)

The simplest function of all is one that takes an argument and returns it. That’s it.

We write such a function in the lambda calculus as λx.x. In this notation, the λ denotes the definition of an anonymous function, the x (and other symbols) to the left of the . refer to the formal parameters of the function, and the expression to the right of the . is the body of the function. In this example, we take an argument to this anonymous function and return it - the quintessential identity function.

As is immediately obvious, the x really has no implicit significance in the above form - it’s just a symbol. The form λy.y is absolutely identical. So we are free to rewrite any lambda by renaming all occurrences of a symbol with a different symbol that has not been used before. You may run into this in the literature as the α-conversion rule, and it is handy to resolve name collisions when you’re working with a lot of composed forms.

The only other operation afforded to us in lambda calculus is function application, which we represent as just a space-separated sequence of symbols with the function to be applied on the left and the argument to apply the function on to the right.

Like this: (λx.x) b

This is read as “take the function on the left (viz (λx.x)) and apply it to the argument on the right (viz b)”.

To do this, we take the function body and replace all instances of the argument symbol x with the parameter value b, resulting in b, which is what you expect when you apply the identity function on a value b. You may run into this in the literature as the β-reduction rule.

And that’s it. We’re done with Lambda Calculus. All of it.

Going forward, I’m going to skip the formal notation used in mathematical literature and write out actual functions in a weakly typed language in Javascript so we can actually run and evaluate these forms in a browser!

4.2 The Javascript Version

You can generally fire up a Javascript Evaluator in your favourite browser and run the code here in the Console. You can also watch this video for an beautifully detailed explanation of what I’ve summarized here.

Our identity function is simple and elegant: x => x. This is exactly the same expression as λx.x in Javascript syntax.

Applying this function (illegally, because numbers aren’t really allowed in Lambda Calculus) does what is expected: (x => x) (2) // returns 2

Since Lambda Calculus doesn’t have booleans or if-statements, we’re not going to use those constructs from Javascript either. We’re going to build those up from scratch. And since everything in Lambda Calculus is a function, booleans are functions! We’ll define TRUE as a function that takes two arguments and returns the first one, and FALSE as a function that takes two arguments and returns the second.

(t, f) => t) // TRUE
(t, f) => f) // FALSE

Now we can define the NOT function as one that takes a boolean and returns its complement.

b => b(((t, f) => f), ((t, f) => t))

We can see that this gets unwieldy very quickly, so we are going to cheat and allow aliases, noting that we could mechanically replace an alias with its value (with perhaps an α-conversion to resolve name collisions) whenever we wanted to. This leads to a much more tractable approach straightaway:

TRUE = (t, f) => t;
FALSE = (t, f) => f;
NOT = b => b(FALSE, TRUE);

// check
NOT(TRUE)("true", "false"); // evaluates to "false"
NOT(FALSE)("true", "false"); // evaluates to "true"

We can implement other boolean operations and the if-then-else construct

AND = (x, y) => x(y, FALSE);
OR = (x, y) => x(TRUE, y);
IF = (b, x, y) => b(x, y);

//check
IF (AND (TRUE, TRUE), "left", "right"); // evaluates to "left"

I’ll leave it to you to discover how numbers and math operators can be implemented with functions, with the hint that these are called “Church Numerals”.

Once we’ve done all this, we can effectively pretend that we can use numbers, strings, booleans, and if-statements because we have built these up from scratch using nothing but function definition and application - and some entirely mechanical assistance for aliasing and application of rules.

4.3 Looping back to recursion

We still do not have any mechanism for looping or repetitive constructs though. So let’s see how we can implement that using just functions.

Consider a function that takes an argument and applies it on itself. Thus: x => x (x);

Javascript doesn’t complain when we define that function because it is effectively an untyped language in this scenario. And since it’s not actually being applied on anything, the definition is just latently present.

However, something interesting happens if we apply this function on itself, like this: (x => x(x)) (x => x(x));

This immediately evaluates to a stack overflow - indicating that we’re trying to create a kind of infinite “loop” by infinitely recurring!

The reason why this works becomes apparent when we alias it

g = x => x(x);
g (g)

In the first line, we say that g is a function that takes a function x and applies it on itself. In the second line, we pass in a function that applies itself on itself, to a function that applies itself on itself. If that sounds like a headlong fall into the abyss, it’s because that’s exactly what it is. The function x calls itself by calling itself in a kind of forever evaluation. And this is actually exactly what we were looking for - a kind of infinitely repetitive structure.

This way of synthesizing repetition from nothing more than function application was invented by Haskell Curry, who used this construction to demonstrate a logical construct called Curry’s Paradox. Dive down that rabbit-hole at your own discretion!

4.4 The Fixed Point Generator

Let’s harness the repeated invocation by doing something useful like calling a function f each time. Since we’re not sure what f to use, let’s pass it in as an argument, thus: f => ((x => f(x(x)))(x => f(x(x)))).

Now let’s see what happens when we invoke this function with a function argument g:

(f => ((x => f(x(x)))(x => f(x(x)))))(g) evaluates to the following expression where the formal parameter f in the body of the anonymous function above is replaced with the actual value g:

(x => g(x(x)))(x => g(x(x)))

Now let’s do the same thing again, and apply the right function to the left one - so every x in the left expression is replaced with the right expression. Let us explicitly observe the steps performed mechanically as follows:

1. Start with (x => g(x(x)))(x => g(x(x)))
2. The left part is a function with one argument x and body g(x(x)). If we pass in a value, say b, for x, we mechanically replace x with b in the body of the function, leaving the evaluated value g(b(b)).
3. We therefore replace the x in the body with the function passed in, viz (x => g(x(x))). This results in the value g ((x => g(x(x))) ((x => g(x(x))))).
4. We note that the right part of the expression, viz (x => g(x(x))) (x => g(x(x))) is what we started out with!

That is to say, if we alias the initial expression as Y = f => ((x => f(x(x)))(x => f(x(x)))), then the invocation Y(g) evaluates to g(Y(g))!

Expanding this out a few more times results in the following equivalence chain:

Y(g) = g(Y(g)) = g(g(Y(g))) = g(g(g(Y(g)))) ...

Now this should be somewhat exciting, because when we left the last section we were looking for a way to generate repeated calls to x, and now we seem to have found something that might be able do that!

You’ll come across the term fixed-point in the literature. Y is a fixed-point generator for g in this example.

4.5 Whoa, Nelly!

By looking at this code, we realize that it does almost what we want it do - but it never stops!

The reason it doesn’t stop is because when we ask for Y (g), JavaScript tries to eagerly evaluate all invocations of g at once, and it rapidly descends into the infinite recursion abyss. What we want is for some way to say “Hey, I am going to give you a g - call it only when you need its value”. That way, we can call g sequentially, but we can craft a termination condition into g and get the Y function to stop recurring.

We can do this by wrapping g with a function - which only evaluates g when the wrapper function is evaluated.

More generally, the following rewrite is completely equivalent modulo the delayed evaluation! Given a value or expression x, we can always write it as (n => x)(n). In fact, it doesn’t matter what n is - just that the value of x isn’t evaluated until that wrapper function is called.

Let’s make our Y function lazy thus:

1. Take the body of the Y function: f => ((x => f(x(x)))(x => f(x(x))))
2. Wrap every x(x) expression with a suspension function: f => ((x => f(n => x(x)(n)))(x => f(n => x(x)(n))))
3. Call this expression Z, because it’s a lazy version of Y and merits its own name: Z = f => ((x => f(n => x(x)(n)))(x => f(n => x(x)(n))))

Now let’s pass in our familiar function to Z and try to compute the factorial

fact = Z (f => x => x == 0 ? 1 : x * f (x - 1));
fact (10); // returns 3628800

Hurray! This works!

So we’ve finally hit upon our solution:

1. Use a cleverly crafted completely generic expression (thank you, Haskell Curry!) to generate an infinite number of calls in an environment that only supports function definition and application
2. Harness the infinitely recurring mechanism to invoke some workload function we want to use repeatedly
3. Play some mechanical tricks to introduce lazy evaluation into an eagerly evaluated language
4. Terminate the infinite loop at exactly the right time so that the workload function is invoked the correct number of times

Ok, let’s return to the F# world and try the same approach!

5 Curing Schizophrenia

F# is even further removed from the untyped lambda calculus than JavaScript, since it is both eagerly evaluated and strongly typed. This leads us to have to do some type gymnastics to implement what came somewhat more easily in JavaScrupt.

Naively transcribing the Z combinator from above gives us

(fun f ->
    (fun x -> f (fun n -> (x x) (n)))
        (fun x -> f (fun n -> (x x) (n))))
    (fun p ->
        function
        | 0 -> 1
        | n ->
            n * p(n - 1))
    10

This does not typecheck - and it is instructive to unpack why:

First, let’s see what the compiler complains about with the x in the first expression:

The x parameter is referred to twice in the body - first as a function and then as an argument to that function. Clearly the type system is inadequate to describe this schizophrenic behaviour. What we really want it to do is blindly start recurring, which is what it did in the weakly-typed JavaScript. Roughly speaking, we want x to be a function that takes an object and returns whatever the result of f is.

So we can annotate the type with the weaker definition as follows

(fun f ->
    (fun  (x : obj -> _) -> f (fun n -> (x x) (n)))
        (fun x -> f (fun n -> (x x) (n))))
    (fun p ->
        function
        | 0 -> 1
        | n ->
            n * p(n - 1))
    10

This has the desired effect and the compiler accepts the first expression as valid. This forces the type inference of the second lambda to take an argument of type obj.

Of course, this then completely confuses the F# compiler, because we go ahead and apply the value x as a function in the body of the second lambda. So the compiler complains saying that it can’t apply an object like a function.

In reality, because the only object type in lambda calculus is the function type, x is both an obj and a function, so we have to encode this schizophrenic behaviour as type annotations.

(fun f ->
    (fun (x : obj -> _) -> f (fun n -> x x n))
        (fun x -> f (fun n -> (x :?> obj -> _) x n)))
    (fun p ->
        function
        | 0 -> 1
        | n ->
            n * p(n - 1))
    10

// 3628800

We agree with the type-checker that the parameter x to the second expression is an object, and then arm-twist it to treat it like a function when we need to apply it. We can do this because we know that it’s really a function and we’re only disguising it as an object to get around strong typing.

This now runs just fine, and we’ve successfully synthesized recursion using just function application some type gymnastics. Just like we did in JavaScript, we can christen the Z combinator.

let Z f = 
    (fun (x : obj -> _) -> f (fun n -> x x n))
        (fun x -> f (fun n -> (x :?> obj -> _) x n))

To my eyes, this is only a tiny bit less elegant than the JavaScript version!

Z = f => (x => f(n => x(x)(n))) (x => f(n => x(x)(n)))

6 Lifting Heavy Things…

We’ve worked through a lot of concepts to get to this point. We’ve had to try to synthesize recursion by building up repetition manually, grok Lambda Calculus, play with JavaScript and encounter the Y and Z combinators, and then do type-gymnastics to transliterate the solution to F#.

Was there a point to all of this? After all, F# and JavaScript both have native support for recursion, so this does feel like a lot of activity with a useless, albeit academically curious, resolution.

Or is it?

6.1 Logging and Tracing

Let’s go back to the factorial generator function:

let fact_gen =     
    (fun p ->
        function
        | 0 -> 1
        | n ->
            n * p(n - 1))

Now we know that the fixed point of this function is the fact function which computes the factorial of a number.

let fact = Z fact_gen

fact 10 // 3628800

Now, let’s say we want to actually log each invocation of fact_gen, but without having to modify the fact_gen code itself. This is a reasonable requirement, as we have gone through some effort to separate out the concern of computing a factorial term from everything else, and we don’t want to start mixing other concerns like logging into it!

Now, one observation we made when we derived the combinator was that the g we passed into Z g was invoked once per “iteration”. Now we want to do two things per iteration - log that iteration happened, and compute the factorial term. As functional programmers, we have a favourite tool for this kind of thing: function composition, so let’s use it:

let log (f : 'a -> 'b) =
    (fun x ->
        let result = f x            // invoke the function we're logging...
        printfn "%A -> %A" x result // ...and log the argument and result
        result)

let fact_with_log = Z (fact_gen >> log)
fact_with_log 13

which prints out

6.2 Memoization

Let’s really take advantage of the fact that we get control on every recursion stage now.

Memoization is a powerful technique to trade off space for compute time, providing an elegant way to reduce recomputation. We can write a naive memoize function for a function of one argument like this:

let memoize (map : System.Collections.ConcurrentConcurrentDictionary<'a, 'b>) (f : 'a -> 'b) =
    (fun x -> map.GetOrAdd(x, f))

let m

We could use this with a simple function as follows:

let square x = x * x
let square x = x * x

let sqm = memoize (new System.Collections.Concurrent.ConcurrentDictionary<_,_ > ()) (log square)
sqm 3 |> printfn "%A";
sqm 3 |> printfn "%A";
sqm 3 |> printfn "%A";

which results in

Clearly showing that that the actual square method was called once, and the next invocations just found and returned the result from the cache.

Why is this naive? Well if we tried to use this on a recursive function, memoize would only be able to wrap the outermost call - and the inner recursive calls would still be executed repeatedly.

Let’s see this in action:

let rec fib = 
    function
    | 0 -> 1
    | 1 -> 1
    | n -> fib (n-1) + fib (n-2)

let time (f : unit -> 'a) =
    let timer = new System.Diagnostics.Stopwatch()

    timer.Start()
    let result = f()
    timer.Stop()

    (result, timer.ElapsedMilliseconds)
    
time (fun () -> fib 45) |> printfn "%A"

This eventually finishes in about 5.5s

Contrary to most expectations, memoizing this function will not improve anything:

time (fun () -> (memoize (new System.Collections.Concurrent.ConcurrentDictionary<_,_ > ()) (log fib)) 45) |> printfn "%A"

We note that the log method is only called once, and the time is roughly the same.

Of course, we can see why immediately - it’s because the recursive calls in the body of fib have not been memoized, and indeed we have no way of doing that without rewriting the innards of the fib function.

However, if we recognize that the fixed-point combinator gives us control over each recursive invocation, allowing us to intercept the call and either update or access the cache, then it becomes possible to gain the benefits of memoization very elegantly.

For this, we extract the fib computation from the in-built F# recursion mechanism, and memoize that:

let fib_gen fib =
    function
    | 0 -> 1
    | 1 -> 1
    | n -> fib (n-1) + fib (n-2)

let fib = Z (fib_gen >> (memoize (new System.Collections.Concurrent.ConcurrentDictionary<_, _>())) >> log)

time (fun () -> fib 45) |> printfn "%A"

And there we have it - each call to compute fib happens only once, as is evidenced by the log - and the whole computation takes 4ms instead of a thousand times longer.

This is actually a real-world example of where we would need to understand and use fix-point combinators, because they give us a much more flexible and controlled mechanism to do recursion - and this kind of control is what makes all the effort we put in worth it - even though languages like F# and JavaScript have in-built recursion.

Are there any other applications that come to mind as you read this?

7. Conclusion

We’ve finally reached both a deeper understanding of the functional foundations of recursion, and seen some of the power of what it affords.

• We started with continuations and separated out the mechanism for invocation from the workload being invoked.
• Then we switched to an untyped language and encoded a few primitives of lambda calculus, showing how we could derive all the familiar things we were taught as primitive from just function definition and application
• We then borrowed an idea from Haskell Curry and came up with a scheme of function application that goes on forever,
• We then crafted a way to inject the workload function into this scheme so we could do repeated invocation. This resulted in the Y combinator
• Then, because we started with a language that did eager evaluation, we found a way to suspend computations so we could terminate the invocation sequence based on the workload. This resulted in the Z combinator
• Then we took that scheme and got it to work in a strongly-typed language like F#.
• Finally, we saw some examples that used the fact that we had much more control over the recursion using the Z combinator to do something we couldn’t do with the language-provided recursion mechanisms.

I hope this rather lengthy document was lucid and effective in its explanation of the Y (and Z) combinators as Jim’s talk was. Again, we - as a community - continue to be indebted to his work and contributions.

I also hope that this gave you a flavour of how powerful and useful recursion can be.

In fact, the point has been made, and cogently, that the entire branch of dynamic programming which seeks to obviate recomputation by cleverly refactoring the problem to be solved can be profoundly impacted by using memoization - which achieves the same goal without sacrificing a (usually succinct) top-down description of the problem.

But that is a discussion for another day, and this is a good place to stop.

Happy Holidays!