We study the expressive power of non-size increasing recursive definitions over lists. This notion of computation is such that the size of all intermediate results will automatically be bounded by the size of the inpu...
详细信息
ISBN:
(纸本)9781581134506
We study the expressive power of non-size increasing recursive definitions over lists. This notion of computation is such that the size of all intermediate results will automatically be bounded by the size of the input so that the interpretation in a finite model is sound with respect to the standard semantics. Many well-known algorithms with this property such as the usual sorting algorithms are definable in the system in the natural way. The main result is that a characteristic function is definable if and only if it is computable in time O(2(p(n))) for some polynomial p. The method used to establish the lower bound on the expressive power also shows that the complexity becomes polynomial rime if we allow primitive recursion only. This settles art open question posed in [1, 7]. The key tool for establishing upper bounds on the complexity of derivable functions is an interpretation in a finite relational model whose correctness with respect to the standard interpretation is shown using a semantic technique.
We present a process logic for the pi-calculus with the linear/affine type discipline [6, 7, 31, 32, 33, 59, 60]. Built on the preceding studies on logics for programs and processes, simple systems of assertions are d...
详细信息
ISBN:
(纸本)9781581139051
We present a process logic for the pi-calculus with the linear/affine type discipline [6, 7, 31, 32, 33, 59, 60]. Built on the preceding studies on logics for programs and processes, simple systems of assertions are developed, capturing the classes of behaviours ranging from purely functional interactions to those with destructive update, local state and genericity. A central feature of the logic is representation of the behaviour of an environment as the dual of that of a process in an assertion, which is crucial for obtaining compositional proof systems. From the process logic we can derive compositional program logics for various higher-order programming languages, whose soundness is proved via their embeddings into the process logic. In this paper, the key technical framework of the process logic and its applications is presented focussing on pure functional behaviour and a prototypical call-by-value functional language, leaving the full technical development to [27, 26].
Modular programming and modular verification go hand in hand, but most existing logics for concurrency ignore two crucial forms of modularity: higher-order functions, which are essential for building reusable componen...
详细信息
ISBN:
(纸本)9781450323260
Modular programming and modular verification go hand in hand, but most existing logics for concurrency ignore two crucial forms of modularity: higher-order functions, which are essential for building reusable components, and granularity abstraction, a key technique for hiding the intricacies of fine-grained concurrent data structures from the clients of those data structures. In this paper, we present CaReSL, the first logic to support the use of granularity abstraction for modular verification of higher-order concurrent programs. After motivating the features of CaReSL through a variety of illustrative examples, we demonstrate its effectiveness by using it to tackle a significant case study: the first formal proof of (partial) correctness for Hendler et al.'s "flat combining" algorithm.
The construction of natural language interfaces to computers continues to be a major challenge. The need for such interfaces is growing now that speech recognition technology is becoming more readily available, and pe...
详细信息
The construction of natural language interfaces to computers continues to be a major challenge. The need for such interfaces is growing now that speech recognition technology is becoming more readily available, and people cannot speak those computer-oriented formal languages that are frequently used to interact with computer applications. Much of the research related to the design and implementation of natural language interfaces has involved the use of high-level declarative programming languages. This is to be expected as the task is extremely difficult, involving syntactic and semantic analysis of potentially ambiguous input. The use of LISP and Prolog in this area is well documented. However, research involving the relatively new lazy functional programming paradigm is less well known. This paper provides a comprehensive survey of that research.
Space-Filling Curves (SFCs) map a multi-dimensional cellular space into one dimension. Although several algorithms have been introduced that can generate different SFCs, they barely consider deploying SFCs for non-cel...
详细信息
Space-Filling Curves (SFCs) map a multi-dimensional cellular space into one dimension. Although several algorithms have been introduced that can generate different SFCs, they barely consider deploying SFCs for non-cellular spaces. This article presents a new higher-order functional approach that enables a new level of abstraction which separates the SFC representation (i.e. a set of functions that define the SFC) from the algorithms that use it (e.g. SFC generator, point ordering, etc.). We describe the proposed approach and, as example cases, show how different SFCs can be used as the ordering mechanism for generating the K-d trees and R-trees for a set of arbitrarily distributed points using the proposed higher-order representation of the SFCs.
Embedded code pointers (ECPs) are stored handles of functions and continuations commonly seen in low-level binaries as well as functional or higher-order programs. ECPs are known to be very hard to support well in Hoa...
详细信息
Embedded code pointers (ECPs) are stored handles of functions and continuations commonly seen in low-level binaries as well as functional or higher-order programs. ECPs are known to be very hard to support well in Hoare-logic style verification systems. As a result, existing proof-carrying code (PCC) systems have to either sacrifice the expressiveness or the modularity of program specifications, or resort to construction of complex semantic models. In Reynolds's LICS'02 paper, supporting ECPs is listed as one of the main open problems for separation logic. In this paper we present a simple and general technique for solving the ECP problem for Hoare-logic-based PCC systems. By adding a small amount of syntax to the assertion language, we show how to combine semantic consequence relation with syntactic proof techniques. The result is a new powerful framework that can perform modular reasoning on ECPs while still retaining the expressiveness of Hoare logic. We show how to use our techniques to support polymorphism, closures, and other language extensions and how to solve the ECP problem for separation logic. Our system is fully mechanized. We give its complete soundness proof and a full verification of Reynolds's CPS-style "list-append" example in the Coq proof assistant.
Modular programming and modular verification go hand in hand, but most existing logics for concurrency ignore two crucial forms of modularity: higher-order functions, which are essential for building reusable componen...
详细信息
Modular programming and modular verification go hand in hand, but most existing logics for concurrency ignore two crucial forms of modularity: higher-order functions, which are essential for building reusable components, and granularity abstraction, a key technique for hiding the intricacies of fine-grained concurrent data structures from the clients of those data structures. In this paper, we present CaReSL, the first logic to support the use of granularity abstraction for modular verification of higher-order concurrent programs. After motivating the features of CaReSL through a variety of illustrative examples, we demonstrate its effectiveness by using it to tackle a significant case study: the first formal proof of (partial) correctness for Hendler et al.'s "flat combining" algorithm.
Capsules are a clean representation of the state of a computation in higher-order programming languages with effects. Their intent is to simplify and replace the notion of closure. They naturally provide support for f...
详细信息
Capsules are a clean representation of the state of a computation in higher-order programming languages with effects. Their intent is to simplify and replace the notion of closure. They naturally provide support for functional and imperative features, including recursion and mutable bindings, and ensure lexical scoping without the use of closures, heaps, stacks or combinators. We present a comparison of the use of closures and capsules in the semantics of higher-order programming languages with effects. In proving soundness of one to the other, we give a precise account of how capsule environments and closure environments relate to each other.
Mindfulness meditation might improve a variety of cognitive processes, but the available evidence remains fragmented. This preregistered meta-analysis (PROSPERO-CRD42018100320) aimed to provide insight into this hypot...
详细信息
Mindfulness meditation might improve a variety of cognitive processes, but the available evidence remains fragmented. This preregistered meta-analysis (PROSPERO-CRD42018100320) aimed to provide insight into this hypothesis by assessing the effects of brief mindful attention induction on cognition. Articles were retrieved from Pubmed, PsycInfo and Web of Science up until August 1, 2018. A total of 34 studies were included. The outcomes were categorized into four cognitive domains: attentional functioning, memory, executive functioning and higher-order function. A small effect was found across all cognitive domains (Hedges' g = 0.18, 95% IC = 0.07-0.29). Separated analyses for each cognitive domain revealed an effect only in higherorder cognitive functions (k = 10, Hedges' g = 0.35, 95% IC = 0.20-0.50). Results suggest that mindfulness induction improves cognitive performance in tasks involving complex higher-order functions. There was no evidence of publication bias, but studies generally presented many methodological flaws.
暂无评论