DOC PREVIEW
NU EECS 395 - Homework 3 - rec

This preview shows page 1-2-3-23-24-25-26-46-47-48 out of 48 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

NU EECS 395 - Homework 3 - rec

Download Homework 3 - rec
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework 3 - rec and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 3 - rec 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?