I. static properties of variables (2.3)
 A. static vs. dynamic properties
------------------------------------------
    STATIC VS. DYNAMIC PROPERTIES (2.3)


def: a property of a language is:
    - *static* if


    - *dynamic* if



Static properties are important for



------------------------------------------
	Why aren't the dynamic ones important?
 B. variable bindings, static (2.3.1)
------------------------------------------
	  THE LAMBDA CALCULUS (2.3.1)
		lambda-1

Why?
   - core of most programming languages
   - only naming

Grammar:

  <lambda-1-exp> ::=



  <varref> ::= <var>
  <var> ::= <symbol>


------------------------------------------
	Can you give some examples in this grammar?
	Can you write a derivation of (lambda (x) x) using this grammar?
  1. free and bound variable references
------------------------------------------
        FREE AND BOUND VARREFS


  ((lambda (n) n) (car x))



def: a <varref> is *bound* in E if it
refers to


def: a <varref> is *free* in E if it
does not refer to a surrounding
formal parameter.

def: a variable x *occurs free* in E if


def: a variable x *occurs bound* in E if
E contains a bound <varref> named x.


Example:

   ((lambda (n) n) n)
                ^  ^
          bound-/  \-free
------------------------------------------
	in the expression, what does n refer to? car? x?
	So if n occurs free in a expression,
		does that mean it doesn't occur bound?
------------------------------------------
                FOR YOU TO DO

What are the (a) free, and
             (b) bound variables in ...

(lambda (x) (lambda (y) x))



(f (cdr x))



(lambda (x) (f (cdr x)))



(lambda (f) (lambda (x) (f (cdr x))))



------------------------------------------
------------------------------------------
	   FORMAL DEFINITIONS

notation:
  FV(E) = set of E's free variables
  BV(E) = set of E's bound variables

def: x \in FV(E) if and only if either:
1. E is a varref, x

2. E is an application, (E1 E2), and


3. E is a lambda, (lambda (y) E), and



def: x in BV(E) if and only if either:
1. E is a varref and false

2. E is an application, (E1 E2), and


3. E is a lambda, (lambda (y) E), and



------------------------------------------
------------------------------------------
	   MORE TERMINOLOGY

lexically bound =

globally bound =


dependency:
    (lambda (ls) (car (car ls)))

closed expression, combinator =


         SOME COMBINATORS

(lambda (n) n)               ; I
(lambda (x)                  ; K
  (lambda (y) x))
(lambda (x)                  ; S
  (lambda (y)
    (lambda (z)
      ((x z) (y z)))))
------------------------------------------
 C. scope and lexical address (2.3.2)
------------------------------------------
       VARIABLE DECLARATION REGIONS

 !-----------------------------!
 !   (lambda (x)	       !
 !   !----------------------!  !
 !   ! (lambda (y)	    !  !
 !   !  		    !  !
 !   !    (car (cons x y)) )!) !
 !   !----------------------!  !
 !-----------------------------!



     (lambda (x)

        (lambda (x)

           (+ x 3) ) )


def: a variable declaration's *region* is
an area of the program's text that
includes the declaration, and within which


def: a variable declaration's *scope* is
that part of its region within which

------------------------------------------
------------------------------------------
	   FOR YOU TO DO

     (lambda (x)

       (lambda (y)

         ((lambda (x) (x y))  x) ) )


1. draw arrows from each <varref>
   to the <var> declaration for it.

2. draw the contours.

3. What is the scope of each declaration?


		TERMINOLOGY

hole in the scope = 

------------------------------------------
	Is there a hole in the declaration of y's scope?
  1. lexical depth
------------------------------------------
	  LEXICAL DEPTH

def: the lexical depth of a <varref> is



 !-----------------------------!
 !   (lambda (x)	       !
 !   !----------------------!  !
 !   ! (lambda (y)	    !  !
 !   !  		    !  !
 !   !    (car (cons x y)) )!) !
 !   !----------------------!  !
 !-----------------------------!



------------------------------------------
	What's the lexical depth of y? x? cons? car?
  2. lexical address
------------------------------------------
	  LEXICAL ADDRESS

identify each varref by 2 numbers:
	d = lexical depth
	p = position, counted from 0

format:
	(v : d p)
         ^
         \-------- var name

(lexical-address
 (parse-lcm+if-exp 'cdr)) ==> (cdr : 0 0)

(lexical-address
 (parse-lcm+if-exp
     '(lambda (ls) (cdr ls))))
  ==> (lambda (ls)
       ((cdr : 1 0) (ls: 0 0)))

(lexical-address
 (parse-lcm+if-exp
     '(lambda (x)
        (lambda (y)
        (car (cons x y))))))
  ==> (lambda (x)
        (lambda (y)
	  ((car :   ) ((cons :   )
                          (x :    )
			  (y :    )))))
------------------------------------------
------------------------------------------
	  FOR YOU TO DO

What is?...

(lexical-address
 (parse-lcm+if-exp 
  '(lambda (x) (lambda (y) x))))


(lexical-address
 (parse-lcm+if-exp 
  '(lambda (x) (lambda (x) x))))


(lexical-address
 (parse-lcm+if-exp 
  '(lambda (x) (lambda (z) x))))


(lexical-address
 (parse-lcm+if-exp 
   '(lambda (a b c)
      (lambda (f g)
        (f (g a b) c a)))))





------------------------------------------
  3. renaming variables (2.3.3)
	do variable names really matter to a compiler?
------------------------------------------
	   RENAMING FORMALS

Which are equivalent?

 (lambda (x) (lambda (y) x))  ; a

 (lambda (x) (lambda (x) x))  ; b

 (lambda (x) (lambda (z) x))  ; c

 (lambda (m) (lambda (y) m))  ; d

 (lambda (m) (lambda (y) x))  ; e


Problems in renaming variables:
   - capture, as in

   - respecting inner bindings, as in

------------------------------------------
	What are their lexical address forms?
------------------------------------------
	FOR YOU TO DO

Are these equivalent?

  (lambda (x)
    ((lambda (x) (cons x '()))
     (cons x '())))

and
 
  (lambda (y)
    ((lambda (x) (cons y '()))
     (cons y '())))

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