bluuebunny/crossref_metadata_2025 huggingface dataset:
A tree-structured mean value analysis algorithm
Authors: Hoyme K. P. , Bruell S. C. , Afshari P. V. , Kain R. Y.
Published: July 2002

In a recent paper, Lam and Lien described an algorithm called tree-convolution that can reduce the space and computation time required for evaluating sparse multiclass, product-form queueing networks. In this paper, we develop an exact algorithm based on mean value analysis (MVA) that is the counterpart of the tree-convolution algorithm. The order of reduction in storage and computation achieved by our new
Tree-MVA
algorithm compared to the standard MVA algorithm is the same order of reduction obtained by the tree-convolution algorithm over that of the standard convolution algorithm. Our Tree-MVA algorithm preserves the inherent simplicity of MVA based algorithms.
Computer science
Authors: Hopcroft John E.
Published: July 2002

The continued rapid development of computer science will require an expansion of the science base and an influx of talented new researchers. Computers have already altered the way we think and live; now they will begin to elevate our knowledge of the world.
Windows of opportunity in electronic classrooms
Authors: Shneiderman Ben , Alavi Maryann , Norman Kent , Borkowski Ellen Yu
Published: July 2002

Paradigm-shifting landmark buildings are cherished by their occupants and remembered because they reshape our expectations of schools, homes, or offices. Classic examples include Thomas Jefferson's communal design of the “academical village” at the University of Virginia where faculty and students lived close to classrooms, Frank Lloyd Wright's organic harmony with nature in Fallingwater (in western Pennsylvania) where the waterfall sounds and leafy surroundings offered a stress-reducing getaway for an urban executive, or Kevin Roche's open glass-walled Ford Foundation (in New York City) that promoted new team-oriented management strategies.
Developing an object-oriented software testing and maintenance environment
Authors: Kung David , Gao Jerry , Hsia Pei , Toyoshima Yasufumi , Chen Chris , Kim Young-Si , Song Young-Kee
Published: July 2002

The object-oriented (OO) paradigm is rapidly gaining acceptance in the software industry. However, the powerful features of this new paradigm also introduce a new set of OO software testing and maintenance problems. The pioneering work in identifying these new problems includes [7, 10-12, 14, 16, 18]. The problems can be summarized as: 1) the understanding problem; 2) the complex interdependency problem; 3) the object state behavior testing problem; and 4) the tool support problem. Detailed discussions of these problems will be provided later. Our industrial experience confirms these discoveries.
Portable run-time support for dynamic object-oriented parallel processing
Authors: Grimshaw Andrew S. , Weissman Jon B. , Strayer W. Timothy
Published: July 2002

Mentat is an object-oriented parallel processing system designed to simplify the task of writing portable parallel programs for parallel machines and workstation networks. The Mentat compiler and run-time system work together to automatically manage the communication and synchronization between objects. The run-time system marshals member function arguments, schedules objects on processors, and dynamically constructs and executes large-grain data dependence graphs. In this article we present the Mentat run-time system. We focus on three aspects—the software architecture, including the interface to the compiler and the structure and interaction of the principle components of the run-time system; the run-time overhead on a component-by-component basis for two platforms, a Sun SparcStation 2 and an Intel Paragon; and an analysis of the minimum granularity required for application programs to overcome the run-time overhead.
KNOs: KNowledge acquisition, dissemination, and manipulation Objects
Authors: Tsichritzis D. , Fiume E. , Gibbs S. , Nierstrasz O.
Published: July 2002

Most object-oriented systems lack two useful facilities: the ability of objects to migrate to new environments and the ability of objects to acquire new operations dynamically. This paper proposes Knos, an object-oriented environment that supports these actions. Knos' operations, data structures, and communication mechanisms are discussed. Knos objects “learn” by exporting and importing new or modified operations. The use of such objects as intellectual support tools is outlined. In particular, various applications involving cooperation, negotiation, and apprenticeship among objects are described.
Computer Science Program Accreditation: the first-year activities of the computing sciences accreditation board
Authors: Booth Taylor , Miller Raymond E.
Published: July 2002

This report summarizes the activities of the Computing Sciences Accreditation Board from its inception in 1984 through its first accreditation cycle completed in June 1986. The major activities during this period were directed at developing the CSAB structure necessary to carry out the accreditation process, and at conducting the first round of accreditation visits and actions.
How to declare an imperative
Authors: Wadler Philip
Published: July 2002

How can we integrate interaction into a purely declarative language? This tutorial describes a solution to this problem based on a monad. The solution has been implemented in the functional language Haskell and the declarative language Escher. Comparisons are given with other approaches to interaction based on synchronous streams, continuations, linear logic, and side effects.
Memory data organization for improved cache performance in embedded processor applications
Authors: Panda Preeti Ranjan , Dutt Nikil D. , Nicolau Alexandru
Published: July 2002

Code generation for embedded processors opens up the possibility for several performance optimization techniques that have been ignored by traditional compilers due to compilation time constraints. We present techniques that take into account the parameters of the data caches for organizing scalar and array variables declared in embedded code into memory, with the objective of improving data cache performance. We present techniques for clustering variables to minimize compulsory cache misses, and for solving the memory assignment problem to minimize conflict cache misses. Our experiments with benchmark code kernels from DSP and other domains on the CW4001 embedded processor from LSI Logic indicate significant improvements in data cache performance by the application of our memory organization technique.
Adaptive, fine-grained sharing in a client-server OODBMS
Authors: Zaharioudakis Markos , Carey Michael J. , Franklin Michael J.
Published: July 2002

For reasons of simplicity and communication efficiency, a number of existing object-oriented database management systems are based on page server architectures; data pages are their minimum unit of transfer and client caching. Despite their efficiency, page servers are often criticized as being too retrictive when it comes to concurrency, as existing systems use pages as the minimum locking unit as well. In this paper we show how to support object-level locking in a page-server context. Several approaches are described, including an adaptive granularity approach that uses page-level locking for most pages but switches to object-level locking when finer-grained sharing is demanded. Each of the approaches is based on extending the idea of callback locking. We study the performance of these approaches, comparing them to both a pure page server and a pure object server. For the range of workload that we have examined, our results indicate that the adaptive page server provides very good performance, usually outperforming the pure page server and the other page-server variants as well. In addition, the adaptive page server is often preferable to the pure object server; our results provides insight into when each approach is likely to perform better.
Code generation for fixed-point DSPs
Authors: Araujo Guido , Malik Sharad
Published: July 2002

This paper examines the problem of code-generation for Digital Signal Processors (DSPs). We make two major contributions. First, for an important class of DSP architectures, we propose an optimal
O(n)
algorithm for the tasks of register allocation and instruction scheduling for expression trees. Optimality is guaranteed by sufficient conditions derived from a structural representation of the processor Instruction Set Architecture (ISA). Second, we develop heuristics for the case when basic blocks are Directed Acyclic Graphs (DAGs).
Inverted files versus signature files for text indexing
Authors: Zobel Justin , Moffat Alistair , Ramamohanarao Kotagiri
Published: July 2002

Two well-known indexing methods are inverted files and signature files. We have undertaken a detailed comparison of these two approaches in the context of text indexing, paying particular attention to query evaluation speed and space requirements. We have examined their relative performance using both experimentation and a refined approach to modeling of signature files, and demonstrate that inverted files are distinctly superior to signature files. Not only can inverted files be used to evaluate typical queries in less time than can signature files, but inverted files require less space and provide greater functionality. Our results also show that a synthetic text database can provide a realistic indication of the behavior of an actual text database. The tools used to generate the synthetic database have been made publicly available
Pricing computer services: queueing effects
Authors: Mendelson Haim
Published: July 2002

This article studies the effects of queueing delays, and users' related costs, on the management and control of computing resources. It offers a methodology for setting price, utilization, and capacity, taking into account the value of users' time, and it examines the implications of alternative control structures, determined by the financial responsibility assigned to the data processing manager.
Optimal file designs and reorganization points
Authors: Batory D. S.
Published: July 2002

A model for studying the combined problems of file design and file reorganization is presented. New modeling techniques for predicting the performance evolution of files and for finding optimal reorganization points for files are introduced. Applications of the model to hash-based and indexed-sequential files reveal important relationships between initial loading factors and reorganization frequency. A practical file design strategy, based on these relationships, is proposed.
Optimization of query evaluation algorithms
Authors: Yao S. Bing
Published: July 2002

A model of database storage and access is presented. The model represents many evaluation algorithms as special cases, and helps to break a complex algorithm into simple access operations. Generalized access cost equations associated with the model are developed and analyzed. Optimization of these cost equations yields an optimal access algorithm which can be synthesized by a query subsystem whose design is based on the modular access operations.
The Organization of Computations for Uniform Recurrence Equations
Authors: Karp Richard M. , Miller Raymond E. , Winograd Shmuel
Published: July 2002

A set equations in the quantities

a
i

(
p
), where
i
= 1, 2, · · ·,
m
and
p
ranges over a set
R
of lattice points in
n
-space, is called a
system of uniform recurrence equations
if the following property holds: If
p
and
q
are in
R
and
w
is an integer
n
-vector, then

a
i

(
p
) depends directly on

a
j

(
p
-
w
) if and only if

a
i

(
q
) depends directly on

a
j

(
q
-
w
). Finite-difference approximations to systems of partial differential equations typically lead to such recurrence equations. The structure of such a system is specified by a
dependence graph G
having
m
vertices, in which the directed edges are labeled with integer
n
-vectors. For certain choices of the set
R
, necessary and sufficient conditions on
G
are given for the existence of a schedule to compute all the quantities

a
i

(
p
) explicitly from their defining equations. Properties of such schedules, such as the degree to which computation can proceed “in parallel,” are characterized. These characterizations depend on a certain iterative decomposition of a dependence graph into subgraphs. Analogous results concerning implicit schedules are also given.
On the Time Required to Perform Multiplication
Authors: Winograd S.
Published: July 2002

The time required to perform multiplication is investigated. A lower bound on the time required to perform multiplication, as well as multiplication modulo
N
, is derived and it is shown that these lower bounds can be approached. Then a lower bound on the amount of time required to perform the most significant part of multiplication (⌞
xy
/
N
⌟) is derived.
A Formalization of Transition Diagram Systems
Authors: Lomet David Bruce
Published: July 2002

The transition diagram systems first introduced by Conway are formalized in terms of a restricted deterministic pushdown acceptor (DPDA) called a nested DPDA. It is then established that the class of nested DPDA's is capable of accepting all deterministic context-free languages. The proof of this involves demonstrating that left recursion can be eliminated from deterministic (or LR(
k
)) grammars without destroying the deterministic property. Using various structural properties of nested DPDA's, one can then establish equivalence results for certain classes of deterministic languages.
Synthesis of a Feedback Queueing Discipline for Computer Operation
Authors: Michel J. A. , Coffman E. G.
Published: July 2002

Considerable effort has been invested in devising and analyzing sequencing rules for multiprogrammed or time-shared systems. A much studied discipline of this kind is the so-called system with feedback to lower priority queues. This discipline contains many parameters, in general, which must be fixed in order to achieve the desired waiting-time performance of the discipline. In this paper the problem of synthesizing a system of the above type is solved, by setting parameter values so that prespecified waiting time criteria are satisfied, assuming Poisson arrival and general service time parameters are known.
Optimal Order of One-Point and Multipoint Iteration
Authors: Kung H. T. , Traub J. F.
Published: July 2002

The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2

n
-1

which use
n
evaluations of ƒ and no derivative evaluations, as well as a second family of iterations of order 2

n
-1

based on
n
— 1 evaluations of ƒ and one of ƒ′. In particular, with four evaluations an iteration of eighth order is constructed. The best previous result for four evaluations was fifth order.

It is proved that the
optimal
order of one general class of multipoint iterations is 2

n
-1

and that an upper bound on the order of a multipoint iteration based on
n
evaluations of ƒ (no derivatives) is 2

n

.

It is conjectured that a multipoint iteration without memory based on
n
evaluations has optimal order 2

n
-1

.
Analysis and Applications of the Delay Cycle for the
M/M/c
Queueing System
Authors: Omahen K. , Marathe V.
Published: July 2002

The method of analysis employing decomposition of busy periods
has, in various forms, been applied to the M/G/1 queueing system
under a variety of scheduling rules This paper extends the
technique of decomposition of busy periods in order to deal with
the M/M/c queueing system. Particular attention is given to a
special busy period referred to as a "delay cycle." The delay cycle
commences with a delay period (of general distribution) in which
jobs arrive but are not serviced, at the conclusion of the delay
period, processing begins and continues until the system is empty.
Closed form solutions are obtained for various entities such as
distribution of busy period length and expected waiting time
conditioned on the type of busy period in progress at the tmae of
job arrival. These results are applied and extended to the analysis
of six examples of multiprocessor systems.
Logical, internal, and physical reference behavior in CODASYL database systems
Authors: Effelsberg Wolfgang , Loomis Mary E. S.
Published: July 2002

This work investigates one aspect of the performance of CODASYL database systems: the data reference behavior. We introduce a model of database traversals at three levels: the logical, internal, and physical levels. The mapping between the logical and internal levels is defined by the internal schema, whereas the mapping between the internal and the physical levels depends on cluster properties of the database. Our model explains the physical reference behavior for a given sequence of DML statements at the logical level.

Software has been implemented to monitor references in two selected CODASYL DBMS applications. In a series of experiments the physical reference behavior was observed for varying internal schemas and cluster properties of the database. The measurements were limited to retrieval transactions, so that a variety of queries could be analyzed for the same well-known state of the database. Also, all databases were relatively small in order to allow fast reloading with varying internal schema parameters. In all cases, the database transactions showed less locality of reference than do programs under virtual memory operating systems; some databases showed no locality at all. No evidence of physical sequentiality was found. This suggests that standard page replacement strategies are not optimal for CODASYL database buffer management; instead, replacement decisions in a database buffer should be based on specific knowledge available from higher system layers.
Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives
Authors: Rinard Martin C.
Published: July 2002

This article presents our experience using optimistic synchronization to implement fine-grain atomic operations in the context of a parallelizing compiler for irregular, object-based computations. Our experience shows that the synchronization requirements of these programs differ significantly from those of traditional parallel computations, which use loop nests to access dense matrices using affine access functions. In addition to coarse-grain barrier synchronization, our irregular computations require synchronization primitives that support efficient fine-grain atomic operations. The standard implementation mechanism for atomic operations uses mutual exclusion locks. But the overhead of acquiring and releasing locks can reduce the performance. Locks can also consume significant amounts of memory. Optimistic synchronization primitives such as
loud-linked/store conditional
are an attractive alternative. They require no additional memory and eliminate the use of heavyweight blocking synchronization constructs. We evaluate the effectiveness of optimistic synchronization by comparing experimental results from two versions of a parallelizing compiler for irregular, object-based computations. One version generates code that uses mutual exclusion locks to make operations execute atomically. The other version generates code that uses mutual exclusion locks to make operations execute atomically. The other version uses optimistic synchronization. We used this compiler to automatically parallelize three irregular, object-based benchmark applications of interest to the scientific and engineering computation community. The presented experimental results indicate that the use of optimistic synchronization in this context can significantly reduce the memory consumption and improve the overall performance.
Composite model-checking
Authors: Bultan Tevfik , Gerber Richard , League Christopher
Published: July 2002

There has been a surge of progress in automated verification methods based on state exploration. In areas like hardware design, these technologies are rapidly augmenting key phases of testing and validation. To date, one of the most successful of these methods has been symbolic model-checking, in which large finite-state machines are encoded into compact data structures such as Binary Decision Diagrams (BDDs), and are then checked for safety and liveness properties. However, these techniques have not realized the same success on software systems. One limitation is their inability to deal with infinite-state programs, even those with a single unbounded integer. A second problem is that of finding efficient representations for various variable types. We recently proposed a model-checker for integer-based systems that uses arithmetic constraints as the underlying state representation. While this approach easily verified some subtle, infinite-state concurrency problems, it proved inefficient in its treatment of boolean and (unordered) enumerated types—which are not efficiently representable using arithmetic constraints. In this article we present a new technique that combines the strengths of both BDD and arithmetic constraint representations. Our composite model merges multiple type-specific symbolic representations in a single model-checker. A system's transitions and fixpoint computations are encoded using both BDD (for boolean and enumerated types) and arithmetic constraints (for integers) representations, where the choice depends on the variable types. Our composite model-checking strategy can be extended to other symbolic representations provided that they support operations such as intersection, union, complement, equivalence checking, and relational image computation. We also present conservative approximation techniques for composite representations to address the undecidability of model-checking on infinite-state systems. We demonstrate the effectiveness of our approach by analyzing two example software specifications which include a mixture of booleans, integers, and enumerated types. One of them is a requirements specification for the control software of a nuclear reactor's cooling system, and the other one is a protocol specification.
Symbolic mathematical computation
Authors: Wolfram Stephen
Published: July 2002

Standard programming languages are inadequate for the kind of symbolic mathematical computations that theoretical physicists need to perform. Higher mathematics systems like SMP address this problem.
A needed narrowing strategy
Authors: Antoy Sergio , Echahed Rachid , Hanus Michael
Published: July 2002

The narrowing relation over terms constitutes the basis of the most important operational semantics of languages that integrate functional and logic programming paradigms. It also plays an important role in the definition of some algorithms of unification modulo equational theories that are defined by confluent term rewriting systems. Due to the inefficiency of simple narrowing, many refined narrowing strategies have been proposed in the last decade. This paper presents a new narrowing strategy that is optimal in several respects. For this purpose, we propose a notion of a needed narrowing step that, for inductively sequential rewrite systems, extends the Huet and Lévy notion of a needed reduction step. We define a strategy, based on this notion, that computes only needed narrowing steps. Our strategy is sound and complete for a large class of rewrite systems, is optimal with respect to the cost measure that counts the number of distinct steps of a derivation, computes only incomparable and disjoint unifiers, and is efficiently implemented by unification.
Digital halftones by dot diffusion
Authors: Knuth Donald E.
Published: July 2002

This paper describes a technique for approximating real-valued pixels by two-valued pixels. The new method, called dot diffusion, appears to avoid some deficiencies of other commonly used techniques. It requires approximately the same total number of arithmetic operations as the Floyd-Steinberg method of adaptive grayscale, and it is well suited to parallel computation; but it requires more buffers and more complex program logic than other methods when implemented sequentially. A “smooth” variant of the method may prove to be useful in high-resolution printing.
Petri nets and speed independent design
Authors: Misunas David
Published: July 2002

Petri nets are investigated as one method of modeling speed independent asynchronous circuits. A study of circuit realizations of Petri nets leads to a demonstration of their usefulness in modeling speed independent operation. This usefulness is emphasized by the design of a speed independent processor from modules developed in the investigation of Petri net implementation.
Tracing the lineage of view data in a warehousing environment
Authors: Cui Yingwei , Widom Jennifer , Wiener Janet L.
Published: July 2002

We consider the
view data lineage
problem in a warehousing environment: For a given data item in a materialized warehouse view, we want to identify the set of source data items that produced the view item. We formally define the lineage problem, develop lineage tracing algorithms for relational views with aggregation, and propose mechanisms for performing consistent lineage tracing in a multisource data warehousing environment. Our result can form the basis of a tool that allows analysts to browse warehouse data, select view tuples of interest, and then “drill-through” to examine the exact source tuples that produced the view tuples of interest.
Meeting the crisis in computer science
Authors: Yau Stephen S. , Ritchie Robert W. , Semon Warren , Traub Joseph , Van Dam Andries , Winkler Stanley
Published: July 2002

Participants in the 1982 Snowbird Conference reassessed the problems in computer science education and recommended steps for improvement.
A survey of attitudes toward computers
Authors: Morrison Perry R.
Published: July 2002

What do people really think about computers and their impact? In 1970, a study of people's attitudes in North America showed computers to be regarded as either “beneficial tools of mankind” or as “awesome thinking machines.” A recent survey taken in Australia and reported in this article, though, suggests there may have been a change in attitudes over the past decade. The Australians expressed much concern over the computer's possible disemploying and dehumanizing effects—as well as disquiet over the control computers could exercise over their lives. If these attitudes are typical beyond the shores of Australia, they could create a barrier to the widespread acceptance and application of computers around the world.
Estimating block accesses and number of records in file management
Authors: Cheung To-Yat
Published: July 2002

We consider the problems of estimating the number of secondary storage blocks and the number of distinct records accessed when a transaction consisting of possibly duplicate requested records is presented to a file management system. Our main results include (1) a new formula for block access estimation for the case where the requested records may have duplications and their ordering in immaterial and (2) a simple formula for estimating the number of distinct records in the transaction.
ACM president's letter: eating our seed corn
Authors: Denning Peter J.
Published: July 2002

On July 12 and 13, 1980, the biennial meeting of Computer Science Department chairmen was held at Snowbird, Utah. This meeting, which is organized by the Computer Science Board (CSB), is a forum for the heads of the 83 departments in the United States and Canada that grant Ph.D.s in Computer Science. The meeting was attended by 56 department heads or their representatives, and by six observers from industry and government. This report was developed during the meeting as a result of intensive discussions about the crisis in Computer Science. This report was endorsed by the entire assembly.
Problems in application software maintenance
Authors: Lientz Bennet P. , Swanson E. Burton
Published: July 2002

The problems of application software maintenance in 487 data processing organizations were surveyed. Factor analysis resulted in the identification of six problem factors: user knowledge, programmer effectiveness, product quality, programmer time availability, machine requirements, and system reliability. User knowledge accounted for about 60 percent of the common problem variance, providing new evidence of the importance of the user relationship for system success or failure. Problems of programmer effectiveness and product quality were greater for older and larger systems and where more effort was spent in corrective maintenance. Larger scale data processing environments were significantly associated with greater problems or programmer effectiveness, but with no other problem factor. Product quality was seen as a lesser problem when certain productivity techniques were used in development.
Design of a LISP-based microprocessor
Authors: Steele Guy Lewis , Sussman Gerald Jay
Published: July 2002

We present a design for a class of computers whose “instruction sets” are based on LISP. LISP, like traditional stored-program machine languages and unlike most high-level languages, conceptually stores programs and data in the same way and explicitly allows programs to be manipulated as data, and so is a suitable basis for a stored-program computer architecture. LISP differs from traditional machine languages in that the program/data storage is conceptually an unordered set of linked record structures of various sizes, rather than an ordered, indexable vector of integers or bit fields of fixed size. An instruction set can be designed for programs expressed as trees of record structures. A processor can interpret these program trees in a recursive fashion and provide automatic storage management for the record structures.

We discuss a small-scale prototype VLSI microprocessor which has been designed and fabricated, containing a sufficiently complete instruction interpreter to execute small programs and a rudimentary storage allocator.
An event-driven compiling technique
Authors: Banâtre J. P. , Routeau J. P. , Trilling L.
Published: July 2002

Due to the linear structure of source text, difficulties may arise in a one-pass compilation process. These difficulties occur when an entity cannot be processed because of a forward reference to information only obtainable from subsequent entities. Classic solutions ask for data structures appropriate for each case. A technique is presented here which uses instead control structures, namely events and processes. The work of the compiler-writer becomes easier both conceptually and in practice because he can forget these problems at the outset and he avoids special processing for each problem. This technique has been applied to the construction of an Algol 68 compiler. Three examples from that implementation are described and discussed here.
Proof techniques for hierarchically structured programs
Authors: Robinson Lawrence , Levitt Karl N.
Published: July 2002

A method for describing and structuring programs that simplifies proofs of their correctness is presented. The method formally represents a program in terms of levels of abstraction, each level of which can be described by a self-contained nonprocedural specification. The proofs, like the programs, are structured by levels. Although only manual proofs are described in the paper, the method is also applicable to semi-automatic and automatic proofs. Preliminary results are encouraging, indicating that the method can be applied to large programs, such as operating systems.
Test data as an aid in proving program correctness
Authors: Geller Matthew
Published: July 2002

Proofs of program correctness tend to be long and tedious, whereas testing, though useful in detecting errors, usually does not guarantee correctness. This paper introduces a technique whereby test data can be used in proving program correctness. In addition to simplifying the process of providing correctness, this method simplifies the process of providing accurate specification for a program. The applicability of this technique to procedures and recursive programs is demonstrated.
Pseudochaining in hash tables
Authors: Halatsis Constantine , Philokyprou George
Published: July 2002

This paper presents pseudochaining as a new collision-resolution method. Pseudochaining is half way between open addressing and chaining. It owes its name to the fact that link fields are present in each cell of the hash table which permits “chaining” of the first overflow items in the table. The efficiency of the method is derived and a tradeoff analysis is given.
Shallow binding in Lisp 1.5
Authors: Baker Henry G.
Published: July 2002

Shallow binding is a scheme which allows the value of a variable to be accessed in a bounded amount of computation. An elegant model for shallow binding in Lisp 1.5 is presented in which context-switching is an environment tree transformation called rerooting. Rerooting is completely general and reversible, and is optional in the sense that a Lisp 1.5 interpreter will operate correctly whether or not rerooting is invoked on every context change. Since rerooting leaves assoc [
v, a
] invariant, for all variables
v
and all environments
a
, the programmer can have access to a rerooting primitive, shallow[], which gives him dynamic control over whether accesses are shallow or deep, and which affects only the speed of execution of a program, not its semantics. In addition, multiple processes can be active in the same environment structure, so long as rerooting is an indivisible operation. Finally, the concept of rerooting is shown to combine the concept of shallow binding in Lisp with Dijkstra's display for Algol and hence is a general model for shallow binding.
An algorithm for reasoning about equality
Authors: Shostak Robert E.
Published: July 2002

A simple technique for reasoning about equalities that is fast and complete for ground formulas with function symbols and equality is presented. A proof of correctness is given as well.
The system for business automation (SBA)
Authors: Zloof Moshé M. , de Jong S. Peter
Published: July 2002

The system for business automation (SBA) is a system within which application experts—nonprogrammers—can describe and execute their applications on a computer. The user of SBA views his application as manipulation of information in two-dimensional pictures of tables, business forms, and reports on a display terminal. He can gradually automate this application by giving “examples” to the system of how he manually manipulates the information. The Query-by-Example database language is a subset of the SBA programming language.
Performance evaluation of highly concurrent computers by deterministic simulation
Authors: Kumar B. , Davidson E. S.
Published: July 2002

Simulation is presented as a practical technique for performance evaluation of alternative configurations of highly concurrent computers. A technique is described for constructing a detailed deterministic simulation model of a system. In the model a control stream replaces the instruction and data streams of the real system. Simulation of the system model yields the timing and resource usage statistics needed for performance evaluation, without the necessity of emulating the system. As a case study, the implementation of a simulator of a model of the CPU-memory subsystem of the IBM 360/91 is described. The results of evaluating some alternative system designs are discussed. The experiments reveal that, for the case study, the major bottlenecks in the system are the memory unit and the fixed point unit. Further, it appears that many of the sophisticated pipelining and buffering techniques implemented in the architecture of the IBM 360/91 are of little value when high-speed (cache) memory is used, as in the IBM 360/195.
Abstract data types and software validation
Authors: Guttag John V. , Horowitz Ellis , Musser David R.
Published: July 2002

A data abstraction can be naturally specified using algebraic axioms. The virtue of these axioms is that they permit a representation-independent formal specification of a data type. An example is given which shows how to employ algebraic axioms at successive levels of implementation. The major thrust of the paper is twofold. First, it is shown how the use of algebraic axiomatizations can simplify the process of proving the correctness of an implementation of an abstract data type. Second, semi-automatic tools are described which can be used both to automate such proofs of correctness and to derive an immediate implementation from the axioms. This implementation allows for limited testing of programs at design time, before a conventional implementation is accomplished.
High-level data flow analysis
Authors: Rosen Barry K.
Published: July 2002

In contrast to the predominant use of low-level intermediate text, high-level data flow analysis deals with programs essentially at source level and exploits the control flow information implicit in the parse tree. The need for high-level flow analysis arises from several aspects of recent work on advanced methods of program certification and optimization. This paper proposes a simple general method of high-level data flow analysis that allows free use of escape and jump statements, avoids large graphs when compiling large programs, facilitates updating of data flow information to reflect program changes, and derives new global information helpful in solving many familiar global flow analysis problems. An illustrative application to live variable analysis is presented. Many of the graphs involved are constructed and analyzed before any programs are compiled, thus avoiding certain costs that low-level methods incur repeatedly at compile time.
Some theorems to aid in solving the file allocation problem
Authors: Grapa Enrique , Belford Geneva G.
Published: July 2002

The file allocation problem — i.e. the problem of finding the optimal set of network sites at which to locate copies of a file — is known to be, in general, polynomial complete. Heuristics and other aids to finding optimal, or near-optimal, solutions are therefore much needed. In this paper we present three theorems which can be applied a priori to indicate that certain sites should (or should not) be included in an optimal allocation.
Semantic evaluation from left to right
Authors: Bochmann Gregor V.
Published: July 2002

This paper describes attribute grammars and their use for the definition of programming languages and compilers; a formal definition of attribute grammars and a discussion of some of its important aspects are included. The paper concentrates on the evaluation of semantic attributes in a few passes from left to right over the derivation tree of a program. A condition for an attribute grammar is given which assures that the semantics of any program can be evaluated in a single pass over the derivation tree, and an algorithm is discussed which decides how many passes from left to right are in general necessary, given the attribute grammar. These notions are explained in terms of an example grammar which describes the scope rules of Algol 60. Practical questions, such as the relative efficiency of different evaluation schemes, and the ease of adapting the attribute grammar of a given programming language to the left-to-right evaluation scheme are discussed.
Analysis of the PFF replacement algorithm via a semi-Markov model
Authors: Chu Wesley W. , Opderbeck Holger
Published: July 2002

An analytical model is presented to estimate the performance of the Page Fault Frequency (PFF) replacement algorithm. In this model, program behavior is represented by the LRU stack distance model and the PFF replacement algorithm is represented by a semi-Markov model. Using these models, such parameters as the inter-page-fault interval distribution, the probability of the number of distinct pages being referenced during an inter-page-fault interval, etc. are able to be analytically determined. Using these models to evaluate these parameter values permits study of the performance of the replacement algorithm by simulating the page fault events rather than every page reference event. This significantly reduces the required computation time in estimating the performance of the PFF algorithm.
The computer science and engineering research study (COSERS)
Authors: Arden Bruce W.
Published: July 2002

The Computer Science and Engineering Research Study (COSERS) is briefly described. The motivation, organization, and schedule for this NSF supported study are given. For possible further reference, the subject area panel chairmen and the members of the Steering Committee are identified.
Computer-aided analysis and design of information systems
Authors: Nunamaker J. F. , Konsynski Benn R. , Ho Thomas , Singer Carl Allen
Published: July 2002

This paper describes the use of computer-aided analysis for the design and development of an integrated financial management system by the Navy Material Command Support Activity (NMCSA). Computer-aided analysis consists of a set of procedures and computer programs specifically designed to aid in the process of applications software design, computer selection and performance evaluation. There are four major components: Problem Statement Language, Problem Statement Analyzer, Generator of Alternative Designs, and Performance Evaluator. The statement of requirements was written in ADS (Accurately Defined Systems) and analyzed by a Problem Statement Analyzer for ADS. The ADS problem definition was supplemented with additional information in order to create a complete problem definition. The analyzed problem statement was translated to the form necessary for use by the SODA (Systems Optimization and Design Algorithm) program for the generation of alternative specifications of program modules and logical database structures.
Sentence paraphrasing from a conceptual base
Authors: Goldman Neil M.
Published: July 2002

A model of natural language generation based on an underlying language-free representation of meaning is described. A program based on this model is able to produce sentence paraphrases which demonstrate understanding with respect to a given context. This generator operates in conjunction with a natural language analyzer and a combined memory and inference model. In generating sentences from meaning structures, the program employs both the information retrieval and deduction capabilities of the memory model.

The model encompasses several diverse classes of linguistic knowledge, which include: (1) executable tests of conceptual properties stored in discrimination nets; (2) information relating conceptual to syntactic roles, stored in a word-sense dictionary, and (3) surface grammatical knowledge, stored in a formal grammar.
Implementation of a structured English query language
Authors: Astrahan M. M. , Chamberlin D. D.
Published: July 2002

The relational model of data, the XRM Relational Memory System, and the SEQUEL language have been covered in previous papers and are reviewed. SEQUEL is a relational data sublanguage intended for ad hoc interactive problem solving by non-computer specialists. A version of SEQUEL that has been implemented in a prototype interpreter is described. The interpreter is designed to minimize the data accessing operations required to respond to an arbitrary query. The optimization algorithms designed for this purpose are described.
The evolution of storage structures
Authors: Bachman Charles W.
Published: July 2002

Data base management systems have grown rapidly in their power and complexity over the 15-year history of data processing on commercially available computers. The original concepts have split, and new terms have been adopted to name and refer to these concepts. The Data Structure Diagram graphic technique is used to illustrate the splitting of the concepts and the structural relations which exist between these concepts at each point in the evolution.
File organization
Authors: Ghosh Sakti P.
Published: July 2002

The consecutive retrieval property is an important relation between a query set and record set. Its existence enables the design of an information retrieval system with a minimal search time and no redundant storage. Some important theorems on the consecutive retrieval property are proved in this paper. Conditions under which the consecutive retrieval property exists and remain invariant have been established. An outline for designing an information retrieval system based on the consecutive retrieval property is also discussed.
Thinning algorithms on rectangular, hexagonal, and triangular arrays
Authors: Deutsch E. S.
Published: July 2002

In this report three thinning algorithms are developed: one each for use with rectangular, hexagonal, and triangular arrays. The approach to the development of each algorithm is the same. Pictorial results produced by each of the algorithms are presented and the relative performances of the algorithms are compared. It is found that the algorithm operating with the triangular array is the most sensitive to image irregularities and noise, yet it will yield a thinned image with an overall reduced number of points. It is concluded that the algorithm operating in conjunction with the hexagonal array has features which strike a balance between those of the other two arrays.
Automatic errorbounds for simple zeros of analytic functions
Authors: Rokne J.
Published: July 2002

The Cauchy-Ostrowski theorem on convergence of Newton iterates for an analytic function in one variable is extended to include computational errors using complex interval arithmetic. Several numerical examples are given for polynomials with real and complex roots and one example for the Bessel function of the first kind.
Natural language question-answering systems: 1969
Authors: Simmons Robert F.
Published: July 2002

Recent experiments in programming natural language question-answering systems are reviewed to summarize the methods that have been developed for syntactic, semantic, and logical analysis of English strings. It is concluded that at least minimally effective techniques have been devised for answering questions from natural language subsets in small scale experimental systems and that a useful paradigm has evolved to guide research efforts in the field. Current approaches to semantic analysis and logical inference are seen to be effective beginnings but of questionable generality with respect either to subtle aspects of meaning or to applications over large subsets of English. Generalizing from current small-scale experiments to language-processing systems based on dictionaries with thousands of entries—with correspondingly large grammars and semantic systems—may entail a new order of complexity and require the invention and development of entirely different approaches to semantic analysis and question answering.
Experience with an extensible language
Authors: Irons Edgar T.
Published: July 2002

An operational extensible language system is described. The system and its base language are appraised with respect to efficiency, flexibility, and utility for different categories of users.
A program to teach programming
Authors: Fenichel Robert R. , Weizenbaum Joseph , Yochelson Jerome C.
Published: July 2002

The TEACH system was developed at MIT to ease the cost and improve the results of elementary instruction in programming. To the student, TEACH offers loosely guided experience with a conversational language which was designed with teaching in mind. Faculty involvement is minimal.

A term of experience with TEACH is discussed. Pedagogically, the system appears to be successful; straighforward reimplementation will make it economically successful as well.

Similar programs of profound tutorial skill will appear only as the results of extended research. The outlines of this research are beginning to become clear.