Assignment 4: Store-Passing Style
values
1
filter*
match-let values let-
To implement SPS, you will use values [http://docs.racket-lang.org/reference/values.html? q=values#%28def._%28%28quote._~23~25kernel%29._values%29%29] and let-values [http://docs.racket- lang.org/reference/let.html?q=let-values#%28form._%28%28quote._~23~25kernel%29._let-values%29%29]. Consult lecture notes or office hours if you forget how these work.
1 filter
filter*-sps
filter-sps
filter-sps
Show pagesource
Log In
partition
> (filter-sps even? ‘(1 2 3 4 5 6 7 8 9 10) ‘())
(2 4 6 8 10)
(1 3 5 7 9)
> (filter-sps odd? ‘(1 2 3 4 5 6 7) ‘())
(1 3 5 7)
(2 4 6)
> (filter-sps (lambda (x) (or (> x 6) (< x 2))) '(1 2 3 4 5 6 7) '())
(1 7)
(2 3 4 5 6)
(define filter*
(lambda (f ls)
(cond
[(null? ls) '()]
[(list? (car ls))
(cons (filter* f (car ls)) (filter* f (cdr ls)))]
[(f (car ls)) (cons (car ls) (filter* f (cdr ls)))]
[else (filter* f (cdr ls))])))
> (filter* even? ‘(1 2 3 4 5 6))
(2 4 6)
> (filter* odd? ‘(1 (2 3 (4 5)) 6 7))
(1 (3 (5)) 7)
> (filter* (lambda (x) (or (even? x) (< 7 x))) '(1 (2 3 (4 5)) 6 7 ((8 9) 10)))
((2 (4)) 6 ((8 9) 10))
.hcae fo erutcurts eht sevreserp dna stsil peed no skrow tub , sa noitcnuf emas eht smrofrep taht noitcnuf a ecudorP
:swollof sa stsil peed )yllaitnetop( no retlfi smrofrep hcihw noitcnuf a redisnoC
.taht yltcaxe seod taht tnemelpmI .etaciderp a no desab tupni eht dluoc ew ,yaw tahT .su ot kcab dednah osla erew tsil eht morf devomer stluser eht fo lla fi lufesu
eb dluow tI .]1-tnemngissa=di?php.ukod/113c/bup-igc/ude.anaidni.sc.www//:sptth[ 1 tnemngissa morf llaceR
.debircsed scitnames tcerroc eht evah yeht taht hcus elyts gnissap-erots otni woleb snoitcnuf eht mrofsnart ot si ksat ruoY
.ylralimis etarepo esehT .
dna gnisu eb ll'ew ,krowemoh ruoy nO .SPS tnemelpmi ot ssalc ni dna stsil desu eW
.]txt.remirp/crs/gro.yksfortep//:ptth[ enasni yldlim eht rof selur xatnyS yrt ,taht retfa erom rof yrgnuh llits er'uoy fI .]fdp.selur-xatnys/selehcim~/ude.ttip.tsayhp.www//:ptth[ cirtnecce ylerem eht rof selur xatnyS hguorht kool ylbaborp dluohs uoy ,sorcam roF ._segaugnaL gnimmargorP fo slaitnessE_ tlusnoc osla dluoc uoy ,SPS roF
.woleb slairotut orcam eht tlusnoc thgim uoy dna ,keew siht ssalc morf lairetam SPS dna sorcam eht fo esu ekaM noitcudortnI
.tekcop eht tfel ti sa ,dekaeuqs ti ”?uoy era oo' ,erE' “ .noitpecxe on saw siht dna ,feihcsim eht era sesrup 'sllorT
SPS 1 traP tnemngissA
> (filter*-sps even? ‘(1 2 3 4 5 6) ‘())
(2 4 6)
(1 3 5)
> (filter*-sps odd? ‘(1 (2 3 (4 5)) 6 7) ‘())
(1 (3 (5)) 7)
((2 (4)) 6)
> (filter*-sps (lambda (x) (or (even? x) (< 7 x))) '(1 (2 3 (4 5)) 6 7 ((8 9) 10)) '())
((2 (4)) 6 ((8 9) 10))
(1 (3 (5)) 7 (()))
2
and* list* match
syntax-rules and list*
(expand
3. and* and
.
fib-sps
> (fib-sps 0 ‘())
0
((0 . 0))
> (fib-sps 1 ‘())
1
((1 . 1))
> (fib-sps 3 ‘())
2
((3 . 2) (2 . 1) (0 . 0) (1 . 1))
> (fib-sps 10 ‘())
55
((10 . 55)
(9 . 34)
(8 . 21)
(7 . 13)
(6 . 8)
(5 . 5)
(4 . 3)
(3 . 2)
(2 . 1)
(1 . 1)
(0 . 0))
(syntax datum
> (syntax->datum (expand ‘(cond (#t #f) (else 7))))
(if ‘#t (let-values () ‘#f) (let-values () ‘7))
> (and* 1 2 3)
3
> (and* #f)
#f
> (and*)
#t
> (and* ‘a)
a
> (and* #t #t #t #t #t #t #t #t #f)
#f
.otsdnapxeorcamatahweesot]lmth.smroF_leveL-poT_gnidnapxE/ecnerefer/gro.gnal-tekcar.scod//:ptth[ereh dnuof seitilitu eht fo emos ro ,bal/ssalc ni evah thgim ew sa dna
→
,tekcaRrD ni reppets orcam eht esu nac uoy ,smelborp gniwollof eht no krow uoy sA :etoN .snoitulos ruoy ni esu t’nod ,oslA .snoitatnemelpmi ruoy ni
tekcaR otni tliub ew sa ,sorcam
dna
eht esu ot elbatpecca ton si ti ,smelborp dna eht roF .ssalc ni etorw ylno esu ot erus ekam ,snoitseuq gniwollof eht roF .sorcam emos tnemelpmi s’teL
.snoitatupmocbus eht lla evah uoy taht dna ,snoitatupmocbus yna gnitacilpud ‘tnera uoy taht erusne ,tcerroc si margorp ruoy erusne ot tuB .elbatpecca si tahT .redro siht ylesicerp ni tnirp ton yam erots ruoy ,noitatnemelpmi ruoy nopu gnidnepeD
)stluser eht yfiralc ot ylpmis si siht ,ylticilpxe eht htiw nettirw era woleb srewsna ehT( .swollof sa noitaziomem rof erots eht sesu taht tnemelpmI.noitatupmocpudeepsyltaergnachcihw,stluserfo]noitaziomeM/ikiw/gro.aidepikiw.ne//:ptth[
noitaziomem si egasu hcus enO .smargorp ni ycneicffie retaerg rof elyts gnissap-erots tiolpxe ot elbissop si tI
. s’tekcaR ot ylralimis krow dluohs sihT
sorcaM 2 traP
4. list* list*
5.
list*
(raise-syntax-error “Incorrect argument-count to list*”) list*
> (list* ‘a ‘b ‘c ‘d)
(a b c . d)
> (list* ‘a)
a
6.
list
if
macro-list
else
> (define list (lambda a a))
> (list 1 2 3 4)
> (copy-code (lambda (x) x))
cond
list
> (macro-list)
()
> (macro-list 1 ‘b 2 ‘d)
(1 b 2 d)
map
if
mcond
> (mcond
(#f #t)
(else ‘dog))
dog
> (mcond
(else ‘cat))
cat
> (mcond
(#t #t)
(unbound variables))
#t
> (cond (#t ‘a ‘b ‘c))
c
> (cond
(#f ‘a-thing)
(#f)
(‘turtle)
(else ‘rock))
turtle
> (cond
((member ‘a ‘(d a g w o o d)) => length)
(else ‘not-a-member))
6
7.
> (map (lambda (x) (list x x)) ‘(a b c))
((a a) (b b) (c c))
> (define-syntax copy-code
(syntax-rules ()
[(_ x) `(,x x)]))
.dliwgoh og neht uoy sekirts doom eht fi tub ,roivaheb siht tnemelpmi ot deriuqer t’nera uoY .cte ,esualc a ni seidob elpitlum
,noitaton ⇒ ,sesualc tnemele-eno rof troppus gnidulcni ,roivaheb artxe fo laed doog a sah tekcaR dradnatS
.sesualc rof tnemtaert etairporppa eht edivorp ot erus ekaM .s detsen fo seires a ot sragused tub ,dnoc ekil stca hcihw orcam na etirW .stnemetats fo seires a sa dnoc taert nac ew taht wonk eW
.meht fo tsil a sdliub dna stnemugra fo rebmun yna sekat hcihw , tnemelpmI .orcam evisrucer a sa detnemelpmi saw ,daetsnI .snoitcnuf cidairav on erew ereht ,psiL fo syad ylrae eht ni tuB .noitcnuf eht ot retemarap lamrof eht dnuora sesehtnerap fo ecnesba eht etoN
.sadbmal )yra-n( _cidairav_ gnisu tekcaR ni noitcnuf a sa ylpmis detnemelpmi eb nac noitcnuf tekcaR ehT tsil-orcam
. s’tekcaR ot ylralimis etarepo dluohs rewsna :gnillac yb rorre na troper dluohs orcam ruoy ,stnemugra on htiw dellac nehW .tnemugra taht nruter ylpmis dluohs ti ,dessap si tnemugra elgnis
ruoY .
a fI .tsil reporpmi na nruter dluohs ,tsil a ton si tnemugra lanfi eht fI .stnemugra sti rehtegot se-snoc
:orcam a htiw esu tonnac ew taht ecitoN .pam-orcaM
dnocm
(#
> (copy-code ‘a)
(a ‘a)
> (map copy-code ‘(a b c))
stdin::167: copy-code: bad syntax
in: copy-code
context…:
macro-map
> (macro-map quote ‘((trinidad and tobago) (saint vincent and the grenadines) (antigua and barbuda)))
((trinidad and tobago)
(saint vincent and the grenadines)
(antigua and barbuda))
> (macro-map copy-code ‘((lambda (x) x) (lambda (x) (+ 2 x)) (lambda (x) 7)))
((#
(#
(#
> (define-syntax quote-quote
(syntax-rules ()
[(_ e) (quote (quote e))]))
> (macro-map quote-quote ‘((trinidad and tobago) (saint vincent and the grenadines) (antigua and barbuda)))
(‘(trinidad and tobago)
‘(saint vincent and the grenadines)
‘(antigua and barbuda))
8.
condre cond
cond
(define proc-list
(lambda (ls)
(cond
((null? ls) ‘())
(else ;; This part here.
(let ((a (car ls)))
(cond
((number? a) (cons (even? a) (proc-list (cdr ls))))
((boolean? a) (cons a (proc-list (cdr ls))))
(else (cons #f (proc-list (cdr ls))))))))))
> (condre
(let ((a 5))
((number? a) #t)
(else #f)))
#t
> (define proc-list
(lambda (ls)
(condre
let* letrec letrec*
((null? ls) ‘())
(let ((a (car ls)))
((number? a) (cons (even? a) (proc-list (cdr ls))))
((boolean? a) (cons a (proc-list (cdr ls))))
(else (cons #f (proc-list (cdr ls))))))))
> (proc-list ‘(#t 2 3 #f ‘dog))
(#t #t #f #f #f)
.worra na fo edis dnah-thgir eht no ydob eno naht erom dna ,seidob erom ro 1 ,⇒ , , , rof troppus dedda ,erdnA gnieb ,erdnA
.) s’erdnA rof( retnE .kuY .noitatnedni wen a rednu dnoc wen a trats neht ,gnidnib-tel a ecudortni ,esle na dda ot evah I tub ,kcolb dnoc eno fo trap lla eb ot ti tnaw yllaer I .tnenopmoc dnoc-tel-esle taht si noitnetta ruoy tcerid ot tnaw I hcihw ot trap ehT
eht ekil gnihtemos od ot dah uoy evah semit ynam woh ,ecnatsni roF .
:gniwollof ot snoitatimil etanutrofnu emos era erehT
.orcam a pam ot su orcam a enfied s’tel ,melborp siht dnuora teg oT .etalpmet wen emos otni nrettap a fo sehctam morf dednapxe eb ot evah yeht ,daetsnI .rennam taht ni noitcnuf a ot stnemugra sa dessap eb tonnac sorcaM
wolla lliw hcihw ,
erdnoc tresseD tsuJ
.keew siht seirrow oN .dettimO resaetniarB
condre
syntax-rules
> (condre
(#f)
(letrec ((ls? (lambda (ls)
(condre
[(null? ls) #t]
[(pair? ls) (ls? (cdr ls))]
[else #f]))))
((ls? ‘(1 2 3 . 4)) #f)
((ls? ‘(1 2 3 4)) => (display ‘Should-be-seven->) (lambda (t) (set! t 7) t))
(else #f)))
Should-be-seven->7
cvm yb 53:51 60/20/0202 :defiidom tsaL · txt.sps
.gnihctam nrettap htiw deen ll’uoy stset eht fo emos od ot yrekcirt voylesiK/yksforteP eht fo emos dna ,sorcam elyts-rotalumucca spahrep ,sorcam gnissap-noitaunitnoc deen ll’uoY .gnikeep fo muminim a htiw ti od nac uoy fi nuf erom s’ti tub ,siht od ot woh swohs taht tnemucod a evah ydaerla uoY .margorp eht fo noitaulave eht detelpmoc evah ll’uoy ,dehsinfi si noisnapxe orcam emit eht yb ,si tahT .orcam a sa reterpretni eht tnemelpmi gnikeep tuohtiw ro htiW
?uoy od , dnarb-ffo na htiw dnuora gniklaw eb annaw t’nod uoy tuB .od ot dellepmoc leef uoy sa siht fo hcum sa tsuj edulcni nac uoy os ,nuf rof tsuj si siht ,ylsuoivbO
tressed sunob artxE