serious stuff
www.cubbi.com
personal
programming
fibonacci numbers
algorithms
benchmarks
forth examples
postscript examples
muf examples
joy examples
j examples
scheme examples
hope examples
ocaml examples
haskell examples
prolog examples
c++ examples
java examples
assembly language examples
fortran examples
c examples
sh examples
awk examples
perl examples
tcl examples
asmix
hacker test
resume
science
martial arts
fun stuff
www.cubbi.org
|
Hope
Date: 1978
Type: Pure functional programming language
Usage: academic
(this language got me into functional programming)
ALGORITHM 1A: NAIVE BINARY RECURSION |
uses lists;
dec frec : num -> num;
--- frec 0 <= 0;
--- frec 1 <= 1;
--- frec(n+2) <= frec n + frec(n+1);
dec f : num -> num;
--- f n <= (if n<0 and n mod 2=0 then \(n)=>0-n else id) (frec (abs n));
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", num2str(f n)];
write (output argv)
where output ==
\(n) => if 1 = length n then [ main number ]
else [ "Usage: f1a.hop <n>" ]
where number == str2num (argv @ 0);
|
ALGORITHM 1B: CACHED BINARY RECURSION |
uses lists;
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
where sum == x+y;
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
where (y::ys) == reverse x
where pn2s ==
\(n) => pad ('0', length (num2str (B-1)), num2str n);
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;
dec mfib : num -> list bignum -> bignum # list bignum;
--- mfib n l <= if length l > n then (l@n, l)
else (sum, l2<>[sum])
where sum == bigadd(p1, p2)
where (p1,l2) == mfib (n-1) l1
where (p2,l1) == mfib (n-2) l;
dec fib : num -> bignum;
--- fib n <= a where (a,_) == mfib n l
where l == [fromnum 0, fromnum 1];
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
write (output argv)
where output ==
\(n) => if 1 = length n then [ main number ]
else [ "Usage: f1a.hop <n>" ]
where number == str2num (argv @ 0);
|
ALGORITHM 2A: CACHED LINEAR RECURSION / INFINITE LAZY EVALUATED LIST |
uses lists;
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
where sum == x+y;
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
where (y::ys) == reverse x
where pn2s ==
\(n) => pad ('0', length (num2str (B-1)), num2str n);
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;
dec fibs : list bignum;
--- fibs <= fs whererec fs == fromnum 0::fromnum 1::map bigadd (fs||tail fs);
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fibs@(abs n));
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
write (output argv)
where output ==
\(n) => if 1 = length n then [ main number ]
else [ "Usage: f2a.hop <n>" ]
where number == str2num (argv @ 0);
|
ALGORITHM 2B: LINEAR RECURSION WITH ACCUMULATOR |
uses lists;
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
where sum == x+y;
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
where (y::ys) == reverse x
where pn2s ==
\(n) => pad ('0', length (num2str (B-1)), num2str n);
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;
dec fib : num -> bignum;
--- fib n <= l (fromnum 1, fromnum 0, n)
whererec l == \(a,b,succ c) => if c<1 then a else l(bigadd(a,b),a,c)
|(a,b,0) => fromnum 0;
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
write (output argv)
where output ==
\(n) => if 1 = length n then [ main number ]
else [ "Usage: f2b.hop <n>" ]
where number == str2num (argv @ 0);
|
ALGORITHM 2C: NON-RECURSIVE LOOP |
Hope does not support non-recursive loops.
Rewriting this algorithm using recursion gives ALGORITHM 2B.
|
ALGORITHM 3A: MATRIX MULTIPLICATION |
uses lists;
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
where sum == x+y;
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
where (y::ys) == reverse x
where pn2s == ! padded num2str
\(n) => pad ('0', length (num2str (B-1)), num2str n);
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;
dec halve : bignum -> bignum;
--- halve n <= reverse (l(reverse n,false))
whererec l == \((x1::(x2::xs)),c) => (if h>0 or c then [h] else [])
<> l((x2+x1 mod 2*B)::xs,true)
where h == x1 div 2
|([],_) => []
|([x],_) => [x div 2];
dec bigeven : bignum -> bool;
--- bigeven [] <= true;
--- bigeven (x::xs) <= x mod 2=0;
dec bigmul : bignum # bignum -> bignum;
--- bigmul (b,n) <= l(fromnum 0,b,n)
whererec l == \(u,b,[]) => u
|(u,b,[0]) => u
|(u,b,n) => if bigeven n then l(u,bigadd(b,b),halve n)
else l(bigadd(u,b),bigadd(b,b),halve n);
dec transpose : list (list alpha) -> list (list alpha);
--- transpose ([]::_) <= [];
--- transpose n <= map head n :: transpose (map tail n);
dec dot : list bignum -> list bignum -> bignum;
--- dot a b <= foldr (fromnum 0, bigadd) (map bigmul (a||b));
dec mm : list (list bignum) # list (list bignum) -> list (list bignum);
--- mm (a,b) <= map (\(row) => map (\(col) => dot row col) tb) a
where tb == transpose b;
dec power : (alpha # alpha -> alpha) -> alpha -> alpha -> num -> alpha;
--- power f u b 0 <= u;
--- power f u b n <= if n mod 2=0 then power f u (f(b,b)) (n div 2)
else power f (f(u,b)) (f(b,b)) (n div 2);
dec fib : num -> bignum;
--- fib 0 <= fromnum 0;
--- fib (n+1) <= let [[a,_],_] == power mm u t n
where t,u == ([[fromnum 1,fromnum 1],[fromnum 1,fromnum 0]],
[[fromnum 1,fromnum 0],[fromnum 0,fromnum 1]])
in a;
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
write (output argv)
where output ==
\(n) => if 1 = length n then [ main number ]
else [ "Usage: f3a.hop <n>" ]
where number == str2num (argv @ 0);
|
ALGORITHM 3B: FAST RECURSION |
uses lists;
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
where sum == x+y;
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
where (y::ys) == reverse x
where pn2s == ! padded num2str
\(n) => pad ('0', length (num2str (B-1)), num2str n);
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;
dec halve : bignum -> bignum;
--- halve n <= reverse (l(reverse n,false))
whererec l == \((x1::(x2::xs)),c) => (if h>0 or c then [h] else [])
<> l((x2+x1 mod 2*B)::xs,true)
where h == x1 div 2
|([],_) => []
|([x],_) => [x div 2];
dec bigeven : bignum -> bool;
--- bigeven [] <= true;
--- bigeven (x::xs) <= x mod 2=0;
dec bigmul : bignum # bignum -> bignum;
--- bigmul (b,n) <= l(fromnum 0,b,n)
whererec l == \(u,b,[]) => u
|(u,b,[0]) => u
|(u,b,n) => if bigeven n then l(u,bigadd(b,b),halve n)
else l(bigadd(u,b),bigadd(b,b),halve n);
dec fib : num -> bignum;
--- fib n <= a where (a,b) == l(n)
whererec l == \(n) =>
if n<1 then (fromnum 0,fromnum 0) else
if n=1 then (fromnum 1,fromnum 0) else
if n mod 2 = 0 then
(bigmul(k2,bigadd(k1,k3)), bigadd(k1s,k2s))
else
(bigadd(k3s,k2s), bigmul(k2,bigadd(k1,k3)))
where k3 == bigadd(k2,k1)
where k2s == bigmul(k2,k2)
where k1s == bigmul(k1,k1)
where k3s == bigmul(bigadd(k2,k1),bigadd(k2,k1))
where (k2,k1) == l(n div 2);
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
write (output argv)
where output ==
\(n) => if 1 = length n then [ main number ]
else [ "Usage: f3b.hop <n>" ]
where number == str2num (argv @ 0);
|
ALGORITHM 3C: BINET'S FORMULA WITH ROUNDING |
uses lists;
dec fib : num -> num;
--- fib n <= floor (0.5 + pow(phi,n)/sqrt(5) )
where phi == (1+sqrt(5))/2;
dec f : num -> num;
--- f n <= (if n<0 and n mod 2=0 then \(n)=>0-n else id) (fib (abs n));
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", num2str(f n)];
write (output argv)
where output ==
\(n) => if 1 = length n then [ main number ]
else [ "Usage: f3c.hop <n>" ]
where number == str2num (argv @ 0);
|
|