bluuebunny/crossref_metadata_2025_split huggingface dataset:
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.
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.
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.
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.
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.
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.
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.
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.
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.
A study of the application of compiler techniques to the generation of micro-code
Authors: Tirrell A. Keith 
Published: November 2005

With the advent of writable control memories, the opportunity for using “firmware” to implement software systems increases dramatically. This paper presents one approach to the problem of constructing a micro-program compiler which uses a machine-independent language.
While this kind of compiler language may not generate micro-programs as efficient as those constructed by assembly language, the improvement in documentation, the ease of locating logic errors, and the possibility of using micro-programs on different computer systems make a micro-programming compiler a useful tool.
A COBOL Machine
Authors: Chevance R. J. 
Published: November 2005

This paper describes a research project undertaken by CII. This project is sponsored by the “Comité de Recherches en Informatique” contract No CRI 72-11.
In this study, we have to define a COBOL Machine and a Compilation Machine and to implement them on a medium-scale microprogrammed computer. The expected results are : performance evaluation of these machines, code compaction, COBOL compiler characteristics, operating system implications...
How to read floating point numbers accurately
Authors: Clinger William D. 
Published: November 2005

Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the
IEEE Standard for Binary Floating-Point Arithmetic
does not require the result of such a conversion to be the best approximation.

This paper presents an efficient algorithm that always finds the best approximation. The algorithm uses a few extra bits of precision to compute an IEEE-conforming approximation while testing an intermediate result to determine whether the approximation could be other than the best. If the approximation might not be the best, then the best approximation is determined by a few simple operations on multiple-precision integers, where the precision is determined by the input. When using 64 bits of precision to compute IEEE double precision results, the algorithm avoids higher-precision arithmetic over 99% of the time.
The input problem considered by this paper is the inverse of an output problem considered by Steele and White: Given a binary floating point number, print a correctly rounded decimal representation of it using the smallest number of digits that will allow the number to be read without loss of accuracy. The Steele and White algorithm assumes that the input problem is solved; an imperfect solution to the input problem, as allowed by the IEEE standard and ubiquitous in current practice, defeats the purpose of their algorithm.
Generators and the replicator control structure in the parallel environment of ALLOY
Authors: Mitsolides Thanasis , Harrison Malcolm 
Published: November 2005

The need for searching a space of solutions appears often. Many problems, such as iteration over a dynamically created domain, can be expressed most naturally using a generate-and-process style. Serial programming languages typically support solutions of these problems by providing some form of generators or backtracking.
A parallel programming language is more demanding since it needs to be able to express parallel generation and processing of elements. Failure driven computation is no longer sufficient and neither is multiple-assignment to generated values.

We describe the
replicator
control operator used in the high level parallel programming language ALLOY. The replicator control operator provides a new view of generators which deals with these problems.
Continuous system simulation languages
Authors: Fairley Richard E. 
Published: November 2005

Continuous system simulation languages are very high level programming languages which facilitate modelling and simulation of systems characterized by ordinary and partial differential equations. This paper discusses design principles and implementation techniques for continuous system simulation languages.
Following a brief introduction to very high level languages, design principles for continuous system simulation languages are presented. These principles are illustrated by examples from the Continuous System Modelling Program (CSMP) and the Partial Differential Equation Language (PDEL). A typical program in each language is included.
Batch and interactive implementation techniques for continuous system simulation languages are discussed. The classical batch implementation technique is to provide a preprocessor which translates the simulation language into an algorithmic language such as FORTRAN or PL/1. The PL/1 preprocessor is described as a useful language for the implementation of very high level language translators.
The final section of the paper presents an interactive implementation technique which interfaces a batch program processor to interactive graphics display and updating routines. In this manner, efficient simulation code is interfaced to flexible interaction routines. In addition, the batch processor is preserved intact, thus requiring only one implementation of the language for both batch and interactive applications.
An introduction to the UMTA specification language
Authors: Ziegler E. W. 
Published: November 2005

Many of the problems in the implementation and maintenance of computer programs occur during the transition from detailed functional specifications to reliable computer code (i.e., in the detailed design, coding, testing, and integration of the computer program). A study for the U.S. Air Force found that approximately 65 percent of the software effort in several large systems went into these transitional activities.(1) In other words, about twice as much software effort went into getting the computer programs to work reliably as went into determining what functions the programs should perform. This paper describes a tool to improve that ratio.
The Urban Mass Transportation Administration (UMTA) is employing a highly systematic approach to the management of computer software development. Part of this approach is the documentation and review of detailed technical specifications for computer programs. This review helps assure that the computer programs, when implemented, will do the job they are intended to do. The review takes place prior to any coding of the computer programs to reduce the amount of redesign and recoding during programming.
Data abstractions for data bases
Authors: Hammer Michael 
Published: November 2005

The concept of abstract data types has emerged from programming language research as a device to encourage and facilitate structured and modular programming [1]. It separates the abstraction of a data object from its implementation. The user of an abstract data type only concerns himself with the behavioral semantics of the type: what meaningful operations can be applied to objects of the type; the internal representation and structure of the type is unknown to him. In this way, irrelevent detail is suppressed and meaningfulness of programs enhanced.
What application does this concept have to the area of data bases? There are some obvious similarities between the principle of abstraction and the concept of data independence of data bases [2]. Data independence means that application programs that utilize a data base do not need to know either the physical or the structural organization of the data base, but can relate to it purely on a logical plane. As with data abstractions, the goal is clarity and modifiability of programs, resulting from concentration on semantics rather than representation.
Research directions in abstract data structures
Authors: Shaw Mary 
Published: November 2005

A number of interesting research problems arise from current attempts to incorporate abstraction mechanisms in programming languages. Some of them are central issues in current research projects and others are direct extensions of current work. Several problems in each of these areas are outlined below. A third section presents a series of speculations about how this work might evolve in the future.
Since this is supposed to be a session to spark research ideas, I have written brief descriptions of a number of topics and not delved very deeply into any one. Most of these problems can probably be solved in more than one way. Hence the fact that a problem is being worked on should not deter anyone from looking at it from another viewpoint.