(* Section 2.1 *)

(* Exercise 1 *)

5 * (2 * 3 + 3 * 4) ;;
(if 2 = 3 then "hello" else "hi") ^ " world" ;;
fst (let x = 1 + 2 in (x, x)) ;;
string_length ("x" ^ string_of_int (3 + 1)) ;;

(* Section 2.2 *)

reset (fun () -> 3 + 5 * 2) - 1 ;;

(* Exercise 2 *)

5 * reset (fun () -> 2 * 3 + 3 * 4) ;;
reset (fun () -> if 2 = 3 then "hello" else "hi") ^ " world" ;;
fst (reset (fun () -> let x = 1 + 2 in (x, x))) ;;
string_length (reset (fun () -> "x" ^ string_of_int (3 + 1))) ;;

(* Section 2.5 *)

reset (fun () -> 3 + shift (fun _ -> 5 * 2) - 1) ;;
reset (fun () -> 3 + shift (fun _ -> "hello") - 1) ;;
reset (fun () -> 3 + shift (fun _ -> 5 * 2)) - 1 ;;
(* reset (fun () -> 3 + shift (fun _ -> "hello")) - 1 ;; *)

(* Exercise 3 *)

(*
5 * reset (fun () -> [.] + 3 * 4) ;;
reset (fun () -> if [.] then "hello" else "hi") ^ " world" ;;
fst (reset (fun () -> let x = [.] in (x, x))) ;;
string_length (reset (fun () -> "x" ^ string_of_int [.])) ;;
*)

(* Exercise 4 *)

let rec times lst = match lst with
    [] -> 1
(*| 0 :: rest -> ... *)
  | first :: rest -> first * times rest ;;

(* Section 2.6 *)

let f x = reset (fun () -> 3 + shift (fun k -> k) - 1) x ;;
let f = reset (fun () -> 3 + shift (fun k -> k) - 1) ;;

(* Exercise 5 *)

(*
reset (fun () -> 5 * ([.] + 3 * 4)) ;;
reset (fun () -> (if [.] then "hello" else "hi") ^ " world") ;;
reset (fun () -> fst (let x = [.] in (x, x))) ;;
reset (fun () -> string_length ("x" ^ string_of_int [.])) ;;
*)

(* Exercise 6 *)

let rec id lst = match lst with
    [] -> []
  | first :: rest -> first :: id rest ;;

reset (fun () -> id [1; 2; 3]) ;;

(* Section 2.7 *)

type tree_t = Empty
            | Node of tree_t * int * tree_t ;;

let tree1 = Node (Node (Empty, 1, Empty), 2, Node (Empty, 3, Empty)) ;;
let tree2 = Node (Empty, 1, Node (Empty, 2, Node (Empty, 3, Empty))) ;;

(* walk : tree_t -> unit *)
let rec walk tree = match tree with
    Empty -> ()
  | Node (t1, n, t2) ->
      walk t1;
      print_int n;
      walk t2 ;;

type 'a result_t = Done
                 | Next of int * (unit / 'a -> 'a result_t / 'a) ;;

(* yield : int => unit *)
let yield n = shift (fun k -> Next (n, k)) ;;

(* walk : tree_t => unit *)
let rec walk tree = match tree with
    Empty -> ()
  | Node (t1, n, t2) ->
      walk t1;
      yield n;
      walk t2 ;;

(* start : tree_t -> 'a result_t *)
let start tree =
  reset (fun () -> walk tree; Done) ;;

(* print_nodes : tree_t -> unit *)
let print_nodes tree =
  let rec loop r = match r with
      Done -> ()        (* no more nodes *)
    | Next (n, k) ->
        print_int n;    (* print n *)
        loop (k ()) in  (* and continue *)
  loop (start tree) ;;

(* Exercise 7 *)

(* 
let same_fringe t1 t2 = ...
*)

(* Section 2.8 *)

let f x = reset (fun () ->
            shift (fun k -> fun () -> k "hello") ^ " world") x ;;

(* Exercise 8 *)

(*
reset (fun () -> "hello " ^ [...] ^ "!") "world" ;;
*)

(* Section 2.10 *)

let get () =
  shift (fun k -> fun state -> k state state) ;;

let tick () =
  shift (fun k -> fun state -> k () (state + 1)) ;;

let run_state thunk =
  reset (fun () -> let result = thunk () in
                   fun state -> result) 0 ;;

run_state (fun () ->
  tick ();            (* state = 1 *)
  tick ();            (* state = 2 *)
  let a = get () in
  tick ();            (* state = 3 *)
  get () - a) ;;

(* Exercise 9 *)

run_state (fun () ->
  (tick (); get ()) - (tick (); get ())) ;;

(* Exercise 10 *)

(*
let put new_state = ...
*)

(* Section 2.11 *)

reset (fun () -> 1 + (shift (fun k -> 2 * k 3))) ;;

type term_t = Var of string
            | Lam of string * term_t
            | App of term_t * term_t ;;

(* id_term : term_t -> term_t *)
let rec id_term term = match term with
    Var (x) -> Var (x)
  | Lam (x, t) -> Lam (x, id_term t)
  | App (t1, t2) -> App (id_term t1, id_term t2) ;;

let counter = ref 0;;

(* gensym : unit -> string *)
let gensym () =
  counter := !counter + 1;
  "t" ^ string_of_int !counter ;;

(* id_term' : term_t -> term_t *)
let rec id_term' term = match term with
    Var (x) -> Var (x)
  | Lam (x, t) -> Lam (x, id_term' t)
  | App (t1, t2) ->
      let t = gensym () in   (* generate fresh variable *)
      App (Lam (t, Var (t)), (* let expression *)
           App (id_term' t1, id_term' t2)) ;;

(* a_normal : term_t => term_t *)
let rec a_normal term = match term with
    Var (x) -> Var (x)
  | Lam (x, t) -> Lam (x, reset (fun () -> a_normal t))
  | App (t1, t2) ->
      shift (fun k ->
        let t = gensym () in    (* generate fresh variable *)
        App (Lam (t,            (* let expression *)
                  k (Var (t))), (* continue with new variable *)
             App (a_normal t1, a_normal t2))) ;;

(* Exercise 11 *)

let s = Lam ("x", Lam ("y", Lam ("z",
          App (App (Var "x", Var "z"), App (Var "y", Var "z"))))) ;;

(* Section 2.12 *)

(* either : 'a -> 'a -> 'a *)
let either a b =
  shift (fun k -> k a; k b) ;;

reset (fun () ->
  let x = either 0 1 in
  print_int x;
  print_newline ()) ;;

(* Exercise 12 *)

(*
let choice lst = ...
*)

reset (fun () ->
  let p = either true false in
  let q = either true false in
  if (p || q) && (p || not q) && (not p || not q)
  then (print_string (string_of_bool p);
        print_string ", ";
        print_string (string_of_bool q);
        print_newline ())) ;;

(* Exercise 13 *)

(*
let search () =
  let x = ... in
  let y = ... in
  let z = ... in
  ...

reset (fun () -> search ()) ;;
*)