Fibonacci numbers (Hume)

From LiteratePrograms

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₀ = (fib₀, fib₁) = (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

Retrieved from "http://literateprograms.org/Fibonacci_numbers_%28Hume%29"

Categories: Fibonacci numbers | Programming language:Hume | Environment:Linux