bluuebunny/crossref_metadata_2025 huggingface dataset:
Fumigating mature spruce branches with SO2: effects on net photosynthesis and stomatal conductance
Authors: Meng Fan-Rui , Cox R.M. , Arp Paul A.
Published: August 2009

Branches on mature red spruce trees (Picearubens Sarg.) were fumigated with SO2 in late summer of 1990 and 1991. There were four SO2 treatment levels (0, 0.1, 0.2, and 0.4 ppm) and 12 fumigation chambers. Each treatment was replicated on three neighboring trees. Net photosynthesis and stomatal conductance of current-year foliage were determined with a Li-Cor photosynthesis system. Rates of foliar SO2 absorption were estimated using regression models, with leaf temperature, relative humidity, atmospheric CO2 concentrations, and photosynthetically active radiation as predictors. Fumigation effects became visible in terms of needle yellowing and browning after a few weeks of treatment. Effects on net photosynthesis and stomatal conductance were generally negative and in direct proportion with cumulative foliar SO2 absorption. It was found that, in shade-adapted foliage, visible symptoms were delayed, and stomatal conductance was slightly stimulated at low SO2 levels. In other foliage, leaf yellowing and browning occurred earlier, and stomatal conductance was depressed. Net photosynthesis was depressed at about the same rate regardless of branch position. Foliage subjected to high SO2 concentration treatments did not recover from SO2 damage 1 year after treatment: needles had fallen off the twigs, and needle and twig length of new foliage was reduced.
Natural variation and genetic parameters in Fraser fir for growth and Christmas tree traits
Authors: Arnold R.J. , Jett J.B. , McKeand S.E.
Published: August 2009

Open-pollinated progeny trials of Fraser fir (Abiesfraseri (Pursh) Poir.) assessed at 8 years provided genetic parameter estimates for growth, Christmas tree quality traits, and wholesale value at harvest age. Significant variation was found between and within nine different seed sources. Estimated individual tree heritabilities of important traits ranged from a low of 0.13 for USDA Christmas tree grade to a moderate value of 0.33 for crown diameter. Heritabilities within the better performing seed sources tended to be higher. Of the two traits that determine wholesale value, USDA grade and height class, the latter proved to have the greater influence, both phenotypically and genetically. Genetic correlations of early age height growth with 8-year total height, height class, USDA Christmas tree grade, and individual tree wholesale value proved favorable and strong (range of 0.57–0.96). In combination with moderate heritabilities for early growth traits, such correlations provide potential for effective early age selections in Fraser fir Christmas trees.
Single- and multiple-trait index selection efficiencies in Fraser fir Christmas trees
Authors: Arnold R.J. , Bridgwater F.E. , Jett J.B.
Published: August 2009

Selection methods for Abiesfraseri (Pursh) Poir. for Christmas tree wholesale value were evaluated based on parameters from the species' first genetic field test. For single-trait individual selection, combined individual plus family selection at half rotation age (4 years) on total height (HT4) gave the greatest estimated full rotation (8-year) retail value (VALUE) gain of 24.3%. The best 8-year trait, crown diameter, resulted in a gain of only 22.4%. Incorporation of family mean information together with individual values in the selection process was important in maximizing gains. Only 8-year stem straightness (STR8) had unfavorable genetic and phenotypic correlations with other traits. With multitrait combined optimum index selection, use of Kempthorne restrictions to prevent adverse change in this trait seriously limited gains in other 8-year traits. Severity of this limitation increased for younger age indices, and for those with fewer traits. Unrestricted combined optimum indices offered substantial VALUE gain advantages and only small decreases in STR8. Initial selection among seed sources also increased VALUE gain, despite decreasing the effective additive genetic variation. VALUE gains through initial source selection exceeded gain reductions from the genetic variation decreases. The optimum selection strategy, with 30.5% VALUE gain, involved initial source selection followed by unrestricted combined optimum index selection on HT4, and 4-year density. Though slightly below the maximum, this strategy would provide substantial economic and technical advantage in conducting field tests.
Turn-location parameters for a continuous landing model. I. Road tangents
Authors: Greulich Francis E.
Published: August 2009

Timber harvesting operations often employ continuous landings on or along truck road right-of-ways. During the harvest-unit design process forest engineers describe the spatial distribution of turns with respect to a proposed landing by distribution parameters such as average yarding distance and average yarding slope. In this two-part paper these parameters and others are derived for a continuous landing model. In this first paper, parameters are derived and applied to a continuous landing located on or along a road center-line tangent. In the second paper, a similar development is applied to a continuous landing located on or along the circular curve of a road.
Turn-location parameters for a continuous landing model. II. Circular curves
Authors: Greulich Francis E.
Published: August 2009

Timber harvesting operations often employ continuous landings on or along truck road right-of-ways. During the harvest-unit design process forest engineers describe the spatial distribution of turns with respect to a proposed landing by distribution parameters such as average yarding distance and average yarding slope. In this two-part paper these parameters and others are derived for a continuous landing model. In the first paper, parameters were derived and applied to a continuous landing located on or along a road center-line tangent. In this second paper, a similar development is applied to a continuous landing located on or along the circular curve of a road.
The effects of thinning and broadcast burning on sporocarp production of hypogeous fungi
Authors: Waters Jeffrey R. , McKelvey Kevin S. , Zabel Cynthia J. , Oliver William W.
Published: August 2009

The objectives of our study were to determine the effects of commercial thinning and broadcast burning on sporocarp production of hypogeous ectomycorrhizal (HEM) fungi. At two sites in northeastern California, Jennie Springs (JS) and Swain Mountain (SM), we compared HEM sporocarp production among units that had been heavily thinned, moderately thinned, and unthinned. At one of those sites, JS, we also compared sporocarp production between units that had been broadcast burned and units left unburned. Sporocarps were sampled in 1992, 10 years after thinning and 9 years after burning occurred at JS, and 17 years after thinning occurred at SM. Total relative frequency and biomass of sporocarps did not differ significantly among thin levels at either site, or between burn levels at JS. There was, however, significant association between thin level and frequencies of the most common genera at JS, suggesting that thinning significantly affected the composition of HEM fungi. The association between burn level and frequencies of the most common genera was also significant, but less pronounced than the association between thin level and the frequencies of common genera.
Evaluation of eight forest fertilizer response estimators by means of a simulation study
Authors: McWilliams E.R.G. , Burk T.E.
Published: August 2009

not available
ANYONE CAN BUILD CHUA'S CIRCUIT: HANDS-ON-EXPERIENCE WITH CHAOS THEORY FOR HIGH SCHOOL STUDENTS
Authors: GANDHI GAURAV , CSEREY GYÖRGY , ZBROZEK JOHN , ROSKA TAMÁS
Published: August 2009

Chaos is a physical and mathematical phenomenon discovered by E. Lorenz in 1963. The first simple electronic implementation had been invented by L. O. Chua in 1984. This electronic circuit, called Chua's circuit was designed for ease of implementation. In the current brief we will explain chaos by building Chua's chaotic circuit using our Chua's circuit kit with inexpensive components. For readers without access to an oscilloscope, this paper proposes the use of a laptop/Personal Computer to capture the voltage waveforms generated from the circuit and plot the waveforms on a computer screen using a virtual oscilloscope software provided by the authors. The kit is available, the software is downloadable.
NECESSITY FROM CHANCE: SELF-ORGANIZED REPLICATION OF SYMMETRIC PATTERNS THROUGH SYMMETRIC RANDOM INTERACTIONS
Authors: BARBÉ ANDRÉ
Published: August 2009

We present an algorithm, completely random in nature, that, without invoking a fitness function or purposeful design, produces symmetric replicas in a population of so-called cellicules. Cellicules consist of "cells" arranged in a structure with geometric symmetry S. Each cell has one of two possible states, thus defining a state-configuration pattern on a cellicule. The algorithm acts recurrently on a population of cellicules, possibly randomly initialized, through a random "copying interaction" between two randomly selected cellicules that first undergo a random reorientation in accordance with the symmetry S. The dynamics of the algorithm is analyzed in detail for several symmetries. This shows that it is a random walk with absorbing states which correspond to a population in which all cellicules have an identical S-symmetric configuration pattern. We discuss some aspects concerning the evolution of cellicule-populations under mixing and mutation, and some variations on the basic algorithm.
SADDLE QUANTITIES AND CYCLICITY OF 2-POLYCYCLE
Authors: ZHAO LIQIN , WANG XUEXING
Published: August 2009

We study the bifurcation of limit cycles in the neighborhood of a 2-polycycle through two hyperbolic saddles with both hyperbolicity ratios being 1. The cyclicity is expressed as an explicit function of saddle quantities. Our results can be applied to the case when both connections are broken under perturbations.
DETERMINISTIC LEARNING OF NONLINEAR DYNAMICAL SYSTEMS
Authors: WANG CONG , CHEN TIANRUI , CHEN GUANRONG , HILL DAVID J.
Published: August 2009

In this paper, we investigate the problem of identifying or modeling nonlinear dynamical systems undergoing periodic and period-like (recurrent) motions. For accurate identification of nonlinear dynamical systems, the persistent excitation condition is normally required to be satisfied. Firstly, by using localized radial basis function networks, a relationship between the recurrent trajectories and the persistence of excitation condition is established. Secondly, for a broad class of recurrent trajectories generated from nonlinear dynamical systems, a deterministic learning approach is presented which achieves locally-accurate identification of the underlying system dynamics in a local region along the recurrent trajectory. This study reveals that even for a random-like chaotic trajectory, which is extremely sensitive to initial conditions and is long-term unpredictable, the system dynamics of a nonlinear chaotic system can still be locally-accurate identified along the chaotic trajectory in a deterministic way. Numerical experiments on the Rossler system are included to demonstrate the effectiveness of the proposed approach.
A PARAMETER-SPACE OF A CHUA SYSTEM WITH A SMOOTH NONLINEARITY
Authors: ALBUQUERQUE HOLOKX A. , RECH PAULO C.
Published: August 2009

In this paper we investigate, via numerical simulations, the parameter space of the set of autonomous differential equations of a Chua oscillator, where the piecewise-linear function usually taken to describe the nonlinearity of the Chua diode was replaced by a cubic polynomial. As far as we know, we are the first to report that this parameter-space presents islands of periodicity embedded in a sea of chaos, scenario typically observed only in discrete-time models until recently. We show that these islands are self-similar, and organize themselves in period-adding bifurcation cascades.
DYNAMICS OF A SIMPLIFIED LORENZ SYSTEM
Authors: SUN KEHUI , SPROTT J. C.
Published: August 2009

A simplified Lorenz system with one bifurcation parameter is investigated by a detailed theoretical analysis as well as dynamic simulation, including some basic dynamical properties, Lyapunov exponent spectra, fractal dimension, bifurcations and routes to chaos. The results show that this system has complex dynamics with interesting characteristics.
STABILITY AND BIFURCATION IN A LOGISTIC EQUATION WITH PIECEWISE CONSTANT ARGUMENTS
Authors: ZHANG CHUNRUI , ZHENG BAODONG , ZHANG YAZHUO
Published: August 2009

A logistic equation with piecewise constant arguments is investigated. Firstly, the linear stability of the model is studied. It is found that there exists a Hopf bifurcation when the parameter passes a critical value. Then the explicit algorithm for determining the direction of the Hopf bifurcation and the stability of the bifurcating periodic solution is derived by using the normal form method and center manifold theorem. Finally, computer simulations are performed to illustrate the analytical results found.
MIDPOINT DIAGRAM IN BILLIARDS
Authors: LI XIAOJUN , LI YONGAN , BAI JINTAO , LI XIAONIU
Published: August 2009

An interesting phenomenon in billiards was found. If the midpoints of every segment of a straight line in trajectory of a billiard were taken, they will form an interesting diagram which we call midpoint diagram. After research on several kinds of billiards, it was discovered that midpoint diagram which is made up of several discrete points corresponds to the periodic behavior of the billiard, and the midpoint diagram made up of lines corresponds to quasi-periodic behavior, while the midpoint diagram made up of large numbers of dispersion points corresponds to chaotic behavior. The midpoint diagram can be used to describe the dynamical behavior of billiards.
AN ERGODIC THEORY OF CONSCIOUSNESS
Authors: BOYARSKY ABRAHAM , GÓRA PAWEŁ
Published: August 2009

It has been suggested that the properties of "integration" and "differentiation" are necessary for the emergence of consciousness. We present a dynamical system model that is based on these two conditions. The collection of neurons are partitioned into clusters on which we define a map that reflects the communication between clusters. Such a map displays the forward and backward circuitry between clusters in a probabilistic manner. The presence of "re-entry" guarantees that the map is sufficiently complex, that is, nonlinear and chaotic, to possess numerous invariant sets of clusters, which are referred to as agglomerations. We suggest that an agglomeration that is mixing characterizes a conscious state. The model establishes a theoretical framework that may structure and encourage experimental work.
EXAMPLES OF FORCED SYMMETRY-BREAKING TO HETEROCLINIC CYCLES AND NETWORKS IN THREE-DIMENSIONAL EUCLIDEAN-INVARIANT SYSTEMS
Authors: PARKER M. J. , GOMES M. G. M. , STEWART I. N.
Published: August 2009

In [Parker et al., 2008a] group theory was employed to prove the existence of homoclinic cycles in forced symmetry-breaking of simple (SC), face-centered (FCC), and body-centered (BCC) cubic planforms. In this paper we extend this classification demonstrating that more elaborate heteroclinic cycles and networks can arise through the same process. Our methods naturally generate graphs that represent possible heteroclinic cycles and networks. The results do not depend on the representation of the symmetry group and are thus quite general.

This study is motivated by pattern formation in three dimensions which occur in reaction–diffusion systems, certain nonlinear optical systems and the polyacrylamide methylene blue oxygen reaction. This work extends previous work by Parker et al. [2006, 2008a, 2008b] and Hou and Golubitsky [1997].
POLYCHRONOUS WAVEFRONT COMPUTATIONS
Authors: IZHIKEVICH EUGENE M. , HOPPENSTEADT FRANK C.
Published: August 2009

There is great interest in methods for computing that do not involve digital machines. Many computational paradigms were inspired by brain research, such as Boolean neuronal logic [McCulloch & Pitts, 1943], the perceptron [Rosenblatt, 1958], attractor neural networks [Hopfield, 1982] and cellular neural nets [Chua & Yang, 1988]. All these paradigms abstract biological circuits to artificial neural networks, i.e. interconnected units (neurons) that perform computations based on the connections between the units (synapses). Here we present a novel computational framework based on polychronous wavefront dynamics. It is entirely different from an artificial neural network paradigm, rather it is based on temporal and spatial patterns of activity in pulse-propagating media and their interaction with transponders, which create pulses in response to receiving appropriate inputs, e.g. two coincident input pulses. A pulse propagates as a circular wave from its source to other transponders. Computations result from interactions between transponders, and they are encoded by the exact physical locations of transponders and by precise timings of pulses. We illustrate temporal pattern recognition, reverberating memory, temporal signal analysis and basic logical operations using polychronous wavefront computations. This work reveals novel principles for designing nanoscale computational devices.
CENTER PROBLEM AND MULTIPLE HOPF BIFURCATION FOR THE Z6-EQUIVARIANT PLANAR POLYNOMIAL VECTOR, FIELDS OF DEGREE 5
Authors: LIU YIRONG , LI JIBIN
Published: August 2009

This paper proves that a Z6-equivariant planar polynomial vector field of degree 5 has at least six symmetric centers, if and only if it is a Hamiltonian vector field. The characterization of a center problem is completely solved. The shortened expressions of the first four Lyapunov constants are given. Under small Z6-equivariant perturbations, the conclusion that the perturbed system has at least 24 limit cycles with the scheme 〈 4 ∐ 4 ∐ 4 ∐ 4 ∐ 4 ∐ 4〉 is rigorously proved. Two schemes of distributions of limit cycles are given.
Language constructs for transactional memory
Authors: Harris Tim
Published: August 2009

Building concurrent shared-memory data structures is a notoriously difficult problem, and so the widespread move to multi-core and multi-processor hardware has led to increasing interest in language constructs that may make concurrent programming easier. One technique that has been studied widely is the use of atomic blocks built over transactional memory (TM): the programmer marks a section of code as atomic, and the language implementation speculatively executes it using transactions. Transactions can run in parallel so long as they access different data.

In this talk I'll introduce some of the challenges that I've seen in building robust implementations of this idea. What are the language design choices that exist? What language features can be used inside atomic blocks, and where can atomic blocks occur? Which uses of atomic blocks should be considered correct, and which uses should be considered "racy"? What are the likely impacts of different design choices on performance? What are the impacts on flexibility for the language implementer, and what are the impacts on flexibility to the programmer using these constructs?

I'll argue that one way of trying to resolve these questions is to be rigorous about keeping the ideas of atomic blocks and TM separate; in practice they've often been conflated (not least in languages that I've worked on). I'll argue that, when thinking about atomic blocks, we should keep a wide range of possible implementations in mind (for example, TM, lock inference, or simply control over pre-emption). Similarly, when thinking about TM, we should recognize that it can be exposed to programmers through a wide range of abstractions and language constructs.
A calculus of atomic actions
Authors: Elmas Tayfun , Qadeer Shaz , Tasiran Serdar
Published: August 2009

We present a proof calculus and method for the static verification of assertions and procedure specifications in shared-memory concurrent programs. The key idea in our approach is to use atomicity as a proof tool and to simplify the verification of assertions by rewriting programs to consist of larger atomic actions. We propose a novel, iterative proof style in which alternating use of abstraction and reduction is exploited to compute larger atomic code blocks in a sound manner. This makes possible the verification of assertions in the transformed program by simple sequential reasoning within atomic blocks, or significantly simplified application of existing concurrent program verification techniques such as the Owicki-Gries or rely-guarantee methods. Our method facilitates a clean separation of concerns where at each phase of the proof, the user worries only about only either the sequential properties or the concurrency control mechanisms in the program. We implemented our method in a tool called QED. We demonstrate the simplicity and effectiveness of our approach on a number of benchmarks including ones with intricate concurrency protocols.
Modular code generation from synchronous block diagrams
Authors: Lublinerman Roberto , Szegedy Christian , Tripakis Stavros
Published: August 2009

We study modular, automatic code generation from hierarchical block diagrams with synchronous semantics. Such diagrams are the fundamental model behind widespread tools in the embedded software domain, such as Simulink and SCADE. Code is modular in the sense that it is generated for a given composite block independently from context (i.e., without knowing in which diagrams the block is to be used) and using minimal information about the internals of the block. In previous work, we have shown how modular code can be generated by computing a set of interface functions for each block and a set of dependencies between these functions that is exported along with the interface. We have also introduced a quantified notion of modularity in terms of the number of interface functions generated per block, and showed how to minimize this number, which is essential for scalability. Finally, we have exposed the fundamental trade-off between modularity and reusability (set of diagrams the block can be used in).

In this paper we explore another trade-off: modularity vs. code size. We show that our previous technique, although it achieves maximal reusability and is optimal in terms of modularity, may result in code replication and therefore large code sizes, something often unacceptable in an embedded system context. We propose to remedy this by generating code with no replication, and show that this generally results in some loss of modularity. We show that optimizing modularity while maintaining maximal reusability and zero replication is an intractable problem (NP-complete). We also show that this problem can be solved using a simple iterative procedure that checks satisfiability of a sequence of propositional formulas. We report on a new prototype implementation and experimental results. The latter demonstrate the practical interest in our methods.
Verifying liveness for asynchronous programs
Authors: Ganty Pierre , Majumdar Rupak , Rybalchenko Andrey
Published: August 2009

Asynchronous or 'event-driven' programming is a popular technique to efficiently and flexibly manage concurrent interactions. In these programs, the programmer can post tasks that get stored in a task buffer and get executed atomically by a non-preemptive scheduler at a future point. We give a decision procedure for the fair termination property of asynchronous programs. The fair termination problem asks, given an asynchronous program and a fairness condition on its executions, does the program always terminate on fair executions? The fairness assumptions rule out certain undesired bad behaviors, such as where the scheduler ignores a set of posted tasks forever, or where a non-deterministic branch is always chosen in one direction. Since every liveness property reduces to a fair termination property, our decision procedure extends to liveness properties of asynchronous programs. Our decision procedure for the fair termination of asynchronous programs assumes all variables are finite-state. Even though variables are finite-state, asynchronous programs can have an unbounded stack from recursive calls made by tasks, as well as an unbounded task buffer of pending tasks. We show a reduction from the fair termination problem for asynchronous programs to fair termination problems on Petri Nets, and our main technical result is a reduction of the latter problem to Presburger satisfiability. Our decidability result is in contrast to multithreaded recursive programs, for which liveness properties are undecidable. While we focus on fair termination, we show our reduction to Petri Nets can be used to prove related properties such as fair nonstarvation (every posted task is eventually executed) and safety properties such as boundedness (find a bound on the maximum number of posted tasks that can be in the task buffer at any point).
A foundation for flow-based program matching
Authors: Brunel Julien , Doligez Damien , Hansen René Rydhof , Lawall Julia L. , Muller Gilles
Published: August 2009

Reasoning about program control-flow paths is an important functionality of a number of recent program matching languages and associated searching and transformation tools. Temporal logic provides a well-defined means of expressing properties of control-flow paths in programs, and indeed an extension of the temporal logic CTL has been applied to the problem of specifying and verifying the transformations commonly performed by optimizing compilers. Nevertheless, in developing the Coccinelle program transformation tool for performing Linux collateral evolutions in systems code, we have found that existing variants of CTL do not adequately support rules that transform subterms other than the ones matching an entire formula. Being able to transform any of the subterms of a matched term seems essential in the domain targeted by Coccinelle.

In this paper, we propose an extension to CTL named CTLVW (CTL with variables and witnesses) that is a suitable basis for the semantics and implementation of the Coccinelles program matching language. Our extension to CTL includes existential quantification over program fragments, which allows metavariables in the program matching language to range over different values within different control-flow paths, and a notion of witnesses that record such existential bindings for use in the subsequent program transformation process. We formalize CTL-VW and describe its use in the context of Coccinelle. We then assess the performance of the approach in practice, using a transformation rule that fixes several reference count bugs in Linux code.
SPEED
Authors: Gulwani Sumit , Mehra Krishna K. , Chilimbi Trishul
Published: August 2009

This paper describes an inter-procedural technique for computing symbolic bounds on the number of statements a procedure executes in terms of its scalar inputs and user-defined quantitative functions of input data-structures. Such computational complexity bounds for even simple programs are usually disjunctive, non-linear, and involve numerical properties of heaps. We address the challenges of generating these bounds using two novel ideas.

We introduce a proof methodology based on multiple counter instrumentation (each counter can be initialized and incremented at potentially multiple program locations) that allows a given linear invariant generation tool to compute linear bounds individually on these counter variables. The bounds on these counters are then composed together to generate total bounds that are non-linear and disjunctive. We also give an algorithm for automating this proof methodology. Our algorithm generates complexity bounds that are usually precise not only in terms of the computational complexity, but also in terms of the constant factors.

Next, we introduce the notion of user-defined quantitative functions that can be associated with abstract data-structures, e.g., length of a list, height of a tree, etc. We show how to compute bounds in terms of these quantitative functions using a linear invariant generation tool that has support for handling uninterpreted functions. We show application of this methodology to commonly used data-structures (namely lists, list of lists, trees, bit-vectors) using examples from Microsoft product code. We observe that a few quantitative functions for each data-structure are usually sufficient to allow generation of symbolic complexity bounds of a variety of loops that iterate over these data-structures, and that it is straightforward to define these quantitative functions.

The combination of these techniques enables generation of precise computational complexity bounds for real-world examples (drawn from Microsoft product code and C++ STL library code) for some of which it is non-trivial to even prove termination. Such automatically generated bounds are very useful for early detection of egregious performance problems in large modular codebases that are constantly being changed by multiple developers who make heavy use of code written by others without a good understanding of their implementation complexity.
Automatic modular abstractions for linear constraints
Authors: Monniaux David P.
Published: August 2009

We propose a method for automatically generating abstract transformers for static analysis by abstract interpretation. The method focuses on linear constraints on programs operating on rational, real or floating-point variables and containing linear assignments and tests.

In addition to loop-free code, the same method also applies for obtaining least fixed points as functions of the precondition, which permits the analysis of loops and recursive functions. Our algorithms are based on new quantifier elimination and symbolic manipulation techniques.

Given the specification of an abstract domain, and a program block, our method automatically outputs an implementation of the corresponding abstract transformer. It is thus a form of program transformation.

The motivation of our work is data-flow synchronous programming languages, used for building control-command embedded systems, but it also applies to imperative and functional programming.
Bidirectionalization for free! (Pearl)
Authors: Voigtländer Janis
Published: August 2009

A bidirectional transformation consists of a function get that takes a source (document or value) to a view and a function put that takes an updated view and the original source back to an updated source, governed by certain consistency conditions relating the two functions. Both the database and programming language communities have studied techniques that essentially allow a user to specify only one of get and put and have the other inferred automatically. All approaches so far to this bidirectionalization task have been syntactic in nature, either proposing a domain-specific language with limited expressiveness but built-in (and composable) backward components, or restricting get to a simple syntactic form from which some algorithm can synthesize an appropriate definition for put. Here we present a semantic approach instead. The idea is to take a general-purpose language, Haskell, and write a higher-order function that takes (polymorphic) get-functions as arguments and returns appropriate put-functions. All this on the level of semantic values, without being willing, or even able, to inspect the definition of get, and thus liberated from syntactic restraints. Our solution is inspired by relational parametricity and uses free theorems for proving the consistency conditions. It works beautifully.
A cost semantics for self-adjusting computation
Authors: Ley-Wild Ruy , Acar Umut A. , Fluet Matthew
Published: August 2009

Self-adjusting computation is an evaluation model in which programs can respond efficiently to small changes to their input data by using a change-propagation mechanism that updates computation by re-building only the parts affected by changes. Previous work has proposed language techniques for self-adjusting computation and showed the approach to be effective in a number of application areas. However, due to the complex semantics of change propagation and the indirect nature of previously proposed language techniques, it remains difficult to reason about the efficiency of self-adjusting programs and change propagation.

In this paper, we propose a cost semantics for self-adjusting computation that enables reasoning about its effectiveness. As our source language, we consider a direct-style λ-calculus with first-class mutable references and develop a notion of trace distance for source programs. To facilitate asymptotic analysis, we propose techniques for composing and generalizing concrete distances via trace contexts (traces with holes). We then show how to translate the source language into a self-adjusting target language such that the translation (1) preserves the extensional semantics of the source programs and the cost of from-scratch runs, and (2) ensures that change propagation between two evaluations takes time bounded by their relative distance. We consider several examples and analyze their effectiveness by considering upper and lower bounds.
Copy-on-write in the PHP language
Authors: Tozawa Akihiko , Tatsubori Michiaki , Onodera Tamiya , Minamide Yasuhiko
Published: August 2009

PHP is a popular language for server-side applications. In PHP, assignment to variables copies the assigned values, according to its so-called
copy-on-assignment
semantics. In contrast, a typical PHP implementation uses a
copy-on-write
scheme to reduce the copy overhead by delaying copies as much as possible. This leads us to ask if the semantics and implementation of PHP coincide, and actually this is not the case in the presence of sharings within values. In this paper, we describe the copy-on-assignment semantics with three possible strategies to copy values containing sharings. The current PHP implementation has inconsistencies with these semantics, caused by its naïve use of copy-on-write. We fix this problem by the novel
mostly copy-on-write
scheme, making the copy-on-write implementations faithful to the semantics. We prove that our copy-on-write implementations are correct, using bisimulation with the copy-on-assignment semantics.
Positive supercompilation for a higher order call-by-value language
Authors: Jonsson Peter A. , Nordlander Johan
Published: August 2009

Previous deforestation and supercompilation algorithms may introduce accidental termination when applied to call-by-value programs. This hides looping bugs from the programmer, and changes the behavior of a program depending on whether it is optimized or not. We present a supercompilation algorithm for a higher-order call-by-value language and we prove that the algorithm both terminates and preserves termination properties. This algorithm utilizes strictness information for deciding whether to substitute or not and compares favorably with previous call-by-name transformations.
Compositional shape analysis by means of bi-abduction
Authors: Calcagno Cristiano , Distefano Dino , O'Hearn Peter , Yang Hongseok
Published: August 2009

This paper describes a compositional shape analysis, where each procedure is analyzed independently of its callers. The analysis uses an abstract domain based on a restricted fragment of separation logic, and assigns a collection of Hoare triples to each procedure; the triples provide an over-approximation of data structure usage. Compositionality brings its usual benefits -- increased potential to scale, ability to deal with unknown calling contexts, graceful way to deal with imprecision -- to shape analysis, for the first time.

The analysis rests on a generalized form of abduction (inference of explanatory hypotheses) which we call
bi-abduction
. Bi-abduction displays abduction as a kind of inverse to the frame problem: it jointly infers anti-frames (missing portions of state) and frames (portions of state not touched by an operation), and is the basis of a new interprocedural analysis algorithm. We have implemented our analysis algorithm and we report case studies on smaller programs to evaluate the quality of discovered specifications, and larger programs (e.g., an entire Linux distribution) to test scalability and graceful imprecision.
Unifying type checking and property checking for low-level code
Authors: Condit Jeremy , Hackett Brian , Lahiri Shuvendu K. , Qadeer Shaz
Published: August 2009

We present a unified approach to type checking and property checking for low-level code. Type checking for low-level code is challenging because type safety often depends on complex, program-specific invariants that are difficult for traditional type checkers to express. Conversely, property checking for low-level code is challenging because it is difficult to write concise specifications that distinguish between locations in an untyped program's heap. We address both problems simultaneously by implementing a type checker for low-level code as part of our property checker.

We present a low-level formalization of a C program's heap and its types that can be checked with an SMT solver, and we provide a decision procedure for checking type safety. Our type system is flexible enough to support a combination of nominal and structural subtyping for C, on a per-structure basis. We discuss several case studies that demonstrate the ability of this tool to express and check complex type invariants in low-level C code, including several small Windows device drivers.
Local rely-guarantee reasoning
Authors: Feng Xinyu
Published: August 2009

Rely-Guarantee reasoning is a well-known method for verification of shared-variable concurrent programs. However, it is difficult for users to define rely/guarantee conditions, which specify threads' behaviors over the whole program state. Recent efforts to combine Separation Logic with Rely-Guarantee reasoning have made it possible to hide thread-local resources, but the shared resources still need to be globally known and specified. This greatly limits the reuse of verified program modules.

In this paper, we propose LRG, a new Rely-Guarantee-based logic that brings local reasoning and information hiding to concurrency verification. Our logic, for the first time, supports a frame rule over rely/guarantee conditions so that specifications of program modules only need to talk about the resources used locally, and the verified modules can be reused in different threads without redoing the proof. Moreover, we introduce a new hiding rule to hide the resources shared by a subset of threads from the rest in the system. The support of information hiding not only improves the modularity of Rely-Guarantee reasoning, but also enables the sharing of dynamically allocated resources, which requires adjustment of rely/guarantee conditions.
State-dependent representation independence
Authors: Ahmed Amal , Dreyer Derek , Rossberg Andreas
Published: August 2009

Mitchell's notion of representation independence is a particularly useful application of Reynolds' relational parametricity -- two different implementations of an abstract data type can be shown contextually equivalent so long as there exists a relation between their type representations that is preserved by their operations. There have been a number of methods proposed for proving representation independence in various pure extensions of System F (where data abstraction is achieved through existential typing), as well as in Algol- or Java-like languages (where data abstraction is achieved through the use of local mutable state). However, none of these approaches addresses the interaction of existential type abstraction and local state. In particular, none allows one to prove representation independence results for generative ADTs -- i.e. ADTs that both maintain some local state and define abstract types whose internal representations are dependent on that local state.

In this paper, we present a syntactic, logical-relations-based method for proving representation independence of generative ADTs in a language supporting polymorphic types, existential types, general recursive types, and unrestricted ML-style mutable references. We demonstrate the effectiveness of our method by using it to prove several interesting contextual equivalences that involve a close interaction between existential typing and local state, as well as some well-known equivalences from the literature (such as Pitts and Stark's "awkward" example) that have caused trouble for previous logical-relations-based methods.

The success of our method relies on two key technical innovations. First, in order to handle generative ADTs, we develop a possible-worlds model in which relational interpretations of types are allowed to grow over time in a manner that is tightly coupled with changes to some local state. Second, we employ a step-indexed stratification of possible worlds, which facilitates a simplified account of mutable references of higher type.
Modeling abstract types in modules with open existential types
Authors: Montagu Benoît , Rémy Didier
Published: August 2009

We propose F-zip, a calculus of open existential types that is an extension of System F obtained by decomposing the introduction and elimination of existential types into more atomic constructs. Open existential types model modular type abstraction as done in module systems. The static semantics of F-zip adapts standard techniques to deal with linearity of typing contexts, its dynamic semantics is a small-step reduction semantics that performs extrusion of type abstraction as needed during reduction, and the two are related by subject reduction and progress lemmas. Applying the Curry-Howard isomorphism, F-zip can be also read back as a logic with the same expressive power as second-order logic but with more modular ways of assembling partial proofs. We also extend the core calculus to handle the double vision problem as well as type-level and term-level recursion. The resulting language turns out to be a new formalization of (a minor variant of) Dreyer's internal language for recursive and mixin modules.
Focusing on pattern matching
Authors: Krishnaswami Neelakantan R.
Published: August 2009

In this paper, we show how pattern matching can be seen to arise from a proof term assignment for the focused sequent calculus. This use of the Curry-Howard correspondence allows us to give a novel coverage checking algorithm, and makes it possible to give a rigorous correctness proof for the classical pattern compilation strategy of building decision trees via matrices of patterns.
Relaxed memory models
Authors: Boudol Gérard , Petri Gustavo
Published: August 2009

Memory models define an interface between programs written in some language and their implementation, determining which behaviour the memory (and thus a program) is allowed to have in a given model. A minimal guarantee memory models should provide to the programmer is that well-synchronized, that is, data-race free code has a standard semantics. Traditionally, memory models are defined axiomatically, setting constraints on the order in which memory operations are allowed to occur, and the programming language semantics is implicit as determining some of these constraints. In this work we propose a new approach to formalizing a memory model in which the model itself is part of a weak operational semantics for a (possibly concurrent) programming language. We formalize in this way a model that allows write operations to the store to be buffered. This enables us to derive the ordering constraints from the weak semantics of programs, and to prove, at the programming language level, that the weak semantics implements the usual interleaving semantics for data-race free programs, hence in particular that it implements the usual semantics for sequential code.
The semantics of progress in lock-based transactional memory
Authors: Guerraoui Rachid , Kapalka Michal
Published: August 2009

Transactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This paper is the first to formally define the progress semantics of lockbased TMs, which are considered the most effective in practice.

We use our semantics to reduce the problems of reasoning about the correctness and computability power of lock-based TMs to those of simple try-lock objects. More specifically, we prove that checking the progress of any set of transactions accessing an arbitrarily large set of shared variables can be reduced to verifying a simple property of each individual (logical) try-lock used by those transactions. We use this theorem to determine the correctness of state-of-the-art lock-based TMs and highlight various configuration ambiguities. We also prove that lock-based TMs have consensus number 2. This means that, on the one hand, a lock-based TM cannot be implemented using only read-write memory, but, on the other hand, it does not need very powerful instructions such as the commonly used compare-and-swap.

We finally use our semantics to formally capture an inherent trade-off in the performance of lock-based TM implementations. Namely, we show that the space complexity of every lock-based software TM implementation that uses invisible reads is at least exponential in the number of objects accessible to transactions.
Types and higher-order recursion schemes for verification of higher-order programs
Authors: Kobayashi Naoki
Published: August 2009

We propose a new verification method for temporal properties of higher-order functional programs, which takes advantage of Ong's recent result on the decidability of the model-checking problem for higher-order recursion schemes (HORS's). A program is transformed to an HORS that generates a tree representing all the possible event sequences of the program, and then the HORS is model-checked. Unlike most of the previous methods for verification of higher-order programs, our verification method is sound and complete. Moreover, this new verification framework allows a smooth integration of abstract model checking techniques into verification of higher-order programs. We also present a type-based verification algorithm for HORS's. The algorithm can deal with only a fragment of the properties expressed by modal mu-calculus, but the algorithm and its correctness proof are (arguably) much simpler than those of Ong's game-semantics-based algorithm. Moreover, while the HORS model checking problem is n-EXPTIME in general, our algorithm is linear in the size of HORS, under the assumption that the sizes of types and specification formulas are bounded by a constant.
Verifying distributed systems
Authors: Ridge Thomas
Published: August 2009

This work develops an integrated approach to the verification of behaviourally rich programs, founded directly on operational semantics. The power of the approach is demonstrated with a state-of-the-art verification of a core piece of distributed infrastructure, involving networking, a filesystem, and concurrent OCaml code. The formalization is in higher-order logic and proof support is provided by the HOL4 theorem prover.

Difficult verification problems demand a wide range of techniques. Here these include ground and symbolic evaluation, local reasoning, separation, invariants, Hoare-style assertional reasoning, rely/guarantee, inductive reasoning about protocol correctness, multiple refinement, and linearizability. While each of these techniques is useful in isolation, they are even more so in combination. The first contribution of this paper is to present the operational approach and describe how existing techniques, including all those mentioned above, may be cleanly and precisely integrated in this setting.

The second contribution is to show how to combine verifications of individual library functions with arbitrary and unknown user code in a compositional manner, focusing on the problems of private state and encapsulation.

The third contribution is the example verification itself. The infrastructure must behave correctly under arbitrary patterns of host and network failure, whilst for performance reasons the code also includes data races on shared state. Both features make the verification particularly challenging.