Fibonacci numbers (Hume)
- 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.
<<I/O bindings and typedefs>>=
stream output to "std_out";
type integer = int 32 ;
exception EUnbelievable :: (integer, string) ;
exception EIllegalArg :: string ;
<<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);
Given that the series of pairs of consecutive fibo values can be expressed in the following way
S0 = (fib0, fib1) = (0, 1) ;
for n >= 1, succ (fibn-1, fibn) = (fibn, fibn+1) = (fibn, fibn-1 + fibn) ;
Naming (fibn-1, fibn) as (result, next) then succ (result, next) = (next, (result+next))
fibn = 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;
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
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 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)
<<fibo-i.hume>>= I/O bindings and typedefs tail recursive fibonacci bounded tail recursive fibonacci automaton box for the interpreter wirings
./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 ...
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))
;
<<fibo-c.hume>>= I/O bindings and typedefs recursive fibonacci bounded regular recursive fibonacci automaton box for the compiler wirings
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 |