Filetype PDF | Posted on 07 Feb 2023 | 2 years ago
Authentication
digital resources
131x Filetype PDF File size 0.12 MB Source: www.inf.ed.ac.uk
Future Generation Computer Systems 16 (2000) 739–751
Abstract machines for programming language implementation
Stephan Diehla,∗, Pieter Hartelb, Peter Sestoftc
a FB-14 Informatik, Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany
b Department of Electronics and Computer Science, University of Southampton, Highfield, Southampton SO17 1BJ, UK
c Department of Mathematics and Physics, Royal Veterinary and Agricultural University, Thorvaldsensvej 40,
DK-1871Frederiksberg C, Denmark
Accepted 24 June 1999
Abstract
We present an extensive, annotated bibliography of the abstract machines designed for each of the main programming
paradigms(imperative, object oriented, functional, logic and concurrent). We conclude that whilst a large number of efficient
abstract machines have been designed for particular language implementations, relatively little work has been done to design
abstract machines in a systematic fashion. ©2000 Elsevier Science B.V. All rights reserved.
Keywords: Abstract machine; Compiler design; Programming language; Intermediate language
1. What is an abstract machine? next instruction to be executed. The program counter
is advanced when the instruction is finished. This ba-
Abstract machines are machines because they per- sic control mechanism of an abstract machine is also
mit step-by-step execution of programs; they are known as its execution loop.
abstract because they omit the many details of real
(hardware) machines. 1.1. Alternative characterizations
Abstract machines provide an intermediate lan-
guage stage for compilation. They bridge the gap The above characterization fits many abstract ma-
between the high level of a programming language chines, but some abstract machines are more abstract
and the low level of a real machine. The instructions than others. The extremes of this spectrum are char-
of an abstract machine are tailored to the particu- acterized as follows:
lar operations required to implement operations of a • An abstract machine is an intermediate language
specific source language or class of source languages. with a small-step operational semantics [107].
Common to most abstract machines are a program • An abstract machine is a design for a real machine
store and a state, usually including a stack and regis- yet to be built.
ters. The program is a sequence of instructions, with a
special register (the program counter) pointing at the 1.2. Related terms
∗ Corresponding author. Tel.: +49-681-302-3915. The term abstract machine is sometimes also used
E-mail addresses: diehl@cs.uni-sb.de (S. Diehl), for different concepts and other terms are used for
phh@ecs.soton.ac.uk (P. Hartel), sestoft@dina.kvl.dk (P. Sestoft) the concept of abstract machines, e.g. some authors
0167-739X/00/$ – see front matter ©2000 Elsevier Science B.V. All rights reserved.
PII: S0167-739X(99)00088-6
740 S. Diehl et al./Future Generation Computer Systems 16 (2000) 739–751
use the terms emulator or interpreter and some use for the same source language. But also some system-
the term virtual machine for implementations of ab- atic approaches have been investigated. Wand was one
stract machines, similar as we use the term program of the first to deal with the question of deriving ab-
for implementations of an algorithm. Sun calls its stract machines from the semantics of a language. In
abstract machine for Java the Java Virtual Machine 1982, he proposed an approach based on combinators
[86,91]. The term virtual machine is widely used for [130]. To find suitable combinators was not automated
the different layers of abstractions in operating sys- andwasadifficulttask,whichwassimplifiedinalater
tems [121] and in IBM’s VM operating system virtual paper[131].TheCAM(1985)wasderivedinasimilar
machines are execution environments for running way [34]. Another approach is based on partial eval-
several versions of the same operating system on the uation of interpreters with given example programs
same machine. In theoretical computer science the and folding of recurring patterns in the intermediate
term abstract machine is sometimes used for models code [44,80,98]. Finally there are approaches based
of computation including finite state machines, Mealy on pass separation [45,56,70,89,116]. Pass separation
machines, push down automata and Turing machines is a transformation which splits interpreters into com-
[61]. piling and executing parts, the latter being the abstract
machine. It has also been used in the 2BIG system
1.3. What are abstract machines used for? (1996) to automatically generate abstract machines
In the above characterization of abstract machines from programming language specifications [43,46].
their use as an intermediate language for compila-
tion is an essential feature. As a result the imple- 3. Abstract machines for imperative
mentation of a programming language consists of two programming languages
stages. The implementation of the compiler and the
implementation of the abstract machine. This is a typ- Discussions in the late fifties within the ACM and
ical divide-and-conquer approach. From a pedagogi- otherrelatedbodiesresultedinvariousproposalsbeing
cal point of view, this simplifies the presentation and madeforanUNCOL:AUNiversalComputerOriented
teaching of the principles of programming language Language. Various UNCOLs have been proposed.
implementations. From a software engineering point Conway’s machine [33] for example was a register
of view, the introduction of layers of abstraction in- machine, with two instructions. Steel’s machine [119]
creases maintainability and portability and it allows had sophisticated adressing modes. The principle of
for design-by-contract. Abstract machines have been an UNCOL is sound, but they have not been much
successful for the design of implementations of lan- used. We believe that this is mainly because of the
guages that do not fit the “Von-Neumann computer” lack of performance of the generated code. Chow and
well. As a consequence most abstract machines are for Ganapathi [30] give an overview of abstract machines
exotic or novel languages. There are only few abstract for imperative programming languages that were cur-
machines for languages like C or Fortran. Recently rent in the mid-1980s. Some believe that the Java Vir-
abstract machines have been used for mobile code in tual Machine [86] of the late 1990s might finally play
heterogenous networks such as the Internet. the role of an UNCOL, but we think that performance
In addition to all their practical advantages abstract will remain a concern in many areas of computing.
machines are theoretically appealing as they facilitate We will now look at some successful abstract ma-
to prove the correctness of code generation, program chines, which were designed for rather more modest
analyses and transformations [20,111]. goals:
• The Algol Object Code (1964) [109] is an abstract
2. Where do abstract machines come from? machine for Algol60. It has a stack, a heap and
a program store. Its instructions provide mecha-
Abstract machines are often designed in an ad-hoc nisms for variable and procedure scope, allocation
manner based on experience with other abstract ma- of memory, access to variables and arrays, and
chines or implementations of interpreters or compilers call-by-value and call-by-name procedure calls.
S. Diehl et al./Future Generation Computer Systems 16 (2000) 739–751 741
• The P4-machine (1976) is an abstract machine for op-code and a five-bit ‘index’, or instruction argu-
the execution of Pascal programs, developed by ment. The eight instructions are: push self, push
Wirth and colleagues [7]. The compiler from Pascal literal, send message (to invoke a method or access
to P4andtheabstractmachinecodearedocumented a field), self send, super send, delegate (to a par-
in [102]. The P4 machine has fixed-length instruc- ent), return, and index extension. The bytecode is
tions. It implements block structure by a stack of ac- dynamically translated into efficient machine code
tivation records (frames), using dynamic and static [28,29].
links to implement recursion and static scoping, re- • Java (1994) is a statically typed class-based
spectively. object-oriented language, whose ‘official’ interme-
• The UCSD P-machine [32] is an abstract ma- diate language is the statically typed Java Virtual
chine for the execution of Pascal programs, with Machine (JVM) bytecode. The JVM has special
variable-length instructions. The compact bytecode support for dynamic loading and linking, with
of the machine has special instructions for calling load-time verification (including type checking) of
Pascal’s nested procedures, for calling formal pro- the bytecode. The instruction set supports object
cedures, for record and array indexing and index creation, field access, virtual method invocation,
checks, for handling (Pascal) sets, for signalling casting an object to a given class, and so on [86].
and waiting on semaphores, etc. The P-machine For hardware implementations of the JVM (see
was used in the popular UCSD Pascal system for Section 11).
microcomputers (ca. 1977). A commercial hard-
ware implementation of the P-machine was made
(see Section 11). 5. Abstract machines for string processing
• Forth (1970) may be considered as a directly exe- languages
cutable language of a stack-based abstract machine:
expressionsarewritteninpostfix(reversePolishno- Astringprocessing language is a programming lan-
tation), a subroutine simply names a code address, guage that focuses on string processing rather than
etc. [77,94]. processing numeric data. String processing languages
have been around for decades in the form of com-
mand shells, programming tools, macro processors,
4. Abstract machines for object-oriented and scripting languages. This latter category has be-
programming languages come prominent as scripting language are used to
‘glue’ components together [101]. The components
Abstractmachinesforobject-orientedlanguagesare are typically written in a (systems) programming lan-
typically stack-based and have special instructions for guage, such as C, but they may be glued components
accessing the fields and methods of objects. Memory themselves.
management is often implicit (done by a garbage col- String processing languages are either implemented
lector) in these machines. by interpreting a proprietary representation of the
• Smalltalk-80 (1980) is a dynamically typed source text, or the implementation is based on some
class-based object-oriented language, implemented low level abstract machine. There are two reasons for
by compilation into a stack-based virtual machine using a proper abstract machine: improved execution
code. The bytecode has instructions for stack ma- speed and better portability. Machine independence
nipulation, for sending a message to an object (to hasbecomelessofanissueinrecentyears,becausethe
access a field or invoke a method), for return, for number of different computer architectures has fallen
jump, and so on [51] (the second edition [52] omits dramatically over time, and because C acts as a lingua
most of the material on the virtual machine). franca to virtually every platform currently in use.
• Self (1989) is a dynamically typed class-less We will discuss two prominent examples of early
object-oriented language. Self has a particularly string processing languages, where an abstract ma-
simple and elegant stack-based virtual machine chine is used mainly to achieve machine indepen-
code: every instruction has a three-bit instruction dence.
742 S. Diehl et al./Future Generation Computer Systems 16 (2000) 739–751
• Snobol4 [54] is a string processing language with • Tcl [100] is a command language designed to be
a powerful pattern matching facility. The language easily extensible with application specific, com-
has been used widely to build compilers, symbolic piled commands. The most widely know applica-
algebra packages, etc. The Snobol4 abstract ma- tion of Tcl is the Tk library for building Graphical
chine(SIL)operatesondatadescriptors,whichcon- User Interfaces. The flexibility of Tcl is achieved
tain either scalar data or references, as well as the primarily by representing all data as strings and
type of the data and some control information. The by using a simple and uniform interface to com-
data representation makes it possible to treat strings mands. For example the while construct from the
as variables, and to offer data directed dispatch of Tcl language is implemented by a C procedure,
operations, muchinthesamewayasobjectoriented taking two strings as arguments. The first string
systems offer today. The machine operates a pair of is the conditional expression and the second is the
stacks, a garbage collected heap (mark scan). The statement to be executed. The C procedure calls
instruction set is designed firstly to provide efficient the Tcl command interpreter recursively to evaluate
support for the most common operations and sec- the conditional and the statements ([100], p. 321).
ondly to ease the task of porting it [53]. The abstract machine does not have any stacks of
• ML/I [23] is a macro processor. Macro processors its own, it relies on the C implementation.
are based on a substitution model, whereas ordinary Since version 8.0 Tcl uses a bytecode interpreter
string processors treat strings as data to which oper- [74].
ations are applied. Macro processors are generally • Perl [128] is a scripting language, with an enor-
more difficult to program than ordinary string pro- mous collection of modules for a wide range of
cessors. The ML/I macro processor is implemented applications, such as building CGI scripts for Web
via the LOWL abstract machine. This machine servers. The implementation compiles Perl code
offers two stacks, three registers, non-recursive into an intermediate, tree structured representation,
sub-routines and a small set of instructions. Porta- with each instruction pointing to the next. The
bility has been the major driver for the design. abstract machine has seven stacks which are ex-
UNIX has had a profound influence on what we plicitly manipulated by the compiled instructions.
consider scripting languages today. With UNIX came There are six different data types, and over 300
the now classical tool-set comprising the shell, awk, instructions. Reference counting is used to perform
and make. As far as we know, all of these are imple- storage management [118].
mented using an internal representation close to the • Pythonisanobjectorientedscriptinglanguage[87].
source text. Descendants of these tools are now ap- Python is implemented using a stack based abstract
pearing that use abstract machines again, mainly for machine. The instructions are rather like method
speed but also for machine independence: calls, dispatching on the type of the operands found
• Awk[1]constructsaparsetreefromthesource.The on the stack. There are over 100 instructions, or-
interpreter then traverses the parse tree, interpret- ganized as segments of code, with jumps to alter
ing the nodes. Interior nodes correspond to an op- the flow of control. Python uses a reference count
erator or control flow construct; leaves are usually garbage collector.
pointers to data. Interpreter functions return cells Hugunin [63] has created an implementation of
that contain the computed results. Control flow in- JPython, which targets the Java Virtual Machine
terruptions like break, continue, and function return instead.
are handled specially by the main interpreter. The performance of the scripting languages has
• Nmake [49] is a version of the make tool for above been studied by a number authors. Kernighan
UNIX, which provides a more flexible style of de- and van Wyk [74] compare Awk, Perl, Tcl, Java,
pendency assertions. To be able to port these new Visual Basic, Limbo, C and Scheme. They show
make files to older systems, Nmake can translate that depending on the benchmark and the platform,
its input into instructions for the Make Abstract C and Java sometimes do worse than the scripting
Machine (MAM). These are easy to translate into languages. Romer et al. [110], benchmark Java, Perl
more common Makefile formats [78]. and Tcl using a cache level simulator of the MIPS
no reviews yet
Please Login to review.
