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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
---
title: Implementing Prolog
subtitle: A λ-Nantes Workshop
author: arnaud@pankzsoft.com - @abailly.bsky.social
date: 2025-12-10
---
# Usage
## Example
A _program_ about Star Wars characters (including the crappy recent ones)
## Example - Facts
Simple facts asserting the gender of some characters.
```prolog
female(leia).
male(vader).
male(luke).
male(kylo).
```
## Example - Facts
More complex facts asserting a `child`hood _relation_ between some characters.
```prolog
child(luke, vader).
child(leia, vader).
child(kylo, leia).
```
## Example - Rules
_Rules_ (or _Clauses_) allowing to infer some relation from other relations.
```prolog
son(X,Y) :- male(X), child(X,Y).
daughter(X,Y) :- female(X), child(X,Y).
```
## Example - Rules
More complex rules asserting a transitive relation
```prolog
grandchild(X,Z) :- child(X,Y), child(Y,Z).
```
## Example - Query
We can _query_ this program, for example asking who is a grandchild of Darth Vader
```prolog
> ?- grandchild(X, vader).
success. Type [Enter] to list solutions.
>
[X -> kylo]
```
## Example - Query
A Prolog query can have several answers:
```prolog
> ?- child(X, vader).
success. Type [Enter] to list solutions.
>
[X -> luke]
>
[X -> leia]
```
## Example - Query
Or no answer:
```prolog
> ?- grandchild(leia, X).
failure
```
# Implementation
## Terms
* variables start with upper casae: `X`, `Y`...
* symbols start with lower case: `s`, `z`, `child`, ...
* symbols have 0 or more arguments, e.g an _arity_ : `bob`, `child(X, Y)`, `father(bob, Z)`...
## Clauses
* _head_: a single term
* _premises_: a (possibly empty) list of terms
* a _data set_ (or a _program_) is a list of clauses or _facts_
* a _query_ is a term introduced with `?-`
## Basic algorithm
Given a query and a set of clauses, a Prolog interpreter loop goes like:
1. Push _query_ on its goal stack
2. Pop up current _goal_ from the stack
3. Try to match _goal_ with each _clause_:
a. _Unify_ goal with the _head_ of _clause_ with _fresh_ variables
b. If unification succeeds, push _premises_ of clause onto goals stack
4. Query succeeds if stack is empty with a successful match
## Unification
Given two terms $t_1$ and $t_2$ with _free variables_ $fv(t_1)$, $fv(t_2)$,
unification is the process of defining a _substitution_ between variables and _terms_
$$
\sigma : fv(t_1) \cup fv(t_2) \rightarrow T
$$
## Unification
* Two variables unify with each other
* A variable unifies with a term if not already mapped
* Two relations unify with each other iff
* Their symbol is the same
* Their arguments unify with each other
## Unification
* $\sigma(X, Y) = \{ X \mapsto Y \}$
* $\sigma(X, foo) = \{ X \mapsto foo \}$
* $\sigma(foo, X) = \{ X \mapsto foo \}$
* $\sigma(foo(bar, Y), foo(X, Z)) = \{ X \mapsto bar, Y \mapsto Z \}$
# Practice
## References
* [NanoProlog](https://github.com/norm2782/NanoProlog)
* [hslogic](https://github.com/abailly/hslogic)
* [miniprolog](https://github.com/andrejbauer/plzoo/tree/master/src/miniprolog)
|
