% % % % automatically generated % % bibtex2html custom.bib _delete_me.b1b -force -icons -partial-equality-of-names % Date: Wed Aug 24 20:40:48 2005 % Author: jsiek % % % @PhdThesis{siek05:_thesis, author = {Jeremy G. Siek}, title = {A Language for Generic Programming}, school = {Indiana University}, year = 2005, month = {August}, annote = {The past decade of software library construction has demonstrated that the discipline of generic programming is an effective approach to the design and implementation of large-scale software libraries. At the heart of generic programming is a semi-formal interface specification language for generic components. Many programming languages have features for describing interfaces, but none of them match the generic programming specification language, and none are as suitable for specifying generic components. This lack of language support impedes the current practice of generic programming. In this dissertation I present and evaluate the design of a new programming language, named G (for generic), that integrates the generic programming specification language with the type system and features of a full programming language. The design of G is based on my experiences, and those of colleagues, in the construction of generic libraries over the past decade. The design space for programming languages is large, thus this experience is vital in guiding choices among the many tradeoffs. The design of G emphasizes modularity because generic programming is inherently about composing separately developed components. In this dissertation I demonstrate that the design is implementable by constructing a compiler for G (translating to C++) and show the suitability of G for generic programming with prototypes of the Standard Template Library and the Boost Graph Library in G. I formalize the essential features of G in a small language and prove type soundness.} } @Article{garcia05:_extended_comparing05, author = {Ronald Garcia and Jaakko J\"arvi and Andrew Lumsdaine and Jeremy Siek and Jeremiah Willcock}, title = {An Extended Comparative Study of Language Support for Generic Programming}, journal = {Journal of Functional Programming}, year = 2005, note = {Submitted}, } @InProceedings{siek05:_fg_pldi, author = {Jeremy Siek and Andrew Lumsdaine}, title = {Essential Language Support for Generic Programming}, booktitle = {{PLDI} '05: Proceedings of the {ACM} {SIGPLAN} 2005 conference on Programming language design and implementation}, year = 2005, month = {June}, isbn = {1-59593-056-6}, pages = {73--84}, location = {Chicago, {IL}, {USA}}, doi = {http://doi.acm.org/10.1145/1065010.1065021}, publisher = {{ACM} Press}, address = {New York, {NY}, {USA}}, annote = {``Concepts'' are an essential language feature needed to support generic programming in the large. Concepts allow for succinct expression of bounds on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make generic algorithms easier to use. In this paper we present the design of a type system and semantics for concepts that is suitable for non-type-inferencing languages. Our design shares much in common with the type classes of Haskell, though our primary influence is from best practices in the \Cpp{} community, where concepts are used to document type requirements for templates in generic libraries. Concepts include a novel combination of associated types and same-type constraints that do not appear in type classes, but that are similar to nested types and type sharing in ML.} } @InProceedings{siek05:_g_stl, author = {Jeremy Siek and Andrew Lumsdaine}, title = {Language Requirements for Large-Scale Generic Libraries}, booktitle = {{GPCE} '05: Proceedings of the fourth international conference on {Generative} {Programming} and {Component} {Engineering}}, year = 2005, month = {September}, note = {accepted for publication}, annote = {The past decade of experience has demonstrated that the generic programming methodology is highly effective for the design, implementation, and use of large-scale software libraries. The fundamental principle of generic programming is the realization of interfaces for entire sets of components, based on their essential syntactic and semantic requirements, rather than for any particular components. Many programming languages have features for describing interfaces between software components, but none completely support the approach used in generic programming. We have recently developed G, a language designed to provide first-class language support for generic programming and large-scale libraries. In this paper, we present an overview of G and analyze the interdependence between language features and libraries design in light of a complete implementation of the Standard Template Library using G. In addition, we discuss important issues related to modularity and encapsulation in large-scale libraries and how language support for validation of components in isolation can prevent many common problems in component integration. } } @TechReport{siek05:_concepts_cpp0x, author = {Jeremy Siek and Douglas Gregor and Ronald Garcia and Jeremiah Willcock and Jaakko J\"arvi and Andrew Lumsdaine}, title = {Concepts for C++0x}, institution = {ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language {C++}}, year = 2005, url = "http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2005/n1758.html", number = {N1758=05-0018} } @InProceedings{siek04:_modular_generics, author = {Jeremy Siek and Andrew Lumsdaine}, title = {Modular Generics}, booktitle = {Concepts: a Linguistic Foundation of Generic Programming}, year = 2004, month = {April}, organization = {{Adobe Systems}}, annote = {This paper presents the design of G, a new language specifically created for generic programming. We review and identify important language features of C++ and Haskell in light of the past decade of generic library research and development. Based on this analysis we propose and evaluate relevant language design decisions for G. Generic programming is concerned with the construction of libraries of reusable software components and is inherently about programming ``in the large.'' Thus, the design of G places its greatest emphasis on modularity and safety, while also providing run-time efficiency and programmer convenience. This paper focuses on name scoping and type checking for generic functions, support for dispatching to algorithm specializations, support for type associations among abstractions, and separate compilation. The resulting design for G includes three novel aspects: scoped models declarations, nested types in concepts, and optional type constraints on generic functions. } } @TechReport{siek04:_fg1, author = {Jeremy Siek and Andrew Lumsdaine}, title = {Essential Language Support for Generic Programming: Formalization Part 1}, institution = {Indiana University}, year = 2004, number = 605, month = {December}, url = {http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR605}, annote = {``Concepts'' are an essential language feature needed to support generic programming in the large. Concepts allow for succinct expression of bounds on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make generic algorithms easier to use. In this paper we formalize the design of a type system and semantics for concepts that is suitable for non-type-inferencing languages. Our design shares much in common with the type classes of Haskell, though our primary influence is from best practices in the \Cpp{} community, where concepts are used to document type requirements for templates in generic libraries. The technical development in this paper defines an extension to System F and a type-directed translation from the extension back to System F. The translation is proved sound; the proof is written in the human readable but machine checkable Isar language and has been automatically verified by the Isabelle proof assistant. This document was generated directly from the Isar theory files using Isabelle's support for literate proofs.} } @Article{friedman03:_improve_krivine, author = {Daniel P. Friedman and Abdulaziz Ghuloum and Jeremy G. Siek and Lynn Winebarger}, title = {Improving the Lazy Krivine Machine}, journal = {Higher-Order and Symbolic Computation}, year = 2003, note = {accepted for publication} } @InProceedings{comparing_generic_programming03, author = {Ronald Garcia and Jaakko J\"arvi and Andrew Lumsdaine and Jeremy G. Siek and Jeremiah Willcock}, title = {A Comparative Study of Language Support for Generic Programming}, booktitle = {Proceedings of the 2003 ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA'03)}, year = 2003, month = oct, url = "http://doi.acm.org/10.1145/949305.949317", } @InProceedings{constrained_polymorphism:mpool03, author = {Jaakko J{\"a}rvi and Andrew Lumsdaine and Jeremy Siek and Jeremiah Willcock}, title = {An Analysis of Constrained Polymorphism for Generic Programming}, booktitle = {Multiparadigm Programming in Object-Oriented Languages Workshop (MPOOL) at OOPSLA}, year = 2003, editor = {Kei Davis and J\"org Striegnitz}, address = {Anaheim, CA}, month = oct, url = "http://www.osl.iu.edu/~jajarvi/publications/papers/mpool03.pdf", } @TechReport{abrahams03:_new_iterator_concepts, author = {David Abrahams and Jeremy Siek and Thomas Witt}, title = {New Iterator Concepts}, institution = {ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language {C++}}, year = 2003, number = {N1477=03-0060}, url = "http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1477.html", } @TechReport{abrahams03:_iterat_facad_adapt, author = {David Abrahams and Jeremy Siek and Thomas Witt}, title = {Iterator Facade and Adaptor}, institution = {ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language {C++}}, year = 2003, url = "http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1476.html", number = {N1476=03-0059} } @TechReport{friedman03:_improve_krivine_tr, author = {Daniel P. Friedman and Abdulaziz Ghuloum and Jeremy G. Siek and Lynn Winebarger }, title = {Improving the Lazy Krivine Machine}, institution = {Indiana University}, year = 2003, number = 581, month = {November}, note = {To appear in the journal, Higher Order and Symbolic Computation}, url = {http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR581}, annote = {Krivine presents the K machine, which produces weak head normal form results. Sestoft introduces several call-by-need variants of the K machine that implement result sharing via pushing update markers on the stack in a way similar to the TIM and the STG machine. When a sequence of consecutive markers appears on the stack, all but the first cause redundant updates. Improvements related to these sequences have dealt with either the consumption of the markers or the removal of the markers once they appear. Here we present an improvement that eliminates the production of marker sequences of length greater than one. This improvement results in the C machine, a more space and time efficient variant of K. We then apply the classic optimization of short-circuiting operand variable dereferences to create the call-by-need S machine. Finally, we combine the two improvements in the CS machine. On our benchmarks this machine uses half the stack space, performs one quarter as many updates, and executes between 27 0.000000aster and 17lower than our L variant of Sestoft's lazy Krivine machine. More interesting is that on one benchmark L, S, and C consume unbounded space, but CS consumes constant space. Our comparisons to Sestoft's Mark 2 machine are not exact, however, since we restrict ourselves to unpreprocessed closed lambda terms. Our variant of his machine does no environment trimming, conversion to deBruijn-style variable access, and does not provide basic constants, data type constructors, or the recursive let. (The Y combinator is used instead.)} } @TechReport{jaervi03:_declt_auto, author = {J. J\"arvi and Bjarne Stroustrup and Douglas Gregor and Jeremy Siek}, title = {Decltype and Auto}, institution = {ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, : Programming Language {C++}}, year = 2003, number = {N1478=03-0061}, url = "http://www.osl.iu.edu/~jajarvi/publications/papers/decltype_n1478.pdf", } @TechReport{veldhuizen03:_comb_opt_thy, author = {Todd L. Veldhuizen and Jeremy Siek}, title = {Combining Optimizations, Combining Theories}, institution = {Indiana University}, year = 2003, number = 582, month = {May}, url = {http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR582}, annote = {We consider the problem of how best to combine optimizations in imperative compilers. It is known that combined optimizations (or ``super-analyses'') can be strictly better than iterating separate improvement passes. We propose an explanation of why this is so by drawing connections between program analysis and the algebraic and coalgebraic views of programs and processes. We argue that ``optimistic'' analyses decide coinductively-defined relations and are based on bisimilarity. We relate combining program improvements to the problem of deciding combinations of theories. Iterating program improvements is similar to the Nelson-Oppen method of deciding combined theories: in Nelson-Oppen decision procedures communicate equalities, and iterated improvement passes implicitly communicate equalities via term replacements. To decide combined theories of bisimilarity, some ``co-Nelson-Oppen'' procedure is needed that propagates \emph{inequalities} amongst decision procedures. Hence, iterating optimistic analyses fails to be effective because inequalities cannot be communicated by semantics-preserving rewrites. Superanalysis is conjectured to overcome this failing by behaving like a ``co-Nelson-Oppen'' decision procedure.} } @Book{siek02:_bgl_book, author = {Jeremy Siek and Lee-Quan Lee and Andrew Lumsdaine}, title = {The Boost Graph Library: User Guide and Reference Manual}, publisher = {Addison-Wesley}, year = 2002, url = {http://www.awprofessional.com/title/0201729148}, } @InProceedings{schupp02:_ngs_ipdps02, author = {Sibylle Schupp and D. P. Gregor and B. Osman and David R. Musser and Jeremy G. Siek and Lie-Quan Lee and Andrew Lumsdaine}, title = {Concept-Based Component Libraries and Optimizing Compilers}, booktitle = {Proceedings {IPDPS'02}}, year = 2002, } @TechReport{SGO+02, author = {Sibylle Schupp and Douglas Gregor and Brian Osman and David R. Musser and Jeremy Siek and Lie-Quan Lee and Andrew Lumsdaine}, title = {Concept-based Component Libraries and Optimizing Compilers}, institution = {RPI Computer Science Department Technical Report 02-02}, year = {2002} } @Article{siek01:_concept_check, author = {Jeremy G. Siek and Andrew Lumsdaine}, title = {{C++} Concept Checking}, journal = {Dr. Dobb's Journal}, year = 2001, month = {June} } @InProceedings{abrahams01:_policy_adaptors, author = {David Abrahams and Jeremy Siek}, title = {Policy Adaptors and the Boost Iterator Adaptor Library}, BOOKTITLE = "Second Workshop on {C++} Template Programming", MONTH = "October", YEAR = 2001, } @InProceedings{TMPW01:_Willcock, author = {Jeremiah Willcock and Jeremy Siek and Andrew Lumsdaine}, title = {{C}aramel: A Concept Representation System for Generic Programming}, BOOKTITLE = "Second Workshop on {C++} Template Programming", address = "Tampa, Florida", MONTH = "October", YEAR = "2001", URL = "http://oonumerics.org/tmpw01/willcock.pdf", } @InBook{siek00:_scitools, author = {Jeremy G. Siek and Andrew Lumsdaine}, title = {Advances in Software Tools for Scientific Computing}, chapter = {A Modern Framework for Portable High Performance Numerical Linear Algebra}, publisher = {Springer}, url = "http://www.springeronline.com/sgw/cda/frontpage/0,10735,4-40109-22-2042346-0,00.html", year = 2000 } @Article{siek00:_soft_eng_peak, author = {Jeremy Siek and Andrew Lumsdaine}, title = {Software Engineering for Peak Performance}, journal = {{C++} Report}, year = 2000, pages = {23--27}, month = {May} } @Article{siek00:_ggcl, author = {Jeremy G. Siek and Andrew Lumsdaine}, title = {The Generic Graph Component Library}, journal = {Dr. Dobb's Journal}, year = 2000, month = {September} } @inproceedings{ siek00concept, author = "Jeremy Siek and Andrew Lumsdaine", title = "Concept checking: Binding parametric polymorphism in {C}++", booktitle = "Proceedings of the First Workshop on C++ Template Programming", address = "Erfurt, Germany", year = "2000", url = "citeseer.nj.nec.com/siek00concept.html", } @Article{Siek:1999:SPM, author = "Jeremy G. Siek and Andrew Lumsdaine", title = "The Matrix Template Library: Generic Components for High-performance Scientific Computing", journal = "Computing in Science and Engineering", volume = "1", number = "6", pages = "70--78", month = "Nov", year = "1999", ISSN = "1521-9615", url = {http://dx.doi.org/10.1109/5992.805137}, doi = {http://dx.doi.org/10.1109/5992.805137}, } @InProceedings{ggcl-iscope, author = {Lie-Quan Lee and Jeremy G. Siek and Andrew Lumsdaine}, title = {Generic Graph Algorithms for Sparse Matrix Ordering}, booktitle = {ISCOPE'99}, year = 1999, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag} } @inproceedings{ggcl-oopsla, author = {Jeremy G. Siek and Lie-Quan Lee and Andrew Lumsdaine}, title = {The generic graph component library}, booktitle = {Proceedings of the 1999 ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications}, year = {1999}, isbn = {1-58113-238-7}, pages = {399--414}, location = {Denver, Colorado, United States}, doi = {http://doi.acm.org/10.1145/320384.320428}, publisher = {ACM Press}, } @InProceedings{siek99:_mayfly, author = {Jeremy Siek and Andrew Lumsdaine}, title = {Mayfly: A Pattern for Lightweight Generic Interfaces}, booktitle = {Pattern Languages of Programs}, year = 1999, month = {July} } @MastersThesis{siek99:_msthesis, author = {Jeremy G. Siek}, title = {A Modern Framework for Portable High Performance Numerical Linear Algebra}, school = {University of Notre Dame}, year = 1999, } @InProceedings{ siek98:_blais_scitools, author = "Jeremy G. Siek and Andrew Lumsdaine", title = "The Basic Linear Algebra Instruction Set: Building Blocks for Portable High Performance", booktitle = "SciTools", year = 1998, } @InProceedings{siek98:_iscope, author = {Jeremy G. Siek and Andrew Lumsdaine}, title = {The Matrix Template Library: A Generic Programming Approach to High Performance Numerical Linear Algebra}, booktitle = {International Symposium on Computing in Object-Oriented Parallel Environments}, number = 1505, pages = {59--70}, series = {Lecture Notes in Computer Science}, year = 1998, } @InProceedings{siek98:_mtl_poosc, author = {Jeremy G. Siek and Andrew Lumsdaine}, title = {The Matrix Template Library: A Unifying Framework for Numerical Linear Algebra}, booktitle = {Parallel Object Oriented Scientific Computing}, year = 1998, organization = {ECOOP} } @InProceedings{siek98:_blais_poosc, author = {Jeremy G. Siek and Andrew Lumsdaine}, title = {A Rational Approach to Portable High Performance: The Basic Linear Algebra Instruction Set (BLAIS) and the Fixed Algorithm Size Template (FAST) Library}, booktitle = {Parallel Object Oriented Scientific Computing}, year = 1998, organization = {ECOOP}, } @InProceedings{siek98:_siamoo, author = {Jeremy G. Siek and Andrew Lumsdaine and Lie-Quan Lee}, title = {Generic Programming for High Performance Numerical Linear Algebra}, booktitle = {Proceedings of the SIAM Workshop on Object Oriented Methods for Inter-operable Scientific and Engineering Computing (OO'98)}, year = 1998, publisher = {SIAM Press}, } @InProceedings{ siek98:_mtl_scitools, author = "Jeremy G. Siek and Andrew Lumsdaine", title = "Generic Programming for High Performance Numerical Linear Algebra", booktitle = "SciTools", year = 1998, }