Lambda the Ultimate

This is not a PLT paper, but I found the programming adventures of mathematicians trying to compute the Kazhdan-Lusztig polynomials for E8 very interesting: The Character Table for E8 by David Vogan. The software part begins on page 9.

I wish he had expanded on the following (emphasis mine in bold):

So late in 2004, Fokko began to add to his software an implementation of the Kazhdan-Lusztig algorithm for real groups. The papers in which this algorithm is formulated are extremely dense, and written with no consideration for computational practice. An expert could easily spend many months just to understand the mathematical statements. Fortunately, Jeff Adams had been working on a new formulation of Theorem 6 (parametrizing irreducible representations), growing out of earlier work that he did with Dan Barbasch and me. Jeff's formulation seemed suited to computer implementation; he had been working with Fokko to make it more so.

Over the course of the next year, Fokko understood the Kazhdan-Lusztig algorithm for real groups, recasting it in the language that he and Jeff had developed. He wrote clear and efficient code to implement it. In November of 2005 --incredibly soon!-- he finished. Very quickly he and Jeff used the software to compute Kazhdan-Lusztig polynomials (and so character tables) for all of the real forms of F4, E6, and E7, and for the non-split form of E8.

Expression and Loop Libraries for High-Performance Code Synthesis. Christopher Mueller and Andrew Lumsdaine. LCPC2006.

To simultaneously provide rapid application development and high performance, developers of scientific and multimedia applications often mix languages, using scripting languages to glue together high-performance components written in compiled languages. While this can be a useful development strategy, it distances application developers from the optimization process while adding complexity to the development tool chain. Recently, we introduced the Synthetic Programming Environment (SPE) for Python, a library for generating and executing machine instructions at run-time.

The authors didn't show much interest yet in supporting the most widespread ISAs, those for Intel processors. Instead they focus on PowerPC but also Cell. Have fun with Python and PS3 hacking.

Edit: You might also checkout the site of Christopher Mueller containing related material.

Morphing: Safely Shaping a Class in the Image of Others, Shan Shan Huang, David Zook, and Yannis Smaragdakis. ECOOP 2007.

We present MJ: a language for specifying general classes whose members are produced by iterating over members of other classes. We call this technique “class morphing” or just “morphing”. Morphing extends the notion of genericity so that not only types of methods and fields, but also the structure of a class can vary according to type variables. This offers the ability to express common programming patterns in a highly generic way that is otherwise not supported by conventional techniques. For instance, morphing lets us write generic proxies (i.e., classes that can be parameterized with another class and export the same public methods as that class); default implementations (e.g., a generic do-nothing type, configurable for any interface); semantic extensions (e.g., specialized behavior for methods that declare a certain annotation); and more. MJ’s hallmark feature is that, despite its emphasis on generality, it allows modular type checking: an MJ class can be checked independently of its uses. Thus, the possibility of supplying a type parameter that will lead to invalid code is detected early—an invaluable feature for highly general components that will be statically instantiated by other programmers.

This is related to the paper by Turon and Reppy I linked to yesterday; it's another take on compile-time metaprogramming. This time they have a static iteration over the structure of a class, which makes their safety result rather impressive. I talked Huang, and she told me that their big-picture goal is to eventually build a full language for manipulating programs at compile time, while still preserving all the safety guarantees we expect.