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

Auteur: S. D. Swierstra
Taal: Engels
Advanced Functional Programming
  • Engels
  • Paperback
  • 9783540662419
  • Druk: 1999 ed.
  • juli 1999
  • 298 pagina's
Alle productspecificaties

Samenvatting

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

Productspecificaties

Inhoud

Taal
Engels
Bindwijze
Paperback
Druk
1999 ed.
Verschijningsdatum
1999-07-07
Aantal pagina's
298 pagina's
Illustraties
Nee

Betrokkenen

Auteur
S. D. Swierstra P. R. Henriques
Co-auteur
P. R. Henriques
Redacteur
P.R. Henriques
Co-redacteur
Oliveira, Jose N.
Uitgever
Springer

EAN

EAN
9783540662419

Overige kenmerken

Extra groot lettertype
Nee
NUR code
958
Oorspronkelijke releasedatum
1999-07-07
Subtitel
Third International School, AFP'98, Braga, Portugal, September 12-19, 1998, Revised Lectures
Thema Subject Code
UM

Je vindt dit artikel in

Categorieën
Boek, ebook of luisterboek?
Boek
Taal
Engels
Software taal
Algemeen
Studieboek of algemeen
Algemene boeken
Nog geen reviews
Bindwijze: Paperback
78 50
2 - 4 weken Tooltip
Verkoop door bol.com
  • Gratis verzending
  • 30 dagen bedenktijd en gratis retourneren
  • Ophalen bij een bol.com afhaalpunt mogelijk
  • Dag en nacht klantenservice