# Semantics of Programming Languages: A Tool-Oriented ApproachThis research was supported in part by the Telematica Instituut under the Domain-Specific Languages project.

## 1 The Role of Programming Language Semantics

Programming language semantics has lost touch with large groups of potential users . Among the reasons for this unfortunate state of affairs, one stands out. Semantic results are rarely incorporated in practical systems that would help language designers to implement and test a language under development, or assist programmers in answering their questions about the meaning of some language feature not properly documented in the language’s reference manual. Nevertheless, such systems are potentially more effective in bringing semantics-based formalisms and techniques to the places they are needed than their dissemination in publications, courses, or even exemplary (but little-used) programming languages.

The current situation in which semantics, languages, and tools are drifting steadily further apart is shown in Figure 2. The tool-oriented approach to semantics aims at making semantics definitions more useful and productive by generating as many language-based tools from them as possible. This will, we expect, reverse the current trend as shown in Figure 2. The goal is to produce semantically well-founded languages and tools. Ultimately, we envision the emergence of “Language Design Assistants” incorporating substantial amounts of semantic knowledge.

Table 1 lists the semantics definition methods we are aware of. Examples of their use can be found in . Petri nets, process algebras, and other methods that do not specifically address the semantics of programming languages, are not included. Dating back to the sixties, attribute grammars and denotational semantics are among the oldest methods, while abstract state machines (formerly called evolving algebras), coalgebra semantics, and program algebra are the latest additions to the field. Ironically, while attribute grammars are popular with tool builders, semanticists do not consider them a particularly interesting definition method. Since we will only discuss the various methods in general terms without going into technical details, the reader need not be familiar with them. In any case, the differences between them, while often hard to decipher because the field is highly fragmented and appropriate “dictionaries” are lacking, do not affect our main argument.

Table 2 lists a representative language development system (if any) for the semantics definition methods of Table 1. The last entry, Software Refinery, which has its origins in knowledge-based software environments research at Kestrel Institute, does not fit any of the current semantics paradigms. The pioneering Semanol system  is, to the best of our knowledge, no longer in use and is not included. The systems listed have widely different capabilities and are in widely different stages of development. Before discussing their characteristics and applications in Section 3, we first explain the general ideas underlying the tool-oriented approach to programming language semantics. These were shaped by our experiences with the ASF+SDF Meta-Environment (Table 2) over the past ten years. Finally, we discuss Language Design Assistants in Section 4.

## 2 A Tool-Oriented Approach to Semantics

The tool-oriented approach to semantics aims at making semantics definitions more useful and productive by generating as many language-based tools from them as possible. This affects many aspects of the way programming language semantics is practiced and upsets some of its dogmas.

Table 3 lists some of the tools that might be generated. In principle, the language definition has to be augmented with suitable tool-specific information for each tool to be generated, and this may require tool-specific language extensions to the core semantics definition formalism. In practice, this is not always necessary since semantics definitions tend to contain a good deal of implicit information that may be extracted and used for tool generation.

The first entry of Table 3, scanner and parser generation, is standard technology. Lex and Yacc are well-known examples of stand-alone generators for this purpose. Their input formalisms are close to regular expressions and BNF, the de facto standard formalisms for regular and context-free grammars, respectively. Unfortunately, for most of the other tools in Table 3 there are no such standard formalisms.

The key features of the tool-oriented approach are:

* Language definitions are primarily tool generator input. They do not have to provide any kind of theoretical “explanation” of the constructs of the language in question nor do they have to become part of a language reference manual.
* An interpreter that can act, among other things, as an “oracle” to programmers needing help will be among the first tools to be generated.
* Writing (large) language definitions loses its esoteric character and becomes similar to any other kind of programming. Semantics formalisms tend to do best on small examples, but lose much of their power as the language definitions being written grow. In the tool-oriented approach, semantics formalisms have to be modular and separate generation (the analogue of separate compilation) has to be supported. Libraries of language constructs become important.
* The tool-oriented approach may require addition of tool-specific features to the core formalism. This leads to an open-ended rather than a “pure” style of semantics description.
* The scope of the tool-oriented approach includes, for instance,

+ Domain-specific and little languages . Many of the tools in Table 3 are as useful for DSLs as they are for programming languages.
    + Software maintenance and renovation tools . Some of these are included at the end of Table 3.
    + Compiler toolkits such as CoSy , Cocktail , OCS , SUIF , and PIM .

## 3 Existing Language Development Systems

Table 4 summarizes the tool generation capabilities of the representative language development systems listed in Table 2. All of them can generate lexical scanners, parsers, and prettyprinters, many of them can produce syntax-directed editors, typecheckers, and interpreters, and a few can produce various kinds of software renovation tools. To this end, they support one or more specification formalisms, but these differ in generality and application domain.

For instance, the Synthesizer Generator supports attribute grammars with incremental attribute evaluation, which is particularly suitable for typechecking, static analysis and translation, but less suitable for dynamic semantics. The ASF+SDF Meta-Environment supports conditional rewrite rules rather than attribute grammars, and these can be used for defining dynamic semantics as well. Software Refinery comes with a full-blown functional language in which a wide range of computations on programs can be expressed. Other systems provide more specialized specification formalisms. PSG, for instance, uses context relations to describe incremental typechecking (even for incomplete program fragments) and denotational definitions for dynamic semantics. Gem-Mex supports a semi-visual formalism optimized for the definition of programming language semantics and tool generation. It can generate a typechecker, an interpreter, and a debugger.

Table 4 is far from complete. Some other language development systems are SIS , PSP , GAG , SPS , MESS , Actress , Pregmatic , LDL , and Eli . Many of the tools listed in Table 3 are not generated by any current system. Ample opportunities for tool generation still exist in areas like optimization, dynamic program analysis, testing, and maintenance.

## 4 Toward Language Design Assistants

The logical next step beyond semantics-based tool generation would lead to a situation similar to that of computer algebra. Large parts of mathematics are being incorporated in computer algebra systems. Conversely, computer algebra itself has become a fruitful mathematical activity, yielding new results of general mathematical interest. In the case of semantics, we see opportunities for “Language Design Assistants” incorporating a substantial amount of both formal and informal semantic knowledge. The latter is found, for instance, in language design rationales and discussion documents produced by standardization bodies. Development of such assistants will not only push semantics even further toward practical application, but also give rise to new theoretical questions.

The Language Design Assistants we have in mind would support the human language designer by providing design choices and performing consistency checks during the design process. Operational knowledge about typical issues like typing rules, scope rules, and execution models should be incorporated in them. Major research questions arise here regarding the acquisition, representation, organization, and abstraction level of the required knowledge. For instance, should it be organized according to any of the currently known paradigms of object-oriented, functional, or logic programming? Or should a higher level of abstraction be found from which these and other, new, paradigms can be derived? How can constraints on the composition of certain features be expressed and checked? Another key question is how to construct a collection of “language feature components” that are sufficiently general to be reusable across a wide range of languages.

Similar considerations apply to tool development. By incorporating knowledge about tool generation in the Language Design Assistant we can envision a Tool Generation Assistant that helps in constructing tools in a more advanced way than the tool generation we had in mind in the previous sections.

To make this perspective somewhat more tangible, consider the relatively simple case of an if-then-else-like conditional construct that has to be modelled as a language feature component. Table 5 gives an impression of the wide range of issues that has to be addressed before such a generic conditional construct can be specialized into a concrete if-then-else-statement or conditional expression in a specific language. It is a research question to design an abstract framework in which these and similar questions can be expressed and answered.

Another major question is how to organize the specialization process from language feature component to concrete language construct. The main alternatives are parameterization and transformation . Using parameterization, specialization of the component in question amounts to instantiating its parameters. Since parameters have to be identified beforehand and instantiation is usually a rather simple mechanism, the adaptability/reusability of a parameterized component is limited. Using transformations, on the other hand, a language feature component is designed without explicit parameters. Specialization is achieved by applying appropriate transformation rules to it to obtain the desired specific case. Clearly, this approach is more flexible since any part of the language feature component can be modified by the transformation rules and can thus effectively act as a parameter. The relation between this approach of meta-level transformation and parameterized modules is largely unexplored.

Although we are not aware of research on Language Design Assistants from the broad perspective sketched here, there is some work pointing in the same general direction:

* The Language Designer’s Workbench sketched as future work in  has some of the same goals.
* Action semantics  also emphasizes libraries of reusable language constructs.
* Plans (no longer pursued) for the Language Development Laboratory  included a library of reusable language constructs, a knowledge base containing knowledge of languages and their compilers/interpreters, and a tool for language design.
* The “design and implementation by selection” of languages described in  is a case study in high-level interactive composition of predefined language constructs.

### Acknowledgements

We would like to thank Jan Bergstra, Mark van den Brand, Arie van Deursen, Ralf Lämmel, and Jan Rutten for useful comments on earlier versions.