bluuebunny/crossref_metadata_2025_split huggingface dataset:
Zero-cost range splitting
Authors: Kurlander Steven M. , Fischer Charles N. 
Published: November 2005

This paper presents a new optimization technique that uses empty delay slots to improve code scheduling. We are able to split live ranges for free, by inserting spill code into empty delay slots. Splitting a live range can reduce interferences with other live ranges and can sometimes free registers. Live ranges no longer interfering with the split live range can sometimes make use of the extra register.
Our algorithm, as a final pass over the code, exploits empty delay slots that would remain unused if spill code was not inserted. This paper proposes a variety of optimizations that use the extra registers generated from live range splitting, including coalescing live ranges and improving code scheduling. We present an algorithm for improving code scheduling and present implementation results.
Type analysis of Prolog using type graphs
Authors: Van Hentenryck P. , Cortesi A. , Le Charlier B. 
Published: November 2005

Type analysis of Prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a few. However, these optimizations often require a sophisticated type inference system capable of inferring disjunctive and recursive types and hence expensive in computation time.
The purpose of this paper is to describe a type analysis system for Prolog based on abstract interpretation and type graphs (i.e. disjunctive rational trees) with this functionality. The system (about 15,000 lines of C) consists of the combination of a generic fixpoint algorithm, a generic pattern domain, and a type graph domain. The main contribution of the paper is to show that this approach can be engineered to be practical for medium-sized programs without sacrificing accuracy. The main technical contributions to achieve this result are (1) a novel widening operator for type graphs which appears to be accurate and effective in keeping the sizes of the graphs, and hence the computation time, reasonably small; (2) the use of the generic pattern domain to obtain a compact representation of equality constraints between subterms and to factor out sure structural information.
An implementation of a code generator specification language for table driven code generators
Authors: Bird Peter L. 
Published: November 2005

This paper discusses an implementation of Glanville's code generator generator for producing a code generator for a production Pascal compiler on an Amdahl 470.
We successfully replaced the hand written code generator of an existing compiler with one which was produced automatically from a formal specification. This paper first outlines Glanville's original scheme, then describes extensions which were necessary for generating code for a production compiler.
A practical method for syntactic error diagnosis and recovery
Authors: Burke Michael , Fisher Gerald A. 
Published: November 2005

Our goal is to develop a practical syntactic error recovery method applicable within the general framework of viable prefix parsing. Our method represents an attempt to accurately diagnose and report all syntax errors without reporting errors that are not actually present. Successful recovery depends upon accurate diagnosis of errors together with sensible “correction” or alteration of the text to put the parse back on track. The issuing of accurate and helpful diagnostics is achieved by indicating the nature of the recovery made for each error encountered. The error recovery is prior to and independent of any semantic analysis of the program. However, the method does not exclude the invocation of semantic actions while parsing or preclude the use of semantic information for error recovery.
The method assumes a framework in which an LR or LL parser, driven by the tables produced by a parser generator, maintains an input symbol buffer, state or prediction stack, and parse stack. The input symbol buffer contains part or all of the sequence of remaining input tokens, including the current token. The LR state stack is analogous to the LL prediction stack; except when restricting our attention to the LL case, prediction stack shall serve as a generic term indicating the LR state or LL prediction stack. The parse stack contains the symbols of the right hand sides that have not yet been reduced.
A graphics typesetting language
Authors: Van Wyk Christopher J. 
Published: November 2005

We present a new programming language, IDEAL, in which two-dimensional figures can be expressed. The language is intended to work with existing text-formatting systems so that text and figures can be typeset at the same time.
The building block for IDEAL programs is called a “box” it shares some features with procedures and some with records in general-purpose programming languages. A box includes a system of constraints (in this incarnation, equations in complex variables) that declares the relative positions of its significant points and requests for actions to be performed at those points.
A box is called by adding enough constraints to the system in its definition that its significant points can be solved for uniquely. A box call may also include additional actions to be performed during the call. The notions of drawing a line using a pattern and texturing a polygonal area follow directly from the mechanism for defining and calling boxes.
Users may also ask for a box to be “opaque” so that it blots out pieces of picture that it covers. Finally, two commands embody the idea of sketching several pictures on different parallel planes, then merging them into a single picture. We use these when erasing to create one part of a picture would destroy another part that we want.
We discuss good algorithms for implementing IDEAL when the constraints are expressed as a special kind of nonlinear system and the pictures are composed of straight lines and circular arcs. The language has been implemented, and was used to produce the paper.
An all(1) compiler generator
Authors: Milton D. R. , Kirchhoff L. W. , Rowland B. R. 
Published: November 2005

Aparse is a flexible and modular system for generating efficient one-pass compilers from attributed grammar specifications. The system is of particular interest in that it combines recent research in attributed parsing and error-correction into a powerful and practical tool.
It has been amply demonstrated that attributed grammars are a convenient mechanism for organizing translations ([Fan 72], [LRS 74], [Bra 76]). This is partially due to the fact that an attributed grammar is not a completely formal specification tool—it merely provides a framework for structuring a semantic and syntactic specification. A number of compiler-compilers have been written to process attributed grammars ([LB 74], [BW 78], [GRW 77]), but Aparse is unique in incorporating attribute values in the parsing function. We have found that this facility permits smaller grammars to be used, and smaller parsers to be generated. In addition, a significant degree of context-sensitivity can be reflected in what is essentially a context-free framework. Section 2 will contain a brief introduction to attributed grammars, and section 3 will sketch the theory of attributed parsing.
An intermediate language for source and target independent code optimization
Authors: Frailey Dennis J. 
Published: November 2005

This paper describes an intermediate language to be generated by a syntax analyzer and processed by a code generator. An (essentially) optional code optimization phase may be used before code generation. The language is designed to exclude source and target dependencies (these are specified in a set of auxiliary tables) and has been used to implement a general purpose code optimization module. This module has been incorporated into compilers for several source languages and has resulted in production-quality target code.
The paper focuses on the features of the language and reviews the optimizations for which it has been designed. A major benefit of this approach has been to isolate many of the characteristics which lead to code optimization opportunities. Of particular note are numerous facts which can be gathered in a target-independent manner, even though their utilization will depend on the details of the target machine.
Automatic synthesis of optimal invariant assertions
Authors: Cousot Patrick , Cousot Radhia 
Published: November 2005

The problem of discovering invariant assertions of programs is explored in light of the fixpoint approach in the static analysis of programs, Cousot [1977a], Cousot[1977b].
In section 2 we establish the lattice theoric foundations upon which the synthesis of invariant assertions is based. We study the resolution of a fixpoint system of equations by Jacobi's successive approximations method. Under continuity hypothesis we show that any chaotic iterative method converges to the optimal solution. In section 3 we study the deductive semantics of programs. We show that a system of logical forward equations can be associated with a program using the predicate transformer rules which define the semantics of elementary instructions. The resolution of this system of semantic equations by chaotic iterations leads to the optimal invariants which exactly define the semantics of this program. Therefore these optimal invariants can be used for total correctness proofs (section 4). Next we show that usually a system of inequations is used as a substitute for the system of equations. Hence the solutions to this system of inequations are approximate invariants which can only be used for proofs of partial correctness (section 5). In section 6 we show that symbolic execution of programs consists in fact in solving the semantic equations associated with this program. The construction of the symbolic execution tree corresponds to the chaotic successive approximations method. Therefore symbolic execution permits optimal invariant assertions to be discovered provided that one can pass to the limit, that is consider infinite paths in the symbolic execution tree. Induction nrinciDles can be used for that purpose. In section 7 we show how difference equations can be utilized to discover the general term of the sequence of successive approximations so that optimal invariants are obtained by a mere passage to the limit. In section 8 we show that an approximation of the optimal solution to a fixpoint system of equations can be obtained by strengthening the term of a chaotic iteration sequence. This formalizes the synthesis of approximate invariants by heuristic methods. Various examples provide a helpful intuitive support to the technical sections.
Experience in the design, implementation and use of PL-11, a programming language for the PDP-11
Authors: Russell Robert D. 
Published: November 2005

PL-11 is a programming language for the PDP-11 family of computers designed and implemented as part of the OMEGA Project at CERN (the European Organization for Nuclear Research). Its purpose is to provide an effective tool for both physicists and systems programmers to use in building real-time data acquisition systems that are on-line to high-energy physics experiments. It is a fairly typical member of the PL-class of programming languages (44) which are based on the initial design of PL360 (41) (see Table 1). Each of these languages represents a linguistic model of its specific machine architecture, thereby providing a Systems Implementation Language (SIL) that is extremely efficient on its target machine, yet is also highly effective for human programmers to use. The need for such a tool is obvious on all computer systems, but especially on minicomputers, where most applications are in fact “systems programs”. For example, in any data acquisition environment the distinction between “user” and “operating system” largely disappears—the user's prime concern is to handle time-dependent sequences of events involving the manipulation of special I/O devices through direct status checking and data streaming—all functions which are usually buried in the operating system of conventional computing systems.
This paper discusses four years of experience with PL-11, especially as this relates to the general topic of SILs on minicomputers.
At the Programming Language - Microprogramming interface
Authors: Reigel E. W. , Lawson H. W. 
Published: November 2005

Significant research has been conducted at the Programming Language-Microprogramming (PL-M) interface. The purposes of this paper are to (1) review some of this work, (2) provide some definitions and background information concerning these two disciplines, and (3) suggest potential areas for future work. The topics at the Programming Language - Microprogramming interface that have received most attention are: Programming Language implementations using Microprogramming, the development of languages for writing microprograms, and the application of Programming Language processing techniques to Microprogramming.
At the PL-M interface, we may view the digital computer system implementation as being structured into several levels
A language-oriented instruction set for the BALM language
Authors: Harrison Malcolm C. 
Published: November 2005

The availability of microprogramming has increased interest in the design of instruction sets which are oriented towards particular higher-level languages (see (1), for example). We will refer to these as language-oriented instruction sets (or LOISs). In this paper we give a formal definition of a LOIS for the extendable language BALM. This LOIS, which we call MBALM, is used as the basis of the implementation of the current version of the language, BALM4. We will also compare two implementations of the MBALM instruction set, and outline briefly our experiences with them.
The external description of BALM4 is given in detail elsewhere (2,3). Briefly, it is an extendable language with an Algol-like syntax and data-types integer, real, logical, string, pair (list), vector, identifier, procedure, and label. Type information is carried with all data-objects, and run-time type testing and conversion is done when necessary. Garbage collection and a run-time compiler are significant attributes of the system. Outlined below are some of the properties of the implementation, which was designed initially for reasons of simplicity and flexibility, but which illustrate some of the advantages of a LOIS-based system.
A general-purpose high-level language machine for minicomputers
Authors: Wade Bradford W. , Schneider Victor B. 
Published: November 2005

In the course of our investigations into the design of translator writing systems (compiler-compilers), it has been established [2] that a certain set of “semantic primitives” can adequately express the major portion of the semantics of programs written in any of the several common high-level languages (e.g., PL/I, ALGOL W). It was also observed that each of these semantic primitives, while representing frequently-used high-level language constructs, corresponds to predictable sequences of machine-language instructions in the object code of programs.
Similarly, other authors have noted that conventional computer instruction sets are less than satisfactory as target languages for high-level language programs and have offered, as a solution to this problem, hardware or firmware processors designed specifically for programs written in a particular high-level language—the machine language and the programming language are essentially identical. The best known early example of such a processor is Helmut Weber's microprogrammed implementation of the EULER language on an IBM 360/30. [5] More recently, Burroughs Corporation has produced the B1700, a computer that has a microprogrammed language processor for each of several languages, the appropriate one of which is loaded into control memory to interpret a given program. [6,7] Such processors show significant speed increases over conventional computers of comparable basic speed in executing programs written in their particular language, but are too specialized to execute other languages efficiently. Therefore we have conjectured that, by designing a computer organization which implements a set of semantic primitives similar to Lancaster's via microprogramming, one instruction per primitive (so that the work required by a DO statement, for example, is performed in the firmware rather than in the software), we can achieve speed increases approaching those of the single-language processors, while retaining the flexibility characteristic of conventional computer organizations. This paper describes those primitives which we have chosen for initial implementation, and presents some preliminary results on the speedups obtained.
Common Lisp Object System specification
Authors: Bobrow Daniel G. , DeMichiel Linda G. , Gabriel Richard P. , Keene Sonya E. , Kiczales Gregor , Moon David A. 
Published: November 2005

Introduction

The Common Lisp Object System is an object-oriented extension to Common Lisp as defined in
Common Lisp: The Language,
by Guy L. Steele Jr. It is based on generic functions, multiple inheritance, declarative method combination, and a meta-object protocol.

The first two chapters of this specification present a description of the standard Programmer Interface for the Common Lisp Object System. The first chapter contains a description of the concepts of the Common Lisp Object System, and the second contains a description of the functions and macros in the Common Lisp Object System Programmer Interface. The chapter "The Common Lisp Object System Meta-Object Protocol" describes how the Common Lisp Object System can be customized.
The fundamental objects of the Common Lisp Object System are classes, instances, generic functions, and methods.

A
class
object determines the structure and behavior of a set of other objects, which are called its
instances.
Every Common Lisp object is an
instance
of a class. The class of an object determines the set of operations that can be performed on the object.

A
generic function
is a function whose behavior depends on the classes or identities of the arguments supplied to it. A generic function object contains a set of methods, a lambda-list, a method combination type, and other information. The
methods
define the class-specific behavior and operations of the generic function; a method is said to
specialize
a generic function. When invoked, a generic function executes a subset of its methods based on the classes of its arguments.

A generic function can be used in the same ways that an ordinary function can be used in Common Lisp; in particular, a generic function can be used as an argument to
funcall
and
apply
and can be given a global or a local name.

A
method
is an object that contains a method function, a sequence of
parameter speclalizers
that specify when the given method is applicable, and a sequence of
qualifiers
that is used by the
method combination
facility to distinguish among methods. Each required formal parameter of each method has an associated parameter specializer, and the method will be invoked only on arguments that satisfy its parameter specializers.

The method combination facility controls the selection of methods, the order in which they are run, and the values that are returned by the generic function. The Common Lisp Object System offers a default method combination type and provides a facility for declaring new types of method combination.
Programming with abstract data types
Authors: Liskov Barbara , Zilles Stephen 
Published: November 2005

The motivation behind the work in very-high-level languages is to ease the programming task by providing the programmer with a language containing primitives or abstractions suitable to his problem area. The programmer is then able to spend his effort in the right place; he concentrates on solving his problem, and the resulting program will be more reliable as a result. Clearly, this is a worthwhile goal.
Unfortunately, it is very difficult for a designer to select in advance all the abstractions which the users of his language might need. If a language is to be used at all, it is likely to be used to solve problems which its designer did not envision, and for which the abstractions embedded in the language are not sufficient.
This paper presents an approach which allows the set of built-in abstractions to be augmented when the need for a new data abstraction is discovered. This approach to the handling of abstraction is an outgrowth of work on designing a language for structured programming. Relevant aspects of this language are described, and examples of the use and definitions of abstractions are given.
Structured data structures
Authors: Shneiderman Ben , Scheuermann Peter 
Published: November 2005

Much attention has been focused lately on the notions of structured programming, a crucial factor when dealing with the design of large programming Systems. Rather than viewing programming as an art and the programmer as the perpetual artist, structured programming provides a more .systematic (and in a way more restricted) approach which facilitates debugging and proving assertions about programs.
One of the ideas developed by advocates of structured programming is the top-down elaboration of program control structures by a recursive process of successive refinements [1]. No such process has been developed for dealing with data structures. The main reason for this is the improper intermixing of the semantic and implementation concepts [2] of a data structure. The failure to distinguish between these concepts is a result of the conflicting factors involved in choosing a data structure: simplicity of element access, minimization of search time, dynamics of growth or elimination of data, simplicity of restructuring and extension, efficiency of storage utilization and others.
High level domain definition in a relational date base system
Authors: McLeod Dennis J. 
Published: November 2005

A relational data base is herein defined as a collection of normalized relations (relations in first normal form) and a collection of domains. A normalized relation may be viewed as a table, wherein each row of the table corresponds to a tuple of the relation, and the entries in a given column belong to the set of values constituting the domain underlying that column. The domains of a data base have an abstract existence apart from the data base relations.
The data base also includes various types of semantic integrity rules, which specify additional properties of the data in the data base. One such type of semantic integrity rule is the domain definition. A domain definition includes the precise description of the set of values (objects) constituting the domain. In a normalized data base, all domains are sets of atomic data values. A domain definition also includes a specification of the ordering on the values in a domain, for comparability purposes. In addition, a domain definition contains a specification of the action that is to occur if an attempt is made to violate the restriction that every entry in each column of a relation must be from the underlying domain of that column.
A nonprocedural language permitting the high level expression of domain definitions is defined. Language details and examples are presented, and the syntax and informal semantics of the domain definition language are given. This approach to domain definition is analyzed in terms of its impact on other aspects of data base semantic integrity. The relationship with the data base system in general is outlined. An analysis of intradomain and interdomain comparability is included. An introduction to relevant implementation issues is also presented. Emphasis is placed on a general approach to implementation and implementation techniques, rather than on a specific system.