Reflective Program Generation with Patterns

Reflective Program Generation with Patterns. Manuel Fähndrich, Michael Carbin, James R. Larus. October 2006.

Runtime reflection facilities, as present in Java and .NET, are powerful mechanisms for inspecting existing code and metadata, as well as generating new code and metadata on the fly. Such power does come at a high price though. The runtime reflection support in Java and .NET imposes a cost on all programs, whether they use reflection or not, simply by the necessity of keeping all metadata around and the inability to optimize code because of future possible code changes. A second---often overlooked---cost is the difficulty of writing correct reflection code to inspect or emit new metadata and code and the risk that the emitted code is not well-formed. In this paper we examine a subclass of problems that can be addressed using a simpler mechanism than runtime reflection, which we call compile-time reflection.We argue for a high-level construct called a transform that allows programmers to write inspection and generation code in a pattern matching and template style, avoiding at the same time the complexities of reflection APIs and providing the benefits of staged compilation in that the generated code and metadata is known to be well-formed and type safe ahead of time.

Macros, multi-staged programming etc. are the appropriate buzzowrds.

LtU readers will probably be interested in the STM example (see sec. 7.1)

Scrap your Nameplate

Scrap your Nameplate
by James Cheney
Recent research has shown how boilerplate code, or repetitive code for traversing datatypes, can be eliminated using generic programming techniques already available within some implementations of Haskell. One particularly intractable kind of boilerplate is nameplate, or code having to do with names, name-binding, and fresh name generation. One reason for the difficulty is that operations on data structures involving names, as usually implemented, are not regular instances of standard map, fold , or zip operations. However, in nominal abstract syntax, an alternative treatment of names and binding based on swapping, operations such as alpha-equivalence, capture-avoiding substitution, and free variable set functions are much better-behaved. In this paper, we show how nominal abstract syntax techniques similar to those of FreshML can be provided as a Haskell library called FreshLib. In addition, we show how existing generic programming techniques can be used to reduce the amount of nameplate code that needs to be written for new datatypes involving names and binding to almost nothing—in short, how to scrap your nameplate.

Sage: A Programming Language With Hybrid Type-Checking

Since we've been discussing hybrid type checking, dependent types, etc. recently...


Sage is a prototype functional programming language designed to provide high-coverage checking of expressive program specifications (types). Sage allows a programmer to specify not only simple types such as "Integers" and "Strings" but also arbitrary refinements from simple ranges such as "Positive Integers" to data structures with complex invariants such as "Balanced binary search trees." In addition to featuring these predicates upon types, Sage merges the syntactic categories of types and terms, in the spirit of Pure Type Systems, to express dependent types such as that of the infamous printf function.

Sage performs hybrid type checking of these specifications, proving or refuting as much as possible statically, and inserting runtime checks otherwise. For the complete details of the theory and empirical results, we direct you to the technical report.

Oz has macros!

Some of you might be interested to learn that Oz got a basic macro facility.

A bit more information can be found in the mailing list.

EasyExtend - Python MetaProgramming

Just saw this announcement on Google groups / comp.lang.python.

EasyExtend is a constructive approach to extend the Python language using pure Python. EasyExtend is developed as a Python framework depending only on tools provided by the CPython interpreter suite ( compiler ) and standard library as well as some pieces of code borrowed from the PyPy project. Opposite to toolkits for writing extension modules in C ( or RPython in future ) the EasyExtend framework is dedicated to extend the language itself by adding new grammar rules and transformation of parse trees. Acting directly on the nodes of syntax trees makes EasyExtend safe and extensible. Moreover the parser and the transformations are considerably fast. While EasyExtend can obviously be used to define "little languages" embedded in Python it can also be used to create Python oriented tools like a code coverage tool based on code generation. For both use-cases examples will be provided.

You'll want to probably want to check out the examples.

Code Generation Network

It's been quite a while since I visited, and it seems like the site grew considerably, so you might want to check it out again too.

Code generation is an important programming technique (not to be confused with the code generation phase of compilers), which I am sure everyone here is familiar with. It seems to me that the percentage of programmers who know about code generation is relatively small. Am I right in this assumption? I am not asking about people actually using the technique, mind you, just about knowing that it exists and what it means, and don't think the basic idea is "strange" or involves dark magic.

I wonder where, if anywhere, should programmers (and CS students) learn about it. And no, the answer well, on LtU of course isn't a good option!

HashCaml--an extension of the OCaml bytecode compiler with support for type-safe marshalling and related naming features.


Peter Sewell and crew follow up on their work on Acute:

In this paper we put these ideas into practice, describing the HashCaml extension to the OCaml bytecode compiler, which supports type-safe and abstraction-safe marshalling, together with related naming constructs. Our contribution is threefold: (1) We show how to define globally meaningful runtime type names for key OCaml type constructs that were not covered in our previous work, dealing with the generativity issues involved: user-defined variant and record types, substructures, functors, arbitrary ascription, separate compilation, and external C functions. (2) We support marshalling within polymorphic functions by type-passing, requiring us to build compositional runtime type names and revisit the OCaml relaxed value restriction. We show that with typed marshalling one must fall back to the SML97 value restriction. (3) We show how the above can be implemented with reasonable performance as an unintrusive modification to the existing OCaml language, implementation, and standard libraries. An alpha release of HashCaml, capable of bootstrapping itself, is available, along with an example type-safe distributed communication library written in the language.


User Manual for the Series Macro Package by Richard C. Waters (MIT AI Memo 1082, 1989).

The benefits of programming in a functional style are well known. In particular, algorithms that are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent algorithms expressed as loops. Unfortunately, many programmers hesitate to use series expressions. In part, this is due to the fact that series expressions are typically implemented very inefficiently.

A Common Lisp macro package (called Series) has been implemented that can evaluate a wide class of series expressions very efficiently by transforming them into iterative loops. When using this class of series expressions, programmers can obtain the advantages of expressing computations as series expressions without incurring any run-time overhead.

There is an up-to-date copy of the Series package on Sourceforge.

This Is the Title of This Story, Which Is Also Found Several Times in the Story Itself

This is the first sentence of this story. This is the second sentence. This is the title of this story, which is also found several times in the story itself. This sentence is questioning the intrinsic value of the first two sentences. This sentence is to inform you, in case you haven't already realized it, that this is a self-referential story, that is, a story containing sentences that refer to their own structure and function. This is a sentence that provides an ending to the first paragraph.

This is the link to the story

Active Libraries and Universal Languages

Active Libraries and Universal Languages

The ideas in this dissertation had their early origins in the years I spent working on the Blitz++
library for numerical arrays. Rather than relying on the compiler to optimize arrays, it performed
these optimizations itself using template techniques (‘expression templates’ and ‘template metaprograms’).
The fact this could be done made me wonder about the general problem of domainspecific
code optimization. From reading the literature it seemed a widespread debate: where ought
domain-specific optimizations be performed? In compilers? Compiler plug-ins? Metalevel code?
Preprocessors? Libraries? The C++ experience indicates that with a sufficiently powerful language
and compiler, libraries can define their own optimizations, and we can package abstractions and
optimizations together as a coherent library. Template metaprogramming is, let’s be frank, a rather
miserable programming environment — its popularity suggests a real need in this area. The definition
of Active Libraries helped turn these vague thoughts into a concrete goal: to realize
compilers and languages to support such libraries in earnest.
This dissertation proposes one possible direction for this.

Or, shorter:

Roughly speaking, this thesis addresses the question: How might we provide DSLs that are fast
and safe?

XML feed