## 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`"_+_→_"`

).

- Constructing a

### Complete Sources

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

s. 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 `tuple`

s 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 `double`

s 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** (`«c`

) construction, which must correspond to a _{0}|c_{1}|…|c_{n}»!`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 |