Merge pull request #76 from gerui/main

Add Rui Ge

2 files changed, 66 insertions, 0 deletions

diff --git a/entries/gerui/fib.pl b/entries/gerui/fib.pl
new file mode 100644
index 0000000..0065246
--- /dev/null
+++ b/entries/gerui/fib.pl
@@ -0,0 +1,15 @@
+% To my surprise, there has been no Prolog implementation submitted so far. 
+% To get the ball rolling, and to pay respect to Prolog, here is a well-known Prolog implementation of the Fibonacci sequence.
+
+% fib(N, S): S is the Nth Fibonacci number. 
+
+:- table fib/2. 
+
+fib(0, 1) :- !. 
+fib(1, 1) :- !. 
+fib(N, S) :- N > 1, 
+             N1 is N-1, 
+             N2 is N-2, 
+             fib(N1, S1), 
+             fib(N2, S2), 
+             S is S1+S2.
diff --git a/entries/gerui/gfib.ml b/entries/gerui/gfib.ml
new file mode 100644
index 0000000..1757498
--- /dev/null
+++ b/entries/gerui/gfib.ml
@@ -0,0 +1,51 @@
+(*
+This is an MetaOCaml implementation of a Generalised Fibonacci Function (gfib n a b) 
+where gfib is the function's name, n is a non-negative integer, and a and b are integers. 
+
+    gfib n a b = a                                        when n = 0
+    gfib n a b = b                                        when n = 1
+    gfib n a b = (gfib (n - 1) a b) + (gfib (n - 2) a b)  when n > 1
+*)
+
+(* Unstaged program, for reference *)
+let rec gfib_unstaged n a b = if n = 0 then a else gfib_unstaged (n - 1) b (a + b)
+
+(*
+Assume n is known a priori, and a and b are provided at runtime. Stage the above program accordingly.  
+*)
+
+(* Staged programs *)
+let rec gfib n a b = if n = 0 then a else gfib (n - 1) b (.<.~a + .~b>.)
+let rec gfib_main n = .<fun a b -> .~(gfib n .<a>. .<b>.)>.
+
+(*
+Assume n is known to be 10 a priori. Specialise the staged programs. 
+*)
+let gfib_10 = gfib_main 10 
+
+(*
+Try gfib_10 on a few instances of a and b at runtime. 
+   #  open Runcode;;
+   #  run gfib_10 1 1;;
+   #  run gfib_10 12 23;; 
+   #  run gfib_10 ~-1 ~-2;;
+*)
+
+
+(*
+README
+1. Generalised Fibonacci Function is one of the most well-known example in the community of multi-stage programming. 
+2. This example has been tested on BER MetaOCaml. If you are unfamiliar to MetaOCaml, follow these steps: 
+   (1) Install BER MetaOCaml
+   (2) In your Terminal, go the directory of this file and run:
+       %  metaocaml
+       #  #use "gfib.ml";;
+   (3) Try gfib_10 on a few instances of a and b at runtime:  
+       #  open Runcode;;
+       #  run gfib_10 1 1;;
+       #  run gfib_10 12 23;; 
+       #  run gfib_10 ~-1 ~-2;;
+   (4) Exit:
+       #  exit 0;; 
+3. Can you rewrite the programs (both unstaged and staged) for better runtime performance? 
+*)