Implementazione dell'interprete Prolog
Introduzione - Analisi lessicale - Analisi sintattica - Valutazione - Estensione - Demo

Valutazione in Prolog

    Si è già accennato al fatto che la valutazione Prolog avviene sulla base della cosiddetta interpretazione procedurale. In base ad essa ogni termine viene eseguito come se fosse una procedura. I suoi argomenti costituiscono i parametri attuali della chiamata e l'unificazione rappresenta il meccanismo di passaggio dei parametri (legame tra i parametri formali ed i parametri attuali), i quali possono essere sia di ingresso che di uscita.
    La realizzazione dell'interprete ha richiesto l'implementazione di:

    Vediamo di analizzare i vari elementi citati in modo più dettagliato.

    L'EngineSexpVisitor realizza il motore d'inferenza Prolog. Questo ha il compito di dirigere la computazione tenendo traccia delle clausole dimostrate e di quelle da dimostrare. Inoltre deve salvare i vari punti di scelta che via via si accumulano durante l'esplorazione dell'albero di ricerca SLD. L'esplorazione avviene con strategia di ricerca depth-first (nell'insieme delle clausole ordinate in base all'ordine di definizione e cioè testualmente) e regola di computazione left-most con backtracking cronologico. Il compito più significativo è la gestione dei record di attivazione e dei punti di scelta. I record di attivazione sono quelli delle chiamate a procedura corrispondenti alla valutazione di ciascun termine (interpretazione procedurale). La gestione dei record di attivazione può avvenire con uno stack. Anche per i punti di scelta è opportuno usare uno stack per poter gestire adeguatamente il meccanismo di backtracking. Allora una possibile soluzione è quella di usare due stack. Un'altra soluzione prevede invece l'utilizzo di un solo stack (stack di esecuzione) contenente sia i record di attivazione che i punti di scelta. In questo caso sono necessari due puntatori allo stack:

    La soluzione adottata nel nostro caso sfrutta la base Java, in particolare lo stack di Java stesso. E' necessario comunque uno stack per gestire i termini and. Vediamo con un esempio quello che succede. Supponiamo di voler eseguire la query ?-p. nel caso in cui il DataBase sia costituito dalle seguenti clausole:
    p :- r.
    p :- q.
    q :- s.
    s.
Dal punto di vista del Visitor la query ?-p. deve restituire come risultato quello che si ottiene invocando la accept() dell'oggetto costruito con quella query. Il termine Prolog p è un oggetto TermSexp nel nostro interprete. Quindi il risultato della valutazione della query è il risultato della visit() del TermSexp dato da p. Quella visit() allora accede al DB e trova due possibili clausole, una con body r ed una con body q. Allora si chiama la accept() del TermSexp corrispondente al primo punto di scelta, ovvero quello corrispondente ad r. Questa chiamata provoca la creazione sullo stack Java da parte dell'interprete Java di un nuovo record di attivazione per la accept(). Dunque non è necessario fare la stessa cosa all'interno del Visitor. Infatti quella accept porterà ad un fallimento che nel Visitor corrisponderà ad una return che riporterà il controllo alla visit() della TermSexp corrispondente a p e quindi di fatto il controllo torna alla procedura che valuta p. La visit() avendo di nuovo il controllo capisce che la prima alternativa ha fallito (vi sarà un flag indicante l'esito della valutazione) e quindi deve provare la seconda, ovvero si valuta il secondo punto di scelta chiamando la accept() di q. Questo punto di scelta porta ad un certo punto alla valutazione di s, che avverrà con la solita visit() di un TermSexp. Questa visit() come detto in precedenza deve accedere al DB Prolog per determinare quali sono la clausole che hanno per testa il termine da dimostrare. Questa volta di tali clausole ve n'è una sola ed è un fatto. Allora la visit() segnala direttamente sull'output che la dimostrazione ha avuto successo. Se vengono chieste soluzioni alternative (comando ; o anche more) allora questa visit() deve terminare con insuccesso così che si possano valutare i punti di scelta rimasti (se ve ne sono) ripetendo il procedimento già illustrato. Se invece non vengono chieste ulteriori soluzioni allora la visit() setta un flag con cui indica di aver terminato con successo ed effettua una return. Tutti le procedure corrispondenti ai record di attivazione presenti sullo stack vengono riattivate una alla volta e ciascuna effettua una semplice return dopo aver verificato che si è già ottenuta la soluzione. Tutti i punti di scelta vengono scartati automaticamente alla rimozione dei vari record dallo stack Java.
    Il tutto funziona correttamente in assenza di termini and. Un termine and viene valutato dal metodo visit() dedicato agli oggetti della classe AndSexp. Questo metodo deve valutare gli argomenti dell'and, ovvero deve valutare il primo argomento e se questo ha successo allora deve valutare il secondo. Non si può seguire il metodo sopra citato perché se il primo argomento è per esempio un termine la sua valutazione avviene invocando la accept() di un oggetto TermSexp e quindi in definitiva invocando la visit() dei TermSexp. Questa funzione in caso di successo non deve segnalare il proprio risultato direttamente in output, perché devono ancora essere valutati i termini in and con esso. Quindi quello che facciamo nella visit() degli AndSexp è di salvare su un apposito stack (andStack) il secondo argomento dell'and prima di chiamare la accept() sul primo. Quindi in ciascuna visit() se si ha successo si deve controllare se quello stack è vuoto, poiché se non lo è si deve terminare con successo, ma non si deve visualizzare in output alcun messaggio finale. A tal proposito è stata definito un apposito metodo (Stampa(boolean)) che viene chiamato dalle varie visit() al termine della loro computazione: tale metodo ha il compito di controllare quello stack e stabilire se la computazione è terminata o no. Se lo stack non è vuoto allora si effettua una pop e si chiama la accept() dell'oggetto restituito.
    L'altro punto delicato è il comando cut (!). Il cut è un comando che interviene sulla strategia di esplorazione dell'interprete Prolog in quanto porta alla potatura di alcuni rami dell'albero di risoluzione (albero SLD). In pratica l'esecuzione di un cut (che termina sempre con successo) produce l'eliminazione di alcuni punti di scelta. Nella nostra soluzione tale eliminazione non può avvenire durante l'esecuzione del comando stesso. Infatti i punti di scelta sono mantenuti nel codice e nei dati di procedure delle quali il record di attivazione è quello dell'interprete Java e quindi ad esso non è possibile accedere direttamente. Quindi quello che facciamo è di tener traccia del fatto che si è presentato un cut in modo che ciascuna procedura una volta riattivata possa controllare se i punti di scelta che contiene sono da scartare o no.
    Bisogna però osservare che l'aver sfruttato lo stack Java ha come conseguenza l'impossibilità di gestire direttamente i record di attivazione con la conseguenza che non è possibile per esempio implementare la tail recursion.

    Il database di clausole è costruito sfruttando una Hashtable in cui sono memorizzati tutti i funtori. Per ogni funtore abbiamo varie liste (ClauseVector) ognuna contenente le clausole con funtore ed arity prefissate. Per collegare l'Hashtable alle  liste si ha una lista intermedia di puntatori corrispondente ognuno ad una certa arity. La figura seguente dovrebbe chiarire meglio il tutto.

    Il RenameVisitor è un Visitor creato per effettuare il renaming. Il renaming consiste nel rinominare le variabili Prolog di ciascuna clausola. Ciò è necessario in quanto ogni variabile Prolog ha scope limitato alla clausola in cui compare. Quindi quando si utilizza una qualunque clausola, per esempio accedendo al DataBase Prolog, bisogna per prima prima cosa sostituire tutte gli oggetti che costituiscono le variabili di quella clausola con nuovi oggetti corrispondenti ai preesistenti ma diversi da questi. Gli oggetti "variabili" sono trattati in funzione della loro identità e quindi se non si fa renaming si possono introdurre delle unificazioni che non dovrebbero esserci. Vediamo un esempio per chiarire il concetto: 

DataBase -> 
        cl1)    p(X) :- X>0.
        cl1)    q :- p(1),p(2).

con query: ?- q.
    In questo esempio allorché si effettua la valutazione di p(1) (nel body della clausola cl2)) si accede al DataBase unificando con la clausola cl1) e quindi si provoca l'unificazione (l'argomento unificazione verrà ripreso più avanti) della variabile X con il valore 1. Se si è utilizzata la clausola cl1) senza effettuare renaming allora ad aver unificato con 1 è l'oggetto unico X, con la conseguenza che la successiva valutazione di p(2) fallisce perché l'oggetto X è già legato alla costante 1 e quindi non può più unificare con la costante 2! Ciò non è assolutamente corretto. Quindi è necessario che ogni qualvolta si accede al database per reperire la clausola cl1) la variabile X, che compare in essa, corrisponda ogni volta ad un oggetto diverso. Il renaming fa proprio questo: al primo accesso al DB viene restituita la clausola p(X) :- X>0, di essa si fa il renaming ottenendo la clausola p(X1) :- X1>0. in cui la variabile X1 è un oggetto diverso dall'oggetto X. Ad unificare con 1 è X1 e non X. Al secondo accesso si fa la stessa cosa ottenendo alla fine la clausola p(X2) :- X2>0. in cui X2 è diversa sia da X che da X1 e può quindi unificare con 2 poiché è una variabile libera. Alla fine l'interprete può concludere con successo avendo effettuato le unificazioni di X1 con 1 e di X2 con 2.
    Nel nostro interprete il renaming avviene tramite un Visitor che "visita" la clausola creandone una nuova in modo da sostituire alle variabili presenti delle nuove variabili (ovvero nuovi oggetti). Non sarebbe necessario ricostruire l'intera clausola in quanto ciò che interessa è di sostituire le sole variabili. Quindi si potrebbe definire un metodo per la classe contenete la clausola in grado di modificare il contenuto della stessa, in particolare sostituire le variabili con nuovi oggetti. Tuttavia abbiamo scelto di non fare mai uso di metodi modificatori poiché senza di essi ed utilizzando solo costruttori, selettori e predicati non è possibile fare effetti collaterali (programmazione in stile funzionale).

    La classe Unifier implementa un algoritmo di unificazione.
    L'unificazione è "un procedimento di manipolazione formale che stabilisce se due espressioni coincidono tramite opportune sostituzioni". La seguente tabella riassume tutti i casi in cui due espressioni unificano (SI) indicando le relative sostituzioni, oppure non unificano (NO):
 
  <costante> C2 <variabile> X2 <termine composto> S2
<costante> C1 SI se C1=C2 SI
{X2/C1}		 NO
<variabile> X1 SI
{X1/C2}		 SI
{X1/X2}		 SI
{X1/S2}
<termine composto> S1 NO SI
{X2/S1}		 SI se S1 ed S2 hanno stesso funtore e arità e gli argomenti unificano

    L'unificazione deve produrre una tabella di sostituzioni, ovvero una associazione tra variabili e valori, in quali possono essere a loro volta costanti, termini o variabili.
    È necessario organizzare attentamente la tabella delle sostituzioni per accedere velocemente al valore di una variabile. Basti pensare che se unifico X con Y, poi successivamente unifico Y con un termine, anche X deve essere legato allo stesso termine e viceversa.
    Per realizzare ciò abbiamo usato il metodo reference-dereference. Unificando due variabili unbound viene inserito una sola sostituzione (o riferimento), per esempio X -> Y. Quando successivamente devo unificare una di queste due variabili con qualcos'altro, dereferenzio la variabile seguendo ricorsivamente la catena di riferimenti fino a trovare una variabile unbound od un termine. Continuando l'esempio precedente, sia se devo unificare X con term che Y con term, la nuova sostituzione prodotta è comunque Y -> term. In questo modo si semplifica la creazione e l'utilizzo della tabella delle sostituzioni.
    È possibile anche scegliere se effettuare l'Occur Check, ovvero il controllo dei riferimenti circolari. Grazie al metodo reference-dereference il calo delle prestazioni dovute all'introduzione dell'Occur Check non risulta visibile.

Si è introdotta anche la possibilità di utilizzare le variabili come meta-variabili, cioè come un goal nel corpo di una clausola. Questo avviene semplicemente dereferenziando la variabile ed avviando la risoluzione sul risultato. Se il risultato è una variabile unbound viene genereato un errore di instanziazione.

    A conclusione di questa sezione elenchiamo tutti gli operatori ed i termini predefiniti che sono stati implementati nell'interprete.

    Gli operatori predefiniti sono riassunti dalla seguente tabella:
 
Simbolo
Priorità
Tipo
Descrizione
:-
1200
xfx
 separa antecedente e conseguente di una clausola
:-
1200
 fx costruisce una query con risolvente dato dal suo argomento
;
1100
 xfy operatore or
,
1000
 xfy operatore and
not
900
 fy operatore not: avvia una risoluzione SLDNF
=
700
xfx
 operatore di unificazione
is
700
xfx
 operatore di assegnamento di un'espressione aritmetica ad una variabile
=..
700
xfx
 consente di trasformare un termine nella lista delle sue componenti 
==
700
xfx
 operatore di uguaglianza fra oggetti
\==
700
xfx
 operatore di disuguaglianza fra oggetti
=:=
700
xfx
 operatore di confronto di uguaglianza aritmetica
=\=
700
xfx
 operatore di confronto di disuguaglianza aritmetica
<
700
xfx
 operatore di confronto aritmetico "minore"
>
700
xfx
 operatore di confronto aritmetico "maggiore"
=<
700
xfx
 operatore di confronto aritmetico "uguale o minore"
>=
700
xfx
 operatore di confronto aritmetico "maggiore o uguale"
+
500
yfx
 operatore aritmetico di somma (binario)
-
500
yfx
 operatore aritmetico di sottrazione (binario)
+
500
fx
 operatore aritmetico di somma (unario)
-
500
fx
 operatore aritmetico di sottrazione (unario)
*
400
yfx
 operatore aritmetico di moltiplicazione
/
400
yfx
 operatore aritmetico di divisione
^
200
xfy
 operatore aritmetico di elevamento a potenza

    I termini predefiniti sono riassunti dalla seguente tabella:
 
Funtore/arità Note
atom/1 atom(T): T è un atomo non numerico
atomic/1 atomic(T): T è un atomo oppure un numero (ossia T non è una struttura composta)
number/1 number(T): T è un numero intero o reale
integer/1 integer(T): T è un numero intero
var/1 var(T): T è una variabile non istanziata
nonvar/1 var(T): T non è una variabile non istanziata
compound/1 compound(T): T è un termine composto
functor/3 functor(T,F,N): il termine T ha come funtore principale F e come numero di argomenti N
arg/3 arg(N,T,A): A è l'argomento in posizione N del termine T
clause/2 clause(H,B): " ':-'(H,B) " è una clausola contenuta nel DataBase Prolog
assert/1 assert(T): la clausola T viene aggiunta al DataBase (in fondo)
asserta/1 asserta(T): la clausola T viene aggiunta all'inizio del DataBase
retract/1 retract(T): la prima clausola nel DataBase unificabile con T viene rimossa
retractall/1 retractall(T): tutte le clausole nel DataBase unificabili con T vengono rimosse
ground/1 ground(T): T non è una variabile unbound oppure è un termine composto che non contiene variabili unbound
call/1 call(T): T è il nuovo goal;
rende disponibile all'utente la funzione di valutazione Prolog
listing/1 listing(T): stampa sullo standard output il contenuto del database relativo a Term, se Term è un atomo stampa tutte le clausole con testa uguale a Term.
random/3 random(Min,Max,V): unifica a V un numero random compreso fra Min e Max
write/1 write(T): stampa T sullo standard output
read/1 read(T): t viene unificato con il termine letto da standard input
"Consultare un file" [X]: X è il nome di un file che viene consultato
nl stampa sullo standard output un "new line" 
fail provoca il fallimento dell'interprete
true ha sempre successo
! è il cut: provoca una "potatura" dell'albero di ricerca