Applications of Prolog

This book is the second volume by the author on Prolog programming and its applications written for Ventus. Whereas in the first book [9], specific Prolog programming techniques were explained, in this volume we discuss some areas where Prolog can be fruitfully employed.

Both books owe their existence to the recognition that the higher educational system (in the UK) does not offer enough opportunities for students to experience the satisfaction associated with successfully completing a technical task. In the writer’s opinion, the learning experience of today’s average student is dominated too much by assessments.

The book comprises four chapters, the first three of them are devoted to Prolog in Artificial Intelligence (AI). The last one is on text processing using Prolog with LATEX in mind.

The first chapter solves an intriguing AI puzzle which was first published in the New Scientist magazine [1] in 2003. The Prolog solution presented here combines problem specific knowledge using Finite Mathematics with the well-know AI technique ‘generate-and-test’. Even though this chapter did not emanate from my teaching activities, the presentation follows a well-tested pattern: the problem is broken down into manageable and identifiable subproblems which then are more or less readily implemented in Prolog. Many interesting hurdles are identified and solved thereby. The availability of unification as a pattern matching tool makes Prolog uniquely suitable for solving such problems. This first chapter is an adaptation of work reported in [7]. Further recent developments on solving this problem can be found in [4].

The second and third chapters are respectively devoted to blind search and informed search. The material presented in them can be used in lectures to teach Prolog for AI as well as in AI lectures themselves. I have tried to compile a varied and interesting mixture of applications most of which won’t be available anywhere else. Some of the problems considered here served over the years in my lectures as coursework material, though, for various reasons, the discussion is more thorough here.

The fourth chapter is the least conventional one for a Prolog book. It is in two parts.

1. A tool is developed in Prolog for manipulating LATEX files.

2. Prolog is used to generate LATEX commands for drawing parametric curves in documents written in LATEX.

I also explain here how an SWI-Prolog program can be embedded into a Linux shell script, removing thereby the need for the user to deal with Prolog directly. This results in applications of direct practical interest.

For the maximum benefit (and fun) readers should work through parts of this book interactively with SWI-Prolog. I have tried to retain the experimental and exploratory style of the first volume [9] even though sometimes digression to more theoretical topics was unavoidable.

There are 54 exercises in this book, 32 of them are solved in Appendix A. The last chapter is somewhat of an exception since there the exercises themselves are the main vehicle for conveying the subject material. Therefore, detailed sample solutions are provided for 6 of the 7 exercises in that chapter.

The associated software (Prolog sorces, Linux shell scripts, data files) listed in Appendix B is freely available from the Ventus website. All three systems used here (Linux, SWI-Prolog, LATEX) are freely available on the Internet.

1. Enigma 1225: Rows are Columns
   1. A Puzzle
   2. First Thoughts
   3. Symbolic Solutions
   4. Implementation Details
   5. Enhanced Implementation
2. Blind Search
   1. Digression on theModule System in Prolog
   2. Basic Search Problem
   3. Depth First Search
   4. Breadth First Search
   5. Bounded Depth First Search
   6. Iterative Deepening
   7. The Module blindsearches
   8. Application: A Loop Puzzle
   9. Application: The Eight Puzzle
3. InformedSearch
   1. The Network Search Problemwith Costs
   2. Case Study: The Eight Puzzle Revisited
   3. Project: Robot Navigation
   4. Project: The Shortest Route in aMaze
   5. Project: Moving a Knight
4. Text Processing
   1. Text Removal
   2. Text Generation and Drawing with LATEX
   3. Exercises
5. Solutions of Selected Exercises
   1. Chapter 1 Exercises
   2. Chapter 2 Exercises
   3. Chapter 3 Exercises
   4. Chapter 4 Exercises
6. Software
7. References
8. Index
9. Errata to Volume 1