We present a novel sampling framework for probabilistic programs. The framework combines two recent ideas-control-data separation and logical condition propagation-in a nontrivial manner so that the two ideas boost th...
详细信息
We present a novel sampling framework for probabilistic programs. The framework combines two recent ideas-control-data separation and logical condition propagation-in a nontrivial manner so that the two ideas boost the benefits of each other. We implemented our algorithm on top of Anglican. The experimental results demonstrate our algorithm's efficiency, especially for programs with while loops and rare observations. (c) 2023 Elsevier Inc. All rights reserved.
Weak memory models formalize the inconsistent behaviors that one can expect to observe in multithreaded programs running on modern hardware. In so doing, however, they complicate the already-difficult task of reasonin...
详细信息
Weak memory models formalize the inconsistent behaviors that one can expect to observe in multithreaded programs running on modern hardware. In so doing, however, they complicate the already-difficult task of reasoning about correctness of concurrent code. Worse, they render impotent the sophisticated formal methods that have been developed to tame concurrency, which almost universally assume a strong (i.e., sequentially consistent) memory model. This paper introduces GPS, the first program logic to provide a full-fledged suite of modern verification techniques including ghost state, protocols, and separation logic for high-level, structured reasoning about weak memory. We demonstrate the effectiveness of GPS by applying it to challenging examples drawn from the Linux kernel as well as lock-free data structures. We also define the semantics of GPS and prove in Coq that it is sound with respect to the axiomatic C11 weak memory model.
Type-based amortised resource analysis following Hofmann and Jost where resources are associated with individual elements of data structures and doled out to the programmer under a linear typing discipline-have been s...
详细信息
Type-based amortised resource analysis following Hofmann and Jost where resources are associated with individual elements of data structures and doled out to the programmer under a linear typing discipline-have been successful in providing concrete resource bounds for functional programs, with good support for inference. In this work we translate the idea of amortised resource analysis to imperative pointer-manipulating languages by embedding a logic of resources, based on the affine intuitionistic logic of Bunched Implications, within Separation logic. The Separation logic component allows us to assert the presence and shape of mutable data structures on the heap, while the resource component allows us to state the consumable resources associated with each member of the structure. We present the logic on a small imperative language, based on Java bytecode, with procedures and mutable heap. We have formalised the logic and its soundness property within the Coq proof assistant and extracted a certified verification condition generator. We also describe an proof search procedure that allows generated verification conditions to be discharged while using linear programming to infer consumable resource annotations. We demonstrate the logic on some examples, including proving the termination of in-place list reversal on lists with cyclic tails.
Stone-type duality theorems, which relate algebraic and relational/topological models, are important tools in logic because - in addition to elegant abstraction - they strengthen soundness and completeness to a catego...
详细信息
Stone-type duality theorems, which relate algebraic and relational/topological models, are important tools in logic because - in addition to elegant abstraction - they strengthen soundness and completeness to a categorical equivalence, yielding a framework through which both algebraic and topological methods can be brought to bear on a logic. We give a systematic treatment of Stone-type duality for the structures that interpret bunched logics, starting with the weakest systems, recovering the familiar BI and Boolean BI (BBI), and extending to both classical and intuitionistic Separation logic. We demonstrate the uniformity and modularity of this analysis by additionally capturing the bunched logics obtained by extending BI and BBI with modalities and multiplicative connectives corresponding to disjunction, negation and falsum. This includes the logic of separating modalities (LSM), De Morgan BI (DMBI), Classical BI (CBI), and the sub-classical family of logics extending Bi-intuitionistic (B)BI (Bi(B)BI). We additionally obtain as corollaries soundness and completeness theorems for the specific Kripke-style models of these logics as presented in the literature: for DMBI, the sub-classical logics extending BiBI and a new bunched logic, Concurrent Kleene BI (connecting our work to Concurrent Separation logic), this is the first time soundness and completeness theorems have been proved. We thus obtain a comprehensive semantic account of the multiplicative variants of all standard propositional connectives in the bunched logic setting. This approach synthesises a variety of techniques from modal, substructural and categorical logic and contextualizes the 'resource semantics' interpretation underpinning Separation logic amongst them. This enables the application of algebraic and topological methods to both Separation logic and the systems of bunched logics it is built upon. Conversely, the new notion of indexed frame (generalizing the standard memory model of Separation L
In the paper we suggest an approach to proving global properties of structured states by using languages with special modal operators reflecting an internal structure of these states.
In the paper we suggest an approach to proving global properties of structured states by using languages with special modal operators reflecting an internal structure of these states.
This paper presents a formal framework for compositional reasoning about secure systems. A key insight is to view a trusted system in terms of the interfaces that the various components expose: larger trusted componen...
详细信息
This paper presents a formal framework for compositional reasoning about secure systems. A key insight is to view a trusted system in terms of the interfaces that the various components expose: larger trusted components are built by combining interface calls in known ways;the adversary is confined to the interfaces it has access to, but may combine interface calls without restriction. Compositional reasoning for such systems is based on an extension of rely-guarantee reasoning for system correctness [27,21] to a setting that involves an adversary whose exact program is not known. At a technical level, the paper presents an expressive concurrent programming language with recursive functions for modeling interfaces and a logic of programs in which compositional reasoning principles are formalized and proved sound with respect to trace semantics. The methods are illustrated through a small fragment of an idealized file system.
We propose a new approach to formally describing the requirement for statistical inference and checking whether a program uses the statistical method appropriately. Specifically, we define belief Hoare logic (BHL) for...
详细信息
We propose a new approach to formally describing the requirement for statistical inference and checking whether a program uses the statistical method appropriately. Specifically, we define belief Hoare logic (BHL) for formalizing and reasoning about the statistical beliefs acquired via hypothesis testing. This program logic is sound and relatively complete with respect to a Kripke model for hypothesis tests. We demonstrate by examples that BHL is useful for reasoning about practical issues in hypothesis testing. In our framework, we clarify the importance of prior beliefs in acquiring statistical beliefs through hypothesis testing, and discuss the whole picture of the justification of statistical inference inside and outside the program logic.
Background Workforce development for implementation practice has been identified as a grand challenge in health services. This is due to the embryonic nature of the existing research in this area, few available traini...
详细信息
Background Workforce development for implementation practice has been identified as a grand challenge in health services. This is due to the embryonic nature of the existing research in this area, few available training programs and a general shortage of frontline service staff trained and prepared for practicing implementation in the field. The interest in the role of "implementation support" as a way to effectively build the implementation capacities of the human service sector has therefore increased. However, while frequently used, little is known about the skills and competencies required to effectively provide such support. Main body To progress the debate and the research agenda on implementation support competencies, we propose the role of the "implementation support practitioner" as a concept unifying the multiple streams of research focused on e.g. consultation, facilitation, or knowledge brokering. Implementation support practitioners are professionals supporting others in implementing evidence-informed practices, policies and programs, and in sustaining and scaling evidence for population impact. They are not involved in direct service delivery or management and work closely with the leadership and staff needed to effectively deliver direct clinical, therapeutic or educational services to individuals, families and communities. They may be specialists or generalists and be located within and/or outside the delivery system they serve. To effectively support the implementation practice of others, implementation support practitioners require an ability to activate implementation-relevant knowledge, skills and attitudes, and to operationalize and apply these in the context of their support activities. In doing so, they aim to trigger both relational and behavioral outcomes. This thinking is reflected in an overarching logic outlined in this article. Conclusion The development of implementation support practitioners as a profession necessitates improved concep
暂无评论