Though the potential of linear logic in facilitating reasoning on resource usage has long been recognized, its convincing use in practice is still rare. Recently, Zhu and Xi developed a type system that can effectivel...
Though the potential of linear logic in facilitating reasoning on resource usage has long been recognized, its convincing use in practice is still rare. Recently, Zhu and Xi developed a type system that can effectively support safe memory manipulation through pointers. However, this linear type system does not provide adequate support for resource sharing. As a consequence, it requires that resources be threaded through functions, which can cause serious difficulties in practice (e.g. program modularity may be sacrificed) and thus severely restrict the use of linear types. In this dissertation, we develop a general type-theoretical framework for supporting safe sharing of linear resources. In sequential programming, we first introduce a modality, which we refer to as the sharing modality, in support of resource sharing (with no use of locks). We then develop the underlying type theory for the sharing modality and establish its soundness based on a notion of types with effects. Also, an intimate relation between this modality and the issue of code reentrancy is formally studied in this context. Next, we formalize a concurrent programming language equipped with a linear type system and establish its soundness, which guarantees that many common safety violations (e.g., race conditions and resource corruptions) can never occur during the evaluation of a well-typed program. A novel aspect of this language lies in a formal treatment of linear locks for protecting shared resources. The resources protected by linear locks cannot be leaked, as such locks are themselves a form of resources that must be safely reclaimed after their use. We carry out the type theoretical development in the Applied Type System framework, which makes it standard to accommodate (universally and existentially quantified) dependent types, polymorphic types and also a paradigm of programming with theorem proving. We use the programming language ATS for implementation and present a variety of realisti
This article details advances in a lightweight technology we have evolved to handle post hoc verification in the very large, uncontrolled and rapidly evolving code-bases exemplified by C language open source projects ...
详细信息
This article details advances in a lightweight technology we have evolved to handle post hoc verification in the very large, uncontrolled and rapidly evolving code-bases exemplified by C language open source projects such as the Linux kernel. Successful operation in this context means timeliness, and we are currently treating millions of lines of unrestricted mixed C and assembler source code in a few hours on very modest platforms. The technology is soundly based, in that it delivers false alarms (in a ratio of about 8 to 1 in practice), rather than misses true alarms. Speed of operation is traded off against accuracy via configuration of a program logic tailored to each analysis. The program logic specification language and the theory behind it will be described here.
In this paper we compare three different formalisms that can be used in the area of models for distributed, concurrent and mobile systems. In particular we analyze the relationships between a process calculus, the Fus...
详细信息
In this paper we compare three different formalisms that can be used in the area of models for distributed, concurrent and mobile systems. In particular we analyze the relationships between a process calculus, the Fusion Calculus, graph transformations in the Synchronized Hyperedge Replacement with Hoare synchronization (HSHR) approach and logicprogramming. We present a translation from Fusion Calculus into HSHR (whereas Fusion Calculus uses Milner synchronization) and prove a correspondence between the reduction semantics of Fusion Calculus and HSHR transitions. We also present a mapping from HSHR into a transactional version of logicprogramming and prove that there is a full correspondence between the two formalisms. The resulting mapping from Fusion Calculus to logicprogramming is interesting since it shows the tight analogies between the two formalisms, in particular for handling name generation and mobility. The intermediate step in terms of HSHR is convenient since graph transformations allow for multiple, remote synchronizations, as required by Fusion Calculus semantics.
This paper presents a property of propositional theories under the answer sets semantics (called Equilibrium logic for this general syntax): any theory can always be reexpressed as a strongly equivalent disjunctive lo...
详细信息
This paper presents a property of propositional theories under the answer sets semantics (called Equilibrium logic for this general syntax): any theory can always be reexpressed as a strongly equivalent disjunctive logic program, possibly with negation in the head. We provide two different proofs for this result: one involving a syntactic transformation, and one that constructs a program starting from the countermodels of the theory in the intermediate logic of here-and-there.
In this paper, we present a framework for the semantics and the computation of aggregates in the context of logicprogramming. In our study, an aggregate can be an arbitrary interpreted second order predicate or funct...
详细信息
In this paper, we present a framework for the semantics and the computation of aggregates in the context of logicprogramming. In our study, an aggregate can be an arbitrary interpreted second order predicate or function. We define extensions of the Kripke-Kleene, the well-founded and the stable semantics for aggregate programs. The semantics is based on the concept of a three-valued immediate consequence operator of an aggregate program. Such an operator approximates the standard two-valued immediate consequence operator of the program, and induces a unique Kripke-Kleene model, a unique well-founded model and a collection of stable models. We study different ways of defining such operators and thus obtain a framework of semantics, offering different trade-offs between precision and tractability. In particular, we investigate conditions on the operator that guarantee that the computation of the three types of semantics remains on the same level as for logic programs without aggregates. Other results show that, in practice, even efficient three-valued immediate consequence operators which are very low in the precision hierarchy, still provide optimal precision.
In this paper, we present our proposal to Constraint Functional logicprogramming over Finite Domains (CFLP(FD)) with a lazy functional logicprogramming language which seamlessly embodies finite domain (FD) constrain...
详细信息
In this paper, we present our proposal to Constraint Functional logicprogramming over Finite Domains (CFLP(FD)) with a lazy functional logicprogramming language which seamlessly embodies finite domain (FD) constraints. This proposal increases the expressiveness and power of constraint logicprogramming over finite domains (CLP(FD)) by combining functional and relational notation, curried expressions, higher-order functions, patterns, partial applications, non-determinism, lazy evaluation, logical variables, types, domain variables, constraint composition, and finite domain constraints. We describe the syntax of the language, its type discipline, and its declarative and operational semantics. We also describe TOY(FD), an implementation for CFLP(FD), and a comparison of our approach with respect to CLP(FD) from a programming point of view, showing the new features we introduce. And, finally, we show a performance analysis which demonstrates that our implementation is competitive with respect to existing CLP(FD) systems and that clearly outperforms the closer approach to CFLP(FD).
Control flow compilation is a hybrid between classical WAM compilation and meta-call, limited to the compilation of non-recursive clause bodies. This approach is used successfully for the execution of dynamically gene...
详细信息
Control flow compilation is a hybrid between classical WAM compilation and meta-call, limited to the compilation of non-recursive clause bodies. This approach is used successfully for the execution of dynamically generated queries in an inductive logicprogramming setting (ILP). Control flow compilation reduces compilation times up to an order of magnitude, without slowing down execution. A lazy variant of control flow compilation is also presented. By compiling code by need, it removes the overhead of compiling unreached code (a frequent phenomenon in practical ILP settings), and thus reduces the size of the compiled code. Both dynamic compilation approaches have been implemented and were combined with query packs, an efficient ILP execution mechanism. It turns out that locality of data and code is important for performance. The experiments reported in the paper show that lazy control flow compilation is superior in both artificial and real life settings.
We have studied the update operator circle plus(1) defined for update sequences by Eiter et al. without tautologies and we have observed that it satisfies an interesting property(1). This property, which we call Weak ...
详细信息
We have studied the update operator circle plus(1) defined for update sequences by Eiter et al. without tautologies and we have observed that it satisfies an interesting property(1). This property, which we call Weak Independence of Syntax (WIS), is similar to one of the postulates proposed by Alchourron, Gardenfors, and Makinson (AGM);only that in this case it applies to nonmonotonic logic. In addition, we consider other five additional basic properties about update programs and we show that circle plus(1) satisfies them. This work continues the analysis of the AGM postulates with respect to the circle plus(1) operator under a refined view that considers N-2 as a monotonic logic which allows us to expand our understanding of answer sets. Moreover, N-2 helped us to derive an alternative definition of circle plus(1) avoiding the use of unnecessary extra atoms.
暂无评论