Examples of PROLOG code I have written.

Described below are two PROLOG programs. The first is a generic searching program using three search algorithms: depth-first, breadth-first and best-first. It is used to find solutions to the Knight's move and water jug problems (described below). The second is a simple English parsing program which uses multiple inheritance to define nouns, verbs and articles. The links for downloading the source code are at the end of each section.


Depth-first, breadth-first and depth-first searching program

The following PROLOG code solves the water jugs and knight moves problems using depth-first, breadth-first and best-first search algorithms. It searches the space defined by the 'move' rule. Thus, since the move rules may be redefined, this code represents a generic searching program. I used the code from the class supplement, with minor modifications, for the search algorithms. These are the first three files attached below. Following that is the code for the ADT's stack, set, queue and priority queue, again taken from the class supplement with minor modifications. For the heuristic predicate of the priority queue, I simply used the distance (squared) between the current state and the goal state. Following the ADT's are the move rules, first for the water jug problem followed by the knight moves problem.

Description of problems:

The water jug problem consists of a small and a large jug, of arbitrary size. Legal moves consist of emptying either jug, filling either jug, emptying either jug into the other until the other is full, or until the first one is empty. The jugs begin with an arbitrary integer quantity of fluid in each, with the goal being to reach a given final state using only the moves described above. The final state is to have each jug contain any arbitrary integer quantity of fluid, and may be the same or different from the initial state.

The knight moves problem consists of moving a knight on a chess-board of arbitrary size from an arbitrary starting position to an arbitrary final position, using only legal knight moves (i.e. one up and two over).


Analysis:

Considering the water jugs problem, it is apparent that the depth-first search is less efficient than the breadth-first or best-first search. For example, in moving from the initial state of [1,4] to [empty, empty] (where the first number indicates the amount of liquid in the small jug, the second number is for the large jug), the depth-first algorithm takes four moves:

[1,4] ->[5,4]->[5,6]->[0,6]->[0,0]

while the other two search algorithms only take two moves:

[1,4]->[0,4]->[0,0].

This is because the depth-first search plunges ahead with searching the descendants of the first child before going on to the next child, whereas the other two searches look at all the children before going on to the grandchildren, and it turns out the solution in this case is only one layer deep.

An example in which the breadth-first search out-performs both the best-first and the depth-first searches is in going from [3,2] to [1,5]. The depth-first and best-first searches each take 10 moves while the breadth-first takes 5 moves. Apparently I did not chose a good heuristic algorithm for this case.

The breadth-first search also wins out in going from [0,0] to [3,2]. It only takes three moves while the other two take 14! Here the heuristic algorithm almost catches the best initial move, which is to go to [0,5]. However, it instead goes to the state [3,0], which has the same heuristic value as [0,5] and is at the same depth as [0,5] but is stumbled upon before [0,5], which means it is given precedence over [0,5]. This sets the best-first search off on the wrong path, and it takes a while for it to recover.

For the knight's path problem, the breadth-first search is the winner for the examples I tried, and the depth-first search is the loser. A better heuristic algorithm would have been to take into account that it is better for a knight to be at a distance of 5 from the goal than at a distance less than 5 but greater than zero (5 = 2 X 2 + 1 X 1), since then only one move is required to reach the goal.

You can download the source code here:
  1. depth-first search code
  2. breadth-first search code
  3. best-first search code
  4. ADT stack
  5. ADT set
  6. ADT queue
  7. ADT priority-queue
  8. water-jugs move rules
  9. knight's path move rules

Simple English parsing program

This program will parse simple English sentences to determine if the grammar is correct. It is context sensitive in the sense that it enforces noun-verb and noun-article agreement. For example, if a plural noun is used, the plural verb must also be used (e.g.. 'the man likes the dog' is valid but 'the men likes the dog' is not valid). It uses a dictionary that contains the following words:

noun
man
men
woman
women
dog
dogs
verb
likes
like
bites
bite
adjective
big
small
adverb
strongly
very
quite
article
a
the
conjunction
and
but
preposition
on
The nouns, verbs and articles are defined using multiple inheritance. Below is a schematic diagram of the semantic network used in the program. The remaining words are defined using simple rules.
You can download the source code here:
  1. simple parsing program.