(* Programming language concepts for software developers, 2009-08-20 * *)

(* Representing object language expressions using recursive datatypes *)

type expr = 
  | CstI of int
  | Prim of string * expr * expr;;

let e1 = CstI 17;;

let e2 = Prim("-", CstI 3, CstI 4);;

let e3 = Prim("+", Prim("*", CstI 7, CstI 9), CstI 10);;


(* Evaluating expressions using recursive functions *)

let rec eval (e : expr) : int =
    match e with
      | CstI i -> i
      | Prim("+", e1, e2) -> eval e1 + eval e2
      | Prim("*", e1, e2) -> eval e1 * eval e2
      | Prim("-", e1, e2) -> eval e1 - eval e2
      | Prim _            -> failwith "unknown primitive";;

let e1v = eval e1;;
let e2v = eval e2;;
let e3v = eval e3;;


(* Changing the meaning of subtraction *)

let rec eval (e : expr) : int =
    match e with
      | CstI i -> i
      | Prim("+", e1, e2) -> eval e1 + eval e2
      | Prim("*", e1, e2) -> eval e1 * eval e2
      | Prim("-", e1, e2) -> 
        let res = eval e1 - eval e2
        in if res < 0 then 0 else res 
      | Prim _            -> failwith "unknown primitive";;


let e4v = eval (Prim("-", CstI 10, CstI 27));;


(* Association lists map object language variables to their values *)

let env = [("a", 3); ("c", 78); ("baf", 666); ("b", 111)];;

let emptyenv = []; (* the empty environment *)

let rec lookup env x =
    match env with 
     | []        -> failwith (x ^ " not found")
     | (y, v)::r -> if x=y then v else lookup r x;;

lookup env "c";;


(* Object language expressions with variables *)

type expr = 
  | CstI of int
  | Var of string
  | Prim of string * expr * expr;;

let e1 = CstI 17;;

let e2 = Prim("+", CstI 3, Var "a");;

let e3 = Prim("+", Prim("*", Var "b", CstI 9), Var "a");;


(* Evaluation within an environment *)

let rec eval e (env : (string * int) list) : int =
    match e with
      | CstI i            -> i
      | Var x             -> lookup env x 
      | Prim("+", e1, e2) -> eval e1 env + eval e2 env
      | Prim("*", e1, e2) -> eval e1 env * eval e2 env
      | Prim("-", e1, e2) -> eval e1 env - eval e2 env
      | Prim _            -> failwith "unknown primitive";;

let e1v  = eval e1 env;;
let e2v1 = eval e2 env;;
let e2v2 = eval e2 [("a", 314)];;
let e3v  = eval e3 env;;