Lecture 7

--- 
Administrative

 - homework 1 is due.
 - homework 2 is out and is due at 9:30AM, 15 Oct. 
   Note: submission policy change: email your submission to BOTH the instructor and the TA


---

- Names and scopes.

 > Names in high level programming languages are abstraction of location in memory. 

    Goal: to ease programmer from the burden of handling addresses directly.

    Coveat: 1.  distinction b/w names and the objects to which they refer
            2.  name space -> avoid conflicting (see scoping for another alternative)

 > Binding: asscociation between a name and the thing it names.

    o Binding time: 

       Compile time (static)  -> more efficiency, less flexibility

       Run time (dynamic)     -> less efficiency, more flexibility 

 > Object lifetime and storage management

    o distinction between the binding's lifetime

       - binding outlives the object -> dangling reference

       - objects outlive binding -> memory leakage -> garbage collection

    o object types

       - static: such as global variables, constants, program instructions:
                 -> absolute address

       - stack:  such as local variables in subroutines
                 -> activation records (frames) are put on a stack 
                    (local variables' offset w.r.t the frame is fixed)



                        ^
                        | direction of stack growth
                        |
                        | 

                 |              |
         sp -->  |--------------|
                 | subroutine C |
                 |   ------     |
                 |   Temp       |
                 |   ------     |
                 |   local      |
                 |  variables   | 
                 |   ------     |
                 |   misc       |
                 |   ------     |
                 | return addr  |
                 |              |
         fp-->   |--------------|  
                 | subroutine B |  
                 |--------------|  
                 | subroutine A |  
                 |              |
                 ---------------

             (more details when discuss subroutines) 


       - heap:   dynamically allocated and deallocated at arbitrary time
                 (garbage colletion is meant for this chunck of memory) 

             (more details when discuss garbage collection)

- Scope Rules

  > Definition: scope is part of a program where you can refer to a variable with its name

    o Goal: to ease burden on your imagination to give distinct names,
            to save name space, and to enable structural and/or modular programming

    o scopes are typically nested

      -  Global scope, such as in BASIC

  > Shadowing

    global objects are hidden or shadowed by local objects of the same names.
    

  > Static (or lexical) scoping: most textually recent one that has not
                          ended yet. Can be determined at compile time
     e.g., C, and most programming languages

  > Dynamic scoping: can only be determined at run-time
     e.g., APL, Snobol, and early dialects of Lisp

e.g.,

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

  g 5;
  > 7 (* if dynamic *)
  > 6 (* if static *)

  > hybrids: Perl

  > problem with dynamic scoping.

   e.g.,
     val pi = 3.14159
     fun area r = pi * r * r

     fun dough pi sz = pi * area (sz / 2 )
     dough 20 10
     > 20 * 20 * (10/2) * (10/2)

    However, it is simpler to implement interpretor using dynamic scoping.


  > Aliasing: an extra name for something that already has a name 
         in the current scope.
     o will often cause problems.
  e.g., pass a variable by reference to a subroutine that also accesses
    that variable directly.

     void swap (int &x, int &y) {
        x = x + y; 
        y = x - y;
        x = x - y;
     } // this artificial version of code tries to same space 
       // from assigning a temp variable. 

     swap (a, a); // will return 0, which is wrong!



Environments: the set of active bindings

   empty
   insert name x env
   lookup name env

--------------------------

   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)