bluuebunny/crossref_metadata_2025 huggingface dataset:
A linear-time scheme for version reconstruction
Authors: Yu Lin , Rosenkrantz Daniel J.
Published: October 2002

An efficient scheme to store and reconstruct versions of sequential files is presented. The reconstruction scheme involves building a data structure representing a complete version, and then successively modifying this data structure by applying a sequence of specially formatted differential files to it. Each application of a differential file produces a representation of an intermediate version, with the final data structure representing the requested version.

The scheme uses a linked list to represent an intermediate version, instead of a sequential array, as is used traditionally. A new format for differential files specifying changes to this linked list data structure is presented. The specification of each change points directly to where the change is to take place, thereby obviating a search. Algorithms are presented for using such a new format differential file to transform the representation of a version, and for reconstructing a requested version. Algorithms are also presented for generating the new format differential files, both for the case of a forward differential specifying how to transform the representation of an old version to the representation of a new version, and for the case of a reverse differential specifying how to transform the representation of a new version to the representation of an old version.

The new version reconstruction scheme takes time linear in the sum of the size of the initial complete version and the sizes of the file differences involved in reconstructing the requested version. In contrast, the classical scheme for reconstructing versions takes time proportional to the sum of the sizes of the sequence of versions involved in the reconstruction, and therefore has a worst-case time that is quadratic in the sum of the size of the initial complete version and the sizes of the file differences. The time cost of the new differential file generation scheme is comparable to the time cost of the classical differential file generation scheme.
Transforming acyclic programs
Authors: Bossi Annalisa , Etalle Sandro
Published: October 2002

An unfold/fold transformation system is a source-to-source rewriting methodology devised to improve the efficiency of a program. Any such transformation should preserve the main properties of the initial program: among them, termination. In the field of logic programming, the class of acyclic programs plays an important role in this respect, since it is closely related to the one of terminating programs. The two classes coincide when negation is not allowed in the bodies of the clauses.

We prove that the Unfold/Fold transformation system defined by Tamaki and Sato preserves the acyclicity of the initial program. From this result, it follows that when the transformation is applied to an acyclic program, then the finite failure set for definite programs is preserved; in the case of normal programs, all major declarative and operational semantics are preserved as well. These results cannot be extended to the class of left-terminating programs without modifying the definition of the transformation.
Static slicing in the presence of goto statements
Authors: Choi Jong-Deok , Ferrante Jeanne
Published: October 2002

A static program slice is an extract of a program which can help our understanding of the behavior of the program; it has been proposed for use in debugging, optimization, parallelization, and integration of programs. This article considers two types of static slices: executable and nonexecutable. Efficient and well-founded methods have been developed to construct executable slices for programs without goto statements; it would be tempting to assume these methods would apply as well in programs with arbitrary goto statements. We show why previous methods do not work in this more general setting, and describe our solutions that correctly and efficiently compute executable slices for programs even with arbitrary goto statements. Our conclusion is that goto statements can be accommodated in generating executable static slices.
Strictness optimization for graph reduction machines (why id might not be strict)
Authors: Beemster Marcel
Published: October 2002

Strictness optimizations in the implementation of lazy functional languages are not always valid. In nonoptimized graph reduction, evaluation always takes place at the request of case analysis or a primitive operation. Hence, the result of a reduction is always a data value and never a function. This implies that in an implementation no argument satisfaction check is required. But in the presence of strict arguments, “premature” reduction may take place outside the scope of a case or primitive operation. This causes problems in graph reducers that use an
aggressive take
. Two solutions are presented, one based on a run-time argument satisfaction check, the other on a weakened strictness analyzer. Experimental results are used to compare the two solutions and show that the cost of the aggressive take can be arbitrarily high for specific programs. The experimental results enable a trade-off to be made by the reduction machine designer.
A generalized theory of bit vector data flow analysis
Authors: Khedker Uday P. , Dhamdhere Dhananjay M.
Published: October 2002

The classical theory of data flow analysis, which has its roots in unidirectional flows, is inadequate to characterize bidirectional data flow problems. We present a generalized theory of bit vector data flow analysis which explains the known results in unidirectional and bidirectional data flows and provides a deeper insight into the process of data flow analysis. Based on the theory, we develop a worklist-based generic algorithm which is uniformly applicable to unidirectional and bidirectional data flow problems. It is simple, versatile, and easy to adapt for a specific problem. We show that the theory and the algorithm are applicable to all bounded monotone data flow problems which possess the property of the separability of solution.

The theory yields valuable information about the complexity of data flow analysis. We show that the complexity of worklist-based iterative analysis is the same for unidirectional and bidirectional problems. We also define a measure of the complexity of round-robin iterative analysis. This measure, called
width
, is uniformly applicable to unidirectional and bidirectional problems and provides a tighter bound for unidirectional problems than the traditional measure of
depth
. Other applications include explanation of isolated results in efficient solution techniques and motivation of new techniques for bidirectional flows. In particular, we discuss edge splitting and edge placement and develop a feasibility criterion for decomposition of a bidirectional flow into a sequence of unidirectional flows.
Extending attribute grammars to support programming-in-the-large
Authors: Micallef Josephine , Kaiser Gail E.
Published: October 2002

Attribute grammars add specification of static semantic properties to context-free grammars, which, in turn, describe the syntactic structure of program units. However, context-free grammars cannot express programming-in-the-large features common in modern programming languages, including unordered collections of units, included units, and sharing of included units. We present extensions to context-free grammars, and corresponding extensions to attribute grammars, suitable for defining such features. We explain how batch and incremental attribute-evaluation algorithms can be adapted to support these extensions, resulting in a uniform approach to intraunit and interunit static semantic analysis and translation of multiunit programs.
Compositional verification of concurrent systems using Petri-net-based condensation rules
Authors: Juan Eric Y. T. , Tsai Jeffrey J. P. , Murata Tadao
Published: October 2002

The state-explosion problem of formal verification has obstructed its application to large-scale software systems. In this article, we introduce a set of new condensation theories: IOT-failure equivalence, IOT-state equivalence, and firing-dependence theory to cope with this problem. Our condensation theories are much weaker than current theories used for the compositional verification of Petri nets. More significantly, our new condensation theories can eliminate the interleaved behaviors caused by asynchronously sending actions. Therefore, our technique provides a much more powerful means for the compositional verification of asynchronous processes. Our technique can efficiently analyze several state-based properties: boundedness, reachable markings, reachable submarkings, and deadlock states. Based on the notion of our new theories, we develop a set of condensation rules for efficient verification of large-scale software systems. The experimental results show a significant improvement in the analysis large-scale concurrent systems.
A data-driven model for a subset of logic programming
Authors: Bic Lubomir , Lee Craig
Published: October 2002

There is a direct correspondence between semantic networks and a subset of logic programs, restricted only to binary predicates. The advantage of the latter is that it can describe not only the nodes and arcs comprising a semantic net, but also the data-retrieval operations applied to such nets. The main objective of this paper is to present a data-driven model of computation that permits this subset of logic programs to be executed on a highly parallel computer architecture. We demonstrate how logic programs may be converted into collections of data-flow graphs in which resolution is viewed as a process of finding matches between certain graph templates and portions of the data-flow graphs. This graph fitting process is carried out by messages propagating asynchronously through the data-flow graph; thus computation is entirely data driven, without the need for any centralized control and centralized memory. This permits a potentially large number of independent processing elements to cooperate in solving a given query.
Specificational functions
Authors: Morris J. M. , Bunkenburg A.
Published: October 2002

Mathematics supplies us with various operators for creating functions from relations, sets, known functions, and so on. Function inversion is a simple example. These operations are useful in specifying programs. However, many of them have strong constraints on their arguments to ensure that the result is indeed a function. For example, only functions that are bijective may be inverted. This is a serious impediment to their use in specifications, because at best it limits the specifier's expressive power, and at worst it imposes strong proof obligations on the programmer. We propose to loosen the definition of functions so that the constraints on operations such as inversion can be greatly relaxed. The specificational functions that emerge generalize traditional functions in that their application to some arguments may yield no good outcome, while for other arguments their application may yield any of several outcomes unpredictably. While these functions are not in general algorithmic, they can serve as specifications of traditional functions as embodied in programming languages. The idea of specificational functions is not new, but accommodating them in all their generality without falling foul of a myriad of anomalies has proved elusive. We investigate the technical problems that have hindered their use, and propose solutions. In particular, we develop a formal axiomatization for reasoning about specificational functions, and we prove its consistency by constructing a model.
A global communication optimization technique based on data-flow analysis and linear algebra
Authors: Kandemir M. , Banerjee P. , Choudhary A. , Ramanujam J. , Shenoy N.
Published: October 2002

Reducing communication overhead is extremely important in distributed-memory message-passing architectures. In this article, we present a technique to improve communication that considers data access patterns of the entire program. Our approach is based on a combination of traditional data-flow analysis and a linear algebra framework, and it works on structured programs with conditional statements and nested loops but without arbitrary goto statements.The distinctive features of the solution are the accuracy in keeping communication set information, support for general alignments and distributions including block-cyclic distribu-tions, and the ability to simulate some of the previous approaches with suitable modifications. We also show how optimizations such as message vectorization, message coalescing, and redundancy elimination are supported by our framework. Experimental results on several benchmarks show that our technique is effective in reducing the number of messages (anaverage of 32% reduction), the volume of the data communicated (an average of 37%reduction), and the execution time (an average of 26% reduction).
CIRCAL and the representation of communication, concurrency, and time
Authors: Milne George J.
Published: October 2002

The CIRCAL calculus is presented as a mathematical framework in which to describe and analyze concurrent systems, whether hardware or software.

The
dot operator
is used to compose CIRCAL descriptions, and it is this operator which permits the natural modeling of asynchronous
and
simultaneous behavior, thus allowing the representation and analysis of system timing properties such as those found in circuits.

The CIRCAL framework uses an
abstraction
operator to permit the modeling of a system at different levels of detail. Behavioral complexity of real systems makes abstraction crucial when producing a tractable model, and we illustrate how abstraction introduces
nondeterminisim
into system representations.

An operational semantics,
acceptance
semantics, is introduced, and it is in terms of this
active experimentation
that meaning is given to the CIRCAL syntax, thus allowing proof of system properties to be constructed.
Optimal parallel generation of a computation tree form
Authors: Bar-on Ilan , Vishkin Uzi
Published: October 2002

Given a general arithmetic expression, we find a computation binary tree representation in
O
(log
n
) time using
n
/log
n
processors on a concurrent-read, exclusive-write, parallel random-access machine.

A new algorithm is introduced for this purpose. Unlike previous serial and parallel solutions, it is not based on using a stack.
Understanding class hierarchies using concept analysis
Authors: Snelting Gregor , Tip Frank
Published: October 2002

A new method is presented for analyzing and reengineering class hierarchies. In our approach, a class hierarchy is processed along with a set of applications that use it, and a fine-grained analysis of the access and subtype relationships between objects, variables, and class members is performed. The result of this analysis is again a class hierarchy, which is guaranteed to be behaviorally equivalent to the original hierarchy, but in which each object only contains the members that are required. Our method is semantically well-founded in
concept analysis
: the new class hierarchy is a minimal and maximally factorized
concept lattice
that reflects the access and subtype relationships between variables, objects and class members. The method is primarily intended as a tool for finding imperfections in the design of class hierarchies, and can be used as the basis for tools that largely automate the process of reengineering such hierachies. The method can also be used as a space-optimizing source-to-source transformation that removes redundant fields from objects. A prototype implementation for Java has been constructed, and used to conduct several case studies. Our results demonstrate that the method can provide valuable insights into the usage of a class hierarchy in a specific context, and lead to useful restructuring proposals.
An Alternative to the Use of Patterns in String Processing
Authors: Griswold Ralph E. , Hanson David R.
Published: October 2002

SNOBOL4 is best known for its string processing facilities, which are based on patterns as data objects. Despite the demonstrated success of patterns, there are many shortcomings associated with their use. The concept of patterns in SNOBOL4 is examined and problem areas are discussed. An alternative method for high-level string processing is described. This method, implemented in the programming language Icon, employs
generators
, which are capable of producing alternative values. Generators, coupled with a goal-driven method of expression evaluation, provide the string processing facilities of SNOBOL4 without the disadvantages associated with patterns. Comparisons between SNOBOL4 and Icon are included and the broader implications of the new approach are discussed.
Managing Reentrant Structures Using Reference Counts
Authors: Bobrow Daniel G.
Published: October 2002

Automatic storage management requires that one identify storage unreachable by a user's program and return it to free status. One technique maintains a count of the references from user's programs to each cell, since a count of zero implies the storage is unreachable. Reentrant structures are self-referencing; hence no cell in them will have a count of zero, even though the entire structure is unreachable. A modification of standard reference counting can be used to manaage the deallocation of a large class of frequently used reentrant structures, including two-way and circularly linked lists.

All the cells of a potentially reentrant structure are considered as part of a single group for deallocation purposes. Information associated with each cell specifies its group membership. Internal references (pointers from one cell of the group to another) are not reference counted. External references to any cell of this group are counted as references to the group as a whole. When the external reference count goes to zero, all the cells of the group can be deallocated. This paper describes several ways of specifying group membership, properties of each implementation, and properties of mutable and immutable group membership.
Incremental data-flow analysis algorithms
Authors: Ryder Barbara G. , Paull Marvin C.
Published: October 2002

An incremental update algorithm modifies the solution of a problem that has been changed, rather than re-solving the entire problem. ACINCF and ACINCB are incremental update algorithms for forward and backward data-flow analysis, respectively, based on our equations model of Allen-Cocke interval analysis. In addition, we have studied their performance on a “nontoy” structured programming language L. Given a set of localized program changes in a program written in L, we identify a priori the nodes in its flow graph whose corresponding data-flow equations may be affected by the changes. We characterize these possibly affected nodes by their corresponding program structures and their relation to the original change sites, and do so
without actually performing the incremental updates
. Our results can be refined to characterize the reduced equations possibly affected if structured loop exit mechanisms are used, either singly or together, thereby relating richness of programming language usage to the ease of incremental updating.
Abstract types have existential type
Authors: Mitchell John C. , Plotkin Gordon D.
Published: October 2002

Abstract data type declarations appear in typed programming languages like Ada, Alphard, CLU and ML. This form of declaration binds a list of identifiers to a type with associated operations, a composite “value” we call a
data algebra
. We use a second-order typed lambda calculus SOL to show how data algebras may be given types, passed as parameters, and returned as results of function calls. In the process, we discuss the semantics of abstract data type declarations and review a connection between typed programming languages and constructive logic.
Featherweight Java
Authors: Igarashi Atsushi , Pierce Benjamin C. , Wadler Philip
Published: October 2002

Several recent studies have introduced lightweight versions of Java: reduced languages in which complex features like threads and reflection are dropped to enable rigorous arguments about key properties such as type safety. We carry this process a step further, omitting almost all features of the full language (including interfaces and even assignment) to obtain a small calculus, Featherweight Java, for which rigorous proofs are not only possible but easy. Featherweight Java bears a similar relation to Java as the lambda-calculus does to languages such as ML and Haskell. It offers a similar computational "feel," providing classes, methods, fields, inheritance, and dynamic typecasts with a semantics closely following Java's. A proof of type safety for Featherweight Java thus illustrates many of the interesting features of a safety proof for the full language, while remaining pleasingly compact. The minimal syntax, typing rules, and operational semantics of Featherweight Java make it a handy tool for studying the consequences of extensions and variations. As an illustration of its utility in this regard, we extend Featherweight Java with
generic classes
in the style of GJ (Bracha, Odersky, Stoutamire, and Wadler) and give a detailed proof of type safety. The extended system formalizes for the first time some of the key features of GJ.
Toward compiler implementation correctness proofs
Authors: Chirica Laurian M. , Martin David F.
Published: October 2002

Aspect of the interaction between compiler theory and practice is addressed. Presented is a technique for the syntax-directed specification of compilers together with a method for proving the correctness of their parse-driven implementations. The subject matter is presented in an order-algebraic framework; while not strictly necessary, this approach imposes beneficial structure and modularity on the resulting specifications and implementation correctness proofs. Compilers are specified using an order-algebraic definition of attribute grammars. A practical class of compiler implementations is considered, consisting of those driven by LR(
k
) or LL(
k
) parsers which cause a sequence of translation routine activations to modify a suitably initialized collection of data structures (called a translation environment). The implementation correctness criterion consists of appropriately comparing, for each source program, the corresponding object program (contained in the final translation environment) produced by the compiler implementation to the object program dictated by the compiler specification. Provided that suitable intermediate assertions (called
translation invariants
) are supplied, the program consisting of the (parse-induced) sequence of translation routine activations can be proven partially correct via standard inductive assertion methods.
Linear combination of transformations
Authors: Alexa Marc
Published: October 2002

Geometric transformations are most commonly represented as square matrices in computer graphics. Following simple geometric arguments we derive a natural and geometrically meaningful definition of scalar multiples and a commutative addition of transformations based on the matrix representation, given that the matrices have no negative real eigenvalues. Together, these operations allow the linear combination of transformations. This provides the ability to create weighted combination of transformations, interpolate between transformations, and to construct or use arbitrary transformations in a structure similar to a basis of a vector space. These basic techniques are useful for synthesis and analysis of motions or animations. Animations through a set of key transformations are generated using standard techniques such as subdivision curves. For analysis and progressive compression a PCA can be applied to sequences of transformations. We describe an implementation of the techniques that enables an easy-to-use and transparent way of dealing with geometric transformations in graphics software. We compare and relate our approach to other techniques such as matrix decomposition and quaternion interpolation.
Robust epsilon visibility
Authors: Duguet Florent , Drettakis George
Published: October 2002

Analytic visibility algorithms, for example methods which compute a subdivided mesh to represent shadows, are notoriously unrobust and hard to use in practice. We present a new method based on a generalized definition of extremal stabbing lines, which are the extremities of shadow boundaries. We treat scenes containing multiple edges or vertices in degenerate configurations, (e.g., collinear or coplanar). We introduce a robust ε method to determine whether each generalized extremal stabbing line is blocked, or is touched by these scene elements, and thus added to the line's generators. We develop robust blocker predicates for polygons which are smaller than ε. For larger ε values, small shadow features merge and eventually disappear. We can thus robustly connect generalized extremal stabbing lines in degenerate scenes to form shadow boundaries. We show that our approach is consistent, and that shadow boundary connectivity is preserved when features merge. We have implemented our algorithm, and show that we can robustly compute analytic shadow boundaries to the precision of our chosen ε threshold for non-trivial models, containing numerous degeneracies.
Self-similarity based texture editing
Authors: Brooks Stephen , Dodgson Neil
Published: October 2002

We present a simple method of interactive texture editing that utilizes self-similarity to replicate intended operations globally over an image. Inspired by the recent successes of hierarchical approaches to texture synthesis, this method also uses multi-scale neighborhoods to assess the similarity of pixels within a texture. However, neighborhood matching is not employed to generate new instances of a texture. We instead locate similar neighborhoods for the purpose of replicating editing operations on the original texture itself, thereby creating a fundamentally new texture. This general approach is applied to texture painting, cloning and warping. These global operations are performed interactively, most often directed with just a single mouse movement.
Improving noise
Authors: Perlin Ken
Published: October 2002

Two deficiencies in the original Noise algorithm are corrected: second order interpolation discontinuity and unoptimal gradient computation. With these defects corrected, Noise both looks better and runs faster. The latter change also makes it easier to define a uniform mathematical reference standard.
Responsible web caching
Authors: Berghel Hal
Published: October 2002

Putting the distribution control of the Web's intellectual content in the hands of those who created it.
Personalized search
Authors: Pitkow James , Schütze Hinrich , Cass Todd , Cooley Rob , Turnbull Don , Edmonds Andy , Adar Eytan , Breuel Thomas
Published: October 2002

A contextual computing approach may prove a breakthrough in personalized search efficiency.
Two case studies of open source software development
Authors: Mockus Audris , Fielding Roy T. , Herbsleb James D.
Published: October 2002

According to its proponents, open source style software development has the capacity to compete successfully, and perhaps in many cases displace, traditional commercial development methods. In order to begin investigating such claims, we examine data from two major open source projects, the Apache web server and the Mozilla browser. By using email archives of source code change history and problem reports we quantify aspects of developer participation, core team size, code ownership, productivity, defect density, and problem resolution intervals for these OSS projects. We develop several hypotheses by comparing the Apache project with several commercial projects. We then test and refine several of these hypotheses, based on an analysis of Mozilla data. We conclude with thoughts about the prospects for high-performance commercial/open source process hybrids.
A survey of rollback-recovery protocols in message-passing systems
Authors: Elnozahy E. N. (Mootaz) , Alvisi Lorenzo , Wang Yi-Min , Johnson David B.
Published: October 2002

This survey covers rollback-recovery techniques that do not require special language constructs. In the first part of the survey we classify rollback-recovery protocols intocheckpoint-basedandlog-based.Checkpoint-basedprotocols rely solely on checkpointing for system state restoration. Checkpointing can be coordinated, uncoordinated, or communication-induced.Log-basedprotocols combine checkpointing with logging of nondeterministic events, encoded in tuples calleddeterminants. Depending on how determinants are logged, log-based protocols can be pessimistic, optimistic, or causal. Throughout the survey, we highlight the research issues that are at the core of rollback-recovery and present the solutions that currently address them. We also compare the performance of different rollback-recovery protocols with respect to a series of desirable properties and discuss the issues that arise in the practical implementations of these protocols.
Creativity, art practice, and knowledge
Authors: Edmonds Ernest , Candy Linda
Published: October 2002

Achieving a balance of control and freedom by supporting a mix of strategies.
Shape distributions
Authors: Osada Robert , Funkhouser Thomas , Chazelle Bernard , Dobkin David
Published: October 2002

Measuring the similarity between 3D shapes is a fundamental problem, with applications in computer graphics, computer vision, molecular biology, and a variety of other fields. A challenging aspect of this problem is to find a suitable shape signature that can be constructed and compared quickly, while still discriminating between similar and dissimilar shapes.In this paper, we propose and analyze a method for computing shape signatures for arbitrary (possibly degenerate) 3D polygonal models. The key idea is to represent the signature of an object as ashape distributionsampled from ashape functionmeasuring global geometric properties of an object. The primary motivation for this approach is to reduce the shape matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence, or model fitting.We find that the dissimilarities between sampled distributions of simple shape functions (e.g., the distance between two random points on a surface) provide a robust method for discriminating between classes of objects (e.g., cars versus airplanes) in a moderately sized database, despite the presence of arbitrary translations, rotations, scales, mirrors, tessellations, simplifications, and model degeneracies. They can be evaluated quickly, and thus the proposed method could be applied as a pre-classifier in a complete shape-based retrieval or analysis system concerned with finding similar whole objects. The paper describes our early experiences using shape distributions for object classification and for interactive web-based retrieval of 3D models.
Modelling with implicit surfaces that interpolate
Authors: Turk Greg , O'Brien James F.
Published: October 2002

We introduce new techniques for modelling withinterpolating implicit surfaces. This form of implicit surface was first used for problems of surface reconstruction and shape transformation, but the emphasis of our work is on model creation. These implicit surfaces are described by specifying locations in 3D through which the surface should pass, and also identifying locations that are interior or exterior to the surface. A 3D implicit function is created from these constraints using a variational scattered data interpolation approach, and the iso-surface of this function describes a surface. Like other implicit surface descriptions, these surfaces can be used for CSG and interference detection, may be interactively manipulated, are readily approximated by polygonal tilings, and are easy to ray trace. A key strength for model creation is that interpolating implicit surfaces allow the direct specification of both the location of points on the surface and the surface normals. These are two important manipulation techniques that are difficult to achieve using other implicit surface representations such as sums of spherical or ellipsoidal Gaussian functions ("blobbies"). We show that these properties make this form of implicit surface particularly attractive for interactive sculpting using the particle sampling technique introduced by Witkin and Heckbert. Our formulation also yields a simple method for converting a polygonal model to a smooth implicit model, as well as a new way to form blends between objects.
Efficient implementation of lattice operations
Authors: Aït-Kaci Hassan , Boyer Robert , Lincoln Patrick , Nasr Roger
Published: October 2002

Lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and relative complementation (BUTNOT) are becoming more and more important in programming languages supporting object inheritance. We present a general technique for the efficient implementation of such operations based on an encoding method. The effect of the encoding is to plunge the given ordering into a boolean lattice of binary words, leading to an almost constant time complexity of the lattice operations. A first method is described based on a transitive closure approach. Then a more space-efficient method minimizing code-word length is described. Finally a powerful grouping technique called
modulation
is presented, which drastically reduces code space while keeping all three lattice operations highly efficient. This technique takes into account idiosyncrasies of the topology of the poset being encoded that are quite likely to occur in practice. All methods are formally justified. We see this work as an original contribution towards using semantic (vz., in this case, taxonomic) information in the engineering pragmatics of storage and retrieval of (vz., partially or quasi-ordered) information.
The concept of a supercompiler
Authors: Turchin Valentin F.
Published: October 2002

A supercompiler is a program transformer of a certain type. It traces the possible generalized histories of computation by the original program, and compiles an equivalent program, reducing in the process the redundancy that could be present in the original program. The nature of the redundancy that can be eliminated by supercompilation may be various, e.g., some variables might have predefined values (as in partial evaluation), or the structure of control transfer could be made more efficient (as in lazy evaluation), or it could simply be the fact that the same variable is used more than once. The general principles of supercompilation are described and compared with the usual approach to program transformation as a stepwise application of a number of equivalence rules. It is argued that the language Refal serves the needs of supercompilation best. Refal is formally defined and compared with Prolog and other languages. Examples are given of the operation of a Refal supercompiler implemented at CCNY on an IBM/370.
The PSG system: from formal language definitions to interactive programming environments
Authors: Bahlke Rolf , Snelting Gregor
Published: October 2002

The PSG programming system generator developed at the Technical University of Darmstadt produces interactive, language-specific programming environments from formal language definitions. All language-dependent parts of the environment are generated from an entirely nonprocedural specification of the language's syntax, context conditions, and dynamic semantics. The generated environment consists of a language-based editor, supporting systematic program development by named program fragments, an interpreter, and a fragment library system. The major component of the environment is a full-screen editor, which allows both structure and text editing. In structure mode the editor guarantees prevention of both syntactic and semantic errors, whereas in textual mode it guarantees their immediate recognition. PSG editors employ a novel algorithm for incremental semantic analysis which is based on unification. The algorithm will immediately detect semantic errors even in incomplete program fragments. The dynamic semantics of the language are defined in denotational style using a functional language based on the lambda calculus. Program fragments are compiled to terms of the functional language which are executed by an interpreter. The PSG generator has been used to produce environments for Pascal, ALGOL 60, MODULA-2, and the formal language definition language itself.
A structural view of the Cedar programming environment
Authors: Swinehart Daniel C. , Zellweger Polle T. , Beach Richard J. , Hagmann Robert B.
Published: October 2002

This paper presents an overview of the Cedar programming environment, focusing on its overall structure—that is, the major components of Cedar and the way they are organized. Cedar supports the development of programs written in a single programming language, also called Cedar. Its primary purpose is to increase the productivity of programmers whose activities include experimental programming and the development of prototype software systems for a high-performance personal computer. The paper emphasizes the extent to which the Cedar language, with run-time support, has influenced the organization, flexibility, usefulness, and stability of the Cedar environment. It highlights the novel system features of Cedar, includingautomatic storage managementof dynamically allocated typed values, arun-time type systemthat provides run-time access to Cedar data type definitions and allows interpretive manipulation of typed values, and apowerful device-independent imaging modelthat supports the user interface facilities. Using these discussions to set the context, the paper addresses the language and system features and the methodologies used to facilitate the integration of Cedar applications. A comparison of Cedar with other programming environments further identifies areas where Cedar excels and areas where work remains to be done.
Interprocedural slicing using dependence graphs
Authors: Horwitz Susan , Reps Thomas , Binkley David
Published: October 2002

The notion of a
program slice
, originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, and program integration. A slice of a program is taken with respect to a program point
p
and a variable
x
; the slice consists of all statements of the program that might affect the value of
x
at point
p
. This paper concerns the problem of interprocedural slicing—generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a
system dependence graph
, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation. (It should be noted that our work concerns a somewhat restricted kind of slice: rather than permitting a program to b
e sliced with respect to program point
p
and an
arbitrary
variable, a slice must be taken with respect to a variable that is
defined
or
used
at
p
.)

The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data dependence edges that represent
transitive
dependences due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.
The Mechanisms of Pollination and Fertilization in Plants
Authors: Lord Elizabeth M. , Russell Scott D.
Published: October 2002

▪ Abstract  In flowering plants, pollen grains germinate to form pollen tubes that transport male gametes (sperm cells) to the egg cell in the embryo sac during sexual reproduction. Pollen tube biology is complex, presenting parallels with axon guidance and moving cell systems in animals. Pollen tube cells elongate on an active extracellular matrix in the style, ultimately guided by stylar and embryo sac signals. A well-documented recognition system occurs between pollen grains and the stigma in sporophytic self-incompatibility, where both receptor kinases in the stigma and their peptide ligands from pollen are now known. Complex mechanisms act to precisely target the sperm cells into the embryo sac. These events initiate double fertilization in which the two sperm cells from one pollen tube fuse to produce distinctly different products: one with the egg to produce the zygote and embryo and the other with the central cell to produce the endosperm.
Signaling Pathways in Vascular Development
Authors: Rossant Janet , Howard Lorraine
Published: October 2002

▪ Abstract  The vasculature is one of the most important and complex organs in the mammalian body. The first functional organ to form during embryonic development, the intricately branched network of endothelial and supporting periendothelial cells is essential for the transportation of oxygen and nutrients to and the removal of waste products from the tissues. Serious disruptions in the formation of the vascular network are lethal early in post-implantation development, while the maintenance of vessel integrity and the control of vessel physiology and hemodynamics have important consequences throughout embryonic and adult life. A full understanding of the signaling pathways of vascular development is important not just for understanding normal development but because of the importance of reactivation of angiogenic pathways in disease states. Clinically there is a need to develop therapies to promote new blood vessel formation in situations of severe tissue ischemia, such as coronary heart disease. In addition, there is considerable interest in developing angiogenic inhibitors to block the new vessel growth that solid tumors promote in host tissue to enhance their own growth. Already studies on the signaling pathways of normal vascular development have provided new targets for therapeutic intervention in both situations. Further understanding of the complexities of the pathways should help refine such strategies.
Cellular Control of Actin Nucleation
Authors: Welch Matthew D. , Mullins R. Dyche
Published: October 2002

▪ Abstract  Eukaryotic cells use actin polymerization to change shape, move, and internalize extracellular materials by phagocytosis and endocytosis, and to form contractile structures. In addition, several pathogens have evolved to use host cell actin assembly for attachment, internalization, and cell-to-cell spread. Although cells possess multiple mechanisms for initiating actin polymerization, attention in the past five years has focused on the regulation of actin nucleation—the formation of new actin filaments from actin monomers. The Arp2/3 complex and the multiple nucleation-promoting factors (NPFs) that regulate its activity comprise the only known cellular actin-nucleating factors and may represent a universal machine, conserved across eukaryotic phyla, that nucleates new actin filaments for various cellular structures with numerous functions. This review focuses on our current understanding of the mechanism of actin nucleation by the Arp2/3 complex and NPFs and how these factors work with other cytoskeletal proteins to generate structurally and functionally diverse actin arrays in cells.
Plasma von Willebrand Factor and Soluble P-Selectin as Indices of Endothelial Damage and Platelet Activation in 1321 Patients With Nonvalvular Atrial Fibrillation
Authors: Conway Dwayne S.G. , Pearce Lesly A. , Chin Bernard S.P. , Hart Robert G. , Lip Gregory Y.H.
Published: October 2002

Background—

Epidemiological studies have identified clinical and echocardiographic factors associated with increased stroke risk in atrial fibrillation (AF), but mechanisms linking these factors to stroke in AF are incompletely understood. We hypothesized that stroke risk factors may be associated with increased endothelial damage/dysfunction and platelet activation among patients with AF.

Methods and Results—

We measured plasma levels of von Willebrand factor (vWF, a marker of endothelial damage/dysfunction) and soluble P-selectin (sP-sel, a marker of platelet activation) by ELISA in 1321 participants in the Stroke Prevention in Atrial Fibrillation (SPAF) III study and related these indices to the presence of stroke risk factors and cardiovascular disease. Age (
P
<0.001), prior cerebral ischemia (
P
<0.01), recent heart failure (
P
<0.001), diabetes (
P
<0.001), and body mass index (
P
<0.001) were independently associated with increased vWF (
r
2
adjusted=9%). Independent associates of increased sP-sel were diabetes (
P
=0.01), peripheral vascular disease (
P
<0.001), and current smoking (
P
=0.01), whereas prior cerebral ischemia (
P
=0.002) and female sex (
P
<0.001) were associated with reduced sP-sel (
r
2
adjusted=4%). Using prospectively validated stroke risk stratification criteria, we observed a significant stepwise increase in vWF from low- to moderate- to high-risk groups (
r
2
adjusted=3%,
P
<0.001), whereas sP-sel remained constant (
P
= 0.24).

Conclusions—

Four recognized risk factors for stroke in AF (advancing age, prior cerebral ischemia, recent heart failure, and diabetes) were independently associated with raised plasma vWF (or endothelial damage/dysfunction), whereas only 1 (diabetes) was associated with increased sP-sel (platelet activation). Further longitudinal studies are now needed to confirm relationships between endothelial damage/dysfunction, platelet activation, and stroke in AF.
An Anatomy of Anatomy
Authors: Weiss Allen S.
Published: October 2002

A new take on Northrup Frye's Anatomy of Criticism celebrating hybridity, montage, and a recontextualized, rewritten, reconceived notion of the “classics.”
Desublimation and Morbidity
Authors: Weiss Allen S.
Published: October 2002

Performative writing—autobiographical and fetishistic—about dolls of all kinds, from Barbie to ritual ancestral figures, from demonic figurines to unmentionable, unrepresentable, uncanny objects.
Climatic Change on the Iberian Peninsula Recorded in a 30,000-Yr Pollen Record from Lake Banyoles
Authors: Pèrez-Obiol Ramon , Julià Ramon
Published: October 2002

The Banyoles lacustrine sequence shows that the vegetational history of the northeastern Iberian Peninsula during the last 30,000 yr follows the North Atlantic pattern of climatic oscillations. The Banyoles pollen diagram, supported by two calibrated 14C dates and nine U/Th dates, shows a clear interstadial event between 30,000 and 27,000 yr B.P., a Pleniglacial period with minor oscillations that ended abruptly ca. 14,420 ± 410 yr B.P., and a late-glacial sequence that records the classical stages described in Northern Europe: the Bølling-Allerød Interstade, the Younger Dryas event at 12,000 yr B.P. (U-series age), and a short warming phase between the Younger Dryas and the last cold event (dated at 11,000 yr B.P., U-series age).