Reasoning about Prolog programs: From modes through types to assertions

We provide here a systematic comparative study of the relative strength and expressive power of a number of methods for program analysis of Prolog. Among others we show that these methods can be arranged in the following hierarchy: mode analysis type analysis monotonic properties nonmonotonic run-time properties. We also discuss a method allowing us to prove global run-time properties.     

Reasoning about programs

This paper describes a theorem prover that embodies knowledge about programming constructs, such as numbers, arrays, lists, and expressions. The program can reason about these concepts and is used as part of a program verification system that uses the Floyd-Naur explication of program semantics. It is implemented in the qa4 language; the qa4 system allows many pieces of strategic knowledge, each expressed as a small program, to be coordinated so that a program stands forward when it is relevant to the problem at hand. The language allows clear, concise representation of this sort of knowledge. The qa4 system also has special facilities for dealing with commutative functions, ordering relations, and equivalence relations; these features are heavily used in this deductive system. The program interrogates the user and asks his advice in the course of a proof. Verifications have been found for Hoare's FIND program, a real-number division algorithm, and some sort programs, as well as for many simpler algorithms. Additional theorems have been proved about a pattern matcher and a version of Robinson's unification algorithm. The appendix contains a complete, annotated listing of the deductive system and annotated traces of several of the deductions performed by the system.     

Reasoning about faulty quantum programs

We show how to use a programming language for formally describing and reasoning about errors in quantum computation. The formalisation is based on the concept of performing the correct operation with probability at least p, and the erroneous one with probability at most 1 − p. We apply the concept to two examples: Bell’s inequalities and the Deutsch–Jozsa quantum algorithm. The former is a fundamental thought experiment aimed at showing that Quantum Mechanics is not “local and realist”, and it is used in quantum cryptography protocols. We study it assuming faulty measurements, and we derive hardware reliability conditions that must be satisfied in order for the experiment to support its conclusions. The latter is a quantum algorithm for efficiently solving a classification problem for Boolean functions. The algorithm solves the problem with no error, but when we introduce faulty operations it becomes a two-sided error algorithm. Reasoning is accomplished via standard programming laws and quantum laws.     

Reasoning about programs in continuation-passing style

Plotkin's _v -calculus for call-by-value programs is weaker than the -calculus for the same programs in continuation-passing style (CPS). To identify the call-by-value axioms that correspond to on CPS terms, we define a new CPS transformation and an inverse mapping, both of which are interesting in their own right. Using the new CPS transformation, we determine the precise language of CPS terms closed under -transformations, as well as the call-by-value axioms that correspond to the so-called administrative -reductions on CPS terms. Using the inverse mapping, we map the remaining and equalities on CPS terms to axioms on call-by-value terms. On the pure (constant free) set of -terms, the resulting set of axioms is equivalent to Moggi's computational -calculus. If the call-by-value language includes the control operatorsabort andcall-with-current-continuation, the axioms are equivalent to an extension of Felleisenet al.'s _v -C-calculus and to the equational subtheory of Talcott's logic IOCC.This article is a revised and extended version of the conference paper with the same title [42]. The technical report of the same title contains additional material.The authors were supported in part by NSF grant CCR 89-17022 and by Texas ATP grant 91-003604014.     

From Prolog III to Prolog IV: The Logic of Constraint Programming Revisited

Constraint programming languages stem from the integration of constraints in conditional rules. By taking a close look at the design choices made for Prolog IV, the author retraces the general evolution of this recent and novel paradigm, from its roots in inference systems and optimization, to its applications in model building and problem solving.     

Reasoning about plan revision in BDI agent programs

Facilities for handling plan execution failures are essential for agents which must cope with the effects of nondeterministic actions, and some form of failure handling can be found in most mature agent programming languages and platforms. While such features simplify the development of more robust agents, they make it hard to reason about the execution of agent programs, e.g., to verify their correctness. In this paper, we present an approach to the verification of agent programs which admit exceptional executions. We consider executions of the BDI-based agent programming language 3APL in which plans containing non-executable actions can be revised using plan revision rules, and present a logic for reasoning about normal and exceptional executions of 3APL programs. We provide a complete axiomatization for the logic and, using a simple example, show how to express properties of 3APL programs as formulas of the logic.     

Reasoning about probabilistic sequential programs in a probabilistic logic

We introduce a notion of strong monotonicity of probabilistic predicate transformers. This notion enables us to establish a normal form theorem for monotone probabilistic predicate transformers. Three other healthiness conditions, namely, conjunctivity, disjunctivity and continuity for probabilistic predicate transformers are also examined, and they are linked to strong monotonicity. A notion of probabilistic refinement index is proposed, and it provides us with a continuous strength spectrum of refinement relations which may be used to describe more flexible refinement between probabilistic programs. A notion of probabilistic correctness is introduced too. We give a probabilistic weakest-precondition, choice and game semantics to the contract language, and present a probabilistic generalization of the winning strategy theorem. Received: 16 April 2002 / 20 January 2003 RID="a" ID="a" This work was partly supported by the National Key Project for Fundamental Research of China (Grant No: 1998030905) and the National Foundation of Natural Sciences of China (Grant No: 60273003)     

Reasoning about designs through frequent patterns mining

This paper deals with reasoning about designs based on their internal structures in the form of attributed hypergraphs. A database containing hypergraphs representing solutions of similar design tasks is searched for frequently occurring subgraphs. On the basis of search results the quality of newly created solutions is evaluated. Moreover the syntactic reasoning rules are specified by the designer on the basis of the design knowledge concerning a given task and used to evaluate hypergraphs representing new solutions.     

Meta-rules: Reasoning about control

How can we insure that knowledge embedded in a program is applied effectively? Traditionally the answer to this question has been sought in different problem solving paradigms and in different approaches to encoding and indexing knowledge. Each of these is useful with a certain variety of problem, but they all share a common problem: they become ineffective in the face of a sufficiently large knowledge base. How then can we make it possible for a system to continue to function in the face of a very large number of plausibly useful chunks of knowledge?In response to this question we propose a framework for viewing issues of knowledge indexing and retrieval, a framework that includes what appears to be a useful perspective on the concept of a strategy. We view strategies as a means of controlling invocation in situations where traditional selection mechanisms become ineffective. We examine ways to effect such control, and describe meta-rules, a means of specifying strategies which offers a number of advantages. We consider at some length how and when it is useful to reason about control, and explore the advantages meta-rules offer for doing this.     

From goals to manipulator programs

We describe an approach to robot programming that supports task-oriented specifications of manipulation activities. Plan formation and program generation techniques are used to transform task specifications into executable programs for various robots. The plan formation operates on a database of knowledge about the world to produce the sequence of actions needed to execute the task. The program generation transforms the sequence of actions into an executable program using knowledge about the robot and its control system.     

From patterns to frameworks to parallel programs

Object-oriented programming, design patterns, and frameworks are abstraction techniques that have been used to reduce the complexity of sequential programming. This paper describes our approach of applying these three techniques to the more difficult parallel programming domain. The Parallel Design Patterns (PDP) process, the basis of the CO₂P₃S parallel programming system, combines these techniques in a layered development model. The result is a new approach to parallel programming that addresses correctness and openness in a unique way. At the topmost development layer, a customized framework is generated from a design pattern specification of the parallel structure of the program. This framework encapsulates all of the structural details of the pattern, including communication and synchronization, to prevent programmer errors and ensure correctness. Lower layers are used only for performance tuning to make the code as efficient as necessary. This paper describes CO₂P₃S, based on the PDP process, and demonstrates it using an example application. We also provide results from a usability study of CO₂P₃S.     

Content reference: Reasoning about rules

In a companion paper [1] we described the concept of saturation, the situation in a program in which so many knowledge sources (KSs) are potentially useful at each invocation cycle that it is unrealistic to consider unguided, exhaustive invocation. We argued that saturation appears almost inevitable in large AI programs.We suggested that the process of invocation can be viewed as occurring in three steps: retrieval (selecting some subset of KSs from the knowledge base), refinement (pruning or reordering that subset), and execution (executing one or more of the KSs). We then argued that one useful approach to dealing with saturation is by embedding intelligence in the refinement phase, and described meta-rules, a means of encoding knowledge used to effect refinement.In this paper we consider a more detailed, ‘engineering’ issue, but one with a number of interesting implications: While there are many ways to implement refinement, we suggest that one particular technique—which we call content reference—offers a number of advantages, including giving the system some ability to reason about the content of its knowledge.     

From sequential programs to concurrent threads

Chip multiprocessors are of increasing importance due to difficulties in achieving higher clock frequencies in uniprocessors, but their success depends on finding useful work for the processor cores. This paper addresses this challenge by presenting a simple compiler approach that extracts non-speculative thread-level parallelism from sequential codes. We present initial results from this technique targeting a validated dual-core processor model, achieving speedups ranging from 9-48% with an average of 25% for important benchmark loops over their single-threaded versions. We also identify important next steps found during our pursuit of higher degrees of automatic threading.     

调用模式和正确调用模式语义在Prolog程序测试中的应用

将基于调用模式语义和正确调用模式语义的程序分析技术应用于Prolog程序的CPM测试。通过调用模式分析获得内部过程被调用和成功调用的条件,利用前者删除不满足调用条件的测试帧,或当删除条件不满足时利用该条件更新测试规格中过程属性的划分准则;利用后者预测CPM测试的结果。该方法可较好地保持程序测试的质量,改善Prolog程序的CPM测试过程。     

From types to type requirements: genericity for model-driven engineering

Model-driven engineering (MDE) is a software engineering paradigm that proposes an active use of models during the development process. This paradigm is inherently type-centric, in the sense that models and their manipulation are defined over the types of specific meta-models. This fact hinders the reuse of existing MDE artefacts with other meta-models in new contexts, even if all these meta-models share common characteristics. To increase the reuse opportunities of MDE artefacts, we propose a paradigm shift from type-centric to requirement-centric specifications by bringing genericity into models, meta-models and model management operations. For this purpose, we introduce so-called concepts gathering structural and behavioural requirements for models and meta-models. In this way, model management operations are defined over concepts, enabling the application of the operations to any meta-model satisfying the requirements imposed by the concept. Model templates rely on concepts to define suitable interfaces, hence enabling the definition of reusable model components. Finally, similar to mixin layers, templates can be defined at the meta-model level as well, to define languages in a modular way, as well as layers of functionality to be plugged-in into other meta-models. These ideas have been implemented in MetaDepth, a multi-level meta-modelling tool that integrates action languages from the Epsilon family for model management and code generation.     

Reasoning about river basins: WaWO+ revisited

This paper characterizes part of an interdisciplinary research effort on Artificial Intelligence (AI) techniques and tools applied to Environmental Decision-Support Systems (EDSS). WaWO+ the ontology we present here, provides a set of concepts that are queried, advertised and used to support reasoning about and the management of urban water resources in complex scenarios as a River Basin. The goal of this research is to increase efficiency in Data and Knowledge interoperability and data integration among heterogeneous environmental data sources (e.g., software agents) using an explicit, machine understandable ontology to facilitate urban water resources management within a River Basin.