Automatic Generation of a Compiler and an Abstract Machine for Action Notation

Stephan Diehl, 1995

We present a system, that generates a compiler and abstract machine from a Natural Semantics specification of a programming language. First an overview of the system and the transformations involved are given. Then we apply the system to a specification of Actress Action Notation. As an example we trace the transformations of rules for an action combinator. The resulting compiler and abstract machine can be used as a basis for a compiler generator based on Action Semantics. Finally we discuss future and related work.

A Prolog Positive Supercompiler

Stephan Diehl, 1995

Supercompilation is a method for program specialization. It has been developed in the context of functional languages. First we present the basic control strategy of supercompilation in the setting of a simple programming language. Next we present a positive supercompiler for Prolog. We give the basic algorithm used in APROPOS and explain the different phases involved in supercompilation of logic programs. Then the operation and efficiency of the method is demonstrated by means of examples. Finally we compare our work to related work in supercompilation and partial evaluation.

Transformations of Evolving Algebras

Stephan Diehl, 1995

We give a precise definition of evolving algebras as nondeterministic, mathematical machines. All proofs in the paper are based on this definition. First we define constant propagation as a transformation on evolving algebras. Then we extend evolving algebras by macro definitions and define folding and unfolding transformations for macros. Next we introduce a simple transformation to flatten transition rules. Finally a pass separation transformation for evolving algebras is presented For all transformations the operational equivalence of the resulting algebras with the original algebras is proven. In the case of pass separation, we show, that the results of the computations in the original and the transformed evolving algebra are equal. Next we apply pass separation to a simple interpreter. Finally a comparison to other work is given.
A former version is available as Technischer Bericht A 02/95, FB Informatik, University Saarbruecken , available as
Postscript Version or in the FTP Directory (University of Michigan) on Evolving Alegbras as Postscript Version

An Experiment in Abstract Machine Design

Stephan Diehl, 1996

In this article we present Typed Feature Structures as an extension of Prolog and show how to come up with a compilation scheme and an abstract machine using a design methodology based on partial evaluation. First we define the transformations used by our partial evaluator. Then we present the design methodology which we will use later. Next we clarify the notion of Typed Feature Structures that underlies our work and we formally define the unification of such structures. Based on this definition we develop a unification procedure with explicit heap representation. By partially evaluating this procedure with respect to some example programs, we show how to come up with the machine instructions and translation schemes. Finally we briefly address coreferences, cyclic structures and the unification of types.

Typed Feature Structures and Prolog: A Compiler for Parallel Computers

Stephan Diehl, 1993

This thesis is concerned with the compilation of logic programming languages. The WAM is an abstract machine. The vast majority of compilers for logic programming languages produce code for this machine. In the first part of this thesis we present an OR-parallel implementation of the WAM. In the second part we use partial evaluation to derive extensions to the WAM, such that Typed Feature Structures in addition to the standard first-order terms can be compiled.

VRML++: A Language for Object-Oriented Virtual Reality Models

Stephan Diehl, 1997

We present a new object-oriented language called VRML++ which extends the Virtual Reality Modeling Language (VRML 2.0), a specification language for interactive three-dimensional scenes on the internet. The new features of VRML++ are classes and inheritance, an improved type system, and dynamic routing. As a net result we get type-safe inclusion polymorphism and dynamic binding. We argue, that these features are essentials of object-oriented programming languages. Furthermore using these new features it is possible to define abstractions of routing structures which we call connection classes. VRML++ increases reuseability, readability, and extensibility of specifications while reducing run-time errors. Finally we discuss our implementation of VRML++.

A Formal Introduction to the Compilation of Java

Stephan Diehl, 1997

The goal of this paper is to explain the JVM and how Java is translated into Byte-Code. Eventually this should lead to a more in-depth understanding of Java. Furthermore the JVM can also be used as a target machine to translate other programming languages. Our presentation of the JVM follows the technical style introduced by Wilhelm and Maurer in the book "Compiler Design", Addison-Welsey, to describe other abstract machines. We present the language concepts, the related byte-code instructions and the compilation schemes. None of the existing literature on the JVM (as of spring 1997) describes how compilation is done, but present the JVM in isolation.

Towards Lean and Open Multi-User Technologies

Stephan Diehl, 1998

The standardization of the Virtual Reality Modeling Language and its APIs paves the way for platform independant, open standards based implementations of distributed, virtual worlds. After a discussion of key requirements of those and an overview of how the underlying technology moved from proprietary to open standards, we describe our implementation which is based on CORBA, Java and VRML and comment on how open these languages are. Finally, by exploiting CORBA services as far as possible it is our goal to get a lean multi-user technology, which can be loaded over the internet.

Object-Oriented Animations with VRML++

Stephan Diehl, 1998

In this paper we show how VRML++ can be used to specify animations. VRML++ extends the Virtual Reality Modeling Language (VRML 2.0) by classes and inheritance, an improved type system, and dynamic routing. Using these new features it is possible to define abstractions of routing structures which we call connection classes. Such connection classes are a powerful tool to define generic animation class. The example discussed in detail in this paper demonstrates that VRML++ increases reuseability, readability, and extensibility of specifications while reducing run-time errors.

Bootstrapped Semantics-Directed Compiler Generation

Stephan Diehl, 1999

We introduce our natural semantics-directed generator 2BIG for compilers and abstract machines. It applies a sequence of transformations to a set of natural semantics rules including a pass separation transformation. Then we discuss how it can be used to generate a compiler and abstract machine for action notation. With the help of these components we can then generate compilers for other source languages whose semantics has been specified in Action Notation. We also briefly discuss the concept of an abstract machine language language based on the abstract machine generated for action notation.

Visualizing Principles of Abstract Machines by Generating Interactive Animations

Stephan Diehl and Thomas Kunze, 2000

In this paper we describe the design rationale of GANIMAM, a web-based system which generates interactive animations of abstract machines from specifications. Common principles of abstract machines come into play at three levels: the design of the specification language, the choice of graphical annotations to visualize higher-level abstractions and the use of the system to explore and better understand known and detect new principles.

Principles of Abstract Machines

Stephan Diehl, 2000

In this article give a brief historical overview of work on abstract machines. Then we introduce common principles of abstract machines by first presenting the programming language concept and then its implementation in form of abstract machine instructions and compilation schemes. Finally, we provide pointers for further reading.

Abstract Machines for Programming Language Implementation

Stephan Diehl, Pieter Hartel and Peter Sestoft,2000

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.

A generative methodology for the design of abstract machines

Stephan Diehl, 2000

In this paper we demonstrate how to use a semantics-directed generator to systematically design abstract machines. The main novelty of the generator is that it generates compilers and abstract machines. The generator is fully automated and its core transformations are proved correct. In this paper we propose a design methodology based on our generator and as an example we design a functional abstract machine which turns out to be very similar to the categorial abstract machine.
Stephan Diehl / diehl@cs.uni-sb.de