A graph theory oriented extension to Algol

A language is presented for the representation of graphs and the formulation of related problems. For a language for graphs to be complete, it should have all computing facilities of symbolic languages, like ALGOL or FORTRAN, and, in addition, it should be able to easily handle graph-like data structures. As a consequence, our language is defined as a set of phrases to be added to another existing language, in particular to ALGOL. This set of phrases constitutes thegraphic language (G.L.), while the complete language for graphs handling is thegraphic extended ALGOL (G.E.A.). The phrases of the graphic language have to be translated into pieces of ALGOL programs by a pre-compiler. The graphic language has been defined by an operators precedence grammar, written in Backus normal form, so that a syntax directed compiler can be used.     

Implementing ALGOL 68 predicates

Predicates are used in the Revised ALGOL 68 Report to indicate blind alleys and to reduce the number of rules in the Report. They may also be used by the compiler writer to implement some of the non-context-free aspects of the language. This paper shows how the predicates can be transformed in a relatively straightforward way into ALGOL 68 procedures to form part of an analyser for the revised language.     

SATHE: Some aspects of an ALGOL implementation

The development of a compiler for a dialect of ALGOL 60 is described. The emphasis is on the strategies used in the detection and smooth recovery from errors in the input text. These strategies are independent of both the language implemented and the implementation language. The user's view is such that he sees an ALGOL machine: the user is addressed in a language he is familiar with, using notions from the programming language and his particular program only.     

Error-checking compilers and portability

One of the major purposes of a high-level language is to provide a large measure of machine-Independence in the specification of algorithms. Definitions of languages such as FORTRAN IV and ALGOL 60 encourage compatibility between various implementations. Language specifications are inadequate in that they normally underdefine a language. In particular, the specifications do not normally demand a response to a language violation. The freedom normally given to an implementor to decide the degree and nature of error detection and response hinders portability and may lead to-unexpected results when moving code from one machine to another or even when changing implementations on the same machine. To support the contention that languages should specify a response to violations, an analysis of four FORTRAN IV implementations and a FORTRAN IV verifier was conducted. The study showed that different implementations often lead to different results for the same illegal program. A study of programmers also revealed that they cannot be relied upon to avoid language violations without compiler aids.     

Babel and SOAP applications of extensible compilers

This paper describes a method of writing compilers which can easily be extended or altered. Two applications of the method are described; the first is a conventional programming language called Babel and the second is a program called SOAP which documents ALGOL 60 programs. Two important features have made extensions practicable; the compiler has a modular construction and was initially written in ALGOL 60.     

XDSPCORE: a compiler-based configurable digital signal processor

XDSPCORE is a digital signal processor (DSP) architecture that enables time- and space-efficient execution of typical digital signal applications written in high-level languages. Our evaluation shows that the corresponding compiler can use all the DSP features as efficiently as a programmer coding in assembly language.     

Formal compiler construction in a logical framework

The task of designing and implementing a compiler can be a difficult and error-prone process. In this paper, we present a new approach based on the use of higher-order abstract syntax and term rewriting in a logical framework. All program transformations, from parsing to code generation, are cleanly isolated and specified as term rewrites. This has several advantages. The correctness of the compiler depends solely on a small set of rewrite rules that are written in the language of formal mathematics. In addition, the logical framework guarantees the preservation of scoping, and it automates many frequently-occurring tasks including substitution and rewriting strategies. As we show, compiler development in a logical framework can be easier than in a general-purpose language like ML, in part because of automation, and also because the framework provides extensive support for examination, validation, and debugging of the compiler transformations. The paper is organized around a case study, using the MetaPRL logical framework to compile an ML-like language to Intel x86 assembly. We also present a scoped formalization of x86 assembly in which all registers are immutable.     

A simple nucleus written in modula-2: A case study

A simple nucleus for a single-processor computer is considered. The entire nucleus program is written in the high-level programming language Modula-2¹ without assembly coding. The concepts of the nucleus and some simple applications are described. A complete listing of the nucleus is included. We conclude that programming of a nucleus in an appropriate high-level language is simpler than in an assembly language. The resulting nucleus has a comparable performance with other nuclei written in assembly code.     

Deriving a compiler from an operational semantics written in VDL

This paper addresses the issue of compiler correctness. The approach taken is to systematically construct a correct compiler for a language from a formal semantic definition of the language. For this purpose, an operational semantics of a language is chosen as the basis for the approach. That is, the compiler for a language is derived from an interpreter of the language. The derivation process uses the notion of mixed computation proposed by Ershov. Briefly stated, one begins interpreting and when a primitive state changing instruction is about to be executed, the instruction is emitted as code instead. The correctness of all compilers produced by the method is guaranteed by proving the derivation rules correct. This proof is a one-time task for each specification language. The specification language studied in this paper is the Vienna Definition Language (VDL). The object code generated by the compiler is in an intermediate language close to an assembly language. Therefore, the translation from the intermediate language into the assembly language should be straightforward.     

The design and implementation of a code generation tool

A practical approach to the development of a high-quality, re-usable code generator is described in this paper. This code generator produces code for the Prime 64V mode architecture, but the methodology used is generally applicable to the construction of compilers for most architectures. The code generator accepts a tree-structured intermediate form, linearized and represented as a file of integers. This intermediate form uses high-level operators, minimizing work by compiler front-ends that use it and providing a number of advantages in the code generation process. The output of the code generator is assembly language. This tool was found to considerably extend the capabilities of students in a graduate compiler class and has been used in the construction of Pascal and C compilers.     

A mechanically verified language implementation

This paper briefly describes a programming language, its implementation on a microprocessor via a compiler and link-assembler, and the mechanically checked proof of the correctness of the implementation. The programming language, called Piton, is a high-level assembly language designed for verified applications and as the target language for high-level language compilers. It provides executeonly programs, recursive subroutine call and return, stack based parameter passing, local variables, global variables and arrays, a user-visible stack for intermediate results, and seven abstract data types including integers, data addresses, program addresses and subroutine names. Piton is formally specified by an interpreter written for it in the computational logic of Boyer and Moore. Piton has been implemented on the FM8502, a general purpose microprocessor whose gate-level design has been mechanically proved to implement its machine code interpreter. The FM8502 implementation of Piton is via a function in the Boyer-Moore logic which maps a Piton initial state into an FM8502 binary core image. The compiler and link-assembler are both defined as functions in the logic. The implementation requires approximately 36K bytes and 1400 lines of prettyprinted source code in the Pure Lisp-like syntax of the logic. The implementation has been mechanically proved correct. In particular, if a Piton state can be run to completion without error, then the final values of all the global data structures can be ascertained from an inspection of an FM8502 core image obtained by running the core image produced by the compiler and link-assembler. Thus, verified Piton programs running on FM8502 can be thought of as having been verified down to the gate level.This work was supported in part by the Defense Advanced Research Projects Agency under DARPA Orders 6082 and 9151, contract MDA904-87-C-H009.     

A demonstrably correct compiler

As critical applications grow in size and complexity, high level languages, rather than better-trusted assembly languages, will be used in their development. This adds potential for extra errors to creep in, especially in the now necessary compiler. To avoid these new errors, it is necessary to have a formal specification of the high level language, and a formal development of its compiler. We outline what we believe is a practical route for achieving a demonstrably correct compiler, and describe a prototype compiler we have built by this route for a small, but non-trivial, language.     

Experience from the standardization of the SIMULA programming language

SIMULA is a high-level language comparable in power to PL/I or ALGOL 68. SIMULA compilers exist for eight different computer series. SIMULA is standardized by a committee mainly consisting of one representative for each implementation. This has given good compatibility between the implementations and the efficient handling of standards problems. The fact that the SIMULA language is defined in such a way that there are no undefined constructs in the language has also helped compatibility and standardization.     

A structured approach to language design

This report is an attempt at systematizing a set of ground rules for high-level language design. It recommends the use of a hierarchical semantic model schema. HGL, in a step by step, top-down approach imposing more and more structure on the language components as the design becomes solidified. The approach is demonstrated by showing the stepwise design of the high-level language, GRAAL. The method recommended is divided into three major phases. The first is an informal one. The second is encoding the language components into a very high-level model. This high-level design allows a redesign of language components before they have been specified at too detailed a level. The third phase is to design the compiler in HGL using the final language design.     

Adam: An Ada-based language for multiprocessing

Adam is a high-level language for parallel processing. It is intended for programming resource scheduling applications, in particular supervisory packages for run-time scheduling of multiprocessing systems. An important design goal was to provide support for implementation of Ada and its run-time environment. Adam has been used to implement Ada task supervision and also as a high-level target language for compilation of Ada tasking. Adam provides facilities corresponding to the Ada sequential constructs (including subprograms, packages, exceptions, generics). In addition, it provides specialized module constructs for implementation of packages that may be shared between parallel processes, and new predefined types for scheduling. The parallel processing constructs of Adam are more primitive than Ada tasking. Strong restrictions are enforced on the ways in which parallel processes can interact. A compiler for Adam has been implemented in MacLisp on DEC PDP-10 computers. Runtime support packages in Adam for scheduling (on a single CPU) and I/O are also provided. The compiler contains a library manipulation facility for separate compilation. The Adam compiler has been used to build an Ada compiler for most of the July 1980 Ada, including task types and rendezvous constructs. This was achieved by implementing the translation of Ada tasking into Adam parallel processing as a preprocessor to the Adam compiler. This present Ada compiler, which has been operational since December 1980, uses a procedure call implementation of tasking. It can be easily modified to other implementations. Compilation of Ada tasking into a high-level target language such as Adam facilitates studying questions of correctness and efficiency of various compilation algorithms, and code optimizations specific to tasking, e.g. elimination of unnecessary threads of control. This paper gives an overview of Adam and examples of its use. Emphasis is placed on the differences from Ada. Experience using Adam to build the experimental Ada system is evaluated. Design of a run-time supervisor in Adam is discussed in detail.     

Automatic code generation for GPUs in llc

llc is a C-based language where parallelism is expressed using compiler directives. In this paper, we present a new backend of an llc compiler that produces code for GPUs. We have also implemented a software architecture that eases the development of new backends. Our design represents an intermediate layer between a high-level parallel language and different hardware architectures.     

Security types preserving compilation

Starting from the seminal work of Volpano and Smith, there has been growing evidence that type systems may be used to enforce confidentiality of programs through non-interference. However, most type systems operate on high-level languages and calculi, and “low-level languages have not received much attention in studies of secure information flow” (Sabelfeld and Myers, [Language-based information-flow security. IEEE Journal on Selected Areas in Communications 2003; 21:5–19]). Therefore, we introduce an information flow type system for a low-level language featuring jumps and calls, and show that the type system enforces termination-insensitive non-interference.Furthermore, information flow type systems for low-level languages should appropriately relate to their counterparts for high-level languages. Therefore, we introduce a compiler from a high-level imperative programming language to our low-level language, and show that the compiler preserves information flow types.     

Quick compiler construction using uniform code generators

This paper describes our experience in using a common set of code generating subroutines as the basis for compilers of ALGOL W, ALGOL 60 and subsets of PL/I and COBOL. The advantages of using a common set of primitives for implementing more than one compiler include: (1) greatly reduced effort to implement additional languages; (2) simplified maintenance of the generated compilers; (3) standardized diagnostic messages for all compilers implemented using this system; and (4) simplified documentation of the compilers.     

The Design and Implementation of a Domain-Specific Language for Network Performance Testing

CONCEPTUAL is a toolset designed specifically to help measure the performance of high-speed interconnection networks such as those used in workstation clusters and parallel computers. It centers around a high-level domain-specific language, which makes it easy for a programmer to express, measure, and report the performance of complex communication patterns. The primary challenge in implementing a compiler for such a language is that the generated code must be extremely efficient so as not to misattribute overhead costs to the messaging library. At the same time, the language itself must not sacrifice expressiveness for compiler efficiency, or there would be little point in using a high-level language for performance testing. This paper describes the CONCEPTUAL language and the CONCEPTUAL compiler's novel code-generation framework. The language provides primitives for a wide variety of idioms needed for performance testing and emphasizes a readable syntax. The core code-generation technique, based on unrolling CONCEPTUAL programs into sequences of communication events, is simple yet enables the efficient implementation of a variety of high-level constructs. The paper further explains how CONCEPTUAL implements time-bounded loops - even those that comprise blocking communication - in the absence of a time-out mechanism as this is a somewhat unique language/implementation feature.