bluuebunny/crossref_metadata_2025 huggingface dataset:
An experiment in table driven code generation
Authors: Graham Susan L. , Henry Robert R. , Schulman Robert A.
Published: November 2005

We have constructed a local code generator for the VAX-11
2
using a parser-like instruction pattern matcher. The code generator replaces the second pass of the UNIX
3
Portable “Crdquo; compiler. This paper describes the design of the code generator and the special considerations imposed by the pattern matching process. We summarize the structure of the machine description grammar and its associated semantic actions, as well as the tools we developed to manipulate the large VAX description. In our experience, this approach makes the instruction selection phase of the compiler easier and faster to implement, and more likely to be correct than traditional techniques.
Register allocation & spilling via graph coloring
Authors: Chaitin G. J.
Published: November 2005

In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. Previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoe techniques used took considerable amounts of compile time. We have now discovered how to extend the graph coloring approach so that it naturally solves the spilling problem. Spill decisions are now made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. This new approach produces better object code and takes much less compile time.
Optimization of range checking
Authors: Markstein Victoria , Cocke John , Markstein Peter
Published: November 2005

An analysis is given for optimizing run-time range checks in regions of high execution frequency. These optimizations are accomplished using strength reduction, code motion and common subexpression elimination. Test programs, using the above optimizations, are used to illustrate run-time improvements.
Gprof
Authors: Graham Susan L. , Kessler Peter B. , Mckusick Marshall K.
Published: November 2005

Large complex programs are composed of many small routines that implement abstractions for the routines that call them. To be useful, an execution profiler must attribute execution time in a way that is significant for the logical structure of a program as well as for its textual decomposition. This data must then be displayed to the user in a convenient and informative way. The
gprof
profiler accounts for the running time of called routines in the running time of the routines that call them. The design and use of this profiler is described.
A facility for the downward extension of a high-level language
Authors: Turba Thomas N.
Published: November 2005

This paper presents a method whereby a high-level language can be extended to provide access to all the capabilities of the underlying hardware and operating system of a machine. In essence, it is a facility that allows a user to make special purpose extensions to a language without requiring the compiler to be modified for each extension. Extensions are specified in an assembler-like language that is used at compile time to produce executable code to be combined with compiler-generated code. This facility has been implemented in a systems-programming language and was designed to provide access to facilities not directly available in the language. The way in which the facility was implemented calls for a minimum of user-visible language changes and is well suited for generating code sequences for any language. The facility provides the extension writer access to information available in the high-level language during compilation, permits the selective generation of user-defined code sequences depending on the context in which they are being used, provides for the integration of this code with compiler-generated code, and provides for the generation of user-understandable error messages when an extension is used incorrectly.
A practical method for code generation based on exhaustive search
Authors: Krumme David W. , Ackley David H.
Published: November 2005

An original method for code generation has been developed in conjunction with the construction of a compiler for the C programming language on the DEC-10 computer. The method is comprehensive, determining evaluation order and doing register allocation and instruction selection simultaneously. It uses exhaustive search rather than heuristics, and is table-driven, with most machine-specific information isolated in the tables. Testing and evaluation have shown that the method is effective, that the search process is not too time consuming, and that the compiler is capable of producing code as good as that of other optimizing compilers.
An optimizing compiler for lexically scoped LISP
Authors: Brooks Rodney A. , Gabriel Richard P. , Steele Guy L.
Published: November 2005

We are developing an optimizing compiler for a dialect of the LISP language. The current target architecture is the S-I, a multiprocessing supercomputer designed at Lawrence Livermore National Laboratory. While LISP is usually thought of as a language primarily for symbolic processing and list manipulation, this compiler is also intended to compete with the S-1 PASCAL and FORTRAN compilers for quality of compiled numerical code. The S-1 is designed for extremely high-speed signal processing as well as for symbolic computation; it provides primitive operations on vectors of floating-point and complex numbers. The LISP compiler is designed to exploit the architecture heavily.

The compiler is structurally and conceptually similar to the BLISS-11 compiler and the compilers produced by PQCC. In particular, the TNBIND technique has been borrowed and extended.
An efficient separate compilation strategy for very large programs
Authors: Rudmik Andres , Moore Barbara G.
Published: November 2005

This paper describes the design of a compiling system that supports the efficient compilation of very large programs. The system consists of front ends for different languages, a common program database to store the intermediate code, and various back ends, optimizers, debuggers and other development tools. The compiling system achieves efficiency of use by minimizing the number of system components that must be invoked when a small change is made in a program.

A new separate compilation strategy is presented that is both easy and natural to use and does not require language extensions for its use. The database provides the necessary contextual information to support separate compilation and to facilitate complete compile-time checking. Also, the use of this database affords a unique opportunity to reduce substantially the cost of recompilation and to support an efficient source patching facility.
The design of an integrated support software system
Authors: Avakian Arra , Haradhvala Sam , Knobe Bruce
Published: November 2005

This paper describes some of the interesting features of a large integrated support software system. The system was built to support the development, on an IBM 370, of an extremely large Pascal program to be run on a network of Intel 8086 microprocessors. The Pascal program was composed of over 1500 separately compiled components containing over 1,000,000 lines of source code. About 200 technical people were involved in this activity. In a project of this magnitude, integration issues are of overriding importance. There must be all the type checking and managerial control associated with standard Pascal programs, but the Pascal solution of compiling the whole application as one unit is clearly unacceptable. Various pieces must be separately compiled.
A single-pass syntax-directed front end for Ada
Authors: Baker T. P.
Published: November 2005

This paper describes the front-end processor of an Ada compiler that is under development at Florida State University. The compiler is coded in Pascal, to execute on a CDC Cyber system, and is presently targeted to the Z8000 microprocessor architecture. Owing at least in part to the peculiar origins and changing goals of this project, the front end processor is rather unlike those of the other Ada compilers of which we know. Perhaps its most distinctive feature is that it operates in one pass.
Syntax-directed editing of general data structures
Authors: Fraser Christopher W.
Published: November 2005

Program editors help users create syntactically correct programs. Though such editors normally edit parse trees, applying similar techniques to other tree structures that need editing helps both users and implementors. This paper describes an editor that accepts a grammar describing a hierarchical data structure and allows the user to enter and edit arbitrary trees having this structure. It displays the pros and cons of this approach using instances of this editor that edit formatted documents, simple line drawings, and stick figures for trees.
The design of a language-directed editor for block-structured languages
Authors: Morris Joseph M. , Schwartz Mayer D.
Published: November 2005

A language-directed editor combines the text manipulation functions of a general-purpose editor with the syntax-checking functions of a compiler. It allows a user to create and modify a program in terms of its syntactic structure. The design of a user interface and an implementation for one such editor is described in language-independent terms. The design rationale is given. The implementation is outlined in terms of its major data structures.
PEN
Authors: Allen Todd , Nix Robert , Perlis Alan
Published: November 2005

Three terms in common usage in computerized text processing are
text-editing, word-processing,
and
computer controlled typesetting
. This paper deals with a fourth term,
manuscript preparation
, that has important intersections with the above three. A
computerized manuscript preparation system
is one that supports an author in the preparation of a manuscript. In what follows we deal with one such, the
PEN
system, directed towards the preparation of manuscripts containing significant mathematical notation.
PIC—a language for typesetting graphics
Authors: Kernighan Brian W.
Published: November 2005

PIC is a language for specifying pictures so that they can be typeset as an integral part of a document preparation system.

The basic objects in PIC are boxes, lines, arrows, circles, ellipses, arcs and splines, which may be placed anywhere and labeled with arbitrary text. Most of the effort in designing PIC has gone into making it possible to specify the sizes and positions of objects with minimal use of absolute coordinates.

This paper describes PIC, with primary emphasis on those aspects of the language that make it easy to use.
Prettyprinting in an interactive programming environment
Authors: Mikelsons Martin
Published: November 2005

Prettyprint algorithms designed for printing programs on paper are not appropriate in an interactive environment where the interface to the user is a CRT screen. We describe a data representation and an algorithm that allow the efficient generation of program displays from a parsed internal representation of a program. The displays show the structure of the program by consistent and automatic indentation. They show the program in varying levels of detail by replacing unimportant parts with ellipsis marks. The relative importance of program parts is determined jointly by the structure of the program and by the current focus of attention of the programmer.
On the line breaking problem in text formatting
Authors: Achugbue James O.
Published: November 2005

A basic problem in text formatting is that of determining the break points for separating a string of words into lines to obtain a formatted paragraph. When formatted text is required to be aligned with both the left and right margins, the choice of break points greatly affects the quality of the formatted document. This paper presents and discusses solutions to the line breaking problem. These include the usual line-by-line method, a dynamic programming approach, and a new algorithm which is optimal and runs almost as fast as the line-by-line method.
A redisplay algorithm
Authors: Gosling James
Published: November 2005

This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques.
EMACS the extensible, customizable self-documenting display editor
Authors: Stallman Richard M.
Published: November 2005

EMACS is a display editor which is implemented in an interpreted high level language. This allows users to extend the editor by replacing parts of it, to experiment with alternative command languages, and to share extensions which are generally useful. The ease of extension has contributed to the growth of a large set of useful features. This paper describes the organization of the EMACS system, emphasizing the way in which extensibility is achieved and used.

This report describes work done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-80-C-0505.
A model for implementing Euclid modules and type templates
Authors: Holt Richard C. , Wortman David B.
Published: November 2005

The structuring of data has become a central theme in programming language research. The ultimate utility of data structuring techniques such as clustering and type parameterization mechanisms will, however be determined in large part by our ability to provide understandable and efficient implementations.

This paper presents an implementation model for the data clustering and type parameterization facilities in Euclid. This model provides a basis for understanding the compile-time and run-time mechanisms necessary to support these features. It is an extension of the implementation model that has traditionally been used for Algol-like languages. Another implementation model (for CLU) has been described in [Atkinson, et.al., 1978].
Program checking
Authors: Williams Graeme
Published: November 2005

In languages such as Pascal, the programmer can arrange to have the compiler check such things as the range of the value of a variable only by defining a new type or sub-type. I have investigated how more powerful checking facilities might be provided if they were divorced from the type machinery, and also if the necessary language constructs were designed independent of what any particular compiler would check at compile-time.

The first part of the project is the language design. An important goal is that the programmer can have checked as little or as much as he cares, and that it is not necessary for the programmer to specify complete input and output specifications for the program. My work falls short of program verification not only because I wanted to be able to check a program quickly, but also because I was unwilling to force the programmer to specify the program in that much detail. Current program verification systems, such as that of Constable [Constable and Johnson, 1978] seem to require that the programmer write the program twice: once as a program and again as a proof.
Dynamic allocation of space for attribute instances in multi-pass evaluators of attribute grammars
Authors: Räihä Kari-Jouko
Published: November 2005

Attribute grammars [14] have proved useful as the basis of input languages for compiler-compilers. Many algorithms have evolved which can be used to automatically produce an evaluator for a given attribute grammar. The task of an evaluator is to compute the values of the attribute instances attached to a parse tree. From the compiler point of view, the evaluator takes care of the semantic analysis and in some cases also the code generation of the compiler. An overview of various evaluation algorithms is given in [6]. A bibliography can be found in [21].
Semantic charts
Authors: Cordy James R. , Holt Richard C. , Wortman David B.
Published: November 2005

This paper describes a technique for implementing the part of a compiler that processes the semantics of a programming language. It presents a concise, easy to understand notation for describing this semantic processing. The notation utilizes
semantic charts
which are similar to the separable transition diagrams [Conway63, Barnard75] that are used to define the syntax of programming languages. The charts describe semantic processing in terms of a set of operations that manipulate a small number of special-purpose data structures. They form a variable-free programming language, which accesses data via a set of operations organized into mechanisms to manage the associated data structure. These mechanisms can be modelled (and thus formalized) using abstract data types.
A code generator generator language
Authors: Donegan Michael K. , Noonan Robert E. , Feyock Stefan
Published: November 2005

Code generation has withstood attempts at automation for some time. This paper describes a non-procedural, problem-oriented language for expressing a code generator. The basis for the language is the description of the target machine as a finite-state automaton. An example code generator for a subset of HAL/S to Intel 8080 machine language is given.
Automatic storage optimization
Authors: Fabri Janet
Published: November 2005

Most studies of optimization techniques for higher level languages have focused on improving execution time of generated programs, often at the expense of increased storage. When storage optimization has been addressed, it is usually in conjunction with time optimization, such as in instruction-reducing code transformations. In the Bliss Compiler (WJWHG75), a storage-optimizing compiler, transformations that reduce register temporary storage are also performed, but automatic overlay of program variables is not addressed.

The rising popularity of mini-computers and micro-processors suggests that the time has come to examine the problem of automatic storage optimization in its totality. Because lack of space has always been a problem in the small systems environment, the proliferation of small machines implies the growing importance of the problem. Although the decreasing cost of memory may mitigate this trend, a variant of Murphy's Law ensures that program size will always increase faster than the available storage. In other words, programmers always write programs that don't fit, and, as time goes on, more of them will be doing it.
Implementation of a portable Fortran 77 compiler using modern tools
Authors: Feldman Stuart I.
Published: November 2005

I have recently written a portable compiler [1] for the Fortran 77 language [2]. It attacks an old language with new tools: the parser is generated automatically from an LALR(1) grammar, the program is produced by code generators designed for another language. These tools proved very valuable, but they are based on theory and experience one or two decades fresher than that underlying Fortran, so they really do not fit this application. The following discusses the approach taken, the ways in which the tools had to be bent to do the job, the properties of Fortran that seem to cause the most trouble, and the costs of writing a portable compiler. It also describes certain aspects of the approach to code generation, since others may wish to use the same tools. This paper does not describe low-level details of the implementation.

This compiler is intimately connected with the programming language C[3]. The compiler is written in C, it uses tools written in C, the input/output library uses the standard C library, and it uses the second pass of a C compiler as code generator. To a much smaller extent, this compiler is based on the UNIX operating system, since all of the development work was done on UNIX systems and the current version of the compiler assumes the UNIX system process structure. It would require a serious but not enormous effort to move this compiler to a different operating system; it would be impossible to move it to a non-C environment.
The CIMS PL/I compiler
Authors: Abrahams Paul W.
Published: November 2005

CIMS PL/I is an implementation of PL/I on the Control Data 6600 computer. The most challenging aspect of implementing PL/I is dealing with the sheer size and complexity of the language; since a PL/I compiler is an inherently large object, building one is a good way to test the limits of ideas on compiler construction and programming methodology. Version 1 of CIMS PL/I has been in active use since 1973 and includes roughly 70% of the full language, but is limited by some severe design flaws. Version 2 is now under development; the parser and the declaration processor are in excellent working order, but the later passes are still being worked on. In this paper I shall describe Version 2 as though it already existed in full. Version 2 is intended to implement full ANSI Standard PL/I [1], and the passes that have been completed accept the full language. Both versions are themselves written almost entirely in PL/I, and have been developed using boot-strapping methods.
On implementing separate compilation in block-structured languages
Authors: LeBlanc Richard J. , Fischer Charles N.
Published: November 2005

Perhaps the single most important paradigm of modern programming language design is block structure. Block-structured languages are characterized by nested definitional units (ALGOL blocks, PASCAL procedures, Euclid modules) having rather specialized scoping rules. In particular, access to entities defined in containing units is allowed (although sometimes with restrictions) while access to entities defined within a unit from outside it is severely restricted or totally forbidden.

This method of programming language structuring supports a top-down program development methodology: the body of a definition unit can be developed (or modified) without affecting other units (since its internal details are “hidden” from the outside). Such units (most notably procedures) become the natural units of program development and modification.
Efficient computation of LALR(1) look-ahead sets
Authors: DeRemer Frank , Pennello Thomas J.
Published: November 2005

We define two relations that capture the essential structure of the problem of computing LALR(1) look-ahead sets, and present an efficient algorithm to compute the sets in time linear in the size of the relations. In particular, for a PASCAL grammar, our algorithm performs less than 20% of the set unions performed by a popular-compiler (YACC).
Machine-independent register allocation
Authors: Sites Richard L.
Published: November 2005

The context of this paper is a machine-independent Pascal optimizer that transforms an intermediate stack-machine pseudo-code program into a generally smaller and faster pseudo-code program. The emphasis of this current paper is on the approach taken for mapping registers and storage, using an abstract but practical definition of the target machine's storage hierarchy. A companion paper [7] describes the overall optimizer project. After starting on this project, additional input became available from a Fortran-to-Pcode compiler written at Stanford [2]. Our storage mapping design is sufficiently robust that the addition of Fortran EQUIVALENCE and COMMON statements required no changes.

Our particular allocation algorithm is not unique or original, but the abstract description of the storage hierarchy, and its inclusion of practical considerations we feel to be an original contribution. The description framework has so far stood the test of describing the storage hierarchy of many commercially-available machines without needing to be extended or embellished. We hope that this is a good predictor for the future.
Abstractions, instantiations, and proofs of marking algorithms
Authors: Yelowitz Lawrence , Duncan Arthur G.
Published: November 2005

A detailed look is taken at the problem of factoring program proofs into a proof of the underlying algorithm, followed by a proof of correct implementation of abstract variables at the concrete level. We do this considering four different concrete “marking” algorithms and formulating a single abstract algorithm and set of abstract specifications that can be instantiated to each of the four concrete cases. An intermediate assertion, as well as sufficient conditions for correct initialization, invariance, and correctness at termination are given at the abstract level. Proofs at the concrete level are then given by exhibiting appropriate mapping functions (from the concrete state vector to the abstract variables), and showing that the sufficient conditions are true. Proofs of termination are given by instantiating “termination schemas”.
The automatic synthesis of recursive programs
Authors: Manna Zohar , Waldinger Richard
Published: November 2005

We describe a deductive technique for the automatic construction of recursive programs to meet given input-output specifications. These specifications express what conditions the output of the desired program is expected to satisfy. The deductive technique involves transforming the specifications by a collection of rules, summoned by pattern-directed function invocation. Some of these transformation rules express the semantics of the subject domain; others represent more general programming techniques. The rules that introduce conditional expressions and recursive calls into the program are discussed in some detail.

The deductive techniques described are embedded in a running system called SYNSYS. This system accepts specifications expressed in high-level descriptive language and attempts to transform them into a corresponding LISP program. The transformation rules are expressed in the QLISP programming language. The synthesis of two programs performed by the system are presented.

This research was supported in part by the Advanced Research Projects Agency of the Department of Defense under Contract MDA903-76-C-0206, by the National Science Foundation under Grant DCR72-03737 A01, by the Office of Naval Research under Contracts N00014-76-C-0687 and N00014-75-C-0816; and by a grant from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.

The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of Stanford University, Stanford Research Institute, or the U.S. Government.
The incremental garbage collection of processes
Authors: Baker Henry C. , Hewitt Carl
Published: November 2005

This paper investigates some problems associated with an argument evaluation order that we call “future” order, which is different from both call-by-name and call-by-value, In call-by-future, each formal parameter of a function is bound to a separate process (called a “future”) dedicated to the evaluation of the corresponding argument. This mechanism allows the fully parallel evaluation of arguments to a function, and has been shown to augment the expressive power of a language.

We discuss an approach to a problem that arises in this context: futures which were thought to be relevant when they were created become irrelevant through being ignored in the body of the expression where they were bound. The problem of irrelevant processes also appears in multiprocessing problem-solving systems which start several processors working on the same problem but with different methods, and return with the solution which finishes first. This
parallel method
strategy has the drawback that the processes which are investigating the losing methods must be identified, stopped, and re-assigned to more useful tasks.
Design rationale for TELOS, a PASCAL-based AI language
Authors: Travis Larry , Honda Masahiro , LeBlanc Richard , Zeigler Stephen
Published: November 2005

TELOS is a PASCAL-based AI language intended to facilitate efficient development of efficient, well-structured programs. The design emphasizes powerful data abstraction and control abstraction mechanisms rather than the provision of particular high-level constructs. Among the many capabilities of TELOS are those intended to make it especially suitable for systematic AI model building, for example, in the areas of knowledge representation, planning, and reasoning. An event facility is provided which unifies the handling of conditional interrupts (demons), process suspension, process communication and execution faults. The context-dependent TELOS data base is referenceable either associatively or directly.
Automated derivation of program control structure from natural language program descriptions
Authors: Wile David , Balzer Robert , Goldman Neil
Published: November 2005

This paper describes a system which organizes a natural language description of a program into a conventional program control structure, as a part of a larger system for converting informal natural language program specifications into running programs. Analysis of the input program fragments using a model of a human “reader” of specifications has been found to be a very successful adjunct to conventional “planning” methodologies.

Natural language descriptions of programs can frequently be characterized as “rubble”—a very loosely organized set of almost independent description fragments [Schwartz]. Such specifications are often quite robust, due to a large degree of redundancy; they are also frequently quite concise, due to reliance on the readers' innate knowledge and their knowledge of the application domain. This paper discusses a paradigm for structuring the portion of “rubble” program descriptions which maps into conventional programming language control constructs and definition facilities.
Quantifying the test effectiveness of Algol 68 programs
Authors: Hennell M. A. , Hedley D. , Woodward M. R.
Published: November 2005

In this paper we describe how a software testbed is used to determine the quality of testing of Algol 68 programs. The system monitors the execution of an Algol 68 program and obtains a run-time execution history. This history is then compared with the results of a static analysis and three levels of testing are calculated. The third level is an extension to Algol 68 of a method originally devised for analysing Fortran IV programs. The system has been used extensively in the coordination stage of the NAG Algol 68 numerical algorithms library and we quote some results obtained from an analysis of stringent tests on these library routines.
Algol 68 as an implementation language for portable interpreters
Authors: Pagan Frank G.
Published: November 2005

By making use of its advanced and highly expressive facilities, Algol 68 can be used to implement interpretive language processors with an unusual degree of conceptual clarity and machine independence. The internal representations of source programs in such a processor consist of high-level data structures which are interpreted by means of a set of readable, mutually recursive Algol 68 procedures. The technique is illustrated by applying it to the implementation of a miniature sample language. Efficiency considerations and aspects of the relevant programming methodology are discussed.
Towards a machine-independent transput section
Authors: van Vliet J. C.
Published: November 2005

If the transput section of an ALGOL-68 compiler is to be portable, it must be described in such a way that it is clear which aspects are machine-dependent, and which are not. There should be a clear set of primitives underlying the transput. In this report, a description is proposed which can really be used as an implementation model: the transput is described in pseudo-ALGOL 68, except for the underlying primitives, whose semantics are given in some kind of formalized English. The state of this model is by no means definitive, but may serve as a start for further discussion.
An attribute description of a subset of Algol 68
Authors: Simonet M.
Published: November 2005

Among the formalisms used for the definition of programming languages, context-free grammars are widely and satisfactorily used, but their power is limited. Augmented with attributes they can express context sensitive aspects of a language. In this paper a subset of Algol 68 is described by an attribute-grammar. This is done in a way which suggests that the attribute point of view may also help reading and writing W-grammars.
Implementation of a PDP11/ICL1900 cross assembler in Algol 68R
Authors: Bennett M. W.
Published: November 2005

The implementation in Algol 68R of a cross assembler for the PDP11 minicomputer to run on the ICL1900 is described. The assembler duplicates the features of the PAL11 assembler. RRE's Syntax Improving Device was used for a two pass assembly system. The cross assembler uses a tree structured symbol table, a lexical analyser to read in basic assembler items and code generation routines that use Algol 68 modes and operators to map the 8 bit bytes and 16 bit words of the mini onto the ICL1900 words. The cross assembler reproduces the error diagnostics of PAL11 with more detailed diagnostics available if required by the user. The assembler outputs binary program on paper tape for loading directly onto the mini.
ALGOL 68 and structured programming for learner-programmers
Authors: Ratcliff Bryan
Published: November 2005

A method is described of introducing to absolute beginners basic concepts of structured programming, including constructing programs by “step-wise refinement”. This is interleaved with a “top-down” description of a simple mini-subset of ALGOL 68, which is closely followed by the concepts of data structuring and procedurisation, as expressed in this language. Emphasis throughout is on the programming philosophy behind the approach controlling the teaching of ALGOL 68, rather than vice versa.
Abstract data and functors
Authors: Foster J. M. , Foster P. D.
Published: November 2005

The use of 'functors' is proposed to generalise the ideas of abstract data and representation, and it is shown that these ideas have further uses in setting up libraries of algorithms. The properties of functors are discussed.
Optimized machine-independent extended FORTRAN for minicomputer programming
Authors: Bennett-Novak Gordon
Published: November 2005

A FORTRAN compiler is being developed to aid in writing systems and application programs for minicomputers. The compiler is machine-independent in the sense that it can be made to generate code for a new machine with relatively little effort. The FORTRAN language accepted by the compiler is extended to facilitate the writing of “systems” programs. Particular emphasis is placed on optimization of the generated code for efficiency of storage utilization.
Program control via transition matrices—a novel application of micro-programming
Authors: Oliver S. Ron , Jones Nell D.
Published: November 2005

The problem of processing and interpreting character-strings in a systematic, efficiently implementable manner has given rise to a variety of decision- (or transition-) table and transition-diagram techniques. These have been used in the design and/or coding of string-oriented processors, such as lexical analysis portions of compilers. All these techniques share in common the idea of an input driven transition control.

This report describes a micro-coded implementation of a particularly rich concept—the transition matrix (TM). The micro-coded interpreter (ITM) executes the flow-of-control implicit within the structure of the TM. The TM may be coded in a natural, easy to use language (LTMØSP), and then be automatically translated into ITM-usable form by a user-level translator called TMØSP. The completed system (ITM and TMØSP) permits TM-oriented decision-making techniques to be utilized in virtually any task that can be described by means of a transition matrix.
Interpretive execution of real-time control applications
Authors: Adix Mary S. , Schutz Henrik A.
Published: November 2005

Interpretive execution has often been regarded as too slow for real-time control applications. Assembly language implementations, however, may exhaust available memory long before running out of machine cycles. For such applications, interpretation of a virtual machine language (VML) is attractive if it yields substantial memory savings at a tolerable cost in execution time. This paper discusses the design of a VML and interpreter which have been used to implement a real-time control application. Performance is evaluated relative to an assembly language version of the same problem. The assembly language version executed 4.8 times faster than the interpretive version, but required 31% more memory. Space compaction is achieved by making basic operations in the application area primatives of the VML. The interpreter simulates a computer whose machine language is the VML. In addition to conserving memory, this approach can facilitate the implementation of a high-level programming language on a variety of minicomputers.
Structuring BASIC programs for managing overlays in a small computer system
Authors: Cary Ted
Published: November 2005

In a small computer system, it is not unusual to write a BASIC program which is too large to fit into main memory. Such a program must be replaced by a collection of overlay modules together with inter-module sequencing logic. A sophisticated BASIC interpreter allows this sequencing to be done under program control. Unless carefully managed, a decomposition can produce an environment where programs exhibit undesirable characteristics. A structuring and design strategy is presented, discussed, and illustrated by a typical business application. Attention is given to program production, efficiency, reliability, maintainability, and modifiability using this strategy.
Numerical applications of minicomputers at the National Bureau of Standards
Authors: Lozier Daniel W.
Published: November 2005

At the National Bureau of Standards, minicomputers are used in a variety of applications requiring the acquisition and processing of physical data. In this paper, a general view of minicomputer use in laboratories at NBS is given. Several specific applications with current and future requirements in numerical processing are discussed. Computation on small computers is typically constrained, more severely than on large computers, by hardware limitations. These can be overcome only by mathematical software that is not required in large computer systems. The validity of computed results depends on this software as well as on the same type of mathematical software that would be used to solve the same problem on a large computer. But mathematical software of known high quality is less readily available for minicomputers. Some possible means of alleviating the software problems of minicomputers, and some steps taken in this direction at NBS, are discussed.
Proving the correctness of a flight-director program for an airborne minicomputer
Authors: Maurer W. D.
Published: November 2005

Over the past five years, our research efforts have been devoted in large part to developing techniques for proving the correctness of assembly-language and machine-language programs running on actual computers. In this paper, we report upon an effort to put this work into practice by proving the correctness of a program written for the Litton C4000 airborne computer. This includes overflow analysis, non-self-modification analysis, round-off and truncation analysis, fixed-point scaling considerations, and analysis of the sub-routine parameter and return-address conventions used in the given program. The basic method we use is the inductive assertion method of (Floyd, 1967), suitably modified and extended for application to a machine-language situation.
Development of educational software using the DEC PDP-11
Authors: Cowan D. D. , Dirksen P. H. , Graham J. W. , Welch J. W.
Published: November 2005

During the past two years, the Waterloo Foundation for the Advancement of Computing (WATFAC) and the University of Waterloo have been developing educational software in a number of projects using DEC PDP-11 mini-computers. These projects include the development of WATFOR-11 (a load-and-go FORTRAN compiler), WATBOL-11 (a load-and-go COBOL compiler), and WIDJET (a student editing and job-entry system). This paper presents a survey of these projects and discusses several problems encountered during their implementation.
ETOS - multi-lingual Time Sharing System for the PDP8
Authors: Schreier Thomas
Published: November 2005

EDUCOMP's Time-shared Operating System (ETOS) is an integrated package of hardware and software designed for maximum utility of a PDP8 computer. ETOS supports up to 16 users, with each user able to use the system as if he were operating on a stand-alone PDP8 with 64K bytes of memory.

This paper will contrast the various modes of computer operation and illustrate how the combination of batch, real-time, and interactive usage results in the optimum fulfillment of the all-important criterion of price/performance.

Emphasis is placed on the maintenance of continuous system performance. This is especially important to the educational user. In many situations, if the machine must be shut down for one type of user, the educational user is the first one to be sacrificed. Computer assisted instruction, drills, simulations, and general student motivation are somehow viewed as less important than the use of the computer to collect taxes. ETOS is EDUCOMP's solution to this misguided allocation of resources.

ETOS requires a 16K omnibus PDP8, clock, an RK8e controller with an RK05 drive, a backup peripheral for the RK05 drive, and a Time Share Control Module.
ABACUS/X an incremental compiler for minicomputer use
Authors: Fulton David L. , Thomas Richard T.
Published: November 2005

This paper describes an incremental compiler which has been developed for use on minicomputers. The language which it accepts, ABACUS/X, is described, as is overall system operation. The internal workings of the compiler are discussed, along with the methods developed to minimize the memory space problems inherent in the use of incremental compilers. Speed and space comparisons are included for some benchmark programs.
TOMAL-a high-level programming language for microprocessor process control applications
Authors: Kieburtz R. B. , Hennessy J. L.
Published: November 2005

This paper describes the multi-tasking capabilities of a new microprocessor programming language that has been designed to support process control applications. A program in TOMAL is a collection of tasks, priority ordered, and possibly having real-time response constraints and internal synchronization statements. It also supports device-independent I/O programming, by allowing the characteristics of each external device to be given in a declaration. A TOMAL source program is translated into space-optimized, absolute code for a target microprocessor. The object program runs under the control of a compact, application-tailored Task Control Monitor that is also generated by the compiler. The paper discusses design philosophy and several important requirements of an implementation to achieve multi-tasking capabilities.
Adapting large systems to small machines
Authors: Stuart Thomas
Published: November 2005

An evaluation of software available on mini-computers and its adequacy was made. It led to extension of a systems implementation language to two minicomputers. The language LITTLE was chosen for its machine independence and efficiency. Techniques for code generation and storage allocation are recounted with a special emphasis on producing compact code.
Corporate integration through systems software
Authors: McKeeman William M.
Published: November 2005

A software development system is proposed. It is to be used by a manufacturer of a product that contains a minicomputer, and where the minicomputer may have to be programmed differently for each customer. The programming effort yields (1) software tools on a powerful central computer, (2) invariant code for the mini, and (3) mini code that can vary under customer demand. The emphasis is on managing the complexity of (3) as the number of product deliveries increases.

The techniques of cross-assembly, emulation and real-time event simulation are used to aid the development team. Superimposed on the development tools are driver programs that allow sales and maintenance people to interact with the tools. The result is both enhancement of these non-development efforts and a further reduction in the costs of development.
Using a distributed mini-computer network to automate a biochemical laboratory
Authors: Lennon William J. , Baatz Eric L. , Colussi Sandra L. , Kinnear Kenneth E.
Published: November 2005

This research considers a distributed system constructed by networking small computers as an appropriate architecture for the automation of laboratories having an integrated function. The simplicity, inherent reliability, and flexibility of such an architecture can be realized only if the laboratory as a whole and its proposed final operational characteristics are considered from the very beginning. This desire to automate an integrated laboratory forces us to address not only the normal problems associated with instrument automation but also the goal oriented behavior of the laboratory. We have clarified these requirements by extending the accepted characterization of instrument automation and also by characterizing the levels of interaction appropriate for laboratories which must attain successive levels of integration.

Because the distributed computer system is capable of supporting either integrated or independent activities and because computing power can be added incrementally as needed, the distributed system must be viewed as a design tool easily as important as those traditionally employed. We have access to the usual tools associated with software and hardware production—e.g. translators, editors, document generators—but also the facilities to utilize them simultaneously with production programs in a reliable and flexible manner.
The design of an emulator for a parallel machine language
Authors: Lesser Victor R.
Published: November 2005

A paradigm is developed for structuring a complex emulator operating in a parallel hardware environment. This paradigm is based on the view that a complex emulator is best structured as of a set of microprocesses, each performing a small independent task, that interact in a closely-coupled manner. This is in contrast to the conventional method of structuring an emulator as a set of subroutines with a sequential flow of control among them. The design of an emulator for a parallel machine language (i.e. Adam's Graph Machine Language) using the new paradigm is discussed in detail, including the dynamic execution characteristics of the emulator in a parallel hardware environment. The analysis indicates that, given an appropriate microcomputer architecture, this structuring allows an emulator for a parallel machine language to be naturally and compactly coded and to fully map parallelism at the emulated machine language level into parallelism at the hardware level. In particular, it has been shown that an emulator can be structured so as to utilize well more than sixteen identical microprocessors. In addition, the emulator uses the idea of tailoring an emulator's control structure both to the emulated machine language and dynamically to the specific program being emulated.