I. static properties of variables (EOPL2e 1.3) A. static vs. dynamic properties ------------------------------------------ STATIC VS. DYNAMIC PROPERTIES (1.3) def: a property of a language is: - *static* if - *dynamic* if Static properties are important for ------------------------------------------ Are the dynamic ones important too? B. variable bindings, static (1.3.1) ------------------------------------------ THE LAMBDA CALCULUS (1.3.1) lambda-1-exp Why? - core of most programming languages - only naming Grammar: ::= ------------------------------------------ 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 def: In (lambda () ) the is the declaration of a formal parameter and *binds* all occurrences of that variable in , 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 --------------------------------------------------------- in the expression, what does b refer to? car? f? --------------------------------------------------------- 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) ) --------------------------------------------------------- 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)))) ------------------------------------------ ------------------------------------------ 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) ------------------------------------------ ------------------------------------------ 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 (1.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 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 = ------------------------------------------ Is there a hole in the declaration of y's scope? 1. lexical depth ------------------------------------------ LEXICAL DEPTH def: the lexical depth of a variable use 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-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 : ))))) ------------------------------------------ ------------------------------------------ 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))))) ------------------------------------------ 3. renaming variables (skip) 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 '()))) ------------------------------------------