bluuebunny/crossref_metadata_2025 huggingface dataset:
Can structured programs be efficient?
Authors: DeMillo R. A. , Eisenstat S. C. , Lipton R. J.
Published: November 2005

By using a new method for comparing the power of control structures, we give evidence that there are provable
quantitative
differences among various control structures. The key result discussed in this note states that there are natural goto programs which can
only
be simulated by structured programs that are either very large or very slow.
Parallel programming concepts in a definitional language
Authors: Kessels J. L. W.
Published: November 2005

A sequential programming language forces the programmer to prescribe explicitly the order in which the operations in his program have to be executed; even if the order is not relevant to the solution of his problem. The requirement to indicate irrelevant sequencing can be removed if the language provides facilities to specify a task in a nonprocedural manner. In general, a program specified in this way will allow concurrent evaluation.This paper describes a conceptual framework for a high level programming language providing nonprocedural and sequential facilities. In one program nonprocedural and sequential program modules may be nested in an arbitrary order and to an arbitrary depth.
An introduction to Trellis/Owl
Authors: Schaffert Craig , Cooper Topher , Bullis Bruce , Kilian Mike , Wilpolt Carrie
Published: November 2005

Trellis/Owl is an object-based language incorporating a type hierarchy with multiple inheritance and compile-time type checking. The combination of features in the language facilitates the design, implementation, and evolution of large computer programs. This paper provides an brief introduction to the Trellis/Owl language. It discusses the basic elements of the language, objects, and shows how these are specified and implemented using
types, operations,
and
components
. The notion of a type hierarchy is introduced by a discussion of
subtyping
and
inheritance
. Other elements of the Trellis/Owl language such as
type generators, iterators,
and
exceptions
are briefly presented.
Encapsulation and inheritance in object-oriented programming languages
Authors: Snyder Alan
Published: November 2005

Object-oriented programming is a practical and useful programming methodology that encourages modular design and software reuse. Most object-oriented programming languages support
data abstraction
by preventing an object from being manipulated except via its defined external operations. In most languages, however, the introduction of
inheritance
severely compromises the benefits of this encapsulation. Furthermore, the use of inheritance itself is globally visible in most languages, so that changes to the inheritance hierarchy cannot be made safely. This paper examines the relationship between inheritance and encapsulation and develops requirements for full support of encapsulation with inheritance.
A third generation Smalltalk-80 implementation
Authors: Caudill Patrick J. , Wirfs-Brock Allen
Published: November 2005

A new, high performance Smalltalk-80™ implementation is described which builds directly upon two previous implementation efforts. This implementation supports a large object space while retaining compatibility with previous Smalltalk-80™ images. The implementation utilizes a interpreter which incorporates a generation based garbage collector and which does not have an object table. This paper describes the design decisions which lead to this implementation and reports preliminary performance results.
Swamp: a fast processor for Smalltalk-80
Authors: Lewis David M. , Galloway David R. , Francis Robert J. , Thomson Brian W.
Published: November 2005

A processor for the Smalltalk-80↑ programming language is described. This machine is implemented using a standard bit slice ALU and sequencer, TTL MSI, and NMOS LSI RAMS. It executes an instruction set similar to the Smalltalk-80 virtual machine instruction set. The data paths of the machine are optimized for rapid Smalltalk-80 execution by the inclusion of a context cache, tag checking, and a hardware method cache. Each context is only partly initialized when created, and has no memory allocated for it until a possibly non-LIFO reference to it is created. The machine is microprogrammed, and uses a simple next micro-address prediction strategy to obtain most of the performance of pipelining without the attendant complexity. The machine can execute simple instructions at over 7M bytecodes per second and has a predicted average throughput of 1.9M bytecodes per second.

A processor for the Smalltalk-80↑ programming language is described. This machine is implemented using a standard bit slice ALU and sequencer, TTL MSI, and NMOS LSI RAMS. It executes an instruction set similar to the Smalltalk-80 virtual machine instruction set. The data paths of the machine are optimized for rapid Smalltalk-80 execution by the inclusion of a context cache, tag checking, and a hardware method cache. Each context is only partly initialized when created, and has no memory allocated for it until a possibly non-LIFO reference to it is created. The machine is microprogrammed, and uses a simple next micro-address prediction strategy to obtain most of the performance of pipelining without the attendant complexity. The machine can execute simple instructions at over 7M bytecodes per second and has a predicted average throughput of 1.9M bytecodes per second.
The application accelerator illustration system
Authors: Miller Michael S. , Cunningham Howard , Lee Chan , Vegdahl Steven R.
Published: November 2005

The Application Accelerator Illustration System is a prototype of an integrated CAD environment that supports the development of application-specific integrated circuits. The current implementation features a hardware description language compiler, timing analyzer, functional simulator, waveform tracer, and data path place and route facility. The system is implemented in Smalltalk-80™.
Virtual instruments: object-oriented program synthesis
Authors: Bhaskar K. S. , Pecol J. K. , Beug J. L.
Published: November 2005

Virtual Instruments
1
is an experimental programming environment for developing electronic test and measurement (T&M) applications. Intended users are test engineers, who are not programmers, but computer literate domain specialists. Unlike traditional programming environments, that provide weak support for a broad range of applications, virtual instruments provides strong support for a specific application. The programming paradigm is bottom-up synthesis of layers of virtual machines — called virtual instruments — using human interface models from the application domain, so that software development occurs without writing code. The object-oriented view of the world has proven a natural fit. Implementation was in Berkeley Smalltalk on a SUN workstation.
The design and implementation of Concurrent Smalltalk
Authors: Yokote Yasuhiko , Tokoro Mario
Published: November 2005

ConcurrentSmalltalk is a programming language/system which incorporates the facilities of concurrent programming in Smalltalk-80
1
. Such facilities are realized by providing
concurrent constructs
and
atomic objects
. This paper first gives an outline of ConcurrentSmalltalk. Then, the design of ConcurrentSmalltalk is described. The implementation of ConcurrentSmalltalk is presented in detail.
A diagram for object-oriented programs
Authors: Cunningham Ward , Beck Kent
Published: November 2005

We introduce a notation for diagramming the message sending dialogue that takes place between objects participating in an object-oriented computation. Our representation takes a global point of view which emphasizes the collaboration between objects implementing the behavior of individuals. We illustrate the diagram's usage with examples drawn from the Smalltalk-80™ virtual image. We also describe a mechanism for automatic construction of diagrams from Smalltalk code.
Boolean classes
Authors: McAllester David , Zabih Ramin
Published: November 2005

We extend the notion of class so that any Boolean combinations of classes is also a class. Boolean classes allow greater precision and conciseness in naming the class of objects governed a particular method. A class can be viewed as a predicate which is either true or false of any given object. Unlike predicates however classes have an inheritance hierarchy which is known at compile time. Boolean classes extend the notion of class, making classes more like predicates, while preserving the compile time computable inheritance hierarchy.
Augmentation of object-oriented programming by concepts of abstract data type theory: the ModPascal experience
Authors: Olthoff Walter G.
Published: November 2005

Object-oriented programming and abstract data type (ADT) theory have emerged from the same origin of computer science: the inability to deal efficiently with 'programming in the large' during the early seventies. Each of the approaches has led to significant practical and theoretical results resp. Nevertheless it is still unsatisfactory that up to now the mutual influence seems to be limited to more or less syntactical issues (e.g. the provision of packages, clusters, forms).

In this paper we report on the object-oriented language ModPascal that was developed as part of the Integrated Software Development and Verification (ISDV) Project. We show how the essence of concepts of ADT theory as algebraic specifications, enrichments, parameterized specifications or signature morphisms as well as their semantics can be consistently integrated in an imperative object-oriented language. Furthermore, as the experience of using ModPascal as target language of the ISDV System has shown, we claim that without similar support of theoretical concepts techniques like formal specification of programs or algebraic verification loose their power and even applicability.
The management of changing types in an object-oriented database
Authors: Skarra Andrea H. , Zdonik Stanley B.
Published: November 2005

We examine the problem of type evolution in an object-oriented database environment. Type definitions are persistent objects in the database and as such may be modified and shared. The effects of changing a type extend to objects of the type and to programs that use objects of the type. We propose a solution to the problem through an extension of the semantic data model.

A change in the interface defined by a type may result in errors when programs use new or old objects of the type. Through the use of an abstraction of the type over time, timestamping and error handling mechanisms provide support for the type designer in creating compatible versions of the type. The mechanisms are incorporated into the behavior defined by the type and are inherited via the type-lattice.
A block-and-actions generator as an alternative to a simulator for collecting architecture measurements
Authors: Huguet M. , Lang T. , Tamir Y.
Published: November 2005

To design a new processor or to modify an existing one, designers need to gather data to estimate the influence of specific architecture features on the performance of the
proposed machine
(PM). To obtain this data, it is necessary to measure on an
existing machine
(EM) the dynamic behavior of
typical programs
. Traditionally,
simulators
have been used to obtain measurements for PMs. Since several hundred EM instructions are required to decode, interpret, and measure each simulated (PM) instruction, the simulation time of typical programs is prohibitively large. Thus, designers tend to simulate only small programs and the results obtained might not be representative of a real system behavior. In this paper we present an alternative tool for collecting architecture measurements: the Block-and-Actions Generator (BKGEN). BKGEN produces a version of the program being measured which is directly executable by the EM. This executable version is obtained directly with the EM compiler or with the PM compiler and a assembly-to-assembly translator. The choice between these alternatives depends on the EM and PM compiler technology and the type of measurements to be obtained. BKGEN also collects the PM events to be measured (called
actions
). Each EM
block of instructions
is associated with a PM
block of actions
so that when the program is executed, it collects the measurements associated with the PM. The main advantage of BKGEN is that the execution time is substantially reduced compared to the execution time of a simulator while collecting similar data. Thus, large typical programs (compilers, assemblers, word processors, ...) can be used by the designer to obtain meaningful measurements.
Automatic design and implementation of language data types
Authors: Shebs S. T. , Kessler R. R.
Published: November 2005

Language implementation is in need of automation. Although compiler construction has long been aided by parser generators and other tools, interpreters and runtime systems have been neglected, even though they constitute a large component of languages like Lisp, Prolog, and Smalltalk. Of the several parts of a runtime system, the primitive datatype definitions present some of the most difficult decisions for the implementor. The effectiveness of type discrimination schemes, interactions between storage allocation and virtual memory, and general time/space tradeoffs are issues that have no simple resolution-they must be evaluated for each implementation. A formalism for describing implementations has been developed and used in a prototype designer of primitive data structures. The designer is a collection of heuristic rules that produce multiple designs of differing characteristics. Cost evaluation on machine code derived from those designs yields performance formulas, which are then used to estimate the designs' effect on benchmark programs.
Enhancement through extension: the extension interpreter
Authors: Notkin D. , Griswold W. G.
Published: November 2005

The ability to extend programs dynamically has clear advantages. However, providing efficient yet sufficiently flexible support for such capabilities system-wide presents significant challenges. We describe a design and implementation of an extension mechanism that depends heavily on interpretive techniques, including call arbitration, dynamic linking, and multilanguage extensions. We discuss these mechanisms in the context of our
Extension Interpreter
, which embodies our ideas and provides a framework for discussing the efficiency and generality of the implementation. Our current implementation runs under BSD UNIX 4.2 and 4.3 on VAXes and SUN workstations. Extensions can be written in both C and in Icon, demonstrating our ability to address problems both of compiled and interpreted languages.
Efficient interpretation of synchronizable series expressions
Authors: Waters R. C.
Published: November 2005

The benefits of programming in a functional style are well known. For example, algorithms which are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent algorithms expressed as loops. Unfortunately, many programmers hesitate to use series expressions because they are typically implemented very inefficiently-the prime source of inefficiency being the creation of intermediate series objects.A restricted class of series expressions, obviously synchronizable series expressions, is defined which can be evaluated very efficiently because they do not require the creation of any intermediate series objects. A Common Lisp macro package has been implemented which supports obviously synchronizable series expressions. Using this macro package, programmers can obtain the advantages of expressing computations as series expressions without incurring any runtime overhead. Obviously synchronizable series expressions could be straightforwardly supported in any programming language.
An eductive interpreter for the language Lucid
Authors: Faustini A. A. , Wadge W. W.
Published: November 2005

We describe an interpreter for pLucid, a member of the Lucid family of functional dataflow languages. In appearance, pLucid is similar to Landin's Iswim, exept that individual variables and expressions denote
streams
(infinite sequences of data items), and function variables denote
filters
(stream-to-stream transformations). The actual data objects in pLucid (the components of streams) are those of
POP2:
numbers, strings, words, and lists. The 'inner syntax' (infix operations, conventions for denoting constants) are those of
POP2
as well.The interpreter (which was written in C) is
eductive:
it uses a tagged demand-driven scheme. Demands for values in the output stream generate demands for values of other variables internal to the program. These demands, and the values returned in response, are tagged according to "time" (sequence index) and place (node in the tree of function calls). Once computed, values are stored in an associative memory (the "warehouse") in case they are demanded again later in the computation. The warehouse is periodically cleaned out using a heuristic called the "retirement plan". The heuristic is not perfect, but does not have to be: in an eductive computation, the program is not altered as in reduction. If discarded values are needed again, they can be recomputed.The pLucid interpreter performs extensive runtime checks and error messages quote the source line containing the offended operator. A special end-of-data object permits a very simple treatment of finite (terminating) input and output. Of special interest is its interface to UNIX, which allows any system command to be used as a filter
inside
a pLucid program.The interpreter performs well enough for nontrivial programs to be developed and tested. These include (simple versions of) a text formatter, a distributed airline reservation system, and a full screen editor.
Selective interpretation as a technique for debugging computationally intensive programs
Authors: Chase B. B. , Hood R. T.
Published: November 2005

As part of Rice University's project to build a programming environment for scientific software, we have built a facility for program execution that solves some of the problems inherent in debugging large, computationally intensive programs. By their very nature such programs do not lend themselves to full-scale interpretation. In moderation however, interpretation can be extremely useful during the debugging process. In addition to discussing the particular benefits that we expect from interpretation, this paper addresses how interpretive techniques can be effectively used in conjunction with the execution of compiled code. The same implementation technique that permits interpretation to be incorporated as part of execution will also permit the execution facility to be used for debugging parallel programs running on a remote machine.
Design of an interpretive environment for Turing
Authors: Cordy James R. , Graham T. C. N.
Published: November 2005

This paper presents the design of an interpreter structure for modern programming languages such as Turing and Modula II that is modular and highly orthogonal while providing maximal flexibility and efficiency in implementation. At the outermost level, the structure consists of a front end, responsible for interaction with the user, and a back end, responsible for execution. The two are linked by a single database consisting of the tokenized statements of the user program. Interfaces between the major modules of each part are defined in such a way as to maximize reusability, and each interface can service a range of plug-compatible modules implementing radically different semantics. The design accommodates a wide spectrum of interpreter types ranging from batch-oriented compiler-simulators to statement-by-statement interactive execution, and provides for a range of program editing tools from simple line editors through to modern language-directed programming environments. It has served as the basis for several interpretive systems including the production Turing interpreter, the Turing Programming Environment, and the Turing Tool software maintenance tool.
The JADE interpreter: a RISC interpreter for syntax directed editing
Authors: Clark C. F.
Published: November 2005

This paper describes key features of an interpreter for a language-based editor. The interpreter unites in a RISC framework features which have been used in other domains. The paper examines each feature's integration into the RISC framework.
Register windows vs. register allocation
Authors: Wall D. W.
Published: November 2005

A large register set can be exploited by keeping variables and constants in registers instead of in memory. Hardware register windows and compile-time or link-time global register allocation are ways to do this. A measure of the effectiveness of any of these register management schemes is how thoroughly they remove loads and stores. This measure must also count extra loads and stores executed because of window overflow or conflicts between procedures.

By combining profiling, instrumentation, and in-line simulation, we measured the effectiveness of several register management schemes. These included compile-time and link-time schemes for allocating registers, and register window schemes using fixed-size or variable-sized windows. Link-time allocation based on profile information was the clear winner in some cases and did about as well as windows in the rest. Even link-time allocation based on an estimated profile was about as good as windows. Variable-sized windows sometimes did better than fixed-sized windows, but the difference was usually small.

Register windows require extra logic in the data path, which may slow the machine cycle slightly, and often use more chip real estate for additional registers. Proponents of windows suppose that they trade these drawbacks for a reduction in the number of memory references they must make. Our results show that this tradeoff should be made the other way. Keep the hardware simple, because a link-time register allocator can nearly duplicate the improvement in memory reference frequency. Then the cycle time can be as small as possible, resulting in faster programs overall.
DOC: a practical approach to source-level debugging of globally optimized code
Authors: Coutant D. S. , Meloy S. , Ruscetta M.
Published: November 2005

As optimizing compilers become more sophisticated, the problem of debugging the source code of an application becomes more difficult. In order to investigate this problem, we implemented DOC, a prototype solution for Debugging Optimized Code. DOC is a modification of the existing C compiler and source-level symbolic debugger for the HP9000 Series 800. This paper describes our experiences in this effort. We show in an actual implementation that source-level debugging of globally optimized code is viable.
Debugging concurrent processes: a case study
Authors: Stone J. M.
Published: November 2005

We present a case study that illustrates a method of debugging concurrent processes in a parallel programming environment. It uses a new approach called
speculative replay
to reconstruct the behavior of a program from the histories of its individual processes. Known time dependencies between events in different processes are used to divide the histories into dependence blocks. A graphical representation called a
concurrency map
displays possibilities for concurrency among processes. The replay technique preserves the known dependencies and compares the process histories generated during replay with those that were logged during the original program execution. If a process generates a replay history that does not match its original history, replay backs up. An alternative ordering of events is created and tested to see if it produces process histories that match the original histories. Successively more controlled replay sequences are generated, by introducing additional dependencies. We describe ongoing work on tools that will control replay without reconstructing the entire space of possible event orderings.

The case study presents a miniature example of shared-queue management that can be examined in detail. It demonstrates the replay technique and the construction and use of the concurrency map. Using our techniques, we detect a failure to which a standard algorithm for shared-queue management is susceptible.
Higher-order abstract syntax
Authors: Pfenning F. , Elliott C.
Published: November 2005

We describe motivation, design, use, and implementation of
higher-order abstract syntax
as a central representation for programs, formulas, rules, and other syntactic objects in program manipulation and other formal systems where matching and substitution or unification are central operations. Higher-order abstract syntax incorporates name binding information in a uniform and language generic way. Thus it acts as a powerful link integrating diverse tools in such formal environments. We have implemented higher-order abstract syntax, a supporting matching and unification algorithm, and some clients in Common Lisp in the framework of the Ergo project at Carnegie Mellon University.
Synchronous operations as first-class values
Authors: Reppy J. H.
Published: November 2005

Synchronous message passing via channels is an interprocess communication (IPC) mechanism found in several concurrent languages, such as CSP, occam, and Amber. Such languages provide a powerful selective I/O operation, which plays a vital role in managing communication with multiple processes. Because the channel IPC mechanism is “operation-oriented,” only procedural abstraction techniques can be used in structuring the communication/synchronization aspects of a system. This has the unfortunate effect of restricting the use of selective I/O, which in turn limits the communication structure. We propose a new, “value-oriented” approach to channel-based synchronization. We make synchronous operations first-class values, called
events
, in much the same way that functions are first-class values in functional programming languages. Our approach allows the use of data abstraction techniques for structuring IPC. We have incorporated events into PML, a concurrent functional programming language, and have implemented run-time support for them as part of the Pegasus system.
Multiprocessor Smalltalk: a case study of a multiprocessor-based programming environment
Authors: Pallas J. , Ungar D.
Published: November 2005

We have adapted an interactive programming system (Smalltalk) to a multiprocessor (the Firefly). The task was not as difficult as might be expected, thanks to the application of three basic strategies: serialization, replication, and reorganization. Serialization of access to resources disallows concurrent access. Replication provides multiple instances of resources when they cannot or should not be serialized. Reorganization allows us to restructure part of the system when the other two strategies cannot be applied.

We serialized I/O, memory allocation, garbage collection, and scheduling, we replicated the interpreter process, software caches, and a free-list, and we reorganized portions of the scheduling system to deal with some deep-seated assumptions. Our changes yielded a fairly low static overhead. We attribute our success to the choice of a small, flexible operating system, a set of constraints which simplified the problem, and the versality of the three strategies for dealing with concurrency. The current system has a moderate amount of overhead when parallelism is being used—25% to 65%. It is acceptable, but we believe it can be improved.
A portable global optimizer and linker
Authors: Benitez M. E. , Davidson J. W.
Published: November 2005

To reduce complexity and simplify their implementation, most compilers are organized as a set of passes or phases. Each phase performs a particular piece of the compilation process. In an optimizing compiler, the assignment of function and order of application of the phases is a critical part of the design. A particularly difficult problem is the arrangement of the code generation and optimization phases so as to avoid phase ordering problems caused by the interaction of the phases. In this paper, we discuss the implementation of a compiler/linker that has been designed to avoid these problems. The key aspect of this design is that the synthesis phases of the compiler and the system linker share the same intermediate program representation. This results in two benefits. It permits the synthesis phases of the compiler to be performed in any order and repeatedly, thus eliminating potential phase ordering problems. Second, it permits code selection to be invoked at any point during the synthesis phases as well as at link time. The ability to perform code selection at link time presents many opportunities for additional optimizations. Measurements about the effectiveness of using this approach in a C compiler on two different machines are presented.
The evolution of APL
Authors: Falkoff Adin D. , Iverson Kenneth E.
Published: November 2005

This paper is a discussion of the evolution of the APL language, and it treats implementations and applications only to the extent that they appear to have exercised a major influence on that evolution. Other sources of historical information are cited in References 1-3; in particular,
The Design of APL
[1] provides supplementary detail on the reasons behind many of the design decisions made in the development of the language. Readers requiring background on the current definition of the language should consult
APL Language
[4].

Although we have attempted to confirm our recollections by reference to written documents and to the memories of our colleagues, this remains a personal view which the reader should perhaps supplement by consulting the references provided. In particular, much information about individual contributions will be found in the Appendix to
The Design of APL
[1], and in the Acknowledgements in
A Programming Language
[10] and in
APL\360 User's Manual
[23]. Because Reference 23 may no longer be readily available, the acknowledgements from it are reprinted in Appendix A.
History of LISP
Authors: McCarthy John
Published: November 2005

This paper concentrates on the development of the basic ideas and distinguishes two periods - Summer 1958 through Summer 1958 when most of the key ideas were developed (some of which were implemented in the FORTRAN based FLPL), and Fall 1958 through 1962 when the programming language was implemented and applied to problems of artificial intelligence. After 1962, the development of LISP became multi-stranded, and different ideas were pursued in different places.
ACM SIGPLAN history of programming languages conference PL/I language summary
Authors: Rosin Robert F.
Published: November 2005

PL/I was developed in two distinct stages. First the language NPL was conceived by a joint user-IBM committee. IBM alone then developed PL/I by clarifying and refining the rather incomplete specification of NPL. This overview describes the major features of PL/I, and George Radin's paper makes clear the distinctions between these two languages.

The characteristics of PL/I were strongly influenced by two factors; what was known (in 1964-65) about commercial, scientific, real-time and system programming applications, and the features of FORTRAN, COBOL, and ALGOL which were useful in implementing those applications. The result is a language of great expressive power, which occasionally requires the programmer to manage great complexity.
The operating system and language support features of the BELLMAC
TM
-32 microprocessor.
Authors: Berenbaum Alan D. , Condry Michael W. , Lu Priscilla M.
Published: November 2005

The BELLMAC-32 microprocessor is a 32-bit microprocessor, implemented with CMOS technology, designed to support operating system functions and high level languages efficiently. The architecture was designed with the following objectives in mind:

• High performance.

• Enhanced operating system support capabilities.

• High level language support.

• High reliability, availability and maintainability.
Register allocation for free
Authors: Ditzel David R. , McLellan H. R.
Published: November 2005

The Bell Labs C Machine project is investigating computer architectures to support the C programming language.
1
One of the goals is to match an efficient architecture to the language and the compiler technology available. Measurements of different C programs show that roughly one out of every twenty instructions executed is either a procedure call or return.
2
Procedure call overhead is therefore a very important consideration in the overall machine design. A second and related area of primary concern in overall machine efficiency is the register allocation strategy. While use of additional registers can offer considerable improvement in execution times, adding registers usually has the adverse effects of increasing the procedure call overhead due to register saving and creating an undue burden on the compiler. In this paper we describe a piece of the C Machine architecture which effectively eliminates the register allocation problem, and improves procedure calling by drastically reducing storage references required by traditional register saving. The technique can be generalized for other languages and architectures, though we will only directly address those issues involving the C language.
On a general property of memory mapping tables
Authors: Reed Karl
Published: November 2005

The paper shows that memory mapping tables can be used to implement the display registers used in providing architectural support for block-structured languages such as Algol 60. This allows full lexical level addressing to be implemented on so-called von-Neuman machines.

The problems of fragmentation of the paged address space are explored, and machines with memory mapping schemes capable of supporting the proposals identified.

Attention is drawn to the similarity between segmented and paged schemes, and it is suggested that the latter may be used to support the former.
An experiment to improve operand addressing
Authors: Cook Robert P. , Donde Nitin
Published: November 2005

MCODE is a high-level language, stack machine designed to support strongly-typed, Pascal-based languages with a variety of data types in a modular programming environment. The instruction set, constructed for efficiency and extensibility, is based on an analysis of 120,000 lines of Pascal programs. The design was compared for efficiency with the instruction sets of the Digital Equipment PDP-11 and VAX by examining the generated code from the same compiler for all three machines. In addition, the original design choices were tested by analyzing the generated code from 19,000 lines of StarMod programs. As a result of this iterative experiment, we have summarized our observations in an efficient reorganization of the VAX's addressing modes.
A multi-microprocessor architecture with hardware support for communication and scheduling
Authors: Ahuja Sudhir R. , Asthana Abhaya
Published: November 2005

We describe a multiprocessor system that attempts to enhance the system performance by incorporating into its architecture a number of key operating system concepts. In particular:

— the scheduling and synchronization of concurrent activities are built in at the hardware level,

— the interprocess communication functions are performed in hardware, and,

— a coupling between the scheduling and communication functions is provided which allows efficient implementation of parallel systems that is precluded when the scheduling and communication functions are realized in software.
An interactive integrated system to design and use data bases
Authors: Albano Antonio , Orsini Renzo
Published: November 2005

Recent works on languages for modeling complex data base application environments show overlapping issues with other research areas such as Artificial Intelligence and Programming Languages. Moreover, a lot of attention is nowadays given to another important field, the overall data base design process, which, as it will be shown, furthermore extends the above connections.
Processing data model abstractions
Authors: Hardgrave W. Terry , Deutsch Donald R.
Published: November 2005

A number of data abstraction, database, and conceptual modeling issues border on the three technical areas that this workshop addresses: artificial intelligence, database management, and programming languages. We assume that the workshop is dedicated to removing the boundaries between these three fields in order to shape research and development of common interest. While enthusiastically supporting this objective, we believe that each area has a unique perspective and emphasis worth preserving. The three fields can truly benefit from each other only if each one appreciates the diversity of these research viewpoints. In this spirit we describe a research project on Abstract Data Models conducted by the Institute for Computer Sciences and Technology (ICST) of the National Bureau of Standards (NBS). Before doing so, however, we wish to discuss from our perspective both some problems that database management shares with the areas of artificial intelligence and programming languages, and some possible mathematical solutions to these problems.
Data dictionaries in open system communication
Authors: Hitchcock Peter
Published: November 2005

My current work is based on the premise that one should be able to access a foreign database system with the same ease that one can move from one type of telephone system to another. Data dictionaries must form the focal point in any architecture which would support such a concept. Data from a foreign system must be presented to the local system in such a way that the local system can understand it if the databases are disjoint, or merge the foreign conceptual model with the local one if the data bases have some common structure. Once such a rapport has been established, other aspects of the conceptual models, such as constraints and operations on the data, must be translated from one system to the other. This raises the following issues which I would like to see discussed at the workshop.
Associating types with domains of relational data bases
Authors: Lacroix Michel , Pirotte Alain
Published: November 2005

In the DB field, there are two
interpretations
(or perceptions or schools of thought)
concerning the relational model
:

(a) one interpretation considers that the relational model contribution to the DB field essentially consists in the presentation of a clear and simple notion of (flat) file, and that many users will be very satisfied to describe their data structures as tables;

(b) another interpretation considers the relational model as a (reasonable) support for a (weak) entity relationship model.
A perspective for research on conceptual modelling
Authors: Mylopoulos John
Published: November 2005

This position paper is intended to provide a perspective for research on conceptual modelling carried out over the past five years at the University of Toronto and to draw some conclusions from the experiences we have accumulated. “Conceptual modelling” here refers to the activity of constructing abstract models of knowledge about some world and is synonymous with the terms “knowledge representation” and “semantic data model” as they have been used in AI and Databases respectively. Much of the research on the subject has focused on the development of descriptive tools for the description of such models. Less attention has been paid, so far, on methodologies for building such models.
Database management systems past and present
Authors: Sibley E. H.
Published: November 2005

The theme of this note is on the two points:

1. Many of the ideas discussed in both data base and the other two areas were well known in the sixties—some go back to the fifties.

2.Too much attention was placed on trivia.
Data abstraction, data bases and conceptual modelling (Position Paper)
Authors: Thatcher J. W.
Published: November 2005

There is no paper with a mathematical foundation that I know of that strikes more at the heart of the subject of this Workshop than that of R.M. Burstall and J.A. Goguen [10], presented at the Fifth International Joint Conference on Artificial Intelligence in August of 1977.
Abstract specialization and its applications
Authors: Puebla Germán , Hermenegildo Manuel
Published: November 2005

The aim of program specialization is to optimize programs by exploiting certain knowledge about the context in which the program will execute. There exist many program manipulation techniques which allow specializing the program in different ways. Among them, one of the best known techniques is
partial evaluation
, often referred to simply as program specialization, which optimizes programs by specializing them for (partially) known input data. In this work we describe
abstract specialization
, a technique whose main features are: (1) specialization is performed with respect to "abstract" values rather than "concrete" ones, and (2)
abstract interpretation
rather than standard interpretation of the program is used in order to propagate information about execution states. The concept of abstract specialization is at the heart of the specialization system in CiaoPP, the Ciao system preprocessor. In this paper we present a unifying view of the different specialization techniques used in CiaoPP and discuss their potential applications by means of examples. The applications discussed include program parallelization, optimization of dynamic scheduling (concurrency), and integration of partial evaluation techniques.
Optimizing Ackermann's function by incrementalization
Authors: Liu Yanhong A. , Stoller Scott D.
Published: November 2005

This paper describes a formal derivation of an optimized Ackermann's function following a general and systematic method based on incrementalization. The method identifies an appropriate input increment operation and computes the function by repeatedly performing an incremental computation at the step of the increment. This eliminates repeated subcomputations in executions that follow the straightforward recursive definition of Ackermann's function, yielding an optimized program that is drastically faster and takes extremely little space. This case study uniquely shows the power and limitation of the incrementalization method, as well as both the iterative and recursive nature of computation underlying the optimized Ackermann's function.
User-controllable coherence for high performance shared memory multiprocessors
Authors: McCurdy Collin , Fischer Charles
Published: November 2005

In programming high performance applications, shared address-space platforms are preferable for fine-grained computation, while distributed address-space platforms are more suitable for coarse-grained computation. However, currently only distributed address-space systems scale beyond the low hundreds of processors. In this paper we introduce a hybrid architecture that allows users to trade off local memory usage for coherence communication, making possible larger-scale shared memory architectures. We introduce a programming model and examine possible implementations of hardware mechanisms, evaluating some of the trade-offs inherent in each. Preliminary experiments on an application with particularly fine-grained communication requirements indicate that effective placement of directives can reduce coherence communication by more than a factor of 10 for 64 processors.
Exploiting high-level coherence information to optimize distributed shared state
Authors: Chen DeQing , Tang Chunqiang , Sanders Brandon , Dwarkadas Sandhya , Scott Michael L.
Published: November 2005

InterWeave is a distributed middleware system that supports the sharing of strongly typed, pointer-rich data structures across a wide variety of hardware architectures, operating systems, and programming languages. As a complement to RPC/RMI, InterWeave facilitates the rapid development of maintainable code by allowing processes to access shared data using ordinary reads and writes.Internally, InterWeave employs a variety of aggressive optimizations to obtain significant performance improvements with minimal programmer effort. In this paper, we focus on
application-specific
optimizations that exploit dynamic high-level information about an application's spatial data access patterns and the stringency of its coherence requirements. Using applications drawn from computer vision, datamining, and web proxy caching, we illustrate the specification of coherence requirements based on the (temporal) concept of "recent enough" to use, and introduce two (spatial) notions of
view
s, which allow a program to limit coherence management to the portion of a data structure actively in use. Experiments with these applications show that InterWeave can reduce their communication traffic by up to one order of magnitude with minimum effort on the part of the application programmer.
Phoenix
Authors: Taura Kenjiro , Kaneda Kenji , Endo Toshio , Yonezawa Akinori
Published: November 2005

This paper proposes Phoenix, a programming model for writing parallel and distributed applications that accommodate dynamically joining/leaving compute resources. In the proposed model, nodes involved in an application see a large and fixed
virtual node name space
. They communicate via messages, whose destinations are specified by virtual node names, rather than names bound to a physical resource. We describe Phoenix API and show how it allows a transparent migration of application states, as well as dynamically joining/leaving nodes as its by-product. We also demonstrate through several application studies that Phoenix model is close enough to regular message passing, thus it is a general programming model that facilitates porting many parallel applications/algorithms to more dynamic environments. Experimental results indicate applications that have a small task migration cost can quickly take advantage of dynamically joining resources using Phoenix. Divide-and-conq! uer algorithms written in Phoenix achieved a good speedup with a large number of nodes across multiple LANs (120 times speedup using 169 CPUs across three LANs). We believe Phoenix provides a useful programming abstraction and platform for emerging parallel applications that must be deployed across multiple LANs and/or shared clusters having dynamically varying resource conditions.
Routine run-time code generation
Authors: Kamin Sam
Published: November 2005

Run-time code generation (RTCG) would be used routinely if application programmers had a facility with which they could easily create their own run-time code generators, because it would offer benefits both in terms of the efficiency of the code that programmers would produce and the ease of producing it. Such a facility would necessarily have the following properties: it would not require that programmers know assembly language; programmers would have full control over the generated code; the code generator would operate entirely at the binary level. In this paper, we offer arguments and examples supporting these assertions. We briefly describe Jumbo, a system we have built for producing run-time code generators for Java..
Acceptability-oriented computing
Authors: Rinard Martin
Published: November 2005

We discuss a new approach to the construction of software systems. Instead of attempting to build a system that is as free of errors as possible, the designer instead identifies key properties that the execution must satisfy to be acceptable to its users. Together, these properties define the
acceptability envelope
of the system: the region that it must stay within to remain acceptable. The developer then augments the system with a layered set of components, each of which enforces one of the acceptability properties. The potential advantages of this approach include more flexible, resilient systems that recover from errors and behave acceptably across a wide range of operating environments, an appropriately prioritized investment of engineering resources, and the ability to productively incorporate unreliable components into the final software system.