Prolog e la programmazione logica

Il mio primo incontro con il Prolog e la programmazione logica risale ai primi anni '90 del secolo scorso, quando trovai un compilatore per il linguaggio Prolog installato sul pc assegnato a un tesista che avevo seguito in qualità di relatore esterno.
In quegli anni mi capitò diverse volte di essere relatore esterno di tesi di laurea presso l'Ateneo di Pisa. Il laureando di turno svolgeva il suo lavoro di ricerca presso i laboratori Olivetti di Ivrea, affidato a un interno (io, in questi casi), lavorando su un pc messo a disposizione dalla Olivetti stessa.
Si trattava in genere di pc utilizzati per test, che venivano appunto distratti per alcuni mesi. Una volta discussa la tesi, il laureando (ormai laureato) liberava il pc, rimuovendo file e programmi che aveva caricato sul pc.

Il Prolog, per fare cosa

Quel compilatore Prolog rimase invece installato e, complice l'avvicinarsi delle ferie con il conseguente calo del carico di lavoro, nelle settimane successive spesi diverse ore a giocare con la programmazione logica.
Del codice che mi divertii a mettere insieme, ricordo due programmi: un inventario dei libri che avevo in casa e un gestore di pianificazione operativa con i diagrammi di Gantt.

A quell'epoca sui pc girava Windows 3.1, mentre Excel era una chicca per pochi fortunati. Quindi sviluppare un programma che mi consentiva, interattivamente, di elencare i libri scritti da Tizio, o editi da Caio, o che nel titolo avessero un particolare termine, non era una cosa da poco.

Il programma di pianificazione operativa, invece, mi accompagnò sul lavoro per qualche mese, ma non si rivelò di particolare utilità, e così dopo un po' la programmazione logica finì in cantina (dove dev'esserci ancora qualche listato, che prima o poi riporterò alla luce).

Il Prolog oggi

A distanza di tanti anni ho ritrovato il Prolog tra gli ambienti di sviluppo offerti dalla piattaforma Tutorialspoint. Googlando un po', ho scoperto che è tuttora utilizzato nell'ambito per cui era nato, l'intelligenza artificiale.
Ho provato quindi a rispolverare i ricordi, anche se riprendere è quasi come tornare ai primi passi incerti.

Le basi del Prolog

Il Prolog non è un linguaggio imperativo, né funzionale , né a oggetti.
Nel primo caso, infatti, la macchina dovrebbe eseguire sequenze di istruzioni che intendono risolvere un particolare compito, ma non è così. Nel secondo caso, l'elaborazione dovrebbe basarsi sul richiamo di un insieme di funzioni, ma ancora una volta non è questo il caso. Infine l'esecuzione di un programma Prolog non si basa nemmeno sulla definizione di un insieme di oggetti software e sui messaggi che questi si scambiano.

Nel Prolog, invece, il programma lavora per sintesi di proposizioni logiche, e consiste di un insieme di fatti e regole, che si assume descrivano in modo compiuto l'ambito si cui si lavora. Il programma Prolog deve calcolare se una proposizione assegnata sia vera o meno, sulla base di fatti e regole disponibili.

Un esempio: figli e genitori

Ho una nipotina, Luna, gioia dei genitori Valentina e Giovanni. Al Prolog posso raccontare la cosa mediante due fatti:

genitore(luna, valentina).
genitore(luna,giovanni).

Ho implicitamente definito una relazione genitore(X,Y), in cui Y è genitore di X. Da notare il punto finale che chiude l'affermazione del fatto, e l'utilizzo della minuscola iniziale per le stringhe e della maiuscola inziale per le variabili.

Potrei ora avere l'obiettivo di elencare i genitori di luna. Se scrivessi:

genitori(luna) :- genitore(luna, X), write(X).

il programma troverebbe solo il primo genitore, valentina, e soddisfatto di aver concluso positivamente il suo obiettivo, si arresterebbe. Da notare qui il simbolo ":-" e il connettivo ",". La frase si legge:

genitore di luna è vero se un genitore di luna è X e stampo X.

Come fare per ottenere la stampa del nome di tutti e due i genitori? Basta far fallire questa concatenazione, costringendo il programma a cercare un ulteriore genitore. Il programma si complica un po':

:- initialization(main).
genitore(luna, valentina).
genitore(luna,giovanni).
scrivi(X) :- X \== "", write(X), nl.
scrivi(_).
genitori(X) :- genitore(X,Y), scrivi(Y), fail.
genitori(_).
main :- genitori(luna).

Ho strutturato il programma in:

• la riga introduttiva, che definisce qual'è l'obiettivo del programma (main);
• un obiettivo principale (stampa il nome dei genitori di luna);
• un predicato scrivi, che stampa il valore che gli viene passato, se è una stringa non vuota, e subito dopo fallisce, mentre ha successo se il valore passato è una stringa vuota;
• un predicato genitori, che fallisce tutte le volte che trova un genitore (e ne stampa il nome), mentre ha successo quando ha esaurito la sua ricerca.

Da notare inoltre:

• nl (new line), per andare a capo;
• fail, per forzare il fallimento di un predicato;
• scrivi(_). e genitori(_)., che forzano il successo del predicato.

Il fallimento di un predicato causa il backtracking del programma, cioè la ricerca all'indietro di altre soluzioni possibili.

Evviva, il programma risponde correttamente:

valentina
giovanni

Un albero genealogico più ricco

Si può arricchire la base dei fatti disponibili e aggiungere una regola che definisca cos'è un nonno e cos'è un bisnonno:

:- initialization(main).

  genitore(luna,valentina).
  genitore(luna,giovanni).
  genitore(valentina,orsella).
  genitore(valentina,pasquale).
  genitore(giovanni,teresa).
  genitore(giovanni,mauro).
  genitore(orsella,sisina).
  genitore(orsella,ciccio).

  genitori(X) :- genitore(X,Y), scrivi(Y), fail.
  genitori(_).
  nonni(X) :- genitore(X,Y), genitore(Y, Z), scrivi(Z), fail.
  nonni(_).
  bisnonni(X) :- genitore(X,Y), genitore(Y, Z), genitore(Z,W), scrivi(W), fail.
  bisnonni(_).
  
  scrivi(X) :- X \== "", write(X), nl, fail.
  scrivi(_).
  
  main :- write('I genitori di Luna sono:'), nl, genitori(luna), nl, 
        write('I nonni di Luna sono:'), nl, nonni(luna), nl, 
        write('I bisnonni di Luna sono:'), nl, bisnonni(luna).

La lettura delle nuove regole è abbastanza semplice:

• se X ha come genitore Y e Y ha come genitore Z, allora X ha come nonno Z;
• se X ha come genitore Y, Y ha come genitore Z e Z ha come genitore W,  allora X ha come bisnonno W.

Il programma, correttamente, elenca quanto richiesto:

I genitori di Luna sono:
valentina
giovanni

I nonni di Luna sono:
orsella
pasquale
teresa
mauro

I bisnonni di Luna sono:
sisina
ciccio

E figli e fratelli?

Si potrebbe arricchire ancora la base dati, aggiungendo qualche regola:

figlio(X,Y) :- genitore(Y,X).
cioè: X ha come figlia/o Y se Y ha come genitore X;

fratello(X,Y) :- genitore(X,Z), genitore(Y,Z).
cioè: X e Y sono fratelli (o sorelle) se hanno un genitore in comune.

ma direi che con le esplorazioni familiari mi fermo un passo prima.
Però, adesso che ho la soluzione (il Prolog), devo trovare un problema.

Foto di apertura di Monika Grafik da Pixabay.