blob: 17574980d2549ecb2a4b51a015cf3ed517538dbb (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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?
*)
|
