Prolog

Prolog
A Tutorial Introduction
James Lu Jerud J. Mead
Computer Science Department Bucknell University Lewisburg, PA 17387

1

Contents
1 Introduction 2 Easing into Prolog 2.1 Logic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The SWI-Prolog Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 A CloserLook at Prolog 3.1 Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Lists in Prolog 1 2 2 3 6 6 6 7 12

5 Data Input inProlog 17 5.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2 Building a Tokenizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Parsing 6.1 Low-level Parsing with Prolog . 6.2 High-level Parsing with Prolog 6.3 Parsing Expressions . . . . . . 6.4 Parsing Optional Structures . . 7 Building aSymbol Table 8 Prolog Semantics - The Computational 8.1 Unification . . . . . . . . . . . . . . . 8.2 Resolution . . . . . . . . . . . . . . . . 8.3 Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 22 22 24 25 27 Model 32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

i

1

Introduction

Logic programming is a programming paradigm based on mathematical logic. In thisparadigm the programmer specifies relationships among data values (this constitutes a logic program) and then poses queries to the execution environment (usually an interactive interpreter) in order to see whether certain relationships hold. Putting this in another way, a logic program, through explicit facts and rules, defines a base of knowledge from which implicit knowledge can be extracted. Thisstyle of programming is popular for data base interfaces, expert systems, and mathematical theorem provers. In this tutorial you will be introduced to Prolog, the primary logic programming language, through the interactive SWI-Prolog system (interpreter). You will notice that Prolog has some similarities to a functional programming language such as Hugs. A functional program consists of a sequenceof function definitions — a logic program consists of a sequence of relation definitions. Both rely heavily on recursive definitions. The big difference is in the underlying execution “engine” — i.e., the imperative parts of the languages. The execution engine of a functional language evaluates an expression by converting it to an acyclic graph and then reducing the graph to a normal form whichrepresents the computed value. The Prolog execution environment, on the other hand, doesn’t so much “compute” an answer, it “deduces” an answer from the relation definitions at hand. Rather than being given an expression to evaluate, the Prolog environment is given an expression which it interprets as a question: For what parameter values does the expression evaluate to true? You will see that Prolog isquite different from other programming languages you have studied. First, Prolog has no types. In fact, the basic logic programming environment has no literal values as such. Identifiers starting with lower-case letters denote data values (almost like values in an enumerated type) while all other identifiers denote variables. Though the basic elements of Prolog are typeless, most implementations...