bluuebunny/crossref_metadata_2025 huggingface dataset:
Who Offers Liquidity on Options Markets when Volatility is High?
Authors: Chang Matthew C. , Wu Chung-Fern
Published: November 2012

In this paper, we investigate the relationship between volatility of and liquidity provision through the aggregation of high-frequency data on the stock index option markets of Taiwan. Strong evidence shows the different behaviors of liquidity supply for market makers and nonmarket makers. In addition, evidence demonstrates that nonmarket makers are unwilling to offer liquidity on buy-side when option price is high, but the phenomena are not evident for the market makers. Overall, nonmarket makers provide less liquidity when volatility is high. In contrast, market makers provide the same or more liquidity on the limit order book when volatility is high. Therefore, the market makers play more important a role when market is volatile. The policy implication is that professional market makers on option markets are stable forces to offer liquidity when market is volatile, and it is referable for those pure order-driven option markets without market makers (e.g., Korea Exchange, KRX).
QUANTUM FLUCTUATION DYNAMICS DURING THE TRANSITION OF A MESOSCOPIC BOSONIC GAS INTO A BOSE–EINSTEIN CONDENSATE
Authors: SCHELLE ALEXEJ
Published: November 2012

The condensate number distribution during the transition of a dilute, weakly interacting gas of N = 200 bosonic atoms into a Bose–Einstein condensate is modeled within number conserving master equation theory of Bose–Einstein condensation. Initial strong quantum fluctuations occuring during the exponential cycle of condensate growth reduce in a subsequent saturation stage, before the Bose gas finally relaxes towards the Gibbs–Boltzmann equilibrium.
Discotic liquid crystals of transition metal complexes 47: synthesis of phthalocyanine-fullerene dyads showing spontaneous homeotropic alignment
Authors: Kamei Tenpei , Kato Takayuki , Itoh Eiji , Ohta Kazuchika
Published: November 2012

In previous work, we successfully synthesized the first columnar liquid crystalline 1:1 phthalocyanine(Pc)-fullerene( C60 ) dyad, C12(OMalC60)PcCu (4), showing spontaneous homeotropic alignment, by using Bingel reaction. However, it gave undesirable 2:1 and 3:1 Pc- C60 by-products at the same time, so that the 1:1 Pc- C60 dyad (4) could be obtained in a very low yield (20%). On the other hand, in this work we have prepared novel Pc- C60 dyads, C12(OFbaC60)PcM (8: M = Co (a), Ni (b) and Cu (c)), by using Prato reaction. Very interestingly, it gave almost only the target 1:1 Pc- C60 dyads 8a–8c in very high yields (81–96%) with negligible amount of Pc- C60 by-products. These dyads 8a–8c and the precursor Pc derivatives were characterized by polarizing microscope, differential scanning calorimeter and temperature-dependent X-ray diffractometer. Thus, it was revealed that each of the dyads and precursors shows spontaneous homeotropic alignment in their Coltet mesophase.
Interface States in p-Type GaAs/GaAs1-xBixHeterostructure
Authors: Fuyuki Takuma , Kashiyama Shota , Oe Kunishige , Yoshimoto Masahiro
Published: November 2012

The characteristics of interface states in a GaAs/GaAs1-xBixheterointerface have been evaluated by capacitance–frequency measurements, thermal admittance spectroscopy, and isothermal capacitance transient spectroscopy. The interface states densityDitis evaluated to be approximately 9 ×1011cm-2eV-1for the first time. The large density is probably caused by the fact that the surface of GaAs and GaAs1-xBixare shown to be nonmetallic and metallic, respectively. The interface states density is reduced by half by insertion of a Bi graded layer into the GaAs/p-GaAs1-xBixheterointerface, which is on the same order as other III–V heterointerfaces such as GaAs/GaAs0.97N0.03and In0.5Ga0.5P/Al0.25Ga0.75As.
Switching Properties of Titanium Dioxide Nanowire Memristor
Authors: Nagashima Kazuki , Yanagida Takeshi , Kanai Masaki , Oka Keisuke , Klamchuen Annop , Rahong Sakon , Meng Gang , Horprathum Mati , Xu Bo , Zhuge Fuwei , He Yong , Kawai Tomoji
Published: November 2012

We present the memristive switching properties in a single nanowire device made of titanium dioxide. We constructed the single oxide nanowire device made of titanium dioxide on a Si substrate. First, we confirmed the existence of memristive switching in a 10 nm scale nanowire device. We successfully extracted the carrier-types for memristive switching by utilizing atmosphere control measurements. Although cobalt oxide and nickel oxide showed the p-type behavior reported previously, the present titanium dioxide nanowire memristor exhibited n-type behavior. Our results highlight the fact that carrier-type of memristive switching seems to be consistent with that of a bulk material, but this is in fact somehow contradictive to a model based on precipitation of metals within an oxide matrix. Since, in conventional capacitor-type memristors, it has been impossible to measure the carrier-type in memristive switching because memristive events are buried within a solid, the open-top planar-type “nanowire memristor” is clearly a powerful device for extracting the intrinsic features of memristive switching phenomena.
Microstructure, Growth Mechanism, Magnetoelectricity, and Raman Scattering of Featherlike CoFe2O4–BaTiO3 Nanostructures
Authors: Deng Yu , Zhou Jianxin , Wu Di , Yu Huiqiang , Du Youwei
Published: November 2012

Featherlike (CoFe2O4)0.3–(BaTiO3)0.7 (CFO–BTO) nanostructures were synthesized by a hydrothermal reaction and polymer-assisted deposition. With CFO nanopillars embedded in the BTO matrix, the nanostructures show an average diameter of 250 nm and lengths of up to 5 µm. The microstructure and growth mechanism of the nanostructures were investigated. A large magnetoelectric (ME) coefficient of 51.8 mV cm-1 Oe-1 at room temperature and a strong phonon abnormality between 110 and 140 °C are discussed.
Composites of MgB2with Bi2O3, Bi, Sb2O3, or Sb Obtained by Ex-situ Spark Plasma Sintering
Authors: Badica Petre , Aldica Gheorghe , Burdusel Mihail , Endo Kazuhiro
Published: November 2012

Mixtures of MgB2and metal or oxide additions with starting compositions of (MgB2)(M2O3)x,x= 0.0025, 0.005, 0.015, and (MgB2)(M)y,y= 0.01, M = Bi, Sb, were processed by spark plasma sintering (SPS). As-obtained samples are composites with high density exceeding 94% of the theoretical values. Secondary phases indicate similar reactions for samples with Bi- or Sb-based additions. However, samples show very different superconducting characteristics depending on the addition type and amount. A direct correlation with the melting temperature of the addition could not be revealed, although some aspects will be discussed. From the critical current density (Jc) and irreversibility field (Hirr) enhancement viewpoints, optimum additions are oxides forx=0.0025, 0.005. Both oxides improveJcat high fields, but Sb2O3is effective up to 10 K, whereas Bi2O3is effective up to 30 K. Metal additions decreaseJcandHirrwhen compared with a pristine MgB2sample.
Atmospheric Microplasma Application for Surface Modification of Biomaterials
Authors: Shimizu Kazuo , Fukunaga Hodaka , Tatematsu Shigeki , Blajan Marius
Published: November 2012

Atmospheric microplasma has been intensively studied for applications in various fields, since in this technology the generated field is only 1 kV (approx) under atmospheric pressure and a dielectric barrier discharge gap of 10 to 100 µm. A low discharge voltage atmospheric plasma process is an economical and effective solution for various applications such as indoor air control including sterilization, odor removal, and surface treatment, and would be suitable for medical applications in the field of plasma life sciences. In this paper, we present the application of microplasma for the surface treatment of materials used in medical fields. Moreover, a biomaterial composed of L-lactic acid is used in experiments, which can be biodecomposed in the human body after medical operations. The surface modification process was carried out with active species generated between the microplasma electrodes, which were observed by emission spectrometry. Microplasma treatment of a polymer sheet using Ar as the process gas decreased the contact angle of a water droplet at the surface of the polymer from 78.3 to 45.6° in 10 s, indicating improved surface adhesive characteristics.
Numerical Study of Multichannel Gain and Phase Recovery Dynamics of Quantum-Dot Semiconductor Optical Amplifiers by Solving Coupled Rate Equations
Authors: Kim Jungho
Published: November 2012

We theoretically investigate the effect of multichannel pump injection on the ultrafast gain and phase recovery dynamics of quantum-dot (QD) semiconductor optical amplifiers (SOAs) by solving 10880 coupled rate equations. The ultrafast gain and phase recovery responses induced by three-channel pump injection are calculated compared with the single-channel pump injection. The gain and phase recovery response caused by three-channel pump injection is different from the summation of the three gain and phase recovery responses induced by separate single-channel pump injection. We identify the physical mechanism of the distinct gain and phase recovery responses due to different pump wavelength by considering the interplay between the Lorentzian line shape function and the spectral spacing between the pump and probe beams. The calculation results help to understand the gain and phase recovery dynamics of QD SOAs for multichannel amplification in coarse wavelength division multiplexing (CWDM) applications.
Method for Measuring Anisotropic Electrical Resistivity
Authors: Suzuki Minoru , Katsui Hiromitsu
Published: November 2012

A novel method is presented for measuring anisotropic electrical resistivity. In this method, a pedestal structure is fabricated on a surface of a crystal. Such a single sample enables measurement of anisotropic resistivity tensor elements simultaneously. The pedestal structure can be very small, in which case the measurement provides a more precise evaluation of anisotropic resistivity than ever. This method is exclusively advantageous in the case of laminar materials or thin films. An example is given of a measurement of the high-T
c superconductor Bi2Sr2CaCu2O8+δ.
Perylene and Perylene-Derivative Nano-Cocrystals: Preparation and Physicochemical Property
Authors: Baba Koichi , Konta Sayaka , Oliveira Daniel , Sugai Kenji , Onodera Tsunenobu , Masuhara Akito , Kasai Hitoshi , Oikawa Hidetoshi , Nakanishi Hachiro
Published: November 2012

Organic nano-cocrystals of functional dyes of perylene and a perylene derivative were successfully prepared by the reprecipitation method. The particle sizes, optical properties, and powder X-ray diffraction patterns of nano-cocrystals were evaluated. Typically, the size with size distribution of nano-cocrystals was 55±15 nm when the molar ratio of perylene to the perylene derivative was 50:50. The particular intermolecular electronic interaction between perylene and the perylene derivative in the nano-cocrystal state was observed by absorption and fluorescence spectra measurements. The powder X-ray diffraction pattern analysis confirmed that the structure of nano-cocrystals was different from those prepared from perylene and the perylene derivative. The nano-cocrystal having unique physicochemical properties will be potentially classified as a new type of functional nanomaterial.
Rapid Sterilization of Escherichia coli by Solution Plasma Process
Authors: Andreeva Nina , Ishizaki Takahiro , Baroch Pavel , Saito Nagahiro
Published: November 2012

Solution plasma (SP), which is a discharge in the liquid phase, has the potential for rapid sterilization of water without chemical agents. The discharge showed a strong sterilization performance againstEscherichia colibacteria. The decimal value (Dvalue) of the reduction time forE. coliby this system with an electrode distance of 1.0 mm was estimated to be approximately 1.0 min. Our discharge system in the liquid phase caused no physical damage to theE. coliand only a small increase in the temperature of the aqueous solution. The UV light generated by the discharge was an important factor in the sterilization ofE. coli.
Transient Stress Imaging after Irradiation with a Focused Femtosecond Laser Pulse inside a Single Crystal
Authors: Tochio Takaya , Sakakura Masaaki , Shimotsuma Yasuhiko , Nishi Masayuki , Hirao Kazuyuki , Miura Kiyotaka
Published: November 2012

A focused femtosecond laser pulse inside a single crystal induces anisotropic structural changes, which depend on the atomic arrangement of the crystal. The transient stress after the photoexcitation should be responsible for the structural changes. In this study, we developed a novel transient stress observation system by time-resolved birefringence analysis and observed the relative amplitude and azimuth of the transient stresses after the photoexcitation inside MgO and LiF crystals. The principle and advantage of the observation system are described in this paper by comparing the system with a conventional stress observation method, a crossed-Nicols imaging method.
Stochastic approximation over multidimensional discrete sets with applications to inventory systems and admission control of queueing networks
Authors: Lim Eunji
Published: November 2012

We propose new methods to solve simulation optimization problems over multidimensional discrete sets. The proposed methods are based on extending the objective function from a discrete domain to a continuous domain and applying stochastic approximation to the extended function. The extension of the objective function is constructed as a piecewise linear interpolation of the original objective function over a particular partition of ℝ

d

. The advantage of the proposed approach lies in that stochastic approximation is applied to the extension, not the original function, over ℝ

d

, so the estimated optimal solution at each iteration of the proposed methods is not restricted to be an integer point. Rather, we are free to approach the optimal solution aggressively by moving toward the direction of the steepest descent, thereby skipping over intervening points, thereby resulting in fast convergence in the early stage of the procedures.

We provide a set of sufficient conditions under which the proposed methods guarantee the almost sure (a.s.) convergence to the optimal solution. One of such conditions is the multimodularity or
L
♮
-convexity of the objective function, which arises in various inventory systems and queueing networks with controlled admission. Numerical examples illustrate the effectiveness of the proposed methods in such settings.
Sharpening comparisons via gaussian copulas and semidefinite programming
Authors: Henderson Shane G. , Ehrlichman Samuel M. T.
Published: November 2012

A common problem in operations research involves comparing two system designs through simulation of both systems. The comparison can often be made more accurate through careful control (coupling) of the random numbers that are used in simulating each system, with common random numbers being the standard example. We describe a new approach for coupling the random-number inputs to two systems that involves generating realizations of a Gaussian random vector and then transforming the Gaussian random vector into the desired random-number inputs. We use nonlinear semidefinite programming to select the correlation matrix of the Gaussian random vector, with the goal of sharpening the comparison.
Elaborating intersection and union types
Authors: Dunfield Jana
Published: November 2012

Designing and implementing typed programming languages is hard. Every new type system feature requires extending the metatheory and implementation, which are often complicated and fragile. To ease this process, we would like to provide general mechanisms that subsume many different features.

In modern type systems, parametric polymorphism is fundamental, but intersection polymorphism has gained little traction in programming languages. Most practical intersection type systems have supported only
refinement intersections
, which increase the expressiveness of types (more precise properties can be checked) without altering the expressiveness of terms; refinement intersections can simply be erased during compilation. In contrast,
unrestricted
intersections increase the expressiveness of terms, and can be used to encode diverse language features, promising an economy of both theory and implementation.

We describe a foundation for compiling unrestricted intersection and union types: an elaboration type system that generates ordinary
λ
-calculus terms. The key feature is a Forsythe-like merge construct. With this construct, not all reductions of the source program preserve types; however, we prove that ordinary call-by-value evaluation of the elaborated program corresponds to a type-preserving evaluation of the source program.

We also describe a prototype implementation and applications of unrestricted intersections and unions: records, operator overloading, and simulating dynamic typing.
Superficially substructural types
Authors: Krishnaswami Neelakantan R. , Turon Aaron , Dreyer Derek , Garg Deepak
Published: November 2012

Many substructural type systems have been proposed for controlling access to shared state in higher-order languages. Central to these systems is the notion of a *resource*, which may be split into disjoint pieces that different parts of a program can manipulate independently without worrying about interfering with one another. Some systems support a *logical* notion of resource (such as permissions), under which two resources may be considered disjoint even if they govern the *same* piece of state. However, in nearly all existing systems, the notions of resource and disjointness are fixed at the outset, baked into the model of the language, and fairly coarse-grained in the kinds of sharing they enable.

In this paper, inspired by recent work on "fictional disjointness" in separation logic, we propose a simple and flexible way of enabling any module in a program to create its own custom type of splittable resource (represented as a commutative monoid), thus providing fine-grained control over how the module's private state is shared with its clients. This functionality can be incorporated into an otherwise standard substructural type system by means of a new typing rule we call *the sharing rule*, whose soundness we prove semantically via a novel resource-oriented Kripke logical relation.
Transporting functions across ornaments
Authors: Dagand Pierre-Evariste , McBride Conor
Published: November 2012

Programming with dependent types is a blessing and a curse. It is a blessing to be able to bake invariants into the definition of datatypes: we can finally write correct-by-construction software. However, this extreme accuracy is also a curse: a datatype is the combination of a structuring medium together with a special purpose logic. These domain-specific logics hamper any effort of code reuse among similarly structured data. In this paper, we exorcise our datatypes by adapting the notion of ornament to our universe of inductive families. We then show how code reuse can be achieved by ornamenting functions. Using these functional ornaments, we capture the relationship between functions such as the addition of natural numbers and the concatenation of lists. With this knowledge, we demonstrate how the implementation of the former informs the implementation of the latter: the user can ask the definition of addition to be lifted to lists and she will only be asked the details necessary to carry on adding lists rather than numbers. Our presentation is formalised in a type theory with a universe of datatypes and all our constructions have been implemented as generic programs, requiring no extension to the type theory.
Proof-producing synthesis of ML from higher-order logic
Authors: Myreen Magnus O. , Owens Scott
Published: November 2012

The higher-order logic found in proof assistants such as Coq and various HOL systems provides a convenient setting for the development and verification of pure functional programs. However, to efficiently run these programs, they must be converted (or "extracted") to functional programs in a programming language such as ML or Haskell. With current techniques, this step, which must be trusted, relates similar looking objects that have very different semantic definitions, such as the set-theoretic model of a logic and the operational semantics of a programming language.

In this paper, we show how to increase the trustworthiness of this step with an automated technique. Given a functional program expressed in higher-order logic, our technique provides the corresponding program for a functional language defined with an operational semantics, and it provides a mechanically checked theorem relating the two. This theorem can then be used to transfer verified properties of the logical function to the program.

We have implemented our technique in the HOL4 theorem prover, translating functions to a core subset of Standard ML, and have applied it to examples including functional data structures, a parser generator, cryptographic algorithms, and a garbage collector.
High performance embedded domain specific languages
Authors: Olukotun Kunle
Published: November 2012

Today, all high-performance computer architectures are parallel and heterogeneous; a combination of multiple CPUs, GPUs and specialized processors. This creates a complex programming problem for application developers. Domain-specific languages (DSLs) are a promising solution to this problem because they provide an avenue for application-specific abstractions to be mapped directly to low level architecture-specific programming models providing high programmer productivity and high execution performance.

In this talk I will describe our approach to building high performance DSLs, which is based on embedding in Scala, light-wieght modular staging and a DSL infrastructure called Delite. I will describe how we transform impure functional programs into efficient first-order low-level code using domain specific optimization, parallelism optimization, locality optimization, scalar optimization, and architecture-specific code generation. All optimizations and transformations are implemented in an extensible DSL compiler architecture that minimizes the programmer effort required to develop a new DSL.
Experience report
Authors: Pike Lee , Wegmann Nis , Niller Sebastian , Goodloe Alwyn
Published: November 2012

Embedded domain-specific languages (EDSLs) are an approach for quickly building new languages while maintaining the advantages of a rich metalanguage. We argue in this experience report that the "EDSL approach" can surprisingly ease the task of building a high-assurance compiler. We do not strive to build a fully formally-verified tool-chain, but take a "do-it-yourself" approach to increase our confidence in compiler-correctness without too much effort.
Copilot
is an EDSL developed by Galois, Inc. and the National Institute of Aerospace under contract to NASA for the purpose of runtime monitoring of flight-critical avionics. We report our experience in using type-checking, QuickCheck, and model-checking "off-the-shelf" to quickly increase confidence in our EDSL tool-chain.
Addressing covert termination and timing channels in concurrent information flow systems
Authors: Stefan Deian , Russo Alejandro , Buiras Pablo , Levy Amit , Mitchell John C. , Maziéres David
Published: November 2012

When termination of a program is observable by an adversary, confidential information may be leaked by terminating accordingly. While this termination covert channel has limited bandwidth for sequential programs, it is a more dangerous source of information leakage in concurrent settings. We address concurrent termination and timing channels by presenting a dynamic information-flow control system that mitigates and eliminates these channels while allowing termination and timing to depend on secret values. Intuitively, we leverage concurrency by placing such potentially sensitive actions in separate threads. While termination and timing of these threads may expose secret values, our system requires any thread observing these properties to raise its information-flow label accordingly, preventing leaks to lower-labeled contexts. We implement this approach in a Haskell library and demonstrate its applicability by building a web server that uses information-flow control to restrict untrusted web applications.
Experience report
Authors: Daniels Noah M. , Gallant Andrew , Ramsey Norman
Published: November 2012

Haskell gives computational biologists the flexibility and rapid prototyping of a scripting language, plus the performance of native code. In our experience, higher-order functions, lazy evaluation, and monads really worked, but profiling and debugging presented obstacles. Also, Haskell libraries vary greatly: memoization combinators and parallel-evaluation strategies helped us a lot, but other, nameless libraries mostly got in our way. Despite the obstacles and the uncertain quality of some libraries, Haskell's ecosystem made it easy for us to develop new algorithms in computational biology.
A meta-scheduler for the par-monad
Authors: Foltzer Adam , Kulkarni Abhishek , Swords Rebecca , Sasidharan Sajith , Jiang Eric , Newton Ryan
Published: November 2012

Modern parallel computing hardware demands increasingly specialized attention to the details of scheduling and load balancing across heterogeneous execution resources that may include GPU and cloud environments, in addition to traditional CPUs. Many existing solutions address the challenges of particular resources, but do so in isolation, and in general do not compose within larger systems. We propose a general, composable abstraction for execution resources, along with a continuation-based meta-scheduler that harnesses those resources in the context of a deterministic parallel programming library for Haskell. We demonstrate performance benefits of combined CPU/GPU scheduling over either alone, and of combined multithreaded/distributed scheduling over existing distributed programming approaches for Haskell.
Tales from the jungle
Authors: Sewell Peter
Published: November 2012

We rely on a computational infrastructure that is a densely interwined mass of software and hardware: programming languages, network protocols, operating systems, and processors. It has accumulated great complexity, from a combination of engineering design decisions, contingent historical choices, and sheer scale, yet it is defined at best by prose specifications, or, all too often, just by the common implementations. Can we do better? More specifically, can we apply rigorous methods to this mainstream infrastructure, taking the accumulated complexity seriously, and if we do, does it help? My colleagues and I have looked at these questions in several contexts: the TCP/IP network protocols with their Sockets API; programming language design, including the Java module system and the C11/C++11 concurrency model; the hardware concurrency behaviour of x86, IBM POWER, and ARM multiprocessors; and compilation of concurrent code.

In this talk I will draw some lessons from what did and did not succeed, looking especially at the empirical nature of some of the work, at the social process of engagement with the various different communities, and at the mathematical and software tools we used. Domain-specific modelling languages (based on functional programming ideas) and proof assistants were invaluable for working with the large and loose specifications involved: idioms within HOL4 for TCP, our Ott tool for programming language specification, and Owens's Lem tool for portable semantic definitions, with HOL4, Isabelle, and Coq, for the relaxed-memory concurrency semantics work. Our experience with these suggests something of what is needed to make full-scale rigorous semantics a commonplace reality.
Typing unmarshalling without marshalling types
Authors: Henry Grégoire , Mauny Michel , Chailloux Emmanuel , Manoury Pascal
Published: November 2012

Unmarshalling primitives in statically typed language require, in order to preserve type safety, to dynamically verify the compatibility between the incoming values and the statically expected type. In the context of programming languages based on parametric polymorphism and uniform data representation, we propose a relation of compatibility between (unmarshalled) memory graphs and types. It is defined as constraints over nodes of the memory graph. Then, we propose an algorithm to check the compatibility between a memory graph and a type. It is described as a constraint solver based on a rewriting system. We have shown that the proposed algorithm is sound and semi-complete in presence of algebraic data types, mutable data, polymorphic sharing, cycles, and functional values, however, in its general form, it may not terminate. We have implemented a prototype tailored for the OCaml compiler [17] that always terminates and still seems sufficiently complete in practice.
Deconstraining DSLs
Authors: Jones Will , Field Tony , Allwood Tristan
Published: November 2012

Strongly-typed functional languages provide a powerful framework for embedding Domain-Specific Languages (DSLs). However, building type-safe functions defined over an embedded DSL can introduce application-specific type constraints that end up being imposed on the DSL data types themselves. At best, these constraints are unwieldy and at worst they can limit the range of DSL expressions that can be built. We present a simple solution to this problem that allows application-specific constraints to be specified at the point of use of a DSL expression rather than when the DSL's embedding types are defined. Our solution applies equally to both tagged and tagless representations and, importantly, also works in the presence of higher-rank types.
A traversal-based algorithm for higher-order model checking
Authors: Neatherway Robin P. , Ramsay Steven J. , Ong Chih-Hao Luke
Published: November 2012

Higher-order model checking - the model checking of trees generated by higher-order recursion schemes (HORS) - is a natural generalisation of finite-state and pushdown model checking. Recent work has shown that it can serve as a basis for software model checking for functional languages such as ML and Haskell. In this paper, we introduce
higher-order recursion schemes with cases
(HORSC), which extend HORS with a definition-by-cases construct (to express program branching based on data) and non-determinism (to express abstractions of behaviours). This paper is a study of the
universal HORSC model checking problem for deterministic trivial automata
: does the automaton accept every tree in the tree language generated by the given HORSC? We first characterise the model checking problem by an intersection type system extended with a carefully restricted form of union types. We then present an algorithm for deciding the model checking problem, which is based on the notion of
traversals
induced by the fully abstract game semantics of these schemes, but presented as a goal-directed construction of derivations in the intersection and union type system. We view HORSC model checking as a suitable backend engine for an approach to verifying functional programs. We have implemented the algorithm in a tool called
TravMC
, and demonstrated its effectiveness on a test suite of programs, including abstract models of functional programs obtained via an abstraction-refinement procedure from pattern-matching recursion schemes.
Predicate abstraction of Java programs with collections
Authors: Parízek Pavel , Lhoták OndYej
Published: November 2012

Our goal is to develop precise and scalable verification techniques for Java programs that use collections and properties that depend on their content. We apply the popular approach of predicate abstraction to Java programs and collections. The main challenge in this context is precise and compact modeling of collections that enables practical verification. We define a predicate language for modeling the observable state of Java collections at the interface level. Changes of the state by API methods are captured by weakest preconditions. We adapt existing techniques for construction of abstract programs. Most notably, we designed optimizations based on specific features of the predicate language. We evaluated our approach on Java programs that use collections in advanced ways. Our results show that interesting properties, such as consistency between multiple collections, can be verified using our approach. The properties are specified using logic formulas that involve predicates introduced by our language.
Molecule
Authors: Bocq Sébastien , Daenen Koen
Published: November 2012

Molecule is a domain specific language library embedded in Scala for easing the creation of scalable and modular concurrent applications on the JVM. Concurrent applications are modeled as parallel process networks that exchange information over mobile and type-safe messaging interfaces. In this paper, we present a concurrent programming environment that combines functional and imperative programming. Using a monad, we structure the sequential or parallel coordination of user-level threads, without JVM modifications or compiler support. Our mobile channel interfaces expose reusable and parallelizable higher-order functions, as if they were streams in a lazily evaluated functional programming language. The support for graceful termination of entire process networks is simplified by integrating channel poisoning with monadic exceptions and resource control. Our runtime and system-level interfaces leverage message batching and a novel flow parallel scheduler to limit expensive context switches in multicore environments. We illustrate the expressiveness and performance benefits on a 24-core AMD Opteron machine with three classical examples: a thread ring, a genuine prime sieve and a chameneos-redux.
LEAN
Authors: Huang Jeff , Zhang Charles
Published: November 2012

Debugging concurrent programs is known to be difficult due to scheduling non-determinism. The technique of multiprocessor deterministic replay substantially assists debugging by making the program execution reproducible. However, facing the huge replay traces and long replay time, the debugging task remains stunningly challenging for long running executions. We present a new technique, LEAN, on top of replay, that significantly reduces the complexity of the replay trace and the length of the replay time without losing the determinism in reproducing concurrency bugs. The cornerstone of our work is a redundancy criterion that characterizes the redundant computation in a buggy trace. Based on the redundancy criterion, we have developed two novel techniques to automatically identify and remove redundant threads and instructions in the bug reproduction execution. Our evaluation results with several real world concurrency bugs in large complex server programs demonstrate that LEAN is able to reduce the size, the number of threads, and the number of thread context switches of the replay trace by orders of magnitude, and accordingly greatly shorten the replay time.
Formal specification of a JavaScript module system
Authors: Kang Seonghoon , Ryu Sukyoung
Published: November 2012

The JavaScript programming language, originally developed as a simple scripting language, is now the language of choice for web applications. All the top 100 sites on the web use JavaScript and its use outside web pages is rapidly growing. However, JavaScript is not yet ready for programming in the large: it does not support a module system. Lack of namespaces introduces module patterns, and makes it difficult to use multiple JavaScript frameworks together.

In this paper, we propose a formal specification of a JavaScript module system. A module system for JavaScript will allow safe and incremental development of JavaScript web applications. While the next version of the JavaScript standard proposes a module system, it informally describes its design in prose. We formally specify a module system as an extension to the existing JavaScript language, and rigorously describe its semantics via desugaring to LambdaJS, a prior core calculus for JavaScript. We implement the desugaring process and show its faithfulness using real-world test suites. Finally, we define a set of properties for valid JavaScript programs using modules and formally prove that the proposed module system satisfies the validity properties.
Talk versus work
Authors: Datta Subhajit , Sindhgatta Renuka , Sengupta Bikram
Published: November 2012

IBM's Jazz initiative offers a state-of-the-art collaborative development environment (CDE) facilitating developer interactions around interdependent units of work. In this paper, we analyze development data across two versions of a major IBM product developed on the Jazz platform, covering in total 19 months of development activity, including 17,000+ work items and 61,000+ comments made by more than 190 developers in 35 locations. By examining the relation between developer talk and work, we find evidence that developers maintain a reasonably high level of connectivity with peer developers with whom they share work dependencies, but the span of a developer's communication goes much beyond the known dependencies of his/her work items. Using multiple linear regression models, we find that the number of defects owned by a developer is impacted by the number of other developers (s)he is connected through talk, his/her interpersonal influence in the network of work dependencies, the number of work items (s)he comments on, and the number work items (s)he owns. These effects are maintained even after controlling for workload, role, work dependency, and connection related factors. We discuss the implications of our results for collaborative software development and project governance.
Software data-triggered threads
Authors: Tseng Hung-Wei , Tullsen Dean Michael
Published: November 2012

The data-triggered threads (DTT) programming and execution model can increase parallelism and eliminate redundant computation. However, the initial proposal requires significant architecture support, which impedes existing applications and architectures from taking advantage of this model. This work proposes a pure software solution that supports the DTT model without any hardware support. This research uses a prototype compiler and runtime libraries running on top of existing machines. Several enhancements to the initial software implementation are presented, which further improve the performance.

The software runtime system improves the performance of serial C SPEC benchmarks by 15% on a Nehalem processor, but by over 7X over the full suite of single-thread applications. It is shown that the DTT model can work in conjunction with traditional parallelism. The DTT model provides up to 64X speedup over parallel applications exploiting traditional parallelism.
Execution privatization for scheduler-oblivious concurrent programs
Authors: Huang Jeff , Zhang Charles
Published: November 2012

Making multithreaded execution less non-deterministic is a promising solution to address the difficulty of concurrent programming plagued by the non-deterministic thread scheduling. In fact, a vast category of concurrent programs are scheduler-oblivious: their execution is deterministic, regardless of the scheduling behavior. We present and formally prove a fundamental observation of the privatizability property for scheduler-oblivious programs, that paves the theoretical foundation for privatizing shared data accesses on a path segment. With privatization, the non-deterministic thread interleavings on the privatized accesses are isolated and as the consequence many concurrency problems are alleviated. We further present a path and context sensitive privatization algorithm that safely privatizes the program without introducing any additional program behavior. Our evaluation results show that the privatization opportunity pervasively exists in real world large complex concurrent systems. Through privatization, several real concurrency bugs are fixed and notable performance improvements are also achieved on benchmarks.
A variability-aware module system
Authors: Kästner Christian , Ostermann Klaus , Erdweg Sebastian
Published: November 2012

Module systems enable a divide and conquer strategy to software development. To implement compile-time variability in software product lines, modules can be composed in different combinations. However, this way, variability dictates a dominant decomposition. As an alternative, we introduce a variability-aware module system that supports compile-time variability
inside
a module and its interface. So, each module can be considered a product line that can be type checked in isolation. Variability can crosscut multiple modules. The module system breaks with the antimodular tradition of a global variability model in product-line development and provides a path toward software ecosystems and product lines of product lines developed in an open fashion. We discuss the design and implementation of such a module system on a core calculus and provide an implementation for C as part of the TypeChef project. Our implementation supports variability inside modules from #ifdef preprocessor directives and variable linking at the composition level. With our implementation, we type check all configurations of all modules of the open source product line Busybox with 811~compile-time options, perform linker check of all configurations, and report found type and linker errors -- without resorting to a brute-force strategy.
Constrained kinds
Authors: Tardieu Olivier , Nystrom Nathaniel , Peshansky Igor , Saraswat Vijay
Published: November 2012

Modern object-oriented languages such as X10 require a rich framework for types capable of expressing both value-dependency and genericity, and supporting pluggable, domain-specific extensions. In earlier work, we presented a framework for constrained types in object-oriented languages, parametrized by an underlying constraint system. Types are viewed as formulas C{c} where C is the name of a class or an interface and c is a constraint on the immutable instance state (the properties) of C. Constraint systems are a very expressive framework for partial information. Many (value-)dependent type systems for object-oriented languages can be viewed as constrained types.

This paper extends the constrained types approach to handle type-dependency ("genericity"). The key idea is to introduce constrained kinds: in the same way that constraints on values can be used to define constrained types, constraints on types can define constrained kinds.

We develop a core programming language with constrained kinds. Generic types are supported by introducing type variables---literally, variables with "type" Type---and permitting programs to impose subtyping and equality constraints on such variables. We formalize the type-checking rules and establish soundness.

While the language now intertwines constraints on types and values, its type system remains parametric in the choice of the value constraint system (language and solver). We demonstrate that constrained kinds are expressive and practical and sketch possible extensions with a discussion of the design and implementation of X10.
Exploiting inter-sequence correlations for program behavior prediction
Authors: Wu Bo , Zhao Zhijia , Shen Xipeng , Jiang Yunlian , Gao Yaoqing , Silvera Raul
Published: November 2012

Prediction of program dynamic behaviors is fundamental to program optimizations, resource management, and architecture reconfigurations. Most existing predictors are based on locality of program behaviors, subject to some inherent limitations. In this paper, we revisit the design philosophy and systematically explore a second source of clues: statistical correlations between the behavior sequences of different program entities. Concentrated on loops, it examines the correlations' existence, strength, and values in enhancing the design of program behavior predictors. It creates the first taxonomy of program behavior sequence patterns. It develops a new form of predictors, named sequence predictors, to effectively translate the correlations into large-scope, proactive predictions of program behavior sequences. It demonstrates the usefulness of the prediction in dynamic version selection and loop importance estimation, showing 19% average speedup on a number of real-world utility applications. By taking scope and timing of behavior prediction as the first-order design objectives, the new approach overcomes limitations of existing program behavior predictors, opening up many new opportunities for runtime optimizations at various layers of computing.
Detecting problematic message sequences and frequencies in distributed systems
Authors: Lucas Charles , Elbaum Sebastian , Rosenblum David S.
Published: November 2012

Testing the components of a distributed system is challenging as it requires consideration of not just the state of a component, but also the sequence of messages it may receive from the rest of the system or the environment. Such messages may vary in type and content, and more particularly, in the frequency at which they are generated. All of these factors, in the right combination, may lead to faulty behavior. In this paper we present an approach to address these challenges by systematically analyzing a component in a distributed system to identify specific message sequences and frequencies at which a failure can occur. At the core of the analysis is the generation of a test driver that defines the space of message sequences to be generated, the exploration of that space through the use of dynamic symbolic execution, and the timing and analysis of the generated tests to identify problematic frequencies. We implemented our approach in the context of the popular Robotic Operating System and investigated its application to three systems of increasing complexity.
Open and efficient type switch for C++
Authors: Solodkyy Yuriy , Dos Reis Gabriel , Stroustrup Bjarne
Published: November 2012

Selecting operations based on the run-time type of an object is key to many object-oriented and functional programming techniques. We present a technique for implementing open and efficient type switching on hierarchical extensible data types. The technique is general and copes well with C++ multiple inheritance. To simplify experimentation and gain realistic performance using production-quality compilers and tool chains, we implement a type switch construct as an ISO C++11 library, called Mach7. This library-only implementation provides concise notation and outperforms the visitor design pattern, commonly used for case analysis on types in object-oriented programming. For closed sets of types, its performance roughly equals equivalent code in functional languages, such as OCaml and Haskell. The type-switching code is easier to use and is more expressive than hand-coded visitors are. The library is non-intrusive and circumvents most of the extensibility restrictions typical of the visitor design pattern. It was motivated by applications involving large, typed, abstract syntax trees.