bluuebunny/crossref_metadata_2025 huggingface dataset:
Global context recovery
Authors: Pai Ajit B. , Kieburtz Richard B.
Published: November 2005

Methods for error recovery in parsing a deterministic, context-free language need not be derived by
ad hoc
means. When fixed, table-driven parsing algorithms are used the error recovery procedures can also make use of knowledge about the grammar for the language, derived from the parsing tables. However, at the point of detection of certain kinds of syntax errors, the knowledge of a sentential prefix already parsed, as reflected in the current state of the parsing stack, will be incorrect. Effective error recovery under such circumstances has proven to be difficult. We suggest the use of fiducial, or trustworthy symbols of a language as a key to recovery in these difficult cases. In this paper we give a characterization of such symbols in terms of properties of a grammar and give an algorithm that is capable of global context recovery under all circumstances. It has been implemented in conjunction with an LL(1) parser. We have compared it experimentally with the LR-parser recovery algorithm of Pennello and DeRemer on a test set of 126 small Pascal programs.
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.
A comparison of PASCAL intermediate languages
Authors: Nelson Philip A.
Published: November 2005

PASCAL P-code is an aid when transporting PASCAL to new machines and environments. Implementations using P-code may modify the P-code. This modification process may require some creative effort. Some of this effort may be eliminated by looking at previous work with P-code. This paper describes three versions of P-code and compares ther modifications.
Predicting the effects of optimization on a procedure body
Authors: Ball J. Eugene
Published: November 2005

Practical application of procedure integration (inline expansion) as a program optimization requires some method for estimating the effects of subsequent optimization on the integrated procedure. A technique is described for predicting the code improvement that can be expected due to constant folding and test elision when a procedure call involving constant actual parameters is integrated. The technique is based on information collected during a single data flow analysis of each procedure body, and on execution frequency statistics for the procedure. This information can then be used to estimate the cost in code size and the benefit in execution speed of integrating each call to the procedure. The algorithm uses a syntax directed analysis technique suitable for structured programming languages without gotos.
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.
Program synthesis by analogy
Authors: Ulrich John Wade , Moll Robert
Published: November 2005

By extending a given analogy, a known program which solves a given problem is converted to a program which solves a different but analogous problem. The domains of the two problems need not be the same but they must be related by an initial specified analogy. There are three features which distinguish the approach. First the analogy formation evolves gradually with the synthesis of the new program. Secondly the formation of the analogy is directed by the correctness proof of the known program. Finally the output of the synthesis process produces a correctness proof for the synthesized program.
Control requirements for the design of production system architectures
Authors: Rychener Michael D.
Published: November 2005

Programs in the artificial intelligence domain impose unusual requirements on control structures. Production systems are a control structure with promising attributes for building, generally intelligent systems with large knowledge bases. This paper presents examples to illustrate the unusual position taken by production systems on a number of control and pattern-matching issues. Examples are chosen to illustrate certain powerful features and to provide critical tests which might be used to evaluate the effectiveness of new designs.
Macaroni is better than spaghetti
Authors: Steele Guy Lewis
Published: November 2005

We present a stack implementation of multiple environments similar in principle to that of Bobrow and Wegbreit, but based on a model which provides both static and dynamic scoping. We note some of the pragmatic consequences of this choice of models; one is that no unnecessary control stack is retained for certain important constructions such as “upward funargs” and coroutines. We also discuss the correct treatment of exit functions, and the need for “entry functions” if dynamic switching of control contexts is to be consistent.
What the nature of natural language tells us about how to make natural-language-like programming languages more natural
Authors: Hobbs Jerry R.
Published: November 2005

When a student is learning an algorithm from a textbook, his first approach is frequently through an English description. This is normally easier to understand than raw code, and sometimes easier than a flow chart, in spite of the fact that programming languages are designed for algorithm specification while English is only pressed into its service. If the English is easier to understand, it is likely that it has many features that would ease programming itself. This paper investigates some of these features.
CSSA
Authors: Böhm H. P. , Fischer H. L. , Raulefs P.
Published: November 2005

CSSA (Computing System for Societies of Actors) is an experimental programming language that originated from an attempt to design a language combining various new ideas having evolved from the fields of semantics of programming languages, artificial intelligence, programming methodology, and language design in recent years: (1)
Abstraction semantics
improving denotational semantics by describing the semantics of programming language constructs uniformly in terms of
operational abstractions
[1,2]. (2) Some features of CSSA have been inspired by the
actor concept
of PLASMA [3].(3) Programming in terms of control and data abstractions. (4) Heirarchical control structures (dynamic generation and manipulation of actor nets). (5) Definable access operations and access control to shared data [4]. (6) Data driven and goal directed computation.
A knowledge-based code generator generator
Authors: Fraser Christopher W.
Published: November 2005

XGEN is a program that accepts a machine description and produces a good local code generator for an ALGOL-like language. It is organized as a production system of rules codifying previously acquired human skills for dealing with computer architecture and programming languages.
The PSI Program Model Builder - synthesis of very high-level programs
Authors: McCune Brian P.
Published: November 2005

A system called the Program Model Builder (PMB) is being designed and implemented to perform the basic operations required to synthesize and modify programs. PMB plays a central role as one of the expert modules of the PSI (ψ) program synthesis system. PMB builds a complete and consistent program model from small chunks of program specification received from other (ψ) experts. PMB must deal with the fact that these program fragments often omit details and may be incomplete, ambiguous, inconsistent, nonspecific, and arbitrarily ordered. The initial version of PMB has successfully synthesized a few program models from fragments. This work includes the evolution of a very high-level program modelling language, the identification and codification of useful very high-level programming knowledge including equivalence transformations, and the implementation of a rule-based problem solving system embodying this knowledge.
The selection of efficient implementations for a high-level language
Authors: Kant Elaine
Published: November 2005

This paper considers the problem of identifying an efficient set of implementations for the abstract constructs in a very high level program description. LIBRA is a system that prunes and expands a tree of partially implemented program descriptions, given a set of refinement rules for generating the tree. Several sets of rules group, order, and select refinements. The analysis of the cost of a program (or program part) at any level of refinement is maintained for cost comparisons between different refinements, for bottleneck identification, and for branch and bound search.
Selection of representations for data structures
Authors: Rosenschein Stanley J. , Katz Shmuel M.
Published: November 2005

The process of selecting representations for data structures is considered. The model of the selection process we suggest is centered around a
base
of known abstract data structures and their representations. The abstract data structure for which a representation is required would not necessarily be in the base, but should be a combination of base data structures.

After describing this model of selection and its motivation, two aspects of the process are examined in more detail: a) The interaction with the user is treated by defining a language for the natural description of data structure requirements and b) two main types of combinations—hierarchical and cross-product—are analyzed, clarifying the relation between representations for component data structures and a representation for the combination.
A normal form for compiler testing
Authors: Samet Hanan
Published: November 2005

A formalism is presented for obtaining a normal form to be used in representing programs for compiler testing. Examples are used to motivate the features that must be considered when developing such a formalism. It is particularly suitable for heuristically optimized code and has been successfully used in a system for proving that programs written in a subset of LISP are correctly translated to assembly language.
Program manipulation via an efficient production system
Authors: Kibler D. F. , Neighbors J. M. , Standish T. A.
Published: November 2005

Systems for program transformation have been suggested by many authors [Knuth, Wegbreit, Loveman, Balzer, Standish2, Burstall & Darlington]. Several of these authors note that such transformation systems could be used to transform lucid, high-level, but possibly inefficient program descriptions into efficient but possibly less legible underlying concrete realizations. One problem, mentioned by Loveman [Loveman] is that of chaining together many low-level simple transformations to achieve high-level goals. For example, we may wish to chain together low-level transformations such as constant propagation, performing arithmetic at transformation time, dead variable elimination, empty statement removal and the like, to achieve the high-level goal of program simplification. This paper shows one technique for organizing sequences of low-level program transformations within an interactive programming medium to achieve nearly automatic global program improvements with low search times and minimal human intervention and guidance.
Self-redefinition as a program manipulation strategy
Authors: Chatelin Philippe
Published: November 2005

This is an exploration of a constructive strategy for program improvement and synthesis. A first part recalls unfolding-folding style of manipulations initiated by BURSTALL and DARLINGTON with an application to proofs of equivalence of certain function compositions. Second part, in a more abstract way, presents three basic “forms” and their associated “transforms” constructed with this strategy in a hierarchical order ; they may serve as goals of transformations. Last part associates self-redefinition to mixed strategies for program composition: symbolic macro replacement, logarithmic speed up, resolution of formal recurrences. Each situation, where technique and method apply, is depicted on examples and open problems are evoked.
Derivatives without tears in Algol 68
Authors: Craven P. G.
Published: November 2005

Algol 68 is a very suitable language for tackling problems which lie somewhere between numerical calculation and algebraic manipulation. An algorithm is presented which evaluates a function of n variables and its n partial derivatives using at most C.m operations, where m is the number of operations required to evaluate the function and C is a constant independent of n. By altering mode declarations, an ordinary piece of program text written to evaluate the function can be made instead to generate the expression tree required for calculation of derivatives.
Description of dynamic manipulation of ALGOL68 values using a generative grammar.
Authors: Vansina C. F.
Published: November 2005

Code generation is very complex. Using ALGOL68, complexity increases due to the recursivity of the manipulated values. The set of routines manipulating values will be recursive too. Describing such a manipulating process with flow charts makes it less readable. To avoid that difficulty the description of the process will use a generative action grammar. With such a grammar recursivity is natural, so the description of a recursive process will be very readable. Moreover, such a grammar can easily be translated into a program, which will be very structured and modular. The produced code will be very structured too and that can be helpful for debugging and checking processes.
The ALGOL 68 compiler of Paris-XI University (Orsay)
Authors: Taupin Daniel
Published: November 2005

The ALGOL-68 compiler of the University of Paris-XI (Orsay) has been implemented for Univac's 1110-series, under EXEC-VIII. It can compile the “full language” (including formats, unions, flexible arrays, recursive modes, parallel computation, etc.). It consists in 8 passes and yields usual relocatable code. Minor restrictions concern equivalence recognition of crossed recursive modes, multiple precision and short modes, and scope checking.
Verification of an Algol 68 implementation
Authors: Houssais Bernard
Published: November 2005

A tool for the systematic production of test cases for a compiler is first presented. The input of the generator are formal grammars, derived from the definition of the reference language. This tool has been applied to the generation of test programs for Algol 68. For each construction which the language possesses, the syntactic structure of the corresponding test and the semantic verifications it contains are given. The test set has begun to be employed on a specific implementation. Discovered errors related to Algol 68 constructions are analysed.
Some problems concerning the automatic translation of Fortran to Algol 68
Authors: Prudom A. , Hennell M. A.
Published: November 2005

We consider briefly some of the problems encountered in the initial implementation of a system to automatically convert Fortran programs to Algol 68.
Character string pattern matching in Algol 68
Authors: Housden R. J.W. , Kotarski N.
Published: November 2005

An album of modes, operators and procedures has been implemented to provide SNOBOL-like character string pattern matching facilities for the Algol 68 programmer. Most of the primitive functions and operators of SNOBOL 4 are included in the album. This paper describes some of the facilities available and briefly outlines their implementation.
A balanced view of MUMPS
Authors: Wasserman Anthony I. , Sherertz David D.
Published: November 2005

The MUMPS programming system was designed and developed to facilitate shared conversational access to a hierarchically-organized data base on a small computer. The MUMPS language, which has recently been standardized, contains features for numeric and string operations, along with a built-in file system called globals, embedded in a multiprogrammed execution environment. This paper gives an overview of the MUMPS language and a typical MUMPS system, then evaluates MUMPS in terms of modern notions of programming languages and software development. Despite the many attractive features for the development of interactive programs, MUMPS is seen to have a number of shortcomings when evaluated in this way. Among the problem areas are weakness of control structures, the ability to write self-modifying code, the incomprehensibility of most MUMPS programs, and the lack of support given by the language to notions of abstraction and modularity.
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.
Experiences moving COBOL onto a minicomputer
Authors: Herrick Steven S.
Published: November 2005

This paper presents some subjective experience and relative qualitative results concerning the transfer of a full High Level COBOL compiler designed for the IBM S/370 to a Low-Intermediate Level on a 32-bit minicomputer. The major impacts of language feature deletion upon compiler size and complexity, as well as the effects of specific compiler and object code support via micro-coding, are discussed.
The automated generation of cross-system software for supporting micro/mini computer systems
Authors: Johnson Gearold R. , Mueller Robert A.
Published: November 2005

ASM/GEN and SIM/GEN are a software system comprised of a set of independent FORTRAN program writer modules designed to generate micro computer and small minicomputer assemblers and simulators. It is simple enough to be used by those with limited architecture and programming backgrounds, but flexible and powerful enough to generate efficient and well-structured assemblers and simulators for small micro/mini computers with sophisticated architectures and instruction sets. This paper presents a brief description of the generating system, the generated assemblers and simulators and the advantages they offer in both programming and pedagogical applications.
Minicomputer software development using a maxicomputer
Authors: Blake-Knox M. W. , Morris G. C.
Published: November 2005

This paper examines some of the problems of developing software for minicomputers (or microcomputers). Practical solutions to these problems, involving the use of maxicomputers, are described both generally and by a specific example. Areas examined include source program input and editing, compilation and assembly, loading and finally debugging. In addition, performance measurement of application software is discussed.
Experiences in the development of mathematical software for small computers
Authors: Nash J. C.
Published: November 2005

Personal experiences are reported of the difficulties and the successes associated with attempts to develop mathematical software for small computers. Examples are used to illustrate the process of algorithm selection and program “squeezing.” Some unforeseen advantages of the resulting programs are mentioned.
A Little Implementation Language
Authors: Plauger P. J.
Published: November 2005

A language is described that was implemented on a PDP-11 computer for writing system-level code for the PDP-11 family of minicomputers. The Little Implementation Language LIL offers a number of features that facilitate writing
structured
, high-level code
with no sacrifice in efficiency
over assembly language. The discussion ends with a harsh evaluation of its future usefulness.
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
Functional memory-based dynamic microprocessors for higher level languages
Authors: Rossmann George E. , Jones Louise H.
Published: November 2005

Dynamic microprocessors have been proposed as a means for providing the basic instruction sets necessary for efficient processing of a variety of higher level languages with specific hardware. Functional memory-based dynamic processors consisting of a collection of identical modules formed from writable associative arrays offer a more general solution to this problem. The basic properties of functional memory modules are discussed; and the structure of a functional memory-based microprocessor suitable for executing the SNOBOL 4 replacement statement using the data structures defined by Griswold (15) is given.
Dynamic memory management for APL-like languages
Authors: Zaks Rodnay
Published: November 2005

Microprogramming a high-level language interpreter permits execution speeds to be achieved which rival large conventional systems. However, the limited size of current control memories imposes limitations on the complexity of the resident interpreter. An extremely terse APL interpreter has been developed and implemented by the author, which requires less than 2K words of control storage on a contemporary microprocessor. Two areas in which specially significant advances have been achieved were the design of the parser and the design of the virtual memory management algorithms. The design of dynamic structures for microprogrammed memory management is presented here.
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.
Concurrent programming in Smalltalk-80
Authors: Steigerwald R. , Nelson M.
Published: November 2005

Smalltalk-80 provides only a minimal set of concurrency control mechanisms. The
fork
and
newProcess
messages can be used to indicate that two (or more) processes can run concurrently, and a
Semaphore
class is provided which can be used to achieve synchronization.These features are not enough, however, to simulate true concurrency. A process will not yield the processor until it can no longer continue. This makes it all too easy to unintentionally produce code which is dependent upon yielding the processor at some specific point.The
Delay
and
Random
classes were used to force processes to yield nondeterministically. This allowed a single processor, context switching environment to be simulated. The producer/consumer problem was used to exercise the concurrent mechanisms in this investigation.
Coupling FORTH and GKS in monitoring processes
Authors: Milanese V.
Published: November 2005

Control processes usually require short and fast programs which are often joined with simple graphic activities. In such environments FORTH is used as a system language, since it adds the properties of modularity and structuring of high level programming to those of immediateness and speed which characterize assembler programming. In order to obtain similar performances by graphic modules, it is advisable to employ a low level graphics standard and to implement it by using FORTH itself.
The flow of control notations pancode and boxcharts
Authors: Jonsson D.
Published: November 2005

The textual flow of control notation Pancode and the coresponding graphical notation Boxcharts are defined. These notations embody a new, unified control construct. The definitions given in this paper supersede those in "Pancode and Boxcharts: Structured Programming Revisited" (SIGPLAN Notices, 22, Aug. 1987, 89--98).
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.
Function inlining versus function cloning
Authors: Das Dibyendu
Published: November 2005

Function inlining is a powerful high level optimization which eliminates call cost and increases the chances of other optimizations taking effect due to the breaking down of the call boundaries. Goal-directed function cloning on the other hand strives to create specialized copies of functions to aid interprocedural optimizations. Both of these program transformations create additional code. In the traditional optimizers the problem of choosing which functions to inline is modelled as a 0--1 knapsack problem with a given budget. Function cloning is also treated likewise. However, the usual modelling considers these two as separate knapsack problems with their own respective budgets for code growth. This creates problems as independent budgets can give rise to excessive cloning or inlining and throttling opportunities for one or the other. To circumvent this problem we propose to formulate the inlining and cloning site selection problem as a unified multiple-choice knapsack problem. Multiple-choice knapsack is a well-studied problem in the domain of linear programming. In this paper we would look into a greedy algorithm to solve such knapsack problems and its application to the problem at hand.
The reflective nitrO abstract machine
Authors: Ortin Francisco , Cueva Juan Manuel , Martinez Ana Belen
Published: November 2005

Abstract machines have been widely employed in computing systems in order to obtain different aims. Compiler simplification, platform neutrality, code distribution, interoperability, and direct support for specific paradigms are examples of the benefits they offer. Although performance has been its main drawback, the use of modern techniques like adaptive (hotspot) just in time compilation has overcome this weakness. Nowadays, well-known platforms based on abstract machines such as Java™ or Microsoft .NET are commercially used.With the purpose of supporting any programming-language computational-model in heterogeneous environments, we have noticed that most abstract machines have extensibility, adaptability and heterogeneously lacks. We have designed an abstract machine that, using reflection as the main design principle, overcomes the limitations discovered. In this paper, we describe its objectives, its design, a sample implementation, and a comparison with other similar platforms.
The paradigm of open C++
Authors: Sunik Boris
Published: November 2005

Open languages are a new class of formal languages initially defined in [Sunik]. A language of this class combines the grammar of an object-oriented programming language with the universality of a natural language. This work details Open C++ based on the syntax and the conceptual system of C++.
Automatic generation of device drivers
Authors: Zhang Qing-Li , Zhu Ming-Yuan , Chen Shuo-Ying
Published: November 2005

This paper proposes a new approach to resolve the problem of device driver development: To design a domain specific language, named
DEVIL+
. With this language, users can write a complete device driver, including: interrupt handler, timer controller, logic controller and so on.
DEVIL+
allows a description to be checked for consistency and completeness. This not only improves the safety of the device driver but also uncovers bugs as early as possible in the development process.
An experimental C compiler for the Cray 2 computer
Authors: Gisselquist Richard
Published: November 2005

A language derived from C with the additional keywords 'cache' and 'vector' is described. The compiler, based on pcc, can compile itself. The post-processing optimizer exists. An example of generated code is discussed.
Forms as a language facility
Authors: Hekmatpout S. , Ince D. C.
Published: November 2005

Forms offer considerable potential in office automation systems: they are able to facilitate the changeover from manual to computer-based systems, they provide the correct interface for a wide variety of users and they reflect the logical relationship between entities in an office system. Unfortunately, very few programming languages support this concept. We describe the implementation of forms as an abstract data type in the wide-spectrum language EPROL.
A subset FORTRAN compiler for a modified Harvard architecture
Authors: Parker J. R.
Published: November 2005

The architecture of the target computer clearly has a great impact on the design of a compiler's code generator. In particular, the near complete separation of the code and data memories of the TMS32010 microprocessor creates some interesting problems.
Graph coloring register allocation for processors with multi-register operands
Authors: Nickerson Brian R.
Published: November 2005

Though graph coloring algorithms have been shown to work well when applied to register allocation problems, the technique has not been generalized for processor architectures in which some instructions refer to individual operands that are comprised of multiple registers. This paper presents a suitable generalization.
Improving register allocation for subscripted variables
Authors: Callahan David , Carr Steve , Kennedy Ken
Published: November 2005

Most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.

In this paper, we present a source-to-source transformation, called
scalar replacement
, that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. The objective is to increase the likelihood that these elements will be assigned to registers by the coloring-based register allocators found in most compilers. In addition, we present transformations to improve the overall effectiveness of scalar replacement and show how these transformations can be applied in a variety of loop nest types. Finally, we present experimental results showing that these techniques are extremely effective—capable of achieving integer factor speedups over code generated by good optimizing compilers of conventional design.
Optimizing programs over the constructive reals
Authors: Lee Vernon A. , Boehm Hans-J.
Published: November 2005

The constructive reals provide programmers with a useful mechanism for prototyping numerical programs, and for experimenting with numerical algorithms. Unfortunately, the performance of current implementations is inadequate for some potential applications. In particular, these implementations tend to be space inefficient, in that they essentially require a complete computation history to be maintained.

Some numerical analysts (cf. [3]) propose that the programmer instead be provided with variable precision
interval arithmetic
, and then be required to write code to restart a computation when the intervals become too inaccurate. Though this model is no doubt appropriate at times, it is not an adequate replacement for exact arithmetic. The correct transformation from a program operating on the constructive reals to a reasonable program using iterated interval arithmetic can be nontrivial and error prone. Here we present a technique based on
program slicing
to both automate this process and reduce the amount of reexecution. Thus the programmer is still free to use the simpler abstraction of exact real arithmetic, but we can provide a more efficient interval arithmetic based implementation. Some preliminary empirical results are presented.
Design, implementation and evaluation of the FNC-2 attribute grammar system
Authors: Jourdan Martin , Parigot Didier , Julié Catherine , Durin Olivier , Bellec Carole Le
Published: November 2005

FNC-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. Its development at INRIA started in 1986, and a first running prototype is available since early 1989. Its most important features are: efficient exhaustive and incremental visit-sequence-based evaluation of strongly (absolutely) non-circular AGs; extensive space optimizations; a specially-designed AG-description language, with provisions for true modularity; portability and versatility of the generated evaluators; complete environment for application development. This paper briefly describes the design and implementation of FNC-2 and its peripherals. Then preliminary experience with the system is reported.
A fresh look at optimizing array bound checking
Authors: Gupta Rajiv
Published: November 2005

This paper describes techniques for optimizing range checks performed to detect array bound violations. In addition to the elimination of range checks, the optimizations discussed in this paper also reduce the overhead due to range checks that cannot be eliminated by compile-time analysis. The optimizations reduce the program execution time and the object code size through elimination of redundant checks, propagation of checks out of loops, and combination of multiple checks into a single check. A minimal control flow graph (MCFG) is constructed using which the minimal amount of data flow information required for range check optimizations is computed. The range check optimizations are performed using the MCFG rather the CFG for the entire program. This allows the global range check optimizations to be performed efficiently since the MCFG is significantly smaller than the CFG. Any array bound violation that is detected by a program with all range checks included, will also be detected by the program after range check optimization and
vice versa
. Even though the above optimizations may appear to be similar to traditional code optimizations, similar reduction in the number of range checks executed can not be achieved by a traditional code optimizer. Experimental results indicate that the number of range checks performed in executing a program is greatly reduced using the above techniques.
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 programming and automatic program synthesis
Authors: Lee R. C. T. , Chang S. K.
Published: November 2005

When a computer is used to synthesize a program, there is usually too much information for it to handle. In this paper, we propose the use of stepwise refinement technique, based upon the concept of structured programming, to overcome this difficulty.
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.
PDEL-ID
Authors: Tam Wing Cheung , Karplus Walter J.
Published: November 2005

Mathematical models have been commonly used for the simulation of continuous time systems on a digital computer. In many cases, the system models involve parameters which have to be identified from observed data. The digital simulation language PDEL was extended to provide the facilities and capabilities for the identification of parameters in distributed parameter systems. The extended program is designated as PDEL-ID. The extension includes new language statements and convenient facilities for observed data input and parameter identification. The use of PDEL-ID to identify parameters in partial differential equations requires minimum amount of programming effort and little knowledge on numerical analysis and mathematical programming. The syntax and semantics of PDEL-ID are given. Major facilities and capabilities of the language are described and illustrated by an example.