Assignment 3: Environments and Interpreters
Show pagesource
Log In
env apply-env empty-env four
all four interpreters a3.rkt
You must define two sets of environment helpers: one that uses functional (higher-order) representation of environments, and one that uses data-structural representation of
extend-
environments.
value-of-fn
value-of
tagged list
value-of-ds
(define value-of …)
(define value-of-fn …)
(define empty-env-fn …)
(define extend-env-fn …)
(define apply-env-fn …)
(define value-of-ds …)
(define empty-env-ds …)
(define extend-env-ds …)
(define apply-env-ds …)
zero? sub1 * if
not lambda
let
(let ([x e]) body)
((lambda (x) body) e) let
let
yvnaDdna]rehto_htimscl=txetnoc&2101=elcitra?igc.tnetnocweiv/igc/ude.rys.ecafrus//:ptth[ sdlonyeR ees ,gniod er’ew tahw fo gnidnatsrednu rediw a rof tub ,gnidaer deriuqer lla ta ton era esehT .stneduts 113H dna 125 rof deriuqer era sresaetniarb ,lausu sA rof enil s’reterpretni ruoy rof yaw siht ni esu tsum uoy ,eroferehT tnemelpmi nac uoy ,tnemnorivne eht no eldnah a evah uoy nehw ,revewoH sa fo noisnapxe eht nees evah yam uoY .lanoitisopmoc eb dluohs snoitulos ruoy ,rebmemeR . dna, ,, , ,noitacilppa ,noitcartsba-adbmal ,selbairav ,snaeloob ,srebmun :smrof gniwollof eht eldnah tsum reterpretni ruoY
.snoisserpxe .thgir nwo sti ni
.
:srepleh dna serudecorp ruoy eman dluohs uoy woh rof krowemarf a si sihT .erutcel ni detneserp esoht morf tnereffid eb yam seman eseht ecitoN .ssalc ni detartsnomed noitatneserper eht eb dluohs serutcurts
atad ruoY . srepleh larutcurts-atad htiw noisrev eht dna , lanoitcnuf htiw noisrev eht , noisrev tnedneped-noitatneserper eht llaC
srepleh
.savnaC ot ti timbus dna deman elfi a ni rof edoc ruoy ecalP .erofeb nees t’nevah uoy taht egaugnal a rof reterpretni wen a stnemelpmi 2 traP .reterpretni dr3 dna dn2 eht rof srepleh stnemnorivne fo stes tnereffid owt eht htiw gnola ,erutcel ni detneserp sreterpretni eerht eht :sreterpretni 3 tnemelpmi lliw ew ,1
traP gniruD .sreterpretni tnemelpmi lliw ew ,tnemngissa siht nI . dna , , srepleh eht rof snoitatneserper tnereffid owt nettirw evah ew ,tcaf nI .stnemnorivne ot tcepser htiw tnednepedni noitatneserper ti ekam ot denrael osla evah eW .noisserpxe taht gnitaulave fo tluser eht snruter dna noisserpxe tekcaR a sekat taht reterpretni na etirw ot woh denrael ev’ew ,serutcel tnecer nI
.esufoebot]wua2g3thj5u0v2hj09zcidb9hqfw6l9t/s/moc.xob.ui//:sptth[ ecnednepedni noitatneserper no setoN gniwollof eht dnfi yam uoy ,tnemngissa siht no deecorp uoy sA
.epyt atad eht ni noitarepo rehtona tsuj si margorp a fo noitaulave ;epyt atad xelpmoc a tsuj ,yllacitnames ,si egaugnal gnimmargorp a taht noitisop eht ekat ew ,egaugnal gnimmargorp elpmis a tsuj si epyt atad a taht egada eht gnitrevnI
stnemnorivnE dna sreterpretnI :1 traP
tnemngissA
setoN
> (value-of
‘((lambda (x) (if (zero? x)
#t #f))
0)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
#t
> (value-of
‘((lambda (x) (if (zero? x)
12
47))
0)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
12
> (value-of
‘(let ([y (* 3 4)])
((lambda (x) (* x y)) (sub1 6)))
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
60
> (value-of
‘(let ([x (* 2 3)])
(let ([y (sub1 x)])
(* x y)))
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
30
> (value-of
‘(let ([x (* 2 3)])
(let ([x (sub1 x)])
(* x x)))
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
25
> (value-of
‘(let ((! (lambda (x) (* x x))))
(let ((! (lambda (n)
(if (zero? n) 1 (* n (! (sub1 n)))))))
(! 5)))
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
80
> (value-of
‘(((lambda (f)
(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n))))))
(lambda (f)
(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n)))))))
5)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
120
> (value-of-fn
‘((lambda (x) (if (zero? x)
#t
0)
(empty-env-fn))
#t
> (value-of-fn
‘((lambda (x) (if (zero? x)
12
#f))
0)
(empty-env-fn))
12
> (value-of-fn
‘(let ([y (* 3 4)])
((lambda (x) (* x y)) (sub1 6)))
(empty-env-fn))
60
> (value-of-fn
‘(let ([x (* 2 3)])
(let ([y (sub1 x)])
(* x y)))
(empty-env-fn))
30
> (value-of-fn
47))
.]fdp=epyt&1per=per&7148.461.1.1.01=iod?daolnwod/codweiv/ude.usp.tsi.xreesetic//:ptth[
value-of-ds closures apply-closure-ds make-closure-ds value-of-ds
begin
value-of set! begin2 begin2 set!
‘(let ([x (* 2 3)])
(let ([x (sub1 x)])
(* x x)))
(empty-env-fn))
25
> (value-of-fn
‘(((lambda (f)
(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n))))))
(lambda (f)
(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n)))))))
5)
(empty-env-fn))
120
> (value-of-ds
‘((lambda (x) (if (zero? x)
#t
0)
(empty-env-ds))
#t
> (value-of-ds
‘((lambda (x) (if (zero? x)
12
0)
(empty-env-ds))
12
> (value-of-ds
#f))
47))
‘(let ([y (* 3 4)])
((lambda (x) (* x y)) (sub1 6)))
(empty-env-ds))
60
> (value-of-ds
‘(let ([x (* 2 3)])
(let ([y (sub1 x)])
(* x y)))
(empty-env-ds))
30
> (value-of-ds
‘(let ([x (* 2 3)])
(let ([x (sub1 x)])
(* x x)))
(empty-env-ds))
25
> (value-of-ds
‘(((lambda (f)
(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n))))))
(lambda (f)
(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n)))))))
5)
(empty-env-ds))
120
> (value-of
‘(* (begin2 1 1) 3)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
3
> (value-of
.selbairav setatum fo tnairav a si erehw , dna
dna ,stnemugra owt yltcaxe sekat taht s’tekcaR troppus ot reterpretni ruoy dnetxE .5
rof dna
etirW .reterpretni siht rof snoitcnuf repleh erusolc wen owt etirw dluohs uoY .tnednepedni noitatneserper ruoy ekam dna tniop gnitrats a sa esu ,tnemngissa eht fo trap siht roF
.
sresaetniarB
serusolC:II traP
‘((lambda (a)
((lambda (p)
(begin2 (p a)
a))
(lambda (x) (set! x 4))))
3)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
3
> (value-of
‘((lambda (f)
((lambda (g)
((lambda (z) (begin2
(g z)
z))
55))
(lambda (y) (f y)))) (lambda (x) (set! x 44)))
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
55
> (value-of
‘((lambda (x)
(begin2 (set! x 5) x))
6)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
5
> (value-of
‘(let ((a 3))
(begin2 (begin2 a (set! a 4)) a))
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
4
> (value-of
‘((lambda (x)
(begin2
((lambda (y)
(begin2
(set! x 0)
98)) 99)
x)) 97)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
0
> (value-of
‘((lambda (y)
(let ((x (begin2
(set! y 7)
8))) (begin2
(set! y 3)
((lambda (z) y)
x))))
4)
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
3
> (value-of
‘(let ((a 5))
(let ((y (begin2 (set! a (sub1 a)) 6)))
(begin2
(* y y)
a)))
(lambda (y) (error ‘value-of “unbound variable ~s” y)))
4
(define value-of-lex
(lambda (exp env)
(match exp
[`(const ,expr) expr]
[`(mult ,x1 ,x2) (* (value-of-lex x1 env) (value-of-lex x2 env))]
.ecneuqesnoc ralucitrap on fo era esehT .egaugnal eht fo xatnys eht ni snoitairav thgils rehto wef a era erehT .stnemnorivne ot tcepser htiw tnednepedni -noitatneserper si reterpretni siht ecitoN .)selbairav fo daetsni sesserdda lacixel gnisu snoisserpxe suluclac-adbmal .e.i( suluclac-adbmal eht fo noisrev dezinjiurBed a rof reterpretni gniwollof eht redisnoC .6
> (value-of-lex ‘((lambda (var 0)) (const 5)) (empty-env-lex))
5
apply-env-lex extend-env-lex
should
value-of-lex
not use lambda empty-env-lex
c5
> (define c0 (lambda (f) (lambda (x) x)))
> (define c5 (lambda (f) (lambda (x) (f (f (f (f (f x))))))))
> ((c5 add1) 0)
5
> ((c0 add1) 0)
0
> (define c+ (lambda (m)
(lambda (n)
(lambda (a) (lambda (b) ((m a) ((n a) b)))))))
> (let ((c10 ((c+ c5) c5)))
((c10 add1) 0))
10
c+
csub1
m
m
> (((csub1 c5) add1) 0)
4
> (((csub1 c0) add1) 0)
0
[`(zero ,x) (zero? (value-of-lex x env))]
(`(sub1 ,body) (sub1 (value-of-lex body env)))
(`(if ,t ,c ,a) (if (value-of-lex t env) (value-of-lex c env) (value-of-lex a env)))
(`(var ,num) (apply-env-lex env num))
(`(lambda ,body) (lambda (a) (value-of-lex body (extend-env-lex a env))))
(`(,rator ,rand) ((value-of-lex rator env) (value-of-lex rand env))))))
(define empty-env-lex
(lambda () ‘()))
cvm yb 64:61 21/90/0202 :defiidom tsaL ¡¤ txt.3-tnemngissa
.]0582600bFBF2%7001.01/retpahc/moc.regnirps.knil//:ptth[ tsitned eht ot pirt a gnikat redisnoc ,hguoht pleh thgim ti kniht uoy fI .ti elgooG t’nod os ,nuf s’ti tub ,melborp tlucffiid a saw sihT
.srebmun evitagen fo noiton a t’nevah ew sa ,orez si orez hcruhC fo rossecederp hcruhC eht ,esac dnoces eht nI
.ssap dluohs stset gniwollof ehT .rossecederp hcruhC , tnemelpmi ot si ,revewoh ,ksat ruoY
.n + m fo gninaem eht si tluser eht os ,semit m pu tnuoc lliw taht gniht fo tros eht si .tnemugra dnoces sti rof gninaem eht ti sedivorp ,orez rof gninaem eht fo daetsni ,dna 1dda rof gninaem eht ot sedivorp sesu ,orez rof gninaem a dna 1dda rof gninaem a dedivorp nehw ,taht noitcnuf a snruter ,slaremun hcruhC owt dedivorp nehw ,ti taht si fo noitinfied eht dnatsrednu ot yaw enO
.slaremun hcruhC revo noitidda smrofrep hcihw ,sulp hcruhC rof noitinfied a si gniwollof ehT
.5 rof laremun hcruhC eht fo noitinfied eht si ,ecnatsni roF .meht revo citemhtira dna ,slaremun hcruhC dellac ,srebmun larutan fo noitatneserper a enfied ot desu eb nac suluclac adbmal ehT .7
.srepleh ruoy tset nac ew taht os ,elfi ruoy ot dna dda ot erus ekaM .atad dab eldnah ot deriuqer ton era uoy ,reve sA .
yeht ,tcaf ni ;trohs eb dluohs snoitinfied ruoY . dna enfieD
.stnemnorivne fo noitatneserper erutcurts-atad a gnisu er’ew ees nac eno llac gniwollof eht morF
tresseD tsuJ