计算机编程与数据课件

计算机编程与数据WaystoDesignProgramsThinkaboutwhatyouwanttodo,andturnthatintocode.Thinkaboutwhatyouneedtorepresent,anddesignyourcodearoundthat.Whichisbetter?HistoryofSchemeScheme[GuySteele&GerrySussman,1975]GuySteeleco-designedSchemeandcreatedthefirstSchemeinterpreterforhis4thyearprojectMorerecently,SteelespecifiedJava[1995]“Conniver”[1973]and“Planner”[1967]BasedonLISP[JohnMcCarthy,1958]BasedonLambdaCalculusAlonzoChurch,1930sLastfewlecturesincourseLISP“LotsofInsipidSillyParentheses”“LISt

Processinglanguage”Listsareprettyimportant–hardtowriteausefulSchemeprogramwithoutthem.MakingLists（列表）MakingaPair>(cons12)(1.2)consconstructsapair12SplittingaPair>(car(cons12))1>(cdr(cons12))2carextractsfirstpartofapaircdrextractssecondpartofapair12carcdrWhy“car”and“cdr”?Original(1950s)LISPonIBM704Storedconspairsinmemoryregisterscar=“ContentsoftheAddresspartoftheRegister”cdr=“ContentsoftheDecrementpartoftheRegister”(“could-er”)Doesn’tmatterunlessyouhaveanIBM704Thinkofthemasfirstandrest(definefirstcar)(definerestcdr)(TheDrScheme“PrettyBig”languagealreadydefinesthese,buttheyarenotpartofstandardScheme)Implementingcons,carandcdr(define(consab) (lambda(w)(ifwab)))(define(carpair)(pair#t)(define(cdrpair)(pair#f)Schemeprovidesprimitiveimplementationsforcons,car,andcdr.But,wecoulddefinethemourselves.Pairsarefine,buthowdowemakethreesomes?Triple（三元组）

Atripleisjustapairwhereoneofthepartsisapair!(define(tripleabc)(consa(consbc)))(define(t-firstt)(cart))(define(t-secondt)(car(cdrt)))(define(t-thirdt)(cdr(cdrt)))Quadruple（四元组）

Aquadrupleisapairwherethesecondpartisatriple(define(quadrupleabcd)(consa(triplebcd)))(define(q-firstq)(carq))(define(q-secondq)(t-first(cdrt)))(define(q-thirdt)(t-second(cdrt)))(define(q-fourtht)(t-third(cdrt)))Multuples

（多元组）AquintupleisapairwherethesecondpartisaquadrupleAsextupleisapairwherethesecondpartisaquintupleAseptupleisapairwherethesecondpartisasextupleAnoctupleisgroupofoctupiA?isapairwherethesecondpartisa…?ListsList::=(consElement

List)Alistisapairwherethesecondpartisalist.Onebigproblem:howdowestop?Thisonlyallowsinfinitelylonglists!ListsList::=(consElement

List)List::=Alistiseither:apairwherethesecondpartisalistor,emptyIt’shardtowritethis!NullList::=(consElement

List)List::=Alistiseither:apairwherethesecondpartisalistor,empty(null)nullListExamples>null()>(cons1null)(1)>(list?null)#t>(list?(cons12))#f>(list?(cons1null))#tMoreListExamples>(list?(cons1(cons2null)))#t>(car(cons1(cons2null)))1>(cdr(cons1(cons2null)))(2)RecapAlistiseither:apairwherethesecondpartisalist ornull(note:bookusesnil)Pairprimitives:(consab) Constructapair<a,b>(carpair) Firstpartofapair(cdrpair) SecondpartofapairProblemSet2:

（课后作业）ProgrammingwithDataRepresentingacardcarcdrPairofrank(Ace)andsuit(Spades)ProblemSet2:

（课后作业）ProgrammingwithDataRepresentingaca