Catalogue of emerging techniques

The 3-Lisp LSP is now ten years old. Since then, a lot of exciting tools and techniques have emerged from the research on the implementation of reflective languages, but also dynamic languages such as Prolog, Common Lisp, Scheme, ML, CLOS, Smalltalk, Self, and others ⁸. Several of them appear necessary for the efficient implementation of reflective languages, including:

• Dynamic compilation: in languages like Smalltalk [DS84] and Self [CUL89], it is now routine to compile methods at run-time. In both of these languages, methods are first compiled from the source language text to byte-codes at creation time. On demand, at call time, the byte-codes are compiled to native code to be run by the underlying processor. The native code is cached to be reused from invocation to invocation. Although run-time code generation has been in use since the 1940s, few language implementations, besides the dynamic languages Smalltalk and Self (and 3-Lisp!), are using this technique. Although it has fallen from favor because practices and technology changed, implementors now see it as a way to improve the performance of applications through the use of run-time information. ``The crux of the argument is that, although it costs something to run the compiler at run-time, run-time code generation can sometimes produce code that is enough faster to pay back the dynamic compile costs'' [KEH91]. Engler and Proebsting reports the construction of a machine-independent run-time code generator called DCG [EP94] while Leone and Lee apply run-time code generation to the optimization of ML [LL95].
• Reified compilers: in Smalltalk, the compiler from the source language to byte-codes is written in Smalltalk and available to the users. Although scarcely documented and publicized, it is perfectly possible, and even legitimate, to modify this compiler [Riv96]. Methods also have a field recording their preferred compiler, which may thus differ from the standard one. Open compilers [LKRR92] propose a methodical development of this technique (see §4.3).
• Adaptative run-time systems: families of compilers often share an important part of their run-time systems [Web92]. This kind of reuse does not only simplify the maintenance of compilers, it also paves the way to run-time adaptiveness of compilers to applications. Another example of adaptative run-time systems is the possiblity to choose among several alternative implementations for programming languages ADTs depending on profile data [Sam92].
• First-class continuations and call/cc: Scheme [CR91] provides first-class continuations, so a lot of effort has been directed towards their efficient implementation and the one of the related call/cc. Combined with Smalltalk reified stack frames [Riv96], the Scheme first-class continuations approach will serve as a strong basis for this crucial part of behavioral reflection dealing with control issues.
• Partial evaluation: Partial evaluation is a fairly general tool that specializes functions (programs) given a known subset of their actual parameters [JGS93]. The specialization engine of partial evaluation is essentially based on unfolding function calls. Applications of partial evaluation to reflective languages have been reported by Danvy [Dan88], Ruf [Ruf93] and more recently by Masuhara et al. [MMAY95] (see §4.3).
• Binding-time analysis: crucial to partial evaluation is the ability to statically determine the binding time of the value of each expression in a program, and to segregate among those known at compile time (static) from those known only at run-time (dynamic). In functional programming, good binding time analyses (BTA) [Con90] have been developed. The result of these analyses also enables various optimizations.
• Other static analyses: a lot of interest is currently raised by static analyses in general. Besides the constraint propagation approach developed in standard compiler technique and for object-oriented languages, abstract interpretation is now rapidly developing in functional and logic programming. Analyses based on type inference techniques are also more and more widely used [PS94].
• Compiler generation: automatic compiler generation is an important research theme since almost two decades now (look at [Lee89] for a survey). Despite the problems we still face, recent developments make us believe that it will play a substantial role in the future of reflective languages.
• Monads: introduced by Moggi [Mog89,Mog91] and popularized by Wadler [Wad90,Wad92], monads are categorical constructions that have been advocated for the modular extension of interpreters or denotational semantics. As descriptions of programming language semantics, monads are currently being investigated as a means to describe different programming language features and compose them in a general framework [LHJ95,Ste94,JD93,Fil94]. They are also considered for the automatic generation of efficient compilers [LH95].