Higher-Order and Symbolic Computation, 11(4)353-354
EditorialOlivier Danvy and Carolyn Talcott
|
This issue concludes the journal's eleventh year, and its first year
with the name Higher-Order and Symbolic Computation (HOSC). The change
of name and the addition of six associate editors reflect both the
broadened scope of the journal and its continued commitment to provide
an active forum for results and ideas related to higher-order and
symbolic programming. HOSC's scope encompasses programming languages
that feature higher-order facilities--first-class functions and
continuations, effects and higher-order types, ob-jects, and
actors. Such languages include Lisp, Scheme, ML, Haskell, Java and
Dylan. We are interested in their design, semantics, implementation,
programming environments, andapplications. We are also interested both
in reasoning about programs and in manipulating programs as data, such
as in program analysis and in program transformation (e.g.,
partialevaluation). We will also continue to provide an active forum
for meta-level and reflective computation, for persistence, and for
concurrent, distributed, and mobile programs. Our primary mission is to publish new results and ideas. In addition to regular submissions, we also welcome tutorials and survey articles on topics of relevance. Papers on theory, design, and experimental results all lie within the scope of HOSC, especially if they reportwork exhibiting a mix of formalization, new insights, and applications. In addition to regular issues containing individual contributions, we will continue to publish special issues dedicated to a particular research topic, focusing on specific projects, or arising from a conference or workshop. Occasionally, we also publish papers of significant scientific and historical value thathave appeared only in conference proceedings or have only been available as technical reports or informally circulated notes. This issue is one of those occasions. It provides an archive for two seminal papers: John Reynolds's Definitional Interpreters for Higher Order Programming Languages and Gerald Sussman and Guy Steele's original Schemepaper, SCHEME: An Interpreter for Extended Lambda Calculus. Lisp introduced the idea of defining a programming language by writing an interpreterfor it. Because of its expressive power, Lisp also provided the linguistic support for writing such definitional interpreters with ease. McCarthy's definition of Lisp in Lisp generated a whirl of arguments and counter-arguments about both the value and the validity of this style of definition, reminiscent of Louis Armstrong's aphorism about jazz: "if you need to ask what jazz is, you don't understand it." In his paper, Reynolds dispassionately and methodically addresses the possibilities and the pitfalls of definitional interpreters. He classifies interpreters according to the features of both their defining language and their defined language, and observes the following remarkable phenomenon: with an interpreter expressed in direct style, the defined language inherits the evaluation order of the defining language. With an interpreter expressed in continuation-passing style, however, this is no longer the case. Both because of its results and because of its methodology (e.g., defunctionalization), Reynolds's paper has exercised a profound influence on the general area of programming languages. With an elegant twist, it also introduced the neologism "metacircular" to designate an interpreter where defining language and defined language coincide. Hewitt's actor model provides a model of distributed computation which is both tantalizing and mystifying, and continues to remain the subject of active research. In the mid-seventies, with a solid Lisp background, Sussman and Steele set out to demystify actors by implementing them. As the story goes, they removed many layers of syntactic sugar and essentially re-discovered the lambda-calculus: a procedural language where variables live in a single name space and obey lexical scope. Out of pragmatism, however, this language follows call-by-value and extends the lambda-calculus with literals and primitive operations, conditional expressions, assignments, i/o, and first-class continuations. In hindsight, one can recognize that right from the start, Scheme gave a central place to Landin's notion of closures in what is otherwise essentially the universe of Lisp. Function closures implement first-class, lexically scoped functions as values, and program closures implement first-class continuations as we know them today: Scheme's then control operator catch precisely corresponds to Scheme's present control operator call/cc (and to John Reynolds's escape operator). The original Scheme report has also been profoundly influential in that it has introduced the notion of proper tail-recursion and of continuation-passing style into the Lisp universe. Indeed the term "continuation-passing style" first appeared here. As one can observe though, it wasn't CPS yet. |