Uno sguardo al Prolog

La volta  scorsa abbiamo presentato in breve il Prolog, probabilmente il più usato tra i linguaggi di programmazione logica, nonché uno dei due linguaggi classici nel campo dell’intelligenza artificiale, assieme al LISP. Oggi proseguiremo il discorso, con una rapida descrizione delle sue caratteristiche principali e della sua particolare sintassi.

Per prima cosa, il Prolog è un linguaggio semplice. Più o meno. A livello sintattico, è molto più semplice di qualsiasi linguaggio procedurale, come C (e varianti), Smalltalk, Java, eccetera. Non ci sono molte regole, non ci sono innumerevoli tipi di variabili da ricordare e utilizzare, non ci sono differenti strutture di controllo del flusso: in fin dei conti, la filosofia del Prolog si basa proprio sull’idea che dovrebbe essere il computer a occuparsi di questi dettagli, mentre il programmatore dovrebbe pensare soltanto al cosa fare, non al come farlo. Questa è l’essenza di un linguaggio descrittivo. La realtà del Prolog è un poco diversa, come vedremo, ma è pur sempre un bel passo in questa direzione.

Come abbiamo già detto, un programma in Prolog è composto da due elementi: fatti e regole.

Un fatto afferma alcune proprietà di un oggetto, o relazioni tra due o più oggetti: è sempre vero. Un tipico fatto si presenta così:

maschio(tizio). traducibile come -> Tizio è maschio.

padre_di(tizio, caio). traducibile come -> Tizio è padre di Caio.

Una regola ci permette di dedurre nuove proprietà di un oggetto, analizzando le precondizioni che la compongono. Una regola infatti è composta da una testa, che costituisce il predicato da provare, e un corpo, che costituisce i predicati da dimostrare, per affermare la verità della testa. Testa e corpo sono separati da un :- , simbolo che corrisponde allo "if" di altri linguaggi. Se il corpo è composto da più predicati, i predicati possono essere separati da una virgola, se tutti devono essere verificati (la virgola corrisponde a una "e", oppure allo "and" di altri linguaggi). Se due predicati sono separati da un punto e virgola, invece , significa che sono alternativi: basta che soltanto uno dei due sia vero (corrisponde allo "or" di altri linguaggi). Per esempio:

zio_di(X, Y) :- padre_di(Z, Y), fratello(X, Z).

che, tradotto, significa "X è zio di Y, se ( :- ) esiste una persona Z che sia padre di Y e ( , ) fratello di X".

In concreto, i fatti si possono considerare come un caso speciale di regole, cioè regole che sono sempre vere: per questo  non presentano alcuna precondizione da soddisfare.

Per motivi misteriosi, praticamente tutti i manuali di Prolog cominciano con esempi tratti dalla vita familiare, così ho scelto di rispettare la tradizione anche qui. A ogni modo, già da questi esempi, possiamo osservare alcuni aspetti tipici del Prolog. Tanto per cominciare, fatti e regole sono composti da strutture pressoché uguali: una parola (o due parole, collegate da una barra orizzontale), seguita da una parentesi tonda, che contiene a propria volta una o più parole, separate da una virgola. Questa struttura è chiamata "definizione di predicato". Il predicato è la parola che precede la parentesi e specifica il tipo di proprietà posseduta dai termini fra parentesi. I termini fra parentesi, invece, sono gli argomenti del predicato. Gli argomenti possono essere costanti, variabili o termini composti.

Le costanti possono essere: 

numeri, sia interi che decimali;

simboli, cioè parole o sequenze di caratteri che cominciano per lettera minuscola, oppure singole lettere minuscole;

stringhe, ossia qualsiasi cosa sia racchiusa tra ‘ e ‘.

Le variabili, invece, possono essere parole, singole lettere o sequenze di caratteri, proprio come i simboli che abbiamo visto sopra: l’importante è che comincino con una lettera maiuscola o con una linea _ . Dunque,

costanti: a, 42, ciao, cu78abct7, roma;

variabili: A, Nonno, Caio, _rtuny.

Se vedete qualcosa che comincia con una lettera maiuscola, o con un _, sarà di sicuro una variabile, qualsiasi sia il suo significato (ammesso che ne abbia uno). Le variabili sono sempre locali, ossia hanno valore solo all'interno della regola in cui si trovano. Due variabile dallo stesso nome, poste in due regole diverse, avranno anche un valore diverso.

Un tipo particolare di variabile è la variabile anonima, che si indica con un semplice trattino basso, _. Questo simbolo sta a significare che in quel punto c’è una variabile, ma non ci interessa quale sia e non intendiamo usarla.

Un programma in Prolog, come detto, consiste in un database di fatti e regole, di questo tipo:

maschio(tizio).

maschio(caio).

maschio(pippo).

femmina(gina).

femmina(beppa).

genitore(tizio, caio).

genitore(tizio, gina).

genitore(beppa, caio).

genitore(beppa, gina).

genitore(pippo, tizio).

madre(X) :- femmina(X), genitore(X, Y).

padre(X) :- maschio(X), genitore(X,Y).

nonno(X, Y) :- genitore(X,Z), genitore(Z,Y).

Una volta creato un database di questo tipo, salviamo il file di testo con un nome qualsiasi che abbia estensione .pl (l’estensione classica del Prolog) e lo consultiamo all’interno di un ambiente Prolog. L’uso di un programma in Prolog, normalmente, si svolge attraverso domande, che noi poniamo al programma e a cui il programma ci risponderà, in base alle informazioni che possiede.

Una domanda si presenta come un fatto: noi scriviamo questa domanda e il programma ci risponderà se è vera o falsa, in base alle informazioni che possiede. Per esempio:

?- maschio(caio).

In questo caso, il Prolog consulterà il database e risponderà "yes" (oppure "true", a seconda della versione che state utilizzando). Se invece chiediamo

?- maschio(X).

usando cioè una variabile come argomento, il Prolog esaminerà il database alla ricerca di un termine che possa essere unificato alla variabile e ci risponderà col primo termine che incontra. Siccome una qualsiasi ricerca del Prolog parte dalla prima riga del database e procede a oltranza fino alla fine, la risposta che avremo sarà

X = tizio.

perché maschio(tizio) è il primo fatto che il Prolog incontra. Se non siamo contenti di questa risposta, possiamo chiederne un’altra premendo il punto e virgola (;) subito dopo aver ricevuto la prima risposta: in questo modo, il Prolog ripartirà con la ricerca dal punto a cui è arrivato e ci proporrà la successiva risposta, se ce n’è una. Nel nostro caso, sarà

X = caio.

Se non ci sono altre possibilità, risponderà che non è possibile trovarne altre e fallirà.

Se invece chiediamo al Prolog di rispondere a una regola, per esempio

?- madre(X).

il Prolog cercherà prima un predicato che corrisponda a quello chiesto da noi (cioè "madre"), poi procederà cercando di soddisfare tutti i requisiti di quella regola, in ordine da sinistra a destra. Cercherà prima una X che sia femmina, e troverà come prima risposta "gina", dopodiché procederà con la ricerca di un fatto "genitore" il cui primo argomento sia "gina". E fallirà, perché non esiste.

A questo punto, tornerà a soddisfare il primo requisito, ossia femmina(X), e userà il secondo fatto che ha trovato, ossia femmina(beppa). La X assumerà adesso il valore "beppa" e il compito sarà di trovare un predicato "genitore" che abbia "beppa" come suo primo argomento. E lo troverà, perché il primo sarà proprio genitore(beppa, caio). La ricerca è così riuscita e la risposta sarà

X = beppa.

Se gli chiediamo un'altra soluzione, procederà con l'esame del fatto successivo, ossia "genitore(beppa, gina)" e ci risponderà di nuovo

X = beppa.

Un tentativo successivo fallirà, perché non esistono più alternative che soddisfino la richiesta.

Come si può intuire già da qui, l'ordine in cui presentiamo fatti e regole è di vitale importanza: il Prolog tenterà sempre il primo fatto e la prima regola che incontra, muovendosi dall'altro verso il basso e da sinistra verso destra: solo in caso di fallimenti prenderà in considerazione le eventuali alternative. In questo senso, il Prolog è ancora legato alle meccaniche dei linguaggi procedurali e non sa essere pienamente dichiarativo.

Per quanto possa apparire strano, il nocciolo della sintassi del Prolog è qui. Esistono poi svariate funzioni già esistenti nel linguaggio, strategie per controllare le ricerche all’interno del database, ed esistono le liste, per raccogliere assieme più dati, ma tutto si può ridurre a modi di ricombinare assieme gli elementi di base, che sono predicati, costanti e variabili. Rispetto alla maggioranza degli altri linguaggi di programmazione, la sintassi del Prolog è estremamente semplice; più complicato, semmai, sarà utilizzarla in modo efficiente, soprattutto quando entra in gioco la ricorsione.