Compiler Design: Virtual Machines
Format: PDF / Kindle (mobi) / ePub
While compilers for high-level programming languages are large complex software systems, they have particular characteristics that differentiate them from other software systems. Their functionality is almost completely well-defined – ideally there exist complete precise descriptions of the source and target languages, while additional descriptions of the interfaces to the operating system, programming system and programming environment, and to other compilers and libraries are often available. The implementation of application systems directly in machine language is both difficult and error-prone, leading to programs that become obsolete as quickly as the computers for which they were developed. With the development of higher-level machine-independent programming languages came the need to offer compilers that were able to translate programs into machine language. Given this basic challenge, the different subtasks of compilation have been the subject of intensive research since the 1950s.
This book is not intended to be a cookbook for compilers, instead the authors' presentation reflects the special characteristics of compiler design, especially the existence of precise specifications of the subtasks. They invest effort to understand these precisely and to provide adequate concepts for their systematic treatment. This is the first book in a multivolume set, and here the authors describe what a compiler does, i.e., what correspondence it establishes between a source and a target program. To achieve this the authors specify a suitable virtual machine (abstract machine) and exactly describe the compilation of programs of each source language into the language of the associated virtual machine for an imperative, functional, logic and object-oriented programming language.
This book is intended for students of computer science. Knowledge of at least one imperative programming language is assumed, while for the chapters on the translation of functional and logic programming languages it would be helpful to know a modern functional language and Prolog. The book is supported throughout with examples, exercises and program fragments.
closely related. So far, we have only considered memory allocation for variables that are introduced by declarations. In the declaration, a name is introduced for the object, and a static (relative) address is assigned to this name. If a programming language supports pointers, these can be used to access objects without names. Linked data structures can be implemented by means of pointers. Their size may vary dynamically, and individual objects are not allocated by a declaration, but via a
which defines the function int main(). Note that, for simplicity, we do not consider command line parameters for the function main. The code for program p, thus, consists of: 46 • • • • 2 Imperative Programming Languages code for the allocation of global variables; code for the function definitions; code for the call of function main; the instruction halt, to terminate program execution. For simplicity, we assume that the variable declarations in p appear before the function declarations.
→ pushglob j New instructions are required for handling local and global variables. To access a local variable, the instruction pushloc n is used (Fig. 3.10). This instruction pushes the contents of the stack location with address n relative to the current SP on top of the stack. Let sp and sl be the current value of the stack pointer SP and the stack pushloc n n S[ SP + 1] ← S[ SP − n]; SP++; Fig. 3.10. The instruction pushloc n 72 3 Functional Programming Languages level, respectively. Our
our optmized code generation for variable accesses only arises with recursive definitions of variables by variables where a variable y is used as the right side before the dummy closure corresponding to y has been overwritten. Luckily, we can avoid this problem first, by disallowing at translation time cyclic variable definitions such as y = y and, second, by organizing definitions yi = y j such that the dummy closure for y j is always overwritten before the dummy closure for yi . The code
creates a new unbound variable, pushes a reference to it onto the stack, but does not save a reference for it in the stack frame (Fig. 4.7). putanon FP R FP SP++; H [ HP] ← ( R, HP); S[ SP] ← HP; HP++; Fig. 4.7. The instruction putanon The instruction putref i pushes the reference from S[ FP + i ] onto the stack and then 4.3 Allocation of Terms in the Heap 113 putref i i FP FP SP++; S[ SP] ← deref ( S[ FP + i ]); Fig. 4.8. The instruction putref i dereferences it as much as possible.