搜索
AdaptiveFuntionalProgramming UmutA.AarGuyE.BlellohRobertHarperJanuary11,2002CMU-CS-01-161ComputerSieneDepartmentCarnegieMellonUniversityPittsburgh,PA15213AbstratAnadaptiveomputationmaintainstherelationshipbetweenitsinputandoutputastheinputhanges.Althoughvarioustehniquesforadaptiveomputinghavebeenproposed,theyremainlimitedintheirsopeofappliability.Weproposeageneralmehanismforadaptiveomputingthatenablesonetomakeanypurely-funtionalprogramadaptive.WeshowthatthemehanismispratialbygivinganeÆientimplementationasasmallMLlibrary.Thelibraryonsistsofthreeoperationsformakingaprogramadaptive,plustwooperationsformakinghangestotheinputandadaptingtheoutputtothesehanges.Wegiveageneralboundonthetimeittakestoadapttheoutput,andbasedonthis,showthatanadaptiveQuiksortadaptsitsoutputinlogarithmitimewhenitsinputisextendedbyonekey.Toshowthesafetyandorretnessofthemehanismwegiveaformalde nitionofAFL,aall-by-valuefuntionallanguageextendedwithadaptivityprimitives.ThemodaltypesystemofAFLenforesorretusageoftheadaptivitymehanism,whihanonlybehekedatruntimeintheMLlibrary.BasedontheAFLdynamisemantis,weformalizethehange-propagationalgorithmandproveitsorretness.1IntrodutionAnadaptiveprogramrespondstoinputhangesbyupdatingitsoutputwhileonlyre-evaluatingthoseportionsoftheprograma etedbythehange.Adaptiveprogrammingisusefulinsituationswhereinputhangesleadtorelativelysmallhangesintheoutput.Inlimitingasesoneannotavoidaompletere-omputationoftheoutput,butinmanyasestheresultsofthepreviousomputationmaybere-usedtoobtaintheupdatedoutputmorequiklythanaompletere-evaluation.Forexample,asweshallseebelow,anadaptiveversionofQuiksorttakesexpetedlogarithmitimetoadaptitsoutputwhenitsinputlistisextendedbyonekey.Thisisanimprovementbyalinearfatoroversimplyre-evaluatingthesortforthehangedinputs. ThisresearhwassupportedinpartbyNSFgrantsCCR-9706572,CCR-0085982,andCCR-0122581.Thisreportisaompleteversionof[1℄.1Inthispaperweproposeageneralmehanismforadaptiveprogramming.Ourproposedmehanismextendsall-by-valuefuntionallanguageswithasmallsetofprimitivestosupportadaptiveprogramming.Apartfromrequiringthatthehostlanguagebepurelyfuntional,wemakenootherrestritiononitsexpressivepower.Inpartiularourmehanismisompatiblewiththefullrangeofe et-freeonstrutsfoundinML.Ourproposedmehanismhasthesestrengths: Generality:Itappliestoanypurelyfuntionalprogram.Theprogrammeranbuildadaptivityintoanappliationinanaturalandmodularway. Flexibility:Itenablestheprogrammertoontroltheamountofadaptivity.Forexam-ple,aprogrammeranhoosetomakeonlyoneportionoraspetofasystemadaptive,leavingtheotherstobeimplementedonventionally. Simpliity:Itrequiressmallhangestoexistingode.Forexample,theadaptiveversionofQuiksortpresentedinthenextsetionrequiresonlyminorhangestothestandardimplementation. EÆieny:ThemehanismadmitsasimpleimplementationandyieldseÆientadap-tivity.Forexample,theadaptiveversionofQuiksortupdatestheoutputinexpetedO(logn)timeuponextensiontotheinput.Ouradaptivitymehanismisbasedontheideaofamodi ablereferene(ormodi able,forshort)andthreeoperationsforreating(mod),reading(read),andwriting(write)modi ables.Amodi ableallowsustoreordthedependeneofoneomputationonthevalueofanother.Amodi ablerefereneisessentiallyawrite-onerefereneellthatreordsthevalueofanexpressionwhosevaluemayhangeasa(diretorindiret)resultofhangestotheinputs.Anyexpressionwhosevalueanhangemuststoreitsvalueinamodi ablereferene;suhanexpressionissaidtobehangeable.Expressionsthatarenothangeablearesaidtobestable;stableexpressionsarenotassoiatedwithmodi ables.Anyexpressionthatdependsonthevalueofahangeableexpressionmustexpressthisdependenebyexpliitlyreadingtheontentsofthemodi ablestoringthevalueofthathangeableexpression.Thisestablishesadatadependenybetweentheexpressionreadingthatmodi able,alledthereader,andtheexpressionthatdeterminesthevalueofthatmodi- able,thewriter.Sinethevalueofthemodi ablemayhangeasaresultofhangestotheinput,thereadermustitselfbedeemedahangeableexpression.Thismeansthatareaderannotbeonsideredstable,butmayonlyappearaspartofahangeableexpressionwhosevalueisstoredinsomeothermodi able.Byhoosingtheextenttowhihmodi ablesareusedinaprogram,theprogrammeranontroltheextenttowhihitisabletoadapttohange.Forexample,aprogrammermaywishtomakealistmanipulationprogramadaptivetoinsertionsintoanddeletionsfromthelist,butnotunderhangestotheindividualelementsofthelist.Thisanberepresentedinourframeworkbymakingonlythe\tailelementsofalistadaptive,leavingthe\headelementsstable.However,oneertainaspetsaremadehangeable,allpartsoftheprogramthatdependonthoseaspetsare,byimpliation,alsohangeable.Thekeytoadaptingtheoutputtohangeofinputistoreordthedependeniesbetweenreadersandwritersthatariseduringtheinitialevaluation.Thesedependeniesmaybemain-tainedasagraphinwhiheahnoderepresentsamodi able,andeahedgerepresentsareadwhosesoureisthemodi ablebeingreadandwhosetargetisthemodi ablebeingwritten.2Also,eahedgeistaggedwiththeorrespondingreader.Wheneverthesouremodi ablehanges,thenewvalueofthetargetisdeterminedbyre-evaluatingtheassoiatedreader.Itisnotenough,however,tomaintainonlythisdependenygrap