2.34       PROLOG

Il Prolog  (PROgramming in LOGic) è stato sviluppato all’Università di Marsiglia da Alain Colmerauer all’inizio degli anni 1970, come uno strumento di programmazione basato sulla logica, più precisamente su un sottoinsieme del calcolo dei predicati. Prolog è un linguaggio dichiarativo, in esso non vi è una sequenza di azioni, ma una raccolta di predicati (o fatti) con delle regole: in terminologia logica i predicati sono proposizioni, proposizioni con variabili ed enunciati [1] (con valore di verità "vero") e le regole sono implicazioni; ad esempio:

Φ = " piove" , "piove > strada bagnata"
β = "strada bagnata" 

piove.
bagnato:-piove.

L'esecuzione del programma è una richiesta a Prolog  di dedurre dei fatti dall'insieme di informazioni che Prolog conosce, cioè l'insieme di predicati e di regole comunicate al programma; nell'esempio precedente vi è un predicato "piove" ed una regola "è bagnato se piove"; una possibile richiesta è:

goal bagnato.

yes

Mentre nel calcolo preposizionale si può dedurre unicamente il valore di verità di una proposizione, come nell'esempio visto, Prolog , invece, è in grado di dedurre, se la domanda è un predicato contenente variabili, i valori che soddisfano il predicato. Il cuore di Prolog è un motore di inferenza, cioè un (sotto)programma per ragionare logicamente sulle informazione. Prolog cerca di inferire che un'ipotesi è vera (la domanda che è stata posta), interrogando la collezione di informazione già note per essere vere. La risposta comprende tutte le soluzioni possibili.

2.34.1          Fatti e Regole

I predicati possono esprimere sia proprietà degli oggetti che relazioni; in linguaggio naturale proprietà sono "l'erba è verde" e "Maria è una ragazza.", mentre sono relazioni, ad esempio: "a Mario piace guidare", "Parigi è la capitale della Francia".

L'assunzione basilare è che i predicati sono ciò che è conosciuto, implicitamente ciò che è conosciuto è vero.

Nella sintassi di Prolog  un predicato si scrive con un nome di predicato seguito fra parentesi dall'oggetto o dagli oggetti su cui agisce; il tutto chiuso con un punto:

tipo(ferrari,sportiva).
tipo(maserati,sportiva).
tipo(fiat,famigliare).
tipo(renault,utilitaria).
piace(marco,auto).
piace(elena,auto).
piace(anna,bici).

Le regole sono predicati in cui un fatto è "vero" se uno o più altri fatti sono veri. La regola che definisce quando "piace guidare a Mario" potrebbe essere la seguente: "a Mario piace guidare se l'automobile è sportiva". Quindi le regole sono formate da due parti, la prima (testa) è un predicato che è reso vero dalla seconda (corpo), separata dalla prima tramite i simboli ":-" (due punti meno col significato di se), è:

piace(anna,auto):-tipo(Automobile,famigliare);tipo(Automobile,utilitaria).
piace(mario,auto):-tipo(Automobile,sportiva),Automobile <> "ferrari".

La prima regola afferma che ad anna piace l'auto se e' famigliare o utilitaria, l'alternativa è indicata in Prolog  col segno ";". Per la seconda regola, a mario piacciono le auto sportive purchè non siano ferrari; purchè in questo caso è tradotto con l'operatore logico e, che in Prolg è indicato con il segno ",". Non è per poco rispetto verso Anna, Mario che in Prolog compaiono in minuscolo: in minuscolo si indicano i fatti conosciuti, mentre le variabili hanno un nome che inizia con una lettera maiuscola, come la variabile Automobile che compare nelle regole.

Le regole permettono la deduzione di fatti da altri fatti, ma esse possono essere pensate come procedure. per chiedere a Prolog  di compiere azioni diverse dal provare dei fatti, quali la scrittura di qualcosa o la creazione di un archivio, e in genere, ciò che un linguaggio di programmazione può fare.

2.34.2          Domande

Una volta fornito a Prolog  un insieme di predicati, gli si possono porre domande che riguardano tali predicati; dall'esempio del paragrafo precedente, alcune domande potrebbero essere:

Figura 1‑1

Prolog  per rispondere ad una domanda esamina i predicati che conosce: il caso più semplice è quello in cui la domanda non contiene variabili, come in piace(mario,auto), in questo caso Prolog cerca se esiste il predicato piace(mario,auto) o una regola la cui testa sia il predicato. Se non trova nulla la risposta è no, altrimenti, se esiste il predicato la risposta è yes, se esiste la regola e la coda di essa risulta vera, la risposta è yes, altrimenti è no.

Se la domanda contiene variabili, Prolog  sostituisce alle variabili, via via il valore che ricava dai fatti, la risposta invece di essere yes o no è l'elencazione degli attributi che soddisfano le variabili oppure: No Solution. Alla domanda piace(anna,Cosa), Prolog ha risposto due volte Cosa=auto, ciò deriva dalla caratteristica di Prolog di cercare tutte le soluzioni, infatti la regola:

piace(anna,auto):-tipo(Automobile,famigliare);tipo(Automobile,utilitaria).

é soddisfatta due volte, in quanto fra i fatti ci sono una automobile famigliare ed una automobile utilitaria.

Il segno "_"  indica una variabile anonima per rispondere a domande generiche.

Per rispondere Prolog  esamina tutti i fatti, tranne quando la domanda è senza variabili, per cui all primo predicato verificato è in grado di rispondere yes, e quindi può interrompere la ricerca.

In Prolog  le variabili sono gestite dal motore di inferenza, esse nascono libere (free), e nel corso dell'elaborazione Prolog assegna loro dei valori che ricava dai fatti (bound), per stabilre se soddisfano la richiesta, finita l'elaborazione esse ridiventano libere. In un predicato possono coesistere variabili bound o di input e variabili free o di output. La cosa che più si avvicina al concetto di variabile dei linguaggi tradizionali, è il fatto, ed i fatti si possono aggiungere alla collezione di fatti e regole tramito un apposito predicato (assert).

Un predicato può produrre diverse soluzioni, in funzione dello stato delle variabili con cui è richiamato: ad esempio il predicato str_int(Intero,Stringa) potrà convertire un numero in una stringa, convertire una stringa numerica in numero o verificare che il numero e la stringa numerica convertita in numero siano uguali, secondo la tabella seguente:

In generale se tutte le variabili sono bound, il predicato è vero o falso, altrimenti risponde con il valore od i valori che lo rendono vero.

2.34.3          PROLOG come linguaggio procedurale

La caratteristica di Prolog  di cercare regole o fatti che soddisfino la domanda, è la base del suo utilizzo procedurale, in particolare se la domanda è relativa ad una regola plurima, cioè stessa testa e corpi diversi, Prolog verificherà la prima regola (quindi l'ordine delle regole è talvolta essenziale) se essa non è verificata, procederà con la regola successiva, ad esempio:

ciclo(10):-!.                                /*   variabile = 10 termina      */
ciclo(Counter):-NewCounter=Counter + 1,      /*  aggiorno contatore di ciclo  */
                random(Rnd),                 /* genero un numero a caso       */
                write(NewCounter,"\t",Rnd),nl,  
                ciclo(NewCounter).           /* riciclo                       */

find:-write("Inizio della generazione di numeri casuali\n"),fail.
find:-ciclo(0),fail.
find:-write("Fine della generazione di numeri casuali\n"),exit.

goal find.

La domanda è find, Prolog  verifica la prima regola find, in questa il predicato write produce una scritta sul video e risulta non verificato, a causa del predicato fail. Il predicato fail ha lo scopo forzare Prolog a proseguire e verifica quindi la seconda regola find e poi finalmente la terza.

La seconda find verifica il predicato ciclo che genera 10 numeri casuali, infatti la prima regola ciclo termina il ciclo, la seconda genera un numero a caso, tramite il predicato random, incrementa il contatore del ciclo, scrive il numero casuale ed infine ripete il ciclo.

La regola ciclo(10):-!. termina il ciclo  tramite il predicato ! (cut), il cui scopo è di terminare la verifica della regola. Il predicato ! è utilizzato per lo scopo appena visto e quando interessa conoscere se c'è una soluzione, evitando così la perdita di tempo per trovarle tutte.

Il predicato exit evita la visualizzazione della risposta di Prolog . Infine il predicato nl permette l'avanzamento di una riga (in alternativa ai caratteri "\n" nel predicato write).

2.34.4          PROLOG e la conoscenza implicita

Nelle regole e nei fatti talvolta è presente della "conoscenza implicita":  essa è o nel significato del predicato, ad esempio dati i fatti prima(a,b) e prima(b,c), la conoscenza implicita è prima(a,c) perché prima è una relazione di ordine, o nelle relazioni fra fatti diversi, ad esempio da fatti e regole del paragrafo 1.3.23.1 si capisce che a Mario piacciono le  maserati, e a Elena piacciono tutte le automobili. Ma non c'è una regola o un fatto che dica qualcosa del genere: se a Tizio piacciono le Automobili,  la Marca dell'automobile preferita è …  Prolog  permette di generare dei fatti, tramite il predicato assert(...), quindi potrebbe generare il fatto marca_preferita(persona,marca), e poi elencarlo. 

Le regole relative ad Anna e Carlo fanno riferimento al tipo di auto, quindi se la regola è verificata, Prolog  ha trovato la Marca dell'automobile, si possono modificare le due precedenti regole, come segue:

piace(anna,auto):-  tipo(Automobile,famigliare),
                    assert(marca_preferita(anna,Automobile));                           
                    tipo(Automobile,utilitaria),
                    assert(marca_preferita(anna,Automobile)).
piace(carlo,auto):- tipo(Automobile,sportiva),Automobile <> "ferrari",
                    assert(marca_preferita(carlo,Automobile)).

Questo vale solamente per Anna e Carlo, per tutti gli altri occorre aggiungere (in coda) un'ulteriore regola:

piace(X,auto):-tipo(Auto,_),X <> "anna",X <> "carlo",
               assert(marca_preferita(X,Auto)).

Infine occorre scrivere le regole "procedurali" per eseguire il tutto, qualcosa di simile a ciò che segue:

elenco_marche(X):- piace(X,auto),fail.
elenco_marche(_):- marca_preferita(X,Y),
                   write(X," gradisce la ",Y),nl,fail.
elenco_marche(_):- write("--------------"),nl,exit.

goal elenco_marche(anna).

La risposta di Prolog  è:

anna gradisce la fiat
anna gradisce la renault
--------------

La prima regola elenco_marche genera tutte le preferenze (di Anna), e la seconda le stampa.

La potenza di Prolog  è nella capacità di estrarre la "conoscenza implicita" che è presente nei fatti, mediante opportuni predicati; questi in sostanza formalizzano le relazioni esistenti fra i fatti, ad esempio le relazioni d'ordine che il predicato prima (A è prima di B) sottende. L'esempio che segue vuole è un programma che verifica l'esistenza di cicli in un insieme di attività, di cui sono date le precedenze tramite il predicato prima(). I fatti sono:

prima(ideazione,pianificazione).
prima(pianificazione,pubblicità). 
prima(ideazione,"ricerca materiale").
prima("ricerca materiale",stesura).
prima(pubblicità,ideazione).      % introduce un ciclo
prima(pianificazione,stesura).
prima(stesura,correzione).
prima(correzione,stampa).
prima(pubblicità,distribuzione).
prima(stampa,distribuzione).

I predicati di ricerca dei cicli sono:

trovacicli(X):-attivita(X,Y,[]).
attivita(Prima,Dopo,ListaLavori):-prima(Prima,Dopo),
                                  not(member(Dopo,ListaLavori)),
                                  prima(Dopo,NextDopo),
                                  attivita(Dopo,NextDopo,[Dopo|ListaLavori]).
attivita(_,Dopo,ListaLavori):-member(Dopo,ListaLavori), 
                              write("Ciclo: "),nl,
                              writelist([Dopo|ListaLavori]),fail.
attivita(_,_,[]):-write("--- Fine ---"),nl,
                  exit.

Il secondo predicato attivita agisce dopo il primo, ed ha come oggetti le variabili Dopo e ListaLavori ereditate dal primo predicato attivita, in particolare se questo è fallito per il predicato not(member(Dopo,ListaLavori)), Dopo conterrà l'attività che provoca il ciclo, e ListaLavori l'elenco delle attività che compongono il ciclo, e queste verranno stampate.

Alla domanda:

GOAL trovacicli(ideazione).

Prolog risponde:

Ciclo:
pianificazione
ideazione
pubblicità
pianificazione
--- Fine ---

Alla domanda:

GOAL trovacicli(correzione).

Prolog, non trovand cicli dopo l'attività "correzione",  risponde:

--- Fine ---

In questo programma si è utilizzata una lista per elencare le attività. Le liste sono una struttura di dati che può essere usata ricorsivamente sfruttando la definizione:

Lista = [Testa o primo elemento della lista | Coda o resto della lista]

L' operatore | permette sia la costruire delle liste, che il loro trattamento, un esempio del primo caso è la clausola writelist([Dopo|ListaLavori]):  l'oggetto di writelist è la lista formata dall'elemento Dopo, seguita dalla lista ListaLavori. Sfortunatamente ci sono pochi predicati nativi per trattare le liste, è necessario scriverli, o utilizzare delle definizioni da inserire tramite il comando Prolog include, come è stato fatto nell'esempio precedente con i due predicati:

member(Testa, [Testa|_]).
member(Testa, [_|Coda]):-member(Testa,Coda).
writelist([]):-!.
writelist([Testa|Coda]):-write(Testa),nl,writelist(Coda).

Questi chiariscono come trattare ricorsivamente le liste, ad esempio il predicato member verifica la presenza di un elemento in una lista: se l'elemento è il primo, viene verificato il primo predicato member, altrimenti la ricerca prosegue, ricorsivamente,  sul resto della lista.