bluuebunny/crossref_metadata_2025_split huggingface dataset:
Tower: data structures in Quantum superposition
Authors: Yuan Charles , Carbin Michael 
Published: October 2022

Emerging quantum algorithms for problems such as element distinctness, subset sum, and closest pair demonstrate computational advantages by relying on abstract data structures. Practically realizing such an algorithm as a program for a quantum computer requires an efficient implementation of the data structure whose operations correspond to unitary operators that manipulate quantum superpositions of data.
To correctly operate in superposition, an implementation must satisfy three properties --- reversibility, history independence, and bounded-time execution. Standard implementations, such as the representation of an abstract set as a hash table, fail these properties, calling for tools to develop specialized implementations.
In this work, we present Core Tower, the first language for quantum programming with random-access memory. Core Tower enables the developer to implement data structures as pointer-based, linked data. It features a reversible semantics enabling every valid program to be translated to a unitary quantum circuit.
We present Boson, the first memory allocator that supports reversible, history-independent, and constant-time dynamic memory allocation in quantum superposition.
We also present Tower, a language for quantum programming with recursively defined data structures. Tower features a type system that bounds all recursion using classical parameters as is necessary for a program to execute on a quantum computer.
Using Tower, we implement Ground, the first quantum library of data structures, including lists, stacks, queues, strings, and sets. We provide the first executable implementation of sets that satisfies all three mandated properties of reversibility, history independence, and bounded-time execution.
Bridging the semantic gap between qualitative and quantitative models of distributed systems
Authors: Liu Si , Meseguer Jose , Ölveczky Peter Csaba , Zhang Min , Basin David 
Published: October 2022

Today’s distributed systems must satisfy bothqualitativeandquantitativeproperties. These properties are analyzed using very different formal frameworks: expressive untimed and non-probabilistic frameworks, such as TLA+ and Hoare/separation logics, for qualitative properties; and timed/probabilistic-automaton-based ones, such as Uppaal and Prism, for quantitative ones. This requires developing two quite different models of the same system, without guarantees of semantic consistency between them. Furthermore, it is very hard or impossible torepresentintrinsic features of distributed object systems—such as unbounded data structures, dynamic object creation, and an unbounded number of messages—using finite automata.In this paper we bridge this semantic gap, overcome the problem of manually having to develop two different models of a system, and solve the representation problem by: (i) defining a transformation from a very general class of distributed systems (a generalization of Agha’s actor model) that maps an untimed non-probabilistic distributed system model suitable for qualitative analysis to a probabilistic timed model suitable for quantitative analysis; and (ii) proving the two models semantically consistent. We formalize our models in rewriting logic, and can therefore use the Maude tool to analyze qualitative properties, and statistical model checking with PVeStA to analyze quantitative properties. We have automated this transformation and integrated it, together with the PVeStA statistical model checker, into theActors2PMaudetool. We illustrate the expressiveness of our framework and our tool’s ease of use by automatically transforming untimed, qualitative models of numerous distributed system designs—including an industrial data store and a state-of-the-art transaction system—into quantitative models to analyze and compare the performance of different designs.
Data-driven lemma synthesis for interactive proofs
Authors: Sivaraman Aishwarya , Sanchez-Stern Alex , Chen Bretton , Lerner Sorin , Millstein Todd 
Published: October 2022

Interactive proofs of theorems often require auxiliary helper lemmas to prove the desired theorem. Existing approaches for automatically synthesizing helper lemmas fall into two broad categories. Some approaches are goal-directed, producing lemmas specifically to help a user make progress from a given proof state, but they have limited expressiveness in terms of the lemmas that can be produced. Other approaches are highly expressive, able to generate arbitrary lemmas from a given grammar, but they are completely undirected and hence not amenable to interactive usage.
In this paper, we develop an approach to lemma synthesis that is both goal-directed and expressive.
The key novelty is a technique for reducing lemma synthesis to a data-driven program synthesis problem, whereby examples for synthesis are generated from the current proof state. We also describe a technique to systematically introduce new variables for lemma synthesis, as well as techniques for filtering and ranking candidate lemmas for presentation to the user. We implement these ideas in a tool called lfind, which can be run as a Coq tactic. In an evaluation on four benchmark suites, lfind produces useful lemmas in 68% of the cases where a human prover used a lemma to make progress. In these cases lfind synthesizes a lemma that either enables a fully automated proof of the original goal or that matches the human-provided lemma.
A conceptual framework for safe object initialization: a principled and mechanized soundness proof of the Celsius model
Authors: Blaudeau Clément , Liu Fengyun 
Published: October 2022

An object under initialization does not fulfill its class specification yet and can be unsafe to
use as it may have uninitialized fields. It can sometimes be useful to call methods on such a
partially initialized object in order to compute a complex initial value, or to let the object
escape its constructor in order to create mutually recursive objects. However, inadvertent usage
of uninitialized fields can lead to run-time crashes. Those subtle programming errors are not
statically detected by most modern compilers.
While many other features of object-oriented programming languages have been thoroughly studied
over the years, object initialization lacks a simple, systematic, and principled
treatment. Building on the insights of previous work, we identify a set of four core principles
for safe initialization: monotonicity, authority, stackability, and scopability. We capture the
essence of the principles with a minimal calculus, Celsius, and show that the principles give rise
to a practical initialization system that strikes a balance between expressiveness and
simplicity. The meta-theory of the system is entirely mechanized using the Coq proof assistant. We
believe that our approach based on well-identified core principles sheds new light on the
underlying mechanisms ensuring safety and could serve as a basis for language design when faced
with similar challenges.
Optimal heap limits for reducing browser memory use
Authors: Kirisame Marisa , Shenoy Pranav , Panchekha Pavel 
Published: October 2022

Garbage-collected language runtimes carefully tune heap limits to reduce garbage collection time and memory usage. However, there's a trade-off: a lower heap limit reduces memory use but increases garbage collection time. Classic methods for setting heap limits include manually tuned heap limits and multiple-of-live-size rules of thumb, but it is not clear when one rule is better than another or how to compare them.
We address this problem with a new framework where heap limits are set for multiple heaps at once. Our key insight is that every heap limit rule induces a particular allocation of memory across multiple processes, and this allocation can be sub-optimal. We use our framework to derive an optimal "square-root" heap limit rule, which minimizes total memory usage for any amount of total garbage collection time. Paradoxically, the square-root heap limit rule achieves this coordination without communication: it allocates memory optimally across multiple heaps without requiring any communication between those heaps.
To demonstrate that this heap limit rule is effective, we prototype it for V8, the JavaScript runtime used in Google Chrome, Microsoft Edge, and other browsers, as well as in server-side frameworks like node.js and Deno. On real-world web pages, our prototype achieves reductions of approximately 16.0% of memory usage while keeping garbage collection time constant. On memory-intensive benchmarks, reductions of up to 30.0% of garbage collection time are possible with no change in total memory usage.
Fractional resources in unbounded separation logic
Authors: Dardinier Thibault , Müller Peter , Summers Alexander J. 
Published: October 2022

Many separation logics support fractional permissions to distinguish between read and write access to a heap location, for instance, to allow concurrent reads while enforcing exclusive writes. Fractional permissions extend to composite assertions such as (co)inductive predicates and magic wands by allowing those to be multiplied by a fraction. Typical separation logic proofs require that this multiplication has three key properties: it needs to distribute over assertions, it should permit fractions to be factored out from assertions, and two fractions of the same assertion should be combinable into one larger fraction.
Existing formal semantics incorporating fractional assertions into a separation logic define multiplication semantically (via models), resulting in a semantics in which distributivity and combinability do not hold for key resource assertions such as magic wands, and fractions cannot be factored out from a separating conjunction. By contrast, existing automatic separation logic verifiers define multiplication syntactically, resulting in a different semantics for which it is unknown whether distributivity and combinability hold for all assertions.
In this paper, we present a novel semantics for separation logic assertions that allows states to hold more than a full permission to a heap location during the evaluation of an assertion. By reimposing upper bounds on the permissions held per location at statement boundaries, we retain key properties of separation logic, in particular, the frame rule. Our assertion semantics unifies semantic and syntactic multiplication and thereby reconciles the discrepancy between separation logic theory and tools and enjoys distributivity, factorisability, and combinability. We have formalised our semantics and proved its properties in Isabelle/HOL.
Generic go to go: dictionary-passing, monomorphisation, and hybrid
Authors: Ellis Stephen , Zhu Shuofei , Yoshida Nobuko , Song Linhai 
Published: October 2022

Go is a popular statically-typed industrial programming language. To aid the type safe reuse of code, the
recent Go release (Go 1.18) published early 2022 includes bounded parametric polymorphism via generic types.
Go 1.18 implements generic types using a combination of monomorphisation and call-graph based
dictionary-passing called hybrid. This hybrid approach can be viewed as an optimised form of monomorphisation that
statically generates specialised methods and types based on possible instantiations. A monolithic dictionary
supplements information lost during monomorphisation, and is structured according to the program’s call
graph. Unfortunately, the hybrid approach still suffers from code bloat, poor compilation speed, and limited
code coverage.
In this paper we propose and formalise a new non-specialising call-site based dictionary-passing translation.
Our call-site based translation creates individual dictionaries for each type parameter, with dictionary
construction occurring in place of instantiation, overcoming the limitations of hybrid. We prove it correct using
a novel and general bisimulation up to technique. To better understand how different generics translation
approaches work in practice, we benchmark five translators, Go 1.18, two existing monomorphisation
translators, our dictionary-passing translator, and an erasure translator. Our findings reveal several suggestions for
improvements for Go 1.18— specifically how to overcome the expressiveness limitations of generic Go and
improve compile time and compiled code size performance of Go 1.18.
Compilation of dynamic sparse tensor algebra
Authors: Chou Stephen , Amarasinghe Saman 
Published: October 2022

Many applications, from social network graph analytics to control flow analysis, compute on sparse data that evolves over the course of program execution.
Such data can be represented as dynamic sparse tensors and efficiently stored in formats (data layouts) that utilize pointer-based data structures like block linked lists, binary search trees, B-trees, and C-trees among others.
These specialized formats support fast in-place modification and are thus better suited than traditional, array-based data structures like CSR for storing dynamic sparse tensors.
However, different dynamic sparse tensor formats have distinct benefits and drawbacks, and performing different computations on tensors that are stored in different formats can require vastly dissimilar code that are not straightforward to correctly implement and optimize.
This paper shows how a compiler can generate efficient code to compute tensor algebra operations on dynamic sparse tensors that may be stored in a wide range of disparate formats.
We propose a language for precisely specifying recursive, pointer-based data structures, and we show how this language can express many different dynamic data structures, including all the ones named above as well as many more.
We then describe how, given high-level specifications of such dynamic data structures, a compiler can emit code to efficiently access and compute on dynamic sparse tensors that are stored in the aforementioned data structures.
We evaluate our technique and find it generates efficient dynamic sparse tensor algebra kernels that have performance comparable to, if not better than, state-of-the-art libraries and frameworks such as PAM, Aspen, STINGER, and Terrace.
At the same time, our technique supports a wider range of tensor algebra operations---such as those that simultaneously compute with static and dynamic sparse tensors---than Aspen, STINGER, and Terrace, while also achieving significantly better performance than PAM for those same operations.
Taming transitive redundancy for context-free language reachability
Authors: Lei Yuxiang , Sui Yulei , Ding Shuo , Zhang Qirun 
Published: October 2022

Given an edge-labeled graph, context-free language reachability (CFL-reachability) computes reachable node pairs by deriving new edges and adding them to the graph. The redundancy that limits the scalability of CFL-reachability manifests as redundant derivations, i.e., identical edges can be derived multiple times due to the many paths between two reachable nodes. We observe that most redundancy arises from the derivations involving transitive relations of reachable node pairs. Unfortunately, existing techniques for reducing redundancy in transitive-closure-based problems are either ineffective or inapplicable to identifying and eliminating redundant derivations during on-the-fly CFL-reachability solving.
This paper proposes a scalable yet precision-preserving approach to all-pairs CFL-reachability analysis by taming its transitive redundancy. Our key insight is that transitive relations are intrinsically ordered, and utilizing the order for edge derivation can avoid most redundancy. To address the challenges in determining the derivation order from the dynamically changed graph during CFL-reachability solving, we introduce a hybrid graph representation by combining spanning trees and adjacency lists, together with a dynamic construction algorithm. Based on this representation, we propose a fast and effective partially ordered algorithm POCR to boost the performance of CFL-reachability analysis by reducing its transitive redundancy during on-the-fly solving. Our experiments on context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++ demonstrate the promising performance of POCR. On average, POCR eliminates 98.50% and 97.26% redundant derivations respectively for the value-flow and alias analysis, achieving speedups of 21.48× and 19.57× over the standard CFL-reachability algorithm. We also compare POCR with two recent open-source tools, Graspan (a CFL-reachability solver) and Soufflé (a Datalog engine). The results demonstrate that POCR is over 3.67× faster than Graspan and Soufflé on average for both value-flow analysis and alias analysis.
Veracity: declarative multicore programming with commutativity
Authors: Chen Adam , Fathololumi Parisa , Koskinen Eric , Pincus Jared 
Published: October 2022

There is an ongoing effort to provide programming abstractions that ease the burden of exploiting multicore hardware. Many programming abstractions (
e.g.
, concurrent objects, transactional memory, etc.) simplify matters, but still involve intricate engineering. We argue that some difficulty of multicore programming can be meliorated through a declarative programming style in which programmers directly express the independence of fragments of sequential programs.

In our proposed paradigm, programmers write programs in a familiar, sequential manner, with the added ability to explicitly express the conditions under which code fragments sequentially commute. Putting such commutativity conditions into source code offers a new entry point for a compiler to exploit the known connection between commutativity and parallelism. We give a semantics for the programmer’s sequential perspective and, under a correctness condition, find that a compiler-transformed parallel execution is equivalent to the sequential semantics. Serializability/linearizability are not the right fit for this condition, so we introduce scoped serializability and show how it can be enforced with lock synthesis techniques.
We next describe a technique for automatically verifying and synthesizing commute conditions via a new reduction from our commute blocks to logical specifications, upon which symbolic commutativity reasoning can be performed. We implemented our work in a new language called Veracity, implemented in Multicore OCaml. We show that commutativity conditions can be automatically generated across a variety of new benchmark programs, confirm the expectation that concurrency speedups can be seen as the computation increases, and apply our work to a small in-memory filesystem and an adaptation of a crowdfund blockchain smart contract.
Longitudinal Prediction of Ventricular Arrhythmic Risk in Patients With Arrhythmogenic Right Ventricular Cardiomyopathy
Authors: Carrick Richard T. , te Riele Anneline S.J.M. , Gasperetti Alessio , Bosman Laurens , Muller Steven A. , Pendleton Catherine , Tichnell Crystal , Murray Brittney , Yap Sing-Chien , van den Berg Maarten P. , Wilde Arthur , Zeppenfeld Katja , Hays Allison , Zimmerman Stefan L. , Tandri Harikrishna , Cadrin-Tourigny Julia , van Tintelen Peter , Calkins Hugh , James Cynthia A. , Wu Katherine C. 
Published: October 2022

Background:
The arrhythmogenic right ventricular cardiomyopathy (ARVC) risk calculator stratifies risk for incident sustained ventricular arrhythmias (VA) at the time of ARVC diagnosis. However, included risk factors change over time, and how well the ARVC risk calculator performs at follow-up is unknown.

Methods:
This was a retrospective analysis of patients with definite ARVC and without prior sustained VA. Risk factors for VA including age, nonsustained ventricular tachycardia, premature ventricular complex burden, T-wave inversions on electrocardiogram, cardiac syncope, right ventricular function, therapeutic medication use, and exercise intensity were assessed at the time of 2010 Task Force Criteria based ARVC diagnosis and upon repeat evaluations. Changes in these risk factors were analyzed over 5-year follow-up. The 5-year risk of VA was predicted longitudinally using (1) the baseline ARVC risk calculator prediction, (2) the ARVC risk prediction calculated using updated risk factors, and (3) time-varying Cox regression. Discrimination and calibration were assessed in comparison to observed VA event rates.

Results:
Four hundred eight patients with ARVC experiencing 132 primary VA events were included. Matched comparison of risk factors at baseline versus at 5 years of follow-up revealed decreased burdens of premature ventricular complexes (−1200/day) and nonsustained ventricular tachycardia (−14%). Presence of significant right ventricular dysfunction and number of T-wave inversions on electrocardiogram were unchanged. Observed risk for VA decreased by 13% by 5 years follow-up. The baseline ARVC risk calculator’s ability to predict 5-year VA risk worsened during follow-up (C statistics, 0.83 at diagnosis versus 0.68 at 5 years). Both the updated ARVC risk calculator (C statistics of 0.77) and time-varying Cox regression model (C statistics, 0.77) had strong discrimination. The updated ARVC risk calculator overestimated 5-year VA risk by an average of +6%.

ConclusionS:
Risk factors for VA in ARVC are dynamic, and overall risk for incident sustained VA decreases during follow-up. Up-to-date risk factor assessment improves VA risk stratification.
Childhood Maltreatment and Arterial Stiffness Among Midlife Women
Authors: Carson Mary Y. , Barinas‐Mitchell Emma , Maki Pauline M. , Thurston Rebecca C. 
Published: October 2022

Background
Childhood maltreatment has been associated with arterial stiffness. This relationship has not been examined specifically among women at midlife, a time of increased arterial stiffness in women. This study tested whether childhood maltreatment is associated with arterial stiffness among a cohort of midlife women.

Methods and Results

A total of 162 nonsmoking perimenopausal and postmenopausal women free of clinical cardiovascular disease (mean age, 54 years; 72% White race, 23% Black race, and 5% Asian/Pacific Islander or Mixed race) completed the Child Trauma Questionnaire at baseline. At a follow‐up visit 5 years later, blood pressure and carotid‐femoral pulse wave velocity (a measure of arterial stiffness) were assessed. Relationships between childhood maltreatment and carotid‐femoral pulse wave velocity were tested in linear regression models, adjusting for time between visits, age, race and ethnicity, education, body mass index, heart rate, hypertension medication, and diastolic blood pressure. Seventy‐one women (44% of the sample) met criteria for a history of childhood maltreatment. Women with a history of childhood maltreatment had higher carotid‐femoral pulse wave velocity (B [SE]=0.47 [0.21];
P
=0.03) than women without this history, controlling for time between visits, age, race and ethnicity, education, body mass index, heart rate, hypertension medication, and diastolic blood pressure.

Conclusions
Among these midlife women, childhood maltreatment was associated with arterial stiffness, highlighting the potential long‐term cardiovascular implications of childhood maltreatment.