bluuebunny/crossref_metadata_2025 huggingface dataset:
The A-TABLE data-type for LISP systems
Authors: Cohen Shimon
Published: November 2005

This paper describes the A-TABLE Data-Type for LISP-based languages. The A-TABLE is introduced in an attempt to unify different structures such as the PASCAL-Record, SNOBOL-Table AND INTERLISP Funarg-Block.A set of functions is defined to apply A-TABLES to: (1) Creating, accessing and updating Records; (2) Managing associatively indexed tables; (3) Providing context-dependent computations in processes and coroutines; (4) Defining multivalued functions.We show how and why these functions can be efficiently implemented with respect to access, space, garbage-collection and page-faults. We compare the A-TABLE with other facilities - LIST, ARRAY, etc.It is suggested that the A-TABLE should be one of the data-types in LISP-based systems where it can fill the gap between types "LIST" and "ARRAY".
RDL
Authors: Heacox H. C.
Published: November 2005

The Requirements and Development Language (RDL) is a non-procedural language which permits the user to describe all aspects of software development, from requirements specification through maintenance. RDL statements are used, incrementally, to build an integrated data base containing all data pertinent to the project. From this data base, standard reports can be generated to analyze requirements or design specification, to track problem areas, to produce documentation, to furnish up-to-date status information, and to ensure communication and coordination among all phases of the development process. RDL was developed, and is being used, as an internal tool for Sperry Univac Software Development.This paper describes RDL by discussing the constructs available in the language, and by presenting detailed examples from the area of design specification. In addition, some examples are presented which illustrate the flexibility of the integrated data base and the power of the report-generating facilities of the RDL Processor.
Messages in typed languages
Authors: Hunt J. G.
Published: November 2005

Messages are increasingly being used for interprocess communication. The problem of introducing messages into typed languages is considered, and a solution in terms of typed message-channels is presented. Our particular treatment permits dynamic connexions, including secure linking of separately-compiled programmes, and also features nondeterminacy, thereby enabling automatic resource-scheduling without monitors. Implementation considerations are discussed, and a comparison with the work of other authors is given.
Reasoning about arrays
Authors: Reynolds John C.
Published: November 2005

The use of complete and precise assertions, developed by Floyd and Hoare, is a powerful method for avoiding programming errors. For nontrivial programs, however, such assertions become extremely tedious when written in first-order predicate calculus.In the case of array-manipulating programs, this tedium can be alleviated by several notational and conceptual devices: (1) partition diagrams, which relate intervals of subscript values; (2) pointwise extension, which reduces the need for explicit quantification; and (3) a hierarchy of useful equivalence relations among array values.The effectiveness of these ideas is illustrated by programs for binary search and for merging.
CHAMIL
Authors: Weidner Thomas G.
Published: November 2005

The design of a Pascal based microprogramming language is described. It is a Pascal dialect adapted to the task of microprogramming a highly pipelined, horizontal micro-architecture. The nature of high level microprogramming languages, data and control structures, and the effect of a microprogramming environment on language and translator development are discussed. Certain complexities of horizontal micro-architectures are outlined.
Some statistics on ALGOL 68 programs
Authors: Grune Dick
Published: November 2005

An attempt is made to assess some static and dynamic properties of ALGOL 68 programs, which are useful for optimization decisions. The results indicate that slicing and assignation are the most important candidates for optimization, and that optimization efforts need to be directed to the simple cases only.
A study on program level dependency of implemented algorithms on its potential operands
Authors: Bandyopadhyay S. K.
Published: November 2005

The concept of program level in the implementation of algorithm using any programming language gives its measure ranging between ≤1 and > 0. Program level tends towards the higher value when higher level language is used. It is argued that for general purpose computer applications no high level programming language can really achieve program level 'one'. The paper describes an analytical method of determining the value of program level when any algorithm is implemented using a set of permitted vocabulary. The study reveals that there is a maximum limit of program level which is functionally dependent on the potential operands of the algorithm. The value of maximum program level that can be obtained out of a programming language is found to be inversely related to the potential operands of the algorithm. Existence of high negative correlation coefficient between potential operands and program level obtained from the experimental data further supports the inverse relationship.
Theoretical relationships between potential operands and basic measurable properties of algorithm structure
Authors: Bandyopadhyay S. K.
Published: November 2005

The properties relating to the area of Algorithm Dynamics or Software Physics have been found to be governed by some basic equations expressed in terms of measurable software parameters of implemented algorithm. These properties, though still in the exploratory stage of development, show an acceptable coefficient of correlation in large number of computer programs when observed values of software parameters are concerned with their respective experimental values. The study describes a new set of relationships found to be functionally dependent on input/output parameters of the algorithm structure. The relationships are investigated in various computer programmes for making comparative study of calculated and observed values of the software parameters. An objective assessment of the properties is carried out in both pure and impure varsions of a trivial algorithm.
An implementation and empirical evaluation of the tasking facilities in ADA
Authors: Haridi Seif , Bauner John-Olof , Svensson Gert
Published: November 2005

An implementation of Ada's tasking facilities, on the LSI-11 microcomputer, is described.The performance and the size of the kernel are compared with those of another language having the same basic characteristics, but with a synchronization mechanism based on shared data.The execution of typical test examples shows that the time spent in the two kernels is more or less the same.
Using a high level language as a cross assembler
Authors: Rutter Paul
Published: November 2005

This paper describes how existing high level languages can be used to simplify assembling moderate size programs for new machines. A cross assembler for the Motorola 68000 has been built using these ideas.
Introduction to SQURL
Authors: Jones Douglas McLean
Published: November 2005

This paper introduces SQURL, a new programming language designed to fulfill a need for a simple, flexible alternative to languages currently available for micro-computers. SQURL is a structured language designed for general purpose applications and intended for implementation on almost any micro-computer. A compiler does exist.
Simplicity = efficiency = readability a simple infix to prefix algorithm
Authors: Shimon Cohen
Published: November 2005

The following is not the expected breakthrough in the methodology of computer programming. It is just a small contribution to this troubled topic. It proposes an improved (simple) version for infix expression evaluation. The main idea behind this algorithm is it's simplicity which surprisingly leads to a (very) flexible, efficient, readable, small (I dare say pure) program.The simple purpose of this small paper is to promote the ideal of small and simple programs.
The CWIC/36O system, a compiler for writing and implementing compilers
Authors: Book Erwin , Shorre Dewey Val , Sherman Steven J.
Published: November 2005

Cwic/360 (Compiler for Writing and Implementing Compilers) is a metacompiler system. It is composed of compilers for three special-purpose languages, each intended to permit the description of certain aspects of translation in a straightforward, natural manner. The Syntax language is used to describe the recognition of source text and the construction from it of an intermediate tree structure. The Generator language is used to describe the transformation of the tree into appropriate object language. The MOL/360 language is used to provide an interface with the machine and its operating system.This paper describes each of these languages, presents examples of their use, and discusses the philosophy underlying their design and implementation.
Toward a semiotic theory of programming languages
Authors: Laszlo Steven I.
Published: November 2005

Based on previous results in a variety of related areas, a schema is described to produce a unified semiotic theory specifically applicable to programming languages. An alternative to BNF-like descriptions is referred to, and the structure of the semantic and pragmatic components is outlined. Programming languages are treated as any other algorithmic notation, and no reference is allowed in the proposed theory to equipment, object code, compiler, or environment.
Abstract data types in Euclid
Authors: Chang Ernest , Kaden Neil E. , Elliott W. David
Published: November 2005

The programming language Euclid provides features that support abstract data types, but does not strictly speaking provide a true data abstraction mechanism. This paper assesses the data abstraction facilities that Euclid does provide, examines the two ways of instantiating Euclid modules, and discusses other features of modules that the designers of Euclid chose not to include. In particular, the paper addresses the issues of (1) enforceable separation between abstract definition and representation, (2) specifying the relationship between abstract definition and representation, (3) type parameters in modules, (4) operator extensions, and (5) scope restrictions on identifiers.
Readability and writability in Euclid
Authors: des Rivieres Jim , Spencer Henry
Published: November 2005

Neither readability nor writability of programs were major design goals of the programming language Euclid, yet both are obviously important considerations in determining how effectively the language can be used. This paper considers the influence of various Euclid features on readability and writability.
Euclid and PASCAL
Authors: Venema Ted , des Rivieres Jim
Published: November 2005

The programming language Euclid was intended for writing system programs that could be verifiable by state-of-the-art verification methods. Since verification was not an explicit goal in the design of Pascal, it is not surprising that this gave rise to differences between the two languages. The Euclid designers intended to change Pascal only where it fell short of this goal. This paper examines differences in the two languages in the light of this objective. These differences are roughly grouped under the headings verification, system programming, and user-oriented changes.
Suggestions about a specification technique
Authors: Chaudhary B. D. , Sahasrabuddhe H. V.
Published: November 2005

In this note, we suggest some modifications in a specification technique of abstract data structures. These modifications will enhance its power to specify the delayed effects, exception handling strategy and any other computational properties.
Evaluation of boolean expressions on one's complement machines
Authors: Montgomery Peter L.
Published: November 2005

An algorithm is presented which evaluates an arbitrary boolean expression in terms of a small instruction set and which often generates fewer instructions than other methods the author has seen. The algorithm tells what code to generate whenever a boolean operator, a branch test, a boolean assignment statement, or a conditional expression is encountered. One's complement arithmetic is assumed throughout.
Efficient evaluation of Boolean expressions
Authors: Sinha V. , Kumar K. Vinod
Published: November 2005

An algorithm for the generation of an optimal code applicable to a parsed Boolean expression is presented. The algorithm generates the code during parsing itself.
A unified decimal floating-point architecture for the support of high-level languages
Authors: Ris Frederic N.
Published: November 2005

This paper summarizes a proposal for a decimal floating-point arithmetic interface for the support of high-level languages, consisting both of the arithmetic operations observed by application programs and facilities to produce subroutine libraries accessible from these programs. What is not included here are the detailed motivations, examinations of alternatives, and implementation considerations which will appear in the full work.
Proposals for Fortran data structures
Authors: Smith David N.
Published: November 2005

Three proposals for extensions to the Fortran language for data structuring are made. The first is similar to the STRUCTURE statement of IBM Fortran H [1]; no processor storage allocation function is required. The second is a variation of Hoare records [2] and the third is a variation of PL/I structures [3]. These three illustrate various posibilities and are hoped to be a basis for discussion of requirements which will lead to structuring facilities in the proposed Fortran standard. [4,6,7]
Ordered types and a generalized for statement
Authors: Abramson Harvey
Published: November 2005

An ordered type is a data structure together with predecessor and successor procedures and a relation defined over pairs of elements of the ordered type. A generalized for statement which uses the procedures connected with an ordered type is introduced. This allows ordered types to be used to control statement iteration in programs.
A note on pattern matching under Quickscan in SNOBOL4
Authors: Silverston Stefan M.
Published: November 2005

Quickscan pattern-match mode in SNOBOL4 uses heuristics to determine when it is "impossible" for a pattern match to succeed. Pattern matches ruled hopeless are terminated immediately with failure. An exposition of Quickscan is given in (1). Elaborations of this appear in (2) and (3). This note is intended to set down and clarify three aspects of the Quickscan process. These involve1. the minimum-length assumptions made for each of the fundamental SNOBOL pattern elements2. an exhaustive list of the ways length failure can occur3. the treatment of the pattern element BAL under QuickscanAll assertions here are based on the results of trials run with the macro (or SIL) implementation of SNOBOL4 on an IBM 360. Examples are intended to illustrate the assertions as precisely as possible, and do not represent common or recommended programming practice.
The taming of the pointer
Authors: Dembinski Piotr , Schwartz Richard
Published: November 2005

The existence of pointers in a higher-level programming language has been considered by many as a serious, if not insurmountable, impediment to software reliability. This paper seeks to show that most of the problems created by the use of the pointer are due to an implementation level pointer definition. A new approach is proposed which treats the pointer type in a way consistent with other data types. An example is given of how formal program verification methods can be applied to programs manipulating structures created with pointers if the introduced definition is used. A discussion is given of some implications of the adopted concepts and how they are related to the question of data representation and such notions as data abstraction.
A view of coroutines
Authors: Grune Dick
Published: November 2005

The coroutine mechanism is explained as a simplified implementation of a special case in parallel processing.
Formal types and their application to dynamic arrays in PASCAL
Authors: Pokrovsky Sergei
Published: November 2005

The formal type concept is presented as a means to uniformly introduce in the PASCAL language the dynamic array facility (which may be done as a pure extention) and formal procedure [4] specifications (which would require some changes in the standard language [1]).
IF-THEN-ELSE considered harmful
Authors: Weinberg Gerald M. , Geller Dennis P. , Plum Thomas W. S.
Published: November 2005

Although the if-then-else construct for flow of control is simple in some senses, and certainly superior to unrestricted GO TO logic, the indefinite replication of this structure leads to undesireable program constructs. Other, more extensible control structures may be added to programming languages, while regulating the unrestricted use of if-then-else, in such a way as to reduce the complexity of programs.
Experience with Pascal compilers on mini-computers
Authors: Bates D. , Cailliau R.
Published: November 2005

This paper relates the history of an implementation of the language PASCAL on a minicomputer. The unnecessary difficulties encountered on the way, led the authors to reflect on the distribution of "portable" compilers in general and suggest some guidelines for the future.Their experiences described within show that it should be possible to implement a P4 Pascal system [1] on any 16-bit mini-computer in less than two man months, given an implementor already familiar with the target machine.
Arithmetic shifting considered harmful
Authors: Steele Guy L.
Published: November 2005

For more than a decade there has been great confusion over the semantics of the standard "arithmetic right shift" instruction. This confusion particularly afflicts authors of computer reference handlings and of optimizing compilers. The fact that shifting is not always equivalent to division has been rediscovered over and over again over the year, but has never been publicized.This paper quotes a large number of sources to prove the widest extent of this confusion, and then proceeds to a short discussion of the problem itself and what to do about it.
Aspen language specifications
Authors: Wilcox Thomas R.
Published: November 2005

ASPEN is a "toy" language that has been designed for use in the teaching of compiler construction and is therefore a curious amalgam of highly refined language features that manage to barely cover the full spectrum of algorithmic languages. One selection statement is made to do the work of IF-THEN-ELSE and CASE, but with certain severe restrictions on the conditions that may be written. on the other hand, iterations must be written as a primitive infinite loop with explicit conditional exits.Only floating point (REAL) arithmetic is supported, and although strings are present, their only practical use is restricted to the labeling of output. Both array and record aggregates are defined, but both are reduced to n-tuples of fixed-length words that are referenced through pointers: each word contains either a REAL value or a pointer to another n-tuple or string. All pointers are strongly typed.The user is permitted to define his own types, but no coercions between types are predefined. Type definitions are implemented in the same manner as functions and procedures with all parameter passing being done by value. The uniformity of data structuring permits efficient implementation of simple parametric types and polymorphic procedures.Using two stacks at runtime, instead of one, a degree of dynamic storage allocation is possible, but without the need for a heap and garbage collection. The "dangling reference" problem is not avoided, however. Finally, an encapsulation mechanism that allows controlled permeation of names through a program is provided to support data abstraction and information hiding, although separate compilation is not supported.
Object structure in the Emerald system
Authors: Black Andrew , Hutchinson Norman , Jul Eric , Levy Henry
Published: November 2005

Emerald is an object-based language for the construction of distributed applications. The principal features of Emerald include a uniform object model appropriate for programming both private local objects and shared remote objects, and a type system that permits multiple user-defined and compiler-defined implementations. Emerald objects are fully mobile and can move from node to node within the network, even during an invocation. This paper discusses the structure, programming, and implementation of Emerald objects, and Emerald's use of abstract types.
QUICKTALK: a Smalltalk-80 dialect for defining primitive methods
Authors: Ballard Mark B. , Maier David , Wirfs-Brock Allen
Published: November 2005

QUICKTALK is a dialect of Smalltalk-80 that can be compiled directly into native machine code, instead of virtual machine bytecodes. The dialect includes “hints” on the class of method arguments, instance variables, and class variables. We designed the dialect to describe primitive Smalltalk methods. QUICKTALK achieves improved performance over bytecodes by eliminating the interpreter loop on bytecode execution, by reducing the number of message send/returns via binding some target methods at compilation, and by eliminating redundant class checking. We identify changes to the Smalltalk-80 system and compiler to support the dialect, and give performance measurements.
Intermedia: The architecture and construction of an object-oriented hypemedia system and applications framework
Authors: Meyrowitz Norman
Published: November 2005

This article presents a case study of the development of the Intermedia system, a large, object-oriented hypermedia system and associated applications development framework providing sophisticated document linkages. First it presents the educational and technological objectives underlying the project. Subsequent sections capture the process of developing the Intermedia product and detail its architecture and construction, concentrating on the areas in which object-oriented technology has had a significant role. Finally, the successes and failures of the development approach are examined, and several areas of standardization and research that would enhance the process are proposed.
Building a timeline editor from prefab parts: the architecture of an object-oriented application
Authors: Garrett L. Nancy , Smith Karen E.
Published: November 2005

This article describes InterVal, a software tool that allows authors to create dynamic timelines. It is one tool in Intermedia, a framework developed at Brown University's institute for Research in Information and Scholarship (IRIS) that allows professors and students to create linked multimedia documents and encourages exploration, connectivity, and visualization of ideas. The system was written using an object-oriented extension to C, MacApp, and a set of underlying building blocks, or functional groups of objects. This paper describes InterVal and discusses the architecture of the InterVal application, focusing on the design of the object-oriented architecture and on the use of appropriate building blocks. Concluding sections evaluate object-oriented programming and outline future work
.
Using prototypical objects to implement shared behavior in object-oriented systems
Authors: Lieberman Henry
Published: November 2005

A traditional philosophical controversy between representing general concepts as abstract
sets
or
classes
and representing concepts as concrete
prototypes
is reflected in a controversy between two mechanisms for sharing behavior between objects in object oriented programming languages.
Inheritance
splits the object world into
classes
, which encode behavior shared among a group of
instances
, which represent individual members of these sets. The class/instance distinction is not needed if the alternative of using
prototypes
is adopted. A prototype represents the
default
behavior for a concept, and new objects can re-use part of the knowledge stored in the prototype by saying how the new object differs from the prototype. The prototype approach seems to hold some advantages for representing default knowledge, and incrementally and dynamically modifying concepts.
Delegation
is the mechanism for implementing this in object oriented languages. After checking its idiosyncratic behavior, an object can forward a message to prototypes to invoke more general knowledge. Because class objects must be created before their instances can be used, and behavior can only be associated with classes, inheritance fixes the communication patterns between objects at instance creation time. Because any object can be used as a prototype, and any messages can be forwarded at any time, delegation is the more flexible and general of the two techniques.
A concurrent object-oriented knowledge representation language Orient84/K: its features and implementation
Authors: Ishikawa Yutaka , Tokoro Mario
Published: November 2005

Orient84/K is an object oriented concurrent programming language for describing knowledge systems. In Orient84/K, an object is composed of the
behavior part
, the
knowledge-base part
, and the
monitor part
, in order to provide
object-oriented, logic-based, demon-oriented
, and
concurrent-programming
paradigms in the object framework. Every object is capable of concurrent execution in Orient84/K.

In this paper, after describing an overview of Orient84/K, we will describe implementation issues in a concurrent object oriented language. Then, a new method for an efficient implementation of concurrent objects is proposed and formally described. A new virtual machine for Orient84/K is designed using this method, and some preliminary results of evaluation are presented.
Objects in concurrent logic programming languages
Authors: Kahn Kenneth , Tribble Eric Dean , Miller Mark S. , Bobrow Daniel G.
Published: November 2005

Concurrent Prolog supports object-oriented programming with a clean semantics and additional programming constructs such as incomplete messages, unification, direct broadcasting, and concurrency synchronization [Shapiro 1983a]. While it provides excellent computational support, we claim it does not provide good notation for expressing the abstractions of object-oriented programming. We describe a preprocessor that remedies this problem. The resulting language, Vulcan, is then used as a behicle for exploring new variants of object-oriented programming which become possible in this framework.
Object-oriented concurrent programming in ABCL/1
Authors: Yonezawa Akinori , Briot Jean-Pierre , Shibayama Etsuya
Published: November 2005

An object-oriented computation model is presented which is designed for modelling and describing a wide variety of concurrent systems. In this model, three types of message passing are incorporated. An overview of a programming language called ABCL/1, whose semantics faithfully reflects this computation model, is also presented. Using ABCL/1, a simple scheme of distributed problem solving is illustrated. Furthermore, we discuss the reply destination mechanism and its applications. A distributed “same fringe” algorithm is presented as an illustration of both the reply destination mechanism and the future type message passing which is one of the three message passing types in our computation model.
An object-oriented approach to a large scientific application
Authors: Jacky Jonathan , Kalet Ira
Published: November 2005

We used an object-oriented design to build a large scientific application: simulation of radiation therapy treatments for cancer. We provide features familiar in the graphics workstation world, including graphic editing of the proposed treatment, multiple views of the treatment in different windows, and computations which proceed concurrently as the input data are being edited. To make our system practical for the typical clinic we used a popular minicomputer and the vendor's operating system and compiler. This paper describes how we implemented objects, inheritance, message passing, windows, and concurrency in (almost) standard Pascal on a VAX under VMS.
Language support for changeable large real time systems
Authors: Jacobson Ivar
Published: November 2005

A set of concepts for modeling large real time systems is discussed informally. The concepts support the design of centralized as well as distributed systems. They are object oriented in that they correspond to entities of the 'real world', and they are 'change oriented' in that they support not only the first development stage of a system but also its continuous change and evolution. In particularly, the concepts give a promising solution to 'on the fly' changes of existing, active entities.
Object-oriented spreadsheets: the analytic spreadsheet package
Authors: Piersol Kurt W.
Published: November 2005

The ASP package, a spreadsheet implemented in Smalltalk-80, is discussed. A description of the unique data manipulation features of ASP is given. A discussion of how these features arise from the Smalltalk-80 environment is included, with emphasis on features not common to all object oriented languages.
Development of an object-oriented DBMS
Authors: Maier David , Stein Jacob , Otis Allen , Purdy Alan
Published: November 2005

We describe the results of developing the GemStone object-oriented database server, which supports a model of objects similar to that of Smalltalk-80. We begin with a summary of the goals and requirements for the system: an extensible data model that captures behavioral semantics, no artificial bounds on the number or size of database objects, database amenities (concurrency, transactions, recovery, associative access, authorization) and an interactive development environment. Object-oriented languages, Smalltalk in particular, answer some of these requirements. We discuss satisfying the remaining requirements in an object oriented context, and report briefly on the status of the development efforts. This paper is directed at an audience familiar with object-oriented languages and their implementation, but perhaps unacquainted with the difficulties and techniques of database system development. It updates the original report on the project [CM], and expands upon a more recent article [MDP].
Mimic: a fast system/370 simulator
Authors: May C.
Published: November 2005

Software simulation of one computer on another tends to be slow. Traditional simulators typically execute about 100 instructions on the host machine per instruction simulated. Newer simulators reduce the expansion factor to about 10, by saving and reusing translations of individual instructions. This paper describes an experimental simulator which takes the progression one step further, translating groups of instructions as a unit. This approach, combined with flow analysis, reduces the expansion factor to about 4. The new simulator simulates System/370 on a RISC, namely the IBM RT PC.
The Illinois functional programming interpreter
Authors: Robison A. D.
Published: November 2005

The Illinois Functional Programming (IFP) language is a modified version of Backus' FP(1). IFP has the same side-effect free combinator style of Backus FP, while introducing an ALGOL-like syntax and structure. While IFP superficially appears to be an inefficient language to execute, its simplicity makes it quick to interpret. Functions are always monadic and there are no variable or parameter names. Furthermore, combinator-style languages allow common housekeeping operations to be condensed into efficient machine-language primitives.By reference-counting, the interpreter can often convert call-by-value to destructive call-by-reference while preserving referential transparency. The interpreter has an expression cache which can improve the asymptotic time of some combinatorial functions. IFP function definitions are stored as UNIX files, so much of UNIX's functionality is immediately borrowed into the IFP environment, e.g.
ls, more
, and
grep
.Benchmarks indicate that IFP is an order of magnitude faster than Berkeley FP[2], and is competitive with interpreted von-Neumann languages such as BASIC. The interpreter can parallel process on shared-memory multiprocessors, e.g. the Encore Multimax. IFP currently runs on machines as varied as the IBM PC, VAX, and CRAY-XMP.
DI: an interactive debugging interpreter for applicative languages
Authors: Skedzielewski S. K. , Yates R. K. , Oldehoeft R. R.
Published: November 2005

The DI interpreter is both a debugger and interpreter of SISAL programs. Its use as a program interpreter is only a small part of its role; it is designed to be a tool for studying compilation techniques for applicative languages. DI interprets dataflow graphs expressed in the IF1 and IF2 languages, and is heavily instrumented to report the activity of dynamic storage activity, reference counting, copying and updating of structured data values. It also aids the SISAL language evaluation by providing an interim execution vehicle for SISAL programs. DI provides determinate, sequential interpretation of graph nodes for sequential and parallel operations in a canonical order. As a debugging aid, DI allows tracing, breakpointing, and interactive display of program data values. DI handles creation of SISAL and IF1 error values for each data type and propagates them according to a well-defined algebra. We have begun to implement IF1 optimizers and have measured the improvements with DI.
A recursive interpreter for the Icon programming language
Authors: O'Bagy J. , Griswold R. E.
Published: November 2005

The implementation of the Icon programming language is more interesting and difficult than the implementation of many other programming languages because an expression in Icon can generate a sequence of results. The implementation therefore must support control backtracking in expression evaluation. There also are several novel control structures related to generators. Because expression evaluation is limited lexically, a full coroutine mechanism is not needed and expression evaluation can be handled in a stack-like fashion.The implementation of Icon consists of a virtual machine with a stack-based architecture and an interpreter that executes the virtual machine instructions. There have been several different interpreters for Icon's virtual machine. This paper describes a new approach in which the interpreter is called recursively whenever the context for expression evaluation changes. This recursive interpreter has the advantage of being conceptually clear and flexible without sacrificing efficiency.
Two-level hybrid interpreter/native code execution for combined space-time program efficiency
Authors: Pittman T.
Published: November 2005

A two-level programming model permits the applications programmer to write programs that benefit both from the code density of interpreted virtual machines and from the speed of native code execution. A well-defined boundary between the native code and the virtual machine facilitates the development of translators to be used at both levels.
Incremental incrementally compacting garbage collection
Authors: Lang B. , Dupont F.
Published: November 2005

A mixed-strategy garbage collection algorithm is presented, which combines mark-and-sweep and copy collection. The intent is to benefit from the compacting and linearizing properties of copy collection without losing computational use of half the memory. The stop-and-collect version of the algorithm is a simple and cheap technique to fight memory fragmentation. The collection strategy may be dynamically adapted to minimize the cost of collection, according to the amount of memory actually accessed by the computing process. The parallel version of the algorithm is to our knowledge the only parallel compacting collector for varisized cells, that leaves most (more than half) of the memory available for the computing process.
Detecting conflicts between structure accesses
Authors: Larus J. R. , Hilfinger P. N.
Published: November 2005

Two references to a record structure conflict if they access the same field and at least one modifies the location. Because structures can be connected by pointers, deciding if two statements conflict requires knowledge of the possible aliases for the locations that they access.

This paper describes a dataflow computation that produces a conservative description of the aliases visible at any point in a program. The data structure that records aliases is an alias graph. It also labels instances of structures so that the objects referenced at different points in a program can be compared. This paper shows how alias graphs can be used to detect potential conflicts.
Interprocedural slicing using dependence graphs
Authors: Horwitz S. , Reps T. , Binkley D.
Published: November 2005

A slice of a program with respect to a program point
p
and variable
x
consists of all statements of the program that might affect the value of
x
at point
p
. This paper concerns the problem of interprocedural slicing — generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a
system dependence graph
, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation.

The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data-dependence edges that represent
transitive
dependencies due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.
Minimizing register usage penalty at procedure calls
Authors: Chow F. C.
Published: November 2005

Inter-procedural register allocation can minimize the register usage penalty at procedure calls by reducing the saving and restoring of registers at procedure boundaries. A one-pass inter-procedural register allocation scheme based on processing the procedures in a depth-first traversal of the call graph is presented. This scheme can be overlaid on top of intra-procedural register allocation via a simple extension to the priority-based coloring algorithm. Using two different usage conventions for the registers, the scheme can distribute register saves/restores throughout the call graph even in the presence of recursion, indirect calls or separate compilation. A natural and efficient way to pass parameters emerges from this scheme. A separate technique uses data flow analysis to optimize the placement of the save/restore code for registers within individual procedures. The techniques described have been implemented in a production compiler suite. Measurements of the effects of these techniques on a set of practical programs are presented and the results analysed.
Design and implementation of the UW Illustrated compiler
Authors: Andrews K. , Henry R. R. , Yamamoto W. K.
Published: November 2005

We have implemented an illustrated compiler for a simple block structured language. The compiler graphically displays its control and data structures, and so gives its viewers an intuitive understanding of compiler organization and operation. The illustrations were planned by hand and display information naturally and concisely.
A mechanism for efficient debugging of parallel programs
Authors: Miller B. P. , Choi Jong-Deok
Published: November 2005

This paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (SMMP). We describe the use of
flowback analysis
to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. We introduce a mechanism called
incremental tracing
that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. We extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co-operating processes.
Grammatical abstraction and incremental syntax analysis in a language-based editor
Authors: Ballance R. A. , Butcher J. , Graham S. L.
Published: November 2005

Processors for programming languages and other formal languages typically use a concrete syntax to describe the user's view of a program and an abstract syntax to represent language structures internally. Grammatical abstraction is defined as a relationship between two context-free grammars. It formalizes the notion of one syntax being “more abstract” than another. Two variants of abstraction are presented. Weak grammatical abstraction supports (i) the construction during LR parsing of an internal representation that is closely related to the abstract syntax and (ii) incremental LR parsing using that internal representation as its base. Strong grammatical abstraction tightens the correspondence so that top-down construction of incrementally-parsable internal representations is possible. These results arise from an investigation into language-based editing systems, but apply to any program that transforms a linguistic object from a representation in its concrete syntax to a representation in its abstract syntax or vice versa.
Software pipelining: an effective scheduling technique for VLIW machines
Authors: Lam M.
Published: November 2005

This paper shows that software pipelining is an effective and viable scheduling technique for VLIW processors. In software pipelining, iterations of a loop in the source program are continuously initiated at constant intervals, before the preceding iterations complete. The advantage of software pipelining is that optimal performance can be achieved with compact object code.

This paper extends previous results of software pipelining in two ways: First, this paper shows that by using an improved algorithm, near-optimal performance can be obtained without specialized hardware. Second, we propose a
hierarchical reduction
scheme whereby entire control constructs are reduced to an object similar to an operation in a basic block. With this scheme, all innermost loops, including those containing conditional statements, can be software pipelined. It also diminishes the start-up cost of loops with small number of iterations. Hierarchical reduction complements the software pipelining technique, permitting a consistent performance improvement be obtained.

The techniques proposed have been validated by an implementation of a compiler for Warp, a systolic array consisting of 10 VLIW processors. This compiler has been used for developing a large number of applications in the areas of image, signal and scientific processing.
The American side of the development of Algol
Authors: Perlis Alan J.
Published: November 2005

History is contextual. The Algol* development was a product, perhaps a miraculous product, of its time. All developments proceed, almost implacably, from the primitive to the rococco, e.g. from Algol58 through Algol60 to Algol68 with an appearance of a large number of offshoots (e.g., JOVIAL, MAD, NELIAC and Euler), extensions (FORMULA ALGOL and LCC), virile offspring (PASCAL), etc., occurring enroute. The earliest developments appear clean, surprising us in the new views they reveal. One frets over why the vision that prompted the beginning weakened during the course of future developments. Perhaps it is inevitable that, as unexpected complexity is uncovered, smoothness, equal value if you will, in solutions cannot be maintained. Trivia cannot be identified easily, special cases overwhelm the search for general patterns, custom and habit move performance into the realm of objective concept, experience warps both intuition and reason, fear of instability burdens insight with caution. The elegance of Algol's offspring is a tribute to the grace and power of the original. Algol, a second generation language, was more graceful than any of its predecessors, for example FORTRAN, MATHMATIC and IT.
The European side of the last phase of the development of ALGOL 60
Authors: Naur Peter
Published: November 2005

In preparing this account of some of the developments leading to ALGOL 60 I have primarily sought to present such relevant information that is readily available to myself, but not otherwise accessible or well known. In addition I have tried to answer the specific questions formulated by the organizers of the Conference on the History of Programming Languages. The notes fall in three freely intermixed groups: those that relate to existing documents, those that reflect my own reasoning as a participant in the development, and those that try to answer the organizers' questions. Where the proper support has been lacking I have left open holes in the presentation. Otherwise I have tried to be specific, giving names, dates, and reasons, as far as I have them available.

While this manner of presentation seems to me the best way to support more penetrating historical research into the period, it is also bound to give rise to controversy. First, it is openly one-sided, in the manner that any autobiography is. Further, by being specific the presentation will offer sensitive points of attack to those who see the same development from a different angle and with different eyes. When these circumstances are combined with real events that involved differences of opinion and interest, strong reactions are bound to be provoked. This emerged clearly in the remarks from the reviewers of the draft of the paper.
ACM SIGPLAN history of programming languages conference BASIC language summary
Authors: Lewis Ted G.
Published: November 2005

B
eginner's
A
ll-purpose
S
ymbolic
I
nstruction
C
ode or
BASIC
was originally developed by T. E. Kurtz and J. G. Kemeny at Dartmouth College in 1963-1964. The original version consisted of 14 statement constructs. BASIC was one of several languages operating in a general purpose time-sharing system also developed at Dartmouth. The simple user commands, numbering about 8 or 10, have since become associated with the BASIC language.

A BASIC program is created via the NEW command, listed by the LIST command, edited by a DELETE command, executed by the RUN command, and saved by the SAVE command. Previously saved programs are retrieved from their file by entering OLD and the desired program name.
BASIC
Authors: Kurtz Thomas E.
Published: November 2005

Dartmouth College is a small university dating from 1769, and dedicated “... for the education and instruction of Youth of the Indian Tribes in this Land in reading, writing and all parts of learning... and also of English Youth and any others.” (Wheelock 1769.) The undergraduate student body (now nearly 4000) outnumbers all graduate students by more than 5 to 1, and majors predominantly in the Social Sciences and the Humanities (over 75 percent).

In 1940 a milestone event, not well remembered until recently (Loveday 1977), took place at Dartmouth. Dr. George Stibitz of the Bell Telephone Laboratories demonstrated publicly for the first time, at the annual meeting of the American Mathematical Society, the remote use of a computer over a communications line. The computer was a relay calculator designed to carry out arithmetic on complex numbers. The terminal was a Model 26 Teletype.