2020/2/19 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 1/12
.ylgukooledocruoyekamnac,gnisusiredarg ruoyrotidehcihwnognidneped,dnasrotidetnereffidrednuyltnereffidpuwohsyehtesuaceb sbatgnisudiovaoslA.elbadaertxetmargorpruoyekamotnoitatnedniesutsumuoydnasenil gnolylevissecxeevahtontsumuoy:noitatneserpseodoslaoS.rettamodsmargorpruoyfoytilauq dnaerutcurtsehttahtralucitrapnietoN.gnidargnehwredisnocewseussiehtdnaskrowemoh roflocotorpehtnostnemmocehtdaeroterusekam,krowemohehtnognikrowtratsuoyerofeB
.melborp hcaerofdedeensatuomehtgnillfinidetratstegdnayrotisoperetavirpruoyfonoisrevlacoleht niecalpthgirehtotrevotiypoc,oper-cilbupfoypoclacolruoynognillupybtuoredlofsihtkcehC .esruoc eht rof yrotisoper cilbup eht ni redlof swh eht nihtiw redlof 2wh eht ni lm.6borp hguorht lm.1borpdemanselfinoteleksdedulcnievahew,locotorpdebircsedehtgniwollofniuoyplehoT
.krowruoyroftiderctegtonlliwuoytahtosla gninaem,noitulosuoyedargotelbaebtonlliwewdnanoissimbusruoynoliaflliwslootdetamotua ruo,tnemeriuqersihttcepsertonoduoyfI.mehtotdengissaevahewtahtsepytdnaseman ehtotyltcirtserehdatsumetirwotdeksaeraruoytahtsnoitcnufyna:dessertsebdluohstaht tnioplarenegenO.wolebsnoitpircsedmelborplaudividniehtdedivorperaniatnocotselfieseht fohcaetcepxeewtahwfosliatedrehtruF.ylevitcepser,6hguorht1smelborPotsnoituloseht niatnoc hcihw lm.6borp hguorht lm.1borp deman selfi xis niatnoc dluohs redlof siht ,krowemoh siht otcfiicepS.redlofswhehtnihtiwflestisitaht2whdemanredlofanihtiwesruocsihtrofyrotisoper buhtigetavirpruoynikrowruoyeesotgnitcepxeeraew,denialpxeylsuoiverpevahewsA
2 krowemoH
atosenniM fo ytisrevinU ,0202 gnirpS selpicnirP gnimmargorP decnavdA :1402 ICSC
locotorP noissimbuS
thgindim yb 0202 ,12 beF :euD 0202 ,6 beF :detsoP
2020/2/19 CSCI 2041, Advanced Programming Principles
append sumlist
zip
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 2/12
.etats uoynoisulcnocehthcaerotssalcnidessucsidewsaecnerefniepyt/gnikcehcepytfossecorp ehthguorhtogtsumuoY.noitseuqehtotrewsnaetauqedanaetutitsnoctonlliwflestiybsihttaht etontubgnipytdnasnoitinfiedehttuobasnoitiutniruoykcehcotlmaCOesuesruocfoyamuoY
.rorreepytehtnistlusertahttciflnocehtwohsnehtdnaepyt arefniotgniyrtfossecorpehthguorhtog,sdrowrehtoni;simelborpehttahwyletelpmocdna ylraelcnialpxe,depyt-llewtonsitifI.ssalcnidnarofdidewsadenimretedsiepyt sihthcihwybspetsehthguorhtylticilpxeogdnaepytehtetacidni,depyt-llewsitifI.depyt-llewsi titahtenimretedlliwlmaCOrehtehwetacidni,wolebsnoitinfiednoitcnufdetroprupehtfohcaeroF
.yllacitamotua deeccus dluohs segrem hcus,elfiylno-daerasatitaertuoy.e.i,flesruoyelfikcabdeefehtyfidomtonoduoysagnolsA .hsupotyrtnehtylnodnaegremaekam,yrotisoperruoymorfllupotdeenlliwuoy,sneppahsiht fI.liaflliwtimmocruoydnatciflnocaretnuocnelliwuoyneht,hsuprehtonaekamotgniyrterofeb kcabdeefehtlluptonoduoyfitahtsietonottniopdnocesehT.yrotisoperehtgnihsuperofeb redlofehtniselfiruoyfoenooterehwemosecapsetihwlaitneuqesnocniemosgnidda,elpmaxe rof,ybsihtodnacuoY.kcabdeefehtreggirtotredroniredlofehtfostnetnocehtsegnahc yllautcatahtyawaniretalniagatihsupotevahlliwuoy,emittahterofebkrowemohruoydehsup uoyfI.delbaneneebsahtpircsehtretfa2wh/swhrednuselfiehtstceffatahttimmocahsupuoy nehwylnodetaerceblliwelfikcabdeefeht,tsriF:gnitaeperraebtahtstnioptnatropmifoelpuocA
.krow ruoyotnevigebottidercehtgninimretednienimaxelliwredargehttahtedocruoyfostcepsa rehto osla era ereht dna sesac tset terces emos timo lliw tpircs ruo :msinahcem kcabdeef siht no hcumootylertontsumuoy,erofebdenialpxeevahewsa,tahtetoN.kcabdeefdetadpueviecerot niagallupdna,elihwelttilatiaw,yrotisoperruoyotniagahsupdluohsuoy,sekatsimynagnitcerroc retfA.titcerrocotwoh,yllufepoh,dnasieruliafehttahwdnatsrednuuoyplehdluohsswolloftaht txetehT.edocruoynidnikemosfoseruliafetacidnisenilesehT.”:liaF+”gnirtsehthtiwnigebtaht tinisenilrofkooldnatinepo,lluparetfayrotisoperruoynisraeppadm.kcabdeeF_2whelfiehtfI
.emitretalatagnillupnehtdnagnihsupfossecorpehttaeperdluohsuoyosdna evitcateytonsitpircsehttahtnaemdluowti,detaercneebtonsahelfisihtfI.detaercneebsah dm.kcabdeeF_2whdellacelfiafikcehcdna,yrotisoperruoymorfllup,)etunimatuoba(elihwelttil a tiaw ,yrotisoper ruoy ot gnihsup retfA .yrotisoper ruoy ot nettirw eb lliw hcihw tuptuo etareneg lliwtpircssihT.noitulosasahsupuoytahwnotpircskcabdeefehtelbanelliwew,enildaed noissimbusehterofebyadehtnognitratS.1krowemohrofsaemasehtsikcabdeefsihtgnittegrof ssecorpehT.krowruoynokcabdeefevitsuahxe-non,yranimilerpuoygnivigtademiakrowemoh sihtnirofdeksasmargorpehtnostsetnurlliwtahtstpircsetirwlliwew,1krowemohhtiwsA
noitcnufehtenfiedottpmettanasisihT.1
)stniop 3 + 3( 1 melborP
ssecorP kcabdeeF yranimilerP ehT
2020/2/19 CSCI 2041, Advanced Programming Principles
let rec zip lp =
match lp with
| ([],_) -> []
| (_,[]) -> []
| ((x::l1),(y::l2)) -> (x,y) :: zip (l1,l2)
reverse
let rec reverse l =
match l with
| [] -> []
| (h::t) -> (reverse t) :: h
n = n0;
i = 1;
fib1 = 1;
fib2 = 1;
while (i != n) {
temp = fib1;
fib1 = fib2;
fib2 = fib2 + temp; i=i + 1
}
return fib1;
temp
fib’
fib’
fact reverse
fib’
fib : int -> int
n0
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 3/12
.rebmun orez-non ,evitisop a si tupni stitahtnoitidnocerpehtsahnoitcnufsihttahtemussA.tupnistifoicannobiFehtsetupmoc
taht noitcnufehtfonoitinfiedaetirw,noitcnufyrailixuanasagnisU.3
.defisitas si noitidnocerp eht nehw stupni eht ot tuptuo eht fo pihsnoitaler detcepxe eht noitidnoctsop ehtnisserpxeotdnanoitidnocerpehtnistupniehtneewtebpihsnoitaleraetalupitsoteb thgimsihtodotyawtsebehT.noitcnufehtfostupniehtotsituptuoehtfopihsnoitalereht
tahwyawesicerpyllacitamehtamaniebircsed, fonoitinfiedehterofebtnemmocehtnI.2
.tnemugranasaylticilpxetneserper otediceduoytonrorehtehwnognidneped,stnemugraevfiroruofevahdluohsnoitcnufeht :detratsuoytegottnihA.ssalcnismargorpdnaehthtiwrehtegotdessucsidew saedi eht wolloF . dellac noitcnuf a fo noitinfied evisrucer-liat a otni mrof siht etalsnarT
noisrevevitaretisihtgniwohsnilmaCO-oduespgnisueraew,ssalcnididewsa
; rebmunevitisopafoicannobiFehtetupmocotmargorpevitaretigniwollofehtredisnoC.1
)stniop 2 + 2 + 4( 2 melborP
.derewsnagniebtrapehtforebmunehtsiXerehw )* N traP ot noituloS *(
mrofenilehthtiwsnigebtahttrapdetacramedylraelcaniecalpebtsumtrap hcaeotsrewsnaeht,rehtruF.lm.1borpdemanelfianidedivorpebtsummelborpsihtotsnoituloS
noitcnuf aenfiedotgniyrteraewemitsihT.2
2020/2/19 CSCI 2041, Advanced Programming Principles
option
option
option
find_salary find_phno
(key1,data1) /\
/\ (key2,data2) (key3,data3)
/\/\ /\/\
(key4,data4) Empty Empty (key5,data5) …
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 4/12
yranibasisihtecnis,esruocfO.seertytpmeerasevaelehtdnaeertbusthgiradnatfelasahedon lanretnihcae,smetiatadehtdnayekehtdlohseerthcusfosedonlanretnieht,sdrowrehtonI
gniwollofehtsahcus erutcurtseertaotnidezinagroebnehtdluowesabatadehtninoitamrofniehT.rebmunenohp ehtdnayralasehtfognitsisnocelputaebyamatadehtdnaeeyolpmeehtfoemanehtebthgim xedniroyekeht,esabatadeeyolpmeehtni,elpmaxeroF.atadehtotxedniehtdellacnetfoosla siyekehT.yekehtotgnidnopserrocatadehtmroflliwsmetigniniamerehtdna,eertehtezinagro lliwewhcihwnodesabyekehtsatneserperottnawewselputehtfometienotuoetarapes lliweW.evoba3melborPdna1krowemoHfo6melborPnideredisnocewesabatadnosrep ehtsahcusesabatadatneserperoteerthcraesyranibagnisuredisnoclliwew,melborpsihtnI
].krow eht rof tidercgnittegroflaitnessesisihT.detacidniesohtotyltcirtserehdatsummelborpsihtnirofdeksa snoitcnufdnarotcurtsnocepytehtfosemanehttahtoslA.trapehtforebmunehtsiNerehW
eniltnemmoclmaCOehthtiwsnigebtahtelfieht fonoitcestcnitsidaniderewsnaebdluohshcihwfohcae,strapnevessahmelborpehT.elipmoc otelbaebtsumlmaCOtahtlm.4borpdemanelfianidedivorpebdluohsmelborpsihtotsnoituloS[
)stniop 6 + 4 + 5 + 3 + )2 + 2( + 1 + 5( 4 melborP
.melborp eht xfi ot debircsed evah uoy rennam eht ni eht sesutahtsnoitcnufowtehtfosnoitinfiedehtniatnocnehtdluohselfiehT.elfiehtfogninnigebeht tatnemmoclmaCOnaniraeppatsummelborpehtxfiotsplehepyt ehtwohfonoitanalpxe ehT.elipmocnaclmaCOtahtlm.3borpdemanelfianiraeppatsummelborpsihtotsnoituloS
.melborp eht emocrevo ot aedisihtgnisudnahtobenfiedernehT.epytehtgnisusihtxfinacuoy wohnialpxE.nosrepralucitraparofyrtnenaniatnoctondidesabatadehtnehwnoitautisehthtiw laedotwohtuobaemittahttasnoitseuqemoserewerehT.1krowemoHmorf6melborPtisiveR
.debircsedsayltcaxesnoitcnufowtehtemanotluferac eB.elipmocnaclmaCOtahtlm.2borpdemanelfianidedivorpebtsummelborpsihtotsnoituloS
)* N traP ot noituloS *(
)stniop 2 + 2 + 2( 3 melborP
2020/2/19 CSCI 2041, Advanced Programming Principles
(ty1,ty2) btree ty1 ty2
let tree1 = …
let tree2 = …
find : (‘a, ‘b) btree -> ‘a -> ‘b option
option
insert : (‘a, ‘b) btree -> ‘a -> ‘b -> (‘a, ‘b) btree
btree
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 5/12
epytdnaemangniwollofehtfonoitcnufaenfieD.5
.seert hcraes yranib htiw detaicossa tnairavniehtemussaylsuoivbodluohsuoynoitcnufsihtgninfiednI.yeknevigehtot gnidnopserrocyrtnenaniatnoctonseodeertehtesacnimrof ehtsahepytnruterehT .eertehtniyekrepyrtneenoyltcaxesierehttahtemussA.yekehtotgnidnopserroceerteht niderotseulavatadehtsnrutertahtdnatupnisayekadnaeerthcraesyranibasekattaht
epytdnaemangniwollofehtfonoitcnufaenfieD.4
.sgnirtsdnasregetninogniredrodradnatsehtgnisu tnemeriuqereerthcraesyranibehtyfsitasyehtfigninimretedybdnasepytriehttagnikool ybepytthgirehtfoeraedivorpuoysnoisserpxeehtfikcehclliwewtahtetoN.atadehtsa )yralasadnarebmunenohpagnitneserper(laeradnagnirtsadnayekehtsa)emannosrep agnitneserper(gnirtsaesueertdnocesehtnI.atadehtsagnirtsadnayekehtsaregetni naesu,eerttsrfiehtnI.eerthcraesyranibtnaveleragnitneserpernoisserpxeehtsi…erehw
mrof eht fo edoc evah dluohs uoy ,yllacfiiceps eroM.ataddnasyekfosdniktnereffidrevoseerthcraesyraniblaivirtnonowttneserper
otdedivorpevahuoysnoitaralcedepytehtsesutahtlmaCOnisnoisserpxeowtnwodetirW.3 .eertytpmeehtfognidocneehtoteerttinirefiitnediehtsdnibtahtgnidnibtelaedivorP.2
.ytreporp eht niatniamseerttuptuoynatahthcuseraetirwewsnoitinfiedehttahterusnedluohsewdna snoitcnufruoottupniseertehtroftnemeriuqerasaytreporpehtetalupitsdluohsew,sdrow rehtonI.etirwewsnoitcnufehthguorhtetalupinamdnatcurtsnocewseertehtfotnairavni naeblliwytreporpgniredrosiht,daetsnI.sihtodotgniyrtemitdnepst’nodos,seerthcraes rofytreporpgniredroehterutpacothguonegnortstonsimetsysepytlmaCOehT:etoN
eraewdnikehtfoseerttneserpertaht,dnasepytelbatiusrof, epytfosnoisserpxelmaCOnwodetirwotelbaebdluohsew,noitaralcedsihtdedivorpevah uoyretfA.evobanwohsmrofehtfoseerttneserperotdesuebnactahtsrotcurtsnoceulav detaicossadnaatadehtfoepytehtdnayekehtfoepytehtotgnidnopserrocstnemugra
foriapasekattaht dellacrotcurtsnocepytasefiitneditahtnoitaralcedepytaedivorP.1
.debircsedsaylevisrucersdlohytreporpsiht tahteton;edonehttayekehtnahtregraleraeertbusthgirehtnisyekehtdnaedonehttayekeht nahtrellamseratniopynataeertbustfelehtnisyekehttahthcussinoitazinagroeht,eerthcraes
.ni detseretni
2020/2/19 CSCI 2041, Advanced Programming Principles
keylist : (‘a, ‘b) btree -> (‘a list)
delete : (‘a, ‘b) btree -> ‘a -> (‘a, ‘b) btree
delete_root delete delete_root
=
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 6/12
.sihtodot sesudnadevomerebotedonehtsetacoltitaht os noitcnuf eht ezinagro nehT . noitcnuf siht dellac I ,edoc ym ni ;toor eht tasawtahwniatnoctonseodtahttimorfeertwenasecudorpdnaeertytpme-nonasekat
tahtnoitcnufaetirwtsriF.lufesuebyamnoitseggusa,trapredrahylthgilsasitiecniS:tniH
.ssalcnitissucsidewnehwnoitulosagnidnatsrednu rofuoyeraperplliwsiht,tohstsebruoytievig,revewoH.noitcafsitasruoyottievlosotelba tonerauoyfidegaruocsidtegtonodos,senosuoiverpehtnahttlucffiideromsitrapsihT .trapsihtrofedoclmaCOynaetirwotyrtuoyerofebnoitatupmocehtezinagrootwohtuoba ylluferacknihtos,noitulosruoyfoytilauqehttakoollliwew,edocruoyllahtiwsA:etoN
)2 + 51 + )2 + 2 + 2( ( 5 melborP
.ssecorp ehtniseerthcraesyranibroftnairavniehtniatniamotevahuoy,rebmemeR.devomer yeknevigehtotgnidnopserroctiniyrtneelbissopahtiweertdloehtotsdnopserroc tahteerthcraesyranibwenasnruterdnayekadnaeerthcraesyranibasekattaht
epytdnaemangniwollofehtfonoitcnufaenfieD.7
.syekehtfognitsilderedronagnicudorp fotluserehtsahtidnalasrevartredro-ninadellacsilasrevartfodniksihT.eertbus thgirehtnisyekehtnehtdnaedonatayekehtneht,detsileblliweertbustfelehtnisyek ehttsrfi:redrogniwollofehtnitinisyekehtfotsilaecudorpdnaeertehtesrevartlliwtaht
epytdnaemangniwollofehtfonoitcnufaenfieD.6
.snoitcnuf redro-rehgihtuobadeklatevahewretfa,stnemngissaerutufnitcepsasihtgnildnahfosyaw rettebfoknihtlliweW.edocruoyniyltceridmehtesunacuoy,.e.i,epytsihtnokrowlliw noitalerytilauqeehtosladna>dna
(* for exp1 && exp2 *)
(* for exp1 || exp2 *)
(* for not exp *)
(* for if exp1 then exp2 else exp3 *)
(* for let = exp1 in exp2 *)
(* for fun (x:ty) -> exp *)
(* for (exp1 exp2) *)
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 7/12
anisnoisserpxenoitacilppadnanoitcnuf,teledocneotelbaebwonlliwew,snoitiddaesehtgnisU .sesaceerhtesehtetadommoccaot)noitinfiedepytehtniesactsrfieht(srefiitnedifonoisulcni ehtosladnasesaceerhttsalehtfotahtsihguoht,noitiddagibyllaerehT.balehtnineesegaugnal noisserpxeehtotnisrotareponaeloobdnacitemhtirafotesregralasetaroprocninoitinfiedsihT
:gniwollof eht ot epyt eht rof noitaralced eht yfidom txen eW
.epytatadsihtgnisu ybdetneserpereblliwlmaCOnitni>-tnisa nettirwepytehtsuhT.sepytnoitcnuftneserperotesacwenaedulcnisierehenodevahewtahW
:gniwollofehtotsepytgnitneserper rofnoitaralcedepytehtegnahctsrfiew,noisnetxesihthtiwgnilaedroftxetnocehtetaercoT
.sesac eseht revocottnemtaertehtsdnetxemelborpsihT.snoitacilppanoitcnufdnasnoitcnuf,stelfosepyteht gnikcehcredisnoctonlliwewbalehtnI.tcerrocepytera,epytatadlmaCOnagnisudetneserper ,snoisserpxelmaCOtahtgnikcehc:5baLnieeslliwuoygnihtemosnosdliubmelborpsihT
].oper-cilbup morfelbaliavasitahtlm.5borpelfinoteleksehtniydaerladecalpneebsahsiht,ecneinevnoc ruoy roF .detrats teg ot noitpircsed melborp eht ni dedivorp noitaralced epyt eht deen lliw uoY
.krow eht rof tidercgnittegroflaitnessesisihT.detacidniesohtotyltcirtserehdatsummelborpsihtnirofdeksa snoitcnufdnarotcurtsnocepytehtfosemanehttahtoslA.trapehtforebmunehtsiNerehW
eniltnemmoclmaCOehthtiwsnigebtahtelfieht fonoitcestcnitsidaniderewsnaebdluohshcihwfohcae,strapeerhtsahmelborpehT.elipmoc otelbaebtsumlmaCOtahtlm.5borpdemanelfianidedivorpebdluohsmelborpsihtotsnoituloS[
)* N traP ot noituloS *(
2020/2/19 CSCI 2041, Advanced Programming Principles
((fun (x:int) -> x + 1) true) let x = true in x + 1
None
(Some Ty)
let exp1 = …
let exp2 = …
let exp3 = …
typeof_aux : expr -> (string * ty) list -> ty option
Ty
# typeof_aux (Not (Int 5)) [];;
– : ty option = None
# typeof_aux (Not True) [];;
– : ty option = Some BoolTy
# typeof_aux (Plus (Id “x”,Int 5)) [(“x”,IntTy)];;
– : ty option = Some IntTy
# typeof_aux (And (Id “x”,True)) [(“x”,IntTy)];;
– : ty option = None
# typeof_aux (Let (“x”,True,(Plus (Id “x”, Int 5)))) [];;
– : ty option = None
# typeof_aux (Let (“x”,Int 5,(Plus (Id “x”, Int 5)))) [];;
– : ty option = Some IntTy
# typeof_aux (Fun (“x”, BoolTy, And (Id “x”,True))) [(“x”,IntTy)];;
prob5.ml
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 8/12
:noitcnufsihtfosesuelpmaxeemoS.epytstifonoitatneserperasidnaelbaepyt si noisserpxe eht fi tluser eht ro elbaepyt ton si noisserpxe eht fi tluser ehtsnruterdnasnoitaicossaepytdnaemanrefiitnedifotsiladnanoisserpxenasekattaht
noitcnufehtenfied,noitatneserperahcusgnimussA .sriapepytdnaemanrefiitnedifotsilasatxetnocahcustneserperlliweW.sidnuob gniebelbairavehtfoepytehttahwuoysllettahttxetnocanitiodotevahuoy,noisserpxetel afoydobehtkcehcepytotgniyrtnehw,ylralimiS.sitnemugranoitcnufehtfoepytehttahw
uoysllettahttxetnocanitiodotevahuoy,noitcnufafoydobehtkcehcepytotgniyrtnehW.2 .noitatneserpertnavelerehthtiwnidellfisitrap…ehterehw
:gniwollofehtekilkooltahtsgnidnib teleerhtfomrofehtnielfi ruoynideniatnocebtsumsnoitatneserperesehT
5 ))x )y + x >- )tni:y( nuf(( >- )tni:x( nuf( .c ))5-x esle )1+x( neht y fi >- )loob:y( nuf( >- )tni:x( nuf( .b y + x ni 7 = y tel ni 5 = x tel .a
snoisserpxelmaCOgniwollofehtfo snoitatneserperehttneserP.melborpsihtninoitaralcedepytehtybdettimreperatahtsmrof
noisserpxewenehtfonoitatneserperehtdootsrednuevahuoytahterusekamtsrfisuteL.1
.depyt-lli sinoisserpxenanehwsulletoslalliwdnaevobastcurtsnocehtgnisudemrofsnoisserpxedepyt -llewfoepytehtsueviglliwtahtnoitcnuflmaCOnaenfiedotsimelborpsihtnilaoglautneveehT
.dna
snoisserpxeehtedocnenacew,elpmaxe roF.elbaepytebtonlliwedocnenacewtahtsnoisserpxeehtfoemoS.lmaCOekilegaugnal
2020/2/19 CSCI 2041, Advanced Programming Principles
– : ty option = Some (FunTy (BoolTy, BoolTy))
# typeof_aux (App (Fun (“x”,IntTy, Plus (Id “x”, Int 1)), Int 5)) [];;
– : ty option = Some IntTy
# typeof_aux (Cond (True, True, False)) [];;
– : ty option = Some BoolTy
# typeof_aux (Cond (True, Fun (“x”,IntTy,Id “x”), Fun (“y”,IntTy,Int 5))) [];;
– : ty option = Some (FunTy (IntTy, IntTy))
#
typeof_aux
typeof : expr -> ty option
(Some Ty) Ty
None Ty
Fun Let
type expr =
Id of string
| Int of int
| True
| False
| Plus of expr * expr
| Minus of expr * expr
(* for identifiers *)
(* for integers *)
(* for the boolean value true *)
(* for the boolean value false *)
(* for exp1 + exp2 *)
(* for exp1 – exp2 *)
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 9/12
lmaCO ni noitaralced epytgniwollofehtybderutpacsi,neht,takoollliwewtahtsnoisserpxefonoitcellocehT
.wonthgirrofderaperperaewtahwnaht detacilpmoceromtibasisnoisserpxehcushtiwlaedotwohgnidiceddna,sevlesmehtsnoisserpxe noitcnufebdluoctahtstluserredisnocotsueriuqertuotfelneebevahtahtsmrofnoisserpxe eht;melborpsuoiverpehtnidewollasnoisserpxefonoitcellocehtmorf,snoisserpxenoitacilppa dna noitcnuf .e.i ,sesac owt tsal eht tuo evael lliw ew ,yllacfiicepS .5 melborP ni deredisnoc egaugnalehtnisnoisserpxeehtfotesbusarofreterpretninaetirwlliwewmelborpsihtnI
].oper-cilbupmorfelbaliavasitahtlm.6borpelfinoteleksehtniydaerladecalp neeb sah siht ,ecneinevnoc ruoy roF .detrats teg ot noitpircsed melborp eht ni dedivorp noitaralced epyt eht deen lliw uoY .lm.6borp deman elfi a ni dedivorp eb tsum melborp siht ot noitulos ehT[
.epytstifonoitatneserperasidnaelbaepytsinoisserpxeehtfierehw ro elbaepyttonsinoisserpxeehtfisnruterdnanoisserpxenafonoitatneserperasekattaht
)stniop 21( 6 melborP
noitcnufehtenfied,noitcnuf ehtgnisU.3
.ssalcnidessucsidyawehtnidemrof-llewsinoisserpxenatahtdekcehcevahewretfaylno noitcnufsihtllaclliwew.e.i,neppahrevenlliwsihttahtemussA?tnemugra)tsil(dnocesehtni yrtnenaevahtonodosladnagnidnib aro aybdnuobtoneratahtsrefiitnedisniatnoc
tnemugratsrfiehtsatupnisitahtnoisserpxeehtfitahW:uoynrecnocthgimtahtnoitseuqA
.lacitnedi eb otevahsepytriehttahtsitnemeriuqerylnoeht,epytyrartibrafoebnacesle-neht-finarof sehcnarbeslednanehtehttahteesdluohsuoy,selpmaxeowttsalehttagnikooL.setanimod tahtenoehtsinoisserpxeehtottsesolcgnirruccoenoeht,refiitnediemasehtrofsgnidnib epytelpitlumsniatnoctxetnocanehwtahteesdluohsuoy,erehelpmaxehtxisehttagnikooL
2020/2/19 CSCI 2041, Advanced Programming Principles
| Times of expr * expr
| Div of expr * expr
| Lss of expr * expr
| Eq of expr * expr
| Gtr of expr * expr
| And of expr * expr
| Or of expr * expr
| Not of expr
| Cond of expr * expr * expr
| Let of string * expr * expr
(* for exp1 * exp2 *)
(* for exp1 / exp2, division being for integers *)
(* for exp1 < exp2 *)
(* for exp1 = exp2, = being equality comparison *)
(* for exp1 > exp2 *)
(* for exp1 && exp2 *)
(* for exp1 || exp2 *)
(* for not exp *)
(* for if exp1 then exp2 else exp3 *)
(* for let = exp1 in exp2 *)
let x = 5 in let y = 7 in x + y
Let (“x”,(Int 5),Let (“y”,(Int 7),Plus ((Id “x”),(Id “y”))))
eval : expr -> (string * expr) list -> expr
expr
let exp1 = Let (“x”,(Int 5),Let (“y”,(Int 7),Plus ((Id “x”),(Id “y”))))
let exp2 = Let (“x”,True,Cond (Not (Id “x”),True,False))
let exp3 = Let (“x”,
False,
Cond (Not (Id “x”),
Let (“x”,Int 5,Plus (Id “x”, Int 3)),
Let (“y”,Int 7, Id “y”)))
# eval exp1 [];;
– : expr = Int 12
# eval exp2 [];;
– : expr = False
# eval exp3 [];;
– : expr = Int 8
#
Int i for some integer i, True, or eval
expr
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 10/12
.gnidnib eht ekam ew erofeb .e.i ,ylregae otdnuobebotsirefiitnediehttahtnoisserpxeehtetaulaveew,telanitahtsinoitpmussaeht :emanhcaehtiwevobadebircsedsmrofeerhtehtfoenofonoisserpxenasitahteulavaetaicossa lliwtnemnorivnenasaotderrefernetfositaht,tsilsihttahtetoN.esopruptahtroftnemugra tsilsihtesuewdnaetaercyehtsgnidnibehtgnolayrracotevahew,snoisserpxetelfoseidobeht otnidnecsedewsa,revewoH.ytpmeebyllaitinilliwtsilsihtos,srefiitnedidnuobnuevahtontsum levelpotehttaetaulaveotyrtewsnoisserpxeehT.noisserpxeehtniraeppayamtahtsrefiitnedi rofgnidnibasedivorptnemugrasihT.tnemugradnocesehtsdeen yhwrednowyamuoY
.eslaF :smrof eerht foenoeblliwnoitaulavefotlusereht,gniredisnoceraewegaugnalelpmisehtroftahtevresbO
:lmaCOhtiwnoitcaretnigniwollofehtssentiwdluohsewneht
sgnidnibtelgniwollofehtevahewfi,elpmaxeroF.snoisserpxefosmrof tnereffidehtrofselurtnavelerehtgnisutisetaulavedna epytfonoisserpxenasekattaht
epytdnaemangniwollofehtfonoitcnufaenfiedoterauoy,yllacfiicepS.noitaralced epytehtnidedocnelmaCOfotesbusehtrofrotaulavenadliubotsimelborpsihtniksatruoY
: epytfonoisserpxegniwollofehtybdetneserperebdluow, noisserpxelmaCOeht,elpmaxeetercnocasA.lmaCOnisnoisserpxeteltneserperotdesusihcihw
,mroftsalehtspahrepsiyfiralcotgnihtylnoehT.tiotnoitcudortnieromhcumdeent’nodewos ,krowemohsihtnimelborpsuoiverpehtnineve,erofebnoitatneserperfodniksihtneesevaheW
2020/2/19 CSCI 2041, Advanced Programming Principles
True False
ty
let
let
eval
eval
expr
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 11/12
.udetodnmungistanalapognybdetaerC.0202,6beF:defiidomtsaL
!esruocsihtdnoyebrehtegotnokrownacewstcejorphcraesereb yamereht,sgnihthcusrofedutitpanadnatseretninahtobrevocsiduoyfi,revoeroM.nokcutsteg uoytahtsgnihthtiwuoyplehnacI.mehttuobaemotklat,gnitseretnisnoisnetxeesehtdnfiuoyfI
!tibehttagnfiahcerauoyfidaehadaernac uoytub,esruocehtniretaltahwemosssucsidlliwewtahtgnihtemos,secnereferfoesueht sevlovnisihtgnitaertfowonkIyawtsebehT.sgnidnibtelevisrucerrevocot fonoitinfied
ehtdnetxenehtdnasgnidnibsuoenatlumistimrepot rofnoitaralcedepytehtdnetxE.3
.ssalc ninoosmroftnereffidanissucsidlliwewtahtaedina,erusolcadellacgnihtemosesuotsi sihtodotyawtsebeht;yltneicffiesnoisserpxeotninoitutitsbustaertotwohsiereheussiyek ehT.evisrucertonerasteltahtemussa,noisnetxeehtfonoisrevsihtnI.llewsasnoisserpxe
noitacilppadnanoitcnuffosesacehttaertot6melborPni fonoitinfiedehtdnetxE.2
.deugirtnierauoyfiemotklatnehtdnasihttuobaknihT. ehtfoydob ehtnisecnatsniepytstifoynatadesuebnehtnachcihwepytcihpromylopfonoisserpxea otdnuobebnacrefiitnediehtesuacebsaediwenemoseriuqerlliw fotnemtaertehT.llew sasepythcusesuotedocgnikcehcepytruoyyfidomdnasepythcusedulcniot epyteht fonoitaralcedehtecnahnenehT.lmaCOnievahewdnikehtfosepytcihpromyloptneserper
dluow uoy woh dnatsrednU .5 melborP ni msihpromylop timrep ton did ,elpmis sgniht peek oT .1
:od ot uoy tcepxe 6 dna 5 smelborP tahw dnoyeb og ot ekil dluow uoy fi redisnoc ot stnemecnahne emos era ereH
.snosaerdoogrofdnafoknihtnacewegaugnal ynahcumytterpnisnoisserpxeesehthtiwdetaicossascitnamesehtsiti:tnatropmifodniksisihT .tnemugradnocesehtgnitaulaveotnooguoyodnoisserpxeehtrofeulavhturtehtenimretedton seodtifiylnodnatnemugratsrfiehtetaulaveuoy:rodnadnarofylralimiS.detaulaveebotsdeen taht esac eht denimreted dna noitidnoc eht detaulave evah uoy retfa .e.i ,dnamed no ylno trap esle ehtronehtehtetaulaveuoytahtossihtezinagro,esle-neht-finagnitaulavenehW:etonlanfienO
.stluser “doog” evah syawlaewerusnelliwtahtdna5melborPnideredisnocsawtahwotralimisssecorpaybdetaulave erayehterofebdekcehcepytebsyawlalliwetaulaveotyrtuoysnoisserpxeehtesuaceB?yhw dnA.neppahrevenlliwsihttahtemussadluohsuoytahtsisihtotrewsnaehT? ro yb detneserperseulavehtfoenonahtrehtarpuswohsregetninafitahw,noisserpxednanaetaulave ot gniyrt ma I nehw ,elpmaxe roF ?epyt thgir eht fo ton si noitaulave fo tluser eht fi od I dluohs tahw:gniwollofehtsirotaulavetsrfis’enognitirwsienonehwsesiranetfotahtnoitseuqenO
smelborP egnellahC lanoitpO
2020/2/19 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw2.html 12/12
.atosenniM fo ytisrevinU eht yb devorppa ro deweiver neeb ton evah egap siht fo stnetnoc ehT .)s(rohtua egap eht fo esoht yltcirts era egap siht ni desserpxe snoinipo dna sweiv ehT