ThissamplemidtermisthemidtermfromSpring2008.Ifyouseeanyerrors inthesampleanswer,pleaseemailmeortellmeonPiazza.Goodluckon yourmidterms!
1.“Irelandhasleprechaunsgalore.”isanexampleofaparticularkindof syntacticconstructinEnglish.CanyouconstructasimilarexampleinC++, OCaml,orJava?Ifso,giveanexample;ifnot,explainwhynot
– Artificiallanguagesaregenerallymorecarefully-designedthan naturallanguages.Thus,thesekindsofexceptionsshouldberare,if theyexistatall.
2. a)WriteanOCamlfunction‘twice’thatacceptsafunctionfandreturnsa functiongsuchthatg(x)equalsf(f(x)).Forsimplicity’ssake,youcan assumethatfisfreeofsideeffects,andyoucanimposeother restrictionsonfandx.Trytokeeptherestrictionsasminoraspossible, andexplainanyrestrictionsyouimpose.Or,if‘twice’cannotbewritten easilyinOCaml,explainwhynot.
Copyright By PowCoder代写 加微信 powcoder
– lettwicef x=f(f(x))
– restrictionisthatfis‘a->‘a b)Sameasa)exceptwriteafunction‘half’thatacceptsafunctionfand returnsafunctiongsuchthatf(x)equalsg(g(x)).
– Itisdifficult,sinceitsimplementationmustdependonthespecific functionfused.
– Forexample,iffisidentityfunctionf(x)=x,thengiseasy– alsotheidentityfunction.
– However,iffisthesinefunction,thengissuperdifficult–given x,g(g(x))=sin(x)???
– Therestriction,likea),isthatfis‘a->’a
c)Givethetypesof‘twice’and‘half’ – twice:(‘a->’a)->‘a->‘a
– half:(‘a->‘a)->‘a->‘a
3.ConsiderthefollowinggrammarforasubsetoftheC++language.
expression: expression?expression:expression expression!=expression expression+expression
!expression INTEGER-CONSTANT (expression)
Forexample,(!!0+1!=2?3:4)isreadas“ifnot-not-0plus1doesnot equal2,then3else4,andevaluatesto4.
a)WhatarethetokensofthissubsetofC++? ?:!=+!INTEGER_CONSTANT()
c)Rewritethegrammarsothatitisnolongerambiguous,resolvingany ambiguitiesinthesamewaythatc++does.RecallthatinC-+,the expression
(0!=1!=2||3+!4+5||6?7:8?9:10)islike (((((0!=1)!=2)||((3+(!4))+5))||6)?7:(8?9:10))
E->E2?E2:E|E2 E2->E2!=E3|E3 E3->E3+E4|E4 E4->!E4|E5 E5->INTEGER-CONST|(E)
d)Translatetherewrittengrammarintoasyntaxdiagram
eg.E2 o——>E3—–>o
|<--!=<--|
4.AnumericalanalystisreallybotheredbythespecialvalueofIEEE
f l o a t i n g p o i n t , a n d a s k s y o u t o m o d i f y J a v a C + + t o f i x w h a t s h e v i e w a s a seriousconceptualflaw.ShewantsherJavaprogramstothrowanexception insteadofreturninginfinitiesandNaNs.Isherrequestreasonablefor JavaC++programs?Isitimplementable?Why/whynot?Don’tworryabout compatibilitywithexistingcompilers,etc.;assumethatyouarethe
i n v e n t o r o f J a v a C + + a n d s h e i s a s k i n g f o r t h i s f e a t u r e e a r l y i n y o u r languagedesignprocess.
- It’skindofreasonable...maybethenumericalanalysthas applicationsthatdon’tallowInfsandNaNs.However,thisgetsrid o f t h e c h o i c e o f h a v i n g t h e s e s p e c i a l v a l u e s . T o i m p l e m e n t i t , J a v a C++canthrowanexceptionwheneveritencountersaspecialvalue.
5 . G i v e a n e x a m p l e o f f o u r d i s t i n c t J a v a C + + t y p e s A , B , C , D s u c h t h a t A isasubtypeofB,AisasubtypeofC,BisasubtypeofD,andCisa subtypeofD.Or,ifsuchanexampleisimpossible,explainwhynot.
- classD{...}
- classA:publicB,publicC{...} - classB:publicD{...}
- classC:publicD{...}
6.ExplainhowyouwouldimplementOCaml-styletypechecking,inan implementationthatusesdynamiclinkingheavily.Whatproblemsdoyou foreseeinprogramsthatrelinkthemselvesonthefly?
- (verbatimfromtheprofessor)Theproblemisthatoneneedstodotype checkingaswellastheusualnamecheckingthatlinkeditingnormallydoes. AndthetypecheckingneedstofollowOCaml'srules. Inparticularitneedsto workwithgenerictypes,wherethetypeofthelinked-tofunctiondoesnot exactlymatchthetypeneededbythecaller,butthetypeswillmatchafter applyingaunifier.
7. a)WriteacurriedOCamlfunction“interleaveCSL1L2”thatconstructsa newlistLfromthelistsL1andL2,usingthechooserCwithseedS,and returnsapair(S1,L)whereS1istheresultingseedandListhe interleavedlist.Forexample,“interleaveCS[1;2][3;4;5]”mightinvoke Cfourtimesandthenreturn(S1,[1;3;4;2;5]).Ateachstepofthe iteration,“interleave”shouldusethechoosetodecidewhethertochoose thefirstitemofL1orthefirstitemofL2,whendecidingwhichofthe twoitemstoputnextintoL.IfL1isempty,thechooseneednotbeused, since“interleave”willjustreturnL2;andsimilarlyifL2isempty, “interleave”shouldjustreturnL1withoutinvokingC.
ChooserCisdefined
http://www.cs.ucla.edu/classes/spring08/cs131/hw/hw1.html
“interleave”shouldinvokeCaminimalnumberoftimes,lefttoright acrossthelistsL1andL2.“interleave”shouldavoidsideeffects;it shouldbewritteninafunctionalstyle,withoutusingOCamllibraries.
letrecinterleavecsl1l2= ifl1=[]then(s,l2)elseifl2=[]then(s,l1)else match(cs)with
|(true,s1)->(matchl1with
|h::t->(let(s2,l)=(interleavecs1tl2)in (s2,h::l)))
|(false,s1)->(matchl2with |h::t->(let(s2,l)=(interleavecs1l1t)in
(s2,h::l)))
b)Writeafunction“outerleave”thatdoestheoppositeofwhat“interleave does”:itsplitsalistintotwosubliststhatcanbeinterleavedtoget theoriginallist,andreturnsatripletconsistingofthenewseedandthe twosublists.Thatis,“outerleaveCS[1;3;4;2;5]”mightyield(S1, [1;3;2],[4;5]).IfgivenalistoflengthN,“outerleave”alwaysinvokes thechooserNtimes.
letrecouterleavecsl= matchlwith |[]->(s,[],[]) |h::t->match(cs)with
|(true,s1)->(let(s2,l1,l2)=(outerleavecs1t)in (s2,h::l1,l2))
|(false,s1)->(let(s2,l1,l2)=(outerleavecs1t)in (s2,l1,h::l2))
c)Givethedatatypesofalltop-levelvaluesorfunctionsdefinedinyour answertoa)andb).
– interleave:(‘a->bool*’a)->’a->’blist->’blist->’a*’b list
– outerleave:(‘a->bool*’a)->’a->’blist->’a*’blist*’b list
– chooserc:’a->(bool,’a)
– seeds:’a
– listl1/l2/l:’blist
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com