COMPILE-TIME EVALUATION AND CODE GENERATION FOR SEMANTICS-DIRECTED COMPILERS (DENOTATIONAL)

Programming languages have traditionally been specified in two different forms: by informal (and often imprecise) descriptions in reference manuals, and by implementations of compilers. While the latter are necessarily quite formal (as they must to be executed by computers), they do not serve as a good means to communicate programming language semantics, or as a good basis for reasoning about programs.; Since the introduction of Denotational Semantics to describe programming language semantics, significant progress has been made in being able to automatically derive compilers from Denotational Semantic specifications of programming languages. These specifications can be used both for communication between designers and users, and for automatic translation from the languages they specify into executable machine code.; The compilers produced by such semantics-directed compiler generators have not been as powerful as conventional compilers, in two ways. Some automatically-generated compilers produce semantic structures which must be interpreted many orders of magnitude slower than the equivalent machine code produced by a conventional compiler. Others produce efficient machine code but only handle a small subset of a typical programming language's semantics.; Both of these problems are a consequence of an inability to do enough compile-time evaluation. For example, in a language like Pascal, all of the type checking and representation selection can and should be done at compile time.; By choosing a set of combinators which intuitively correspond to register-transfer operations (the atomic operations of von Neumann machines) the process of compilation can be treated as the reduction of a (large) (lamda)-expression to a normal form in these combinators. Compile-time evaluation during the reduction to normal form includes the allocation of static storage, the selection of data-type representations, type checking and coercion, and constant folding.; An algorithm is given for generating code from the normal form. Thus, a true compiler, not just an interpreter, is specified by giving a Denotational Semantics for the language. The compiler-generator has been fully implemented; it has been used to specify working compilers for Pascal and C. The automatically-generated compilers are slow. However, the machine code they produce is comparable in efficiency to what is produced by conventional hand-built compilers.