bluuebunny/crossref_metadata_2025 huggingface dataset:
Large-scale parallel programming: experience with BBN butterfly parallel processor
Authors: LeBlanc Thomas J. , Scott Michael L. , Brown Christopher M.
Published: November 2005

For three years, members of the Computer Science Department at the University of Rochester have used a collection of BBN Butterfly™ Parallel Processors to conduct research in parallel systems and applications. For most of that time, Rochester's 128-node machine has had the distinction of being the largest shared-memory multiprocessor in the world. In the course of our work with the Butterfly we have ported three compilers, developed five major and several minor library packages, built two different operating systems, and implemented dozens of applications. Our experience clearly demonstrates the practicality of large-scale shared-memory multiprocessors, with non-uniform memory access times. It also demonstrates that the problems inherent in programming such machines are far from adequately solved. Both locality and Amdahl's law become increasingly important with a very large number of nodes. The availability of multiple programming models is also a concern; truly general-purpose parallel computing will require the development of environments that allow programs written under different models to coexist and interact. Most important, there is a continuing need for high-quality programming tools; widespread acceptance of parallel machines will require the development of programming environments comparable to those available on sequential computers.
World-class product certification using Erlang
Authors: Wiger Ulf , Ask Gösta , Boortz Kent
Published: November 2005

It is now ten years ago since the decision was made to apply the functional programming language Erlang to real production projects at Ericsson. In late 1995, development on the Open Telecom Platform (OTP) started, and in mid 1996 the AXD 301 project became the first user of OTP. The AXD 301 Multi-service Switch was released in October 1998, and later became "the heart of ENGINE", Ericsson's leading Voice over Packet solution.In those early days of Erlang programming, high-level tools for development and testing were not really available, and programmers used mainly the Emacs editor and the Erlang shell. Still, anecdotal evidence suggested a 4-10x productivity increase compared to mainstream programming techniques.Through the years, significant progress has been made, especially in the area of automated testing of Erlang programs. The OTP team designed an Erlang-based test suite execution environment, were developers can easily write their own automated test suites, and now performs nightly builds where more than one thousand test cases are executed on ten different platforms. OTP designers can view the outcome in web-based test reports as they come to work the next day. Each corrected bug results in a new test case that is incorporated into the ever-growing test suite. Thus, this world-class middleware is certified to telecom-class quality without a dedicated test team!The AXD 301 project uses OTP's test environment, and executes more than 10,000 automated test cases before each major release. Designers and testers compose their own test suites, and the designers carry out function tests with little or no help from the Integration and Certification team. Each test case can be run both in a simulated environment on the designer's workstation and in the test lab on real hardware. In order to provide stimuli to the system, the testers often design their own traffic generators in Erlang.To analyze the faults that occur, Erlang offers an increasing wealth of debugging options. Beyond the symbolic error messages, which are often sufficient to locate the fault, Erlang developers are able to dynamically turn on tracing on message passing, scheduling events, garbage collections, selected function calls, etc.This paper demonstrates how Erlang's declarative syntax and pattern matching provide an outstanding environment for test suite development.
Template meta-programming for Haskell
Authors: Sheard Tim , Jones Simon Peyton
Published: November 2005

We propose a new extension to the purely functional programming language Haskell that supports
compile-time meta-programming
. The purpose of the system is to support the
algorithmic
construction of programs at compile-time.The ability to generate code at compile time allows the programmer to implement such features as polytypic programs, macro-like expansion, user directed optimization (such as inlining), and the generation of supporting data structures and functions from existing data structures and functions.Our design is being implemented in the Glasgow Haskell Compiler, ghc.
A rule-based language for programming software updates
Authors: Erwig Martin , Ren Delin
Published: November 2005

We describe the design of a rule-based language for expressing changes to Haskell programs in a systematic and reliable way. The update language essentially offers update commands for all constructs of the object language (a subset of Haskell). The update language can be translated into a core calculus consisting of a small set of basic updates and update combinators. The key construct of the core calculus is a scope update mechanism that allows (and enforces) update specifications for the definition of a symbol together with all of its uses.The type of an update program is given by the possible type changes it can cause for an object programs. We have developed a type-change inference system to automatically infer type changes for up-dates. Updates for which a type change can be successfully inferred and that satisfy an additional structural condition can be shown to preserve type correctness of object programs.In this paper we define the Haskell Update Language HULA and give a translation into the core update calculus. We illustrate HULA and its translation into the core calculus by several examples.
The essence of XML
Authors: Siméon Jérôme , Wadler Philip
Published: November 2005

The World-Wide Web Consortium (W3C) promotes XML and related standards, including XML Schema, XQuery, and XPath. This paper describes a formalization of XML Schema. A formal semantics based on these ideas is part of the official XQuery and XPath specification, one of the first uses of formal methods by a standards body. XML Schema features both named and structural types, with structure based on tree grammars. While structural types and matching have been studied in other work (notably XDuce, Relax NG, and a previous formalization of XML Schema), this is the first work to study the relation between named types and structural types, and the relation between matching and validation.
A generic approach to the static analysis of concurrent programs with procedures
Authors: Bouajjani Ahmed , Esparza Javier , Touili Tayssir
Published: November 2005

We present a generic aproach to the static analysis of concurrent programs with procedures. We model programs as communicating pushdown systems. It is known that typical dataflow problems for this model are undecidable, because the emptiness problem for the intersection of context-free languages, which is undecidable, can be reduced to them. In this paper we propose an algebraic framework for defining abstractions (upper approximations) of context-free languages. We consider two classes of abstractions: finite-chain abstractions, which are abstractions whose domains do not contain any infinite chains, and commutative abstractions corresponding to classes of languages that contain a word if and only if they contain all its permutations. We show how to compute such approximations by combining automata theoretic techniques with algorithms for solving systems of polynomial inequations in Kleene algebras.
New results on the computability and complexity of points--to analysis
Authors: Chakaravarthy Venkatesan T.
Published: November 2005

Given a program and two variables
p
and
q
, the goal of points-to analysis is to check if
p
can point to
q
in some execution of the program. This well-studied problem plays a crucial role in compiler optimization. The problem is known to be undecidable when dynamic memory is allowed. But the result is known only when variables are allowed to be structures. We extend the result to show that, the problem remains undecidable, even when only scalar variables are allowed. Our second result deals with a version of points-to analysis called flow-insensitive analysis, where one ignores the control flow of the program and assumes that the statements can be executed in any order. The problem is known to be NP-Hard, even when dynamic memory is not allowed and variables are scalar. We show that when the variables are further restricted to have well-defined data types, the problem is in P. The corresponding flow-sensitive version, even with further restrictions, is known to be PSPACE-Complete. Thus, our result gives some theoretical evidence that flow-insensitive analysis is easier than flow-sensitive analysis. Moreover, while most variations of the points-to analysis are known to be computationally hard, our result gives a rare instance of a non-trivial points-to problem solvable in polynomial time.
From control effects to typed continuation passing
Authors: Thielecke Hayo
Published: November 2005

First-class continuations are a powerful computational effect, allowing the programmer to express any form of jumping. Types and effect systems can be used to reason about continuations, both in the source language and in the target language of the continuation-passing transform. In this paper, we establish the connection between an effect system for first-class continuations and typed versions of continuation-passing style. A region in the effect system determines a local answer type for continuations, such that the continuation transforms of pure expressions are parametrically polymorphic in their answer types. We use this polymorphism to derive transforms that make use of effect information, in particular, a mixed linear/non-linear continuation-passing transform, in which expressions without control effects are passed their continuations linearly.
A type theory for memory allocation and data layout
Authors: Petersen Leaf , Harper Robert , Crary Karl , Pfenning Frank
Published: November 2005

Ordered type theory is an extension of linear type theory in which variables in the context may be neither dropped nor re-ordered. This restriction gives rise to a natural notion of
adjacency
. We show that a language based on ordered types can use this property to give an exact account of the layout of data in memory. The fuse constructor from ordered logic describes adjacency of values in memory, and the mobility modal describes pointers into the heap. We choose a particular allocation model based on a common implementation scheme for copying garbage collection and show how this permits us to separate out the allocation and initialization of memory locations in such a way as to account for optimizations such as the coalescing of multiple calls to the allocator.
Static prediction of heap space usage for first-order functional programs
Authors: Hofmann Martin , Jost Steffen
Published: November 2005

We show how to efficiently obtain linear a priori bounds on the heap space consumption of first-order functional programs.The analysis takes space reuse by explicit deallocation into account and also furnishes an upper bound on the heap usage in the presence of garbage collection. It covers a wide variety of examples including, for instance, the familiar sorting algorithms for lists, including quicksort.The analysis relies on a type system with resource annotations. Linear programming (LP) is used to automatically infer derivations in this enriched type system.We also show that integral solutions to the linear programs derived correspond to programs that can be evaluated without any operating system support for memory management. The particular integer linear programs arising in this way are shown to be feasibly solvable under mild assumptions.
Type-safe multithreading in cyclone
Authors: Grossman Dan
Published: November 2005

We extend Cyclone, a type-safe polymorphic language at the C level of abstraction, with threads and locks. Data races can violate type safety in Cyclone. An extended type system statically guarantees their absence by enforcing that thread-shared data is protected via locking and that thread-local data does not escape the thread that creates it. The extensions interact smoothly with parametric polymorphism and region-based memory management. We present a formal abstract machine that models the need to prevent races, a polymorphic type system for the machine that supports thread-local data, and a corresponding type-safety result.
An integrated toolset for engineering software configurations
Authors: Mahler Axel , Lampen Andreas
Published: November 2005

Configuration management in toolkit oriented software development environments (SDE), such as the UNIX system, is a long standing nuisance. Mostly, one has to face the choice between poorly or not at all integrated, independent tools, or highly integrated, most specialized, and often language dependent environments. The first choice offers very limited support for a complex task that needs a broad informational basis. The second choice often takes away the programmers' most cherished tools, forces him to adopt some different work discipline, and thereby eventually restricts his creativity. The toolset described in this paper integrates a dedicated version control system and shape, a significantly enhanced Make [Feld79a] program, on the basis of a common object model. This object model comprises multiple versions of software objects as well as conventional file system objects. Taking this approach made it possible to have a sufficiently integrated toolsystem for engineering software configurations while retaining the flexibility of the basic toolbox philosophy, permitting the use of 'off-the-shelf' tools, e.g. editors or compilers.
A software development environment for law-governed systems
Authors: Minsky Naftaly H. , Rozenshtein David
Published: November 2005

This paper describes a software development environment based on a new approach for managing large-scale evolving systems. Under this approach, the conventional notion of a
system
is augmented with a new component called the
law of the system
, which is an
explicit
and
strictly enforced
set of rules about the operation of the system, about its evolution, and about the evolution of the law itself. The resulting combination is called a
law-governed system.
A plan-based intelligent assistant that supports the software development
Authors: Huff Karen E. , Lesser Victor R.
Published: November 2005

We describe how an environment can be extended to support the
process
of software development. Our approach is based on the AI
planning
paradigm. Processes are formally defined hierarchically via plan operators, using multiple levels of abstraction.
Plans
are constructed dynamically from the operators; the sequences of actions in plans are tailored to the context of their use, and conflicts among actions are prevented. Monitoring of the development process, to detect and avert process errors, is accomplished by
plan recognition
; this establishes a context in which programmer-selected goals can be automated via
plan generation
. We also show how
nonmonotonic reasoning
can be used to make an independent assessment of the
credibility
of complex process alternatives, and yet accede to the programmer's superior judgment. This extension to intelligent assistance provides deeper understanding of software processes.
An overview of DOD-STD-1838A (proposed) the common APSE interface set: revision
Authors: Munck Robert , Oberndorf Patricia , Ploedereder Erhard , Thall Richard
Published: November 2005

A five-year effort under the Ada Joint Program Office has developed a proposed standard for a host system interface as seen by tools running in an Ada Programming Support Environment (APSE). Standardization of this interface as DOD-STD-1838A will have a number of desirable effects for the Department of Defense, including tool portability, tool integration, data transportability, encouragement of a market in portable tools, and better programmer productivity.

As the capability of tools to communicate with each other is a central requirement in APSEs, the Common APSE Interface Set (CAIS) has paid particular attention to facilitate such communication in a host-independent fashion. CAIS incorporates a well-integrated set of concepts tuned to the needs of writers and users of integrated tool sets.

This paper covers several of these concepts:

• the entity management system used in place of a traditional filing system,

• object typing with inheritance,

• process control including atomic transactions,

• access control and security,

• input/output methods,

• support for distributed resource control, and

• facilities for inter-system data transport.
Using spreadsheet software to support metric's life cycle activities
Authors: Kokol P.
Published: November 2005

The application of the spreadsheet software in the field of software measurement technology is disccussed. A model of metric's life cycle is defined and used together with the spreadsheet software to develop a new class of complexity metrics, called Hybrid metrics. Theirs evaluation has shown that they are supperior to most other complexity metrics in estimating development times and allocating testing resources. Finally, the spreadsheet and conventional programming are compared, and it is not unreasonable to state that spreadsheet better supports activities performd during metric's life cycle then conventional programming.
A language-based design for portable data files
Authors: Burch C.
Published: November 2005

Currently data files to be accessed remotely from dissimilar systems must be transformed to the local language processors' file format and data representation; a process that has changed little since punch cards were the main form of portable data files. A standard is proposed for languages to use the data type information available to the runtime library to make these data transformations before the data is transferred to the file or the user's variables. By specifying one binary format for each basic data type (integer, real, logical, etc) and a file organization that is portable between record-oriented and stream-oriented file systems, we can standardize file formats that will be usable on practically all current systems.
Joyce: an object-oriented decision tree builder
Authors: Marcus B.
Published: November 2005

Joyce is an object-oriented visual programming environment for nonprogrammers. It permits an application developer to assemble a program by graphically choosing methods from a large library and linking them together using predefined control structures. Joyce also provides the developer with the ability to define data structures, interactive forms, and documentation without programming.
Design of a distributed implementation of ABCL/I
Authors: Briot J.-P. , de Ratuld J.
Published: November 2005

In this paper we describe the design decisions leading to a distributed implementation of the ABCL language. We shortly review the ABCL (Actor Based Concurrent Language) computation model. We discuss some slight changes we bring to the current ABCL/1 language in order to distribute objects among several machines. Identification, reference, allocation and communication are the four concepts which need some evolution. The status of a first prototype implementation on a network of workstations (Lisp/Suns+Ethernet) is reported.
A'UM
= Stream + Object + Relation
Authors: Yoshiba K. , Chikayama T.
Published: November 2005

In this paper, we introduce a concurrent programming language
A'UM
[Yoshida88], which has been designed aiming at high parallelism and high expressivity for the development of large scale software.
A'UM
is characterized by three features: stream-based computation, object-oriented abstraction and relational representation.
PROCOL: a protocol-constrained concurrent object-oriented language
Authors: van den Bos J.
Published: November 2005

PROCOL is a simple concurrent object-oriented language supporting a distributed, incremental and dynamic object environment. Its communication is based on unidirectional messages. Objects are only bound during actual message transfer and not during the processing of the message. This short duration object binding promotes parallelism. The communication leading to access has to obey an explicit protocol in each object. It takes the form of a specification of the occurrence and sequencing of the interaction between the object and its communication partners. The use of such protocols fosters structured, safer and potentially verifiable communication between objects.
Elint in Lamina: application of a concurrent object language
Authors: Delagi B. A. , Saraiya N. P.
Published: November 2005

The design and performance of an "expert system" signal interpretion application written in a concurrent object-based programming language, LAMINA, is described together with a synopsis of the programming model that forms the foundation of the language. The effects of load balancing and the limits imposed by task granularity and message transmission costs are studied and their consequences to application performance are measured over the range of one to 250 processors as simulated in SIMPLE/CARE, an extensively instrumented simulation system and computer array model.
XE design rationale: Clu revisited
Authors: Hirvisalo V. , Arkko J. , Kuusela J. , Nuutila E. , Tamminen M.
Published: November 2005

XE is a programming language designed and implemented at the Helsinki University of Technology by the ExBed project. The design of XE is based on the CLU programming language. This paper discusses differences between the two languages and the design decisions of XE.
Implementing a graph-colouring algorithm in Parlog
Authors: Huntbach M.
Published: November 2005

In this paper we give a Parlog program for a parallel algorithm for the graph-colouring problem. Although the algorithm as originally given refers to a specific architecture, it translates with ease into Parlog. Since the parallelism in Parlog is virtual, the same program may be used on any architecture on which Parlog is implemented.
Transformational programming: the derivation of a Prolog interpretation algorithm
Authors: Zhu M. Y.
Published: November 2005

In this paper we will present a case study for the transformational programming technique. The problem we intend to study is the construction of an interpreter for the logic programming language Prolog. We will start from a formal algebraic semantic definition of Prolog, through a series of transformations, step by step, reach a compact and efficient implementation written in programming language Ada. The whole development process are carried out with the support of a software development system called AUTO STAR (AUTOmatic Specification To Ada Realization).
Experience with topaz telebugging
Authors: Redell David D.
Published: November 2005

The Topaz TeleDebug (TTD) facility provides a remote debugging capability supporting software development in the Topaz environment. Topaz is a software environment providing rich support for programming in Modula2+, and extended version of Modula 2. TTD allows uniform use of the same high level source language debugger for all debugging (both local and remote) of software at all levels of the system. Special care has been taken to maximize TTD's reliability and robustness. Our experience suggests that such a facility can be extremely useful, very dependable and quite inexpensive. It also suggests that the implementation issues can be somewhat subtle, and that correct choices in this area are vital if the promise of such a scheme is to be fully realized. This paper focuses on those implementation issues in a fair amount of detail, analyzing the limitations of our first TTD implementation and the redesign that produced a second, improved version. Our main conclusion is that the target (debuggee) end of such a facility should be implemented at the lowest possible level in the operating system, and that a uniformly applicable remote invocation (e.g. remote procedure call) facility is key to enabling this approach. We also conclude that strict adherence to layered information hiding can lead to serious difficulties in the implementation of a remote debugging protocol.

The discussion should be of particular interest to others designers of remote debugging facilities. While the paper does not devote much attention to higher level issues (e.g. novel user interfaces for debugging concurrent or distributed programs) most of the ideas discussed should be applicable to a wide class of debuggers, including those with higher aspirations for debugging such programs.
IGOR: a system for program debugging via reversible execution
Authors: Feldman Stuart I. , Brown Channing B.
Published: November 2005

Typical debugging tools are insufficiently powerful to find the most difficult types of program misbehaviors. We have implemented a prototype of a new debugging system, IGOR, which provides a great deal more useful information and offers new abilities that are quite promising. The system runs fast enough to be quite useful while providing many features that are usually available only in an interpreted environment. We describe here some improved facilities (reverse execution, selective searching of execution history, substitution of data and executable parts of the programs) that are needed for serious debugging and are not found in traditional single-thread debugging tools. With a little help from the operating system, we provide these capabilities at reasonable cost without modifying the executable code and running fairly close to full speed. The prototype runs under the DUNE distributed operating system.

The current system only supports debugging of single-thread programs. The paper describes planned extensions to make use of extra processors to speed the system and for applying the technique to multi-thread and time dependent executions.
A mechanism for efficient debugging of parallel programs
Authors: Miller Barton P. , Choi Jong-Deok
Published: November 2005

This paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (SMMP). We describe the use of
flowback analysis
to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. We introduce a mechanism called
incremental tracing
that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. We extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co-operating processes.
High-level debugging in parasight
Authors: Aral Ziya , Gertner Ilya
Published: November 2005

Debugging parallel programs with time critical dependencies is difficult due to subtle race conditions that may cause deadlock, starvation, and other errors. These errors can be detected by multiple instrumentation points triggered by logical assertions. Although some advanced debuggers provide a programmer with the ability to define complex logical assertions, they are inadequate for debugging parallel programs due to the high overhead of monitoring these assertions.

This paper describes the facilities for high-level debugging in Parasight™ a parallel programming environment. In Parasight, high-level debugging facilities are implemented as separate programs that are linked dynamically to a target program. The target program is controlled by attaching these debugging programs to light-weight instrumentation points that are dynamically inserted and deleted. Different facilities of arbitrary complexity may be created to support high-level debugging. Parasight has been implemented on Multimax™ a shared-memory multiprocessor. It has been used for debugging and profiling “C” programs.
Initial experiences with a pattern-oriented parallel debugger
Authors: Hough Alfred A. , Cuny Janice E.
Published: November 2005

Highly parallel programs are often best understood in terms of logical patterns of inter process communication. In order to debug such programs, the user must determine the extent to which the intended patterns occur during execution. To facilitate this, we have designed and implemented a pattern-oriented debugger in which abstract, user-defined communication events can be described and animated. We report here on our initial experiences with its use.
Voyeur: graphical views of parallel programs
Authors: Socha David , Bailey Mary L. , Notkin David
Published: November 2005

Voyeur is a prototype system that facilitates the construction of application-specific, visual views of parallel programs. These views range from textual views showing the contents of variables to graphical maps of the state of the computational domain of the program. These views have been instrumental in quickly detecting bugs that would have been difficult to detect otherwise.
A graphical representation of concurrent processes
Authors: Stone Janice M.
Published: November 2005

This paper describes a graphical representation called a
concurrency map
. It provides a succinct representation of the potentially large collection of possible correct event-orderings for a set of concurrent processes.

The normal problems of monitoring, debugging and analyzing performance of single-process programs are compounded for programs with concurrent processes. Although we can observe the behavior of each separate process, we do not know what is occurring concurrently in the various processes during successive moments as execution progresses. Furthermore, unknown timing delays among the processes may cause different program behavior when we rerun the program. The relative time-ordering of events in different concurrent processes is not, in general, fixed, and events that occurred in one order on one occasion on which the program performed correctly might occur in another order on another occasion, with equal correctness. We need to know both how the program behaved during execution and how that behavior might have differed under normal variations of concurrent execution. The concurrency map aids in solving these problems.
Concurrent algorithmic debugging
Authors: Lichtenstein Yossi , Shapiro Ehud
Published: November 2005

Algorithmic Debugging is a theory of debugging that uses queries on the compositional semantics of a program in order to localize bugs. It uses the following principle: if a computation of a program's component gives an incorrect result, while all the subcomputations it invokes compute correct results, then the code of this component is erroneous.

Algorithmic Debugging is applied, in this work, to reactive systems, in particular to programs written in Flat Concurrent Prolog (FCP). Debugging reactive systems is known to be more difficult than the debugging of functional systems. A functional system is fully described by the relation between its initial input and final output; this context-freedom is used in debugging. A reactive system continuously responds to external inputs, thus its debugging cannot make use of context-free input/output relations.

Given a compositional semantic model for a concurrent programming language, we demonstrate how one can directly apply the ideas of Algorithmic Debugging to obtain a theory of program debugging for the considered language. The conflict between the context-freedom of input/ output relations and the reactive nature of concurrent systems is resolved by using semantic objects which record the reactive nature of the system's components. In functional algorithmic debugging the queries relate to input/output relations; in concurrent algorithmic debugging the queries refer to semantic objects called
processes
which capture the reactive nature of FCP computations.

A diagnosis algorithm for incorrect FCP programs is proposed. The algorithm gets an erroneous computation and using queries isolates an erroneous clause or an incomplete procedure. An FCP implementation of the diagnosis algorithm demonstrates the usefulness as well as the difficulties of Algorithmic Debugging of FCP programs.
Rated and operating complexity of program—an extension to McCabe's theory of complexity measure
Authors: Sagri M. M.
Published: November 2005

Program complexity measure is arrived at using graph- theoretic method giving a cyclomatic number. However it has been found that programs with same cyclomatic number do not have same complexity. A simple extension to the measure is described in this paper to arrive at a better understanding of complexity. The program's complexity is divided into rated & operating complexity.
Software metrics: using measurement theory to describe the properties and scales of static software complexity metrics
Authors: Zuse H. , Bollmann P.
Published: November 2005

Over the last decade many software metrics have been introduced by researchers and many software tools have been developed using software metrics to measure the "quality" of programs. These metrics for measuring productivity, reliability, maintainability, and complexity, for example, are vital to software development planning and management. In this paper a new approach is presented to describe the properties of the software metrics and their scales using measurement theory. Methods are shown to describe a software complexity metric as an ordinal, an interval or a ratio scale. The use of this concept is shown by application to the Metric of McCabe. These results are very important for selecting appropriate software metrics for software measurement and for developing tools which use software metrics to evaluate the "quality" of software.
Definition of the DISC concurrent language
Authors: Iannello G. , Mazzeo A. , Ventre G.
Published: November 2005

Although commercial distributed computers are now available, developing software for these systems is still a hard task. This prevents the users from getting full advantage out of the use of distributed computers. Among the techiniques proposed to make it easier to program the new architectures,
concurrent languages
have proved to be an effective approach both in system programming and in application development.The concurrent programming language DISC has been designed to promote software engineering techniques in the development of distributed programs. The language extends C with CSP-based concurrent mechanisms and it is especially suited for system programming of loosely coupled distributed architectures. A simple programming environment, running under UNIX System V operating system, allows the user to develop programs in a modular fashion. A first implementation of DISC has been developed on a network of UNIX machines. DISC programs are portable on a wide class of distributed computers, because of both the choice of UNIX as the host environment and the substantial independence of the language run time support from the hardware.In this article we report the definition of DISC and an example to show informally the practical use of the language.
The syntax definition formalism SDF—reference manual—
Authors: Heering J. , Hendriks P. R. H. , Klint P. , Rekers J.
Published: November 2005

SDF is a formalism for the definition of syntax which is comparable to BNF in some respects, but has a wider scope in that it also covers the definition of lexical and abstract syntax. Its design and implementation are tailored towards the language designer who wants to develop new languages as well as implement existing ones in a highly interactive manner. It emphasizes compactness of syntax definitions by offering (a) a standard interface between lexical and context-free syntax; (b) a standard correspondence between context-free and abstract syntax; (c) powerful disambiguation and list constructs; and (d) an efficient incremental implementation which accepts arbitrary context-free syntax definitions. SDF can be combined with a variety of programming and specification languages. In this way these obtain fully general user-definable syntax.
The design of very fast portable compilers
Authors: Tanenbaum A. S. , Kaashoek M. F. , Langendoen K. G. , Jacobs C. J. H.
Published: November 2005

The Amsterdam Compiler Kit is a widely used compiler building system. Up until now, the emphasis has been on producing good object code. In this paper we describe recent work that has focused on reducing compile time. The techniques described in this paper have resulted in C compilers for the Sun-3 and VAX that are 3 to 4 times faster than the native compilers provided by the manufacturers.
A framework for construction and evaluation of high-level specifications for program analysis techniques
Authors: Venkatesh G. A.
Published: November 2005

Abstract interpretation
introduced the notion of formal specification of program analyses. Denotational frameworks are convenient for reasoning about such specifications. However, implementation considerations make denotational specifications complex and hard to develop. We present a framework that facilitates the construction and understanding of denotational specifications for program analysis techniques. The framework is exemplified by specifications for program analysis techniques from the literature and from our own research. This approach allows program analysis techniques to be incorporated into automatically generated program synthesizers by including their specifications with the language definition.
Mul-T: a high-performance parallel Lisp
Authors: Kranz D. A. , Halstead R. H. , Mohr E.
Published: November 2005

Mul-T is a parallel Lisp system, based on Multilisp's future construct, that has been developed to run on an Encore Multimax multiprocessor. Mul-T is an extended version of the Yale T system and uses the T system's ORBIT compiler to achieve “production quality” performance on stock hardware — about 100 times faster than Multilisp. Mul-T shows that futures can be implemented cheaply enough to be useful in a production-quality system. Mul-T is fully operational, including a user interface that supports managing groups of parallel tasks.
A fresh look at combinator graph reduction
Authors: Koopman P. J. , Lee P.
Published: November 2005

We present a new abstract machine for graph reduction called TIGRE. Benchmark results show that TIGRE's execution speed compares quite favorably with previous combinator-graph reduction techniques on similar hardware. Furthermore, the mapping of TIGRE onto conventional hardware is simple and efficient. Mainframe implementations of TIGRE provide performance levels exceeding those previously available on custom graph reduction hardware.
Higher order attribute grammars
Authors: Vogt H. H. , Swierstra S. D. , Kuiper M. F.
Published: November 2005

A new kind of attribute grammars, called higher order attribute grammars, is defined. In higher order attribute grammars the structure tree can be expanded as a result of attribute computation. A structure tree may be stored in an attribute. The term higher order is used because of the analogy with higher order functions, where a function can be the result or parameter of another function. A relatively simple method, using OAGs, is described to derive an evaluation order on the defining attribute occurrences which comprises all possible direct and indirect attribute dependencies. As in OAGs, visit-sequences are computed from which an efficient algorithm for attribute evaluation can be derived.
Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language
Authors: Chambers C. , Ungar D.
Published: November 2005

Dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. Our new implementation techniques extract static type information from declaration-free programs. Our system compiles several copies of a given procedure, each
customized
for one receiver type, so that the type of the receiver is bound at compile time. The compiler
predicts
types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. It
splits
calls, compiling a copy on each control path, optimized to the specific types on that path. Coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages.
Determining average program execution times and their variance
Authors: Sarkar V.
Published: November 2005

This paper presents a general framework for determining average program execution times and their variance, based on the program's interval structure and control dependence graph. Average execution times and variance values are computed using frequency information from an optimized counter-based execution profile of the program.
Generational reference counting: a reduced-communication distributed storage reclamation scheme
Authors: Goldberg B.
Published: November 2005

This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. Although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive.

The communication overhead for generational reference counting is one message for each copy of an interprocessor reference (pointer). Unlike conventional reference counting, when a reference to an object is copied no message is sent to the processor on which the object lies. A message is sent only when a reference is discarded. Unfortunately, generational reference counting shares conventional reference counting's inability to reclaim cyclical structures.

In this paper, we present the generational reference counting algorithm, prove it correct, and discuss some refinements that make it more efficient. We also compare it with weighted reference counting, another distributed reference counting scheme described in the literature.
Contributions to teaching object-oriented design and programming
Authors: Lieberherr K. J. , Riel A. J.
Published: November 2005

We provide a formal agenda for teaching the object-oriented paradigm in a programming language independent manner, and a tool which supports our teaching approach. Our proposal for a comprehensive study of the subject includes an ordered set of objectives designed to guide the uninitiated user from zero knowledge about object-oriented programming through class definitions, inheritance, subtyping, and the parameterization of classes. This set of graded objectives provides both a useful metric for gauging a student's progress, and a facility through which users can begin their studies at a level commensurate with their experience.
Design of the opportunistic garbage collector
Authors: Wilson P. R. , Moher T. G.
Published: November 2005

The Opportunistic Garbage Collector (OGC) is a generational garbage collector for stock hardware and operating systems. While incorporating important features of previous systems, the OGC includes several innovations. A new
bucket brigade
heap organization supports advancement thresholds between one and two scavenges, using only two or three spaces per generation, and without requiring per-object counts.
Opportunistic
scavenging decouples scavenging from the filling of available memory, in order to hide potentially disruptive scavenge pauses and improve efficiency.
Card marking
efficiently records which small areas of the heap may contain pointers into younger generations, and is supported by a refinement of the
crossing map
technique, to enable scanning of arbitrary cards.
Object-oriented design: a responsibility-driven approach
Authors: Wirfs-Brock R. , Wilkerson B.
Published: November 2005

Object-oriented programming languages support encapsulation, thereby improving the ability of software to be reused, refined, tested, maintained, and extended. The full benefit of this support can only be realized if encapsulation is maximized during the design process.

We argue that design practices which take a data-driven approach fail to maximize encapsulation because they focus too quickly on the implementation of objects. We propose an alternative object-oriented design method which takes a responsibility-driven approach. We show how such an approach can increase the encapsulation by deferring implementation issues until a later stage.
Mandatory security in object-oriented database systems
Authors: Thuraisingham M. B.
Published: November 2005

A multilevel secure object-oriented data model (using the ORION data model) is proposed for which mandatory security issues in the context of a database system is discussed. In particular the following issues are dealt with: (1) the security policy for the system, (2) handling polyinstantiation, and (3) handling the inference problem.

A set of security properties that has been established in this paper is more complete than those that have been proposed previously. Finally we describe how certain security constraints are handled by our model.
The use of multimethods and method combination in a CLOS based window interface
Authors: Muller H. , Rose J. , Kempf J. , Stansbury T.
Published: November 2005

Solo is a portable window interface written in the Common Lisp Object System (CLOS) object-oriented programming language. Solo provides a virtual window machine which is targeted to a host window system by implementing a set of host window system specific classes and methods for Solo's host window system driver protocol. The interface presented by Solo to an application insulates it from differences in the host window system, facilitating application portability. Solo distinguishes itself from other object-oriented window systems by exploiting certain features of CLOS. CLOS method combination simplifies initialization of windows while preserving easy extensibility of the basic classes. Generic dispatch on multiple arguments, a feature unique to CLOS, allows a simpler and more flexible input event dispatching protocol. A powerful event description language simplifies the specification of keyboard and mouse events. A prototype implementation runs on the server based XII and NeWS host systems, and on the frame buffer based Lucid Window Toolkit.
OROS: toward a type model for software development environments
Authors: Rosenblatt W. R. , Wileden J. C. , Wolf Alexander L.
Published: November 2005

Three important goals of next generation software development environments (SDEs) are extensibility, integration and broad scope. Our work on OROS is predicated on the hypothesis that a type model, incorporated into an environment's object manager, can contribute to achieving those goals. This paper reports on an attempt at applying object-oriented typing concepts in the domain of software development environments. We believe that the result is a type model that has properties of interest both to software environment builders and also to builders and users of object-oriented systems in general.