(*
 *  In this example, we compute a staged power function while tracking how many
 *  multiplications the generated code performs.  This example demonstrates the
 *  utility of our environment-passing translation, in two ways.  First, it is
 *  easiest to write this example if we use a side effect such as mutable state
 *  in MetaOCaml, but such an extension (a piece of state of type int) has not
 *  been shown sound except through our translation.  Second, we can write this
 *  example in pure MetaOCaml (more awkwardly) using our translation.
 *
 *  Thanks to Olivier Danvy for suggesting this example.
 *)

let rec powerc = function
    | 0 -> (.<fun x -> 1>.,0)
    | 1 -> (.<fun x -> x>.,1)
    | n -> let (c,n1) = powerc (pred n) in
           (.<fun x -> (.~c x) * x>.,succ n1)
;;
let test = powerc 5;;
let testc = (.! (fst test)) 2;;
let mul x y = .<.<.~.~x * .~.~y>.>.;;
let rec powerd = function
    | 0 -> (.<fun x -> .<1>.>.,0)
    | 1 -> (.<fun x -> x>.,1)
    | n -> let (c,n1) = powerd (pred n) in
           (.<fun x -> .~(mul .<.~c x>. .<x>.)>.,succ n1)

let test1 () = powerd 5;;
let testd = .! (fst (test1 ()));;
let testdd = .<fun x -> .~(testd .<x>.)>.;;


(* An attempt to write testd without overt use of multiple levels:
   no nested brackets.
*)
let one = .<1>.;;
let mul1 x y = .<.~x * .~y>.;;
let mull x y = .<mul1 .~x  .~y>.;;

let rec powerd1 = function
    | 0 -> (.<fun x -> one>.,0)
    | 1 -> (.<fun x -> x>.,1)
    | n -> let (c,n1) = powerd1 (pred n) in
           (.<fun x -> .~(mull .<.~c x>. .<x>.)>.,succ n1)
;;

let test11 () = powerd1 5;;
let testd1 = .! (fst (test11 ()));;
let testdd1 = .<fun x -> .~(testd1 .<x>.)>.;;