aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--entries/gerui/fib.pl15
-rw-r--r--entries/gerui/gfib.ml51
-rw-r--r--people.json17
3 files changed, 82 insertions, 1 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?
+*)
diff --git a/people.json b/people.json
index 155858b..3652818 100644
--- a/people.json
+++ b/people.json
@@ -619,5 +619,20 @@
"link": "./entries/joeyshi12/vimscript/fib.vim"
}
]
- }
+ },
+ {
+ "github": "gerui",
+ "name": "Rui Ge",
+ "title": "PhD Candidate, UBC",
+ "entries": [
+ {
+ "name": "gfib.ml",
+ "link": "./entries/gerui/gfib.ml"
+ },
+ {
+ "name": "fib.pl",
+ "link": "./entries/gerui/fib.pl"
+ }
+ ]
+ }
]