%A Uday S. Reddy %T On the relationship between logic and functional languages %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 3-36 %X An essential distinction between logic and functional languages is drawn based on input-output directionality. Functional languages are directional in that programs written in them make an explicit commitment about which quantities are inputs and which are outputs. Logic programs to do not make such a commitment. However, the non-directionality makes the operational behavior of logic programs hard to understand and poses problems in developing parallel implementations of logic languages. We present here a notation for introducing directionality information in logic programs and show that directional logic programs are equivalent to first-order functional programs. Finally, we discuss how the syntax and semantics of functional languages can be extended to capture the additional expressive power of logic languages. %A J. Darlington %A A.J. Field %A H. Pull %T The unification of functional and logic languages %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 37-70 %X This paper discusses the differences between functional and relational styles and proposes an extended functional language (HOPE with unification) which provides all the expressive power of logic programs whilst retaining most of the underlying functional simplicity. This is achieved by the introduction of absolute set abstraction which allows logical variables to be introduced within set expressions on the right hand sides of function-defining equations. We proposes a technique for compiling certain types of functions defined implicitly within set expressions into explicit functions. This effectively involves synthesising function inverses using the processes of symbolic unification and program transformation. When this can be achieved, logical variables can be eliminated altogether and replaced by function composition. %A Harvey Abramson %T A Prological definition of HASL, a purely functional language with unification based conditional binding expressions %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 73-129 %X We present a definition in Prolog of a new purely functional (applicative) language HASL (HArvey's Static Language). HASL is a descendant of Turner's SASL, but, among other features, introduces a one-way unification based conditional binding expression, one-way in the sense that of the two expressions being unified, only one may contain variables. This one-way unification based conditional binding construct is used to structure the design of the compilation of HASL clausal definitions to combinators which may then be reduced. The specification of HASL and its reduction machine is entirely in Prolog, thus providing an executable specification - implementation - of the language. Since HASL programs may be considered a syntactic sugaring of combinator code, we adapt techniques derived from compiling practice to specify the language and its reduction machine. %A Masahiko Sato %A Tatakfumi Sakurai %T QUTE: a functional language based on unification %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 131-155 %X A new programming language called Qute is introduced. Qute is a functional programming language which permits parallel evaluation. While most functional programming languages use pattern matching as basic variable-value binding mechanism, Qute uses unification as its binding mechanism. Since unification is bidirectional, as opposed to pattern match which is unidirectional, Qute becomes a more powerful functional programming language than most of existing functional languages. This approach enables the natural unification of logic programming language and functional programming language. In Qute it is possible to write a program which is very much like one written in conventional logic programming language, say, Prolog. At the same time, it is possible to write a Qute program which looks like an ML (which is a functional language) program. A Qute program can be evaluated in parallel (and-parallelism) and the same result is obtained irrespective of the particular order of evaluation. This is guaranteed by the Church-Rosser property enjoyed by the evaluation algorithm. A completely formal semantics of Qute is given in this paper. %A P.A. Subrahmanyam %A Jia-Huai You %T FUNLOG: a computational model integrating logic programming and functional programming %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 157-198 %X Funlog involves a computational model which integrate functional programming and logic programming. This model is described, along with evaluation strategies to support the execution of programs based upon it. A lazy mechanism, pattern-driven reduction, is developed for the underlying functional model and cleanly and naturally achieves reduction by need. The notion of semantic unification is discussed. Semantic unification serves as a basis for achieving the desired integration of functions and logic, and can be used to replace the conventional unification procedure in logic programming systems. The resulting model supports computations with infinite data structures while avoiding the introduction of complicated control issues at the user level. In addition, it provides the programmer the flexibility of choosing between a backtracking free computation framework and a conventional logic computation framework, i.e., a nondeterministic one involving backtracking. The use of this facility is illustrated via examples. The model can be extended to include the notion of equality when complete E-unification algorithms are used. %A R. Barbuti %A M. Bellia %A G. Levi %A M. Martelli %T LEAF: a language which integrates logic, equations and functions %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 201-238 %X The paper describes a language which integrates a declarative language, consisting of Horn clauses and equational theories with constructors, and a first order functional language. Both language components will eventually be directly supported by a hardware machine. The declarative component permits the definition of both relations and functions, possibly dealing with infinite data structures. A formal semantics, coping with the novel language features, is given in the standard style (operational, model-theoretic and fixpoint). The functional (procedural) component is essentially the functional (deterministic) sublanguage of the declarative one. It has a lazy evaluation based parallel interpreter and allows efficient programming of system software, tools and algorithms. The technique for integrating these two language components is based on using the procedural component as the metalanguage of the declarative component, thus allowing procedural programs to act on meta-objects such as declarative theories and (possibly infinite) sets of solutions of declarative programs. Examples are given of tools for the declarative component and of integrated procedural-declarative applications. %A Shimon Cohen %T The APPLOG language %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 239-276 %X The virtues of PROLOG and LISP are discussed, and the conclusion is reached that a mixture of these two languages is desirable. Toward that end, APPLOG, a combination of LISP and PROLOG, is described. APPLOG is embedded within the PROLOG language with the facilities of PROLOG made available through a simple goal function. The main advantage of APPLOG is the simple integration of LISP and PROLOG into one powerful language which incorporates, in our judgment, the best features of both languages. In particular, APPLOG has the following advantages over traditional LISP languages: (i) pattern directed invocation; (ii) call by reference; (iii) an interface to PROLOG as a database query language; (iv) functions as operators (infix, prefix and postfix); (v) backtracking, and (vi) generators. APPLOG includes aggregates and grouping constructs, and has been extended to a simple relational database query language similar to Query-By-Example. An appendix includes a listing of the principal functions of the APPLOG interpreter. %A William A. Kornfeld %T Equality for Prolog %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 279-293 %X An extension of the language Prolog, called "Prolog-with- Equality", is presented which allows the inclusion of assertions about equality. When an attempt is made to unify two terms that do not unify syntactically, an equality theorem may be used to prove the two terms equal. If it is possible to prove that the two terms are equal, the unification succeeds with the variable bindings introduced by the equality proof. It is shown that this mechanism significantly improves the power of Prolog. Sophisticated data abstraction with the advantages of object-oriented programming becomes available. Techniques for passing partially instantiated data are described that extend the "multi-use" capabilities of the language, improve the efficiency of some programs, and allow the implementation of arithmetic relations that are both general and efficient. The modification to standard Prolog are simple and straightforward and in addition the computational overhead for the extra linguistic power is believed to not be significant. Equality theorems will probably play an important role in future logic programming systems. %A Joseph A. Goguen %A Jose Meseguer %T EQLOG: equality, types, and generic modules for logic programming %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 295-363 %X This paper presents Eqlog, a logic programming language that unifies (predicate-based) Horn clause relational programming with (equality-based) functional programming. The unification seems quite natural, since it is based on the smallest logic having both Horn clauses and equality, namely Horn clause logic with equality. Rather than force functions to be viewed as predicates, or predicates to be viewed as functions, Eqlog allows using both functions and predicates as convenient. Furthermore, Eqlog computes differently with functions than with predicates: functions are computed by term rewriting, while queries to predicates are computed in the usual Prolog-like fashion with unification and backtracking (but with unification modulo equations, implemented by narrowing in general, and by more efficient methods for built-in types). In fact, narrowing does much more than this, since it allows solving for the values of logical variables that occur in equations. This gives Eqlog very powerful capabilities as a "constraint language", using narrowing and Prolog-style backtracking to solve constraints over user-defined abstract data types, and using efficient built-in algorithms for solving constraints over built-in types (such as numbers). With the usual Church-Rosser assumptions, Eqlog's operational semantics is logically complete. In effect, this paper shows how to expand the paradigm of logic programming with a number of features that are prominent in current programming methodology, without any sacrifice of logical rigor. Beyond simple functional programming, Eqlog also provides strong typing, user definable abstract data types, and generic (i.e., "parameterized") modules, using methods developed for the specification language Clear. A very useful refinement is "subsorts," which provide polymorphic operators and an inheritance relation on types of data. We show that our logic admits "initial models" having properties that generalize those of minimal Herbrand models for ordinary Horn clause logic. All of these features are given a rigorous semantics in terms of the underlying logic, and illustrated with a number of examples, including the well-known Missionaries and Cannibals problem and some natural language processing problems. %A Yonathan Malachi %A Zohar Manna %A Richard Waldinger %T TABLOG: a new approach to logic programming %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 365-394 %X The Manna-Waldinger deductive tableau proof system is employed as an interpreter for TABLOG in the same way that PROLOG uses an SLD resolution proof system. Unification is used by TABLOG to match a call with a line in the program and to bind arguments. The basic rules of deduction used for computing are nonclausal resolution and an equality rule that can be viewed as a generalization of narrowing and paramodulation. In this article we describe the basic features of TABLOG and its (implemented) sequential interpreter and we discuss some of its properties. We give examples of programs for which TABLOG is better than a functional language like LISP and others for which it is better than a relational language like PROLOG. %A Robert G. Bandes %T Constraining\-unification and the programming language Unicorn %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 397-410 %X Up to this point, direct implementations of axiomatic or equational specifications have been limited because the implementation mechanisms are incapable of capturing the full semantics of the specifications. The programming language Unicorn was designed and implemented with the intention of exploring the full potential of programming with equations. Unicorn introduces a new language mechanism, called constraining-unification. When coupled with semantic unification, constraining-unification closely models the semantics of equational specifications thereby allowing for the implementation of a wider class of specifications. Unlike the language mechanisms of rewrite-rule and logic programming, constraining-unification is free of order dependencies. The same results are produced regardless of the order in which the axioms are stated. The use of viewpoints contributes to the flexibility of the Unicorn language. Preconditions for partial operations can be specified without added machinery. %A Kenneth M. Kahn %T Uniform \- a Language based upon unification which unifies (much of) Lisp, Prolog, and Act 1 %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 411-438 %X Uniform is an AI programming language based upon augmented unification. It is an attempt to combine, in a simple coherent framework, the most important features of Lisp, actor languages such as Act 1 and SmallTalk, and logic programming languages such as Prolog. Among the unusual abilities of the language is its ability to use the same program as a function, an inverse function, a predicate, a pattern, or a generator. All of these uses can be performed upon concrete, symbolic, and partially instantiated data. Uniform features automatic inheritance from multiple super classes, facilities for the manipulation of programs, and a unification-oriented database. %A Joxan Jaffar %A Jean-Louis Lassez %A Michael J. Maher %T A logic programming language scheme %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 441-467 %X Numerous extended versions of PROLOG are now emerging. In order to provide greater versatility and expressive power, some versions allow functional programming features; others allow infinite data structres. However, there is concern that such languages may have little connection left with logic. In some instances, various logic frameworks have been proposed to solve this problem. Nevertheless, the crucial point has not been addressed: the preservation of the unique semantic properties of logic programs. The significance of our effort here is twofold: (1) There is a natural logic programming language scheme wherein these properties hold. (2) Formal foundations for extended versions of traditional PROLOG can be obtained as instances of this scheme. They automatically enjoy its properties. %A Gert Smolka %T Fresh: a higher-order language with unification and multiple results %B Logic programming: relations, functions, and equations %E Doug DeGroot %E Gary Lindstrom %I Prentice-Hall %D 1985 %K lpfre %P 469-524 %X This paper presents Fresh, a language that integrates logic programming features into higher-order functional programming. The language incorporates unification, multiple results and a collection construct. Many examples illustrate that these extensions of functional programming are useful. We define an operational semantics along the lines of Plotkin's structural approach. The semantics is of intrinsic interest since it covers backtracking and the collection construct. To illustrate the conceptual similarities and differences between logic and functional programming, we begin with a purely functional core language and add first unification and then backtracking. With each addition we discuss the enhanced eloquence of the language and the concomitant modifications to the semantics.