Download free books at BookBooN.com

Skip to main content

Prolog Techniques English

  • Author Attila Csenki
  • ISBN 978-87-7681-476-2
  • 1 edition
  • 186 pages

Description

The book Prolog Techniques is the first of two volumes by the author on the programming language Prolog and its applications; the second, forthcoming, textbook is entitled Applications of Prolog. In the first volume you can read about the accumulator technique, difference lists, program manipulations and exploratory code development. The book refers to ten different Prolog source files, you can download them here.

1

2

3

You need to have Adobe Reader installed in order to open the books from BookBoon.com Get Adobe Reader

Preface

Prolog is considered difficult by students. Usually, by the time they learn Prolog, which is most likely to happen in preparation for a course in Artificial Intelligence (AI) or Expert Systems, they will have studied imperative programming and/or the object oriented paradigm. Unfortunately, this prior experience is not always conducive to learning Prolog. Even though there is a good provision of traditional Prolog textbooks (for example [2]), students still find it hard to write solutions in Prolog to problems of any notable complexity. In my experience this holds also (and in particular) for problems for which Prolog should be the natural choice.

This book is intended to relieve the problem by providing a good collection of programming projects, case studies and exercises of various complexity. It will be useful for three kinds of students.

- Those whose prime source of information is a traditional introductory lecture course in Prolog. For these people my book will serve to show in context how the various programming techniques and language elements may be employed. The book may be used to accompany such a course as a workbook and the student should find in it a wealth of information to answer questions concerning the aspects of Prolog taught in the course.

- Those who want to refresh and extend their knowledge of Prolog, perhaps with some field of application in mind.

- Students of AI learning about search algorithms in particular. Most AI books present search algorithms by pseudocode and are not concerned with details of implementation. In my experience, however, anything seen implemented is more likely to be retained (beyond the exam).

There is a deeper reason also why such a book is felt timely. Programming is a creative activity and it is an innate human need to take pleasure (and pride) in the object of one’s creation, be it a sculpture, a painting, a piece of music, or indeed, a computer program. The opportunity is provided here for students to learn (and experience the said intellectual satisfaction) by creating their own solutions in Prolog to a host of interesting, challenging and varied programming problems. Many of the problems and the way they are approached here are believed to be novel.

Sadly, it is felt that the creative aspect of learning is not given enough room in today’s educational environment in the UK.1 It is hoped that this book will help the student to rediscover Prolog programming as a worthwhile and enjoyable activity.

The core of the material in this book grew out of laboratory classes and coursework prepared by the author for second year computer science students at Bradford University, as part of the lecture course Symbolic and Declarative Computing – Artificial Intelligence. This is a two-semester course with an introduction to Functional Programming with Haskell, Logic Programming with Prolog and the basics of AI. The choice of examples and topics for this book is of course tinged by the context in which Prolog was presented. For example, I discuss the functional programming style since it is useful in producing concise, readable and elegant implementations also in Prolog. The selection of topics for the examples was influenced in part by the AI element of the course though much new material has found its way into the book. To make set problems more easily accessible for the reader, I subdivide the overall task into managable portions indicating in each the desired outcome (if applicable, in form of a sample session in Prolog) with suggestions for how best to attack the subtasks.

The working style advocated here is best described by the following attributes:

- example based,

- interactive,

- exploratory and experimental,

- incremental,

- progressing from the specific to the more general,

- identifying patterns of computation with a view to generalization.

It will be seen from the list of contents that the material, by its very nature, is not ordered in a linear fashion but is grouped in topics deemed important for programming in Prolog.

The work comprises two parts: the present volume Prolog Techniques and the forthcoming Applications of Prolog. This first volume is in four chapters and illustrates special Prolog programming techniques. The second volume will concentrate on applications of Prolog, mainly from Artificial Intelligence.

The order in which the books may be studied is fairly free even though an example introduced somewhere may serve in a later chapter to illustrate the generalization or improvement afforded by the material just covered.

The SWI-Prolog compiler is used throughout: it has been around for quite some time; it is well documented; it is free; and, it is being maintained with new, improved versions becoming available all the time. Furthermore, there is an object oriented extension to SWI-Prolog (XPCE) for building graphical applications, useful if one wants to pursue this line further.

Solutions for a selection of exercises are discussed in the appendices. All Prolog source code produced in the course of this book project (including model solutions for all the exercises) can be downloaded from the Ventus website.

I am grateful to Dr. Coxhead of Birmingham University for discussions and extensive comments on initial versions of several of the chapters. My colleague Dr. Fretwell gave me many tips concerning LATEX, the typesetting system used to produce the books.

Attila Csenki

Bradford

April 2009

Contents

Preface

1 Accumulator Technique
1.1 A Simple Example
1.2 Hand Computations
1.3 Further Examples
1.4 Pseudocodes
1.5 Generalization
1.6 Case Study: The Perceptron Training Algorithm
1.6.1 Classification Problem
1.6.2 Algorithm
1.6.3 Implementation

2 Difference Lists
2.1 Implementations of List Concatenation
2.2 Implementations of List Flattening
2.2.1 Project: Lists as Trees & flatten/2
2.2.2 Flattening Lists by append/3
2.2.3 flatten/2 by the Difference List Technique
2.2.4 Comparing Different Versions
2.3 Implementations of List Reversal
2.3.1 Program Transformations
2.3.2 Difference Lists as Accumulators
2.4 Case Study: Dijkstra’s Dutch Flag Problem
2.4.1 Basic Implementation Using append/3
2.4.2 A More Concise Version
2.4.3 Using Difference Lists
2.5 Rotations
2.5.1 Rotating a List
2.5.2 The Perceptron Training Algorithm Revisited
2.5.3 Planar Rotations
2.5.4 Application: The Gauss–Seidel Method

3 Program Manipulations
3.1 Simple Database Operations
3.1.1 Basic Database Manipulation
3.1.2 Changing the Database
3.1.3 File Modifications
3.1.4 Updating right_to/2 and people.pl
3.1.5 Automated Saving of Selected Predicates
3.1.6 Miniproject: Modelling a Stamp Collection
3.2 Case Study: Automated Unfolding
3.2.1 Elementary Unfolding
3.2.2 Complete One Step Unfolding
3.2.3 Rearranging Clauses
3.3 Dijkstra’s Dutch Flag Problem Revisited
3.3.1 Problem Generalization and First Solution
3.3.2 Enhanced Implementations

4 Exploratory Code Development
4.1 A Nursery Rhyme
4.1.1 First Preliminary Implementation
4.1.2 Another Preliminary Implementation
4.1.3 The Final Version
4.1.4 Other Approaches
4.2 Project: ’One Man Went to Mow ...’
4.3 Chapter Notes

A. Solutions of Selected Exercises
A.1 Chapter 1 Exercises
A.2 Chapter 2 Exercises
A.3 Chapter 3 Exercises
A.4 Chapter 4 Exercises

B. Software

C. Glossary

References

Index

List of Figures

1.1 Hand Computations for new sum/2

1.2 Hand Computations for rev/2

1.3 Hand Computations for min/2

1.4 Suggested Hand Computations for from to/3

1.5 Hand Computations for cnt/3

1.6 Hand Computations for palin/1 — success

1.7 Hand Computations for palin/1 — failure

1.8 Typical Clause Structures of a Predicate with an Accumulator

1.9 Generalized Clause Structures

1.10 A Linearly Separable Data Set

1.11 Classifying a Point

1.12 A Single Updating Step

1.13 Applying the Perceptron Training Algorithm

2.1 Difference List

2.2 List Concatenation by Difference Lists

2.3 Tree Representation of [a,[b,[],[c,a],e]]

2.4 Declarative Reading of (P-2.3)

2.5 Illustrating Clause (b2) in (P-2.6)

2.6 Illustrating Exercise 2.9

2.7 Rotating by Difference Lists

2.8 Hand Computations for averages/2

2.9 Rotating a List with Four Entries

2.10 The Original List and its Rotated Image

2.11 The Original Matrix A and its Rotated Image A(rot)

2.12 Hand Computations for Rotation in the Plane

3.1 The Initial Seating Arrangement

3.2 Rectangular Table

3.3 After George’s Departure

3.4 After Tracy’s and Joe’s arrival

3.5 File Organization for the Round Table Example

3.6 The File people.pl after the Interactive Session

3.7 The File committee.pl

3.8 The File committee.pl

3.9 Interactive Prolog–Assisted Program Transformation: Session I

3.10 Interactive Prolog–Assisted Program Transformation: Session II

3.11 Unfolding, Experiment 1: Disassembling clause 4 of a/5

3.12 Unfolding, Experiment 2: Disassembling clause 3 of c/2

3.13 Unfolding, Experiment 3: Experiments 1 & 2 followed by appropriate unification

3.14 Unfolding, Experiment 4: Experiment 3 followed by new clause creation and database update

3.15 Illustrative Example of Intended Database Updates

3.16 Top Level Definition of def_encolour dl/1

3.17 Example Session for Exercise 3.19

4.1 The Rhyme’s Simplified Pattern

4.2 Exploring Details of the Rhyme’s Structure

4.3 Desired Behaviour of song/0

A.1 Annotated Hand Computations for from to/3

A.2 Hand Computations for mult/3

A.3 Illustrating the Second Clause of dl/2

A.4 The Last Two Customers Swap Places

A.5 Automated Solution of Exercise 2.9, Part (c)

A.6 Database Changes Brought About by cosu/3

A.7 Search Tree of the Query ?- int(1,I)

List of Tables

1.1 Algorithm

1.4.1 and Related Hand Computations (Fig. 1.2)

1.2 Algorithm 1.4.2 and Related Hand Computations (Fig. 1.5)

1.3 Algorithm 1.4.3 and Related Hand Computations (Figs. 1.6 & 1.7)

1.4 Co-ordinates of Points in the Plane with Class Labels

2.1 Gauss–Seidel Iterations

3.1 Cases for swap_neighbours/2

4.1 Rhyme Structure

4.2 CPU Times for Versions of the Query - rhyme_prel( V, R)

A.1 Algorithm A.1.1 & Prolog Clause Correspondence (Example 1.6)

« Back to overview

The book is being downloaded...

(If you don't see a pop-up window, you need to edit your browser settings)

You might also be interested in the following books

Other people downloading ‘Prolog Techniques’ are also downloading the following books:

Receive information about new free books