It is important that practical data-flow analyzers are backed by reliably proven theoretical results. Abstract interpretation provides a sound mathematical framework and necessary generic properties for an abstract do...
详细信息
It is important that practical data-flow analyzers are backed by reliably proven theoretical results. Abstract interpretation provides a sound mathematical framework and necessary generic properties for an abstract domain to be well-defined and sound with respect to the concrete semantics. In logic programming, the abstract domain Sharing is a standard choice for sharing analysis for both practical work and further theoretical study. In spite of this, we found that there were no satisfactory proofs for the key properties of commutativity and idempotence that are essential for Sharing to be well-defined and that published statements of the soundness of Sharing assume the occurs-check. This paper provides a generalization of the abstraction function for Sharing that can be applied to any language, with or without the occurs-check. Results for soundness, idempotence and commutativity for abstract unification using this abstraction function are proven.
PAN is a general purpose, portable environment for executing logic programs in parallel. It combines a flexible, distributed architecture which is resilient to software and platform evolution with facilities for autom...
详细信息
PAN is a general purpose, portable environment for executing logic programs in parallel. It combines a flexible, distributed architecture which is resilient to software and platform evolution with facilities for automatically extracting and exploiting AND and OR parallelism in ordinary Prolog programs. PAN incorporates a range of compile-time and run-time techniques to deliver the performance benefits of parallel execution while retaining sequential execution semantics. Several examples illustrate the efficiency of the controls that facilitate the execution of logic programs in a distributed manner and identify the class of applications that benefit from distributed platforms like PAN.
A 'functional' query is a query whose answer is always defined and unique i.e. it is either true or false in all models. It has been shown that the expressive powers of the various types of stable models, when...
详细信息
A 'functional' query is a query whose answer is always defined and unique i.e. it is either true or false in all models. It has been shown that the expressive powers of the various types of stable models, when restricted to the class of DATALOG functional queries, do not in practice go beyond those of well-founded semantics, except for the least undefined stable models which, instead, capture the whole boolean hierarchy BH. In this paper we present a 'functional' language which, by means of a disciplined use of negation, achieves the desired level of expressiveness up to BH. Although the semantics of the new language is partial, all atoms in the source program are defined and possibly undefined atoms are introduced in a rewriting phase to increase the expressive power. We show that the language satisfies 'desirable' properties better than classical languages with (unstratified) negation and stable model semantics. We present an algorithm for the evaluation of functional queries and we show that exponential time resolution is required for hard problems only. Finally we present the architecture of a prototype of the language which has been developed.
Program specialisation aims at improving the overall performance of programs by performing source to source transformations. A common approach within functional and logic programming, known respectively as partial eva...
详细信息
Program specialisation aims at improving the overall performance of programs by performing source to source transformations. A common approach within functional and logic programming, known respectively as partial evaluation and partial deduction, is to exploit partial knowledge about the input. It is achieved through a well-automated application of parts of the Burstall-Darlington unfold/fold transformation framework. The main challenge in developing systems is to design automatic control that ensures correctness, efficiency, and termination. This survey and tutorial presents the main developments in controlling partial deduction over the past 10 years and analyses their respective merits and shortcomings. It ends with an assessment of current achievements and sketches some remaining research challenges.
We have implemented Kima, an automated error correction system for concurrent logic programs. Kima corrects near-misses such as wrong variable occurrences in the absence of explicit declarations of program properties....
详细信息
We have implemented Kima, an automated error correction system for concurrent logic programs. Kima corrects near-misses such as wrong variable occurrences in the absence of explicit declarations of program properties. Strong moding/typing and constraint-based analysis are turning out to play fundamental roles in debugging concurrent logic programs as well as in establishing the consistency of communication protocols and data types. Mode/type analysis of Moded Flat GHC is a constraint satisfaction problem with many simple mode/type constraints, and can be solved efficiently. We proposed a simple and efficient technique which, given a non-well-moded/typed program, diagnoses the "reasons" of inconsistency by finding minimal inconsistent subsets of mode/type constraints. Since each constraint keeps track of the symbol occurrence in the program, a minimal subset also tells possible sources of program errors. Kima realizes automated correction by replacing symbol occurrences around the possible sources and recalculating modes and types of the rewritten programs systematically. As long as bugs are near-misses, Kima proposes a rather small number of alternatives that include an intended program. Search space is kept small because the minimal subset confines possible sources of errors in advance. This paper presents the basic algorithm and various optimization techniques implemented in Kima, and then discusses its effectiveness based on quantitative experiments.
Slicing is a program analysis technique originally developed for imperative languages. It facilitates understanding of data flow and debugging. This paper discusses slicing of Constraint logic Programs. Constraint Log...
详细信息
Slicing is a program analysis technique originally developed for imperative languages. It facilitates understanding of data flow and debugging. This paper discusses slicing of Constraint logic Programs. Constraint logic programming (CLP) is an emerging software technology with a growing number of applications. Data flow in constraint programs is not explicit, and for this reason the concepts of slice and the slicing techniques of imperative languages are not directly applicable. This paper formulates declarative notions of slice suitable for CLP. They provide a basis for defining slicing techniques (both dynamic and static) based on variable sharing. The techniques are further extended by using groundness information. A prototype dynamic slicer of CLP programs implementing the presented ideas is briefly described together with the results of some slicing experiments.
We introduce a fixpoint semantics for logic programs with two kinds of negation: an explicit negation and a negation-by-failure. The programs may also be prioritized, that is, their clauses may be arranged in a partia...
详细信息
We introduce a fixpoint semantics for logic programs with two kinds of negation: an explicit negation and a negation-by-failure. The programs may also be prioritized, that is, their clauses may be arranged in a partial order that reflects preferences among the corresponding rules. This yields a robust framework for representing knowledge in logic programs with a considerable expressive power. The declarative semantics for such programs is particularly suitable for reasoning with uncertainty, in the sense that it pinpoints the incomplete and inconsistent parts of the data, and regards the remaining information as classically consistent. As such, this semantics allows to draw conclusions in a non-trivial way, even in cases that the logic programs under consideration are not consistent. Finally, we show that this formalism may be regarded as a simple and flexible process for belief revision.
In this paper we establish the relationship between the syntax and semantics of a fuzzy temporal constraint logic (FTCL) proposed by Cardenas et al. FTCL enables us to express interrelated events by means of fuzzy tem...
详细信息
In this paper we establish the relationship between the syntax and semantics of a fuzzy temporal constraint logic (FTCL) proposed by Cardenas et al. FTCL enables us to express interrelated events by means of fuzzy temporal constraints. Moreover, it provides a resolution principle for performing inferences which take these constraints into account. FTCL is compatible with the theoretical temporal reasoning model proposed by Marin et al. - the Fuzzy Temporal Constraint Networks (FTCN). The main contributions of this paper are, on the one hand, the proofs of the FTCL-deduction and the FTCL-refutation theorems, and, on the other, the proof of the soundness of the refutation by resolution in this formal system, together with an exhaustive study of its completeness.
We present a new program transformation strategy based on the introduction of lists. This strategy is an extension of the tupling strategy which is based on the introduction of tuples of fixed length. The list introdu...
详细信息
Recent research has sought to develop formal languages for business communication as more expressive, flexible and powerful alternatives to current electronic data interchange (EDI) standards, with potential benefits ...
详细信息
Recent research has sought to develop formal languages for business communication as more expressive, flexible and powerful alternatives to current electronic data interchange (EDI) standards, with potential benefits both for business-to-business exchanges in e-commerce and for general intra-organizational communication. A prominent approach in this area has become known as the formal language for business communication (FLBC) and is grounded on speech act theory, event semantics, thematic roles, and first-order logic (FOL). In this paper, we discuss some of the specific technical choices for the representation of messages in the original FLBC framework and propose two modifications. The first eliminates a problematic modal logical component from the representations of messages;the second transforms the message representation into Skolemised clausal form. Focusing on two different computational tasks, we illustrate how existing computational methods can be employed directly on the resulting representation for messages. We also propose an alternative formulation for messages using C-logic and discuss possible extensions to the resulting modified FLBC framework, for example, in establishing whether an exchange is meaningful and in compliance with the setting in which the parties have pre-agreed to operate. Finally, we consider some open problems and identify directions for future developments. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论