Logic programming with arrays

Nial is a programming language designed around a mathematical treatment of data as nested arrays. A goal of the research described is to integrate within Nial a functional style of programming based on the theory of arrays with the declarative capabilities of a logic programming environment. This is partially accomplished by storing logic clauses as arrays which can be manipulated using logic clauses. Arrays as terms are considered as part of the syntax of the clauses. The approach to logic programming is based on providing a flexible environment for experimenting with full clausal or Horn clause logic. A variety of predefined control strategies and the capability for user-defined control strategies have been provided. The expressive capabilities of combining logic and functional programming styles provides a suitable language for many application areas. The philosophy and design behind a combined logic/database model used to prototype a knowledge-based systems application are described     

Semantics of Untyped Functional Programs

The paper is devoted to procedural semantics that use interpretation algorithms on which interpreters of untyped functional programming systems are based (or can be based). The aim of this study is to describe such algorithms and compare procedural semantics based on them both with each other and with the basic semantics defined by means of the fixed-point combinator Y.     

Tableaux for logic programming

We present a logic programming language, which we call Proflog, with an operational semantics based on tableaux and a denotational semantics based on supervaluations. We show the two agree. Negation is well behaved, and semantic noncomputability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems are discussed very briefly; the thrust of the paper is primarily theoretical.Research partly supported by NSF Grant CCR-9104015.     

Revision programming

In this paper we introduce revision programming — a logic-based framework for describing constraints on databases and providing a computational mechanism to enforce them. Revision programming captures those constraints that can be stated in terms of the membership (presence or absence) of items (records) in a database. Each such constraint is represented by a revision rule ← ₁,…,_k, where and all ga_i are of the form in(a) and out(b). Collections of revision rules form revision programs. Similarly as logic programs, revision programs admit both declarative and imperative (procedural) interpretations. In our paper, we introduce a semantics that reflects both interpretations. Given a revision program, this semantics assigns to any database B a collection (possibly empty) of P-justified revisions of B. The paper contains a thorough study of revision programming. We exhibit several fundamental properties of revision programming. We study the relationship of revision programming to logic programming. We investigate complexity of reasoning with revision programs as well as algorithms to compute P-justified revisions. Most importantly from the practical database perspective, we identify two classes of revision programs, safe and stratified, with a desirable property that they determine for each initial database a unique revision.     

可更新Datalog的分布式时态逻辑扩展及应用

针对现有的分布式逻辑语言缺乏完整时态表达力等问题,将分布式时态逻辑谓词引入Datalog规则,提出TU-Datalog语言。该语言通过融入U-Datalog的非即时性更新语义,形成完全声明式具有强大时态表达力的逻辑编程语言和环境。通过扩展U-Datalog逻辑固定点语义,提出TU-Datalog语言的固定点时态演化规则,并对该语言的语法、语义、评价算法进行了研究,最后对该语言的应用做了说明和示例。     

函数式逻辑语言的操作语义

函数式语言和逻辑语言在下列意义上是互补的,基于归约的函数式程序设计语言具有确定和懒惰求解等性质.但同时它又缺少诸如存在量化的变量以及部分数据结构等所希望的性质.相反,基于HORN子句逻辑和消解原理的逻辑程序设计语言允许存在量化的变量和部分数据结构但又缺少确定和懒惰求解的性质.从这个角度出发,把函数和逻辑程序设计语言结合成一种范型是很自然的,这种结合提供了一种比逻辑和函数语言表达能力更强的合一语言.提出了函数式逻辑语言的操作语义,同时表明这种操作语义在实践中是可见的.     

Autoepistemic logic programming

An autoepistemic logic programming language is derived from a subset of a three-valued autoepistemic logic, called 3AEL. Autoepistemic programs generalize several ideas underlying logic programming: stable, supported, and well-founded models, Fitting's semantics, Kunen's semantics, and abductive frameworks can all be captured through simple autoepistemic translations; moreover, SLDNF-resolution and a generate-and-test method for stable semantics are generalized to provide sound and complete proof methods for autoepistemic programs. These methods extend existing proof methods for 3AEL. Thus autoepistemic logic programming, besides contributing to the understanding of 3AEL, can be seen as a unifying framework for the theory of logic programs. It should also be regarded as a first step toward a flexible environment where different forms of inference can be formally integrated.This paper is an extended version of [8]. I am grateful to my advisor, Giorgio Levi, to Paolo Mancarella, who read the first version of the paper, and to the anonymous referees, whose comments led to sensible improvements.     

Database query languages and functional logic programming

Functional logic programming is a paradigm which integrates functional and logic programming. It is based on the use of rewriting rules for defining programs, and rewriting for goal solving. In this context, goals, usually, consist of equality (and, sometimes, inequality) constraints, which are solved in order to obtain answers, represented by means of substitutions. On the other hand, database programming languages involve a data model, a data definition language and, finally, a query language against the data defined according to the data model. To use functional logic programming as a database programming language, (1) we will propose a data model involving the main features adopted from functional logic programming (for instance, handling of partial and infinite data), (2) we will use conditional rewriting rules as data definition language, and finally, (3) we will deal with equality and inequality constraints as query language. Moreover, as most database systems, (4) we will propose an extended relational calculus and algebra, which can be used as alternative query languages in this framework. Finally, (5) we will prove that three alternative query languages are equivalent.     

Symmetric structure in logic programming

It is argued that some symmetric structure in logic programs could be taken into account when implementing semantics in logic programming. This may enhance the declarative ability or expressive power of the semantics. The work presented here may be seen as representative examples along this line. The focus is on the derivation of negative information and some other classic semantic issues. We first define a permutation group associated with a given logic program. Since usually the canonical models used to reflect the common sense or intended meaning are minimal or completed models of the program, we expose the relationships between minimal models and completed models of the original program and its so-called G-reduced form newly-derived via the permutation group defined. By means of this G-reduced form, we introduce a rule to assume negative information termed G-CWA, which is actually a generalization of the GCWA. We also develop the notions of G-definite, G-hierarchical and G-stratified logic programs,     

Iterative belief revision in extended logic programming

Extended logic programming augments conventional logic programming with both default and explicit negation. Several semantics for extended logic programs have been proposed that extend the well-founded semantics for logic programs with default negation (called normal programs). We show that two of these extended semantics are intractable; both Dung's grounded argumentation semantics and the well-founded semantics of Alferes et al. are NP-hard. Nevertheless, we also show that these two semantics have a common core, a more restricted form of the grounded semantics, which is tractable and can be computed iteratively in quadratic time. Moreover, this semantics is a representative of a rich class of tractable semantics based on a notion of iterative belief revision.     

Nonmonotonic logic programming

This paper provides a survey of the state of the art in nonmonotonic logic programming. In particular, it surveys advances in the declarative semantics of logic programs, in query processing procedures for nonmonotonic logic programs, and in recent extensions of the nonmonotonic logic programming paradigm     

Category-based modularisation for equational logic programming

Although modularisation is basic to modern computing, it has been little studied for logic-based programming. We treat modularisation for equational logic programming using the institution of category-based equational logic in three different ways: (1) to provide a generic satisfaction condition for equational logics; (2) to give a category-based semantics for queries and their solutions; and (3) as an abstract definition of compilation from one (equational) logic programming language to another. Regarding (2), we study soundness and completeness for equational logic programming queries and their solutions. This can be understood as ordinary soundness and completeness in a suitable “non-logical” institution. Soundness holds for all module imports, but completeness only holds for conservative module imports. Category-based equational signatures are seen as modules, and morphisms of such signatures as module imports. Regarding (3), completeness corresponds to compiler correctness. The results of this research applies to languages based on a wide class of equational logic systems, including Horn clause logic, with or without equality; all variants of order and many sorted equational logic, including working modulo a set of axioms; constraint logic programming over arbitrary user-defined data types; and any combination of the above. Most importantly, due to the abstraction level, this research gives the possibility to have semantics and to study modularisation for equational logic programming developed over non-conventional structures. Received April 15, 1994/April 12, 1995     

Integrating logic and functional programming

The intent of this article is twofold: To survey prominent proposals for the integration of logic and functional programming and to present a new paradigm for the same purpose. We categorize current research into four types of approaches, depending on the level at which the proposed integration is achieved. Unlike most current work, our approach is not based on extending unification to general-purpose equation solving. Rather, we propose a computation delaying mechanism calledresiduation. This allows a clear distinction between functionalevaluation and logicaldeduction. The former is based on the-calculus, and the latter on Horn clause resolution. Residuation is built into the unification operation which may then account for-reduction. In clear contrast with equation-solving approaches, our model supports higher-order function evaluation and efficient compilation of both functional and logic programming expressions, without being plagued by non-deterministic term-rewriting. In addition, residuation lends itself naturally to process synchronization and constrained search. We describe an operational semantics and an implementation of a prototype language called LeFun—Logic, equations, and Functions.This article is a revised and extended version of [1].     

A framework for linguistic logic programming

Lawry's label semantics for modeling and computing with linguistic information in natural language provides a clear interpretation of linguistic expressions and thus a transparent model for real‐world applications. Meanwhile, annotated logic programs (ALPs) and its fuzzy extension AFLPs have been developed as an extension of classical logic programs offering a powerful computational framework for handling uncertain and imprecise data within logic programs. This paper proposes annotated linguistic logic programs (ALLPs) that embed Lawry's label semantics into the ALP/AFLP syntax, providing a linguistic logic programming formalism for development of automated reasoning systems involving soft data as vague and imprecise concepts occurring frequently in natural language. The syntax of ALLPs is introduced, and their declarative semantics is studied. The ALLP SLD‐style proof procedure is then defined and proved to be sound and complete with respect to the declarative semantics of ALLPs. © 2010 Wiley Periodicals, Inc.     

On implementing Prolog in functional programming

This report surveys techniques for implementing the programming language Prolog. It focuses on explaining the procedural semantics of the language in terms of functional programming constructs. The techniquessuccess continuations andproof streams are introduced, and it is shown how Horn clause interpreters can be built upon them. Continuations are well known from denotational semantics theory, in this paper it is shown that they are viable constructs in actual programs. Other issues include implementation of logical variables, structure sharing vs. structure copying, determinacy, builtin predicates, andcut.     

Logic programming with solution preferences

Preference logic programming (PLP) is an extension of logic programming for declaratively specifying problems requiring optimization or comparison and selection among alternative solutions to a query. PLP essentially separates the programming of a problem itself from the criteria specification of its solution selection. In this paper we present a declarative method for specifying preference logic programs. The method introduces a precise formalization for the syntax and semantics of PLP. The syntax of a preference logic program contains two disjoint sets of definite clauses, separating a core program specifying a general computational problem from its preference rules for optimization; the semantics of PLP is given based on the Herbrand model and fixed point theory, where how preferences affects the least Herbrand model of a logic program is interpreted as a sequence of meta-level mapping operations. In addition, we present an operational semantics based on a new resolution strategy and a memoized recursive algorithm for computing strictly stratified logic programs with well-formed preferences, and further show that the operational semantics of such a preference logic program is consistent to its declarative semantics.     

A new framework for declarative programming

We propose a new framework for the syntax and semantics of Weak Hereditarily Harrop logic programming with constraints, based on resolution over τ-categories: finite product categories with canonical structure.

Constraint information is directly built-in to the notion of signature via categorical syntax. Many-sorted equational are a special case of the formalism which combines features of uniform logic programming languages (moduels and hypothetical implication) with those of constraint logic programming. Using the cannoical structure supplied by τ-categories, we define a diagrammatic generalization of formulas, goals, programs and resolution proofs up to equality (rather than just up to isomorphism).

We extend the Kowalski-van Emden fixed point interpretation, a cornerstone of declarative semantics, to an operational, non-ground, categorical semantics based on indexing over sorts and programs.

We also introduce a topos-theoretic declarative semantics and show soundness and completeness of resolution proofs and of a sequent calculus over the categorical signature. We conclude with a discussion of semantic perspectives on uniform logic programming.     

Toward a programming theory for rational agents

An important problem in agent verification is a lack of proper understanding of the relation between agent programs on the one hand and agent logics on the other. Understanding this relation would help to establish that an agent programming language is both conceptually well-founded and well-behaved, as well as yield a way to reason about agent programs by means of agent logics. As a step toward bridging this gap, we study several issues that need to be resolved in order to establish a precise mathematical relation between a modal agent logic and an agent programming language specified by means of an operational semantics. In this paper, we present an agent programming theory that provides both an agent programming language as well as a corresponding agent verification logic to verify agent programs. The theory is developed in stages to show, first, how a modal semantics can be grounded in a state-based semantics, and, second, how denotational semantics can be used to define the mathematical relation connecting the logic and agent programming language. Additionally, it is shown how to integrate declarative goals and add precompiled plans to the programming theory. In particular, we discuss the use of the concept of higher-order goals in our theory. Other issues such as a complete axiomatization and the complexity of decision procedures for the verification logic are not the focus of this paper and remain for future investigation. Part of this research was carried out while the first author was affiliated with the Nijmegen Institute for Cognition and Information, Radboud University Nijmegen.     

Abductive logic programming agents with destructive databases

In this paper we present an agent language that combines agent functionality with a state transition theory and model-theoretic semantics. The language is based on abductive logic programming (ALP), but employs a simplified state-free syntax, with an operational semantics that uses destructive updates to manipulate a database, which represents the current state of the environment. The language builds upon the ALP combination of logic programs, to represent an agent??s beliefs, and integrity constraints, to represent the agent??s goals. Logic programs are used to define macro-actions, intensional predicates, and plans to reduce goals to sub-goals including actions. Integrity constraints are used to represent reactive rules, which are triggered by the current state of the database and recent agent actions and external events. The execution of actions and the assimilation of observations generate a sequence of database states. In the case of the successful solution of all goals, this sequence, taken as a whole, determines a model that makes the agent??s goals and beliefs all true.