Home » Intelligenza Artificiale » 📋 URL
Il Prolog è un linguaggio di programmazione logica utilizzato per la rappresentazione della conoscenza. Il nome “Prolog” deriva da “PROgramming in LOGic“.
A differenza di molti altri linguaggi di programmazione, il Prolog si basa su un paradigma dichiarativo e un sistema d’inferenza che sfrutta la logica del primo ordine e l’unificazione per dedurre le risposte alle interrogazioni.
In Prolog, i programmi sono composti da:
- Fatti (facts): definiscono gli oggetti e le relazioni tra essi
- Regole (rules): definiscono il modo in cui i diversi oggetti sono in relazione
- Obiettivi (goals): definiscono ciò che si vuole ottenere
Nota bene: in Prolog, ogni programma è composto da sole clausole di Horn.
Esempi:
\text{Facts:}\\
\texttt{work(emp1, deepmind)}.\\
\texttt{work(emp2, deepmind)}.\\
\texttt{work(emp3, ibm)}.\\
\texttt{work(emp4, ibm)}.\\
\\[10pt]
\text{Goal:}\\
\texttt{colleague(X, Y)}.\\
\\[10pt]
\text{Rule:}\\
\texttt{colleague(X, Y)}\,\text{:-}\,\,\texttt{work(X, Z), work(Y, Z)}.Nota bene: ogni riga deve finire con il punto.
Per interrogare la knowledge base (ovvero il nostro programma) usiamo l’operatore \text{?-}
\text{?-}\,\,\texttt{colleague(emp1, emp2)}.\\
\text{oppure}\\
\text{?-}\,\,\texttt{colleague(emp1, emp3)}.dove stiamo controllando se i diversi impiegati sono colleghi di lavoro, avendo prima definito il significato di \texttt{colleague(X, Y)}.
In Prolog si possono inoltre utilizzare le seguenti operazioni
\begin{matrix}
&\text{Prolog}&\text{Logica}\\[5pt]
\text{Implicazione}&\text{A :- B}&\text{B$\Rightarrow$A}\\[10pt]
\text{Congiunzione}&\text{A,B}&\text{A$\wedge$B}\\[10pt]
\text{Disgiunzione}&\text{A;B}&\text{A$\vee$B}
\end{matrix}La terminologia
Facendo riferimento al seguente codice Prolog
Chiamiamo le diverse parti del codice nel seguente modo:
likes,food: predicatimary,pizza,antonio,john,icecream: costantiThing: variabile
Ci sono inoltre
Distinguiamo i diversi termini semplici:
- Atoms:
pippo,pluto,topolino… - Numbers: 12, -34, 345.01, 3.1415
- Variables: iniziano con la lettera maiuscola o con l’underscore, ad esempio
X,Y,Who,_variabile…
Nota bene: l’utilizzo dell’underscore _ viene usato per indicare tale variabile come don’t-care, quando non è importante il valore che tale variabile assume.
La tecnica del backtracking
Un aspetto del Prolog è la sua capacità di esplorare tutte le possibili soluzioni tramite il meccanismo del backtracking. Se una query ha più soluzioni possibili, il sistema Prolog può restituire tutte le soluzioni rilevanti controllando in maniera iterativa tutte le possibili coppie che potrebbero risolvere la query posta.
Questa tecnica equivale ad effettuare una ricerca depth first nell’insieme delle soluzioni.
Le variabili
Consideriamo il seguente codice
Interrogando la knowledge base
\text{?-}\,\,\texttt{grampa(tommaso, Who)}Il Prolog riconoscerà il termine Who come una variabile e, tramite la tecnica del backtracking andrà a cercare tutti i possibili valori per Who che sono collegati con tommaso.
Il comando cut (!)
Quando il linguaggio Prolog incontra l’operatore ! (cut), viene effettuata un’esclusione di tutte le possibili alternative per quel punto nel programma. Questo significa che, una volta raggiunto il punto di taglio, il Prolog non proverà più a cercare altre soluzioni per quel particolare frammento di codice.
Esempio: ipotizziamo di avere il seguente codice in Prolog
Il comando
\texttt{teaches(dr\textunderscore fred, Course), !, studies(Student, Course).}Restituirà i valori
\text{Course = history,\quad
Student = alice}Infatti l’esecuzione partirà da teaches(dr_fred, history) e si andrà a cercare se ci sono studenti che hanno lo stesso corso di dr_fred, ovvero history. Appena viene trovata alice l’istruzione ! fa terminare la query.
Se invece di avere la knowledge base appena usata si avesse la seguente
Lo stesso comando restituirebbe semplicemente il valore \text{False}, infatti, al causa del cut, non si sarebbe andati a cercare oltre la prima condizione non soddisfatta nella knowledge base (seguendo l’ordine di scrittura delle righe di codice).
Dopo la prima condizione non soddisfatta il programma infatti non cerca ulteriori match.
Nota bene: il cut in questo caso è stato inserito tra le due condizioni, quindi l’ordine di lettura delle istruzioni sarà il seguente
\texttt{(1) teaches(dr\textunderscore fred, Course), (2) !,(3) studies(Student, Course).}Poiché la condizione \texttt{(2)} viene controllata prima della \texttt{(3)}, la riga di codice termina dopo la prima condizione non soddisfatta.
Se l’ordine di esecuzione fosse invece stato il seguente
\texttt{(1) teaches(dr\textunderscore fred, Course), (2) studies(Student, Course), (3) !.}Nelle prime due condizioni si sarebbe utilizzata la tecnica del backtracking per ottenere un match, dopodiché si sarebbe proceduti all’istruzione successiva (\texttt{!}) che avrebbe fatto terminare la query. Il risultato ottenuto in questo caso sarebbe
\tag{$\spades$}\text{Course = english,\quad Student = alice}Infatti, dapprima vengono state testate tutte le coppie \texttt{(studente, history)}, per poi passare alla condizione successiva dettata da \texttt{(dr\textunderscore fred, course)}, ovvero \texttt{(dr\textunderscore fred, english)}, che viene soddisfatta proprio da (\spades).
L’operazione di unificazione
In Prolog, l’operatore = indica l’operazione di unificazione, ovvero il meccanismo che permette di effettuare una sostituzione per uguagliare due espressioni.
Per esempio, interrogando il motore del Prolog con le seguenti righe di codice, si ottengono le risposte riportate come risultato:
?- tommaso = tommasoRisultato: true?- tommaso = XRisultato: X=tommaso
gampa(X, Y) = grampa(bianca, Z)(in riferimento al codice sopra) Risultato: X=bianca, Y=Z
La ricorsione
In Prolog, grazie al backtracking, si può facilmente programmare degli algoritmi ricorsivi. Per esempio, per il calcolo del fattoriale è sufficiente scrivere
Che possiamo interrogare nel seguente modo
\texttt{?- factorial(6, Result)}Per trovare il fattoriale di 6, ovvero 720.
Le liste
Una lista è una sequenza finita di elementi, per esempio
Sulle liste possiamo usare gli operatori
- Lenght, per esempio
?- lenght([a, b, c], 3)Risultato: true?- lenght([], 0)Risultato: true?- lenght([’pippo’, [a, b], 3])Risultato: false
- Append, per esempio
append([a, b], [1, 2, 3], X)Risultato: X=[a, b, 1, 2, 3]append(X, [1, 2, 3], [a, b, 1, 2, 3])Risultato: X=[a, b] false
Esiste inoltre l’operatore | che può essere utilizzato per decomporre una lista, ad esempio:
?- [Head, Tail] = [antonio, [2, [a, b]], f(X), []].- Risultato: Head=antonio, Tail=[2, [a, b]], f(X), []]
?- [One, Two, Remaining] = [antonio, [2, [b, c]], f(X), []].- Risultato: One=antonio, Remaining=[f(X), []], Two: [2, [b, c]]
L’operatore fail
Nelle istruzioni in Prolog si può utilizzare anche l’operatore fail, che fa fallire automaticamente tutte le condizioni successive ad essa. Tale operazione, seppur possa sembrare inutile, è in realtà utilizzata in Prolog grazie alla presenza del backtracking. Quando una condizione fallisce il Prolog inizia infatti a controllare le altre possibilità che possono soddisfare la query richiesta.
Un esempio di utilizzo del comando fail è riportato nel seguente codice, per indicare delle caratteristiche dei predicati penguin e ostrich:
Vari comandi Prolog (senza un particolare ordine)
?-var(X).Risultato: true?-X=5, var(X).Risultato: false?-X=Y, var(X), var(Y).Risultato: X=Y?-nonvar(X).Risultato: false?-X=5, nonvar(X).Risultato: X=5?-X=Y, nonvar(X), nonvar(Y).Risultato: false?-integer(5).Risultato: true?-integer(5.0).Risultato: false?-X=10, integer(X).Risultato: X=10?-number(5).Risultato: true?-number(5.0).Risultato: true?-number(atom):Risultato: false?-X=10, number(X).Risultato: X=10?-X=abc, number(X).Risultato: false?-atom('hello').Risultato: true?-atom(hello).Risultato: true?-atom('hello world')dRisultato: true?-atom('123').Risultato: true?-atom(123).Risultato: false?-X=abc, atom(X).Risultato: X=abc?-X=123, atom(X).Risultato: false?-atomic(5).Risultato: true?-atomic(5.0).Risultato: true?-atomic(hello).Risultato: true?-X=10, atomic(X).Risultato: X=10?-X=abc, atomic(X).Risultato: X=abc