Advanced Functional Programming
Third International School, AFP'98, Braga, Portugal, September 12-19, 1998, Revised Lectures
Published on 7. July 1999
Book
Paperback/Softback
XIV, 298 pages
978-3-540-66241-9 (ISBN)
Description
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...
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...
More details
Series
Edition
1999 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
XIV, 298 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 17 mm
Weight
476 gr
ISBN-13
978-3-540-66241-9 (9783540662419)
DOI
10.1007/10704973
Schweitzer Classification
Other editions
Additional editions
S. Doaitse Swierstra | Pedro R. Henriques | Jose N. Oliveira
Advanced Functional Programming
Third International School, AFP'98, Braga, Portugal, September 12-19, 1998, Revised Lectures
E-Book
12/2006
Springer
€53.49
Available for download
Content
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.