The Fixed-Point Combinator Function

The goal of this article is to explain the purpose and functionality of fixed-point combinator functions. I had a hard time following along with other articles on this topic so I wrote this as a learning exercise. We’ll be using the Scheme language.

So what is a fixed-point combinator? It is a function which given a function as an argument, returns a fixed point of that function. Let’s demonstrate why this could be useful.

First, let start by defining a factorial function recursively:

(define fact 
  (lambda (n)
    (if (zero? n) 1 (* n (fact (- n 1))))))

Theoretically, if our language suddenly loses recursion as a feature we run into a big problem; we can’t refer to a function that is not bound! There is no ‘self’ keyword inside a anonymous function (which would let us reference the function from within) and therefore the function will no longer be valid:

(lambda (n)
  (if (zero? n) 1 (* n (??? (- n 1)))))

To clarify, the function is actually valid, but only for an input of 0:

; 0 -> 1

((lambda (n)
  (if (zero? n) 1 (* n (??? (- n 1))))) 0)

But if we try with any other value, it will fail:

; 1 -> error: unbound symbol (???)

((lambda (n)
  (if (zero? n) 1 (* n (??? (- n 1))))) 1)

An input of 1 does not fulfill the first condition (zero?), so it attempts to call ??? with (- n 1) as it’s argument. ??? is a symbol not bound to anything so an error is raised. However, we do know that for the current call the expression (- n 1) is equal to 0, since n is bound to 1. We know this function works for zero, so we know we can simply substitute it in for ???. Now we have a function that works for two inputs: 0 and 1:

((lambda (n)
  (if (zero? n)
      1
      (* n ((lambda (n)
              (if (zero? n) 1 (* n (??? (- n 1))))) (- n 1))))) 1)

Using the former logic we can continue this process, replacing ??? with our ‘factorial’ lambda; creating a function that can work with another successive input. This could get tedious, so let’s write a function that does that for us. It will consume a function (f) and return the factorial function, replacing ??? with the input (f). If we provide this new function a factorial function it will have a factorial function to run if the term is not 0.

(define fact-gen
  (lambda (f)
    (lambda (n)
      (if (zero? n) 1 (* n (f (- n 1)))))))

By itself, the return value is our fact0 function, which we used unbound earlier, Since an input of 0 doesnt call the f function, we can pass anything we’d like.

(define fact0 (fact-gen 'trash))
 -> (lambda (next)
      (lambda (n)
        (if (zero? n) 1 (* n ('trash (- n 1))))))

(fact0 0) -> 1

However, due to the conditional statement, if input is greater than 0, the argument will be called, and that’s simply impossible as it is currently is just a ‘trash symbol.

(fact0 1) -> ERROR

We need to supply a function that will give us the factorial of (- 1 1). Wait a second… That expression equals 0… We already have a function that gives us the factorial of 0… Let’s run fact-gen and pass it fact0.

(define fact<=1 (fact-gen fact0))

Using this newly generated function, we can find the factorial of any number equal or less than one. Can we continue? In fact, yes!

(define fact<=2 (fact-gen fact<=1))

Now the next step is clear. We need to supply the consecutive factorial function to the previous factorial function n + 1 times (starting at 0). How can we continually feed the fact-gen function these next factorial functions? Turns out that a combinator function can do that for us:

(define combinator
  (lambda (func)

    (define make-step
      (lambda (next-step)
        (lambda (arg)
          ((func (next-step next-step)) arg))))

    (lambda (arg)
      ((func (make-step make-step)) arg))))

Notice that the returned lambda at the end of combinator function and the returned lambda for the locally scoped function make-step, are exactly the same. This is crucial. That means that when the generated factorial function needs the next factorial function, it simply inserts itself again. Let’s walk through this. Running (combinator fact-gen) will return:

; figure-1
(lambda (arg)
  ((fact-gen (make-step make-step)) arg))

When this function is called with any argument it will first resolve the expression (make-step make-step). This function call will return the following:

; figure-2
(lambda (arg)
  ((fact-gen (make-step make-step)) arg))

Does this look familiar? Its the same as before! This is the fixed point. As seen in figure-1, this lambda (figure-2) will serve as the argument for the (fact-gen figure-2) function call, which returns:

; figure-3
(lambda (n)
      (if (zero? n) 1 (* n (figure-2 (- n 1)))))

Let’s call it with the argument of number ‘1’: (figure-3 1). Since 1 is not zero? the control flow will evaluate the next expression: ( 1 (figure-2 (- 1 1)))*. Which includes the function call (figure-2 (- 1 1)). This will return the following:

((fact-gen (make-step make-step)) arg)

(make-step make-step) will again return:

; figure-4
(lambda (arg)
  ((fact-gen (make-step make-step)) arg))

and the whole figure-2 call will evaluate to:

; figure-5
(lambda (n)
      (if (zero? n) 1 (* n (figure-4 (- n 1)))))

Just to clarify, we are currently evaluating ( 1 (figure-2 (- 1 1)))*. n is bound to 0 in figure-5, so the if expression returns 1. Therefore everything resolves to:

(* 1 1) -> 1

And that’s pretty much it. We can simplify the whole thing by eliminating our locale definition of make-step and replacing our readable variables with single letters:

(define Z
  (lambda (f)
      (lambda (a)
        ((f ((lambda (y) (lambda (a) ((f (y y)) a)))
             (lambda (y) (lambda (a) ((f (y y)) a))))) a))))