diff options
-rw-r--r-- | entries/gerui/fib.pl | 15 | ||||
-rw-r--r-- | entries/gerui/gfib.ml | 51 | ||||
-rw-r--r-- | people.json | 17 |
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" + } + ] + } ] |