Failure and Equality in Functional Logic Programming

Constructive failure has been proposed recently as a programming construct useful for functional logic programming, playing a role similar to that of constructive negation in logic programming. On the other hand, almost any functional logic program requires the use of some kind of equality test between expressions. We face in this work in a rigorous way the interaction of failure and equality (even for non-ground expressions), which is a non trivial issue, requiring in particular the use of disequality conditions at the level of the operational mechanism of constructive failure. As an interesting side product, we develop a novel treatment of equality and disequality in functional logic programming, by giving them a functional status, which is better suited for practice than previous proposals.     

Programming with narrowing: A tutorial

Narrowing is a computation implemented by some declarative programming languages. Research in the last decade has produced significant results on the theory and foundation of narrowing, but little has been published on the use of narrowing in programming. This paper introduces narrowing from a programmer’s viewpoint; shows, by means of examples, when, why and how to use narrowing in a program; and discusses the impact of narrowing on software development activities such as design and maintenance. The examples are coded in the programming language Curry, which provides narrowing as a first class feature.     

Ensuring the quasi-termination of needed narrowing computations

We present a characterization of first-order functional programs which are quasi-terminating with respect to the symbolic execution mechanism of needed narrowing, i.e., computations in these programs consist of a sequence of finitely many different function calls (up to variable renaming). Quasi-terminating programs are particularly useful for program analysis and transformation, since in this context quasi-termination often amounts to full termination.     

Relating the implementation techniques of functional and functional logic languages

Functional logic languages are declarative programming languages that integrate the programming paradigms of functional and logic languages within a single framework. They are extensions of functional languages with principles derived from logic programmingNarrowing, the evaluation mechanism of functional logic languages, can be defined as a generalization ofreduction, the evaluation mechanism of purely functional languages. The unidirectional pattern matching, which is used for parameter passing in functional languages, is simply replaced by the bidirectionalunification known from logic programming languages. We show in this paper, how to extend a reduction machine, that has been designed for the evaluation of purely functional programs to a machine that performs narrowing. The necessary extensions concern the realization of unification and backtracking, for which we fall back upon the methods of Warren’s Prolog engine.²¹⁾ The narrowing machine embodies an optimized treatment of deterministic computations. A complete specification of the reduction and the narrowing machine and of the translation of a sample language into abstract machine code is given. Comparative results of a C-implementation of the reduction and the narrowing machine show that the time overhead of the more complex narrowing evaluation is, in general, less than 10% of the reduction evaluation.     

Introduction of dosim predicate to Prolog

This paper proposes a predicate nameddosim which provides a new function for parallel execution of logic programs. The parallelism achieved by this predicate is a simultaneous mapping operation such as bagof and setof predicates. However, the degree of parallelism can be easily decided by arranging the arguments of the dosim goal. The parallel processing system with dosim was realized on a tight-coupled multiprocessor machine. To control the degree of parallelism and reduce the amount of memory required for execution, we introduce the grouping method for the goals executed in parallel and some variations of the dosim predicate. The effectiveness of the proposed method is demonstrated by the results of the execution of several applications.     

Supporting Function Calls within PELCR

In [M. Pedicini and F. Quaglia. A parallel implementation for optimal lambda-calculus reduction PPDP '00: Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, pages 3–14, ACM, 2000, M. Pedicini and F. Quaglia. PELCR: Parallel environment for optimal lambda-calculus reduction. CoRR, cs.LO/0407055, accepted for publication on TOCL, ACM, 2005], PELCR has been introduced as an implementation derived from the Geometry of Interaction in order to perform virtual reduction on parallel/distributed computing systems.In this paper we provide an extension of PELCR with computational effects based on directed virtual reduction [V. Danos, M. Pedicini, and L. Regnier. Directed virtual reductions. In M. Bezem D. van Dalen, editor, LNCS 1258, pages 76–88. EACSL, Springer Verlag, 1997], namely a restriction of virtual reduction [V. Danos and L. Regnier. Local and asynchronous beta-reduction (an analysis of Girard's EX-formula). LICS, pages 296–306. IEEE Computer Society Press, 1993], which is a particular way to compute the Geometry of Interaction [J.-Y. Girard. Geometry of interaction 1: Interpretation of system F. In R. Ferro, et al. editors Logic Colloquium '88, pages 221–260. North-Holland, 1989] in analogy with Lamping's optimal reduction [J. Lamping. An algorithm for optimal lambda calculus reduction. In Proc. of 17th Annual ACM Symposium on Principles of Programming Languages. ACM, San Francisco, California, pages 16–30, 1990]. Moreover, the proposed solution preserves scalability of the parallelism arising from local and asynchronous reduction as studied in [M. Pedicini and F. Quaglia. PELCR: Parallel environment for optimal lambda-calculus reduction. CoRR, cs.LO/0407055, accepted for publication on TOCL, ACM, 2005].     

Implementing Constructive Intensional Negation

Although negation is an active area of research in logic programming, sound and complete implementations are still absent from actual Prolog systems. One of the most promising techniques in the literature is intensional negation (IN), which follows a transformational approach: for each predicate p in a program its negative counterpart intneg(p) is generated. However, implementations of IN have not been included in Prolog environments due, in part, to the lack of details and explicit techniques, such as the treatment of universally quantified goals. In this paper, we describe a variant of IN, which we have called constructive intensional negation (CIN). Unlike earlier proposals, CIN does not resort to a dedicated resolution strategy when dealing with universally quantified formulae, which has been instrumental in having an effective implementation. Therefore, pure SLD resolution is used, what enables the reuse of existing Prolog implementation technology. Among the contributions of this work we can mention not only a full implementation being tested for its integration in the Ciao Prolog system but also some formal results ensuring soundness and completeness with their associated proofs.

约束归纳逻辑程序设计方法的研究

提出了一种新的约束归纳逻辑程序设计方法。该方法能够与自顶向下的归纳逻辑程序设计系统结合,通过在自顶向下归纳方法的一步特殊化操作中引入Fisher判别分析等方法,使得系统能够导出不受变量个数限制的多种形式的线性约束,在不需要用户诱导,不依赖约束求解器的情况下,学习出覆盖正例而排斥负例的含约束的Horn子句程序。     

归纳逻辑程序设计综述

归纳逻辑程序设计是由机器学习与逻辑程序设计交叉所形成的一个研究领域,是机器学习的前沿研究课题。该文首先从归纳逻辑程序设计的问题背景、类型划分和搜索程序子句三个方面介绍了归纳逻辑程序设计系统的概貌;然后结合实验室的相关研究工作,回顾了归纳逻辑程序设计研究的发展;之后介绍了归纳逻辑程序设计领域中需要深入研究的若干问题,并提出了新的解决思路;最后是总结,以引起读者对归纳逻辑程序设计领域研究的进一步关注。     

How should Prolog computation Be represented for practical use?

We propose a visual computation model called theBox and Plane Model (BPM), which visually clarifies the semantics of backtracking, the cut operator, and side-effects, thus allowing the procedural features of Prolog to be grasped. On the bases of the BPM, we developed a visual debugger for Prolog, PROEDIT2, which has proved that this kind of pragmatic computation model for Prolog increases the efficiency of the debugging work.     

Modelling Multicast QoS Routing by using Best-Tree Search in And-or Graphs and Soft Constraint Logic Programming

We suggest a formal model to represent and solve the multicast routing problem in multicast networks. To attain this, we model the network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the cost of sending a packet on the network link modelled by that connector. Then, we use the Soft Constraint Logic Programming (SCLP) framework as a convenient declarative programming environment in which to specify related problems. In particular, we show how the semantics of an SCLP program computes the best tree in the corresponding and-or graph: this result can be adopted to find, from a given source node, the multicast distribution tree having minimum cost and reaching all the destination nodes of the multicast communication. The costs on the connectors can be described also as vectors (multi-dimensional costs), each component representing a different Quality of Service metric value. Therefore, the construction of the best tree may involve a set of criteria, all of which are to be optimized (multi-criteria problem), e.g. maximum global bandwidth and minimum delay that can be experienced on a single link.     

Proof-Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification

We characterize provability in intuitionistic logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in intuitionistic logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for intuitionistic logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to intuitionistic logic with equality. Thus, any proof procedure for intuitionistic logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in intuitionistic logic with equality.     

Proof Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification

We characterize provability in intuitionistic logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in intuitionistic logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for intuitionistic logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to intuitionistic logic with equality. Thus, any proof procedure for intuitionistic logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in intuitionistic logic with equality.     

A new deductive approach to planning

We introduce a new deductive approach to planning which is based on Horn clauses. Plans as well as situations are represented as terms and, thus, are first-class objects. We do neither need frame axioms nor state-literals. The only rule of inference is the SLDE-resolution rule, i.e. SLD-resolution, where the traditional unification algorithm has been replaced by anE-unification procedure. We exemplify the properties of our method such as forward and backward reasoning, plan checking, and the integration of general theories. Finally, we present the calculus and show that it is sound and complete. An earlier version of this paper was presented at the German Workshop on Artificial Intelligence, 1989.     

Functional queries in Datalog

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 hierarchyBH. In this paper we present a ‘functional’ language which, by means of a disciplined use of negation, achieves the desired level of expressiveness up toBH. 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.     

Fast computation of sample entropy and approximate entropy in biomedicine

Both sample entropy and approximate entropy are measurements of complexity. The two methods have received a great deal of attention in the last few years, and have been successfully verified and applied to biomedical applications and many others. However, the algorithms proposed in the literature require O(N²) execution time, which is not fast enough for online applications and for applications with long data sets. To accelerate computation, the authors of the present paper have developed a new algorithm that reduces the computational time to O(N^3/2)) using O(N) storage. As biomedical data are often measured with integer-type data, the computation time can be further reduced to O(N) using O(N) storage. The execution times of the experimental results with ECG, EEG, RR, and DNA signals show a significant improvement of more than 100 times when compared with the conventional O(N²) method for N = 80,000 (N = length of the signal). Furthermore, an adaptive version of the new algorithm has been developed to speed up the computation for short data length. Experimental results show an improvement of more than 10 times when compared with the conventional method for N > 4000.     

An application of an OR-Parallel Prolog system to phylogenetic analysis

In this paper we discuss an application of our OR-Parallel Prolog system to a search problem of importance in practice: the construction of phylogenetic trees. The use of a maximum likelihood method to construct such trees is based on concrete models of evolutional processes and is well-motivated statistically. However, the use of maximum likelihood methods has been hindered by the computational cost to calculate the likelihood of possible alternative trees (i.e. their confidence scores) at each search step for the optimal tree. To cope with this problem, we used OR-parallel Prolog as a coordination language to orchestrate the search for the optimal tree. A numerical computation written in C computed the likelihood of each alternative tree and a symbolic computation written in Prolog performed a parallel A* tree search. For constructing phylogenetic trees of bacterial organisms, our parallel algorithm allowed us to increase the size of the search space, allowing us to include nearly optimal as well as optimal intermediate trees in the search. Our priority mechanism reduced the generation of useless tasks and resulted in superlinear speedups in some cases.     

SD-Solver: Towards a “multidirectional” CLP-based simulation tool

SD-Solver is a general purpose simulation environment grounded on the Constraint Logic Programming technology. Its main aim is to facilitate the development of Decision Support Systems based on dynamic models. Using SD-Solver, forward and backward simulations can be performed -to some extent- on the basis of a single model. This paper outlines the underlying framework and presents the most important aspects of SD-Solver using two elementary financial examples.[/p]     

How to Implement Product Data Management

introduced are the main implementation contents and brought out is a cycle optimal PDMimplementation methodology by phases through studying requirements of enterprises' datamanagement and summarizing the existing method. The implementation contents include documentsmanagement product structure and configuration management, product classification and codingmanagement, workflow management and software encapsulation. It divides the PDM implementationinto preparing, software selechon and training, implementation plan making, concrete implementingand evaluating. By the cycle of the last two pheses, the successful implementation of PDM can beobtained. This methodology has been used in the CIMS project of two companies and proved to bepractical.     

Cautious induction: An alternative to clause-at-a-time hypothesis construction in inductive logic programming

Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set. This paper formulates and analyses an alternative method for constructing hypotheses. The method, calledcautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm. We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems. Simon Anthony, BEng.: Simon, perhaps better known as “Mr. Cautious” in Inductive Logic Programming (ILP) circles, completed a BEng in Information Engineering at the University of York in 1995. He remained at York as a research student in the Intelligent Systems Group. Concentrating on ILP, his research interests are Cautious Induction and developing number handling techniques using Constraint Logic Programming. Alan M. Frisch, Ph.D.: He is the Reader in Intelligent Systems at the University of York (UK), and he heads the Intelligent Systems Group in the Department of Computer Science. He was awarded a Ph. D. in Computer Science from the University of Rochester (USA) in 1986 and has held faculty positions at the University of Sussex (UK) and the University of Illinois at Urbana-Champaign (USA). For over 15 years Dr. Frisch has been conducting research on a wide range of topics in the area of automated reasoning, including knowledge retrieval, probabilistic inference, constraint solving, parsing as deduction, inductive logic programming and the integration of constraint solvers into automated deduction systems.