A generic program for sequential decision processe

AGenericProgramforSequentialDecisionProcessesOegedeMoorProgrammingResearchGroup,OxfordUniversityComputingLaboratoryWolfsonBuilding,ParksRoad,OxfordOX13QD,UK1MotivationAgenericprogramforaclassofproblemsisaprogramwhichcanbeusedtosolveeachprobleminthatclassbysuitablyinstantiatingitsparameters.ThemostcelebratedexampleofagenericprogramisthealgorithmofAho,HopcroftandUllmanforthealgebraicpathproblem[1].Herewehaveasingleprogram,pa-rameterisedbyanumberofoperators,thatsolvesnumerousseeminglydisparateproblems.Furthermore,theapplicabilityofthegenericprogramiselegantlystatedastheconditionthattheparametersformaclosedsemi-ring.Examplesofsuchgenericalgorithmsareadmittedlyscarce,andonemightbeledtobelievethatthemajorityofprogramscannotbeexpressedinsuchagenericmanner.Ipersonallydonotsharethatview,forthefollowingtworeasons:Firstly,littleeorthasgoneintoattemptstoclassifyexistingalgorithms,reectingthefactthatthecomputingcommunityasawholeplacesmorevalueontheinventionofnewalgorithmsthanontheorganisationofexistingknowledge.Incertainspecialisedareaswhereorganisationaltoolsareindispensable(forexampleinthedesignofarchitecture-independentparallelalgorithms),numerousgenericalgorithmshavebeendiscovered,andformthecoreofthesubject[13].Secondly,toexpressgenericalgorithmsonerequiresahigher-ordernotationinwhichbothprogramsandtypescanbeparameterstootherprograms.Suchhigher-ordernotationsencouragetheprogrammertoexploitgenericitywherepossible,andindeedmanyfunctionalprogrammersnowdosoasamatterofcourse.Moretraditionalprogrammingnotationsdonotoersimilarsupportforwritinggenericprograms.Thispaperisanattempttopersuadeyouofmyviewpointbypresentinganovelgenericprogramforacertainclassofoptimisationproblems,namedsequen-tialdecisionprocesses.ThisclasswasoriginallyidentiedbyRichardBellmaninhispioneeringworkondynamicprogramming[4].Itisaperfectexampleofaclassofproblemswhichareverymuchalike,butwhichhasuntilnowescapedsolutionbyasingleprogram.ThosereaderswhohavefollowedsomeoftheworkthatRichardBirdandIhavebeendoingoverthelastveyears[6,7]willrecognisemanyindividualexamples:allofthesehavenowbeenunied.Thepointofthisobservationisthatevenwhenyouareonthelookoutforgenericprograms,itcantakearatherlongtimetodiscoverthem.Thepresentationbelowwillfollowthatearlierwork,byreferringtothecalculusofrelationsandtherelationaltheoryofdatatypes.Ishallhoweverattempttobelightontheformalism,asIdonotregarditasessentialtothemainthesisofthispaper.Undoubtedlythereareother(perhapsmoreconvenient)notationsinwhichthesameideascouldbedeveloped.ThispaperdoesassumesomedegreeoffamiliaritywithalazyfunctionalprogramminglanguagesuchasHaskell,Hope,Miranda1orGofer.Infact,theLaTEXleusedtoproducethispaperisitselfanexecutableGoferprogram.2SequentialDecisionProcessesManyoptimisationproblemscanbespeciedintheformspecrpgen=listminr.filterp.genHerethegeneratorgengeneratesalistofcandidatesolutions,filterpselectsthosesolutionswhicharefeasible(thosethatsatisfythepredicatep),andnallytheselectorlistminrpicksaminimumsolutionaccordingtotheorderrelationr.Sequentialdecisionprocessesaredistinguishedfromotheroptimisationprob-lemsinthewaythegeneratorisformulated.Thesequentialnatureofthegenera-toriscapturedbyexpressingitasaninstanceofthefunctionfold2.Informally,foldisdenedbytheequationfoldadde[a1,a2,...,an]=a1‘add‘(a2‘add‘...(an‘add‘e))Inwordsonemightsaythatfoldaddextraversesthelistxfromrighttoleft,startingwiththeseedvaluee,andsummingwiththeoperatoraddateachstep.Therecursivedenitionoffoldisfoldadde[]=efoldadde(a:x)=a‘add‘(foldaddex)Inasequentialdecisionprocess,wehavegen=foldfe1MirandaisatrademarkofResearchSoftwareLtd.2Thefunctionfoldisnormallycalledfoldr.BecauseIshalldeviatefromthecommondenitionoffoldr1,Ihavedecidedtousefoldandfold1toavoidconfusion.andateachstep,theoperatorfoersanondeterministicchoicebetweenanumberofalternatives.Itisthischoicethataccountsforthetermdecisionprocess.Thealternativesarepresentedasalistofoperators,andthespecicationofasequentialdecisionprocessthereforereadssdp_specrpfsc=listminr.filterp.fold(choicefs)[c]choicefsaxs=[fax|f-fs,x-xs]Thatis,ateachstepwehavethechoiceofapplyinganyoftheoperatorsfromfstoanyoftheresultssofarproducedinxs.Cognoscentiwillrecognisearelationalfoldhere[2].Theabovecanbevariedslightlyaccordingtothekindoflistsoneworkswith.Forinstance,fornon-emptyliststhecounterpartoffoldisfold1fg[a]=gafold1fg(a:x)=fa(fold1fgx)Thatis,thefunctiongisappliedtothelastelementofthelist,andthenwesumfromrighttoleftusingthefunctionf.Modifyingthenotionofsequentialdecisionprocessaccordingly,oneobtainssdp1_specrpfsl=listminr.filterp.fold1(choicefs)l’wherel’a=[la]Notethatthisdiersfromthedenitionofsdpspecinthebasecaseonly.Belowweshallalsohaveauseforlistswithatleasttwoelements.Againfoldcanbemodiedforthisparticulardatatype:fold2fg[a,b]=gabfold2fg(a:x)=fa(fold2fgx)Inwords,gisappliedtothelasttwoelementsofthelist,andthenwesum(asbefore)fromrighttoleft,usingthefunctionf.Thecorrespondingnotionofsequentialdecisionprocessisgivenbysdp2_specrpfsl=listminr.filterp.fold2(choicefs)l’wherel’ab=[lab]Th