Generic Programming

ThisvolumecontainscontributedpapersfromparticipantsintheGenericP- gramming Seminar held 27 April 1May1998atthDagstuhl e Conference CenterinWadern,Germany. Genericprogrammingisasub-disciplineofcomputersciencethatdealswith ?nding abstract representations of e?cient algorithms, data structures, and other software concepts, and with their systematic organization. The goal of genericprogrammingistoexpressalgorithmsanddatastructuresinabroadly adaptable,interoperableformthatallowstheirdirectuseinsoftwareconstr- tion. Amongthemostobviousachievementsofthisrelativelynewprogramming paradigmarenewlibrariesofsoftwarecomponents,bothinareasoffundam- talandbroadlyusedalgorithmsanddatastructures theStandardTemplate Library andinmorespecializedareassuchascomputeralgebra,graphtheory, and computational geometry. As useful as such components may be, however, theyareprobablylessimportantthantheoverallgenericprogrammingmeth- ologybeingdeveloped. Thepaperscollectedherearereportsfromthe?eldonthe majorproblemsandemergingsolutionsofgenericprogrammingmethodology. June2000 MehdiJazayeri Rudige rLoos DavidMusser VI Organization Organization The Generic Programming Seminar was held 27 April 1May 1998 at the ConferenceCenteroftheSchloßDagstuhl,locatedinWadern,Germany(near Saarbruc ken). Therewerefortynineattendeesfromtencountries. Theformal programofthemeetingincludedthirtysevenlectures,apanelsessiononsoftware librarystandardization,andadiscussionofopenproblemsandprojects. Many informaldiscussionsalsotookplace,oneofthemanybene?tsoftheDagstuhl setting. The traditional Dagstuhl social event was at this meeting a Baroque concertheldinthechapeloftheSchloß. Organizers MehdiJazayeri TechnicalUniversityofVienna R udigerLoos Tubingen University DavidMusser RensselaerPolytechnicInstitute AlexanderStepanov SGI Attendees DavidAbrahams MarkoftheUnicorn,Inc. GiuseppeAttardi UniversityofPisa MattAustern SGI UlrichBreymann HochschuleBremen StephenCerniglia RensselaerPolytechnicInstitute GeorgeCollins UniversityofDelaware JamesCrotinger LosAlamosNationalLab KrzysztofCzarnecki Daimler-Benz JamesDehnert SGI AngelDiaz IBMWatsonResearchCenter AxelDold UlmUniversity MatthewDwyer KansasStateUniversity UlrichEisenecker FachhochschuleHeidelberg HolgerGast Tubingen University RobertGluc k CopenhagenUniversity FriedrichvonHenke UniversityofUlm HoonHong NorthCarolinaStateUniversity MehdiJazayeri TechnicalUniversityofVienna JohannJeuring UtrechtUniversity NicolaiJosuttis Bredex ErichKaltofen NorthCarolinaState UllrichKothe RostockUniversity Organization VII UweKreppel Tubingen University WolfgangKuc hlin Tubingen University DietmarKuhl KonstanzUniversity GaryLeavens IowaStateUniversity KarlLieberherr NortheasternUniversity R udigerLoos Tubingen University KurtMehlhorn MPI,Saarbruc kenUniversity DavidMusser RensselaerPolytechnicInstitute StefanN aher HalleUniversity OscarNierstrasz BernUniversity MartinOdersky UniversityofSouthAustralia WilliamOgden OhioStateUniversity ArturoSanchez-Ruiz UniversityofCentralVenezuela StefanSchirra Saarbruc kenUniversity WolfgangSchreiner RISC-Linz SibylleSchupp RensselaerPolytechnicInstitute ChristophSchwarzweller Tubingen University MuraliSitaraman W. VirginiaUniversity GeorgTrausmuth TechnicalUniversityofVienna DavidVandevoorde Hewlett-Packard ToddVeldhuizen UniversityofWaterloo BruceWeide OhioStateUniversity KarstenWeihe KonstanzUniversity RolandWeiss Tubingen University ReinhardWilhelm Saarbruc kenUniversity AlexandreZamulin RussianAcademyofSciences,Novosibirsk WolfZimmermann KarlsruheUniversity TableofContents FoundationsandMethodologyComparisons FundamentalsofGenericProgramming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 JamesC. Dehnert,AlexanderStepanov(SiliconGraphics,Inc. ) RequirementOrientedProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 DavidMusser,SibylleSchupp(RensselaerPolytechnicInstitute), R udigerLoos(UniversityofTubingen) GenerativeProgrammingandActiveLibraries. . . . . . . . . .

Includes supplementary material: sn.pub/extras

Klappentext

RensselaerPolytechnicInstitute AlexanderStepanov SGI Attendees DavidAbrahams MarkoftheUnicorn,Inc. GiuseppeAttardi UniversityofPisa MattAustern SGI UlrichBreymann HochschuleBremen StephenCerniglia RensselaerPolytechnicInstitute GeorgeCollins UniversityofDelaware JamesCrotinger LosAlamosNationalLab KrzysztofCzarnecki Daimler-Benz JamesDehnert SGI AngelDiaz IBMWatsonResearchCenter AxelDold UlmUniversity MatthewDwyer KansasStateUniversity UlrichEisenecker FachhochschuleHeidelberg HolgerGast Tubingen University RobertGluc k CopenhagenUniversity FriedrichvonHenke UniversityofUlm HoonHong NorthCarolinaStateUniversity MehdiJazayeri TechnicalUniversityofVienna JohannJeuring UtrechtUniversity NicolaiJosuttis Bredex ErichKaltofen NorthCarolinaState UllrichKothe RostockUniversity Organization VII UweKreppel Tubingen University WolfgangKuc hlin Tubingen University DietmarKuhl KonstanzUniversity GaryLeavens IowaStateUniversity KarlLieberherr NortheasternUniversity R udigerLoos Tubingen University KurtMehlhorn MPI,Saarbruc kenUniversity DavidMusser RensselaerPolytechnicInstitute StefanN aher HalleUniversity OscarNierstrasz BernUniversity MartinOdersky UniversityofSouthAustralia WilliamOgden OhioStateUniversity ArturoSanchez-Ruiz UniversityofCentralVenezuela StefanSchirra Saarbruc kenUniversity WolfgangSchreiner RISC-Linz SibylleSchupp RensselaerPolytechnicInstitute ChristophSchwarzweller Tubingen University MuraliSitaraman W. VirginiaUniversity GeorgTrausmuth TechnicalUniversityofVienna DavidVandevoorde Hewlett-Packard ToddVeldhuizen UniversityofWaterloo BruceWeide OhioStateUniversity KarstenWeihe KonstanzUniversity RolandWeiss Tubingen University ReinhardWilhelm Saarbruc kenUniversity AlexandreZamulin RussianAcademyofSciences,Novosibirsk WolfZimmermann KarlsruheUniversity TableofContents FoundationsandMethodologyComparisons FundamentalsofGenericProgramming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 JamesC. Dehnert,AlexanderS

Inhalt
Foundations and Methodology Comparisons.- Fundamentals of Generic Programming.- Requirement Oriented Programming.- Generative Programming and Active Libraries.- The Refinement Relation of Graph-Based Generic Programs.- The Construction Principles of the Class Library Karla.- Programming Methodology.- Exception-Safety in Generic Components.- Segmented Iterators and Hierarchical Algorithms.- Theory and Generality of Complete Traversals.- A Data Abstraction Alternative to Data Structure/Algorithm Modularization.- Language Design.- Two Ways to Bake Your Pizza Translating Parameterised Types into Java.- SuchThat Generic Programming Works.- Specification and Verification.- Software Development in PVS Using Generic Development Steps.- Model Checking Generic Container Implementations.- Mizar Correctness Proofs of Generic Fraction Field Arithmetic.- Language Independent Container Specification.- Applications.- Applications of the Generic Programming Paradigm in the Design of CGAL.- Generic Programming in POOMA and PETE.- The STL Model in the Geometric Domain.- Generic Graph Algorithms.- A Generic Programming Environment for High-Performance Mathematical Libraries.