# 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))))
```