bluuebunny/crossref_metadata_2025_split huggingface dataset:
Programming-in-the large versus programming-in-the-small
Authors: DeRemer Frank , Kron Hans 
Published: November 2005

We distinguish the activity of writing large programs from that of writing small ones. By large programs we mean systems consisting of many small programs (modules), possibly written by different people.
We need languages for programming-in-the-small, i.e. languages not unlike the common programming languages of today, for writing modules. We also need a “module interconnection language” for knitting those modules together into an integrated whole and for providing an overview that formally records the intent of the programmer(s) and that can be checked for consistency by a compiler.
We explore the software reliability aspects of such an interconnection language. Emphasis is placed on facilities for information hiding and for defining layers of virtual machines.
Towards automatic debugging of programs
Authors: Katz Shmuel , Manna Zohar 
Published: November 2005

We present the germ of an idea for automatically correcting logical errors in programs by manipulating the invariants of the program. An invariant tree is defined, and we show how it can be used to change the program in order to guarantee correctness.
Debugging could be incorporated into a verification system which would first try to prove the correctness of the program. If the attempt is unsuccessful, two alternative approaches are suggested and compared. In the first, we try directly to correct the invariants and - through these - the statements, taking the calculated risk of modifying an already correct program. In the second approach, we initially prove incorrectness, and only then try to correct the program, by invalidating this proof.
On attaining reliable software for a secure operating system
Authors: Robinson Lawrence , Levitt Karl N. , Neumann Peter G. , Saxena Ashok R. 
Published: November 2005

This paper presents a general methodology for the design, implementation, and proof of large software systems, each described as a hierarchy of abstract machines. The design and implementation occur in five stages as described in this paper. Formal proof may take place at each stage. We expect the methodology to simplify the proof effort in such a way as to make proof a feasible tool in the development of reliable software. In addition to the anticipated advantages in proof, we feel that the methodology improves a designer's ability to formulate and organize the issues involved in the design of large systems, with additional benefits in system reliability. These advantages remain even if proof is not attempted.
We are currently applying this methodology to the design and proof of a secure operating system. Each level in the system acts as a manager of all objects of a particular type (e .g ., directories, segments, linkage sections), and enforces all of the protection rules involved in the manipulation of these objects. In this paper we illustrate the methodology by examining three of the system levels, including specifications, for a simplified version of these levels. We also demonstrate some proofs of security-related properties and of correctness of implementation.
Restricted data types, specification and enforcement of invariant properties of variables
Authors: Buckle Normand 
Published: November 2005

When defining a data type, it is often useful to specify restrictions on the permitted values of that type.
Pascal's subrange type declaration, a special case of this kind of constraint definition, has already proved itself to be quite useful. Restricted data types allow more complex constraints to be defined and checked; for example, a variable could be declared of type “odd integer” or the day field of a “date” type variable could be checked for consistency with the year and month fields.
A simple mechanism is proposed, allowing the formulation of such constraints and their association with data types; the behaviour of a restricted type variable is described. The effects of the use of such a mechanism on program reliability, readability and efficiency are discussed.
An experimental investigation of the effect of program structure on program understanding
Authors: Love Tom 
Published: November 2005

A within-subjects experimental design was used to test the effect of two variables on program understanding. The independent variables were complexity of control flow and paragraphing of the source code. Understanding was measured by having the subjects memorize the code for a fixed time and reconstruct the code verbatim. Also some subjects were asked to describe the function of the program after completing their reconstruction. The two groups of subjects for the experiment were students from an introductory programming class and from a graduate class in programming languages.
The major findings were that paragraphing of the source had no effect for either group of subjects but that programs with simplified control flow were easier for the computer science students to understand as measured by their ability to reconstruct the programs. The dependent variable, rated accuracy of their description of the programs functions, did not differ as a function of either independent variable.
The paper is concluded with a description of the utility of this experimental approach relative to improving the reliability of software and a discussion of the importance of these findings.
Abstraction mechanisms in CLU
Authors: Liskov Barbara , Snyder Alan , Atkinson Russell , Schaffert Craig 
Published: November 2005

CLU is a new programming language designed to support the use of abstractions in program construction. Work in programming methodology has led to the realization that three kinds of abstractions, procedural, control, and especially data abstractions, are useful in the programming process. Of these, only the procedural abstraction is supported well by conventional languages, through the procedure or subroutine. CLU provides, in addition to procedures, novel linguistic mechanisms that support the use of data and control abstractions.
This paper provides an introduction to the abstraction mechanisms in CLU. By means of programming examples, we illustrate the utility of the three kinds of abstractions in program construction and show how CLU programs may be written to use and implement abstractions. We also discuss the CLU library, which permits incremental program development with complete type-checking performed at compile-time.
A performance comparison of object and relational databases using the Sun Benchmark
Authors: Duhl Joshua , Damon Craig 
Published: November 2005

A general concern about object-oriented systems has been whether or not they are able to meet the performance demands required to be useful for the development of significant production software systems. Attempts to evaluate this assertion have been hampered by a lack of meaningful performance benchmarks that compare database operations across different kinds of databases.
In this paper, we utilize the Sun Benchmark [Rube87] as a means for assessing the performance of an object database and comparing it with existing relational systems. We discuss the benchmark, and many of the implementation issues involved in introducing a relationally oriented benchmark into an object-oriented paradigm. We demonstrate the performance of an object database using Ontologic's Vbase object database platform as an example of a commercially available object database, and we compare these benchmark results against those of existing relational database systems. The results offer strong evidence that object databases are capable of performing as well as, or better than, existing relational database systems.
Intensional concepts in an object database model
Authors: Beech David 
Published: November 2005

There is a requirement for a stronger treatment of intentional concepts and more general inferential ability within database systems. A framework for achieving this will be described in terms of extensions to an object data model.
The type Concept is introduced into the model as a subtype of Action. Intentional concepts may then be defined as filters or generators, depending on the nature of the defining formula. In either case, the dual action should be available—provided automatically by the system or explicitly by the user.
Finally, sets and types are treated as special cases of extensional concepts, leading to a novel structure of the hierarchy of system types.
Restructuring Lisp programs for concurrent execution
Authors: Larus James R. , Hilfinger Paul N. 
Published: November 2005

This paper describes the techniques that the program transformation system CURARE uses to restructure Lisp programs for concurrent execution in multiprocessor Lisp systems and discusses the problems inherent in producing concurrent programs in a flexible and dynamic programming language such as Lisp.
CURARE's overall organization is similar to other program restructuring systems: it detects potential conflicts between statements in a program, then transforms the program to improve its concurrent performance, and finally inserts synchronization to ensure the program's concurrent behavior. However, the language and programs that CURARE transforms are very different from the FORTRAN programs that are the traditional targets of program restructuring and so CURARE requires new algorithms and approaches, which are described in this paper.
Pgraphite: an experiment in persistent typed object management
Authors: Wileden Jack C. , Wolf Alexander L. , Fisher Charles D. , Tarr Peri L. 
Published: November 2005

Defining, creating, and manipulating
persistent typed objects
will be central activities in future software environments. PGRAPHITE is a working prototype through which we are exploring the requirements for the persistent object capability of an object management system in the Arcadia software environment.

PGRAPHITE represents both a set of abstractions that define a model for dealing with persistent objects in an environment and a set of implementation strategies for realizing that model. PGRAPHITE currently provides a type definition mechanism for one important class of types, namely directed graphs, and the automatic generation of Ada implementations for the defined types, including their persistence capabilities.
We present PGRAPHITE, describe and motivate its model of persistence, outline the implementation strategies that it embodies, and discuss some of our experience with the current version of the system.
Extended programming in the large in a software development environment
Authors: Lewerentz Claus 
Published: November 2005

This paper deals with the programming in the large part and the integration with related activities (programming in the small, variant control, support of technical documentation, responsibility and access control) of the software development and maintenance process. It is pointed out how these tasks are supported with an integrated and incremental software project support environment (IPSEN).
Snapshots of a working session are used to demonstrate the user interface and the functionality of the tools for the above mentioned topics. The main concern of this paper is to show how an incremental and integrated tool set, regarding the consistency of software documents can support software development.
Message driven computing and its relationship to actors
Authors: Christopher T. W. 
Published: November 2005

We define Message Driven Computation as a style of computing with two characteristics: 1) Messages, not sequential processes, convey both control and data. Indeed, there are no sequential processes unless they are programmed explicitly in terms of messages. 2) Computation is invoked by the presence of a collection of messages at the same location. MDC may be viewed as a generalization of Actors [AGHA86].
MDC - Message Driven Computing
MDC is based on message passing to named locations at which both data storage and computation is performed.
Messages are sent to labeled message queues called portals. A locus is a named collection of portals.
Messages are not sent or received by processes; rather, a collection of messages at a locus that match a pattern will trigger the execution of a procedure. These pattern-invoked procedures are called behaviors. The execution of a behavior can send further messages.
There are two kinds of patterns currently provided for triggering behaviors. 1) A specified number of messages at each of several specified portals at the same locus can trigger a behavior. 2) A message arriving at a specified portal of a locus can trigger a behavior if that locus has no other messages at any of its portals. The contents of the messages are not examined in either pattern match.
A locus is named by an arbitrary tuple of information. The first component is required to be a symbol, an internally generated value used somewhat like a pointer. All loci whose names begin with the same symbol are typically considered to be components of the same distributed object. Moreover, a garbage collector can collect all loci whose names cannot be generated again because no active computation has access to their initial symbol.
A locus will occupy one node of a multi-computer. The node number may be calculated from the locus name by a user specified formula or by hashing if no other method is specified. A locus is created when a message arrives at it and vanishes when no further messages are present or the garbage collector discovers it can no longer be active.
Similarly, portals are created at loci when messages arrive at them. A portal name is constructed out of a locus name and a portal label.
Transformation of concurrent object systems
Authors: Shibayama E. 
Published: November 2005

Rapid progress of hardware technology makes it feasible to construct a network system consisting of hundreds of small computers. Today, such a system can offer more computing power than a single large computer in a cheaper way. Moreover, a network computer system is much more flexible and, even when some of the processors fall in trouble, the other processors can possibly continue their work. Widely use of network computer systems is expected in near future.
In order to utilize distributed computing systems, we need distributed software. However, the progress of software technology is relatively slow. The design and development of distributed software is a difficult task at least under today's technologies. We need more sophisticated methodologies for design and development of distributed software.
A VHDL compiler based on attribute grammar methodology
Authors: Farrow R. , Stanculescu A. G. 
Published: November 2005

This paper presents aspects of a compiler for a new hardware description language (VHDL) written using attribute grammar techniques. VHDL is introduced, along with the new compiler challenges brought by a language that extends an Ada subset for the purpose of describing hardware. Attribute grammar programming solutions are presented for some of the language challenges.
The organization of the compiler and of the target virtual machine represented by the simulation kernel are discussed, and performance and code-size figures are presented.
The paper concludes that attribute grammars can be used for large commercial compilers with excellent results in terms of rapid development time and enhanced maintainability, and without paying any substantial penalty in terms of either the complexity of the language that can be handled or the resulting compilation speed.
Good news, bad news: experience building software development environment using the object-oriented paradigm
Authors: Harrison W. H. , Sweeney P. F. , Shilling J. J. 
Published: November 2005

This paper presents our experience building an extendible software development environment using the object-oriented paradigm. We have found that object instances provide a natural way to model program constructs, and to capture complex relationships between different aspects of a software system. The object-oriented paradigm can be efficiently implemented on standard hardware and software, and provides some degree of extendibility without requiring major modifications to the existing implementation.
Unfortunately, we have also found that some natural extensions that we would like to make to the environment are not easily incorporated. We argue that the lack of extendibility is due to the object-oriented paradigm's lack of support for providing modifications and extensions to the object-oriented paradigm itself.
Separate compilation for Standard ML
Authors: Appel Andrew W. , MacQueen David B. 
Published: November 2005

Languages that support abstraction and modular structure, such as Standard ML, Modula, Ada, and (more or less) C++, may have deeply nested dependency hierarchies among source files. In ML the problem is particularly severe because ML's powerful parameterized module (functor) facility entails dependencies among implementation modules, not just among interfaces.
To efficiently compile individual modules in such languages, it is useful (in ML, necessary) to infer, digest, and cache the static environment resulting from the compilation of each module.
Our system provides a simple model of compilation and linkage that supports incremental recompilation (a restricted form of separate compilation) with type-safe linkage. This model is made available to user programs in the form of a set of internal compiler modules, a feature that we call the “visible compiler”. The chief client of this interface is the IRM incremental recompilation manager from CMU.
Lazy functional state threads
Authors: Launchbury John , Peyton Jones Simon L. 
Published: November 2005

Some algorithms make critical internal use of updatable state, even though their external specification is purely functional. Based on earlier work on monads, we present a way of securely encapsulating stateful computations that manipulate multiple, named, mutable objects, in the context of a non-strict, purely-functional language.
The security of the encapsulation is assured by the type system, using parametricity. Intriguingly, this parametricity requires the provision of a (single) constant with a rank-2 polymorphic type.
Accurate static estimators for program optimization
Authors: Wagner Tim A. , Maverick Vance , Graham Susan L. , Harrison Michael A. 
Published: November 2005

Determining the relative execution frequency of program regions is essential for many important optimization techniques, including register allocation, function inlining, and instruction scheduling. Estimates derived from profiling with sample inputs are generally regarded as the most accurate source of this information; static (compile-time) estimates are considered to be distinctly inferior. If static estimates were shown to be competitive, however, their convenience would outweigh minor gains from profiling, and they would provide a sound basis for optimization when profiling is impossible.
We use quantitative metrics to compare estimates from static analysis to those derived from profiles. For C programs, simple techniques for predicting branches and loop counts suffice to estimate intraprocedural frequency patterns with high accuracy. To determine inter-procedural estimates successfully, we combine function-level information with a Markov model of control flow over the call graph to produce arc and basic block frequency estimates for the entire program.
For a suite of 14 programs, including the C programs from the SPEC92 benchmark suite, we demonstrate that static estimates are competitive with those derived from profiles. Using simple heuristics, we can determine the most frequently executed blocks in each function with 81% accuracy. With the Markov model, we identify 80% of the frequently called functions. Combining the two techniques, we identify 76% of the most frequently executed call sites.
An optimizing compiler for lexically scoped LISP
Authors: Brooks Rodney A. , Gabriel Richard P. , Steele Guy L. 
Published: November 2005

We are developing an optimizing compiler for a dialect of the LISP language. The current target architecture is the S-I, a multiprocessing supercomputer designed at Lawrence Livermore National Laboratory. While LISP is usually thought of as a language primarily for symbolic processing and list manipulation, this compiler is also intended to compete with the S-1 PASCAL and FORTRAN compilers for quality of compiled numerical code. The S-1 is designed for extremely high-speed signal processing as well as for symbolic computation; it provides primitive operations on vectors of floating-point and complex numbers. The LISP compiler is designed to exploit the architecture heavily.
The compiler is structurally and conceptually similar to the BLISS-11 compiler and the compilers produced by PQCC. In particular, the TNBIND technique has been borrowed and extended.
An efficient separate compilation strategy for very large programs
Authors: Rudmik Andres , Moore Barbara G. 
Published: November 2005

This paper describes the design of a compiling system that supports the efficient compilation of very large programs. The system consists of front ends for different languages, a common program database to store the intermediate code, and various back ends, optimizers, debuggers and other development tools. The compiling system achieves efficiency of use by minimizing the number of system components that must be invoked when a small change is made in a program.
A new separate compilation strategy is presented that is both easy and natural to use and does not require language extensions for its use. The database provides the necessary contextual information to support separate compilation and to facilitate complete compile-time checking. Also, the use of this database affords a unique opportunity to reduce substantially the cost of recompilation and to support an efficient source patching facility.
PIC—a language for typesetting graphics
Authors: Kernighan Brian W. 
Published: November 2005

PIC is a language for specifying pictures so that they can be typeset as an integral part of a document preparation system.
The basic objects in PIC are boxes, lines, arrows, circles, ellipses, arcs and splines, which may be placed anywhere and labeled with arbitrary text. Most of the effort in designing PIC has gone into making it possible to specify the sizes and positions of objects with minimal use of absolute coordinates.
This paper describes PIC, with primary emphasis on those aspects of the language that make it easy to use.
EMACS the extensible, customizable self-documenting display editor
Authors: Stallman Richard M. 
Published: November 2005

EMACS is a display editor which is implemented in an interpreted high level language. This allows users to extend the editor by replacing parts of it, to experiment with alternative command languages, and to share extensions which are generally useful. The ease of extension has contributed to the growth of a large set of useful features. This paper describes the organization of the EMACS system, emphasizing the way in which extensibility is achieved and used.
This report describes work done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-80-C-0505.