In questo post aggiungeremo la relazione predecessor(antenato) al programma famiglia illustrato in precedenza. Consideriamo la relazione


predecessor(X,Y) :-
    parent(X,Y).


essa non è altro che un wrapper della regola parent e per salire nell’albero familiare è necessario riscrivere la regola in questo modo


predecessor(X,Z) :-
    parent(X,Y), parent(Y,Z).


adesso possiamo risalire l’albero familiare di un’altro grado ma per poter risalire alla radice, quindi definire qualsiasi antenato e non solo i nonni, è necessario definire la regola in termini di se stessa. L’idea base è

Per ogni X ed Y,
X è antenato di Z se esiste una Y tale che
(1) X è padre di Z e
(2) Y è a sua volta antenato di X

La traduzione in prolog è data dalle seguenti due regole

(r1)

predecessor(X,Z) :-
    parent(X, Z).

(r2)

predecessor(X , Z) :-
    parent(X, Y),
    predecessor(Y, Z).


Una regola che coinvolge se stessa nella propria definizione è detta regola ricorsiva. Nel nostro caso la prima regola è il caso banale della ricorsione, prolog per rispondere ad una query del tipo predecessor(pam,bob) tenta prima la verifica di (r1) e se quest’ultima da esito negativo viene verificata (r2) è quindi chiaro che senza (r1) si entrerebbe in un ciclo infinito nel tentativo di verificare (r2).

Ecco la nuova regola in azione:

?- predecessor(pam,X).
    X = bob;
    X = ann;
    X = pat;
    X = jim;


Ideato da Robert Kowalski (aspetto teorico), Marten Van Emdem (dimostrazione sperimentale), ed implementato da Alain Colmerauer negli anni 70, costituendo un tentativo di costruire un linguaggio di programmazione che consentisse l’espressione del problema in forma logica invece della traduzione di un algoritmo di soluzione in forma di istruzioni da eseguire da parte della macchina. (Wikipedia)

Prolog è un linguaggio di programmazione basato su pochi meccanismi basilari, come il pattern matching, strutturazione di dati basata su alberi e backtracking automatico, i quali ne fanno un potente framework di programmazione per lavorare su oggetti strutturati e relazioni tra essi. Esso ha radici profonde nella logica matematica di cui non sono richieste particolari conoscenze per usare prolog in modo pratico.

Questo post è l’inizio di una serie di lezioni che introducono alla programmazione prolog.
Lo scopo è quello di introdurre alle basi del prolog attraverso esempi.
Ad oggi esistono diverse implementazioni di prolog le quali differiscono, essenzialmente, tra essere per le funzioni built-in che offrono, quella usata per testare gli esempi di questo tutorial è XSB, è consigliata anche GNU Prolog.

Vediamo subito un esempio di programma che definisce le relazioni di una famiglia di persone. Il fatto che tom sia il padre di bob può essere scritto come segue:

parent(tom,bob).

In questo caso parent è il nome della relazione mentre tom e bob sono argomenti, grazie ad essa possiamo rappresentare un intero albero familiare come segue:


parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

Queste righe di codice compongono un programma prolog vero e proprio composto da sei clausole e ciascuna di esse dichiara un fatto riguardante la relazione parent.

Se si usa XSB è possibile comunicare le righe di codice attraverso il comando [user]. e digitare il codice a video seguito dalla combinazione Control-D oppure salvare tutte le righe in un file con un nome del tipo family.P e caricarlo con il comando [family].

Adesso possiamo interrogare prolog sui fatti definiti, se vogliamo appurare che tom è padre di liz bastera digitare e leggere la risposta.

-? parent(tom,liz).
Yes

Mentre se voglio sapere chi è il padre di un componente della famiglia potrò farlo in questo modo:

-? parent(X,ann).
X=tom

E’ anche possibile scoprire tutta la relazione parent chiedendo a prolog chi è padre di chi.

-? parent(X,Y):



X=pam
Y=bob;
X=tom
Y=bob;
X=tom
Y=liz;

E’ quindi possibile formulare query più complesse usando la congiunzione logica and eprimibile con una virgola tra le clausole in questione, ad esempio come chiedere chi è il nonno di jim.

-? parent(Y,jim),parent(Z,Y).

La risposta sarà.

Y = pat
Z = bob;


In questa prima lezione abbiamo visto che un programma prolog viene costituite da clausole seguite da un punto, gli argomenti delle relazioni possono essere atomi (come tom o pat) oppure variabili(come X o Y).
Le query al sistema vengono poste atrverso uno o più goal da soddifare tipo

-? parent(Y,jim),parent(Z,Y).

Una query può avere risposta positiva(Yes) o negativa(No), in quest ultimo caso si dice che i goals sono insoddisfacibile e la query fallisce mentre nel primo caso prolog propone all’utente le risposte che soddisfano i goals della query.