1  ---
  2  title: Implementing Prolog
  3  subtitle: A λ-Nantes Workshop
  4  author: arnaud@pankzsoft.com - @abailly.bsky.social
  5  date: 2025-12-10
  6  ---
  7  
  8  # Usage
  9  
 10  ![](star-wars.jpg)
 11  
 12  ## Example
 13  
 14  A _program_ about Star Wars characters (including the crappy recent ones)
 15  
 16  ## Example - Facts
 17  
 18  Simple facts asserting the gender of some characters.
 19  
 20  ```prolog
 21  female(leia).
 22  male(vader).
 23  male(luke).
 24  male(kylo).
 25  ```
 26  
 27  ## Example - Facts
 28  
 29  More complex facts asserting a `child`hood _relation_ between some characters.
 30  
 31  ```prolog
 32  child(luke, vader).
 33  child(leia, vader).
 34  child(kylo, leia).
 35  ```
 36  
 37  ## Example - Rules
 38  
 39  _Rules_ (or _Clauses_) allowing to infer some relation from other relations.
 40  
 41  ```prolog
 42  son(X,Y) :- male(X), child(X,Y).
 43  daughter(X,Y) :- female(X), child(X,Y).
 44  ```
 45  
 46  ## Example - Rules
 47  
 48  More complex rules asserting a transitive relation
 49  
 50  ```prolog
 51  grandchild(X,Z) :- child(X,Y), child(Y,Z).
 52  ```
 53  
 54  ## Example - Query
 55  
 56  We can _query_ this program, for example asking who is a grandchild of Darth Vader
 57  
 58  ```prolog
 59  > ?- grandchild(X, vader).
 60  success. Type [Enter] to list solutions.
 61  >
 62  [X -> kylo]
 63  ```
 64  
 65  ## Example - Query
 66  
 67  A Prolog query can have several answers:
 68  
 69  ```prolog
 70  > ?- child(X, vader).
 71  success. Type [Enter] to list solutions.
 72  >
 73  [X -> luke]
 74  >
 75  [X -> leia]
 76  ```
 77  
 78  ## Example - Query
 79  
 80  Or no answer:
 81  
 82  ```prolog
 83  > ?- grandchild(leia, X).
 84  failure
 85  ```
 86  
 87  # Implementation
 88  
 89  ## Terms
 90  
 91  * variables start with upper casae: `X`, `Y`...
 92  * symbols start with lower case: `s`, `z`, `child`, ...
 93  * symbols have 0 or more arguments, e.g an _arity_ : `bob`, `child(X, Y)`, `father(bob, Z)`...
 94  
 95  ## Clauses
 96  
 97  * _head_: a single term
 98  * _premises_: a (possibly empty) list of terms
 99  * a _data set_ (or a _program_) is a list of clauses or _facts_
100  * a _query_ is a term introduced with `?-`
101  
102  ## Basic algorithm
103  
104  Given a query and a set of clauses, a Prolog interpreter loop goes like:
105  
106  1. Push _query_ on its goal stack
107  2. Pop up current _goal_ from the stack
108  3. Try to match _goal_ with each _clause_:
109     a. _Unify_ goal with the _head_ of _clause_ with _fresh_ variables
110     b. If unification succeeds, push _premises_ of clause onto goals stack
111  4. Query succeeds if stack is empty with a successful match
112  
113  ## Unification
114  
115  Given two terms $t_1$ and $t_2$ with _free variables_ $fv(t_1)$, $fv(t_2)$,
116  unification is the process of defining a _substitution_ between variables and _terms_
117  
118  $$
119  \sigma : fv(t_1) \cup fv(t_2) \rightarrow T
120  $$
121  
122  ## Unification
123  
124  * Two variables unify with each other
125  * A variable unifies with a term if not already mapped
126  * Two relations unify with each other iff
127    * Their symbol is the same
128    * Their arguments unify with each other
129  
130  ## Unification
131  
132  * $\sigma(X, Y) = \{ X \mapsto Y \}$
133  * $\sigma(X, foo) = \{ X \mapsto foo \}$
134  * $\sigma(foo, X) = \{ X \mapsto foo \}$
135  * $\sigma(foo(bar, Y), foo(X, Z)) = \{ X \mapsto bar, Y \mapsto Z \}$
136  
137  # Practice
138  
139  ![](workbench.jpg)
140  
141  ## References
142  
143  * [NanoProlog](https://github.com/norm2782/NanoProlog)
144  * [hslogic](https://github.com/abailly/hslogic)
145  * [miniprolog](https://github.com/andrejbauer/plzoo/tree/master/src/miniprolog)