Progetto

Tassonomia delle classi

Dalle considerazioni precedentemente fatte in fase di analisi possiamo modellare il dominio del problema (cioè le espressioni), con la seguente tassonomia di classi:

Oltre alla precedente gerarchia di classi è necessario introdurre dei nuovi tipi di espressione che verranno utilizzate solamente nella fase di parsing delle frasi e che quindi non potranno fare parte dell'apt finale restituito dal parser. A tale scopo è stata creata una classe astratta TokenSexp (derivata da IdentSexp), la quale generalizza il concetto di token, e da questa si sono ottenute le classi concrete dei vari token.

Classe Significato TokenSexp token generico LParToken carattere ( RParToken carattere ) DotToken carattere . LBraToken carattere [ RBraToken carattere ] QuoteToken carattere ' CommaToken carattere , SemiCommaToken carattere ; EofToken fine file

Analisi lessicale

Per la realizzazione dell'analizzatore lessicale si può prevedere una classe astratta Lexer, avente le funzionalità comuni ad ogni lexer, quali ad esempio la lettura del prossimo token, la scrittura di messaggi su un dispositivo di output (cosa utile per il debugging). Da questa classe si deriveranno poi due analizzatori distinti: il primo per Java e Lisp (per cui si utilizzano gli stessi token) ed il secondo per il prolog.

Analisi sintattica

Come per il caso del Lexer anche qui si è prevista una classe astratta Parser che fornisce la lettura della prossima espressione, il controllo sulla fine dello stream e la scrittura di messaggi di debugging. In questo caso ovviamente ad ogni sintassi dovrà corrispondere un differente Parser, per cui se ne dovranno realizzare tre. In tutti e tre i casi l'analisi viene fatta con il metodo dell'analisi ricorsiva discendente, per cui ad ogni simbolo non terminale viene associata una funzione che consuma i token che le competono e restituisce in caso di successo la rappresentazione interna. Questo metodo però non è applicabile nel caso in cui nelle regole di produzione siano presenti di delle ricorsioni a sinistra, nel qual caso infatti il Parser andrebbe in loop. Come abbiamo visto nel caso della sintassi in stile java c'erano delle ricorsioni sinistre, ma queste possono essere eliminate semplicemente riscrivendo le produzioni con la notazione BNF estesa. Ad esempio:

Prop ::= Impl { == Impl }
Impl ::= LExp { => LExp }
...
Exp  ::= Term { + Term } | Term { - Term }
Term ::= Factor { * Factor} | Factor { / Factor }
...

La tabella seguente riassume i metodi di ognuno dei tre parser corrispondenti ai rispettivi simbolo non terminali:

Analisi semantica

Per quanto riguarda l'architettura del valutatore, che è il cuore del nostro interprete, abbiamo diverse possiblità:

• metodologia funzionale: in cui le funzionalità di eval e apply sono realizzate come metodi di una classe valutatore. In questo modo è facile introdurre nuove possibili valutazioni ma è difficoltoso aggiungere delle nuove produzioni (cioè dei nuovi sottotipi di Sexp).
• metodologia ad oggetti: in cui le funzionalità di eval e apply sono realizzate da un metodo specializzato per ogni classe della tassonomia. Con questo metodo, al contrario del precedente è facile aggiungere nuove produzioni ma complicato aggiungere nuovi tipi di valutazione, cosa che comporterebbe l'aggiunta di un nuovo metodo ad ogni classe della tassonomia.
• metodologia con pattern visitor: questo metodo permette di conciliare i due precedenti. In questo caso si ha un double-dispatching che permette di percorrere una struttura dati con diverse politiche. Per la realizzazione di visitor avremo un insieme di classi ognuna relativa ad un diverso tipo di valutazione. Per ciascun visitor si dovranno definire dei metodi per la visita di oguna delle classi della tassonomia. Infine ogni classe della tassonomia dovrà essere dotata di un metodo per specificare un visitor (accept).

Dato che generalmente un linguaggio di programmazione è caratterizzato da una grammatica fissa e da diverse possibili valutazioni, in un primo momento si può pensare di realizzare un'apposita classe per la valutazione che chiameremo LispEvaluator. In un secondo momento poi, si potrà adottare il pattern visitor in modo da effettuare diverse valutazioni. Ad esempio potremo avere un visitor per la valutazione (EvalSexpVisitor), che utilizzerà la classe LispEvaluator precedentemente creata grazie al meccanismo di wrapping, uno per la visualizzazione grafica della rappresentazione interna di un'espressione (TreeSexpVisitor), uno per la rappresentazione esterna in forma Lisp (LispSexpVisitor) ed infine un altro che fornisce la rappresentazione in forma polacca prefissa, infissa e postfissa (PolSexpVisitor).

Per realizzare questo dovremo aver dotato ogni classe della tassonomia di un metodo accept per poter specificare il visitor da utilizzare. L'interfaccia SexpVisitor invece, definisce i metodi di visita che ogni visitor dovrà poi implementare.

Vediamo ora come è stato gestito l'environment. Dobbiamo prima di tutto distinguere tra environment locale ed environment globale. Il primo è quello visibile solo all'interno di una funzione e che quindi viene esteso e ristretto durante la computazione, cioè nelle chiamate ricorsive di eval e apply. Il secondo invece comprende tutti i simboli che sono visibili in ogni punto del programma. Per quanto riguarda il primo, in teoria sarebbe necessario introdurre la gestione di record di attivazione, ma dato che abbiamo già a disposizione la ricorsione di Java, possiamo usare quella per ottenere il risultato deisderato, semplicemente passando l'environment come argomento alla eval. Per quanto riguarda invece l'environment globale possiamo introdurre una nuova classe apposita Environment, dotata dei metodi per aggiungere un binding (extendEnv) e per ricercare un simbolo (searchInEnv). Il concetto di environment può essere realizzato come lista di coppie simbolo / valore, dato che abbiamo già a disposizione la tassonomia delle Sexp (ed in particolare la ConsSexp) e le primitive tipiche delle liste. Questa scelta ci permette di affrontare il problema con un approccio totalmente funzionale, come se stessimo realizzando un metainterprete Lisp scritto in Lisp. Questo va però a scapito dell'efficienza, infatti si potrebbero addottare strutture dati più adatte ed efficienti.

Estensioni per il prolog

Prima di tutto dobbiamo estendere la tassonomia precedentemente creata in modo da supportare i nuovi elementi del linguaggio Prolog.

Anche in questo caso avremo delle classi ulteriori che vengono usate solo in fase di parsing e che non faranno parte dell'APT finale restituito dal parser.

Classe Significato PipeToken carattere | IfToken simbolo :- FunToken funtore

Per quanto riguarda le variabili (classe Var) dobbiamo ricordare che in Prolog una variabile è in pratica un riferimento ad un termine, e per realizzare questo dovremmo introdurre all'interno della classe Var un nuovo campo value che inizialmente punterà alla variabile stessa e che in fase di risoluzione potrà essere associato ad altri termini. Nel considerare le variabili (Var) non bisogna inoltre dimenticare che all'interno della stessa clausola variabili omonime devono corrispondere ad un'unica istanza della classe Var. Per realizzare ciò si tiene memoria delle variabili presenti nella clausola corrente in una tabella (questo avviene in fase di analisi lessicale).

Con le nuove specifiche del prolog abbiamo sia delle nuove classi nella tassonomia che delle nuove possibili interpretazioni della struttura dati. A questo punto quindi la metodologia del pattern visitor sembra perdere le sue qualità, infatti ora dovremmo introdurre un nuovo metodo di visita nell'interfaccia SexpVisitor per ogni nuova classe, ma questo comporterebbe anche la modifica di tutti i visitor precedentemente creati. Inoltre in questo caso i metodi di visita avranno una signature diversa, visto che prevederanno due argomenti anzichè uno solo, dato che la visita che dovremo fare sarà l'unificazione tra due termini. Sembrerebbe quindi necessario rifare tutto da capo. Per ovviare a questo problema invece, si è costruita una nuova interfaccia java denominata PrologVisitor, dotata soltanto dei metodi di visita delle classi relative al prolog. Dopodichè si è aggiunto alle classi della tassonomia un metodo accept2 che accetta un PrologVisitor ed una seconda Sexp, e che nel caso delle classi della tassonomia precedente non fa nulla, mentre per le classi relative al prolog questo metodo viene sovrascritto in modo da invocare il relativo metodo di visita del visitor. Questa soluzione potrebbe non sembrare molto elegante ma è la più rapida da attuare.

Come detto ci servirà un visitor per l'unificazione (UnifyVisitor), che controlli se esiste una sostituzione delle variabili che rende uguali due termini. I bindings variabile / termine che costituiscono l'eventuale unificazione vengono realizzati sfruttando il campo value delle istanze della classe Var con cui vengono rappresentate le variabili. Quando si crea un legame variabile / termine la variabile viene messa in uno stack (trail) per poterla slegare in fase di backtracking. L'unificazione viene fatta seguendo le specifiche della seguente tabella:

Inoltre per implementare gli operatori == e \== ci servirà un ulteriore visitor che realizzi il confronto tra due termini (CompareVisitor). In pratica il confronto coincide con l'unificazione, con la differenza che nel caso delle variabili (classe Var), si ha che una variabile V è uguale ad un termine T se V è unbound e T è una variabile unbound con stesso nome oppure se V è bound a T1 e T1 è uguale a T. Perciò tale visitor potrà essere realizzato estendendo il precedente UnifyVisitor e ridefinendo il metodo di visita delle variabili.

Risoluzione Prolog

La risoluzione è affidata ad un componente PrologEvaluator, ed in particolare al suo metodo demo che riceve in ingresso le rappresentazioni interne del programma e del goal e applica l'algoritmo di risoluzione che presenta una regola di computazione left-most e una regola di ricerca depth first con backtracking. Si procede nel seguente modo:

• se il goal è un'istanza di True si ha successo e viene stampato il risultato con la visualizzazione dei legami delle variabili
• altrimenti viene chiamato il metodo step

La funzione step controlla se il primo atomo del goal unifica (usando UnifyVisitor) con la testa della prima clausola del programma e agisce in questo modo:

• se unifica si tiene traccia dei legami associati alle variabili e viene creato un nuovo risolvente che ha come testa il body della clausola e come resto il resto del goal, quindi si esegue nuovamento demo con questo nuovo goal
• altrimenti cerca di unificare il primo termine del goal con una clausola successiva, se questo non è possibile termina e si dovrà ritornare al passo precedente (backtracking). In particolare si dovrà:
  • eliminare i legami associati alle variabili durante l'unificazione
  • cercare di unificare con la clausola successiva del programma

La memorizzazione dei legami delle variabili può essere realizzata con uno stack (trail). In prolog una volta che è stato stabilito un legame tra una variabile e un termine questo non può essere modificato (proprieta' write-once). Un legame, come abbiamo detto, deve però essere sciolto in caso di backtracking, quando si devono esplorare strade alternative di soluzione. Per realizzare questo si dovrà effettuare un renaming delle variabili del programma ogni volta che c'è un'unificazione. Per ottenere questo bisogna effettuare una deep copy dell'albero che rappresenta il programma, introducendo un metodo per la clonazione nelle classi tella tassonomia. Per risparmiare memoria potremmo usare structure sharing nel caso di oggetti che non hanno stato, come ad esempio le costanti (classe Symbol).

Operatori di confronto == e \==

Gli operatori == e \== vengono gestiti semplicemente inserendo all'inizio della funzione step un test che controlla se il primo atomo del goal è un predicato di nome == o \== con due argomenti. In tal caso si confrontano i due argomenti usando CompareVisitor: se il confronto non fornisce il risultato previsto dall'operatore in questione si esce immediatamente, altrimenti si crea un nuovo goal eliminando il predicato dal goal corrente e si tenta di dimostrarlo richiamando demo, dopodiché si esce.

Operatore di unificazione =

L'operatore = viene gestito inserendo all'inizio della funzione step un test che controlla se il primo atomo del goal è un predicato di nome = con due argomenti. In tal caso si prova ad unificare i due argomenti: se unificano si crea un nuovo goal eliminando il predicato dal goal corrente e si tenta di dimostrarlo (richiamando demo), dopo aver effettuato un renaming delle variabili; dopodichè si esce dopo aver slegato eventuali bindings che si sono formati nei passi precedenti.

Il cut !

In fase di dimostrazione, deve essere ignorato, mentre in fase di backtracking deve provocare l'eliminazione di tutte le alternative aperte per tutte le clausole relative ai termini che lo precedono nel body della clausola in cui esso compare, comprese le alternative relative alla testa della clausola stessa. Per la gestione dei cut si è introdotto un campo head nella classe Cut usata per rappresentare internamente i cut. Questo campo è un puntatore alla testa della corrispondente clausola.
La gestione del cut avviene inserendo all'inizio della funzione step un test che controlla se il primo atomo del goal è un cut. In tal caso si crea un nuovo goal eliminando il cut dal goal corrente e si tenta di dimostrarlo richiamando demo; quindi si pone una variabile di nome cuthead uguale alla testa del cut (a meno che non fosse già stata impostata in precedenza) e si esce. Affinché in backtracking siano considerati falsi tutti i subgoal che precedono ciascun cut fino e compreso il subgoal che ha unificato con la corrispondente testa, basta introdurre il seguente test prima della chiamata ricorsiva alla funzione step: se cuthead non è impostata si fa la chiamata (cioè si prendono in considerazione altre alternative per il goal corrente), altrimenti si esce subito dopo aver eventualmente disattivato cuthead nel caso coincida con la testa della prima clausola del programma corrente (ciò si verifica non appena si riprende la dimostrazione del subgoal che ha unificato con la testa del cut).

More

Dato che vogliamo realizzare la gestione di soluzioni multiple, per implementare la fase di interazione con l'utente relativa alla richiesta di visualizzare ulteriori soluzioni, possiamo realizzare il componente PrologEvaluator citato come Thread. In questo modo sarà possibile mandarlo in esecuzione e sospenderlo appena venga trovata una soluzione. Dopodichè si attenderà che l'utente scelga yes oppure no, e di conseguenza si risveglierà il thread per trovare altre soluzioni, oppure si terminerà il thread.