LPL0(ID:8421/)Extenstion to the LPL by Haridi & Sahlin Related languages
References: in Clark, K.L. et al eds, Logic Programming, Academic Press 1982. view details in Clark, K.L. et al eds, Logic Programming, Academic Press 1982. view details in Clark, K.L. et al eds, Logic Programming, Academic Press 1982. view details Symbol Manipulation. Expert System Programming. Database Software Modelling. Test-implementations of Interpreters and Compilers. Protocol Verification. Graph-Algorithms. This document is a brief introduction to logic programming using a language in the PROLOG-family, LPL0, which has been implemented under the operating system UNIX at CSALAB. External link: Online copy Extract: Introduction Logic as a Programming Language -- The background of LPL0. The idea of using logic as a programming language has been present in the computer science community for a long time. Theorem provers were implemented early, but with only limited capacity regarding speed and storage. The use of the so called resolution principle as suggested by Robinson in the mid-sixties was an important contribution. The idea of using a limited, but efficient, algorithm for proving theorems as the basis of a programming language, where proofs of propositions are equivalent to the construction of terms, led to the Marseille implementation of Prolog in 1972. Since then, several implementations of Prolog have been made with somewhat varying computational strategies in different cases. Particularly noteworthy is Dec-10 Prolog by David Warren et. al. which includes a compiler that generates efficient machine-code. Currently, Logic Programming is attracting the interest of many researchers in the field of computer science. Like functional languages it lends itself to a parallel execution with automatic distribution of small tasks over a network of processing elements. A language in the PROLOG-family but excluding some of the non- logical features of PROLOG, called LPL0, has been implemented in the UNIX-environment at our lab by Dan Sahlin and Seif Haridi. This subset has much in common with PROLOG but it also includes a functional interpretation of deterministic predicates and arithmetic expressions and some other features that make it different from other PROLOGs. The syntax of the language differs slightly from that of Dec-10 PROLOG, but the execution mechanism is basically the same. The system includes tail recursion optimization and a garbage collector. The system was originally intended as an implementation of the logic programming language, LPL, described by Hansson, Haridi and Tarnlund in [ClTa], but several of the characteristics of this language were excluded during the implementation, mainly due to implementation difficulties. Another system based on Natural Deduction and implemented as an interpreter in the language described here, LPL0, is named GEPR (or sometimes LPL) and is described in [HaSa2]. The implementation of the LPL0 language is described in [HaSa1]. Representing a Program as Horn Clauses. Horn Clauses are a subset of the statements of Predicate Logic named after the logician Alfred Horn. A Horn clause has two parts: The head and the body. The body may be empty and the clause is then called an "assertion". An assertion represents a simple fact about its parameters, while the body of a Horn Clause represents conditional facts that have to be true for the head statement to be valid. Example: p(17). p(x) <- x<8 & q(x). p(x) <- q(x) or p(x-1). In english the above example could be stated as follows: The property p holds for the constant 17. The property p holds for a term x if x<8 and q holds for x. The property p holds for x if q holds for x or p holds for x-1. When several clauses exist with the same name, they represent alternative facts and rules about this relation. The connective 'or' in the body of a statement also represents alternative facts about the relation, at least one of which should be true for the relation to hold. The connective '&' connects the goals in the body together, all of which should be true for that alternative of the relation to hold. A program can be understood in either of two ways. First it can be seen as a set of Horn clauses (and functions) stating facts about data. This is the declarative reading of a logic program. Second, considering the particular execution mechanism used in the logic programming system at hand, it can be viewed as a program describing a particular execution. In order to control the program flow, certain non-logical (or extra-logical) predicates are used which do not express any facts about the terms we are talking about. This is the "Procedural Reading" of a logic program. The execution of a logic program could be considered as a constructive proof procedure, where the system attempts at proving a given goal statement in a given environment of computation. If a proof succeeds under some restrictions on the variables in the given goal, these restrictions are shown as "bindings" of the variables. in Clark, K.L. et al eds, Logic Programming, Academic Press 1982. view details Resources
|