Homework 3: recrec should evaluate its arguments immediately• Why?1Homework 3: recrec should evaluate its arguments immediately• Why?To match existing programming languages; otherwise it isnot call-by-value2Homework 3: recrec should evaluate its arguments immediately• Why?To match existing programming languages; otherwise it isnot call-by-value• Can you tell the difference? (recall the “are these twoprograms equivalent?” game)3Homework 3: recrec should evaluate its arguments immediately• Why?To match existing programming languages; otherwise it isnot call-by-value• Can you tell the difference? (recall the “are these twoprograms equivalent?” game)Nontermination and errors both show the difference inF1WAE; if we had other effects (e.g., exceptions, mutablestate) they too would also show the difference4Cost of Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )5Cost of Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )⇒(interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y 1}}}}} )6Cost of Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )⇒(interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y 1}}}}} )⇒(interp {+ 100 {+ 99 {+ 98 ... {+ 2 1}}}} )7Cost of Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )⇒(interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y 1}}}}} )⇒(interp {+ 100 {+ 99 {+ 98 ... {+ 2 1}}}} )With n variables, evaluation will take O(n2) time!8Deferring Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )9Deferring Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )⇒(interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}x = 1)10Deferring Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )⇒(interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}x = 1)⇒(interp {+ 100 {+ 99 {+ 98 ... {+ y x}}}}y = 2 x = 1)11Deferring Substitution(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}} )⇒(interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}x = 1)⇒(interp {+ 100 {+ 99 {+ 98 ... {+ y x}}}}y = 2 x = 1)⇒ ... ⇒(interp yy = 2 x = 1)12Deferring Substitution with the Same Identifier(interp {with {x 1} {with {x 2} x}} )13Deferring Substitution with the Same Identifier(interp {with {x 1} {with {x 2} x}} )⇒(interp {with {x 2} x}x = 1)14Deferring Substitution with the Same Identifier(interp {with {x 1} {with {x 2} x}} )⇒(interp {with {x 2} x}x = 1)⇒(interp xx = 2 x = 1)15Deferring Substitution with the Same Identifier(interp {with {x 1} {with {x 2} x}} )⇒(interp {with {x 2} x}x = 1)⇒(interp xx = 2 x = 1)Always add to start, then always check from start16Deferring Substitution with the Same Identifier(interp {with {x 1} {+ {with {x 2}x}x}} )17Deferring Substitution with the Same Identifier(interp {with {x 1} {+ {with {x 2}x}x}} )(interp {+ {with {x 2} x}x}x = 1)18Deferring Substitution with the Same Identifier(interp {with {x 1} {+ {with {x 2}x}x}} )(interp {+ {with {x 2} x}x}x = 1)(+ (interp {with {x 2} x}x = 1) (interp xx = 1))19Deferring Substitution with the Same Identifier(interp {with {x 1} {+ {with {x 2}x}x}} )(interp {+ {with {x 2} x}x}x = 1)(+ (interp {with {x 2} x}x = 1) (interp xx = 1))(+ (interp xx = 2 x = 1) (interp xx = 1))20Deferring Substitution with the Same Identifier(interp {with {x 1} {+ {with {x 2}x}x}} )(interp {+ {with {x 2} x}x}x = 1)(+ (interp {with {x 2} x}x = 1) (interp xx = 1))(+ (interp xx = 2 x = 1) (interp xx = 1))(+ 2 1)21Representing Deferred SubstitutionChange; interp : WAE -> numto; interp : WAE DefrdSub -> num22Representing Deferred SubstitutionChange; interp : WAE -> numto; interp : WAE DefrdSub -> num(define-type DefrdSub [mtSub] [aSub (name symbol?)(value number?)(rest DefrdSub?)])23Interp with DefrdSub(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}}(mtSub))24Interp with DefrdSub(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}}(mtSub))⇒ (interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}(aSub 'x 1 (mtSub)))25Interp with DefrdSub(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}}(mtSub))⇒ (interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}(aSub 'x 1 (mtSub)))⇒ (interp {+ 100 {+ 99 {+ 98 ... {+ y x}}}}(aSub 'y 2 (aSub 'x 1 (mtSub))))26Interp with DefrdSub(interp {with {x 1} {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}}(mtSub))⇒ (interp {with {y 2} {+ 100 {+ 99 {+ 98 ... {+ y x}}}}}(aSub 'x 1 (mtSub)))⇒ (interp {+ 100 {+ 99 {+ 98 ... {+ y x}}}}(aSub 'y 2 (aSub 'x 1 (mtSub))))⇒ ...⇒ (interp y (aSub 'y 2 (aSub 'x 1 (mtSub))))27WAE Interpreter with Deferred Substitutions; interp : WAE DefrdSub -> num(define (interp a-wae ds) (type-case WAE a-wae [num (n) n] [add (l r) (+ (interp l ds) (interp r ds))] [sub (l r) (- (interp l ds) (interp r ds))] [with (bound-id named-expr body-expr) ...] [id (name) ...]))28WAE Interpreter with Deferred Substitutions; interp : WAE DefrdSub -> num(define (interp a-wae ds) (type-case WAE a-wae [num (n) n] [add (l r) (+ (interp l ds) (interp r ds))] [sub (l r) (- (interp l ds) (interp r ds))] [with (bound-id named-expr body-expr) ...] [id (name) (lookup name ds)]))29WAE Interpreter with Deferred Substitutions; lookup : symbol DefrdSub -> num(define (lookup name ds) (type-case DefrdSub ds [mtSub () (error 'lookup "free variable")] [aSub (sub-name num rest-ds)(if (symbol=? sub-name name)num(lookup name rest-ds))]))30WAE Interpreter with Deferred Substitutions; interp : WAE DefrdSub -> num(define (interp a-wae ds) (type-case WAE a-wae [num (n) n] [add (l r) (+ (interp l ds) (interp r ds))] [sub (l r) (- (interp l ds) (interp r ds))] [with (bound-id named-expr body-expr) ...] [id (name) (lookup name ds)]))31WAE Interpreter with Deferred Substitutions; interp : WAE DefrdSub -> num(define (interp a-wae ds) (type-case WAE a-wae [num (n) n] [add (l r) (+ (interp l ds) (interp r ds))] [sub (l r) (- (interp l ds) (interp r ds))] [with (bound-id named-expr body-expr) ... (interp named-expr ds) ...] [id (name) (lookup name ds)]))32WAE Interpreter with Deferred Substitutions; interp : WAE DefrdSub -> num(define (interp a-wae ds) (type-case WAE a-wae [num (n) n] [add (l r) (+ (interp l ds) (interp r ds))] [sub (l r) (- (interp l ds) (interp r ds))] [with (bound-id named-expr body-expr) ...(aSub bound-id (interp named-expr ds) ds)...] [id (name)
View Full Document