PProlog A prolog for plan9

Introduction

This page provides a very brief overview of prolog. For more documentation look at the documentation page. Also be aware that this introduction is only my explanation, so don't take it as 100% truth.

First of all, prolog is a programming language in the family of languages called logic programming languages. This means that it is very different from imperative or functional programming, so you should read this with an open mind and try to forget some of the things you already know.

Logic

What does it mean to be a logic programming language? Well, it means that the programs written in it can be understood as logical rules and results can be inferred from those rules. This leads to a very declarative way of writing code which is often much cleaner than what could be written in C for example.

It also means that in prolog we don't write code to tell the computer what to do, we write code to express the facts and relations about a problem, and the prolog system then uses those facts and rules to infer the result.

Example

To calculate the length of a list in an imperative language like C, the following code would work.

typedef struct List List;
struct List
{
	int	element;
	List	*next;
};

int
length(List *list)
{
	int len = 0;
	for(; list != nil; list = list->next)
		len++;
	return len;
}

It is very clear that the length function takes a list as input and then runs a loop which increments len until the end of the list is reached.

Compare this to the prolog code below which is a prolog predicate with arity 2, also sometimes called length/2 to describe the name and the arity.

length([], 0).
length([_|Tail], N) :-
	length(Tail, TailLength),
	N is TailLength + 1.

This code is written in a declarative style and it doesn't express how the length of the list is found, it expresses what the length of a list is. The code consists of two clauses: a fact and a rule.

The fact length([], 0). describes that the length of an empty list ([]) is zero.

The rule

length([_|Tail], N) :-
	length(Tail, TailLength),
	N is TailLength + 1.

describes that the length of a non-empty list with head _ (we don't care about the head), and tail Tail has then length N if:

  1. The length of the tail is TailLength and
  2. N is TailLength plus one.

The rule consists of a head length([_|Tail), N) and two goals separated by a comma which means and.

Wait, is the output just the last parameter?

No, in general much prolog code describes relations between the parameters. The length predicate from before as an example of that, but it could just as well be used to check if a list has a given length, by providing an input for both arguments.

Queries

When pprolog is run it presents a toplevel where queries can be entered. The queries are like questions that the prolog system tries to answer. It does this by looking in the prolog database which initially consists of the predicates which are part of the standard library. Since length/2 is part of the standard library, we could ask

?- length([1,2,3,a,b,c], Len).

And it would respond

Len = 6.

In general, if a word starts with an uppercase letter it is a variable like Len, Hello, X and Y, and otherwise it is an atom which just represents itself.

To show that length/2 can be used in multiple ways, consider the query

?- length([1,2], 4).

What do you think it will say? The result is

false.

because it is not possible for the system to infer the the length of the list [1,2] is 4 using any of the rules in the prolog database. The steps the system takes in calculating this result are:

  1. The fact length([],0) is tried first but it fails to unify (more on that later) with the query since the empty list does not unify with our non-empty list, and 0 does not unify with 4.
  2. The rule with the head length([_|Tail], N) is chosen at it unifies with our query giving the variables Tail = [2] and N = 4.
  3. The first goal is length(Tail, TailLength) and with the value of Tail that becomes length([2], TailLenght). As in step 1, the first fact does not unify with this goal since [] does not unify with [2].
  4. The second rule unifies with our goal and the variables become Tail = [] and N = TailLength. Note that it is perfectly valid to assign two unassigned variables to each other in prolog, and this just means that they should now be considered the same, and when one of them is unified with a concrete value, the other will get that value too.
  5. The first subgoal is tried again and this time it matches the first rule since [] unifies with [], and 0 unifies TailLength with the side effect that both TailLength and N is now 0.
  6. We go back to step 4 and continue with subgoal 2 which says that N is TailLength + 1 and N is therefore 1.
  7. We go back to step 3 and continue with subgoal 2 which says that N is TailLength + 1 but this fails since N at this point was 4 and TailLength is 1, but the fact 4 = 1 + 1 is false. Since there are no more rules or facts to try, the whole query fails.

(that explanation was a mess)

Unification

say wut, like pattern matching but works both ways.