Admin: 1 revision

2011-12-12T10:06:30Z

1 revision

New page

[[Category:WG211]]

=
----
+ Teaching Program Generation=

Getting program generation accepted and used starts with teaching our students.

* How should we incorporate program generation in the computer science curriculum?

This session gives room for expressing views and reflecting on experience.

Issues include:

* experience with teaching courses on/involving program generation
* place in the curriculum (wrt other material)
* theoretical and conceptual framework
* tools
* course organization
* topics and their relative priority (what is important)
* suitable example domains
* books
* meta languages
** typing
** other guarantees

==
----
-++ Existing Courses==

* Martin Erwig
* Program Synthesis - Berkeley
* Julia Lawall - DSLs
* Walid Taha - MSP

* Crista Lopes - Irvine
** Programming Languages 2 (PL2)
** http://www.ics.uci.edu/~lopes/teaching/inf102W06/index.html
** Reflection
** Ruby

* Peter Sestoft
** run-time code generation
** ML as meta-language (difficult to learn)
** future: scheme as meta-language

* Paul Kelly
** Compiler Construction
** Advanced Computer Architecture

* Eelco Visser
** Program transformation
*** http://swerl.tudelft.nl/bin/view/Pt
** Software generation and configuration
*** http://www.cs.uu.nl/wiki/Sgc/WebHome

* Tim Sheard
** staged programming
** http://web.cecs.pdx.edu/~sheard/course/stagedcomp/index.html

==
----
-++ Domains==

* Compilers
* J2EE
* Linear Transforms (FFTW, Spiral)
* Web programming
* Language processing
** regular expressions
** grammars
* Databases
** SQL
** database binding
* Functional reactive programming
** Pan (Conal Elliot)
** Haskore
* User interface generators
* Hardware synthesis
** Lava

==
----
--++ Issues==

* Binding
* Variable capture
* Hygienic macros
* Concrete syntax
* Staged computation
* Partial evaluation
* Binding time
** binding time analysis

==
----

----
++ Techniques==

* Reflection
* Introspection
* Parsing
* Template languages
** String Template
* Wizards

==
----

----
++ Technologies==

* Dynamic (scripting) languages
** Ruby
** Scheme
* Staged languages
** Template Haskell

* Google web toolkit

----

----

----

=
----

----
--+ Course Outlines=

Here are some actual, proposed, or imagined outlines for courses involving elements of program generation.

==
----
--++ Eelco Visser - Software Engineering 2==

Goal: learn students how to abstract programming patterns into domain-specific languages.

* Part I : Using DSLs
** Discuss examples of DSLs in real life
*** regular expressions
*** context-free grammars
*** rewrite rules
*** web DSLs
*** database DSLs (SQL)
*** workflow
** Considerations
*** explanation of domains should not take over the course
** Lab
*** Experiment with some of these in practical exercises

* Part II : Developing DSLs (DSL Engineering)
** Syntax and semantics
*** an intro into language definition
** DSL design
*** domain engineering
*** what goes into the DSL?
*** language design issues
** Implementation techniques
*** term rewriting
*** graph rewriting
*** model transformation
*** attribute grammars
*** XML, XSLT
*** syntax embedding
*** reflection (Ruby, Python)
*** DSL definitions as modules
** Lab
*** Implement a (couple of) (simple) DSL(s)

* Part III : Limitations of DSLs
** flexibility / adaptability of generated code
** hygienic code generation / variable capture
** modularity / separate compilation
** retargetability of generators

----

----

----

----

----

----

----

==
----
--++ Sam Kamin - Program Generation==

Proposed (and extremely tentative) course on program generation,
upper-level undergrad level

* I. Uses of program generation and transformation
** A. Textual abstraction as a kind of program abstraction
*** 1. Programs as collections of fragments
*** 2. Product-line architectures; components
*** 3. Synthesis of programs from specifications
** B. The cost of abstraction
*** 1. The cost of generality in libraries
** C. Overcoming the cost of abstraction
*** 1. Gaining efficiency through program generation/transformation
*** 2. The importance of domain knowledge
** D. Domain-specific languages

* II. Example domains (need to be accompanied by concrete examples)
** A. Generating ADT code (catamorphism-type stuff)
** B. Building database programs (generating classes for db schemas)
** C. Scientific computing - FFT, matrix operations, simulation
** D. Language-based examples - lexical analysis, parsing, interpreters, compilers
** E. Building DSL's

* III. Tools (need to be accompanied by programming exercises)
** A. Static, "ad hoc" program generation (e.g. using Ruby)
*** i. Static reflection
** B. Dynamic program generation (e.g. using Jumbo)
** C. Program transformation tools (e.g. Stratego)
** D. Safe program generators (e.g. MetaOCaml)

----

----

----

----

----
--

==
----
++ Crista Lopes - Programming Language 2==

I'm redesigning the course to have less stuff, but more of the things that stay in. It will be something like this:

* Meta-circular interpreter (in Scheme)
* Declarative programming
** SQL
** logic programming (in Scheme)
* AOP (maybe?) (in Scheme)
* OOP inside (Ruby)
* Reflection (Ruby) -- this is the part that is more related to program generation
* Markup languages

This is a programming languages course, hence the focus on PLs.
For a software engineering, enabler tools kind of course, I would do something different. I would have to think a lot more...

----

----

----

----

----
--

==
----
++ Paul Kelly==

Proposal: Course in

* Software Synthesis and Metaprogramming
* Students: Master's level, with some industrial experience
* Objectives: Students should gain an understanding of key principles in the application and design of software that generates and manipulates programs.

This outline presents a large picture; the challenge is to identify from these topics the taxonomy, central theoretical ideas, and software engineering principles.

* Introduction:
** Motivation via a small variety of compelling examples.
** Some large "industrial scale", others open-source and available for hands-on experience and understanding.
* Analysis:
** Reflection (eg in Java, Ruby),
** Code query languages (Codequest etc).
* Aspects and aspect weavers:
** Pointcuts (as reflection, as queries),
** advice (as generation),
** safety; safety holes in AspectJ.
** Aspects as features.
** Aspect composition.
* Generators:
** Macros,
** name capture.
** Static, dynamic: quoting and binding times
** Runtime generation.
** Type-safe program generation.
** Partial evaluation; on-line versus offline.
** Binding time analysis, binding-time improvement.
** Jones optimality?
* Domain-specific generators, domain-specific languages:
** Language embedding;
** syntactic issues, types and binding issues.
** Single source, multiple interpretation.
* Features, product lines, architectures and components:
** Feature mapping and refactoring.
** Feature interaction.
** Architecture description languages.
** Adaptive component architectures, reflective middleware.

----

----

----

----

----
--

==
----
++ Peter Sestoft==

Outline of a course fragment on program generation
Peter Sestoft 2006-10-27

Course prerequisites: Prior to the course, students are assumed to
know Java (or C#) and reflection.

Some prerequisites filled by earlier modules of the course itself:

* Abstract machines, including the JVM and/or .NET bytecode
* Introductory Scheme

Plan

* Explain that program generation is used a lot (J2EE interfaces, Java Server Pages, PHP, object-relational mappers, ...).
* Explain the main purposes:
** Avoid writing boilerplate code, and obtain performance (space, time) by generating specialized code.
* Using small two-parameter examples (see below),
** introduce the concept of binding time (static and dynamic),
** where static computations can be performed early, in a generator,
** and dynamic operations are to be performed late, in the generated code.
** Mention the concept of a partial evaluator and generating extension,
** and that the generating extension of an interpreter is a compiler.
** Etc.
* Show textual source code generation using print-statements, to demystify the concept.
** Explain that this is impractical.
* Show code generation in Scheme using backquote and comma.
** Point out the challenges of always generating syntactically well-formed code and using only variables that are in scope.
** (Correct static typing of the generated code does not enter the picture in Scheme, only when generating bytecode below).
* Show runtime code generation in Scheme using the above and eval.
* Show runtime code generation in Java (or C#) using BCEL or .NET's System.Reflection.Emit.
** Point out that this is exactly analogous to runtime code generation in Scheme,
** only it looks far more complicated and is more difficult to debug.
* Point out that there is a general idea in the above: Staged computation or two-level languages, and that there are many research prototypes of such languages: MetaOCaml, Jumbo, DynJava, Metaphor, ...

Some simple motivating examples

Polynomial evaluation c_0 + c_1 x + c_2 x^2 + ...
<pre>
double PolyEval(double[] cs, double x)
</pre>

The power function x^n
<pre>
double Power(int n, double x)
</pre>

Generating terms of the Taylor series for exp(x)

AES (Rijndael) encryption algorithm
<pre>
byte[] Encrypt(Key key, byte[] block)
</pre>

Sparse matrix multiplication

----

----

----

----

----
--

==
----
++ Martin Bravenboer==

Program Generation

I like the idea of modules provided by different people in the
community. It probably won't happen, but it would be a good thing.

* Introducing: motivating examples
** Lack of abstraction (Enterprise, boilerplate stuff)
** Lack of performance (creepy numerical stuff etc)
** Cross-cutting concerns
** Variability (Conditional code)
* Design issues
** Patterns, when and how to develop DSLs
** Domain knowledge
* Concepts and principles
** Static and dynamic reflection
** Code as input of program generation
** Attribute-oriented techniques
** Probably illustrated by Ruby
** Mirrors
* Programming language concepts:
** Binding time
** Hygiene, scope, shadowing, etc
** Partial evaluation and multi-staging techniques
* Syntax for abstractions: what's the input of a code generator?
** Domain-specific languages
** Models, meta-models
** Text, grammars
** Code: reflection
* Solutions
** Unfortunately, there are far too many solutions, Ideally, the various angles of attack should be illustrated in a single language/environment to make comparision and comprehension easier. However, that will be difficult to realize.
** Macros, templates, C++, Scheme etc.
** Software transformation systems: rewriting rules
** Extensible compilers, Silver, Forwarding
** Template systems
** Embedded DSLs: Converge, Haskell, MetaBorg, etc
** Writing interpreters, compilers
** Run-time code generators, such as Jumbo, .NET compiler API, Java stuff etc.
** From Ruby to Jumbo to type-safe code generators
** Reflective systems, such as Ruby, Smalltalk, Reflex

----

----

----

----

----

----

----
-

=
----

----
-+ Notes from the Meeting=

==================================================
Crista Lopes

* Teaches course on Reflection
** Scheme for interpreters
** Ruby is highly recommended
*** very cute
*** meta-object architecture
*** no environment
*** untyped programming language
* based on Ruby for reflection
* assignment based on Ruby on Rails
* Reflection versus AST
** Easier to teach then reflection
** Dynamic reflection (beyond static reflection)
** Mirrors paper based on OOPSLA based on Smalltalk (Bracha)
* Using search engines for finding code
** Lopes: teach how to use other components/tools/libraries rather than learning all the details of how to do it yourself
* Fit together
* Paul: Let them play

==================================================
Peter Sestoft

* Teaches course on Programming Language Concepts
** Standard ML
** Scheme
*** easier for students
*** more versatile
* Interpreters
* Compilers
* Code generation
** printf
** Scheme
* Run-time code generation
** .NET
** JVM
* Principles:
** Binding time
* show in generator example

==================================================
Paul Kelly

* Teaches course on Compilers
** Compulsary with some motivation issues
** Based on Haskell
** Simple imperative language
** Optimization, back-end
* Teaches course on Advanced Computer Architecture
** Numerical algorithms
** Optimization based on computer architure
* Opinions:
** Program generation not necessarily difficult
** It's a means of learning students about programming languages
* Principles:
** Variable capture, hygienic mcacros
** How are object-oriented languages implemented?

==================================================
Sam Kamin

* Teaches course on Programming Languages: Concepts and Implementation
** ML as meta-language
** Programming paradigms
* Ideas for a course
** General concepts and motivation
** Examples from different domains
* Tools: from Ruby, to Jumbo, to type-safe code generators
** Teach students about abstractions
** Programming patterns motivate DSLs
** ADTs
** Templates
** DSLs
* Principles:
** Partial evaluation
* Let students crash first, then: how to do it right.

==================================================
Visser

* Teaches course on Program Transformation
** Stratego
** Study various transformations
** Problem: not enough time for the concepts
* Present examples of existing DSLs
** Sam: presenting polished DSLs does not illustrate the problems

==================================================
Martin Bravenboer

* Opinions
** Where do we actually produce code from?
* Front-end:
** reflection
** modelling
** text, parsing, grammars

==================================================
Czarnecki

* When to develop a DSL?
* Design issues is more important
* Doing the actual program generation is a small task
* Techniques and tools less important
* Design patterns for DSLs
* "this could use some DSL"

==================================================
Walid

* Suggestion
** Reuse modules created by experts
* Should we teach crazy wacky ideas?
** Don't know if it is a good thing or bad thing
** Might be good
* Courses on Program generation
** Martin Erwik (?)
** Program synthesis at Berkley
* Julia Lawall
** Domain-specific languages
* MSP course:
** Walid could contribute a module
** Don Batory
** Tim Sheard - staged computation
* Courses Aspect-Oriented Programming:
** Probably too many
** Personal statement by Lopes: AspectJ sucks, so I don't want to give a course about it ;)
* Principles:
** Kolmorov Complexity
** Binding time is an important concept to teach

==============================================
Example domains

* Spiral
* Web programming (Ruby)
* Performance things like loop unrolling, matrix multiplication, sorting
* Enterprise, database, EJB
** e.g. Ruby on Rails
* Interpreters and parsers
** regular expressions?
* Funtional reatice programming: hascore / Pan / Fran / Lava, hardware synthesis
* Javascript stuff: Google Web Toolkit / JSAN
* ASP .NET, JSP, PHP

WG211/TeachingProgramGeneration - Revision history

Admin: 1 revision