Lambda the Ultimate

In functional programming, programs are often written in a compositional style. There are many advantages to this, such as clarity and modularity, but the resulting programs can be inefficient in terms of space, due to the use of intermediate data structures. These structures may be removed using deforestation techniques, but whether the space performance is actually improved depends on the structures being consumed in the same order that they are produced. In this paper we explore this problem and suggest a solution, in particular for lists and then generalising to trees.

Since the paper discusses many examples, it is quite enjoyable to read and can even serve as an introduction to folds.

The workshop on Synchronization and Concurrency in Object-Oriented Languages has a nice, accessible collection of papers on software transactional memory and other language-based approaches to building concurrent systems.

I've become enamored with Backus's FP language (and the lesser known follow-up FL) as of late. Does anyone know of *any* programs written in either of these languages that are outside the 1-3 line toy variety? I've found nothing. Even 10+ line toy programs would be fine, but a larger program would be even better.

(For programs in a related style there's Iverson's J, but I'd still like to see some real FP programs.)

Classic Java

This collection is an implementation of (most of) ClassicJava, as defined
in "A Programmer's Reduction Semantics for Classes and Mixins," by Matthew
Flatt, Shriram Krishnamurthi, and Matthias Felleisen; in _Formal Syntax and
Semantics of Java_, Springer-Verlag LNCS 1523, pp. 241-269, 1999. A
tech-report version of the paper is also available at
<http://www.ccs.neu.edu/scheme/pubs/#tr97-293. The implementation is
written in PLT Redex, also available through PLaneT. Please consult that
package's documentation for further details.

Module Mania: A Type-Safe, Separately Compiled, Extensible Interpreter

To illustrate the utility of a powerful modules language, this paper presents the embedded interpreter Lua-ML. The interpreter combines extensibility and separate compilation without compromising type safety. Its types are extended by applying a sum constructor to built-in types and to extensions, then tying a recursive knot using a two-level type; the sum constructor is written using an ML functor. The initial basis is extended by composing initialization functions from individual extensions, also using ML functors.

This is an excellent example of how the ML module language doesn't merely provide encapsulation but also strictly adds expressive power. It also demonstrates how a dynamic language (Lua) can be embedded in the statically-typed context of ML. Finally, it demonstrates that none of this need come at the expense of separate compilation or extensibility. Norman Ramsey's work is always highly recommended.