This volume contains the revised lecture notes corresponding to the lectures given at the 6th International School on Advanced Functional Programming, AFP 2008, held in Heijen, a little village in the woodlands near the city of Nijmegen, The Netherlands, May 19-24, 2008. AFP 2008 was co-located with TFP 2008, the 9th Symposium on Trends in Functional Programming [see P. Achten,P.Koopman,M.Marazan ' : Trends in Functional Programming volume 9, ISBN 978-1-84150-277-9,Intellect]. The school attracted 62 participants from 19 countries, a record, including the lecturers and organizers. This event was precededby?veearlierinstancesinB? astad,Sweden(1995,LNCS925),Olympia, WA, USA (1996, LNCS 1129), Braga,Portugal(1998, LNCS 1608), Oxford, UK (2002, LNCS 2638) and Tartu, Estonia, (2004, LNCS 3622). The goals of the series of Advanced Functional Programming schools are: - Bringing computer scientists, in particular young researchers and progr- mers, up to date with the latest functional programming techniques. - Showinghowtouseadvancedfunctionalprogrammingtechniquesin"progr- ming in the real world". - Bridgingtheeducationalgapbetweenresultspresentedatconferencesonthe one side and material as presented in introductory textbooks on the other side.

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 Jos'eOliveira VII Sponsorship Theschoolhasreceivedgeneroussponsorshipfrom: FCT-Fundac",aoparaaCienciaeTecnologia,Minist'eriodaCienciae Tecnologia AdegaCooperativadePontedeLima AgenciaAbreu CGD-CaixaGeraldeDep'ositos CIUM-CentrodeInform'aticadaUniversidadedoMinho DI-DepartamentodeInform'aticadaUniversidadedoMinho GEPL-GrupodeEspeci?cac",aoeProcessamentodeLinguagens LESI-Direc,c"aodeCursodeEngenhariadeSistemaseInform'atica Enabler Lactolima Latic'?niosdasMarinhas,Lda NovabasePorto-SistemasdeInforma,c"aoSA PrimaveraSoftware ProjectoCamila-GrupodeM'etodosFormais Sidereus-SistemasdeInforma,c"aoeConsultoriaInformat'icaLda SIBS-SociedadeInterbanc'ariadeServico,s VieiradeCastro LocalCommittee: Jos'eAlmeida,Minho Lu'?sBarbosa,Minho Jos'eBarros,Minho M. Joao " Frade,Minho PedroHenriques,Minho F. M'arioMartins,Minho F. LuisNeves,Minho CarlaOliveira,Minho JorgePinto,Lix JorgeRocha,Minho CesarRodrigues,Minho Joa"oSaraiva,Minho M. Joa"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 Jos'eOliveira VII Sponsorship Theschoolhasreceivedgeneroussponsorshipfrom: FCT-Fundac"caoparaaCienciaeTecnologia,Minist'eriodaCienciae Tecnologia AdegaCooperativadePontedeLima AgenciaAbreu CGD-CaixaGeraldeDep'ositos CIUM-CentrodeInform'aticadaUniversidadedoMinho DI-DepartamentodeInform'aticadaUniversidadedoMinho GEPL-GrupodeEspeci?cac"caoeProcessamentodeLinguagens LESI-Direccc"aodeCursodeEngenhariadeSistemaseInform'atica Enabler Lactolima Latic'?niosdasMarinhas,Lda NovabasePorto-SistemasdeInformacc"aoSA PrimaveraSoftware ProjectoCamila-GrupodeM'etodosFormais Sidereus-SistemasdeInformacc"aoeConsultoriaInformat'icaLda SIBS-SociedadeInterbanc'ariadeServicocs VieiradeCastro LocalCommittee: Jos'eAlmeida,Minho Lu'?sBarbosa,Minho Jos'eBarros,Minho M. Joao " Frade,Minho PedroHenriques,Minho F. M'arioMartins,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...4 2. 3 TheListHylomorphism...5 2. 4 InsertionSort...6 2. 5 SelectionSorts...7 3 LeafTrees...9 3. 1 TheLeaf-TreeCatamorphism...9 3. 2 TheLeaf-TreeAnamorphism...10 3. 3 TheLeaf-TreeHylomorphism...11 3. 4 MergeSort...12 4 BinaryTrees...13 4. 1 TheTreeCatamorphism...13 4. 2 TheTreeAnamorphism...14 4. 3 TheTreeHylomorphism...14 4. 4 Quicksort...15 4. 5 HeapSort...16 5 Paramorphisms...18 5. 1 TheListParamorphism...18 5. 2 InsertAsParamorphism...18 5. 3 RemoveAsParamorphism...19 6 GeneralizingDataStructures...20 6. 1 GeneralizingQuicksort...20 6. 2 GeneralizingHeapSort...21 7 Conclusions...23 GenericProgramming-AnIntroduction-...28 RolandBackhouse,PatrikJansson,JohanJeuring,LambertMeertens 1 Introduction...

This is the second time that of ESOP has formed part of the ETAPS cluster of conferences, workshops, working group meetings and other associated activities. One of the results of colocatingso many conferences is a reduction in the number of possibilities to submit a paper to a European conference and the increased competition between conferences that occurs when boundaries between indiv- ual conferences have not yet become well established. This may have been the reason for the fact that only 44 submission were received this year. On the other hand we feel that the average quality of submissions has gone up, and thus the program committee was able to select 18 good papers, only one less than the year before. The program committee did not meet physically, and all discussion was done usinga Web-driven data base system. Despite some mixed feelings there is an overall tendency to appreciate the extra time available for giving papers a s- ond look and really going into comments made by other program committee members. I want to thank my fellow program committee members for the work they have put into the refereeingprocess and the valuable feedback they have given to authors. I want to thank the referees for their work and many detailed comments, and ?nally I want to thank everyone who has submitted a paper: without authors, no conference.

This book constitutes the refereed proceedings of the Eighth International Symposium on Programming Languages, Implementations, Logics, and Programs, PLILP '96, held in conjunction with ALP and SAS in Aachen, Germany, in September 1996.
The 30 revised full papers presented in the volume were selected from a total of 97 submissions; also included are one invited contribution by Lambert Meerlens and five posters and demonstrations. The papers are organized in topical sections on typing and structuring systems, program analysis, program transformation, implementation issues, concurrent and parallel programming, tools and programming environments, lambda-calculus and rewriting, constraints, and deductive database languages.

This book constitutes the proceedings of the Seventh International Symposium on Programming Languages: Implementations, Logics and Programs, PLILP '95, held in Utrecht, The Netherlands, in September 1995.
The book presents 26 refereed full papers selected from 84 submissions; they report research on declarative programming languages and provide insights in the relation between the logic of those languages, implementation techniques, and the use of these languages in constructing real programs. In addition there are abstracts or full presentations of three invited talks as well as eight posters and demonstrations.

This book constitutes the proceedings of the 19th Brazilian Symposium on Progamming Languages, SBLP 2015, held in Belo Horizonte, Brazil, in September 2015. The 10 papers presented in this volume were carefully reviewed and selected from 26 submissions. They deal with fundamental principles and innovations in the design and implementation of programming languages and systems.