CAS 761: Generative Programming (Winter 2024)

Class: Monday, Thursday 13:30-15:00, usual CAS grad room.

The course will cover, through discussion and readings of important papers in the area, the related topics of generative programming, Domain Specific Languages, generic programming and program families. 60% of the mark will be given for leading class discussion of each assigned paper, and 40% on a small project due at the end of the course.

In more detail about the papers:

• Before the class where the paper (or part thereof) will be discussed, you need to hand in a 1-page (recto-verso, 10 or 11pt font, narrow margins) 'summary', comprised of:
  1. Summary of the paper. In your own words, the topics that the paper talks about. You can quote from the paper (make it clear when you do).
  2. 'Take home message': what you think that the author's message is. What you think the author wants you to remember from the paper. (Can often be quite separate from the summary)
  3. What you learned: Things you learned from the paper that were there, but not really the main points. More like a side effect.
  4. Open questions: what is covered in the paper that you still don't quite understand. Questions on 'what next'.
  5. Relevance to research: did you learn something from this paper that can be applied in your research, or otherwise has relevance.
• Leading discussion: you are supposed to act as both moderator and instigator of discussion. Use your own summary as a jumping off point. Go through everyone in the class and ask specific questions.

Also useful is this glossary of terminology around generative programming.

Papers that will be presented:

Papers that may be picked from. The first 3 overviews and 'finally tagless' (technique) will be assuredly done.

Overviews

• Overview of generative software development, K. Czarnecki.
• A survey of Metaprogramming Languages, Y. Lilis, A. Savidis.
• When and How to Develop Domain-Specific Languages, M. Mernik , J. Heering , A.M. Sloane.
• An Extended Comparative Study of Language Support for Generic Programming, R. Garcia, J. Jaarvi, J. Siek, A. Lumsdaine, J. Willcock.
• What is generic programming? by G. Dos Reis and J. Jaarvi.
• Evaluating and comparing language workbenches (official version), by lots and lots of people. (local copy).

Meta-Programming Techniques

• Typed Tagless Final Interpreters ; the course notes are freely downloadable. By Oleg Kiselyov.
• Finally tagless, partially evaluated: tagless staged interpreters for simpler typed languages, J. Carette, O. Kiselyov and C-c. Shan
• Lightweight Modular Staging, Tiark Rompf and Martin Odersky.
• Staging for Generic Programming in Space and Time G. Ofenbeck, T. Rompf, M. Pueschel
• DSL implementation in MetaOCaml, Template Haskell and C++, Czarnecki, K., J. O'Donnell, J. Striegnitz, and W. Taha.
• Multi-stage programming with Functors and Monads: eliminating abstraction overhead from generic code, J.Carette and O. Kiselyov.
• Staged Compilation with Two-Level Type Theory, András Kovács
• Scoped and Typed Staging by Evaluation, Guillaume Allais

Related Implementation Techniques

• Design Patterns as Higher-Order Datatype-Generic Programs, J. Gibbons.
• OMeta: an Object-Oriented Language for Pattern Matching, A. Warth and I. Piumarta.
• Engineering Definitional Interpreters, Jan Midtgaard, Norman Ramsey, Bradford Larsen.
• First-class Runtime Generation of High-performance Types using Exotypes, Zachary DeVito, Daniel Ritchie, Matt Fisher, Alex Aiken, Pat Hanrahan.
• Compiling for Run-time Code Generation F. Smith, D. Grossman, G. Morrisett, L. Hornof and T. Jim.
• Extensible Object Models, I. Piumarta, A. Warth.
• Open, Reusable Object Models, I. Piumarta and A. Warth
• Type-and-scope safe programs and their proofs., Guillaume Allais, James Chapman, Conor McBride, and James McKinna

Frameworks and Language Workbenches

• Jetbrains' MPS by a whole team at jetbrains.com.
• Spoofax, by Lennart C.L. Kats, Eelco Visser. link to PDF.

Analysis and Transformation

• RASCAL: a Domain Specific Language for Source Code Analysis and Manipulation, P. Klint, T. van der Storm, J.J. Vinju.

Software Engineering and Software Development

• Software Development by Refinement, Dusko Pavlovic and Douglas R. Smith. Here's a direct link to a PDF if the other one doesn't work.
• Tecton: A Framework for Specifying and Verifying Generic System Components, D. Kapur, D.R. Musser.
• Mechanizing the Development of Software, D. Smith
• A software engineering experiment in software component generation, R. Kieburtz, L. McKinney, J. Bell, J. Hook, A. Kotov, J. Lewis, D. Olive, T. Sheard, I. Smith, L. Walton.
• Domain-Specific Languages in Practice:A User Study on the Success Factors by Felienne Hermans, Martin Pinzger, Arie van Deursen.

Examples of note

• Spiral, M. Püschel, F. Franchetti, Y. Voronenko.
• Lessons learned from developing mbeddr: a case study in language engineering with MPS Markus Voelter, Bend Kolb, Tamas Szabo, Daniel Ratiu, Arie van Deursen.
• OTT - code, we will read the ICFP version of Ott: Effective Tool Support for the Working Semanticist, Peter Sewell, Francesco Zappa Nardelli, Scott Owens, Gilles Peskine, Thomas Ridge, Susmit Sarkar, Rok Strnisa, as the journal version is 52 pages!
• Parsing and Reflective Printing, Bidirectionally Z. Zhu, Y. Zhang, H-S Ko, P. Martins, J. Saraiva, Z. Hu
• Strymonas (Stream fusion), Kiselyov, Kobayashi, Biboudis, Palladios, Smaragdakis
• Symbolic Execution of Hadamard-Toffoli Quantum Circuits, J. Carette, G. Ortiz, A. Sabry.
• GOOL: Generic Object-Oriented Language, J Carette, B. MacLachlan, S Smith.

Theory

• Partially static data as free extension of algebras (short paper) (PEPM paper; there is a longer version at ICFP) J. Yallop, T. von Glehn, O. Kammar

Staging, Partial Evaluation, Normalization by Evaluation

• Tutorial on Online Partial Evaluation" W. R. Cook, R. Laemmel. These notes are useful for a bit more context.
• Program Generation, Termination and Binding-time Analysis N.D. Jones and A.J. Glenstrup.
• Practical normalization by evaluation for EDSLs, Valliappan, Nachiappan and Russo, Alejandro and Lindley, Sam

Concepts, Theories, Modules

• Design of Concept Libraries for C++ A. Sutton and B. Stroustrup.
• Leveraging the Information Contained in Theory Presentations, Jacques Carette, William M. Farmer, Yasmine Sharoda

• A Language for Generic Programming in the Large, J. Siek and A. Lumsdaine.

Macros

• Hygienic Marco Expansion, E. Kohlbecker, D.P. Friedman, M. Felleisen, B. Duba. The paper that really got the ball going on modern macros.
• Binding as sets of scopes, M. Flatt. Rethink of how macro expansions ought to work, away from contextual name renaming towards sets of scopes.
• Towards the Essence of Hygiene, M. D. Adams. Whereas the previous paper is about implementation, this is instead about the theory.
• Languages as libraries", S Tobin-Hochstadt, V. St-Amour, R. Culpepper, M. Flatt, M. Felleisen. Paper that explains Racket's language extension API and thus how library code can help create a new language.
• For those who find the above fascinating, there is a long (110 pages) paper on the history and techniques of Hygienic Macro Technology, by William D. Cling, and Mitchell Wand. Fascinating, but won't be on our reading list.

• Beyond Notations: Hygienec Macro Expansion for Theorem Proving Languages, S. Ullrich, L. De Moura.

Tactics

• Canonical Structures for the Working Coq User, A. Mahboubi, E. Tassi.
• How to make ad hoc proof automation less ad hoc, Gonthier, G., Ziliani, B., Nanevski, A., & Dreyer, D.

Miscellaneous

• Adding Uncertainty and Units to Quantity Types in Software Models T. Mayerhofer, M. Wimmer, A. Vallecillo

Note that some of the links above are to the author's private copy of the paper, and may not represent the final typesetting of the article by the publisher. Links to the published version will be added too, as time permits.

Procedural Generation

In previous years, the following papers were also read, because several people in the class were doing related research.

• Procedural generation in games: read Automatic level generation for platform videogames using genetic algorithms by Mourato, Prospero, Birra [local copy], as well as Rhythm-based level generation for 2D platformers by Smith, Treanor, Whitehead, and Mateas [local copy]. Those papers are just 8 pages each, with many illustrations, so not so long. If your knowledge of games and procedural generation is such that the material doesn't seem to make much sense on its own, then read Understanding procedural content generation: a design-centric analysis of the role of PCG in games by Smith [local copy]; this paper does not have to read (and thus not in scope of the summary, but feel free to refer to it if it helps).
• Program Synthesis as a generative method E. Butler, K. Siu, A. Zook
• Answer Set Programming for Procedural Content Generation: A Design Space Approach A.M.Smith, M. Mateas