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