[SOLVED] CS ocaml compiler Java ThissamplemidtermisthemidtermfromSpring2008.Ifyouseeanyerrors inthesampleanswer,pleaseemailmeortellmeonPiazza.Goodluckon yourmidterms!

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)WriteanOCamlfunctiontwicethatacceptsafunctionfandreturnsa functiongsuchthatg(x)equalsf(f(x)).Forsimplicityssake,youcan assumethatfisfreeofsideeffects,andyoucanimposeother restrictionsonfandx.Trytokeeptherestrictionsasminoraspossible, andexplainanyrestrictionsyouimpose.Or,iftwicecannotbewritten easilyinOCaml,explainwhynot.
lettwicef x=f(f(x))
restrictionisthatfisa->a b)Sameasa)exceptwriteafunctionhalfthatacceptsafunctionfand returnsafunctiongsuchthatf(x)equalsg(g(x)).
Itisdifficult,sinceitsimplementationmustdependonthespecific functionfused.
Forexample,iffisidentityfunctionf(x)=x,thengiseasy alsotheidentityfunction.
However,iffisthesinefunction,thengissuperdifficultgiven x,g(g(x))=sin(x)???
Therestriction,likea),isthatfisa->a
c)Givethetypesoftwiceandhalf 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)isreadasifnot-not-0plus1doesnot equal2,then3else4,andevaluatesto4.
a)WhatarethetokensofthissubsetofC++? ?:!=+!INTEGER_CONSTANT()
b)Showthatthisgrammarisambiguous Drawthetwoparsetreesforexpression1+2+3
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.AnumericalanalystisreallybotheredbythespecialvalueofIEEEf 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?Dontworryabout compatibilitywithexistingcompilers,etc.;assumethatyouarethei 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.- Itskindofreasonable…maybethenumericalanalysthas applicationsthatdontallowInfsandNaNs.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)WriteacurriedOCamlfunctioninterleaveCSL1L2thatconstructsa 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,interleaveshouldusethechoosetodecidewhethertochoose thefirstitemofL1orthefirstitemofL2,whendecidingwhichofthe twoitemstoputnextintoL.IfL1isempty,thechooseneednotbeused, sinceinterleavewilljustreturnL2;andsimilarlyifL2isempty, interleaveshouldjustreturnL1withoutinvokingC.ChooserCisdefinedhttp://www.cs.ucla.edu/classes/spring08/cs131/hw/hw1.htmlinterleaveshouldinvokeCaminimalnumberoftimes,lefttoright acrossthelistsL1andL2.interleaveshouldavoidsideeffects;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)Writeafunctionouterleavethatdoestheoppositeofwhatinterleave does:itsplitsalistintotwosubliststhatcanbeinterleavedtoget theoriginallist,andreturnsatripletconsistingofthenewseedandthe twosublists.Thatis,outerleaveCS[1;3;4;2;5]mightyield(S1, [1;3;2],[4;5]).IfgivenalistoflengthN,outerleavealwaysinvokes 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