<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
SCOPE OF VARIABLES

READING

* EOPL3e 3.5 [Scoping and binding of variables]
* EOPL3e Exercise 3.28 on page 82

Motivation: now we move back from how to program
	to the study of languages in general
	Still using (subsets of) Scheme for examples, however.

** static vs. dynamic properties
------------------------------------------
    STATIC VS. DYNAMIC PROPERTIES 


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


    - *dynamic* if


Static properties are important for


------------------------------------------
	... it can be checked (in general) before running the program
	... it cannot be checked (in general) before running the program
	... code improvement (so-called optimization),
	    for reasoning about correctness,
	    and for consistency checking (such as type checking).

	Q: Are the dynamic ones important too?
           Yes, but not for optimization or correctness

** variable bindings, static 

------------------------------------------
	  THE LAMBDA CALCULUS 
		lambda-1-exp

Why?
   - core of most programming languages
   - only naming

Grammar:

  <expression> ::=


------------------------------------------
	we'll call this lambda-1-exp to distinguish it from other versions,
		the 1 refers to the 1-argument nature of the procedures

	... <identifier>                          "var-exp (id)"
          | (lambda (<identifier>) <expression>)  "lambda-exp (id body)"
          | (<expression> <expression>)           "app-exp (rator rand)"

	Q: Can you give some examples in this grammar?

	Q: Can you write a derivation of (lambda (x) x) using this grammar?

	The traditional syntax for the 2nd rule is with greek lambda and dot:
		(\ <identifier> . <expression>)

	The meaning is like in Scheme,
		think of (lambda (x) ...) as a declaration of x,
		with value to be supplied by a call (application).

	Note the differences between use of variables in a varref
        and declaration in a lambda as the formal.

*** free and bound variable references

------------------------------------------
        FREE AND BOUND VARREFS

def: In
   (lambda (<identifier>) <expression>)
the <identifier> is the declaration
of a formal parameter and *binds*
all occurrences of that variable in
<expression>, unless there is an
intervening declaration of the formal.

  ((lambda (b) b) (car f))


  (((lambda (b) (lambda (b) (b f))) f) f1)


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


def: a variable x *occurs bound* in E iff
E contains a use of x that is bound by
a declaration of x in E

---------------------------------------------------------
	Q: in the expression, what does b refer to? car? f?

	Draw arrows from uses to declarations in the two examples
          (note, opposite to the arrows in DrScheme)

	Be sure they understand what "intervening declarations" mean
        before going on

	... E contains a use of x that is not bound by any declaration
            of x in E


---------------------------------------------------------
            EXAMPLES

 f, f1 occur free in:
         f
         (f f1)
         (lambda (b) f)

 b, b1 occur bound in:
         (lambda (b) b)
         (lambda (b1) (lambda (b) (b1 b)))

 There can be a mix:

   ((lambda (b) b) f)
                ^  ^
          bound-/  \-free
     occurrence      occurrence

 The same variable can occur both free and bound

   ((lambda (n) n) n)
                ^  ^
          bound-/  \-free
     occurrence      occurrence

 Variables that are free in a subexpression
 may be bound in a larger expression

     (lambda (f)
       ((lambda (b) (b f1)) f)
     )

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

	Q: 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))


(g (cdr x))


(lambda (x) (g (cdr x)))


(lambda (g) (lambda (x) (g (cdr x))))


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

       The book gives the following using the characteristic
       predicates, i.e., x occurs free in E iff...

------------------------------------------
	 CONSTRUCTIVE DEFINITIONS

notation:
  FV(E) = set of variables
            that occur free in E
  BV(E) = set of variables
            that occur bound in E

def: FV(E) =
        {x}, if E is a varref, x

           , if E is (E1 E2), and

           , if E is (lambda (y) E)


def: BV(E) =
         {}, if E is a varref

           , if E is (E1 E2), and


           , if E is (lambda (y) E)


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

	... FV(E1) \union FV(E2)
	... FV(E) - {y}

	... BV(E1) \union BV(E2)
	... BV(E) \union ({y} \intersect FV(E))

------------------------------------------
	   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)))))
------------------------------------------
	a variable reference is:
	... bound to a formal parameter in a surrounding lambda
	... bound at the top level
		it's an error in Scheme if a variable isn't lexically or
		globally bound

	the lambda given is dependent on the value of car,
		if that is changed, it does something different.

	... a term with no free variable references

	interesting that these 3 combinators suffice to program
		any computable function!

** scope and lexical address 

        Now we're going to switch grammars a bit,
        and allow multiple arguments to applications,
        and multiple formals

------------------------------------------
       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

------------------------------------------
	- point out the regions, contours
          A region is the area occupied by a lambda-expression.

	- show how to draw arrows from varrefs to formal declarations

	... the declaration *may* have effect (varrefs may refer to it)
	... the declaration *does* have effect (varrefs will refer to it)

	Note: region and scope refer to declarations, not variables.
		however, sometimes people confuse the two,
		(ok when the same variable isn't used in 2 declarations,
			but can lead to confusion otherwise.)

	motto: declarations have scope, not variables names.
		The following shows this

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

     (lambda (x)

       (lambda (y)

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


1. Draw arrow from each variable reference
   to its declaration.

2. Draw the contours.

3. What is the scope of each declaration?


		TERMINOLOGY

hole in the scope = 

------------------------------------------
	... subarea of a var declaration's region
		in which the var declaration has no effect.

	point out the hole in the scope above.
	Q: Is there a hole in the declaration of y's scope?

*** lexical depth
	This is used in compilers to tell how many static links
		to traverse to find the variable's declaration.
------------------------------------------
	  LEXICAL DEPTH

def: the lexical depth of a variable use
     is


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


------------------------------------------
	... the number of contours crossed in
	going from the variable use to its declaration.

        For this language, contours are the same as
	lambda-expressions, so the number of contours crossed 
        is the same as the number of lambdas exited

	Q: What's the lexical depth of y? x? cons? car?


*** lexical address
	compilers don't want to deal with names for variables,
		work better with numbers
	what they use is a pair of numbers to access each variable:
		lexical depth (number of static links),
		and the lexical position (an offset within activation frame)

------------------------------------------
	  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-expression 'cdr)) ==> (cdr : 0 0)

(lexical-address
 (parse-expression
     '(lambda (ls) (cdr ls))))
  ==> (lambda (ls)
       ((cdr : 1 0) (ls: 0 0)))

(lexical-address
 (parse-expression
     '(lambda (x)
        (lambda (y)
        (car (cons x y))))))
  ==> (lambda (x)
        (lambda (y)
	  ((car :   ) ((cons :   )
                          (x :    )
			  (y :    )))))
------------------------------------------
       ... 

	can erase the names,
		unless needed for debugging (as in -g option of CC)

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

What is?...

(lexical-address
 (parse-expression 
  '(lambda (x) (lambda (y) x))))


(lexical-address
 (parse-expression 
  '(lambda (x) (lambda (x) x))))


(lexical-address
 (parse-expression 
  '(lambda (x) (lambda (z) x))))


(lexical-address
 (parse-expression 
   '(lambda (a b c)
      (lambda (f g)
        (f (g a b) c a)))))


------------------------------------------
	allowing more than one var in a lambda above,
		and more than one expression in an application
	this is as in homework

*** renaming variables (skip)

	The first program transformation rule this course,
		we'll see several,
		all useful in rewriting programs.

	Q: do variable names really matter to a compiler?
	What matters is the shape of an expression,
		that is, what variables refer to what var declarations,
		as in lexical-address computation

------------------------------------------
	   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

------------------------------------------
	Q: What are their lexical address forms?
	... changing y in a to x, producing b, instead of c
	... changing x in a to m, producing e, instead of d


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

Are these equivalent?

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

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

------------------------------------------
	... no