; TeX output 1995.07.01:1517g\32\ܚ\NpKffffcmbx14BeyondLProtwotyp8eImplementa>tions:͍f>PolymorphiccLPro!jectionAnalys8isE.forLGlasgowHaskell"%3"V cmbx10JulianTSew9ard hindtThed؇eAs ignandimplementationofaHs rst-ord؇e r,pAolymorphicproject9ionanalys. erforHask9ell,capableofd؇e-Hstect9ingheNadstr'xictneAsNs,andtThe reforesuitableforsuppAortingallknownHsstr'xictn9eAsNs-relatedtransformat9ions.DevelopmentculminateAdinasucceAsNs-HsfulPtr'xialinst9allationPinv9e rs ion0.19oftTh9eGlasgowHaskellCompile r,Hsan9dtThesystemhasb eenus. eAdtoanalysearangeofHask9ellprograms,HsincludingTaneNarlie rv9ers ionofitfs. elf,13000lin9eAslong."Ѝ,(N cmbx121 Inftro`ductionx,K`y cmr10The#pastdTecade#hass1eenadramÎaticimprovementintUhep#e rformÎanceoflazy,furnctionÎallanguageGs,notablyHaskell,asimplementrorshavedTevelop#eGdwaystro,mÎapsuchlanrguageGsecientUlyontrostoGckarchitUectureGs.Neve rtUheleGsqs,tUheystill,rurnanordTe rofmÎagnitudeslowe rtUhantUheGirimp#e rativecourntUe rparts,and,wors1e,,itQloGoksliketUhep#e rformÎanceimprovementsaretailinrgo .F*urtUhe rincreqas1eGsin,p#e rformÎanceVdTependon ndinrgwaystroreplacecopyinrgbyupGdratUe-in-place,and,lazyevqaluationbystr*ictevqaluation,whenpGoqss#ible.Acr*iticalelementintUhi#sis,tUheUUs1emÎanticanÎalys1eGswhichdi#sTcove rwhensuchtransformÎationsarevqalid. ;SucceGsqsfulPNus1eofstr*ictneGsqsandshar*inrganÎalys1eGsincompile rsdTemandscare-,fulcons#idTe rationoftUheenrginee r*ingconstraintsimpGoqs1edbys1eparatUecompilation,,andVbytUhelimitUeGdcompurtingVreGsourcesavqailable.Section2oftUhi#spape rexam-,ineGsYsuchconstraintsindTetail,asawayofgene ratinrgus1efulmetr*icswitUhwhich,troasqs1eGsspGoss#ibilitiesintUhedTes#ignspace.Bas1edontUhi#s,weourtlineinSec-,tion3HtUhedTeGs#ignofapolymorphic,backwardsstr*ictneGsqsanÎalys1e rforHaskell.,TheanÎalys1e rwasinstalleGdinGlasgowHaskell0.19,andshÎowsanurnpreceGdTen-,tUeGd1pr*ice-p#e rformÎanceratio.Section4preGs1entstUhereGsulrtsoftUhi#sexpe r*imentand,concludTeGs.RAlrtUhÎoughourpr*imaryconce r#nisstr*ictneGsqsanÎalysisofHaskell,tUheGs1e,idTeqasH=havewidTe rapplicabilitytroallabqstract-intUe rpretationbas1eGdanÎalyseGsfor*g\32\ܚRfurnctionÎalolanguageGs,andshÎouldintUe resttUhÎoqs1econce r#nedbytUhes1eeminrglylarge RgapUUb#etweentUhetUheoryandpracticeofabqstractintUe rpretation. waReqal,)usableanÎalys1eGsdi e rf*romprotrotyp#eimplementationsins1eve ralways.RTheN/anÎalys#ishastroruninreqasonÎabletimeandmemory*,evenwhenpreGs1entUedwitUhRurnreqasonÎable2oinputs;itshÎould\ t"prop#e rlyintotUheexi#stinrgcompile rf*rame-Rwork,xvi#s-a-viss1eparatUecompilation,anditshÎoulddoagoGodjobforimportantRlanrguagep-feqatureGs,particularlysurm-of-proGductstyp#eGs,polymorphi#smandhighe r-RordTe rEfurnctions.W*eshÎortUlyexaminetUhecons1equenceGsoftUheGs1econstraintsinsomeRdTetail.aTheemÎainfoGcusoftUhi#spape risonglobaldTeGsigntradTeo s.Bas1eGdontUhatRdi#sTcusqsion,gweourtUlineaparticularlye ectivepGolymorphicpro8jectionanÎalys1e rRforHaskell,andshÎowsomereGsulrtsf*romit.TheanÎalys1e r'sdTeGs#igndetailsareRbGotUhintUe restinrgandvolurminous,butnotappropr*iatUehe re,soreferenceGstromoreRtUhÎoroughA treqatmentsaregiventUhroughÎourt{the rstpGortofcalli#sprobablytUheRaurtUhÎor'sUUPhDtheGs#is[Sew948]. U鍑RArc9hit"ectural>Ove Drview-ȲThi#s9pape rdividTeGss1emÎanticanalys#issystUemsintroRtwoHconceptualparts:anabqstractintUe rpreter,Hwhichgene ratUeGsrecurs#iveequationsRove r`somedomÎains,anda xpGointUe r,whichremoveGsrecurs#ionf*romtUheequations,RtUhe reTby5mÎakinrgthemus1efultrocompile rs.Asusual,werequiretUhedomÎainstrob#eRof6 nitUeheGight6troguaranteete rminÎationof xpGointinrg,andfurtUhe rreGstr*icttUhemRtroUUb#edistr*iburtiveUUlatticeGstromÎake xpGointinrgeqas#ie r.aSeve ral$di erentsTchemeGsfor xpointinrghaveb#eenpropGoqs1ed.TheF*rontie rsRalgor*itUhmb'cleve rlyexploitsmonotronicitytrobuildsyntacticallyurniquerepreGs1enta-Rtions,tUhustr*iviali#sinrgtUhedTetUectionof xpGoints.IntroGducedbyClackandPeytronRJoneGs[PC87 ],tUhealgor*itUhmhasb#eenmUuchturneGdove rtUheyeqars[Mar92Z,Hurn91o],RandsuppGortshighe rordTer xpGointinrg.As1econdlineofenquiryi#stUhatoflazyR xpGointinrg,6whe retUhe xpGointi#sonlycompurtUedwhe reneeGdTed,ondTemÎand.TheRpreci#s1e1or*iginsoflazy xpGointinrgaredTebatable,1burttwoeqarlypreGs1entationsRareduetrotUheCousots[CC78q]andtroJoneGsandMycroft[JM86N=].ExtUens#ionsRtrohighe r-ordTer xpGointinrgareshÎownbyF*e rgusonandHugheGs[FH93!],andbyRRoqs1endrahl[Ros93j].ΆTheworkofHankinandLeMGetaye ron\lazytyp#eGs"[HM94]Ri#sUUalsorelatUeGd.aIn8tUhi#spape rwetakeatUhirdapproach:compurtationofcompletUe xpGointsRby4us#inrgatUe rmrewr*itesystemtrotransforms1emÎanticallyequivqalenttUe rmstroRsyntactically8|idTentical8|normÎalforms.Cons1eldTeGsTcr*ib#es8|asimplerewr*itUe rfortwo-RpGointulatticesus1edinY*aleHaskell[Con91!],andtUhetUechniquewasextUendTeGdtroRotUhe rlatticeGsin[Sew948],Section5.Rewr*itUe-bas1eGd xpointUe rscannot,ingeneral,RsolveUUhighe r-ordTerequations,burt,asweshalls1ee,tUhi#smÎaynotmattUe rmUuch.aNoGcke r[Noc938]ѶshÎowsaworkinrganÎalys1e r,baseGdon\abqstractreduction",Rwhe re8tUerm-rewr*itinrg8i#sus1eGdtoexecutUetUheprogramus#ingsomeabqstracts1e-RmÎantics.dBycompar*i#son,ourtUe rm-rewritinrgi#sus1eGdtodTetUect xpGoints,andRtUhe re-vi#sacleqardistinction-vbetween-vtUheabqstractintUe rpretationand xpGointinrgRactivitieGs.aThe preci#s1enÎatureofabqstractintUe rpretationsi#sdTetUe rmineGd,nÎaturally*,by:g\32\ܚ,tUhetransformÎationtrob#esuppGortUed.OneparticularlyimpGortantcharactUe r*i#sa- ,tionZi#stUhelatticeGstrowhichdi e renttyp#eGsaremÎapp#eGd.IntUhes#impleGstcas1e,,allRnon-furnctionÎaltyp#eGscouldbemÎappeGdtroatwo-pointRlattice,witUhthepGoints,repreGs1entinrgRpnodTemÎandandweqakheqadnormÎalform(WHNF)RodTemandreGsp#ect-,ivelyinstr*ictneGsqsanÎalys#is.F*oras#impleshar*inrganÎalys#is,wemightus1ea3-,pGoint!chain,dTenotinrgnorefe renceGs,exactUlyonerefe rence,andtwoormore,refe renceGs.SimpleabqstractionsliketUheGs1earerourtinelyus1eGdinexi#stinrgHaskell,compile rs[Con91!,PJ93].Thes#implicityoftUheabqstractionsmÎakeGstUheGs1eanÎalyseGs,cheqapUUandreliable,soweshallnotcons#idTe rtUhemfurtUhe r. +;AmorepGowe rfulanÎalys#ismightattUempttrogivedTetaileGdinformÎationabGourt,furnctions?dTeqalingwitUhstructureGdtyp#eGssuchasli#sts,treeGs,orwhatUeve rprogram-,me rs7^caretrodTe ne.LatticeGsabqstractinrgsuchtyp#eGsgrowinaccordrancewitUhthe,complexityapoftUhÎoqs1etyp#eGs,sotUhe rei#snoarbitrarycurto appGointbeyondapwhich,allLDdTetailsareignoreGd.InotUhe rwords,tUhe rei#sapGoqssibilityLDofs1eeGinrgarbitrar*ily,f#ar\insidTe"dratastructureGs.Thedowns#idTeistUhattheGs1elatticeGscananddoget,ve ry&large,sotUheanÎalys#is&becomeGs&expensive.&IntUhi#ss1ense,&semÎantic&analys#isis,aQparticularlyintractableproblem,b#ecaus1etUhelattices#izeGsandtUhusQamourntof,e ort*KrequireGdcangrowexponentially*KwitUhcomplexityoftyp#eGs.F*orexample,if,an&itUemoftyp#e(Int,?Int,Int)&ismoGdTelled&bya9pGointlattice,(2W !", cmsy1022) O!cmsy7?,,addinrgBjustonemoreInttotUhetuplee ectivelydouUbleGsthelattices#ize,giv-,inrg[f(2畸222)?.Thecoqstsofhighe rordTers1emÎanticanalys1eGsarealmoqst,legendrary*,wkbuteven rstordTe ranÎalys1eGscanb#ecomeexcesqs#ivelyexpensive.Get-,tinrgreqasonÎablep#e rformÎancesometimeGsrequires\worklimitinrg"{tUhrowinrgaway,dTetailUUwhichabqstractintUe rpretationwouldotUhe rwi#s1epickup.!@,2 Cons trainftsonviabٙledfe`s0ignsW,2.1 Separaft"eTCompilat9ionW,Cur*iouslyenough,s1eparatUecompilationi#stUhebiggeGsts#inrglesourceofdTes#ign,constraints.OAOconvenientOwaytroviewamUulti-moGduleprogrami#sasadirectUeGd,,roGotUed,poqss#iblycyclicgraph,witUharcsre ectinrgimpGortdTependencieGs,tUheMain,moGduleGattUhe\trop",andtUheHaskellPreludeattUhebGottrom^ٓRcmr71|s.Compilationofa,moGdule.Mcaus1estUhecompile rtroreqadthesourcetUextofMandintUe rf#ace leGsof,moGdulesimmediatUelyb#elowM,andemitcoGdTeandintUe rf#ace leGsforM.IntUe rf#ace, leGsareus1edbytUhecompile rtrocommUunicatUereGsultsofs1emÎanticanalys1eGsacroqss,moGdulebourndar*ieGs.IntUheabqs1enceofinformÎationabGourtimportUedentities,tUhe re,i#salwaysasafeasqsurmptionwhichcanb#emÎadTe.Thisf*rameworkimpGoqs1ess1eve ral,limitations:2@{=ThetintUe rf#ace leGsoughttrob#elimitUeGdtoareqasonÎables#ize,otUhe rwi#s1etUhe=compile r\fmÎaysp#endalotoftimereqadinrgtUhem.F*orexample,GlasgowHaskell=0.19's/PreludeintUe rf#aceisabGourt100klong,andreqadingits#igni cantUlyslows=compile rUUstartupforsmÎallmoGdules., ىff8ϟ L͍-=)Aacmr61 ?ItTi scon9venientTtoasNsum9eallmoAdulesTimporttTh9e1ߤN cmtt9Prelude.*^g\32\ܚX@{cInformÎationonly owsupwards,trowardsMain.F*orqueGstionsoftUheform c\hÎowQ6i#sentityXPgoinrgtob#eus1eGd?",wealsoneeGdinformÎation owsdownwardcf*romUUMain.X@{cT*ocompileamoGduleM,itshÎouldsucetroreqadtUheintUe rf#aceGsformodulescimmeGdiatUelyb#elowM.W*ece rtainlywanttroavoidreqadinrgalltUheintUe rf#aceGscintUhedownwardcloqsureofM:forMain,tUhatcouldmeqanreadinrgtUheentirecs1etUUofintUe rf#aceGs.RMut9uallyrecur-s(ivemoQdules<;Exi#stinrgDimplementationsdTeqalwitUhmurtuallyRrecurs#ivecmoGdulescintwocways.Onei#strocompileallmoGdulescinagrouptro-RgetUhe r,acleqansolurtion,aswitUhY*aleHaskell's\compilationurnits".TheotUhe rRi#sptrocompileeqachmoGduleintUhegroups1eparatUely*,urntilintUe rf#ace leGsstabili#s1e,RdTenotinrgLa xeGdpoint.Thi#smeqanstUhatatleqastonemoGdulewillhavetrob#eRcompileGd?NwitUhze ros1emÎanticknowleGdgeoftUheotUhe rs,witUhthecompile rmÎak-Rinrg{worst-cas1easqsurmptions.TheupqshÎotoftUhi#sistUhat,fors1emÎanticanÎalys1eGsRinvolvinrgUU xpGointing,UUtUhe xpGointsb#einrgcomputUeGdmÎayb#esuUboptimÎal.R2.2 CompJlet"eTorminim}alfunct9iongraphs?RFixpGointinrg1]byminimÎalfurnctiongraphs^2 в(MFGs)buildstUheminimÎals1etofRargurment-reGsult֌pairs b> cmmi10GneeGdTed֌troevqaluatUetUhe xpGointatasp#eci cargurmentRxt}\cmti7init .c/Theinitialgraphi#sf(xinit ;>)g^3|s.AteqachitUe ration,reGsulrtsforallargumentsRin4tUhecurrentgraphG 0ercmmi7n arere-evqaluatUeGd,givinrgGn+1.WhenanapplicationofRaAfurnctiontosomeargumentxi#sencountUe reGd,tUheexi#stinrggraphGnji#ss1eqarcheGdRforsacorreGspondinrgsresult.sIftUhatxi#snotpreGs1ent,thereGsulrti#stakenas>andRtUhe9pair(x;>)i#sins1e rtUeGdintroGn+1.TheproGcesqs9rep#eatsurntilGstabili#s1eGs,Rwhe reupGonUUG(xinit )dTelive rstUherequireGdvqalue.Asanexample,cons#idTe r:+D繍#x': cmti10fѲ::R[2_?2? ظ!2_?2? ] Y#xfxѲ=Ru cmex108 R< R:d?7sifB?x=?liftز(lift(0))ȸu㈲(lift (?)8t(fڧ?))7sifB?x=liftò(?)ظx㈸u(lift (?)8t(fڧx))7sotherwiseRGivenxinitv=%_lift (?),wehaveG0Ҳ=%_f(lift (?);>)g.Evqaluatinrg(f8lift.(?))giveGsRreGsulrtliftز(lift(0))4dandanewpair(?;>),soG1C=f(?;>);(lift (?);liftز(lift(0)))g.RItUe ratinrg4againgiveGsG2 b=Kf(?;?);(lift (?);liftز(lift(0)))g4ܲandG3 b=KG2|s,soRG(xinit )=liftò(lift (0)).aInDtUhi#sexample,therequireGdanswe rwasobtaineGdbyevqaluatinrgfWattwoRourtofitsfourargumentpGoints.WhentUheargurmentlatticeGscontaintUhÎousandsRof]pGoints,tUhehÎop#eistUhatonlyatinyminor*ityofargurment-reGsult]pairsneeGdtroRb#eUUcompurtUeGd.aMFGsh>achieve\lazy" xpGointinrgb#ecaus1etUheymÎakeexplicittUhedTep#endenceRb#etween?inpurtandoutʪputpGoints.NoticehÎowtUhealgor*itUhmi#slimitUeGdtro rstRff8ϟ L͍-=2 ?ATfunct9ion'sgraphi snomoretThanacollectionofargument-reAsultTpairsforit. -=3 ?, cmsy9>TifmaximalT xpAointfsaresough9t,?forminimal xpointfs.@g\32\ܚ,ordTe r6furnctions:highe rordTer xpGointinrgwouldrequirecompar*inrgcompletUefunc- ,tionrepreGs1entations,whichi#sprecis1elywhatlazy xpGointinrgi#sdTeGsignedtroavoid.,Neve rtUheleGsqs,byextUendinrgtUhenotionofdTep#endencyb#etweeninpurtsandourtʪputs,,F*e rguson andHugheGs[FH93!]havesucceGsqsfullygene rali#s1eGdMFGstroworkintUhe,highe rTordTercas1e,callinrgtUhemconcretUedatastructureGs(CDSs),andRoqs1endrahl,repGortsUUs#imilarresulrts[Roqs93j].;F*urnctionÎal6typ#eGsabqstracttrodomÎainswitUhsomanypGointstUhatlazy xpGoint-,inrgpcanmÎakeanenormousdi e renceforhighe rordTeranÎalys#is.pF*ergusonand,HugheGsUUgive gureGsfortUhef#amousfoldr-concatexample:;foldr?::(a->b->b)->b->[a]->b;foldr?fa[]=a;foldr?fa(x:xs)=fx(foldrfaxs);concat?::[[a]]->[a];concat?=foldr(++)[],whe reP(++)i#stUheHaskellli#st-appendPope ratror.PUsingPaBHA-styleforwardab-,stractintUe rpretation[BHA85 []requireGsbuildinrganinstanceoffoldrintUhedo-,mÎain=[4J!4!4]!4!6!4.Thi#sgiveGsanargurmentlatticeofalmoqst,600,0001pGoints.Compurtation1oftUheentirefurnctiongraphtakeGsontUheordTe r,ofGanhÎourus#inrgtUhef*rontie rsalgor*itUhm[FH93!],whe reqaswitUhCDSscompurting,just#tUhÎoqs1epartsneeGdTed#trodetUe rminetUheentire xpGointofconcattakeGstwoor,tUhree s1econdsurndTe rs#imilarcircurmstanceGs.F*ormorecomplexfurnctionspaceGstUhe,di e renceUUi#sevengreqatUer.;Given"suchanove rwhelminrgp#e rformÎanceadvqantage,iti#stUemptinrgtofor-,getentirelyabGourtanyotUhe r xpGointinrgsTcheme.Y*etintUegrationofCDSqbas1eGd, xpGointinrg.+proves.+trouUblesome.+whenvieweGdf*romawidTe rframework.The reare,twoas-yeturnreGsolvedi#sqsues.FirstUly*,asdi#sTcusqs1edb#elow,wehaveadTeepdeGs#ire,troQavoidmonomorphicanÎalys1eGsofanykind.CDSsaspreGs1entUedsof#ararepurely,monomorphic.;Becaus1eoftUheneeGdtrocloqs1elyexpoqs1edTep#endencies;b#etweensuUb-,partsoftUheinpurtandsuUb-partsoftheourtʪput,iti#snotcleqarhÎowtUheymÎayb#e,us1eGd,inapolymorphicway*.For rst-ordTe r,MFG-style, xpGointinrg,pGolymorph-,i#smQisnotaproblem:KuUbiak[KHL91"]hasimplementUeGdapolymorphicpro8jection,anÎalys1e rUUwitUhMFG xpGointinrgintUheGlasgowHaskellcompile r.;AmoreimmeGdiatUeproblemwitUhlazy xpointinrgi#shÎowtrodTeqalwitUhmoGdules.,AdScrudTedWsTchemei#stroexpGortwhatUeve rpartsoftUheabqstractfurnctiongraphhave,b#een{SaggregatUeGdwhilstcompilinrgtUhedTe ningmoGdule.If,compilingsomeotUhe r,moGdule,tUhecompile rneeGdstroknowtUhe xpGointatsomepGointforwhichno,informÎationi#savqailable,iti#ssometimeGspoqss#ibletromÎakeasafeestimÎatUeus#inrg,monotronicityUUandtUheinformÎationwhichisavqailable.;F*or!example,havinrg!expGortUedGj=f(x1|s;fx1);(x2;fx2)g!wemÎaywi#shtro,know`(f x3|s)intUhecas1ewhe rex3 ]v}x1 Ӳandx3 ]v}x2|s.Sincefi#smonotronic,itGGfollowstUhatfmx3ƸvZSfx1úandGGfx3ƸvZSfx2|s,andsofx3ƸvZS(fx1Vu+fx2|s).,ProvidTeGd/weareworkinrginaf*rameworkwhe reove reGstimÎationi#ssafe,tUhisgiveGs,anUUapproximÎatUevqalueforfڧx3|s.Vg\32\ܚaCleqarly*,tUhebigge rtheexpGortUedG,theb#ettUe rtheeGstimÎatUestUhatcanb#emÎadTe Rf*romTit.BurttUhewhÎolepurpGoqs1eofMFGsi#strokeepGassmÎallaspGoqss#ible,Rcontaininrgp#e rhapqsahandfulofpGointsourtoftUhÎousandsofcandidratUeGs.Thi#sRmilitatUeGs3OagainstmÎakinrggoodapproximÎations.3OW*ors1e,notalltUhepointsinGRmÎayb#eus1eGdinmakinrgtUheapproximÎation:intUheexampleabGove,wearelimitUeGdRtroUUus#ingpGointsf(y[;fڧy)2G0jx3Cvy[ٸg.aA>s1econd,?!equallyurneGdifying?!solution?!i#stroexpGortnotonlyG,buttUhere-Rcurs#iveGdomÎainequationf*romwhenceitcame{oreventUhesourcetUextwhichRb#egatdtUheequation.Then,whenGcannotanswe raquery*,iti#sextUendTeGd,intUheRmÎanne r:dTeGsTcr*ib#edabove,:asrequireGd.IftUheabqstractintUe rpretationsgetlarge,Rdurmping/tUhemintrointUe rf#ace leGsmÎaynotbepractical.ThissTcheme/alsohasaRmorexsuUbtleweqakneGss.xAhcrucialins#ighti#stUhat ndinrgtUhe xpGointofadomÎainRequationmÎakeGsitstandonitsown:itnolonrge rreferenceGsanyotUhe requation.RCons#idTe r͗tUhefollowinrgtUhreemoGdules͗dTe ninrgrecurs#ivefurnctionsf,gandhwitUhRcorreGspondinrgUUequationsf#,g#andh#:mamodule?F(f)where{D?f=...f...$}amodule?G(g)where{importF;g=...g...f...}amodule?H(h)where{importG;h=...h...g...}RDurmpingUUtUheurnsolveGddomÎainequationsintrointUe rf#ace(.hi) leGsgives:aF.hi:f#?=...f#...aG.hi:g#?=...g#...f#...aH.hi:h#?=...h#...g#...RWhenmoGduleHi#scompileGditmÎaybeneceGsqsarytroextUendtUhefurnctiongraphRforNg#.ThetrouUblei#sthi#smeqansreadinrgintUe rf#aceF.hieventUhÎoughthetUextofRmoGduleHӲdo#esnotdirectUlyrefe rtroF:ingeneral,itmightb#eneceGsqsarytroreadallRintUe rf#aceGs؍intUhedownwardcloqsureofH.AnysTchemewhichexpGortsintrointUe rf#aceR leGs՜refe rencestrofunctionsinotUhe rmoGdules՜su e rstUhesameproblem.Mre relyRinlininrg?]refe renceGstootUhe requationsdo#eGsnothelp,astUhi#smÎakeGstUheintUe rf#aceGsRcontainUUeve rytUhinrgb#elowtUhemintUhehie rarchy*,andhenceve rylarge:aF.hi:f#?=...f#...aG.hi:g#?=letrecf#=...f#.../?in...g#...f#...aH.hi:h#?=letrecf#=...f#.../?inletrec?g#=...g#...f#... in...g#...h#...RBecaus1eoftUheGsediculrtieGs,lazy xpointinrgdo#esnots1eemtro twellinanRenvironmentUUwhe res1eparatUecompilationi#stUhenorm.mR2.3 P9oJlymorphicTorMonomorphic?RParametr*ic~VpGolymorphi#smisanimpGortantelementoftUhetyp#esystUemsofmoGdTe rnRfurnctionÎalUUlanguageGs.Givenaparametr*icallypGolymorphicfurnction,wecould:kJg\32\ܚ2@{=ReGdotUheanÎalys#isforeqachdi e rentinstantiationoftUhefurnction.Thi#sis =equivqalentߗtroexpandingouttUheprogramintoacollectionofmonomorphic=instanceGsUUb#eforeanÎalysis. ٍ2@{=AnÎalys1e&tUhefurnctiononce,andus1epGolymorphicinvqar*iancereGsulrtstodTeqal=witUhUUdi e rentlyinstantiatUeGdus1eslatUe ron.Q,Anoft-quotUeGddi#sadvqantageoftUheforme rapproachi#stUhatpGolymorphicfurnctions,mÎayDb#eanalys1eGdmanytimeGs,whichi#swastUeful.IntUheworstDcas1e,tUhenUurm|qb#e rof,instanceGscanb#eexponentialintUhelenrgthoftheprogram.Neve rtUheleGsqs,suchb#e-,haviourtfdo#eGsnotappeqartrooGccur.MeqasurementsbyMarkJoneGsofs#ixsuUbqstantial,programs6{intUhenofibsuitUe[Par92q]suggeGstatwofoldincreqas1eintUhenUurm|qb#e rof,bindinrggroupqs[Jon93].F*urtUhe r,onlys#implelist-handlinrgfunctionslikemapand,foldrShavealargenUurm|qb#e rofinstanceGs,andsuchfurnctionsareoftUeninlineGdby,optimi#sinrgcompile rsanyway*.SomonomorphicanÎalys#ismaynotactuallyinvolve,mUuch%duplicationofwork.Obqs1e rvealsotUhats#incetUheabqstractintUe rpretationsof,typ#eGsoftUenmÎapqsmanytyp#eGstrotUhesamelattice,monomorphi#sationontUhebas#is,ofUUlatticeGscaus1eGsevenlesqsexpans#ion.;Moreqs1e r*iousi#s,onceagain,tUheintUeractionofmonomorphi#sationwitUhmoGd-,uleGs.^RF*oramoduleM^Oexportinrgapolymorphicfurnctionf,wecaneGitUhe ranÎalys1e,fɲatalltUheinstanceGsitwillgetus1edat,orwecanwaiturntilallmoGdulesaboveM,arecompileGdandreqanÎalys1efonanas-neeGdTedbas#is.BotUhsTchemeGsareurnÎattract-,ive,tUhe rstb#ecaus1eitrequireGsadownward(MaintroPrelude)pasqstUhroughthe,moGduleggraphtroestabli#shginstantiations,gtUhes1econdb#ecaus1eoftUheneeGdtrocarry,arourndUUf'ssourcetUextwhencompilinrgmoGdulesUUaboveUUM.;Polymorphic\anÎalys#iscircurmventsbGotUhproblemsb#ecaus1easinrgleanÎalysis,s1e rveGs[allquer*ieGs,eventUhÎoqs1efromdi e rentmoGdules.[W*orkbyBaraki,HugheGs,andmLaurnchbury[Bar93,HL92b!X](tromentionburtafew)haseGstabli#shedmtUech-,niqueGs0#forbotUhforwardandbackwardpGolymorphicstr*ictneGsqsanÎalys1es.Back-,ward%anÎalys1eGslendtUhems1elveGsparticularlywelltrosuchanapproach:Section5,of[Sew948]dTeGsTcr*ib#essuchananÎalys#isinconsidTe rabledetail.Baraki'sworkindic-,atUeGshÎowsomeforwardanÎalys1eGsmayb#emadTepGolymorphic:[Sew948],Section3,dTeGsTcr*ib#esUUanimplementation.;F*ord rstordTe rfurnctions,pGolymorphictUechniqueGsgivetUhesamereGsulrtsas,monomorphic82anÎalys#is:tUheyareexact.Burtinthehighe rordTercas1e,accuracy,mÎayb#eloqst.F*orbackwardanalys1eGs,whichareinhe rentUly rst-ordTer,tUhi#smÎay,b#eacceptable.F*orotUhe ranÎalys1eGs,tUhemÎagnitudTeoftUhi#sproblemhasyettrob#e,quanti eGd.!<,2.4 High9e DrTor r-stTorder?<,Highe r ordTer xpGointinrgi#sdicultb#ecaus1etUhelattices#izeGsforfurnctionspaceGs,grow8sorapidly*.Forexample,instr*ictneGsqsanÎalys#is,8anitUemoftyp#e[Int]?->[Int],mightabqstracttrodomÎain[4\!4],whichhas35pGoints.Addinrgas1econdpara-,metUe rooftUhesametyp#egiveGsdomÎain[4!4!4],owitUh24,696points,anincreqas1e,ofove r700timeGs.ThenUurm|qb#e rofpGointsin[4v!4!4!4]i#sce rtainlyve ry| g\32\ܚRlarge.oManyfurnctionÎalparametUe rshavetyp#eGsmorecomplicatUedtUhanthi#s,and RcalculatinrgUUcompletUe xpGointsintUheGirpres1encei#simpractical.aFixpGointinrgbytUe rmrewr*itinrgsometimeGsf#ailsintUhepreGs1enceoffurnctionÎalRparametUe rs. IntUhegene ralcas1e,highe rordTerequationscannotb#esolveGd,b#ecaus1eRtUheGir xpointsdTep#endontUhe xpGointsoftUhefurnctionÎalparametUe rs.TheusualRmetUhÎoGd՛ofrewr*itinrgadjacentapproximÎationstronormÎalformf#ailstodTetUectanRove rall` xpGointb#ecaus1esuUbqsequentapproximÎations`contain`sometUe rminvolvinrgRatfurnctionÎalparametUe rapplieGdmoreandmoretimeGs.Thi#soccurs,forexample,RinUU xpGointinrgforwardsabqstractionsoffoldr:Hٍafoldr#(n)=?\faxs->...f(f...(fE)...)...afoldr#(n+1)?=\faxs->...f(f(f...(fE)...))...Rwhe reEi#ssomearbitrarytUe rm,andfoldr#(n)andfoldr#(n+1)dTenotUetwoRadjacent1approximÎationstrotUhe xpGoint.He re,fi#safurnctionÎalparametUe rb#eGinrgRwrapp#eGdmoreandmoretimeGsarourndE,tUhe reTbymÎakinrgsyntacticdTetUectionofRa xpGointimpoqss#ible.Ofcours1e,iftUhetUe rmrewr*ite ri#sextremelycleve ritcanRdTetUect#tUhat,forsomesuitablylargen,f \pnb=M xfR,soitcanreplacef 3( xfڲ)byR x`>1fhand-tUhe reTbygene ratUenormÎalformswhichdTep#endexplicitUlyonf's xpGoint.RTheprequireGdpattUe r#nmÎatchinrgpi#str*icky{notsosimplefordouUblyrecurs#iveRtUe rms_{andweneeGdtrodTecide_onasuitablen.ThevqalueofndTep#endsontUheRfurnctionܭspaceinqueGstion{cleqarly*,weneeGdaquickalgor*itUhmforgivinrgaRgoGodove reGstimÎatUeoftUhefurnctionspace'sheGight.NielsonandNielsonloGokedatRtUhi#sproblem[NN92],burttheGirworkcangiveexceGsqs#ivelylargeeGstimÎatUesandi#sRof[limitUeGdapplicability*.[A>morefurndamental[problemi#spGolymorphi#sm:intUhatRcas1e,㾵nvqar*ieGswitUhtheinstantiation,sotUhenotionofcompurtingas#inrglevqalueRforUUiti#snons1ense.aNeve rtUheleGsqs,forhigherordTerequationswhichdonotdTep#endontUhe xpGointsRof1tUheGirfurnctionÎalparametUe rs,te rmbas1eGd xpointinrgworkswellandcanb#eRtUhÎousandsoftimeGscheqap#e rtUhanus#inrgf*rontie rs.Suchequationscanb#egene ratUeGd,Rfor՞example,f*romtUheforwardsabqstractionsofmapandfilter([Sew948],SectionR4.3.5).HٍRIndefenceof r-storde Dran}alys(isThi#s%pape rargueGsagainsthigherordTerRanÎalys1eGs.^Whenmodulesarealsotaken^introaccount,tUhenurm|qb#e rofdTeGsigncon-Rstraintsb#ecomeGsintrole rable.CansuchastUepb#ejusti eGd?W*ell,takeninawidTe rRcontUext,9:mÎayb#e.Highe rordTerfurnctionsdTefeqatadvqanceGdcodTegene ration9:tUech-RniqueGs,Zlikear*itycheckavoidrance,un|qbGoxingandargumentsinregi#stUe rs,ZsinceRtUheyrepreGs1entcallstrocompletUelyunknownfunctions.Aqugustsqson[Aug93]sug-RgeGsts>tUhatcallinrgaknownfurnctioncoqstshalfasmUuchascallinrganunknownRone.aThe(Haskell)compile rcommUurnitygotrocons#idTe rabletrouUbletrogetr*idofRcallsUUtrohighe rordTerfurnctions.F*orexample:X@{cSimplenon-recurs#ivecom|qbinÎatrorslike(.)andthenSѲareinlineGd(inGlasgowcHaskell). g\32\ܚ2@{=PreludTeuDfurnctionswhichpasqsfurnctionÎalparametUe rsalonrgunchangeGd,uDlike =mapUUandfoldr,areurnfoldTeGdtoformsp#ecialis1eGdUUve rsions(inY*aleHaskell). E2@{=Ove rloadTeGdefurnctionsaresp#ecialis1eGdattUheirus1einstances,atleqastwitUhin=s#inrglemoGdules(GlasgowandChalme rs).Thi#savoidsagreqatdTealoftUhe=highe ruGordTermÎachine rywhichi#softUenasqsoGciateduGwitUhimplementationsuGof=ove rloadinrg.ύ,Nelan[Nel91]dTeGsTcr*ib#esatsomelenrgtUhtUechniqueGsforwhathetUe rmeGd rsti c-,ation:ltUheaurtomÎaticlremovqalofhighe rordTerfurnctions.AltUhÎoughconve rs#ionlof,highe r-ordTeriprogramstro rst-orde rii#s,ingeneral,impGoqss#ible,iprogrammers,by,and83large,us1ehighe r-ordTer#neGsqs83ince rtainidiomÎaticwayswhichar}'eamenÎabletro, rsti cationDus#inrgNelan'smÎachine ry*.DThismÎachine ry*,Dcom|qbineGdwitUhaggresqs#ive,inlininrg,canb#eremÎarkablye ective.EvenwitUhÎourtus#ing rsti cation,mUuchof,tUheUUoptimi#s1eGdcodTedeqalrtwitUhins#ideGlasgowHaskelli#spurely rstordTe r.;F*romAastr*ictneGsqsanÎalys#isApointofview, rstAordTe ranÎalys#isAhastwomÎa8jor,advqantageGs:2@{=FixpGointinrgi#seqasie r.Thef*rontie rsalgor*itUhmrurnsreqasonÎablyquicklyfor= rstRordTe rexampleGs([Sew948],Section3),andtUe rmrewr*itebas1eGd xpointinrg=i#sguarantUeeGdtrowork.ComputingcompletUefunctiongraphsdo#eGsnotlook=quitUesobadintUhe rstordTe rcas1e,anddoinrgsomÎakeGsmoduleseqas#ie rtro=dTeqalUUwitUh.2@{=Polymorphic6gene rali#sationgiveGsexactresulrts.MonomorphicanÎalys#isand=itsUUattUendrantmoGdule-relatUedUUproblemscanb#eavoidTeGdentirely*.%,3 TheDefr9ive`dDes0ign$Y,3.1 Ov9e Drview$Y,Cons#idTe r*inrgtUhedeGs#ignconstraints,itlookslikea rst-ordTe r,polymorphicanÎa-,lys#iscompurtingcompletUe xeGdpointsmightformaplaus#iblebas#isforaworkinrg,systUem,ksotUhi#siswhathasb#eenconstructUeGd.Aqbqstractinte rpretationkproGduces,tUe rmsinwhatcanb#econsidTe reGdtrobeanabqstractlam|qbGdra-calculus,and xpGoint-,inrgHi#sdonewitUhatUe rm-rewr*iteHsystemwhichtransformss1emÎanticallyequivqalent,tUe rmsUUtrosyntacticallyUUidTenticalUUnormÎalforms.;TheXanÎalys1e rformspartoftUheGlasgowHaskellcompile r,andop#e ratUeGsona,dTeGsugaredHaskellformloGoqs1elyrefe rredtroasCore.Coreallowslam|qbdratUe rms,,applications,alitUe rals,loGcalbindinrgs,one-levelpattUe r#nmÎatchinrga(cases)andcon-,structrorapplications.Typ#einformÎationsupplieGdbypreviouscompile rphas1eGs,meqansftUhetyp#e(andhencetUheabqstractdomÎain)assoGciatUedwitUheve rysub#ex-,preGsqs#ion(\isknown.TheCoretreei#sannotatUeGdwitUhthestr*ictneGsqsinformÎation,compurtUeGd,^mÎakingitavqailabletrosuUbqs1equenttransformÎationpasqs1eGs,andtrotUhe,intUe rf#ace-pr*intinrgbmÎachinery*,bsootUhermoGdulesbcanknowabGourttUhestr*ictneGsqsof,furnctionsUUintUhi#sone. bg\32\ܚR3.2 Th9eTab s-tractin t"e DrpretaftionRAqbqstract)intUe rpretationsforstr*ictneGsqsanÎalys#ishavehi#stror*icallybeencatUegor- Ri#s1eGdBasforwardorbackward[Hug90>],alrtUhÎoughtheapp#eqaranceofrelationÎalana-Rlys1eGsi#snowblurr*inrgtUhatdi#stinction.BackwardanÎalys1eGsgene ratUeinformÎationRabGourtfunctionargumentsgivenknowleGdgeofsomeprop#e rtyoftUheapplicationRasޛawhÎole.F*orexample,backwardޛstr*ictneGsqsanÎalys#isofann-argurmentfunctionRproGducesH3nmÎapqs,oneforeachargurment,mÎappinrgdTemÎandonanapplicationtroRdTemÎandoneqachargurment.AstUhi#simplieGs,thefurndamentalabqstractentitieGsareRpGointsinlattices,whe redi erentpGointsdTenotUedi e rentdTemÎandsor\neeGdTed-RneGsqs"forsomedratastructure.Iti#susualtro(atleqastpGotUentially)alloweqachRdi e rent*concretUetyp#etrohaveitsownlatticeofabqstractdTemÎands,inordTe rtUhatRweUUcandodTetaileGdanÎalys1eswitUhdratastructureGs. PWaAlrtUhÎoughthe rststr*ictneGsqsanÎalys1eswe reoftUheforwardstyp#e,latUe rdTe-Rvelopment{TsuggeGstUedbackwardsanÎalys#ismightbequicke randgiveas#imple rRtreqatment$7ofpGolymorphi#sm,andpracticalworks1eemstrob#eqartUhisourt([Sew948],RSection5).Thefewpap#e rsshÎowinrghÎowstr*ictneGsqsinformÎationcanb#eus1eGdtroRgene ratUec&b#etterc&coGdTe[PJ93,Hal93G]alleitUhe rsuggestorimplytUhatbackwardsRinformÎationF.i#swhati#sactuallyus1eful.T*akentrogetUhe r,tUhecas1eforbuildinrgaRbackwardsUUabqstractintUe rpretations1eemsove rwhelminrg.aSpaceblimitationsprecludTemUuchdi#sTcusqsionoftUheabqstractintUe rpretation.RSuceittrosaytUhatiti#sfairlyconventionÎal:tUheove rallstructurei#ssimilartroRtUhatpreGs1entUedbyJohnHugheGsin[Hug90>],alrtUhÎoughthemechani#smfordTeqalinrgRwitUhdratastructureGs,constructrorsandcas1etUe rmsi#sdi erent.AswitUhanypurelyRbackward anÎalys#is,highe r-ordTeranÎalys#isisimpGoqss#ible,sowenÎaivelyasqsurmetUhatRallUUurnknownfunctionsdonotdTemÎandtUheGirargurmentsatall.aManypbackwardabqstractintUe rpretationsgotroagreqatdTealoftrouUbletromoGdTelRdratastructureGswell,tUhe reTbyinducinrgcons#idTe rablecomplicationintUhemÎachine ryRwhichdTeqalswitUhdratastructureGs{constructrorfunctionsandcases.F*orturnÎatUely,RtUheYpreGs1entationcanb#esimpli eGdbytUheobqs1e rvqationtUhat,providTeGdtUheabqstrac-Rtionnofcasesandconstructrorfunctionsob#eysce rtainconstraints,itdo#eGsn'tmÎat-RtUe r+p#e rformÎancehinrgeGsongeneratinrg>+smÎalltUermsandkeepinrgtUhemsmÎallRtUhroughÎourt/welladvis1eGdtrostr*ivetowards>tUhi#sgoal.Asanexample,PhilW*adle r'sor*i-RginÎala"non- atstr*ictneGsqsanalys#isa"sTcheme[W*ad87]gaveanintUe rpretationofcaseRexpreGsqs#ionseHwhichexpandsexpGonentiallywitUhthes#izeofinstantiatinrgtyp#eGs.ThisRrendTe rsݕitimpracticalforallburttUhetinieGstprograms([Sew948],Section5.8).OurRbackwardsf*rameworki#spGolymorphicallyinvqar*iant,soitavoidstUhatparticularRhÎorror,burtitstillhasplentyofpGotUentialforoptimi#sationus#inrgabqstractlets.RThevpGointoftUhi#sexampleistUhat,withalittlecare,muchvofthe\expGonentialnesqs"RcanUUb#eenrginee reGdaway*,givinrgsuUbqstantialp#e rformÎancebene ts. 7R4 Re`sultsэR4.1 InTtTh9esm}allэRThe6wtUechnologydTeGsTcr*ib#edabove6wwasconstructUeGdins#idTeapurpoqs1e-builrtdTevel-Ropment-`f*ramework.Thef*rameworki#saquick-and-dirtyimplementationoftUheRf*ront&partofacompile rforanoverloadinrg-f*ree&suUbqs1etofHaskell,dTeGs#igned&troRf#acilitatUeexpe r*imentation.Ahigher-ordTerremovqaltransformÎationintUhestyleRofLNelan[Nel91]allows rst-ordTe rLanÎalys1eGsofprogramsmakinrgsuUbqstantialLus1eRofhighe r-ordTerfurnctions.AllanÎalys1eGswe redonemonomorphically*,tromÎakeRcompar*i#sonwitUhaforwardintUe rpretationf#aire r.F*ortUhebackwardsanÎalys1eGs,RofLcours1e,tUhe rei#snointr*insicreqasontrous1emonomorphicanÎalys#is.LF*ourinpurtsRwe reUUus1eGd:gۍX@{cavlTree:UUins1e rtionofitUemsintroanAVLtree(44lineGs).X@{clife:XLaurnchbury'simplementationofConway's\life"s#imUulation(311lineGs).X@{cfft:F*astfour*ie rtransform,fromHartUel'sb#enchmÎarksuite[HL92a](421clineGs).X@{cida:UUSolveGstUhe15-puzzle,alsof*romHartUel'ssuite(728lineGs).M䍑alife,MfftandidaaresuUbqstantialinpurts.QuotUeGds#izesareaftUe rins1ertionofRsuitableipreludTefurnctions.TheymÎakesuUbqstantialus1eofhighe r-ordTerifurnctions,g\32\j͍?ForwCardsEvhalTrans wHeKadStr-qict Z˶ProgramHLτ ff ff\Tim9eHLτ ffgReAs idHLτ ff ffܤTim9eHLτ ffReAs idHLτ ff ff!ETim9eHLτ ffAReAs idYeP5ffU1keavlTree(Lτ ff ff;V`9.58HLτ ffc,1514HLτ ff ff0.23HLτ ff"3j cmti9197HLτ ff ff?0.27HLτ ff200 life(Lτ ff ff2d359.20HLτ ff^11203HLτ ff ff2.01HLτ ffm628HLτ ff ff?2.97HLτ ff615 ޑfft(Lτ ff ff6b28.76HLτ ffb!1473HLτ ff ff6.38HLτ ffj1473HLτ ff ff?8.38HLτ ff 1524 ޑida(Lτ ff ff6b920+HLτ ffW[54000+HLτ ff ff9.32HLτ ffj1725HLτ ff ff?7.70HLτ ff 1734:3,TaCble1.P9e rformanceofabNstractinte rpreters(t9imeins. econds,reAs id؇enciesinKb9ytes). ,It9alici s. eAd2 guresin9dicatep eNakres id؇enciesd؇e n9edb9ypreprocesNs ingph9as. es,ratTh9e rth9an,a9bNstract>inte rpretationor xpAointing.TheForwCardsanalys isofidadidnotcomplete,ev9enTin54megabyteAsofheNap.",which;vtUhe rsti e rhastroworkquitUehardtroremove,andwhichcaus1eGstUheinpurtto ,tUhe7abqstractintUe rpreter7prop#ertrob#econsidTe rablybiggertUhantheurntransformeGd,sourceGs. ꍑ;ThepNanÎalys1e rwaswr*ittUeninstandrardHaskell1.2,compileGdwitUhGlasgow,HaskellbS0.19\-O",andrurnonaquiet64-megabytUeSurnSparc10/31running,SurnOSv4.1.3.vOAgene rationÎalgarbagecollectrorwasus1eGd,andheqaps#izeGswe re,s1etyetrotryandkeepgarbagecollectioncoqstsb#elow10%,alrtUhÎoughforlarge rreGs-,idTencieGs.tUhi#sisdiculrt.TimeGsundTe rs#ixtys1econdsareave rageGdove rs#ixrurns.,TheyKfincludTetUhepreproGcesqs#inrgKftimesKfofpars#inrg,dTeGsugar*ing,typ#echecking,Kfmono-,morphi#sationgand rsti cation,burtinnocas1edotUheGs1eexceed20%oftUhetrotal.,T*able1UUshÎowstUhereGsulrts,us#ingtUhreedi e rentabqstractintUe rpretations:2@{=He adStr1ict:aheqadstr*ict,backwardsintUe rpretationpreci#s1elyasdTeGsTcr*ibed=inUUtUhi#spape r.2@{=Ev\ralT rans:anotUhe rbackwardsintUe rpretation,formeGd,aswitUhHeqadStr*ict,=us#inrg'ktUhegene r*icframework'kdTeGsTcrib#ed'kabove,'kburtus#ingas#imple rcharactUer-=i#sationSofdratastructureGs,esqs1entiallyagene rali#sationofGeo Bur#n'sEvqalu-=ationUUT*ransforme rs.2@{=F orw9ards:aforwardsBHA-styleintUe rpreter,witUhhandlinrgofdatastruc-=tureGstasdTesTcr*ib#edin[Sew918].Thedrata-structurehandlinrgcanb#econsidTe reGd=inUUas1enseUUof\equivqalent"dTetailtrotUhatofEvqalT*rans.,EachintUe rpreterwasmeqasureGdwitUharewr*itUe-bas1ed xpointUe rdTes#ignedsp#ecially,forit.Therewr*itUe rsareve rys#imilar,andbyus#inrgtUhesamekindofoptimi#sations,inUUeqachwehÎop#etromÎaketUhecompar*i#sonreqasonÎablyf#air.;TheGs1e1meqasurementsmÎakecleqarjustwhatanadvqantagetUhebackwardsintUe r-,pretations/have{tUheEvqalT*ransanÎalys#isofliferurnsalmoqsttwohUurndreGdtimeGs,f#astUe r6tUhantheforwardsanÎalys#is,6andinaf*ractionoftUhespace.TheHeqadStr*ict,intUe rpretation-i#snotsigni cantUlyslowe r-than-the-EvqalT*ransve rs#ion.ThiscomeGs,as'abitofasurpr*i#s1e,sinceonemightexp#ectittroproGducemUuchmoredTetail,,andltakecorreGspondinrglylonge r.Insp#ectionofoutʪputsreveqalstUhatitdo#eGsn't,alwaysap ndagreqatdTealmorestr*ictneGsstUhantheEvqalT*ransanÎalys#is.AndquitUe*.g\32\ܚRwhytUheHeqadStr*ictanÎalys#isshÎouldsometimeGsb#equicke r(forida)i#smystUe r*ious, RpGoqss#iblyUUduetrotUhepreci#s1edTetailsofreGductionpatUhsinthetUe rmrewr*ite rs.qmR4.2 InTtTh9elargeqmRAftUe rextens#iveturningintUhedTevelopmentf*ramework,tUhe(pGolymorphic)Heqad-RStr*icty}intUe rpretery}andits xpGointUerwereinstalleGdinGlasgowHaskell0.19troRasqs1eGss+tUheviabilityofsuchstr*ictneGsqsanÎalys#is+\intUhelarge".IntUegrationaddTeGdRabGourt5700non-blank,non-commentlineGsofcodTetroanexi#stingtotalofabGourtR50000.]Becaus1etUhecompile ri#swelldTeGs#igned,]intUegrationwasremÎarkablycleqan,RwitUhthesmÎalleGstofmodi cationstroexi#stinrgcoGdTe.Theexi#stinrgf*rameworkforRtransmittinrg=-pragmÎaticinformÎationb#etweenmoGdules=-wasextUendTeGdtroallowfullRintUe rmoGdule\anÎalys#is;giventUheargurmentspreGs1entUed\inSection2,tUheexp#e r*imentRwouldUUhaveb#eenlargelywortUhleGsqshadtUhi#sbeenomittUeGd.aCompilinrgGlasgow'simplementationoftUheHaskellPrelude,plussomeotUhe rRgene ral-purpGoqs1eIlibrar*ies,trotallingabGout4000lineGs,takeGssomefourhÎoursonaRSurnSparcStationIPX,roughlyadouUblinrgoftheno-anÎalys#istime.Aheqaps#izeRofbT24megabytUeGsbTprovedbTmoretUhanadTequatUe,and,pleqas#inrgly*,tUhe rewasnoneeGdRtroijreGsorttotUhetree-pruningdTeGsTcr*ib#edijinSection3.3.Aneqarlie rve rs#ionoftUheRanÎalys1e r,sinitsdTevelopmentsf*ramework,sconstiturtings13000lineGsin28modules,RwassuUbqs1equentlycompileGd.25moduleswenttUhroughwithnoproblems,whilstRtUhreeUUrequireGdprurning.aByt7anystandrards,suchexp#e r*imentationwitUhreqalcompile rsandreqalpro-RgramsglendsmÎa8jorcreGdibilitytrotUheenrginee r*inggdTeGsTcrib#edgintUhispape r.Ob-Rs1e rvqation\oftUheintUe rpreter\and xpGointUergrapplinrgwitUhnon-toyinputsleqadtoRmÎany5Hre nements,andtrotUhesuggeGstionsforfurtUhe rdTevelopmenttrowardstUheRendUUofSection3.4.R4.3 Conclus(ionsqmRThe`abqstractintUe rpreter`and xpGointinrgmechani#smourtUlineGdabGovehaveb#eenRdTevelop#eGdXandturneGdbyrurnningtUhemove rapproximÎatUelytwentytUhÎousandlineGsRofQHaskellsourcecoGdTe.Asqs1ess#inrgQtUheviabilityofnewsTchemeGsonlyonsmÎallex-RampleGsorus#inrgpape ranÎalys1eGscanbemisleqadinrg.GoGodenginee r*ingrequireGsnotRonlyFsuppGortinrgtUheory{ofwhichtUhe eldshÎowsnoshÎortage{burtalsoextUens-Rive8quantitativeanÎalys#isonreqalistic-sizeGdinpurts.Therelativelackofe ectiveRimplementationsIofstr*ictneGsqsandotUhe rs1emÎanticanÎalys1eGsforHaskellhighlightsRtUheUUneeGdforfurtUhe rattUentiontroenginee r*ingi#sqsueGsinabstractintUe rpretation.aUs#inrgYtUheGs1epr*inciples,apolymorphicpro8jectionanÎalys1e rforHaskellhasb#eenRcreqatUeGd.TheanÎalys1e ri#se ective,robust,reliable,tur#nsingoGodpe rformÎances,Randhasb#eenus1eGdtrosuppGortres1eqarchinaurtomÎaticstr*icti cationofHaskellRprograms^4|s.QItalsolaysourtadTeGs#ignwitUhconsidTe rablepGotUentialforre nement,RparticularlywitUhreGsp#ecttrobuildingmoreeconomicalabqstractintUe rpretations,RandGtro xingshar*ingproblemsintUhe xpGointinrgmechani#sm.F*urtUhe rdTevelopmentRmÎayUUyieldimpreGsqs#ivestr*ictneGsqsandshar*inrganÎalys1eGsforHaskell.Rff8ϟ L͍-=4 ?Deni sTHo9we,DepartmentofComputing,TImp e r'xialCollege,Lon9don.A g\32\ܚ,Refefrence`s#f,[AFM-=+n95]ZxZena'Ar'xiola,Mat3tThiasF:elleAi s. en,JohnMaraist,Mart9inOd؇e rsky:,an9dPhilip XaW:adle r.MAocall-b9y-neeAdlamPbdacalculus.MIn22ndUSymposiumonPrinciplesXaof6ProgrammingLanguages,SanF:ranci s!co,California,JanTuary1995.A9CMXaPreAsNs.,[A|rug93]XaLennartLA|rugustfsNson.Implem9entinghaskellove rloading.InProceedings۹ofXatheFJunctionalProgrammingLanguagesandComputerAÎrchitectureConfer-Xaence,N cmmi10 0ercmmi7K`y cmr10ٓRcmr7u cmex10