Administrative StuffYou should have a tlab account by now; check your spamtraps if you didn’t get email about it.Class is Mondays and Fridays now.Reminder: sign up for the mailing list.1The Arbitrariness of IdentifiersThe “Are the following two programs equivalent?” game2The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ x 1))(f 10)(define (f y) (+ y 1))(f 10)3The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ x 1))(f 10)(define (f y) (+ y 1))(f 10)yesargument is consistently renamed4The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ x 1))(f 10)(define (f x) (+ y 1))(f 10)5The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ x 1))(f 10)(define (f x) (+ y 1))(f 10)nonot a use of the argument anymore6The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ x 1))(f 10)(define (f y) (+ x 1))(f 10)7The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ x 1))(f 10)(define (f y) (+ x 1))(f 10)nonot a use of the argument anymore8The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ y 1))(f 10)(define (f z) (+ y 1))(f 10)9The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ y 1))(f 10)(define (f z) (+ y 1))(f 10)yesargument never used, so almost any name is ok10The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ y 1))(f 10)(define (f y) (+ y 1))(f 10)11The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ y 1))(f 10)(define (f y) (+ y 1))(f 10)nonow a use of the argument12The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ y 1))(f 10)(define (f x) (+ z 1))(f 10)13The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (+ y 1))(f 10)(define (f x) (+ z 1))(f 10)nostill an undefined identifier, but a different one14The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f z) (local [(define y 10)] (+ z y)))(f 0)15The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f z) (local [(define y 10)] (+ z y)))(f 0)yesargument is consistently renamed16The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f x) (local [(define z 10)] (+ x z)))(f 0)17The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f x) (local [(define z 10)] (+ x z)))(f 0)yeslocal identifier is consistently renamed18The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f x) (local [(define x 10)] (+ x x)))(f 0)19The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f x) (local [(define x 10)] (+ x x)))(f 0)nolocal identifier now hides the argument20The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f y) (local [(define y 10)] (+ y y)))(f 0)21The Arbitrariness of IdentifiersAre the following two programs equivalent?(define (f x) (local [(define y 10)] (+ x y)))(f 0)(define (f y) (local [(define y 10)] (+ y y)))(f 0)nolocal identifier now hides the argument22Free and Bound IdentifiersAn identifier for the argument of a function or the nameof a local identifier is a binding occurrence(define (f x y) (+ x y z))(local [(define a 3)(define c 4)] (+ a b c))23Free and Bound IdentifiersA use of a function argument or a local identifier is abound occurrence(define (f x y) (+ x y z))(local [(define a 3)(define c 4)] (+ a b c))24Free and Bound IdentifiersA use of an identifier that is not function argument or alocal identifier is a free identifier(define (f x y) (+ x y z))(local [(define a 3)(define c 4)] (+ a b c))25Arithmetic Language<AE> ::= <num>| {+ <AE> <AE>}| {- <AE> <AE>}26Arithmetic Language<AE> ::= <num>| {+ <AE> <AE>}| {- <AE> <AE>}(define-type AE [num (n number?)] [add (lhs AE?)(rhs AE?)] [sub (lhs AE?)(rhs AE?)])27Arithmetic Language<AE> ::= <num>| {+ <AE> <AE>}| {- <AE> <AE>}(define (interp an-ae) (type-case AE an-ae [num (n) n] [add (l r) (+ (interp l) (interp r))] [sub (l r) (- (interp l) (interp r))]))28Arithmetic Language<AE> ::= <num>| {+ <AE> <AE>}| {- <AE> <AE>}(define (interp an-ae) (type-case AE an-ae [num (n) n] [add (l r) (+ (interp l) (interp r))] [sub (l r) (- (interp l) (interp r))]))No identifiers to help us study binding...29With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW30With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW{with {x {+ 1 2}} {+ x x}}⇒631With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEWx⇒ error: free identifier32With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW{+ {with {x {+ 1 2}} {+ x x}}{with {x {- 4 3}} {+ x x}}} ⇒ 833With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW{+ {with {x {+ 1 2}} {+ x x}}{with {y {- 4 3}} {+ y y}}} ⇒ 834With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW{with {x {+ 1 2}} {with {x {- 4 3}} {+ x x}}}⇒235With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW{with {x {+ 1 2}} {with {y {- 4 3}} {+ x x}}}⇒636With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW(define-type WAE [num (n number?)] [add (lhs WAE?)(rhs WAE?)] [sub (lhs WAE?)(rhs WAE?)] [with (name symbol?)(named-expr WAE?)(body WAE?)] [id (name symbol?)])37With Arithmetic Language<WAE>::=<num>|{+ <WAE> <WAE>}|{- <WAE> <WAE>}|{with {<id> <WAE>} <WAE>}NEW|<id>NEW(define (interp a-wae) (type-case WAE a-wae [num (n) n] [add (l r) (+ (interp l) (interp r))] [sub (l r) (- (interp l) (interp r))] [with (bound-id named-expr body-expr) ...] [id (name) ...]))38With Arithmetic