Fibonacci

Summary

Nearly everyone is introduced to the famous Fibonacci sequence at some point during their scholastic internment. The earliest recorded description of the geometric ideas underlying this sequence are found in the Chandaḥśāstra by Pingala, wherein a Fibonacci number is called a mātrāmeru. In the West, this series was introduced in Liber Abaci by Leonardo Pisano Bigollo, better known as Fibonacci.

The sequence itself is charmingly simple:

$$1,1,2,3,5,8,13,21,34,55,89,144,233,377,\dots$$

And is defined by the recurrence relation:

$$F_{\mathrm{n}}=F_{\mathrm{n}-1}+F_{\mathrm{n}-2}$$

In other words, the first two terms are both 1, and every subsequent term is the sum of the two previous terms.

In this tutorial, we will implement a Fibonacci sequence generator. When we are finished, the result will look something like this:

Prerequisites

• Understand the material presented in the previous tutorials.

Goals

• Learn how to use the vertical line | (U+007C) message metacharacter to provide a choice among finitely many alternatives.
• Learn another loop control structure, "Until_do_".
• Learn more about functions:
  • Declaring an explicit return type for a function definition.
  • Closing outer variables into function definitions.
  • Constructing a function type (using "[«_‡,»]→_").
  • Applying a function (using "_(«_‡,»)").
• Learn about maps and map types.
  • Constructing a map type (using "{_→_`|}").
  • Constructing a map (using "{«_→_‡,»}").
  • Determining the cardinality of a map (using "`|_`|").
  • Subscripting a map in order to obtain an element (using "_[_]" and "_[_]else_").
  • Producing a map that includes a specific key-value binding (using "_+_→_").

Complete Sources

• Fibonacci.avail

Walkthrough

Following the outrageously long walkthrough of the Hilbert Hotel, I figured that we both deserved a shorter tutorial! The Fibonacci module weighs in at a mere 38 lines of code, so we'll be done before you can say "निरन्तरान्धकारिता-दिगन्तर-कन्दलदमन्द-सुधारस-बिन्दु-सान्द्रतर-घनाघन-वृन्द-सन्देहकर-स्यन्दमान-मकरन्द-बिन्दु-बन्धुरतर-माकन्द-तरु-कुल-तल्प-कल्प-मृदुल-सिकता-जाल-जटिल-मूल-तल-मरुवक-मिलदलघु-लघु-लय-कलित-रमणीय-पानीय-शालिका-बालिका-करार-विन्द-गलन्तिका-गलदेला-लवङ्ग-पाटल-घनसार-कस्तूरिकातिसौरभ-मेदुर-लघुतर-मधुर-शीतलतर-सलिलधारा-निराकरिष्णु-तदीय-विमल-विलोचन-मयूख-रेखापसारित-पिपासायास-पथिक-लोकान्".

Let's take this module from the top.

Lines 33-38. There is nothing new or noteworthy about the module header. The Fibonacci module declares a single entry point, "_st|nd|rd|th Fibonacci number", which the user can call with an ordinal in order to obtain the requested element of the Fibonacci sequence.

The method "a Fibonacci generator" (lines 40-51) takes no arguments. On line 51, the function definition declares an explicit return type, []→natural number; an explicit return type must follow a colon : (U+003A). []→natural number is a function type. This particular type includes all arity-0 functions that answer natural number. Function types are constructed using the method "[«_‡,»]→_", which accepts a list of parameter types separated by commas , (U+002C)(inside the brackets) and a return type (after the arrow). Explicit return types are not generally necessary, since the compiler infers the return type of a function definition to be the type of its last expression. However, this is handy when you wish to 1) weaken the return type to a more general type or 2) document the return type to assist a human reader. In this case, the explicit declaration was not necessary; I provided it for clarity only.

Now let's look inside. Lines 42-44 define the local variables x, y, and z, respectively. Each of these local variables can hold a natural number. x begins life uninitialized; it will be written before it can ever be read, so this is okay. y and z each start with the value 1. Notice anything interesting? Like… the first two terms of the Fibonacci sequence are both 1?

Lines 45-50 are the return value of "a Fibonacci generator": a function that operates on x, y, and z. Notice that these variables are defined in an outer scope, i.e, a scope that encompasses the new function. Ordinarily local variables are destroyed upon exit from the function that created them, but these variables will survive because they have been closed into the new function. We therefore say that the new function is a closure of x, y, and z. Closed variables survive for as long as the closure survives. In this scenario, the new function is the return value of "a Fibonacci generator", so each of the closed variables will escape the scope that defined them and survive for at least as long as the sender retains a reference to the new function.

The interior of the return value is very simple. When the function is applied, x assumes the value of y (line 46), then y assumes the value of z (line 47), and then z assumes the sum of x and y (line 48). On line 49, we see that the return value of this function is just x. On the first application of this function, the return value will be 1; on the second, it will also be 1; but on the third it will be 2, and on the fourth it will be 3, and so forth. If you trace the algorithm out in your head or on paper, you should see the Fibonacci sequence emerge after a few steps.

Line 53. The module constant generator is bound to the return value of "a Fibonacci generator". Note that the generator function has never yet been called; "a Fibonacci generator" hands back a hitherto unused generator function that is primed to deliver the first Fibonacci number when applied.

On line 54 we see something else new. The module variable cache is defined with type {natural number→natural number|}. This is a map type. A map is a directed relation from unique keys to unconstrained values; it is an unordered collection of key-value pairs, called bindings, that efficiently supports the ability to access a value given its key. Like tuples, maps are immutable; you will see this theme frequently repeated for Avail's data types. The type {natural number→natural number|} has as its instances every map whose keys (left of the arrow) and values (right of the arrow) are natural numbers. This type expression is just a send of the map type constructor, "{_→_`|}". cache is initialized to the empty map — the map with no bindings — by a send of the map constructor "{«_→_‡,»}".

Oh, you want to know what cache is actually for. Well, you would, wouldn't you? You always struck me as just that kind of person. Computing the 50,000^th Fibonacci number is fairly expensive, so it would be nice if we didn't have to compute it every time that it was asked for. This is where cache comes in. Its keys are Fibonacci ordinals, and the value associated with each key is the corresponding Fibonacci number.

Now we come to the main attraction, "_st|nd|rd|th Fibonacci number" (line 56). Vertical line | (U+007C), also called pipe, is a message metacharacter that alternates with message parts. A sequence of message parts interleaved with pipes forms a syntactic option group; the individual message parts of an option group are called syntactic options. (There are also semantic option groups, but we will defer treatment of these to a future tutorial.) When parsing a syntactic option group, any single syntactic option is considered to satisfy the grammar. Therefore 1st Fibonacci number and 8th Fibonacci number are both understood to be grammatically valid sends of the same message, whereas 4nf Fibonacci number is not (because the only valid syntactic options are st, nd, rd, and th).

Lines 60-69 are a send of "_[_]else_" to cache and an inline function definition. This is the safe variation of the subscript operator that we used on tuples back when we were managing the Hilbert Hotel. It has essentially the same meaning for maps that it has for tuples: If the key is present, then answer its value; otherwise, apply the "else" function and answer its return value. So if the ordinal n (line 58) is already in the cache, then use its value; otherwise, compute the requested Fibonacci number the hard way.

Lines 62-68 compute the n^th Fibonacci number "the hard way". The local variable next (line 62) holds the next Fibonacci number obtained from generator (line 65). Lines 63-67 work by looping until the cardinality (size) of cache ("`|_`|") is equal ("_=_") to the requested ordinal n, at which point next contains the requested Fibonacci number. next is returned as the answer on line 68.

Let's take a closer look at the loop and its contents before we declare victory. An "Until_do_" loop takes two functions — first a predicate and then a body — and works like this:

Though we have used functions in every tutorial thus far, and will likely use them in every tutorial hereafter, we have never explicitly applied a function yet. Function application is performed by sending "_(«_‡,»)" to the function (outside the parentheses) and its arguments (inside the parentheses). generator is arity-0, so it doesn't have any parameters and can't accept any arguments. Thus its application on line 65 just uses empty parentheses. This application is what causes the closed variables x, y, and z to get up and dance, thereby producing the next Fibonacci number.

This leaves us with only one line to ponder: line 66. If you were wondering where cache was getting updated, then wonder no further. The method "_+_→_" takes a map, a key, and a value, and produces a new map that includes a binding from the specified key to the specified value. In this case, we introduce a binding from |cache|+1, the ordinal currently being processed by the loop (the +1 is an adjustment for one-based ordinals), to next, the latest value produced by the Fibonacci sequence generator. The structure of the loop guarantees that every Fibonacci number less than or equal to the largest ever requested is present in the cache. So the first time that you ask for the 50,000^th number might be slow, but the second time will be very fast. If you then ask for the 49,999^th number, it will also be fast, because it got cached as a matter of course when the 50,000^th one was computed.

Further Reading

If you are interested to learn some applications of Fibonacci numbers, then you can read more on Wikipedia.

Encountering the Fibonacci sequence is an excellent excuse to learn more about the history of mathematics, which is a fascinating topic.

Exercises

The Fibonacci sequence is defined by a linear recurrence relation with constant coefficients, so it has a closed-form expression. The n^th Fibonacci number is given by the formula $F_{\mathrm{n}}=\frac{{\phi }^{\mathrm{n}}-{\psi }^{\mathrm{n}}}{\sqrt{5}}$, where $\phi$ is the golden ratio and $\psi$ is $1-\phi$. Build a new entry point, "_st|nd|rd|th closed-form Fibonacci number", that uses this formula to answer the requested element of the series. (Note that you will have to muck about with doubles and inexact answers.)

"_st|nd|rd|th Fibonacci number" does not forbid incorrect ordinal indicators, so you can run a command like 51nd Fibonacci number without a complaint from the compiler. Make the compiler more earnest about proper English grammar by disallowing inappropriate constructions. Start by renaming the method to "_«st|nd|rd|th»!Fibonacci number". This message uses the semantic option group («c0|c1|…|cn»!) construction, which must correspond to a natural number parameter (call it option). The values of option will range from 1 to n, and the exact value is determined by the option that appears at a call site. Once this is in place, you can use a semantic restriction that operates on the exact instance of option in order to reject an unwanted parse.

‹ The Hilbert Hotel

|

Return to Learn