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 ------------------------------------------ Why aren't the dynamic ones important? 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 some intervening declaration occurs. ((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 thath 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: 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 (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 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 (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 '()))) ------------------------------------------