CAS 761: Generative Programming (Fall 2020)
Class: Tuesday 14:30-16:00, Friday 10:30-12:00, MS Teams.
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.
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:
- 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).
- '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)
- What you learned: Things you learned from the paper that were there,
but not really the main points. More like a side effect.
- Open questions: what is covered in the paper that you still don't
quite understand. Questions on 'what next'.
- 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.
Papers that will be presented:
- A survey of Metaprogramming Languages,
Y. Lilis, A. Savidis. Also available under Files on Teams.
(section 1-2: Brendan Fallon on Fri. Sep. 18,
rest: Rehan Theiveehathasan on Tues. Sep 22).
Overview of generative software development, K. Czarnecki.
(Peter Michalski, Fri. Sep. 25).
- When and How to Develop Domain-Specific Languages, M. Mernik , J. Heering , A.M. Sloane.
(Songyi, Tues. Sep 29)
- paper: Typed Tagless Final Interpreters ; the
course notes are freely
downloadable. By Oleg Kiselyov.
(Yu-Shiuan, Sections 1-2 on Fri. Oct. 2, Jason, Section 3 on Fri. Oct 9th)
- 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
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).
(Xin, Tues. Oct. 6th)
- RASCAL: a Domain Specific Language for Source Code Analysis and Manipulation,
P. Klint, T. van der Storm, J.J. Vinju.
(Naveen, Fri. Oct. 16th)
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.
(Jacques, Tues. Oct. 20th)
- Spiral, M. Püschel, F. Franchetti, Y. Voronenko.
(Rehan, Fri. Oct. 23rd)
- Jetbrains' MPS by a whole
team at jetbrains.com.
(Naveen, Tues Oct. 27th)
- Lessons learned from developing mbeddr: a case study in language engineering with MPS Markus Voelter, Bend Kolb, Tamas Szabo, Daniel Ratiu, Arie van Deursen.
(Brendan, Fri. Oct. 30th)
- What is generic programming? by G. Dos Reis and J. Jaarvi.
(Jason, Tues Nov. 3rd)
- Design Patterns as Higher-Order Datatype-Generic Programs, J. Gibbons.
(Xin, Fri. Nov. 6th)
- Program Synthesis as a generative method
E. Butler, K. Siu, A. Zook
(Peter, Tues. Nov. 10th)
- Lightweight Modular Staging, Tiark Rompf and Martin Odersky.
(Sharon, Fri. Nov. 13th)
- Adding Uncertainty and Units to Quantity Types in Software Models
T. Mayerhofer, M. Wimmer, A. Vallecillo
(Brendan, Tues. Nov. 17th)
- Tutorial on Online Partial Evaluation"
W. R. Cook, R. Laemmel. These notes are useful for a bit more context.
(Rehan, Fri. Nov. 20th)
- Staging for Generic Programming in Space and Time
G. Ofenbeck, T. Rompf, M. Pueschel
(Peter, Tues. Nov. 24th)
Answer Set Programming for Procedural Content Generation: A Design Space Approach
A.M.Smith, M. Mateas
(Xin, Fri. Nov. 27th)
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!
(Naveen, Tues. Dec 1rst)
- Parsing and Reflective Printing, Bidirectionally
Z. Zhu, Y. Zhang, H-S Ko, P. Martins, J. Saraiva, Z. Hu
(Jason, Fri. Dec. 4th)
- 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
(Sharon, Tues., Dec. 8th)
Papers that may be picked from:
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
by Lennart C.L. Kats, Eelco Visser.
link to PDF.
Tecton: A Framework for Specifying and Verifying Generic System Components,
D. Kapur, D.R. Musser.
- 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.
- Mechanizing the Development of Software, D. Smith
- Finally tagless, partially evaluation: tagless staged interpreters for simpler typed languages, J. Carette, O. Kiselyov and C-c. Shan
- 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.
- OMeta: an Object-Oriented Language for Pattern Matching, A. Warth and I. Piumarta.
- Engineering Definitional Interpreters, Jan Midtgaard, Norman Ramsey, Bradford
- First-class Runtime Generation of High-performance Types using Exotypes, Zachary DeVito, Daniel Ritchie, Matt Fisher, Alex Aiken, Pat Hanrahan.
- Design of Concept Libraries for C++ A. Sutton and B. Stroustrup.
An Extended Comparative Study of Language Support for Generic Programming,
R. Garcia, J. Jaarvi, J. Siek, A. Lumsdaine, J. Willcock.
Program Generation, Termination and Binding-time Analysis N.D. Jones
and A.J. Glenstrup.
- A Language for Generic Programming in the Large, J. Siek and A. Lumsdaine.
- 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
- Evaluating and comparing language workbenches (official version), by lots and lots of people.
- Domain-Specific Languages in Practice:A User Study on the Success Factors by Felienne Hermans, Martin Pinzger, Arie van Deursen.
Also useful is this glossary
of terminology around generative programming.