Lecture 9

---
Administrative

- homework 2
  > check bulletin board for updates
    o using foldl is no longer a requirement but an extra credit
    o no while loop is allowed
    o no change to the support code is allowed
  > how to "bebug" in SML?
    o print ("hello world\n");
    o example:

       val debugFlag = ref flase
       fun debug msg = 
                (if !debugFlag then print (msg^"\n") else ();
                 fn x => x)

       ...
       fun exec ...
         | exec Exit (vs, ds) = debug "Exit loop" 
                                ....
         | ...
 
     To turn on the debugFlag, under SML prompt types 

       debugFlag := true;

     To turn it off, types

       debugFlag := false;


---
Control Flow (1)

Ordering of program execution is fundamental to most models of
computing.

Ordering can be classified into 7 categories:

 1. sequencing
 2. selection
 3. iteration
 4. procedural abstraction
 5. recursion
 6. concurrency
 7. nondeterminacy



- Expressions versus Statements (or commands)

   Expressions: evaluating sth., and return a value.
   Statements:  doing sth (e.g., change the states of the machine)

   Some languages blur the distinction, like C. 
   In ML, there are only expressions.

   Issues related to ordering:
    > precedence and associativity
    quiz: 1. Given that exponentiation operator (**) is right associtive, 
             how do we group 4**3**2 ?
          2. how precedence and associativity are defined differently 
             when postfix and prefix notation is used?
    > ordering within expressions 
      (not specified by precedence and associativity)

    e.g.,  a - f(b) - c * d
    will a - f(b) be first evaluated or c * d ?
    The order may matter. For example, if f(b) may modify d.


  Assignment

    syntax    x := 1  in Pascal
              x = 1 in C   

   Note: things at two sides are treated very differently.

   e.g., 
         x = y;

   while y will be evaluated, x is not.

   Value model of variables:
    a variable is a named contained for a value.

    x is called L-values, referring to address, or location;
    y is called R-values, referring to variable and contents.

   Therefore, constants can not be used as L-values. 
   e.g., 2 = 3 is wrong.

   *p = 2
   de-reference pointer
   a[1] = 5
   x.name

   e.g., a[i] = b[i];

   where a[i] is L-value, b[i] is R-value, both i's are R-value.

   e.g., a[ b[j] + c[j] ] = 9;

   where b[j] + c[j] while at left-hand side is R-value 
   because you need to evaluate it.

  Reference models of variables:
    a variable is named reference to a value.

  comparisons between value models and reference models:

    b := 2;
    c := b;
    a := b + c;


     value model                    reference model
    -------------                   ---------------

     a   [4]                        a ---->  [4]
    
     b   [2]                        b ----\
                                           > [2]
     c   [2]                        c ----/


   Languages using reference model: 
          Algo 68, Clu, Lisp/Scheme, ML, Haskell, and Smalltalk
   Languages using value model:
          C, Pascal, Ada, and many others
   Languages using hybrid:
          Java  (value model for built-in types, reference model for objects)

  > call-by-reference

      f(x)

   where x is L-value, namely, the address of variable x.

      function f(y) {
         y = 5;
      }

   The assignment inside the function body will also affect x 
   when call-by-reference, but won't affect x at all if call-by-value. 
   This is aliasing.

   Note that these are concepts orthognal to dynamic and static scope.
                                ^^^^^^^^^

  > To handle assignment, we need to modify our definition of environment.

    Environment now has two parts. The first part is still called 
    environment, which is still a finite map, but from variable names 
    to location (instead of directly to variable value); the second part 
    is called store, which maps location to values.

    For R-value we look up variable name in environment to find 
    its Loc and then to find the actual value in store.
    For L-value we only need to look up in environment.

    Correspondingly we mofidy Exp by adding a case for assignment

    datatype Exp = 
       ....
      | Assign of string * Exp

    where string refers to the LHS of assignment and Exp to the RHS.
  
    (* locations *)
    type Loc = int

    (* function to allocate a new location *)
    val = nextLoc = ref 0
    fun newLoc () = (nextLoc := nextLoc + 1; !nextLoc)

    datatype SValue = Snum of int | SFn of string * Exp * Env
    withtype Env    = (string, Loc) Dict
         and Store  = (Loc, SValue) Dict


  Interpretor is implemented as follows.
  (* eval: Exp -> Env -> Store -> SValue * Store *)
                                  ^^^^^^^^^^^^^^
                                  machine state is now part of the final output!

     
  fun eval (Num n) env sto = (SNum n, sto)
    | eval (Add (e1, e2)) env sto =
             let val (n1, sto1) = getNum (eval e1 env sto)
                 val (n2, sto2) = getNum (eval e2 env sto1)
             in 
                 (SNum (n1 + n2), sto2)
             end
(* the reason to use sto1 is when we evaluate e1, e1 may have made some 
 * assignments which change the store. e.g, (x=5) + (x+6).
 * evaluation of assignment may change the store, so this change needs to 
 * be recorded and carried over
 *)


    | eval (Var x) env sto =
             let val loc = lookup x env
             in
                 (lookup loc sto, sto)
             end
    | eval (Fn env) = (SFn (x, e, env), sto)
      (* for static scoping we have to keep env associated with the function *)
 
    | eval (Assign (x, e)) env sto =
             let val (v, sto1) = eval e env sto
                 val loc = lookup x env
                 val sto2 = insert loc v sto1
             in 
                 (v, sto2)
             end

    | eval (App (e1, e2)) env sto = 
             let val (x, ebody, senv, sto1) = get Fn (eval e1 env sto)
                 val (v, sto2) = eval e2 env sto1
                 val loc = newLoc()
                 val senv' = insert x loc senv
                 val sto3 = insert loc v sto1
             in 
                 eval ebody senv' sto3 
             end

    (* complete code will be posted separately *)