From fc4ba27f71e8a806d95fb441c1ee2e8e065b48fe Mon Sep 17 00:00:00 2001 From: Arnaud Bailly Date: Wed, 10 Dec 2025 17:19:36 +0100 Subject: Add basic readme for Prolog workshop --- prolog/README.html | 453 +++++++++++++++++++++++++++++++++++++++++++++++++++ prolog/README.md | 152 +++++++++++++++-- prolog/star-wars.jpg | Bin 0 -> 530628 bytes prolog/workbench.jpg | Bin 0 -> 1815874 bytes 4 files changed, 592 insertions(+), 13 deletions(-) create mode 100644 prolog/README.html create mode 100644 prolog/star-wars.jpg create mode 100644 prolog/workbench.jpg (limited to 'prolog') diff --git a/prolog/README.html b/prolog/README.html new file mode 100644 index 0000000..e521647 --- /dev/null +++ b/prolog/README.html @@ -0,0 +1,453 @@ + + + + + + + + Implementing Prolog + + + + + + + + + +
+
+ +
+

Implementing Prolog

+

A λ-Nantes Workshop

+

arnaud@pankzsoft.com - @abailly.bsky.social

+

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.

+
female(leia).
+male(vader).
+male(luke).
+male(kylo).
+
+
+

Example - Facts

+

More complex facts asserting a childhood +relation between some characters.

+
child(luke, vader).
+child(leia, vader).
+child(kylo, leia).
+
+
+

Example - Rules

+

Rules (or Clauses) allowing to infer some relation +from other relations.

+
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

+
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

+
> ?- grandchild(X, vader).
+success. Type [Enter] to list solutions.
+>
+[X -> kylo]
+
+
+

Example - Query

+

A Prolog query can have several answers:

+
> ?- child(X, vader).
+success. Type [Enter] to list solutions.
+>
+[X -> luke]
+>
+[X -> leia]
+
+
+

Example - Query

+

Or no answer:

+
> ?- 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. +
  2. Pop up current goal from the stack
    3. +
  3. Try to match goal with each +clause: +
      +
    1. Unify goal with the head of +clause with fresh variables
      2. +
    2. If unification succeeds, push premises of +clause onto goals stack
      3. +
    4. +
  4. Query succeeds if stack is empty with a successful +match
    5. +
+
+
+

Unification

+

Given two terms t1 and t2 with free +variables fv(t1), +fv(t2), +unification is the process of defining a substitution between +variables and terms

+

σ : fv(t1) ∪ fv(t2) → 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

+
    +
  • σ(X, Y) = {X ↦ Y}
    • +
  • σ(X, foo) = {X ↦ foo}
    • +
  • σ(foo, X) = {X ↦ foo}
    • +
  • σ(foo(bar, Y), foo(X, Z)) = {X ↦ bar, Y ↦ Z}
    • +
+
+
+
+

Practice

+

+
+
+

References

+ +
+
+
+ + + + + + + + + + + diff --git a/prolog/README.md b/prolog/README.md index d9d6ca0..2501090 100644 --- a/prolog/README.md +++ b/prolog/README.md @@ -1,16 +1,142 @@ -# Implementing Prolog - -## Basics - -* terms: - * variables start with upper casae: `X`, `Y`... - * symbols start with lower case: `s`, `z`, `child`, ... - * symbols have arity 0 or more : `bob`, `child(X, Y)`, `father(bob, Z)`... -* clauses: - * _head_: a single term - * _premises_: a (possibly empty) list of terms -* a _data set_ is a list of clauses -* _queries_ are +--- +title: Implementing Prolog +subtitle: A λ-Nantes Workshop +author: arnaud@pankzsoft.com - @abailly.bsky.social +date: 2025-12-10 +--- + +# Usage + +![](star-wars.jpg) + +## 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 + +![](workbench.jpg) ## References diff --git a/prolog/star-wars.jpg b/prolog/star-wars.jpg new file mode 100644 index 0000000..1b9561f Binary files /dev/null and b/prolog/star-wars.jpg differ diff --git a/prolog/workbench.jpg b/prolog/workbench.jpg new file mode 100644 index 0000000..f81de1a Binary files /dev/null and b/prolog/workbench.jpg differ -- cgit v1.3.1