Advanced Functional Programming - Third International School, AFP'98, Braga, Portugal, September 12-19, 1998, Revised Lectures (Paperback, 1999 ed.)

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...

General

Imprint:	Springer-Verlag
Country of origin:	Germany
Series:	Lecture Notes in Computer Science, 1608
Release date:	2001
First published:	1999
Editors:	S.Doaitse Swierstra • Pedro R Henriques • Jose N. Oliveira
Dimensions:	235 x 155 x 16mm (L x W x T)
Format:	Paperback
Pages:	298
Edition:	1999 ed.
ISBN-13:	978-3-540-66241-9
Categories:	Books > Computing & IT > Computer programming > Programming languages > General Promotions
LSN:	3-540-66241-3
Barcode:	9783540662419

Is the information for this product incomplete, wrong or inappropriate? Let us know about it.

Does this product have an incorrect or missing image? Send us a new image.

Is this product missing categories? Add more categories.

Review This Product

No reviews yet - be the first to create one!