(* Part I Definitions *) type nat = int let rec fact (n:nat) : nat = if n <= 0 then 1 else fact (n-1) * n let rec fib (n:nat) : nat = match n with 0 -> 0 | 1 -> 1 | n -> fib (n-1) + fib (n-2) let rec len (xs:nat list) : nat = match xs with | [] -> 0 | hd::tl -> 1 + len tl (* Part I Solutions *) type cont = nat -> nat let rec fact_cont (n:nat) (k:cont) : nat = if n <= 0 then k 1 else fact_cont (n-1) (fun m -> k (m*n)) let rec fib_cont (n:nat) (k:cont) : nat = match n with 0 -> k 0 | 1 -> k 1 | n -> fib_cont (n-1) (fun m1 -> fib_cont (n-2) (fun m2 -> k (m1 + m2))) let rec len_cont (nl: nat list) (k:cont) : nat = match nl with | [] -> k 0 | hd::tl -> len_cont tl (fun r -> k (1+r) ) let fact_acc (n:nat) : nat = let rec aux (n:nat) (a:nat) : nat = if n <= 0 then a else aux (n-1) (a*n) in aux n 1 let fib_acc (n:nat) : nat = let rec aux (n:nat) (mo:nat) (mt:nat) : nat = if n <= 0 then mt else aux (n-1) (mo+mt) (mo) in aux n 1 0 let rec len_acc (xs:nat list) : nat = let rec aux (xs:nat list) (acc: nat) : nat = match xs with | [] -> acc | hd::tl -> aux tl (acc+1) in aux xs 0 let f5 = fact 5 let c5 = fact_cont 5 (fun m -> m) let a5 = fact_acc 5 let f5 = fib 5 let c5 = fib_cont 5 (fun m -> m) let a5 = fib_acc 5 let l5 = len [1;2;3;4;5] let c5 = len_cont [1;2;3;4;5] (fun m -> m) let a5 = len_acc [1;2;3;4;5] (* Part II *) let c = 5 let d = 6 let apply (f : int -> int) : int = f (c*d) let sum (y : int) : int = y + c + d let result = apply sum (* solution *) type env = {cx:int; dx:int} type ('a,'b) closure = ('a * env -> 'b) * env let apply_code ((f_closure, env) : (int,int) closure * env) : int = let (f_code,f_env) = f_closure in f_code (env.cx*env.dx, f_env) let sum_code ((y, env) : int * env) : int = y + env.cx + env.dx let result_closure = apply_code ((sum_code, {cx=c; dx=d}), {cx=c; dx=d})