summaryrefslogtreecommitdiff
path: root/sites/prolog.pmikkelsen.com/documentation/tutorial/2.-prolog-primer.md
blob: f26345e2f72fbb572148ec4a96086436433f24bd (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# Introduction

This page provides a *very* brief overview of prolog. For more documentation look at 
[the documentation page](https://pprolog.org/documentation/). 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.