Lecture 8


---
Review of last class:

  - referencing environment.

 > Environments: the set of active bindings

   empty
   insert name x env
   lookup name env

 > SML implementation

   datatype ('name, 'a) Env =
        Empty
       |Insert of 'name * 'a * ('name, 'a) Env

   exception NotFound

   val empty = Empty
   fun insert n x e = Insert (n, x, e)

   fun lookup name Empty =
         raise NotFound
     | lookup name (Insert (name', x, env)) =
        if name = name' then x
        else lookup name env
 > Types:

    empty = Empty : ('a, 'b) Env
    insert = fn: 'a -> 'b -> ('a, 'b) Env -> ('a, 'b) Env
    lookup = fn: ''a -> (''a, 'a) Env -> 'b

   (Note: the double quote means equality type polymorphism:
                  a type whose values admit equality testing)


 Symbol tables
 
  - for static scoping, exists at compile time, may retain in the target code for 
    the debugger's purpose.

 Association Lists and Central Reference Tables
  - for dynamic scoping
  - A-lists: (called shallow binding)
  - Central Reference Tables ( called deep binding)

 Subroutine closures
  - deep binding
  - shallow binding 

---


Interpretor can be considered as formal definition of semantics 
of a language.

We will build an interpretor for a very small subset of ML

The Mini-ML: variable name, anonymous function, function application, 
and addition.     

Its abstract syntax tree:

   datatype Exp = 
            Num of int    
          | Add of Exp * Exp
          | Var of string
          | Fn of string * Exp  (* string refers to  formal parameter, 
                                       Exp is body *)
          | App of Exp * Exp    (* calling function  on argument        *)
                                (* The frist Exp refers to the function *)
                                (* The 2nd Exp refers to the argument   *)


Define a fucntion Let, which is basically a syntax sugar.

   fun Let (x, e, body) = App(Fn (x, body), e)

e.g., in ML, we have a usage of "let ... in .. end" as

   let val x = 1
   in x + x
   end

which is equivalent to 

   (fn x => x + x ) 1

We first adopt dynamic scoping. For that, we need to define values to 
manipulate at run-time.

   datatype DValue = DNum of int
          | DFn of string * Exp

The interpretor is a function we name as "deval" with the type 
as follows.

   deval: Exp -> Env -> DValue

Here is the implementation of deval.

   fun deval (Num n) env = DNum n
     | deval (Add (e1, e2)) env = 
             let val n1 = getNum (deval e1 env)
                 val n2 = getNum (deval e2 env)
             in DNum (n1 + n2) end

(* we need to define an exception when we expect a number *)
(* but get sthelse *)

   exception TypeError

(* we define a helper function *)

   fun getNum (DNum n) = n
     | getNum _ = raise TypeError

(* we continue our implementation of deval *)

     | deval (Var x) env = lookup x env

     | deval (Fn (x, body)) env =  (* just read in an anonymous    *)
                                   (* function and change tag from *)
               DFn (x, body)       (* fn to DFn, as we did in the  *)
                                   (* case of deval (Num n).       *)
                                   (* Since the function is        *)
                                   (* anonymous, i.e., it has no   *)
                                   (* name, so we do not have to   *)
                                   (* consider how to implement    *)
                                   (* recursive function           *)

     | deval (App (e1, e2)) env = 
               let val (x, body) = getFn (deval e1 env)
                   val v = deval e2 env
                   val env' = insert x v env   
                   (* plug actual argument into formal parameter *)
               in 
                   deval body env'
               end

 
For implementing static scope, when a function is called, 
you have to evaluate it in the environment when the function was defined, 
which may be very different from the current environment when the function
is being called. 

So it is harder to write an interpretor for static scoping language.

Define run-time value for static scoping.

   datatype SValue = SNum of int
         |  SFn of string * Exp * Env  (* this is called closure *)

   fun seval (Fn (x, body)) env = SFn (x, body, env)  
                                   (* package up the environment   *)
                                  (* with the function definition *)
     | seval (App (e1, e2)) env =      
           let val (x, body, senv) = getFn ( seval e1 env)
               val v = seval e2 env
               val senv' = insert x v senv
           in
               seval body senv'
           end


e.g.,

    let val x = 1
        fun f y = x + y
        fun g y = 
                let val x = 2
                in f y end
    in g 5 end

    > 7 (* dynamic *)
    > 6 (* static  *)

val prog = Let ("x",Num 1,
           Let ("f",Fn ("y",Add (Var "x",Var "y")),
           Let ("g",Fn ("y",Let ("x",Num 2,App (Var "f",Var "y"))),
           App (Var "g",Num 5))))

(* run it with
 *   deval prog empty
 * or
 *   seval prog empty
 *)