(* Little Integer Language Interpreter (lint)

   Author:  Walid Taha
   Date:    Fri Sep 19 13:54:47 CDT 2003

   Problem:    See "A Gentle Introduction to Multi-stage Programming"
*)

(* Basics *)

type exp = Int of int
         | Var of string
         | App of string * exp
         | Add of exp * exp
         | Sub of exp * exp
         | Mul of exp * exp
         | Div of exp * exp
         | Ifz of exp * exp * exp
type def = Declaration of string * string * exp
type prog = Program of def list * exp

exception Yikes
let env0 = fun x -> raise Yikes
let fenv0 = env0
let ext env x v = fun y -> if x=y then v else env y

(* 1 *)

let rec eval e env fenv =
match e with
  Int i -> i
| Var s -> env s
| App (s,e2) -> (fenv s)(eval e2 env fenv)
| Add (e1,e2) -> (eval e1 env fenv)+(eval e2 env fenv)
| Sub (e1,e2) -> (eval e1 env fenv)-(eval e2 env fenv)
| Mul (e1,e2) -> (eval e1 env fenv)*(eval e2 env fenv)
| Div (e1,e2) -> (eval e1 env fenv)/(eval e2 env fenv)
| Ifz (e1,e2,e3) -> if (eval e1 env fenv)=0
                     then (eval e2 env fenv)
                     else (eval e3 env fenv)

let rec peval p env fenv=
    match p with
     Program ([],e) -> eval e env fenv
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        let rec f x = eval e1 (ext env s2 x) (ext fenv s1 f)
        in peval (Program(tl,e)) env (ext fenv s1 f)

(* 2 *)

let rec eval2 e env fenv =
match e with
  Int i -> .<i>.
| Var s -> env s
| App (s,e2) -> .<.~(fenv s).~(eval2 e2 env fenv)>.
| Add (e1,e2) -> .<.~(eval2 e1 env fenv)+ .~(eval2 e2 env fenv)>.
| Sub (e1,e2) -> .<.~(eval2 e1 env fenv)- .~(eval2 e2 env fenv)>.
| Mul (e1,e2) -> .<.~(eval2 e1 env fenv)* .~(eval2 e2 env fenv)>.
| Div (e1,e2) -> .<.~(eval2 e1 env fenv)/ .~(eval2 e2 env fenv)>.
| Ifz (e1,e2,e3) -> .<if .~(eval2 e1 env fenv)=0
                       then .~(eval2 e2 env fenv)
                       else .~(eval2 e3 env fenv)>.

let rec peval2 p env fenv=
    match p with
     Program ([],e) -> eval2 e env fenv
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        .<let rec f x = .~(eval2 e1 (ext env s2 .<x>.) (ext fenv s1 .<f>.))
          in .~(peval2 (Program(tl,e)) env (ext fenv s1 .<f>.))>.

(* 3 *)

let rec eval3 e env fenv =
match e with
  Int i -> Some i
| Var s -> Some (env s)
| App (s,e2) -> (match (eval3 e2 env fenv) with
                   Some x -> (fenv s) x
                 | None   -> None)
| Add (e1,e2) -> (match (eval3 e1 env fenv, eval3 e2 env fenv) with
                   (Some x, Some y) -> Some (x+y)
                  | _ -> None)
| Sub (e1,e2) -> (match (eval3 e1 env fenv, eval3 e2 env fenv) with
                   (Some x, Some y) -> Some (x-y)
                  | _ -> None)
| Mul (e1,e2) -> (match (eval3 e1 env fenv, eval3 e2 env fenv) with
                   (Some x, Some y) -> Some (x*y)
                  | _ -> None)
| Div (e1,e2) -> (match (eval3 e1 env fenv, eval3 e2 env fenv) with
                   (Some x, Some y) -> 
                      if y=0 then None
                             else Some (x/y)
                  | _ -> None)
| Ifz (e1,e2,e3) -> (match (eval3 e1 env fenv) with
                      Some x -> if x=0 then (eval3 e2 env fenv)
                                   else (eval3 e3 env fenv)
                     | None   -> None)

let rec peval3 p env fenv=
    match p with
     Program ([],e) -> eval3 e env fenv
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        let rec f x = eval3 e1 (ext env s2 x) (ext fenv s1 f)
        in peval3 (Program(tl,e)) env (ext fenv s1 f)

(* 4 *)

let rec eval4 e env fenv =
match e with
  Int i -> .<Some i>.
| Var s -> .<Some .~(env s)>.
| App (s,e2) -> .<(match .~(eval4 e2 env fenv) with
                     Some x -> .~(fenv s) x
                   | None   -> None)>.
| Add (e1,e2) -> .<(match (.~(eval4 e1 env fenv), .~(eval4 e2 env fenv)) with
                     (Some x, Some y) -> Some (x+y)
                    | _ -> None)>.
| Sub (e1,e2) -> .<(match (.~(eval4 e1 env fenv), .~(eval4 e2 env fenv)) with
                     (Some x, Some y) -> Some (x-y)
                    | _ -> None)>.
| Mul (e1,e2) -> .<(match (.~(eval4 e1 env fenv), .~(eval4 e2 env fenv)) with
                     (Some x, Some y) -> Some (x*y)
                    | _ -> None)>.
| Div (e1,e2) -> .<(match (.~(eval4 e1 env fenv), .~(eval4 e2 env fenv)) with
                     (Some x, Some y) -> 
                       if y=0 then None        (* This is the "evil if" *)
                              else Some (x/y)
                    | _ -> None)>.
| Ifz (e1,e2,e3) -> .<(match .~(eval4 e1 env fenv) with
                        Some x -> if x=0 then .~(eval4 e2 env fenv)
                                         else .~(eval4 e3 env fenv)
                      | None   -> None)>.

let rec peval4 p env fenv=
    match p with
     Program ([],e) -> eval4 e env fenv
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        .<let rec f x = .~(eval4 e1 (ext env s2 .<x>.) (ext fenv s1 .<f>.))
          in .~(peval4 (Program(tl,e)) env (ext fenv s1 .<f>.))>.

(* 5 *)

let rec eval5 e env fenv k =
match e with
  Int i -> k (Some i)
| Var s -> k (Some (env s))
| App (s,e2) -> eval5 e2 env fenv
                  (fun r -> match r with
                    Some x -> k (Some ((fenv s) x))
                  | None   -> k None)
| Add (e1,e2) -> eval5 e1 env fenv
                   (fun r ->
                     eval5 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some (x+y))
                        | _ -> k None))
| Sub (e1,e2) -> eval5 e1 env fenv
                   (fun r ->
                     eval5 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some (x-y))
                        | _ -> k None))
| Mul (e1,e2) -> eval5 e1 env fenv
                   (fun r ->
                     eval5 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some (x*y))
                        | _ -> k None))
| Div (e1,e2) -> eval5 e1 env fenv
                   (fun r ->
                     eval5 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> 
                           if y=0 then k None
                                    else k (Some (x/y))
                        | _ -> k None))
| Ifz (e1,e2,e3) -> eval5 e1 env fenv
                      (fun r -> match r with
                        Some x -> if x=0 then eval5 e2 env fenv k
                                         else eval5 e3 env fenv k
                       | None   -> k None)

let rec pevalK5 p env fenv k =
    match p with
     Program ([],e) -> eval5 e env fenv k
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        let rec f x = eval5 e1 (ext env s2 x) (ext fenv s1 f) k
          in pevalK5 (Program(tl,e)) env (ext fenv s1 f) k

exception Div_by_zero;;

let peval5 p env fenv =
     pevalK5 p env fenv (function Some x -> x | None -> raise Div_by_zero)

(* 6 *)

let rec eval6 e env fenv k =
match e with
  Int i -> k (Some .<i>.)
| Var s -> k (Some (env s))
| App (s,e2) -> eval6 e2 env fenv
                  (fun r -> match r with
                    Some x -> k (Some .<.~(fenv s) .~x>.)
                  | None   -> k None)
| Add (e1,e2) -> eval6 e1 env fenv
                   (fun r ->
                     eval6 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some .<.~x + .~y>.)
                        | _ -> k None))
| Sub (e1,e2) -> eval6 e1 env fenv
                   (fun r ->
                     eval6 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some .<.~x - .~y>.)
                        | _ -> k None))
| Mul (e1,e2) -> eval6 e1 env fenv
                   (fun r ->
                     eval6 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some .<.~x * .~y>.)
                        | _ -> k None))
| Div (e1,e2) -> eval6 e1 env fenv
                   (fun r ->
                     eval6 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> 
                           .<if .~y=0 then .~(k None)
                                    else .~(k (Some .<.~x / .~y>.))>.
                        | _ -> k None))
| Ifz (e1,e2,e3) -> eval6 e1 env fenv
                      (fun r -> match r with
                        Some x -> .<if .~x=0 then .~(eval6 e2 env fenv k)
                                             else .~(eval6 e3 env fenv k)>.
                       | None   -> k None)

let rec pevalK6 p env fenv k =
    match p with
     Program ([],e) -> eval6 e env fenv k
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        .<let rec f x = .~(eval6 e1 (ext env s2 .<x>.) (ext fenv s1 .<f>.) k) 
          in .~(pevalK6 (Program(tl,e)) env (ext fenv s1 .<f>.) k)>.

exception Div_by_zero;;

let peval6 p env fenv =
     pevalK6 p env fenv (function Some x -> x | None -> .<raise Div_by_zero>.)

(* 7 *)

let rec eval7 e env fenv =
match e with
  Int i -> .<i>.
| Var s -> env s
| App (s,e2) -> .<.~(fenv s (eval7 e2 env fenv))>.
| Add (e1,e2) -> .<.~(eval7 e1 env fenv)+ .~(eval7 e2 env fenv)>.
| Sub (e1,e2) -> .<.~(eval7 e1 env fenv)- .~(eval7 e2 env fenv)>.
| Mul (e1,e2) -> .<.~(eval7 e1 env fenv)* .~(eval7 e2 env fenv)>.
| Div (e1,e2) -> .<.~(eval7 e1 env fenv)/ .~(eval7 e2 env fenv)>.
| Ifz (e1,e2,e3) -> .<if .~(eval7 e1 env fenv)=0
                       then .~(eval7 e2 env fenv)
                       else .~(eval7 e3 env fenv)>.
let rec repeat n f = 
  if n=0 then f else fun x -> f (repeat (n-1) f x)

let rec peval7 p env fenv=
    match p with
     Program ([],e) -> eval7 e env fenv
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        .<let rec f x = 
            .~(let body cf x = eval7 e1 (ext env s2 x) (ext fenv s1 cf) in
               repeat 1 body (fun y -> .<f .~y>.) .<x>.)
          in .~(peval7 (Program(tl,e)) env (ext fenv s1 (fun y -> .<f .~y>.)))>.



(* 8 *)

let rec eval8 e env fenv =
match e with
  Int i -> .<i>.
| Var s -> env s
| App (s,e2) -> .<let x= .~(eval8 e2 env fenv) in .~(fenv s .<x>.)>.
| Add (e1,e2) -> .<.~(eval8 e1 env fenv)+ .~(eval8 e2 env fenv)>.
| Sub (e1,e2) -> .<.~(eval8 e1 env fenv)- .~(eval8 e2 env fenv)>.
| Mul (e1,e2) -> .<.~(eval8 e1 env fenv)* .~(eval8 e2 env fenv)>.
| Div (e1,e2) -> .<.~(eval8 e1 env fenv)/ .~(eval8 e2 env fenv)>.
| Ifz (e1,e2,e3) -> .<if .~(eval8 e1 env fenv)=0
                       then .~(eval8 e2 env fenv)
                       else .~(eval8 e3 env fenv)>.

let rec repeat n f = 
  if n=0 then f else fun x -> f (repeat (n-1) f x)

let rec peval8 p env fenv=
    match p with
     Program ([],e) -> eval8 e env fenv
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        .<let rec f x = 
            .~(let body cf x = eval8 e1 (ext env s2 x) (ext fenv s1 cf) in
               repeat 1 body (fun y -> .<f .~y>.) .<x>.)
          in .~(peval8 (Program(tl,e)) env (ext fenv s1 (fun y -> .<f .~y>.)))>.



(* 9 *)

let rec eval9 e env fenv k =
match e with
  Int i -> k (Some .<i>.)
| Var s -> k (Some (env s))
| App (s,e2) -> eval9 e2 env fenv
                  (fun r -> match r with
                    Some x -> k (Some ((fenv s) x))
                  | None   -> k None)
| Add (e1,e2) -> eval9 e1 env fenv
                   (fun r ->
                     eval9 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some .<.~x + .~y>.)
                        | _ -> k None))
| Sub (e1,e2) -> eval9 e1 env fenv
                   (fun r ->
                     eval9 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some .<.~x - .~y>.)
                        | _ -> k None))
| Mul (e1,e2) -> eval9 e1 env fenv
                   (fun r ->
                     eval9 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> k (Some .<.~x * .~y>.)
                        | _ -> k None))
| Div (e1,e2) -> eval9 e1 env fenv
                   (fun r ->
                     eval9 e2 env fenv
                       (fun s -> match (r,s) with
                         (Some x, Some y) -> 
                           .<if .~y=0 then .~(k None)
                                    else .~(k (Some .<.~x / .~y>.))>.
                        | _ -> k None))
| Ifz (e1,e2,e3) -> eval9 e1 env fenv
                      (fun r -> match r with
                        Some x -> .<if .~x=0 then .~(eval9 e2 env fenv k)
                                             else .~(eval9 e3 env fenv k)>.
                       | None   -> k None)

let rec pevalK9 p env fenv k =
    match p with
     Program ([],e) -> eval9 e env fenv k
    |Program (Declaration (s1,s2,e1)::tl,e) ->
        .<let rec f x = 
            .~(let body cf x = eval9 e1 (ext env s2 x) (ext fenv s1 cf) k in
               repeat 1 body (fun y -> .<f .~y>.) .<x>.)
          in .~(pevalK9 (Program(tl,e)) env (ext fenv s1 (fun y -> .<f .~y>.)) k)>.

exception Div_by_zero;;

let peval9 p env fenv =
     pevalK9 p env fenv (function Some x -> x | None -> .<raise Div_by_zero>.)

(**********************************************************************************)

(* Examples *)

(* let rec f x = if x=0 then 1 else x*(f(x-1)) in f 10 *)

let termFact = Program 
      ([Declaration 
         ("f","x",
           Ifz(Var "x", Int 1, Mul(Var"x",(App ("f", Sub(Var "x",Int 1))))))], 
       App ("f", Int 10))

(* let rec f x = if x=0 then 0 else
             if (x-1)=0 then 1 else
             (f (x-1)) + (f (x-2))
   in f 20
*)

let termFib = Program
      ([Declaration 
         ("f","x",
           Ifz(Var "x", Int 0, 
           Ifz(Sub(Var "x",Int 1), Int 1,
            Add(App ("f", Sub(Var "x",Int 1)),
                App ("f", Sub(Var "x",Int 2))))))], 
       App ("f", Int 20))

(* let rec f x = if x=0 then 1 else x*(f(x-1)) in f (10/2) *)

let termFat = Program 
      ([Declaration 
         ("f","x",
           Ifz(Var "x", Int 1, Mul(Var"x",(App ("f", Sub(Var "x",Int 1))))))], 
       App ("f", Div (Int 10,Int 2)))

(*

(* Timings (The Old Way) *)

let _ = Trx.init_times ()

(* First set *)

let baseline =
  Trx.time 100000 " Baseline  " (fun () -> ())

let unstaged =
  Trx.time 10000 "Unstaged (#1)" (fun () -> peval termFact env0 fenv0)

let native =
  Trx.time 100000 "In OCaml" 
   (fun () -> let rec f x = if x=0 then 1 else x*(f(x-1)) in f 10)

let stage1 =
  Trx.time 10000 "Stage 1 (#2)" (fun () -> peval2 termFact env0 fenv0)

let compiled =
  Trx.time 100   "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 100000 "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.time 10000 "Unstaged (#3)" (fun () -> peval3 termFact env0 fenv0)

let stage1 =
  Trx.time 10000 "Stage 1 (#4)" (fun () -> peval4 termFact env0 fenv0)

let compiled =
  Trx.time 100   "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 100000 "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.time 10000 "Unstaged (#5)" (fun () -> peval5 termFact env0 fenv0)

let stage1 =
  Trx.time 10000 "Stage 1 (#6)" (fun () -> peval6 termFact env0 fenv0)

let compiled =
  Trx.time 100    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 100000 "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.time 10000 "Stage 1 (#7)" (fun () -> peval7 termFact env0 fenv0)

let compiled =
  Trx.time 100    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 100000 "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.time 10000 "Stage 1 (#8)" (fun () -> peval8 termFact env0 fenv0)

let compiled =
  Trx.time 100    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 100000 "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.time 10000 "Stage 1 (#9)" (fun () -> peval9 termFact env0 fenv0)

let compiled =
  Trx.time 100    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 100000 "Stage 2" (fun () -> compiled ())

(* Second set *)

let baseline =
  Trx.time 100000 " Baseline  " (fun () -> ())

let unstaged =
  Trx.time 50 "Unstaged (#1)" (fun () -> peval termFib env0 fenv0)

let native =
  Trx.time 500 "In OCaml" 
   (fun () ->  let rec f x = 
                if x=0 then 0 else
                if (x-1)=0 then 1 else 
                 (f (x-1)) + (f (x-2))
               in f 20)

let stage1 =
  Trx.time 10000 "Stage 1 (#2)" (fun () -> peval2 termFib env0 fenv0)

let compiled =
  Trx.time 100   "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 500 "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.time 10 "Unstaged (#3)" (fun () -> peval3 termFib env0 fenv0)

let stage1 =
  Trx.time 10000 "Stage 1 (#4)" (fun () -> peval4 termFib env0 fenv0)

let compiled =
  Trx.time 100   "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 10 "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.time 10 "Unstaged (#5)" (fun () -> peval5 termFib env0 fenv0)

let stage1 =
  Trx.time 10000 "Stage 1 (#6)" (fun () -> peval6 termFib env0 fenv0)

let compiled =
  Trx.time 50    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 500 "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.time 10000 "Stage 1 (#7)" (fun () -> peval7 termFib env0 fenv0)

let compiled =
  Trx.time 50    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 500 "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.time 10000 "Stage 1 (#8)" (fun () -> peval8 termFib env0 fenv0)

let compiled =
  Trx.time 50    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 500 "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.time 10000 "Stage 1 (#9)" (fun () -> peval9 termFib env0 fenv0)

let compiled =
  Trx.time 50    "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.time 500 "Stage 2" (fun () -> compiled ())

let _ = Trx.print_times ()


*)

(* Timings (The New Way) *)

let _ = Trx.init_times ()

(* First set *)

let baseline =
  Trx.timenew " Baseline  " (fun () -> ())

let unstaged =
  Trx.timenew "Unstaged (#1)" (fun () -> peval termFact env0 fenv0)

let native =
  Trx.timenew "In OCaml" 
   (fun () -> let rec f x = if x=0 then 1 else x*(f(x-1)) in f 10)

let stage1 =
  Trx.timenew "Stage 1 (#2)" (fun () -> peval2 termFact env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.timenew "Unstaged (#3)" (fun () -> peval3 termFact env0 fenv0)

let stage1 =
  Trx.timenew "Stage 1 (#4)" (fun () -> peval4 termFact env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.timenew "Unstaged (#5)" (fun () -> peval5 termFact env0 fenv0)

let stage1 =
  Trx.timenew "Stage 1 (#6)" (fun () -> peval6 termFact env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.timenew "Stage 1 (#7)" (fun () -> peval7 termFact env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.timenew "Stage 1 (#8)" (fun () -> peval8 termFact env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.timenew "Stage 1 (#9)" (fun () -> peval9 termFact env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

(* Second set *)

let baseline =
  Trx.timenew " Baseline  " (fun () -> ())

let unstaged =
  Trx.timenew "Unstaged (#1)" (fun () -> peval termFib env0 fenv0)

let native =
  Trx.timenew "In OCaml" 
   (fun () ->  let rec f x = 
                if x=0 then 0 else
                if (x-1)=0 then 1 else 
                 (f (x-1)) + (f (x-2))
               in f 20)

let stage1 =
  Trx.timenew "Stage 1 (#2)" (fun () -> peval2 termFib env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.timenew "Unstaged (#3)" (fun () -> peval3 termFib env0 fenv0)

let stage1 =
  Trx.timenew "Stage 1 (#4)" (fun () -> peval4 termFib env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let unstaged =
  Trx.timenew "Unstaged (#5)" (fun () -> peval5 termFib env0 fenv0)

let stage1 =
  Trx.timenew "Stage 1 (#6)" (fun () -> peval6 termFib env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.timenew "Stage 1 (#7)" (fun () -> peval7 termFib env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.timenew "Stage 1 (#8)" (fun () -> peval8 termFib env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let stage1 =
  Trx.timenew "Stage 1 (#9)" (fun () -> peval9 termFib env0 fenv0)

let compiled =
  Trx.timenew "Compilation" (fun () -> .! .<fun () -> .~stage1>.)

let stage2 =
  Trx.timenew "Stage 2" (fun () -> compiled ())

let _ = Trx.print_times ();;