Constraint Handling Rules (CHR) are our proposal to allow more flexibility and application-oriented customization of constraint systems. CHR are a declarative language extension especially designed for writing user-de...
详细信息
Constraint Handling Rules (CHR) are our proposal to allow more flexibility and application-oriented customization of constraint systems. CHR are a declarative language extension especially designed for writing user-defined constraints. CHR are essentially a committed-choice language consisting of multi-headed gurded rules that rewrite constraints into simpler ones until they are solved. In this broad survey we aim at covering all aspects of CHR as they currently present themselves. Going from theory to practice, we will define syntax and semantics for CHR, introduce an important decidable property, confluence, of CHR programs and define a tight integration of CHR with constraint logicprogramming languages. This survey then describes implementations of the language before we review several constraint solvers both traditional and nonstandard ones - written in the CHR language. Finally we introduce two innovative applications that benefited from using CHR. (C) 1998 Elsevier Science Inc. All rights reserved.
Languages that integrate functional and logicprogramming with a complete operational semantics are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction principle of functional l...
详细信息
Languages that integrate functional and logicprogramming with a complete operational semantics are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction principle of functional languages and the resolution principle of logic languages. In this article, we present a partial evaluation scheme for functional logic languages based on an automatic unfolding algorithm which builds narrowing trees. The method is formalized within the theoretical framework established by Lloyd and Shepherdson for the partial deduction of logic programs, which we have generalized for dealing with functional computations. A generic specialization algorithm is proposed which does not depend on the eager or lazy nature of the narrower being used. To the best of our knowledge, this is the first generic algorithm for the specialization of functional logic programs. We study the semantic properties of the transformation and the conditions under which the technique terminates, is sound and complete, and is generally applicable to a wide class of programs. We also discuss the relation to work on partial evaluation in functional programming, term-rewriting systems, and logicprogramming. Finally, we present some experimental results with an implementation of the algorithm which show in practice that the narrowing-driven partial evaluator effectively combines the propagation of partial data structures (by means of logical variables and unification) with better opportunities for optimization (thanks to the functional dimension).
Reasoning about actions and changes often starts with an action theory which is then used for planning, prediction or explanation. In practice it is sometimes not simple to give an immediately available action theory....
详细信息
ISBN:
(纸本)3540649581
Reasoning about actions and changes often starts with an action theory which is then used for planning, prediction or explanation. In practice it is sometimes not simple to give an immediately available action theory. In this paper we will present an abductive methodology for describing action domains. We start with an action theory which is not complete, i.e., has more than one model. Then, after some tests are done, we can abduce a complete action theory. Technically, we use a high level action language to describe incomplete domains and tests. Then, we present a translation from domain descriptions to abductive logic programs. Using tests, we then abductively refine an original domain description to a new one which is closer to the domain in reality. The translation has been shown to be both sound and complete. The result of this paper can be used not only for refinement of domain descriptions but also for abductive planning, prediction and explanation. The methodology presented in this paper has been implemented by an abductive logicprogramming system.
We propose two declarative debuggers of missing answers with respect to C- and S-semantics. The debuggers are proved correct for every logic program. Moreover, they are complete and terminating with respect to a large...
详细信息
ISBN:
(纸本)3540643028
We propose two declarative debuggers of missing answers with respect to C- and S-semantics. The debuggers are proved correct for every logic program. Moreover, they are complete and terminating with respect to a large class of programs, namely acceptable logic programs. The debuggers enhance existing proposals, which suffer from a problem due to the implementation of negation as failure. The proposed solution exploits decision procedures far C- and S-semantics introduced in [9].
We present the core-L-pi fragment of L-pi and its program logic. We illustrate the adequacy of L-pi as a mete-language for jointly defining operational semantics and program logics of languages with concurrent and log...
详细信息
ISBN:
(纸本)3540643028
We present the core-L-pi fragment of L-pi and its program logic. We illustrate the adequacy of L-pi as a mete-language for jointly defining operational semantics and program logics of languages with concurrent and logic features, considering the case of a specification logic for concurrent objects addressing mobile features like creation of objects and channels in a simple way. Specifications are executable by a translation that assigns to every specification a model in the form of a core-L-pi program. We also illustrate the usefulness of this framework in reasoning about systems and their components.
This paper describes a concurrent logic specification language for developing programs that control multiple robots. This language is based on guarded Horn clauses and specifications are automatically transformed into...
详细信息
ISBN:
(纸本)0780344650
This paper describes a concurrent logic specification language for developing programs that control multiple robots. This language is based on guarded Horn clauses and specifications are automatically transformed into concurrent logic programs, yielding executable specifications. They makes it possible to easily implement complex tasks such as concurrency control, communication and multiagent-type problem solving for multiple robots. An experiment on program development for multiple manipulators was undertaken to show advantages of the specification language. The resulting observations are twofold. First, specifications are more abstract and natural than conventional procedure-oriented programs. Second, the amounts of specifications are very shorter than that of the programs developed by the underlying concurrent logicprogramming language. Since transformed concurrent logic programs are then compiled into C programs with little overhead, the proposed language can be useful as a multiple robot programming language with the efficiency for both program execution and development.
One of the most intractable problems in software is getting engineers to consistently use effective methods. The Software Engineering Institute (SEI) has worked on this problem for a number of years and has developed ...
详细信息
One of the most intractable problems in software is getting engineers to consistently use effective methods. The Software Engineering Institute (SEI) has worked on this problem for a number of years and has developed effective methods for addressing it. This paper describes these methods and shows what they have accomplished with several hundred students and working engineers. After first describing the problem of changing engineers' practices, the paper discusses the logic engineers typically follow in deciding what methods to use. Next is a description of the Personal Software Process (PSP) and the Team Software Process (TSP). Finally, the implications of SEI's experiences with the PSP and TSP are described, with particular emphasis on software engineering and computer science education.
We study the notion of binding-time analysis for logic programs. We formalise the unfolding aspect of an on-line partial deduction system as a Prolog program. Using abstract interpretation, we collect information abou...
详细信息
ISBN:
(纸本)3540643028
We study the notion of binding-time analysis for logic programs. We formalise the unfolding aspect of an on-line partial deduction system as a Prolog program. Using abstract interpretation, we collect information about the run-time behaviour of the program. We use this information to make the control decisions about the unfolding at analysis time and to turn the on-line system into an off-line system. We report on some initial experiments.
The proceedings contain 18 papers. The special focus in this conference is on programming Languages and Systems. The topics include: Concurrent constraint programming based on functional programming;a bisimulation met...
ISBN:
(纸本)3540643028
The proceedings contain 18 papers. The special focus in this conference is on programming Languages and Systems. The topics include: Concurrent constraint programming based on functional programming;a bisimulation method for cryptographic protocols;a polyvariant binding-time analysis for off-line partial deduction;complexity of concrete type-inference in the presence of exceptions;an efficient new fixpoint algorithm for distributive constraint systems;reasoning about classes in object-oriented languages;language primitives and type discipline for structured communication-based programming;recursive object types in a logic of object-oriented programs;about modes and states for reactive systems;building a bridge between pointer aliases and program dependences;a complete declarative debugger of missing answers;systematic change of data representation and a generic framework for specialization.
Methods for synthesizing concurrent programs from temporal logic specifications based on the use of a decision procedure for testing temporal satisfiability have been proposed by Emerson and Clarke and by Manna and Wo...
详细信息
Methods for synthesizing concurrent programs from temporal logic specifications based on the use of a decision procedure for testing temporal satisfiability have been proposed by Emerson and Clarke and by Manna and Wolper. An important advantage of these synthesis methods is that they obviate the need to manually compose a program and manually construct a proof of its correctness. One only has to formulate a precise problem specification;the synthesis method then mechanically constructs a correct solution. A serious drawback of these methods in practice, however, is that they suffer from the state explosion problem. To synthesize a concurrent system consisting of K sequential processes, each having N states in its local transition diagram, requires construction of the global product-machine having about N-K global states in general. This exponential growth in K makes it infeasible to synthesize systems composed of more than 2 or 3 processes. In this article, we show how to synthesize concurrent systems consisting of many (i.e., a finite but arbitrarily large number K of) similar sequential processes. Our approach avoids construction of the global product-machine for K processes;instead, it constructs a two-process product-machine for a single pair of generic sequential processes. The method is uniform in K, providing a simple template that can be instantiated for each process to yield a solution for any fixed K. The method is also illustrated on synchronization problems from the literature.
暂无评论