Prolog - Esercizi STEM

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: predicati
mary, pizza, antonio, john, icecream: costanti
Thing: 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 = tommaso Risultato: true
?- tommaso = X Risultato: 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')d Risultato: 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

Se hai trovato errori o informazioni mancanti scrivi a:
giacomo.dandria@esercizistem.com

Questa pagina è stata utile?

SìNo