Read an Excerpt
Chapter 1: Introduction
In a recent project of our department we adapted a compiler generation toolkit that produced Ada 83 code to the new Ada 95 standard. Because abstract syntax trees are a really good candidate to use object-oriented mechanisms like inheritance, polymorphism, and dispatch, we chose to rewrite the tools to take advantage of these new features of Ada. During the process of adaptation, we recognized that the Ada language would not allow us to do several things we would have liked to do and forced us to do things we did not want to do. One main problem was that we had not been able to define dispatching operations externally, that is, within a different package as the package the controlling type is defined in. A second, minor problem was the lack of a general mechanism to enable polymorphism over access types in Ada which necessitates many extra conversions in assignments. This paper investigates solutions to these problems and proposes an extension to Ada based on finite unions with dispatching that is very flexible, easy to understand, and efficiently implementable.
The contents of this paper are as follows: the next section will briefly discuss the problems we encountered when adapting the toolkit to produce Ada 95 code and present some possible solutions. Then, in section 3, we will propose a language extension based on finite unions that will be shown to not have the problems as class-wide polymorphism has and additionally allows some other flexibilities like multi-methods. An implementation model for finite unions is also given in that section. Finally, we compare finite unions with the concept of final classes as adopted by, e.g., the Javalanguage, before we summarize in section 4.
2 Problems with Adapting a Compiler Generation Toolkit to Ada 95The compiler generation toolkit Cocktail [10] developed by the "Gesellschaft fur Mathematik and Datenverarbeitung (GMD)" consists of several tools supporting the generation of scanners, parsers, abstract syntax trees, tree evaluators and transformers. For each of these tasks, one or more separate high level specifications may be given. The tools are designed such that each specification of new tree attributes is integrated into one single tree description (the package Tree) but each evaluator specification results in a separate package. Further, tree transformers and evaluators may be specified using the puma tool, which is based on pattern matching on tree nodes. Each puma file also generates a new Ada package. For a more detailed description of this project and the tools, refer to [3].
The approach followed by these tools has one important drawback when Ada 95 is used as target language: even though dispatching seems to be the appropriate solution to implement tree evaluator or transformer operations, this is not possible for the architecture given because Ada requires such operations to be declared in the same package as the controlling type. For example, an Eval routine in the package semantics, generated from an attribute evaluator specification, is forced to explicitly discriminate over the type (tag) of the current argument via nested if-statements-case-statements cannot be used because `Tag' is not a discrete type-which is clearly less efficient than using dispatching and less maintainable in case of hand-written code additions. If dispatching is to be used, Ada requires the Eval subprogram to be defined within the Tree package. There are three general approaches to this problem. First, we could adopt a different kind of architecture for the system. Second, we could try to work around this problem using the rich typing facilities of the Ada language. Third, a language extension could be proposed. We will consider each of these possibilities in the following subsections...