Modal extension of logic programming systems

Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 180–182, November–December, 1993.     

MSVL: a typed language for temporal logic programming

The development of types is an important but challenging issue in temporal logic programming. In this paper, we investigate how to formalize and implement types in the temporal logic programming language MSVL, which is an executable subset of projection temporal logic (PTL). Specifically, we extendMSVL with a few groups of types including basic data types, pointer types and struct types. On each type, we specify the domain of values and define some standard operations in terms of logic functions and predicates. Then, it is feasible to formalize statements of type declaration of program variables and statements of struct definitions as logic formulas. As the implementation of the theory, we extend theMSV toolkit with the support of modeling, simulation and verification of typedMSVL programs. Applications to the construction of AVL tree and ordered list show the practicality of the language.     

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].     

DWAM — A WAM model extension for disjunctive logic programming

Answering queries in disjunctive logic programming requires the use of ancestry-resolution. The resulting complication makes it difficult to implement a Prolog-type query answering procedure for disjunctive logic programs. However, SLO-resolution provides a mechanism which is similar to SLD-resolution and hence offers a solution to this problem. The Warren Abstract Machine has been a very effective model for implementing Prolog. In this paper, we extend the WAM model of Prolog and adapt it for DISLOG — a language for disjunctive logic programming. We describe the extensions and additional instructions needed to make WAM viable for modeling and executing DISLOG. The extension is made in such a way that the original architecture is not disturbed and a Prolog program will execute as efficiently as it does in the original WAM.This work was done while the author was at the University of Kentucky.     

Evaluation strategies for functional logic programming

Recent advances in the foundations and the implementations of functional logic programming languages originate from far-reaching results on narrowing evaluation strategies. Narrowing is a computation similar to rewriting which yields substitutions in addition to normal forms. In functional logic programming, the classes of rewrite systems to which narrowing is applied are, for the most part, subclasses of the constructor-based, possibly conditional, rewrite systems. Many interesting narrowing strategies, particularly for the smallest subclasses of the constructor-based rewrite systems, are generalizations of well-known rewrite strategies. However, some strategies for larger non-confluent subclasses have been developed just for functional logic computations. This paper discusses the elements that play a relevant role in evaluation strategies for functional logic computations, describes some important classes of rewrite systems that model functional logic programs, shows examples of the differences in expressiveness provided by these classes, and reviews the characteristics of narrowing strategies proposed for each class of rewrite systems.     

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.     

A new generic scheme for functional logic programming with constraints

In this paper we propose a new generic scheme CFLP풟, intended as a logical and semantic framework for lazy Constraint Functional Logic Programming over a parametrically given constraint domain 풟. As in the case of the well known CLP풟 scheme for Constraint Logic Programming, 풟 is assumed to provide domain specific data values and constraints. CFLP풟 programs are presented as sets of constrained rewrite rules that define the behavior of possibly higher order and/or non-deterministic lazy functions over 풟. As a main novelty w.r.t. previous related work, we present a Constraint Rewriting Logic CRWL풟 which provides a declarative semantics for CFLP풟 programs. This logic relies on a new formalization of constraint domains and program interpretations, which allows a flexible combination of domain specific data values and user defined data constructors, as well as a functional view of constraints. This research has been partially supported by the Spanish National Projects MELODIAS (TIC2002-01167), MERIT-FORMS (TIN2005-09207-C03-03) and PROMESAS-CAM (S-0505/TIC/0407).     

An extension of lambda-calculus for functional programming

An implementation oriented modification of lambda-calculus is presented together with some additional conversion rules for list manipulations. The resulting set of axioms is very simple and provides for a theoretical foundation of the semantics of functional programming. At the same time it can be used directly for the implementation of a powerful graph-reduction algorithm.     

Extended unification algorithms for the integration of functional programming into logic programming

Extended unification algorithms are considered for the integration of a functional language into a logic programming language. The extended language is a particular case of logic programming language with equality. A comprehensive survey is given which is structured following the procedural semantics taken for the functional language. This survey includes past works based on evaluation and derivation (as procedural semantics of the functional language) and new algorithms based on surderivation. These algorithms are compared especially regarding their completeness. Also, we discuss issues arising in practice when different surderivation strategies are used, as these influence directly efficiency and especially termination. This leads us to propose an algorithm based on lazy surderivation which compares favorably with the others and endows logic programming with two advanced features of functional programming: automatic coroutining and handling of infinite data structures without extra control.     

Distributed programming with typed events

The remote-procedure-call abstraction, including its derivates (underlying, for example, Java RMI, CORBA, and .NET), currently represents one of the most popular paradigms for devising distributed applications. Objects (when acting as servers) are invoked remotely (by clients) through proxies (also called stubs). Because proxies offer the same interfaces as their respective associated remote objects, they hide distribution details, leading to a convenient distributed-programming style that enforces type safety and encapsulation. However, RPC-style interaction does not apply equally well in all contexts. In its classic form, it tends to strongly synchronize-and hence couple-the invoking and invoked objects. Several proposed asynchronous variants of RPC illustrate the severity of this drawback. Type-based publish-subscribe is an appealing candidate programming abstraction for inherently decoupled and completely decentralized applications that run over large-scale and mobile networks. Like RPC, TPS enforces type safety and encapsulation; unlike RPC, it provides decoupling and scalability. To illustrate, we discuss two TPS implementations in Java.     

A framed temporal logic programming language

We discuss the projection temporal logic (PTL), based on a primitive projection operator, prj. A framing technique is also presented, using which a synchronization operator, await, is defined within the underlying logic. A framed temporal logic programming language (FTLL) is presented. To illustrate how to use both the language and framing technique, some examples are given.     

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.     

Learning concept descriptions with typed evolutionary programming

Examples and concepts in traditional concept learning tasks are represented with the attribute-value language. While enabling efficient implementations, we argue that such propositional representation is inadequate when data is rich in structure. This paper describes STEPS, a strongly-typed evolutionary programming system designed to induce concepts from structured data. STEPS higher-order logic representation language enhances expressiveness, while the use of evolutionary computation dampens the effects of the corresponding explosion of the search space. Results on the PTE2 challenge, a major real-world knowledge discovery application from the molecular biology domain, demonstrate promise.     

Inductive logic programming

A new research area, Inductive Logic Programming, is presently emerging. While inheriting various positive characteristics of the parent subjects of Logic Programming and Machine Learning, it is hoped that the new area will overcome many of the limitations of its forebears. The background to present developments within this area is discussed and various goals and aspirations for the increasing body of researchers are identified. Inductive Logic Programming needs to be based on sound principles from both Logic and Statistics. On the side of statistical justification of hypotheses we discuss the possible relationship between Algorithmic Complexity theory and Probably-Approximately-Correct (PAC) Learning. In terms of logic we provide a unifying framework for Muggleton and Buntine’s Inverse Resolution (IR) and Plotkin’s Relative Least General Generalisation (RLGG) by rederiving RLGG in terms of IR. This leads to a discussion of the feasibility of extending the RLGG framework to allow for the invention of new predicates, previously discussed only within the context of IR.     

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     

Multimodal logic programming

We give a framework for developing the least model semantics, fixpoint semantics, and SLD-resolution calculi for logic programs in multimodal logics whose frame restrictions consist of the conditions of seriality (i.e. ) and some classical first-order Horn clauses. Our approach is direct and no special restriction on occurrences of □_i and _i is required. We apply our framework for a large class of basic serial multimodal logics, which are parameterized by an arbitrary combination of generalized versions of axioms T, B, 4, 5 (in the form, e.g. 4:□_i→□_j□_k) and I:□_i→□_j. Another part of the work is devoted to programming in multimodal logics intended for reasoning about multidegree belief, for use in distributed systems of belief, or for reasoning about epistemic states of agents in multiagent systems. For that we also use the framework, and although these latter logics belong to the mentioned class of basic serial multimodal logics, the special SLD-resolution calculi proposed for them are more efficient.