(* This file defines a very simple interpreter for a little expression language
 * similar to Ocaml.
 *)

(************************************************************************)
(* The abstract syntax or AST for the language                          *)
(************************************************************************)
module Ast =
struct
  (* This is a type abbreviation *)
  type var = string 

  (* we only have one type for this little language *)
  type tipe = IntType
    
  (* Define the abstract syntax for a little expression language *)
  type binop = Plus | Minus | Times | Div
    
  type exp = 
    | Int of int
    | Binop of exp * binop * exp
    | Var of var
    | Let of var * exp * exp

  (* Some example expressions as abstract syntax trees *)
  let e1 = Let("x",Int 42,Binop(Var "x",Times,Var "x"))
  let e2 = Binop(e1,Div,Int 3)
  let e3 = Let("y",e2,Binop(Var "y",Minus,Int 14))

end (* module Ast *);;


(************************************************************************)
(* An abstract signature for environments                               *)
(************************************************************************)
module type ENV = 
sig
  type 'a env
  exception UnboundVariable of Ast.var
  val empty : unit -> 'a env
  val lookup : Ast.var -> 'a env -> 'a
  val extend : Ast.var -> 'a -> 'a env -> 'a env
end

(*************************************************************************)
(* One (inefficient) implementation of environments as association lists *)
(*************************************************************************)
module Env : ENV = 
struct
  open Ast
  type 'a env = (var * 'a) list

  (* Declares a new exception *)
  exception UnboundVariable of var

  (* The empty environment -- an empty association list *)
  let empty():'a env = []

  (* Lookup variable x in the environment, returning the associated value,
   * and raising the exception UnboundVariable if the variable is not found. *)
  let rec lookup(x:var) (env:'a env) = 
    match env with
      [] -> raise (UnboundVariable x)
    | (y,i)::rest -> if (x = y) then i else lookup x rest
        
  (* Extend env so that it maps x to i *)
  let extend (x:var) (i:'a) (env:'a env) = (x,i)::env
end

(**************************************************************************)
(* Evaluate an expression in an environment mapping variables to integers *)
(**************************************************************************)
module Eval : sig val evaluate : Ast.exp -> int end =
struct    
  open Ast
  let rec eval (e: exp) (env: int Env.env) : int = 
    let binop2fn b = 
      match b with
        | Plus -> (+)   (* the parens are needed for infix functions like + *)
        | Minus -> (-)
        | Times -> (fun x y -> x*y) (* conflicts with comments... *)
        | Div -> (/)
    in
      match e with
        | Int i -> i
        | Binop (e1,b,e2) -> (binop2fn b) (eval e1 env) (eval e2 env)
        | Var x -> Env.lookup x env
        | Let (x,e1,e2) -> 
            let i = eval e1 env in
              eval e2 (Env.extend x i env)

  (* Evaluate an expression -- start off with the empty environment *)
  let evaluate (e:exp) : int = eval e (Env.empty())
end


(************************************************************************)
(* Put it all together                                                  *)
(************************************************************************)

let calc(e:Ast.exp) = 
  let i = Eval.evaluate e in 
    Printf.printf "The result is %d\n" i

(* You can load this file into the ocaml toplevel by entering 
   "#use "interp.ml" at the prompt.  Note that you need "#" before "use".
   You can then use the interpreter, e.g., 
   calc Ast.e1
   calc (Ast.Int 4)
   etc.
*)