An Optimizing Pascal Compiler

The architecture of a production optimizing compiler for Pascal is described, and the structure of the optimizer is detailed. The compiler performs both interprocedural and global optimizations, in addition to optimization of basic blocks. We have found that a high-level structured language such as Pascal provides unique opportunities for effective optimization, but that standard optimization techniques must be extended to take advantage of these opportunities. These issues are considered in our discussion of the optimization algorithms we have developed and the sequence in which we apply them.     

A portable implementation of a modular multiprocessing database programming language

This paper introduces the database programming language RAPP, which is an integration of the data type relation and relational algebraic operations with the modular multiprocessing language Pascal Plus. A portable version of the RAPP compiler has been implemented and is described.     

V-Pascal: An automatic vectorizing compiler for Pascal with no language extensions

An automatic vectorizing compiler called V-Pascal is described in detail. The compiler has been designed and implemented with a view to vectorizing Pascal source programs. Using the mechanism of vector indirect addressing, it reduces multiply nestedfor loops to equivalent single loops, which are then executed by vector mode with sufficiently long vector lengths. TheD matrix, which is an adjacency matrix giving dependences between intermediate code nodes, plays an important role in the V-Pascal compiler. It is demonstrated that, in some cases, the V-Pascal compiler yields object code that runs faster than the Fortran counterpart. This paper mainly presents the basic constituents of the Version 1 of the V-Pascal compiler. Version 2 includes higher functions such as vectorization ofwhile-do loops and recursive procedures, vectorization of character string manipulations and relational database operations (written in Pascal), and automatic parallel decomposition for multiprocessor environments.     

The costs and benefits of lazy interactive input in pascal

The programming language Pascal was designed and implemented in a non-interactive programming environment. This paper surveys proposals for incorporating interaction into Pascal, and focuses on a scheme known as ‘lazy evaluation’. It presents and compares performance measurements of two Pascal run-time systems for the same compiler; a buffered, non-interactive version, and a modification of that system to support lazy evaluation.     

Integrating library modules into Pascal programs

We present the results of our experience in introducing modularity into the programming language Pascal in order to aid the creation and use of library modules. Our system performs the symbolic linking of source language modules producing a single Pascal text ready for compilation; performing the link phase before compilation anticipates interface consistency checks, and suggests a possible improvement of program development systems. Our extension is implemented in a preprocessor which ensures a complete compatibility with any standard Pascal compiler. In this paper we examine the main features of some high-level programming languages which support modularization and data abstraction and some experiences in introducing modularity into Pascal; on this basis we describe our choice in detail. The design and implementation details are discussed and some examples are presented.     

Experience with the universal intermediate language janus

Janus is a symbolic language intended for use as an intermediate language in the transportation of software. Since its initial design four years ago, it has been used to implement a portable Pascal compiler, in the design of an Algol 68 compiler, and to realize a portable package of mathematical routines. These experiences, together with a critical re-evaluation of the design criteria, have led to some modification of the specifications of Janus and an increased confidence in the viability of the approach. They have also indicated some problems yet to be solved. This paper reviews the significant lessons which we have learned, and quotes some results which support our confidence.     

Generalized Query-By-Rule: a heterogeneous database query language

This paper describes the design and implementation of a high-level query language called Generalized Query-By-Rule (GQBR) which supports retrieval, insertion, deletion and update operations. This language, based on the formalism of database logic, enables the users to access each database in a distributed heterogeneous environment, without having to learn all the different data manipulation languages. The compiler has been implemented on a DEC 1090 system in Pascal.     

GRASP—A 3D graphics system for Pascal users

This paper describes a 3D graphics package ‘GRASP’ implemented in Pascal language and interfaced with the Pascal compiler developed for the DEC PDP-10 machine, by Urs Amman et al. GRASP supports storage tube and raster scan graphics terminals and pen plotters. The package is incorporated as a set of standard procedures into the enhanced Pascal compiler. The various features of the package are presented here and a comparison is made vis-a-vis the other existing 3D graphics packages. GRASP is simple to use and provides a valuable tool for the development of application programs written in Pascal and requiring a graphics capability.     

Automatic generation of self-scheduling programs

Techniques are described for the automatic generation of self-scheduling parallel programs. Both scheduling algorithms and the concurrent components of applications are expressed in a high-level concurrent language. Partitioning and data dependency information are expressed by simple control statements, which may be generated either automatically or manually. A self-scheduling compiler, implemented as a source-to-source transformation, takes application code, control statements, and scheduling routines and generates a new program that can schedule its own execution on a parallel computer. The approach has several advantages compared to previous proposals. It generates programs that are portable over a wide range of parallel computers. There is no need to embed special control structures in application programs. The use of a high-level language to express applications and scheduling algorithms facilitates the development, modification, and reuse of parallel programs     

Implementing strings in Pascal

Sale¹ has proposed that strings be realized in Pascal using the existing sequence abstraction. This short note supports this proposal and shows how strings can be efficiently implemented in standard Pascal. The implementation is done in such a way as to leave existing programs undisturbed should strings be subsequently incorporated in the language and/or compiler.     

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.     

Portable parallelizing Fortran compiler

The Portable Parallelizing Fortran Compiler (PPFC) is an additional component for the portable programming environment developed in Tel-Aviv University for scientific code. This environment supports portable and efficient programming of diverse MIMD multiprocessors, both distributed- and shared-memory. Till now this environment has consisted of two tools: the Virtual Machine for MultiProcessors (VMMP) and the Portable Parallelizing Pascal compiler (P³C). We have added the PPFC which is an automatic parallelizer compiler for the Fortran language. The compiler is fully automatic (does not require additional declarations to assist parallelization), which is characterized by loops operating on regular data structures, and produces efficient and portable code for a variety of multiprocessors from the same serial code. The parallel implementation uses the VMMP, which is a software package that provides a coherent set of services for explicitly parallel application programs running on diverse MIMD multiprocessors. VMMP is intended to simplify parallel program writing and to promote portable and efficient programming. The PPFC parallelized 12 out of the 24 Livermore Loops. It was also applied to parallelize all the 14 Fortran application programs that where parallelized by the P³C and achieved the same speed-ups and efficiencies. In most examples the PPFC achieved high speed-ups and efficiencies on all target multiprocessors. The PPFC emphasizes efficiency and code portability. Although PPFC employs a relatively simple data flow analysis, it produces efficient code for various widely used application programs.     

Implementing prototype testing tools

Testing tools are software analyzers that use information from particular executions of a program as well as information about a specification and the program text itself. Research prototypes of such tools are essential to investigate the ideas they embody. Often, hand calculation is so tedious and error-prone that an investigator cannot obtain any intuition about his or her ideas without an implementation to aid in experiments. Traditionally, such tools have been implemented in conventional high-level languages (e.g., C, Pascal), a process that takes more time than a prototype should. The technology of compiler generators and logic programming, applied to the idea of self-instrumenting programs, drastically shortens the prototype cycle. This paper describes a general method for implementing prototype tools, gives examples of several old and new testing techniques fitted into the method, and discusses the ease with which such prototypes may be changed.     

The Implementation of Run-Time Diagnostics in Pascal

This paper considers the role of run-time diagnostic checking in enforcing the rules of the Pascal programming language. Run-time diagnostic checks must be both complete (covering all language requirements) and efficient. Further, such checks should be implemented so that the cost of enforcing the correct use of a given construct is borne by users of that construct. This paper descxibes simple and efficient mechanisms currently in use with a diagnostic Pascal compiler that monitor the run-time behavior of such sensitive Pascal constructs as pointers, variant records, reference (i.e., var) parameters, and with statements. The use of these mechanisms with related constructs in other languages is considered. Language modifications that simplify run-time checking ate also noted.     

An operational semantics for Icon: Implementation of a procedural goal-directed language

The generation of compiled code for expressions in programming languages such as Icon that support goal-directed evaluation in addition to traditional control structures presents more of a challenge than generating code for traditional imperative programming languages. This paper describes a code-generation technique for translating Icon programs into a traditional high-level language. Translations into both Pascal and C are discussed. However, any language that provides function parameters and recursion is sufficient. The technique described here has been used in the implementation of an optimizing compiler for Icon.     

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.     

SuperPascal—a publication language for parallel scientific computing

Parallel computers will not become widely used until scientists and engineers adopt a common programming language for publication of parallel scientific algorithms. This paper describes the publication language SuperPascal by examples. SuperPascal extends Pascal with deterministic statements for parallel processes and synchronous message communication. The language permits unrestricted combinations of recursive procedures and parallel statements. SuperPascal omits ambiguous and insecure features of Pascal. Restrictions on the use of variables enable a single-pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables. A portable implementation of SuperPascal has been developed on a Sun workstation under Unix.     

Control Computations and the Design of Loop Control Structures

The control computation for a loop in a program is that part of the program concerned with the initialization, incrementation, and testing of the variables that determine the flow of control into, through, and out of the loop. The elements of loop control computations are idenified and their role in structuring our understanding of loops is analyzed. It is argued, through examples drawn from a Pascal compiler, that the intelligibility of a loop is closely tied to the accessibility and intelligibility of the loop control computation. It is further argued, from an analysis of all the loops in this compiler, that most loop control computations fail in a few standard patterns, mostly concerned with the sequential processing of elements of data structures. In light of these results, common loop control statements are critiqued. It appears that better loop control structures than the while, repeat-until, and similar statement structures are possible and desirable, and some proposals for better structures are given.