In this article, we will look into encoding the Fibonacci function using the
fix-point combinator. This is an interesting function as it can be used
to implement general recursion in a programming language.
To set a context we first need to discuss some programming language fundamentals: In daily speech, programmers are used to programming languages being express all possible computations. This is, they are Turing complete.
However, often we want a programming language to support various properties. Some often discussed properties are type safety, which entails that programs that compile also runs without errors, and normalization, which roughly says we always get a result.
An often used framework for reasoning about these properties is the simply typed lambda calculus (STLC) with friends. With the raw STLC, it is not possible to encode general recursion. Hence we need to add a friend, which makes it possible.
This friend could be the fixed point operator.
Day 11 - Fix
fix operator looks as follow:
In this article we let Haskell be our syntactical point of view. This is because we then will have an interpreter for free.
ghci interpreter we may define the function as follows:
> let fix f = let x = f x in x
We now have a function
fix that takes a function as the argument,
applies it to
itself and returns the result. If the function we apply
fix on returns a
value, then fix will return a value:
> fix (\rec -> "Hello Fix!") "Hello fix!"
Next, if we just apply the function on itself we will get an infinite loop:
> fix (\rec -> rec) ^CInterrupted.
Now, this makes sense, as we continuously attempt to apply the lambda function on itself.
In above example, we only have a single argument,
n, which is the function
itself. We can say that we have the recursion directly in our hands. But to
be able to do something interesting, like calculating the i‘th Fibonacci
number, we need to add an argument we can decrement on. First a simple
> fix (\rec n -> if n == 0 then 0 else n + rec (n-1)) 10 55
In above example we use the
if to return a value when we hit 0, otherwise
we apply the function on n-1. The expression simply adds all numbers from
0 to 10.
From here it is straight forward to implement the Fibonacci function. We need to have a nested if-statement, as we have two base cases. Otherwise, it is very similar to the function above.
> let fib = fix (\rec n -> if n == 0 then 0 else if n == 1 then 1 else rec (n-1) + rec (n-2)) > fib 10 55
This is a directly recursive implementation of the Fibonacci function. This is indeed visible from time complexity, and it is not feasible to compute the Fibonacci number of large numbers. It is indeed possible to augment above implementation with an accumulator.
Above implementation is interesting as we completely separate the recursion from the actual computation. In an earlier article, I implemented the function in Haskell using normal function syntax. Here the distinction between the recursion mechanism and the calculating mechanism is not as distinct.
The separation is especially interesting when formally reasoning about programming languages as we can get clutter away. This, however, is much easier when doing this in dedicated languages.
Above examples are kind of futile in Haskell, as it already supports better
functionality for solving the Fibonacci function. It is, however, interesting
to think about what a minimal language for solving the function would be.
In above implementation, we need support for
constructions, and natural numbers. This is four language constructions.