Advanced Functional Programming: Third International School, Afp'98, Braga, Portugal, September 12-19, 1998, Revised Lectures

ISBN-13: 9783540662419 / Angielski / Miękka / 1999 / 298 str.

S. D. Swierstra; P. R. Henriques; J. N. Oliveira

Opis

Inthisvolumeyouwill?ndthelecturenotescorrespondingtothepres- rd tationsgivenatthe3 summerschoolonAdvancedFunctionalProgramming, heldinBraga, PortugalfromSeptember12 19,1998. ThisschoolwasprecededbyearlieronesinB?astad(1995, Sweden, LNCS925) andOlympia, WA(1996, USA, LNCS1129). Thegoalofthisseriesofschoolsis tobringrecentdevelopmentsintheareaoffunctionalprogrammingtoalarge groupofstudents. Thenotesarepublishedinordertoenableindividuals, small studygroups, andlecturerstobecomeacquaintedwithrecentworkinthefast developingareaoffunctionalprogramming. Whatmadethisschoolparticularlyinterestingwasthefactthatalllectures introducedusefulsoftware, thatwasusedbythestudentsintheclassestoget hands-onexperiencewiththesubjectstaught. Weurgereadersofthisvolumeto downloadthelatestversionofthissoftwarefromtheInternetandtrytodothe exercisesfromthetextthemselves;theproofoftheprogramisinthetyping. The?rstlecture, onSortingMorphisms, servesasagentleintroductiontothe thingstocome. Ifyouhavealwaysbeenafraidoftheword morphism, andyou havebeenwonderingwhatcatamorphisms, anamorphisms, hylomorphims, and paramorphimswereabout, thisisthepapertoread?rst;youwilldiscoverthat theyaremerelynamesforrecursionpatternsthatoccuroverandoveragainwhen writingfunctionalprograms. Thealgorithmsinthepaperareallaboutsorting, andsinceyouarelikelytoknowthosealgorithmsbyheartalready, seeingthem structuredandanalyzedinanovelwayshouldserveasamotivationtoreadon tothesecondlecture. Thesecondlecture, onGenericProgramming, isalmostabookinabook. ThenotescanbeseenastheculminatingpointoftheSTOP-project, sponsored bytheDutchgovernmentattheendofthe80 sandthebeginningofthe90 s. Its overallgoalwasthedevelopmentofacalculationalwayofderivingprograms. The projecthasprovideddeeperinsightintorealfunctionalprogrammingandinto thetheorybehindmanythingscommonlywrittenbyfunctionalprogrammers. Oneofthemainachievementsoftheprojecthasbeentomakepeopleaware ofthefactthatmanyalgorithmscanbedescribedinadata-independentway. ThePolyPsystemintroducedinthesenotesisoneofthetranslationstothe Haskell-worldofthistheoreticalunderpinning. Thethirdlecture, onGenericProgramTransformation, canalsobeseenas anapplicationofthetheoryintroducedinlecturetwo. Manye?ciency-improving programtransformationscanbeperformedinamechanicalway, andthesewould nothavebeenpossiblewithoutinsightintothecorrectnessofsuchtransfor- tionsgainedinthelectureonGenericProgramming. Thefourthlecture, onDesigningandImplementingCombinatorLanguages, introducesaneasytowriteformalismforwritingdownthecatamorphismsint- ducedinearlierchapters. Itisshownhowquitecomplicatedcatamorphisms, that at?rstsightseemratherforbiddingbymakingextensiveuseofhigher-orderdo- VI Preface mains, canactuallybedevelopedinastep-wisefashion, usinganattributegr- marview;itisfurthermoreshownhowtorelatethiswayofprogrammingwith conceptsfromtheobject-orientedworldthusmakingclearwhatthestrengths andweaknessesofeachworldare. The?fthlecture, titledUsingMetaML: AStagedProgrammingLanguage, introducestheconceptofpartialevaluation. Itservesasanotherinstanceof thequestfor themostgenericofwritingprogramsatthelowestcost . The stagingtechniquesshowhowcoststhatwereintroducedbyaddingextralevels ofabstraction, maybemovedfromrun-timetocompile-time. Ithasbeencommonknowledgetousersofmodernfunctionallanguagesthat thetypesystemcanbeagreathelpinshorteningprogramsandreducingerrors. Intheextremeonemightseeatypeasapredicatecapturingtheproperties ofanyexpressionwiththattype. InthesixthlectureonCayenne Spiceup yourProgrammingwithDependentTypesitisshowninwhatdirectionfunctional languagesaremostlikelytodevelop, andwhatmaybeexpectedofthenewtype systemstobeintroduced. Thelastlecture, titledHaskellasanAutomationController, showsthat writingfunctionalprogramsdoesnothavetoimplythatoneisboundtoremain isolatedfromtherestoftheworld. Beingabletocommunicatewithsoftware writtenbyothersinauniformway, isprobablyoneofthemostinteresting newdevelopmentsincurrentcomputerscience. Itappearsthattheconceptofa monadtogetherwiththeHaskelltypingrules, isquiteadequatetodescribethe interfacebetweenHaskellprogramsandtheouterworld. Finallywewanttothankeveryonewhocontributedtothisschoolandmade itsuchasuccessfulevent: sponsors, localsystemmanagers, localorganizers, students, andlastbutnotleastthelecturers. Weareconvincedthateveryone presentattheschoolenjoyedthiseventasmuchaswedid, andweallhopethat youwillfeelsomeofthespiritofthiseventwhenstudyingtheselecturenotes. March1999 DoaitseSwierstra PedroHenriques JoseOliveira VII Sponsorship Theschoolhasreceivedgeneroussponsorshipfrom: FCT-Fundac, aoparaaCi enciaeTecnologia, MinisteriodaCi enciae Tecnologia AdegaCooperativadePontedeLima Ag enciaAbreu CGD-CaixaGeraldeDepositos CIUM-CentrodeInformaticadaUniversidadedoMinho DI-DepartamentodeInformaticadaUniversidadedoMinho GEPL-GrupodeEspeci?cac, aoeProcessamentodeLinguagens LESI-Direc, c aodeCursodeEngenhariadeSistemaseInformatica Enabler Lactolima Latic?niosdasMarinhas, Lda NovabasePorto-SistemasdeInforma, c aoSA PrimaveraSoftware ProjectoCamila-GrupodeMetodosFormais Sidereus-SistemasdeInforma, c aoeConsultoriaInformaticaLda SIBS-SociedadeInterbancariadeServico, s VieiradeCastro LocalCommittee: JoseAlmeida, Minho Lu?sBarbosa, Minho JoseBarros, Minho M. Joao Frade, Minho PedroHenriques, Minho F. MarioMartins, Minho F. LuisNeves, Minho CarlaOliveira, Minho JorgePinto, Lix JorgeRocha, Minho CesarRodrigues, Minho Joa oSaraiva, Minho M. Joa oVaranda, Minho IX TableofContents SortingMorphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 LexAugusteijn 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 MorphismsonLists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. 1 TheListCatamorphism. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. 2 TheListAnamorphism. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Spis treści

Sorting Morphisms.- Generic Programming.- Generic Program Transformation.- Designing and Implementing Combinator Languages.- Using MetaML: A Staged Programming Language.- Cayenne — A Language with Dependent Types.- Haskell as an Automation Controller.