RecentWork

The Anticipatory Optimization Generator (AOG): Over the last few years, I have been experimenting with a new architecture for generation systems that accepts high-level domain specific languages (DSLs) and generates high performance target code without the usual solution space explosion.

The underlying new ideas include:

Explicit control structures considered harmful in Domain Specific Languages

	AOG generates custom control structures by weaving together the separate control structures implied by DSL expressions of operators and operands. The custom control structure "weave" shares parts of the separate control structures. This process is called Control Localization (a PowerPoint presentation). ( PDF of presentation slides with notes)
	DSL expressions without explicit control structures allow mathematical manipulation of the expressions. Low level programming languages (e.g., Java or C++) prevent easy manipulation largely because of the presence of explicit control structures (e.g., loops, enumerations, etc.).

Architectural shaping (PowerPoint presentation) of code based on global constraints (e.g., CPU architecture or middleware protocols). ( PDF of slides with notes)

	Accomplished by a new transformation control regime called Tag-Directed transformations
	Tag-Directed transformations are triggered by generator events (e.g., expression substitution, expression simplification, start of a phase, completion of another TD transformation, or action by another TD transformation)
	Tags (including their event expressions) are attached to AST subtrees (either a priori or during generation process)

The technology includes:

Two kinds of transformations

	Pattern-directed (PD) transformations for program refinement
	Tag-directed (TD) transformations for program reorganization and optimization

AST tags that anticipate late stage program reorganizations and thereby comprise an optimization plan that is distributed over the evolving program

Transformation stages (aka phases) that each have well-defined generation purposes

Two dimensional storage organization for PD transformations

	By arbitrary object (with inheritance) based on the semantics of the domain specific operators and operands
	By generation stage (or phase) based on the generation objective (e.g., loop fusion)
	PD transformations are only visible/enabled when the specific object that they are stored under (e.g., a type) is specified as the current source of transformations and AOG is operating in the stage (or phase) associated with a given transformation. For each (object, stage) pair, only a handful of transformations ever need to be tried. This prunes the search space significantly.

A process for reasoning over and evolving both the program and tags (i.e., the optimization plan)

Documentation includes a short overview, a longer overview emphasizing the pattern-driven transformations (PDF), a detailed example of tag-driven optimization (PDF), a look at the new transformation structures in AOG (PDF) and the User Manual for the pattern matcher ( PDF).

Pattern Matching: The pattern matching notation serves as a kind of "logical schema" of the Abstract Syntax Tree (AST) for the AOG generator. It provides complex matching and inference services. The matcher is fully backtracking and is built on a "continuation passing style" of programming. It provides analogs to Prolog operations such as and, or, not, mark, cut, succeed, fail, prove, bind, and rule definition. Additionally, it provides operators for spanning lists, binding remaining data, top-down and bottom-up tree searches, defining local pattern variables, operating with inheritable rule sets, navigating object structures, recursive matching, and executing arbitrary Lisp expressions. The matching notation is open in the sense that the programmer can easily define arbitrary new matching operators.

Generators Nutshell Talk (PowerPoint): This is a talk overviewing generators technology given at the Sixth International Software Reuse Conference in Vienna, Austria, June, 2000. Nutshell talk with speakers notes. (PDF)

Program Generation Perspective: See Annals Of Software Engineering Vol. 5, 1998 (ISSN 1022-7091) for a survey and assessment of program generation systems and mechanisms. I attempt to describe the niches that are most appropriate for different kinds of reuse technologies based on their ability to scale vertically in size (and thereby improve programming productivity) and scale horizontally in feature variation (and thereby improve optimality of fit). The technologies I analyze are:

	Concrete components (e.g., COM components)
	Composition-based generation (e.g., GenVoca)
	General transformation systems (e.g., Draco or CAPE)
	AOG-like systems
	Inference-based generation (e.g., Kids or Novak's views)