To verify that such context conditions are satisfied, the compiler must determine the result type of each expression. This computation uses information from the language definition about the set of legal operators, and information about the types of identifiers and denotations. The type of a denotation can be determined by the kind of basic symbol, but the type of an identifier is determined by its declaration and that information must be conveyed from the point of declaration to the point of use.
Type consistency checks therefore involve several distinct components:
The definition table is a general database, in which each entity is represented by a unique definition table key. Properties of the entity are accessed via operations taking the definition table key as an argument. Each property has its own set of query and update operations. Figure 7.12 shows two basic access operations, which illustrate possible interfaces; an implementation of these interfaces appears in Figure 7.15.
Eli also supports this paradigm with a definition table module implemented as described in Section 7.2. Section 7.2.3 notes that implementation of the property-dependent code for access functions is trivial, but it is obvious that this implementation is burdensome when the number of properties is large. Thus Eli provides a simple property definition language (PDL). When a user describes the desired properties in PDL, Eli can generate a set of basic access functions. More complex behavior, including arbitrary access functions and property initialization, can be specified in PDL.
The most critical aspect of dependence on side effects is recognizing its presence. When we write programs, we seldom consider side effects explicitly because we account for them implicitly in the sequence of operations. Traversal strategies in a compiler are sufficiently complex that we cannot rely on implicit ordering of code. Whether we write code or specifications, we must carefully consider the question of dependence on side effects in our design. Here is a proven strategy:
In most cases the precondition relations determined in step (3) can be stated as either ``do all operations in the order in which their contexts appear in the program'' or ``do all updates before doing any queries''.
The precondition relations for the Value property of a variable in Appel's straight-line programming language can be stated as ``do all operations in the order in which their contexts appear in the program'': Assignments to a variable update its Value property and uses of a variable query its Value property. The left-to-right semantics of the language then demand these precondition relations. Recall that they were encoded in C++ as a depth-first, left-to-right traversal implemented by a single visitor, and they were specified in Eli by a VOID chain.
The precondition relations for the EntityClass property of an identifier (Waite, Section 7.2.1) can be stated as ``do all updates before doing any queries'': At each defining occurrence, the EntityClass property is set to some classification (like VariableName) if it has not been set before, and to MultiplyDefined if it has been set before. It is also examined at each defining occurrence and an error report is issued if its value is MultiplyDefined. The precondition relations ``do all updates before doing any queries'' are required to be able to issue the error report at every defining occurrence (including the first) of a multiply-defined identifier. They can be encoded in a traversal strategy by placing all of the updating computations in one traversal and all of the querying computations in a later traversal. In Eli, they can be specified as follows:
SYMBOL ROOTCLASS COMPUTE SYNT.AllEntityClassesDone=CONSTITUENTS DefiningOccurrence.EntityClassDone; END;
SYMBOL DefiningOccurrence COMPUTE SYNT.EntityClassDone=SetEntityClass(THIS.Key,THIS.Kind,MultiplyDefined); IF(EQ(GetEntityClass(THIS.Key,NotDefined),MultiplyDefined), message(ERROR,"Multiply defined",0,COORDREF)) <- INCLUDING ROOTCLASS.AllEntityClassesDone; END;
This example uses the basic query and update operations of the Eli definition table module. ROOTCLASS is a predefined LIDO symbol implicitly inherited by the root of the tree grammar. Thus AllEntityClassesDone is an attribute of the root, and CONSTITUENTS DefiningOccurrence.EntityClassDone ensures that AllEntityClassesDone depends on all of the SetEntityClass update operations. In turn, INCLUDING ROOTCLASS.AllEntityClassesDone ensures that each of the GetEntityClass query operations depends on the AllEntityClassesDone attribute of the root. Since dependence is transitive, the precondition relation ``do all updates before doing any queries'' is guaranteed.
Generally speaking, the compiler must identify the operator of an expression in order to determine the type of the result of that expression. Operator identification in C-- involves matching the pattern represented by the ``Indication'' and ``Operand Type'' columns in Table A.1 to the information present at a tree node. Each pattern uniquely identifies one of the operations in the rightmost column of the table, and hence fixes the result type. The problem is complicated by the presence of coercions that allow the compiler to convert values of one type into values of another.
Appel's Section 5.3 shows how a specification like Waite's Table A.1 can be implemented by writing switch statements and conditionals. This strategy allows the implementor to take advantage of regularities in the patterns to simplify the code. For example, the results of all of the overloadings of ==, < and> have type int in C-- and therefore no tests are needed for those indications.
Appel's strategy can be easily applied to C-- type analysis using either C++ code or Eli specifications. The necessary operations would be carried out by a visitor in a C++ implementation, or by rule computations in a LIDO implementation. As Appel points out in Section 5.3, certain cases are common enough to warrant additional function definitions. When using Eli, those functions would be written in C and invoked from the LIDO rule computations. The actual design is straightforward, and essentially independent of whether C++ code or an Eli specification is ultimately produced.
C-- presents a simple type analysis problem, having only two types and one coercion (see Waite, Sections A.1.5.1 and A.1.5.2). As the number of types and coercions increases, or user-defined types are allowed, Appel's strategy becomes less appealing. A better approach under those circumstances is to implement general operations that can be applied to data encoding the set of types and coercions. This kind of tradeoff, between solving a problem with specialized code and solving it with generalized code operating on specialized data, is a common one in software design.
Section 10.1 of Waite presents a data-driven solution to the type analysis problem. The presentation is concerned with two distinct questions:
Although it is possible to use a single process to answer both questions, this unnecessarily complicates both the explanation and the implementation. In this course we split the two questions and answer them in different, but related, ways. Even with the split, however, all of the material in Section 10.1 is applicable to type analysis. The only difference is that the sets of types and operators are determined solely by the source language, rather depending on a mixture of source language and target machine considerations as described at the beginning of Section 10.1.1.
Eli provides an implementation of the operator identification module sketched in Section 10.3. Its interface differs somewhat from that described in Figure 10.3 because the module is implemented in C, but it provides the same functionality. It also supports simpler operator identification operations that can be used when operators can be identified without considering the contexts in which they occur (C-- satisfies this constraint). Finally, Eli provides a specification language for describing the relationships among types, coercions and operators. This language allows one to specify the data for the operator identification module in a form very much like that of Table A.1.
Write a brief description of the tasks to be carried out by each team member for the next assignment, giving a rationale for your partitioning. Submit this description to email@example.com before the beginning of class on the due date.
Complete your personal postmortem for this assignment and your personal project plan for the next assignment, and submit them via the web before class on the due date of this assignment.
|Instructor||Revision 1.6 (1998/09/19 21:21:24)|