WG211/TeachingProgramGeneration

From WG 2.11
Jump to: navigation, search



=

+ 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
  • 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

==

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

  double PolyEval(double[] cs, double x)

The power function x^n 

  double Power(int n, double x)

Generating terms of the Taylor series for exp(x)

AES (Rijndael) encryption algorithm 

  byte[] Encrypt(Key key, byte[] block)

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
Retrieved from "https://wiki.hh.se/wg211/index.php?title=WG211/TeachingProgramGeneration&oldid=347"