# Fibonacci numbers (Hume)

### From LiteratePrograms

**Other implementations**: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell |**Hume**| Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by

- 1 \\ \end{cases} ."/>

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.

Let's use the regular recursive model, which execution costs grows exponentially, to experiment with the language capabilities of bounding algorithms in Time, Heap and Stack costs.

As the compiler and the interpreter implement slightly different subsets of the language, separate code block versions are provided when needed.

## Declarations

<<I/O bindings and typedefs>>=stream output to "std_out"; type integer = int 32 ; exception EUnbelievable :: (integer, string) ; exception EIllegalArg :: string ;

## The fibonacci function

<<recursive fibonacci>>=fibo :: integer -> integer ; fibo 0 = 0; fibo 1 = 1; fibo n = if n < 0 then raise EIllegalArg "fibo negative argument: " ++ (n as string) else fibo(n-1) + fibo (n-2);

## Tail recursive fibonacci

Given that the series of pairs of consecutive fibo values can be expressed in the following way

S_{0} = (fib_{0}, fib_{1}) = (0, 1) ;

for n >= 1, succ (fib_{n-1}, fib_{n}) = (fib_{n}, fib_{n+1}) = (fib_{n}, fib_{n-1} + fib_{n}) ;

Naming (fib_{n-1}, fib_{n}) as (result, next) then succ (result, next) = (next, (result+next))

fib_{n} = first item in (a, b)_{n}

<<tail recursive fibonacci>>=fibo2_tr :: integer -> integer -> integer -> integer ; fibo2_tr 0 result next = result ; -- last recursion, take first item fibo2_tr iter result next = fibo2_tr (iter-1) next (result+next); fibo2 :: integer -> integer ; fibo2 n = if n < 0 then raise EIllegalArg "fibo2 negative argument: " ++ (n as string) else fibo2_tr n 0 1;

## Bounding fibonacci in Time

Let's bound fibo costs.

Only time bounding is admitted in an <expr>. Heap and Stack space bounding is admitted in the context of a within-constraint on boxes (compiler only) (Hume Report 2.1.4).

<<bounded regular recursive fibonacci>>=-- bounded regular recursive fibo bfibo :: integer -> integer ; bfibo n = (fibo n) within 10ms ; -- Constraint to 10 miliseconds, raises Timeout

<<bounded tail recursive fibonacci>>=-- bounded tail recursive fibo bfibo2 :: integer -> integer ; bfibo2 n = (fibo2 n) within 10ms ; -- Constraint to 10 miliseconds, raises Timeout

## The automaton (interpreter version)

Main program loop.

<<automaton box for the interpreter>>=box fib in (n::integer) out (nextn::integer, result::(integer, integer, string)) handles Timeout, EUnbelievable, EIllegalArg match n -> if n >= 99 then raise EUnbelievable (n, "reached") else (n+1, (n, bfibo2 n, "\n")) handle Timeout e -> ( 0, (*, *, "Caught timeout, resetting n to 0\n")) -- set nextn to 0, * means ignored output | EUnbelievable (n, msg) -> (0, (*, *, "Unbelievable: " ++ (n as string) ++ msg ++ ", resetting n to 0\n")) | EIllegalArg msg -> (0, (*, *, "IllegalArg: " ++ msg ++ "\n")) ;

## Wiring the automaton

Wiring thread level box I/O

<<wirings>>=wire fib (fib.nextn initially 0) --inputs (get fib.n from fib.nextn) (fib.n, output) ; --outputs (put fib.nextn to fib.n, result to output)

## The whole program (interpreter version)

<<fibo-i.hume>>=I/O bindings and typedefs tail recursive fibonacci bounded tail recursive fibonacci automaton box for the interpreter wirings

## Testing with the interpreter

./hume fibo-i.hume

Produces the output

0 0 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 Caught timeout, resetting n to 0 0 0 1 1 2 1 3 2 4 3 ...

## The automaton, heap and stack bounded (compiler only)

Main program loop. Heap and Stack are discarded after each cycle making garbage collection unneeded. Because of this HeapOverflow or StackOverflow exceptions do not end execution.

It must be compiled without the switch "-lotsaspace" which overrides the Heap and Stack constraint. If no Heap and Stack constraint is set, then "-lotsaspace" is needed since they seem to default to 0, expecting an explicit setting.

<<automaton box for the compiler>>=box fib in (n::integer) out (nextn::integer, result::(integer, integer, string)) handles Timeout, HeapOverflow, StackOverflow, EUnbelievable, EIllegalArg within 400B (200B) -- heap_space ( stack_space) cost bounding match n -> if n >= 99 then raise EUnbelievable (n, "reached") else (n+1, (n, bfibo n, "\n")) handle Timeout e -> ( 0, (*, *, "Caught timeout, resetting n to 0\n")) -- set nextn to 0, * means ignored output | HeapOverflow e -> ( 0, (*, *, "Caught HeapOverflow, resetting n to 0\n")) | StackOverflow e -> ( 0, (*, *, "Caught StackOverflow, resetting n to 0\n")) | EUnbelievable (n, msg) -> (0, (n, *, "Unbelievable value reached, resetting n to 0\n")) -- string concat. not admitted here by compiler | EIllegalArg msg -> (0, (*, *, msg)) ;

## The whole program (compiler version)

<<fibo-c.hume>>=I/O bindings and typedefs recursive fibonacci bounded regular recursive fibonacci automaton box for the compiler wirings

## Testing with the compiler

Lets compile and try. Compile from the compiler folder Add first the . directory to the PATH.

Note. There is an error about output that I can't manage. Exceptions don't show the expected output, they only print the exception name. Heap and Stack constraints generate or not the corresponding exceptions adjusting values, but I could not adjust the time constraint of *bfibo* to show its exception.

humec fibo-c.hume ./fibo-c

which produces the output

0 0 1 1 2 1 3 2 4 3 5 5 Stack overflow 0 0 1 1 2 1 3 2 ...

Download code |