bluuebunny/crossref_metadata_2025 huggingface dataset:
Mark-copy
Authors: Sachindran Narendran , Moss J. Eliot B.
Published: November 2005

Copying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard copying collectors require space equal to twice the size of the maximum live data for a program. We present a
mark-copy
collection algorithm (MC) that extends generational copying collection and significantly reduces the heap space required to run a program. MC reduces space overhead by 75--85% compared with standard copying garbage collectors, increasing the range of applications that can use copying garbage collection. We show that when MC is given the same amount of space as a generational copying collector, it improves total execution time of Java benchmarks significantly in tight heaps, and by 5--10% in moderate size heaps. We also compare the performance of MC with a (non-generational) mark-sweep collector and a hybrid copying/mark-sweep generational collector. We find that MC can run in heaps comparable in size to the minimum heap space required by mark-sweep. We also find that for most benchmarks MC is significantly faster than mark-sweep in small and moderate size heaps. When compared with the hybrid collector, MC improves total execution time by about 5% for some benchmarks, partly by increasing the speed of execution of the application code.
Specifying queries as relational expressions
Authors: Boyce R. F. , Chamberlin D. D. , Hammer M. M. , King W. F.
Published: November 2005

SQUARE (Specifying Queries As Relational Expressions) is a set oriented data sublanguage for expressing queries (access, modification, insertion, and deletion) to a data base consisting of a collection of time-varying relations. The language mimics how people use relations or tables to obtain information. It does not require the sophisticated mathematical machinery of the predicate calculus (bound variables, quantifiers, etc.) in order to express simple references to tables. However, the language has been shown to be complete, i.e., any query expressible in the predicate calculus is expressible in SQUARE.
PEARL
Authors: Snowdon R. A.
Published: November 2005

The PEARL system is an attempt to provide an environment for the writing of correct programs. Facilities are provided for the construction and filing of structured programs, whilst techniques have been developed for the inclusion of assertions involving abstract operations and data types. As a result, programs, possibly incomplete, can be compiled and executed, any error communication with the programmer being in terms of the appropriate level of his source program.
A finite state approach to operator classification
Authors: LaLonde Wilf R.
Published: November 2005

We consider the problem of uniquely classifying operators in expressions containing binary, prefix unary, and suffix unary operators e.g. binary + (addition), prefix unary ~ (negation), and suffix unary ! (factorial). Since the same name may be used to represent distinct operators in different classes, the problem is one of refinement. In the general case, it can be recast in a grammatical frameword whose solution requires all parse trees of an ambiguous grammar. We consider a much simpler finite state solution. More specifically, we consider an automaton based algorithm which refines the classifications of each operator to a unique class (when it exists) as a function of the allowed classifications of the neighboring operators. We do not consider the more complicated problem where operand types effect the result.
Describing software design in Ada
Authors: Booch Grady
Published: November 2005

Ada is a tool suitable for the efficient and reliable development of solutions to a large problem domain. To combat the FORTRAN mind set and exploit the full power of the language, top down functional methodo logies are insufficient, and thus an object-oriented methodology is required. This paper provides some observations on such a methodology with subsequent representation of software design in the Ada Programming Support Environment (APSE).
Problems with the Ada reference grammar
Authors: Wetherell C. S.
Published: November 2005

The Ada grammar published in the
Reference Manual
is not suitable as it stands for use with a parser generation system. The changes necessary to make it suitable and some discussion of grammar design principles are presented here. The revised grammar appears in an appendix.
Error checking, tracing, and dumping in an ALGOL 68 checkout compiler
Authors: Thomson C. M.
Published: November 2005

A case is stated for the need for error checking, tracing, and dumping. Consideration is given to the types of errors which must be checked for. Examples are given which demonstrate the need that all these errors be checked at run time in ALGOL 68. Tracing and dumping are discussed, with emphasis on those aspects of ALGOL 68 which make them difficult. Some possible solutions to these problems are offered. An outline of the facilities provided in the FLASC system is given.
Object-oriented programming with flavors
Authors: Moon David A.
Published: November 2005

This paper describes Symbolics' newly redesigned object-oriented programming system,
Flavors. Flavors
encourages program modularity, eases the development of large, complex programs, and provides high efficiency at run time.
Flavors
is integrated into Lisp and the Symbolics program development environment. This paper describes the philosophy and some of the major characteristics of Symbolics'
Flavors
and shows how the above goals are addressed. Full details of
Flavors
are left to the programmers' manual,
Reference Guide to Symbolics Common Lisp. (5)
CommonLoops: merging Lisp and object-oriented programming
Authors: Bobrow Daniel G. , Kahn Kenneth , Kiczales Gregor , Masinter Larry , Stefik Mark , Zdybel Frank
Published: November 2005

CommonLoops blends object-oriented programming smoothly and tightly with the procedure-oriented design of Lisp. Functions and methods are combined in a more general abstraction. Message passing is invoked via normal Lisp function call. Methods are viewed as partial descriptions of procedures. Lisp data types are integrated with object classes. With these integrations, it is easy to incrementally move a program between the procedure and object-oriented styles.

One of the most important properties of CommonLoops is its extensive use of meta-objects. We discuss three kinds of meta-objects: objects for classes, objects for methods, and objects for discriminators. We argue that these meta-objects make practical both efficient implementation and experimentation with new ideas for object-oriented programming.

CommonLoops' small kernel is powerful enough to implement the major object-oriented systems in use today.
Oaklisp: an object-oriented scheme with first class types
Authors: Lang Kevin J. , Pearlmutter Barak A.
Published: November 2005

The Scheme papers demonstrated that lisp could be made simpler and more expressive by elevating functions to the level of first class objects. Oaklisp shows that a message based language can derive similar benefits from having first class types.
An object-oriented operating system interface
Authors: Ewing Juanita J.
Published: November 2005

This paper discusses an object-oriented interface from the Smalltalk-80™ programming environment to a Unix-like operating system. This interface imposes an object-oriented paradigm on operating system facilities. We discuss some of the higher order abstractions that were created to make use of these facilities, and discuss difficulties we encountered implementing this interface. Several examples of cooperating Smalltalk and operating system processes are presented.
Mach and Matchmaker: kernel and language support for object-oriented distributed systems
Authors: Jones Michael B. , Rashid Richard F.
Published: November 2005

Mach, a multiprocessor operating system kernel providing capability-based interprocess communication, and Matchmaker, a language for specifying and automating the generation of multi-lingual interprocess communication interfaces, are presented. Their usage together providing a heterogeneous, distributed, object-oriented programming environment is described. Performance and usage statistics are presented. Comparisons are made between the Mach/Matchmaker environment and other related systems. Possible future directions are examined.
Virtual memory on a narrow machine for an object-oriented language
Authors: Kaehler Ted
Published: November 2005

LOOM (Large Object-Oriented Memory) is a virtual memory implemented in software that supports the Smalltalk-80(™) programming language and environment on the Xerox Dorado computer. LOOM provides 8 billion bytes of secondary memory address space and is specifically designed to run on computers with a narrow word size (16-bit wide words). All storage is viewed as objects that contain fields. Objects may have an average size as small as 10 fields. LOOM swaps objects between primary and secondary memory, and addresses each of the two memories with a different sized object pointer. When objects are cached in primary memory, they are known only by their short pointers. On a narrow word size machine, the narrow object pointers in primary memory allow a program such as the Smalltalk-80 interpreter to enjoy a substantial speed advantage. Interesting design problems and solutions arise from the mapping between the two address spaces and the temporary nature of an object's short address. The paper explains why the unusual design choices in LOOM were made, and provides an interesting example of the process of designing an integrated virtual memory and storage management system.
SOAR: Smalltalk without bytecodes
Authors: Samples A. Dain , Ungar David , Hilfinger Paul
Published: November 2005

We have implemented Smalltalk-80 on an instruction-level simulator for a RISC microcomputer called SOAR. Measurements suggest that even a conventional computer can provide high performance for Smalltalk-80 by abandoning the 'Smalltalk Virtual Machine' in favor of compiling Smalltalk directly to SOAR machine code, linearizing the activation records on the machine stack, eliminating the object table, and replacing reference counting with a new technique called Generation Scavenging. In order to implement these techniques, we had to find new ways of hashing objects, accessing often-used objects, invoking blocks, referencing activation records, managing activation record stacks, and converting the virtual machine images.
Hurricane: an optimizing compiler for Smalltalk
Authors: Atkinson Robert G.
Published: November 2005

We discuss a recent attempt at providing a more efficient compilation system for the Smalltalk-80™ language than currently exists. The approach is unique in that it attempts to work within the existing semantics of the language. A type declaration and inference mechanism is developed in order to make the problem tractable. Details concerning the compiler implemented to date are given, as well as preliminary speed tests of compiled object code.
Virtual copies: at the boundary between classes and instances
Authors: Mittal Sanja , Bobrow Daniel G. , Kahn Kenneth M.
Published: November 2005

Knowledge bases built in object-oriented systems use networks of interconnected objects in their representations. The mechanism described here provides a way to use such a network as a prototype by making virtual copies of it. The virtual copy is created incrementally. Values of instance variables in the virtual copy are inherited from the prototype until locally overridden in the copy, similar to inheritance of defaults between instances and classes in Loops. A virtual copy preserves the topology of the original network. Virtual copies can be made from virtual copies. Alternative implementations of virtual copies allow different tradeoffs in space and lookup time. Virtual copies can be used for building knowledge bases for design, for representing contexts in a problem solving system, and have other uses in ordinary programming.
Impulse-86: a substrate for object-oriented interface design
Authors: Smith Reid G. , Dinitz Rich , Barth Paul
Published: November 2005

Impulse-86 provides a general and extensible substrate upon which to construct a wide variety of interactive user interfaces for developing, maintaining, and using knowledge-based systems. The system is based on five major building blocks:
Editor, Editor Window, PropertyDisplay, Menu
, and
Operations
. These building blocks are interconnected via a uniform framework and each has a well-defined set of responsibilities in an interface.

Customized interfaces can be designed by declaratively replacing some of the building blocks in existing Impulse-86 templates. Customization may involve a wide range of activities, ranging from simple override of default values or methods that control primitive operations (
e.g.
, font selection), to override of more central Impulse-86 methods (
e.g.
, template instantiation). Most customized interfaces require some code to be written—to handle domain-specific commands. However, in all cases, the Impulse-86 substrate provides considerable leverage by taking care of the low-level details of screen, mouse, and keyboard manipulation.

Impulse-86 is implemented in Strobe, a language that provides object-oriented programming support for Lisp. This simplifies customization and extension.
Experience with Flamingo: a distributed, object-oriented user interface system
Authors: Anderson David B.
Published: November 2005

The Flamingo Window Management System is based on a
remote method invocation
mechanism that provides separate processes running in a heterogeneous, distributed computing environment with complete access to Flamingo's objects and methods. This object-oriented interface has made Flamingo a
kernel window manager
into which device drivers, graphics libraries, window managers and user interfaces can be dynamically loaded. This paper discusses the strengths and weaknesses of Flamingo's system architecture, and introduces a new architecture which will provide a network-wide object space with object protection, migration, and garbage collection.
An experience with a Prolog-based object-oriented language
Authors: Fukunaga Koichi , Hirose Shin-ichi
Published: November 2005

This paper presents an experience with a programming language SPOOL which is based on the combination of object-oriented programming and logic programming. This language inherits the capability of knowledge base organization from object-oriented programming and its expressive power from logic programming.

The experience of the application of SPOOL to the program annotation system showed that this combination was quite useful to formalize domain knowledge into declarative data types and make them reusable in different contexts. It also showed the need for further study such as better linguistic support to exploit the full power of this combination.
A Smalltalk system for algebraic manipulation
Authors: Abdali S. Kamal , Cherry Guy W. , Soiffer Neil
Published: November 2005

This paper describes the design of an algebra system Views implemented in Smalltalk. Views contains facilities for dynamic creation and manipulation of
computational domains
, for
viewing
these domains as various
categories
such as groups, rings, or fields, and for expressing algorithms generically at the level of categories. The design of Views has resulted in the addition of some new abstractions to Smalltalk that are quite useful in their own right.
Parameterized classes
provide a means for run-time creation of new classes that exhibit generally very similar behavior, differing only in minor ways that can be described by different instantiations of certain parameters.
Categories
allow the abstraction of the common behavior of classes that derives from the class objects and operations satisfying certain laws independently of the implementation of those objects and operations.
Views
allow the run-time association of classes with categories (and of categories with other categories), facilitating the use of code written for categories with quite different interpretations of operations. Together, categories and views provide an additional mechanism for code sharing that is richer than both single and multiple inheritance. The paper gives algebraic as well as non-algebraic examples of the above-mentioned features.
Petri net-based object-oriented modelling of distributed systems
Authors: Bruno Giorgio , Balsamo Alessandra
Published: November 2005

This paper presents an object-oriented approach for building distributed systems. An example taken from the field of computer integrated manufacturing systems is taken as a guideline. According to this approach a system is built up through three steps: control and synchronization aspects for each class of objects are treated first using PROT nets, which are a high-level extension to Petri nets; then data are introduced specifying the internal states of the objects as well as the messages they send each other; finally the connections between the objects are introduced by means of a data flow diagram between classes. The implementation uses ADA as the target language, exploiting its tasking and structuring mechanisms. The flexibility of the approach and the possibility of using a knowledge-based user interface promote rapid prototyping and reusability.
An exemplar based Smalltalk
Authors: LaLonde Wilf R. , Thomas Dave A. , Pugh John R.
Published: November 2005

Two varieties of object-oriented systems exist: one based on classes as in Smalltalk and another based on exemplars (or prototypical objects) as in Act/1. By converting Smalltalk from a class based orientation to an exemplar base, independent instance hierarchies and class hierarchies can be provided. Decoupling the two hierarchies in this way enables the user's (logical) view of a data type to be separated from the implementer's (physical) view. It permits the instances of a class to have a representation totally different from the instances of a superclass. Additionally, it permits the notion of multiple representations to be provided without the need to introduce specialized classes for each representation. In the context of multiple inheritance, it leads to a novel view of inheritance (or-inheritance) that differentiates it from the more traditional multiple inheritance notions (and-inheritance). In general, we show that exemplar based systems are more powerful than class based systems. We also describe how an existing class based Smalltalk can be transformed into an exemplar-based Smalltalk and discuss possible approaches for the implementation of both and-inheritance and or-inheritance.
Encapsulators: a new software paradigm in Smalltalk-80
Authors: Pascoe Geoffrey A.
Published: November 2005

Certain situations arise in programming that lead to multiply polymorphic expressions, that is, expressions in which several terms may each be of variable type. In such situations, conventional object-oriented programming practice breaks down, leading to code which is not properly modular. This paper describes a simple approach to such problems which preserves all the benefits of good object-oriented programming style in the face of any degree of polymorphism. An example is given in Smalltalk-80 syntax, but the technique is relevant to all object-oriented languages.
A simple technique for handling multiple polymorphism
Authors: Ingalls Daniel H. H.
Published: November 2005

Certain situations arise in programming that lead to multiply polymorphic expressions, that is, expressions in which several terms may each be of variable type. In such situations, conventional object-oriented programming practice breaks down, leading to code which is not properly modular. This paper describes a simple approach to such problems which preserves all the benefits of good object-oriented programming style in the face of any degree of polymorphism. An example is given in Smalltalk-80 syntax, but the technique is relevant to all object-oriented languages.
Pi: a case study in object-oriented programming
Authors: Cargill T. A.
Published: November 2005

Pi is a debugger written in C + +. This paper explains how object-oriented programming in C + + has influenced Pi's evolution. The motivation for object-oriented programming was to experiment with a browser-like graphical user interface. The first unforeseen benefit was in the symbol table: lazy construction of an abstract syntax-based tree gave a clean interface to the remainder of Pi, with an efficient and robust implementation. Next, though not in the original design, Pi was easily modified to control multiple processes simultaneously. Finally, Pi was extended to control processes executing across multiple heterogeneous target processors.
A distributed repository for immutable persistent objects
Authors: Wiebe Douglas
Published: November 2005

Jasmine is an object-oriented system for programming-in-the-large. Jasmine describes software using
system model objects
. These objects are persistent (they have lifetimes of days or decades) and immutable (since system models act as historical records). This paper describes JStore, a distributed, replicated repository for system model objects. JStore provides
robust, transactional, write-once
storage.

Designs are presented for the serialization, location, and replication of objects.
Description procedures
serialize objects for network transmission and permanent storage. An
expanding ring multicast
search algorithm locates saved objects. JStore replicates objects using a
lazy replication
algorithm built on top of the location mechanism.
Decision procedures
determine the replication policy used at each storage site.
Moving structures between Smalltalk images
Authors: Vegdahl Steven R.
Published: November 2005

There are a number of reasons why a user might want to move data structures between Smalltalk images. Unfortunately, the facilities for doing this in the standard Smalltalk image are inadequate: they do not handle circular structures properly, for example. We have implemented a collection of Smalltalk methods that handles circular structures; in addition, these methods have a number of other advantages over those provided in the standard image. This paper is largely a discussion of the issues that arose during their design, implementation, and use.
Incremental re-execution of programs
Authors: Karinthi R. R. , Weiser M.
Published: November 2005

Interpreters replace the edit/compile/run cyle with edit/run. Dynamic computing environments, like spreadsheets, shorten this still more to just edit. So-called "Visiprog" environments, such as Maryland's XED, permit developing normal imperative programs in a dynamic computing environment, XED and similar environments, because they show the results of executing a program after every (reasonable) editing step, raise the issue of efficient incremental execution. Incremental execution optimizations are also applicable to any programming situation, including batch/cards, in which nearly the same program is run many times on nearly the same data. However, the requirement of remembering large amounts of internal state between runs make incremental exectution most natural for interpreted languages. This paper examines some algorithms for incremental execution. Based on the frequency of typical program editing changes, we predict the importance of optimizing certain kinds of incremental execution. We also examine actual speedups obtained in executing programs after subjecting them to these simulated incremental edits under these optimizations. The speedups range from factors of 1.1 to near 10. Finally, we discuss the feasibility of including these optimizations in an actual dynamic computing environment like XED, and in more traditional programming environments.
The type inference and coercion facilities in the scratchpad II interpreter
Authors: Sutor R. S. , Jenks R. D.
Published: November 2005

The Scratchpad II system is an abstract datatype programming language, a compiler for the language, a library of packages of polymorphic functions and parametrized abstract datatypes, and an interpreter that provides sophisticated type inference and coercion facilities. Although originally designed for the implementation of symbolic mathematical algorithms, Scratchpad II is a general purpose programming language. This paper discusses aspects of the implementation of the interpreter and how it attempts to provide a user friendly and relatively weakly typed front end for the strongly typed programming language.
A generator for language-specific debugging systems
Authors: Bahlke R. , Moritz B. , Snelting G.
Published: November 2005

We present a system which generates interactive high-level debugging systems from formal language definitions. The language definer has to specify a denotational semantics augmented with a formal description of the language specific debugging facilities. The generated debugger offers the traditional features such as tracing programs, setting breakpoints, displaying variables etc; interaction with the user is always on language level rather than on machine level. The concept has been implemented as part of the PSG-Programming System Generator, and has successfully been used to generate debuggers for Pascal and Modula-2. The core of the implementation consists of an interpreter for a functional language, which has been extended with the language-independent mechanisms needed in order to allow interaction with the user during program execution.
Implementation of a high-speed Prolog interpreter
Authors: Krall A.
Published: November 2005

This paper describes the implementation of a high speed Prolog interpreter on a standard microprocessor (50 KLIPS on a 16 MHz MC68020). The interpreter is based on direct threaded code. By this method an interpreted program achieves the same speed as a compiled program, but uses only a tenth of memory. The first part of this paper describes the implementation of the interpreter. The second part compares the implementation, the runtime and the storage requirements with that of a compiler.
Efficient interpretation of Prolog programs
Authors: Barklund J.
Published: November 2005

The paper focuses on three ideas for solving problems with writing interpreters for the logic programming language Prolog in Prolog and how to combine these ideas to an interpreter for Prolog which is both simple and efficient. The resulting interpreter system can be incorporated into a Prolog based on Warren's Abstract Machine and built mostly from existing parts of it. The interpreter has been implemented and is used in a Prolog system developed at Uppsala University.
A Fortran 77 interpreter for mutation analysis
Authors: Offutt A. J. , King K. N.
Published: November 2005

Mutation analysis is a powerful technique for testing software systems. In the Mothra project, conducted at Georgia Tech's Software Engineering Research Center, mutation analysis is used as a basis for building an integrated software testing environment. Mutation analysis requires the execution of many slightly differing versions of the same program to evaluate the quality of the data used to test the program. In the current version of the Mothra system, a program to be tested is translated to intermediate code, where it and its mutated versions are executed by an interpreter.In this paper, we discuss some of the unique requirements of an interpreter used in a mutation-based testing environment. We then describe how these requirements affected the design and implementation of the Fortran 77 version of the Mothra interpreter. Other topics covered include the architecture of the interpreter and many of the design elements that it incorporates. We also describe the intermediate language used by Mothra and the features of the interpreter that are needed for software testing.
Cint: a RISC interpreter for the C programming language
Authors: Davidson J. W. , Gresh J. V.
Published: November 2005

Cint
is an interpretation system for the C programming language. Like most interpretation systems, it provides "load and go" type execution as well as enhanced debugging and performance analysis tools.
Cint
consists of two phases--a translator and an interpreter. The translator compiles the source program into code for a virtual machine. The interpreter then loads and executes this code. While providing services similar to traditional interpreters,
Cint
differs from them in two important ways. First, the virtual machine languages used by many interpreters are quite large; machines with 100 to 200 operations are common. In contrast,
Cint's
virtual machine has only 63 operations. Second, to achieve acceptable execution speeds, interpreters are often implemented in the assembly language of the host machine.
Cint
, however, is written entirely in C and is therefore portable. In fact, it has been transported to four machines without modification. Despite the compact size of the virtual machine language and the high-level language implementation,
Cint's
execution speed is comparable to that of other interpreters. This paper describes the design of the virtual machine, the implementation of the interpreter, and the performance of the system.
Managing stack frames in Smalltalk
Authors: Moss J. E. B.
Published: November 2005

The Smalltalk programming language allows
contexts
(stack frames) to be accessed and manipulated in very general ways. This sometimes requires that contexts be retained even after they have terminated executing, and that they be reclaimed other than by LIFO stack discipline. The authoritative definition of Smalltalk [Goldberg and Robson 83] uses reference counting garbage collection to manage contexts, an approach found to be inadequate in practice [Krasner, et al. 83]. Deutsch and Schiffman have described a technique that uses an actual stack as much as possible [Deutsch and Schiffman 84]. Here we offer a less complex technique that we expect will have lower total overhead and reclaim many frames sooner and more easily. We are implementing our technique as part of a state of the art Smalltalk interpreter. The approach may apply to other languages that allow indefinite lifetimes for execution contexts, be they interpreted or compiled.
Memory allocation and higher-order functions
Authors: Danvy O.
Published: November 2005

This paper presents a constant-time marking-collecting algorithm to efficiently implement recursion with a general heap memory rather than with a vectorial stack, in a context of frequent captures of continuations. It has been seen to reduce the 80% garbage collection overhead to less than 5% on average.The algorithm has been built into a virtual machine to efficiently implement at the assembly level the Actor language PLASMA, an Actor-oriented version of PROLOG and a variant of SCHEME, currently in use on 8086, 68000 and Vax.The rationale to use the heap memory is that continuations are available
via
a single pointer in a unified memory and can be shared optimally when recurrently captured, which is simply impossible using a strategy based on stack recopy. Further, non-captured continuations can be incrementally garbage collected on the fly.Part I describes the elementary recursive instructions of the virtual machine. Part II presents and proves the marking-collecting strategy. Part III safely generalizes the transformation "call + return = branch" in a way compatible with the possible capture of the current continuation. An appendix relates its integration in the Virtual Scheme Machine supporting Scheme 84.
Parallelism, persistence and meta-cleanliness in the symmetric Lisp interpreter
Authors: Gelernter D. , Jagannathan S. , London T.
Published: November 2005

Symmetric Lisp is a programming language designed around first-class environments, where an environment is a dictionary that associates names with definitions or values. In this paper we describe the logical structure of the Symmetric Lisp interpreter. In other interpreted languages, the interpreter is a virtual machine that evaluates user input on the basis of its own internal state. The Symmetric Lisp interpreter, on the other hand, is a simple finite-state machine with no internal state. Its role is to attach user input to whatever environment the user has specified; such environments are transparent objects
created by, maintained by and fully accessible to
the user. The interpreter's semantics are secondary to the
semantics of environments
in Symmetric Lisp: it is the environment-object to which an expression is attached, not the interpreter, that controls the evaluation of expressions.This arrangement has several consequences. Because environments in Symmetric Lisp are governed by a parallel evaluation rule, the Symmetric Lisp interpreter is a
parallel
interpreter. A Symmetric Lisp environment evaluates to another environment; a session with the interpreter therefore yields a well-defined environment object as its result. Users are free to write routines that manage these interpreter-created objects - routines that list the elements of a namespace, coalesce environments, maintain multiple name definitions and so on precisely because environment objects may be freely inspected and manipulated. Because a named environment may contain other named environments as elements, interpreter-created objects may be regarded as hierarchical file systems. Because of the parallel evaluation semantics of environments, the interpreter is well-suited as an interface to a concurrent, language-based computer system that uses Symmetric Lisp as its base language. We argue that - in short - a basic semantic simplification in Symmetric Lisp promises a correspondingly basic increase in power at the user-interpreter interface.
CCAL: an interpreted language for experimentation in concurrent control
Authors: Kearns P. , Freeman M.
Published: November 2005

Concurrent Control Abstraction Language, CCAL, is an interpreted language which provides no particular control regime to the user. CCAL instead supports five primitive operations which manipulate an abstract model of inter-procedural control. This model is intrinsically concurrent, and the user is allowed to construct high-level concurrent control operations from the primitives (hence, control abstraction). The primary use of CCAL is as a vehicle by which rapid prototyping of application specific control forms may be done and as a tool for the construction and evaluation of novel control forms, especially control forms for highly concurrent and distributed systems. The CCAL interpreter is implemented as a distributed program on a network of Vaxen and Sun-3 workstations under 4.2bsd and 4.3bsd Unix
1
. CCAL programs appear as multi-process programs in a shared memory system. Both true and apparent concurrency are possible. This paper describes the control abstraction facilities offered by the CCAL interpreter, its use, and implementation strategies in the distributed environment.
Real-time concurrent collection on stock multiprocessors
Authors: Appel A. W. , Ellis J. R. , Li K.
Published: November 2005

We've designed and implemented a copying garbage-collection algorithm that is efficient, real-time, concurrent, runs on commercial uniprocessors and shared-memory multiprocessors, and requires no change to compilers. The algorithm uses standard virtual-memory hardware to detect references to “from space” objects and to synchronize the collector and mutator threads. We've implemented and measured a prototype running on SRC's 5-processor Firefly. It will be straightforward to merge our techniques with generational collection. An incremental, non-concurrent version could be implemented easily on many versions of Unix.
Interprocedural side-effect analysis in linear time
Authors: Cooper K. D. , Kennedy K.
Published: November 2005

We present a new method for solving Banning's alias-free flow-insensitive side-effect analysis problem. The algorithm employs a new data structure, called the
binding multi-graph
, along with depth-first search to achieve a running time that is linear in the size of the call multi-graph of the program. This method can be extended to produce fast algorithms for data-flow problems with more complex lattice structures.
Anatomy of a hardware compiler
Authors: Keutzer K. , Wolf W.
Published: November 2005

Programming-language compilers generate code targeted to machines with fixed architectures, either parallel or serial. Compiler techniques can also be used to generate the hardware on which these programming languages are executed. In this paper we demonstrate that many compilation techniques developed for programming languages are applicable to compilation of register-transfer hardware designs. Our approach uses a typical syntax-directed translation → global optimization → local optimization → code generation → peephole optimization method. In this paper we will describe ways in which we have both followed and diverged from traditional compiler approaches to these problems and compare our approach to other compiler oriented approaches to hardware compilation.
An optimizer for Ada - design, experiences and results
Authors: Schwarz B. , Kirchgässner W. , Landwehr R.
Published: November 2005

In this paper we describe the design of a global machine independent low level optimizer for the Karlsruhe Ada Compiler. We give a short overview on the optimizations and data structures used in the optimizer as well as some experiences with the optimizer. Detailed measurements are provided for a collection of benchmarks. The average improvement of code speed is 40%.
An automatically generated, realistic compiler for imperative programming language
Authors: Pleban U. F. , Lee P.
Published: November 2005

We describe the automatic generation of a complete, realistic compiler from formal specifications of the syntax and semantics of Sol/C, a nontrivial imperative language “sort of like C.” The compiler exhibits a three pass structure, is efficient, and produces object programs whose performance characteristics compare favorably with those produced by commercially available compilers. To our knowledge, this is the first time that this has been accomplished.
Semantic analysis in a concurrent compiler
Authors: Seshadri V. , Weber S. , Wortman D. B. , Yu C. P. , Small I.
Published: November 2005

Traditional compilers are usually sequential programs that serially process source programs through lexical analysis, syntax analysis, semantic analysis and code generation. The availability of multiprocessor computers has made it feasible to consider alternatives to this serial compilation process. The authors are currently engaged in a project to devise ways of structuring compilers so that they can take advantage of modern multiprocessor hardware. This paper is about the most difficult aspect of concurrent compilation: concurrent semantic analysis.
Compiling C for vectorization, parallelization, and inline expansion
Authors: Allen R. , Johnson S.
Published: November 2005

Practical implementations of real languages are often an excellent way of testing the applicability of theoretical principles. Many stresses and strains arise from fitting practicalities, such as performance and standard compatibility, to theoretical models and methods. These stresses and strains are valuable sources of new research and insight, as well as an oft-needed check on the egos of theoreticians.

Two fertile areas that are often explored by implementations are

Places where tractable models fail to match practice. This can lead to new models, and may also affect practice (e.g., the average programming language has become more context free over the last several decades).

Places where existing algorithms fail to deal with practical problems effectively, frequently because the problems are large in some dimension that has not been much explored.

The present paper discusses the application of a much studied body of algorithms and techniques [Alle 83, KKLW 80, Bane 76, Wolf 78, Wolf 82, Kenn 80, Lamp 74, Huso 82] for vectorizing and optimizing Fortran to the problem of vectorizing and optimizing C. In the course of this work some algorithms were discarded, others invented, and many were tuned and modified. The experience gave us insight into the strengths and weaknesses of the current theory, as well as into the strong and weak points of C on vector/parallel machines. This paper attempts to communicate some of those insights.
The history of FORTRAN I, II, and III
Authors: Backus John
Published: November 2005

Before 1954 almost all programming was done in machine language or assembly language. Programmers rightly regarded their work as a complex, creative art that required human inventiveness to produce an efficient program. Much of their effort was devoted to overcoming the difficulties created by the computers of that era: the lack of index registers, the lack of built- in floating point operations, restricted instruction sets (which might have AND but not OR, for example), and primitive input- output arrangements. Given the nature of computers, the services which “automatic programming” performed for the programmer were concerned with overcoming the machine's shortcomings. Thus the primary concern of some “automatic programming” systems was to allow the use of symbolic addresses and decimal numbers (e.g., the MIDAC Input Translation Program [Brown and Carr 1954]).

But most of the larger “automatic. Programming” systems (with the exception of Laning and Zierler's algebraic system [Laning and Zierler 1954] and the A-2 compiler [Remington Rand 1953; Moser 1954]) simply provided a synthetic “computer” with an order code different from that of the real machine. This synthetic computer usually had floating point instructions and index registers and had improved input-output commands; it was therefore much easier to program than its real counterpart.
The early history and characteristics of PL/I
Authors: Radin George
Published: November 2005

Source material for a written history of PL/I has been preserved and is available in dozens of cartons, each packed with memos, evaluations, language control logs, etc. A remembered history of PL/I is retrievable by listening to as many people, each of whom was deeply involved in one aspect of its progress. This paper is an attempt to gather together and evaluate what I and some associates could read and recall in a few months. There is enough material left for several dissertations.

The exercise is important, I think, not only because of the importance of PL/I, but because of the breadth of its subject matter. Since PL/I took as its scope of applicability virtually all of programming, the dialogues about its various parts encompass a minor history of computer science in the middle sixties. There are debates among numerical analysts about arithmetic, among language experts about syntax, name scope, block structure, etc., among systems programmers about multi-tasking, exception handling, I/O, and more.
Hardware/software tradeoffs for increased performance
Authors: Hennessy John , Jouppi Norman , Baskett Forest , Gross Thomas , Gill John
Published: November 2005

Most new computer architectures are concerned with maximizing performance by providing suitable instruction sets for compiled code and providing support for systems functions. We argue that the most effective design methodology must make simultaneous tradeoffs across all three areas: hardware, software support, and systems support. Recent trends lean towards extensive hardware support for both the compiler and operating systems software. However, consideration of all possible design tradeoffs may often lead to less hardware support. Several examples of this approach are presented, including: omission of condition codes, word-addressed machines, and imposing pipeline interlocks in software. The specifics and performance of these approaches are examined with respect to the MIPS processor.
Coding guidelines for pipelined processors
Authors: Rymarczyk James W.
Published: November 2005

This paper is a tutorial for assembly language programmers of pipelined processors. It describes the general characteristics of pipelined processors and presents a collection of coding guidelines for them. These guidelines are particularly significant to compiler developers who determine object code patterns.
Fast procedure calls
Authors: Lampson Butler W.
Published: November 2005

A mechanism for control transfers should handle a variety of applications (e.g., procedure calls and returns, coroutine transfers, exceptions, process switches) in a uniform way. It should also allow an implementation in which the common cases of procedure call and return are extremely fast, preferably as fast as unconditional jumps in the normal case. This paper describes such a mechanism and methods for its efficient implementation.
Systematic protection mechanism design
Authors: Jones Douglas W.
Published: November 2005

This work describes an attempt to systematically design a hardware resource protection mechanism when given the requirements of a particular language as a target. The design process is formalized as a structured walk through the multidimensional computer design space towards a hypothetical class of optimal machines. Each step in this walk involves a change in the distribution of work between the compiler and run-time system but no change in the source language semantics. The starting point for this walk is the result of a semantic analysis of the language to be implemented; typically, this produces a very high level machine where the compiler, if any, is trivial. The walk ends when no changes result in a net improvement. This does not guarantee that the result is even locally optimal, since the changes tried depend on the ingenuity and persistence of the designer.

This design approach has been used to arrive at a practical, general purpose protection mechanism oriented towards the needs of the Ada language (preliminary version). This architecture was evaluated by comparing it with the PDP-11/45. For the purpose of this comparison, the protection mechanism was incorporated into a partially specified PDP-11 like instruction set. The number of bits making up the processor state and the number of operations involved in address computation were evaluated. On this basis, the result appears to be competitive and worth further investigation.
Compiler chip
Authors: Fusaoka Akira , Hirayama Masaharu
Published: November 2005

In this paper we discuss about another approch:
Compiler Chip
, which is a VLSI implementation of a compiler. Constructing a compiler by a few VLSI chip, the computer manufacturer can deliver compilers by sets of VLSI chips, and these chips are installed in a intelligent terminal in order to remove the compilation from the tasks which are processed in the mainframe.
Hardware support for memory protection
Authors: Wilkes M. V.
Published: November 2005

This paper is intended to stimulate discussion on the present state of hardware supported capability systems. Interest in such systems grew up in the mid-1960's and since that time information has been published on several different versions. In the opinion of some observers, the software complexity of these systems outweighs the advantage gained. The paper surveys the situation, and endeavors to set out the general features that a hardware supported capability system should possess. An attempt is made to identify the causes of the complexity and to make recommendations for removing them. The arguments for and against the tagging of capabilities are discussed and attention is drawn to a system of semi-tagging previously proposed by the author.