Analisi

Architettura del sistema

Prima di tutto è opportuno distinguere nel sistema tre componenti distinti:

Elaborazione: si occupa di leggere i dati da input e fornire i relativi risultati su ouput. In questa applicazione la parte di elaborazione è costituita da un interprete, cioè da un automa che riceve delle frasi in ingresso appartenenti ad un certo linguaggio, le analizza e le valuta.
Input / output: si occupa della comunicazione tra il programma e le risorse esterne (in particolare si riferisce all'accesso al file system e alle risorse di rete).
Interfaccia utente: si occupa dell'interazione tra la macchina e l'utente finale. Nonostante anche l'interfaccia utente sia in pratica un particolare tipo di interazione con l'esterno è opportuno distinguerla dall'input / output per ragioni concettuali.

Questa distinzione in moduli separati permette la riusabilità e la incrementalità del software, infatti sarà possibile riutilizzare gli stessi moduli anche a fronte di variazioni di specifiche. Ad esempio la parte di elaborazione sarà identica sia per interfacce grafiche che testuali, e sia per interazioni locali che remote.

L'interprete a sua volta può essere scomposto in più moduli aventi compiti differenti:

Analizzatore lessicale (lexer): riceve la frase in ingresso e fornisce in uscita dei token, cioè si occupa di separare all'interno della frase i diversi elementi lessicali quali numeri, identificatori, operatori, ecc.
Analizzatore sintattico (parser): riceve in ingresso i token e costruisce una forma interna della frase, sotto forma di albero (APT = Abstract Parse Tree)
Analizzatore semantico (evaluator): riceve la rappresentazione interna della frase e ne esegue la valutazione dandone in uscita il risultato. Da evidenziare che ci possono essere diversi tipi di valutazione per uno stesso linguaggio.

Espressioni

Prima di tutto definiamo formalmente le espressioni che il nostro interprete dovrà riconoscere e valutare. Per cominciare prendiamo in considerazioni le espressioni aritmetiche, descritte dalle seguenti produzioni (lo scopo è Exp), tipiche dei linguaggi di tipo imperativo (tra cui anche java).

Sintassi espressioni aritmetiche:

Exp     ::= Term | Exp + Term | Exp - Term
Term    ::= Factor | Term * Factor | Term / Factor
Factor  ::= ( Exp ) | Number | Ident

Ident   ::= Letter RestId
RestId  ::= Letter | Digit
Number  ::= IntNum | RealNum
IntNum  ::= Digit | IntNum Digit
RealNum ::= IntNum . IntNum | . IntNum
Letter  ::= a | ... | z
Letter  ::= A | ... | Z
Digit   ::= 0 | ... | 9

La rappresentazione interna di un'espressione può essere fatta con un albero binario.
Esempio: 4*2+m/c
può essere rappresentata internamente con l'albero in figura. Per comodità si sono tolti dalla rappresentazione interna tutti i simboli non terminali in quanto non utili ai fini della valutazione (questo equivale a prendere in considerazione la sintassi astratta del linguaggio).

Ora vogliamo estendere la precedente sintassi in modo da allargare il nostro dominio anche alle espressioni relazionali e logiche. Una possibile sintassi potrebbe essere la seguente:

Sintassi espressioni aritmetico - logiche:

Prop    ::= Impl | Prop == Impl
Impl    ::= LExp | Impl => LExp
LExp    ::= LTerm | LExp or LTerm
LTerm   ::= LFact | LTerm and LFact
LFact   ::= not LFact | RelExp
RelExp  ::= Exp | Exp RelOp Exp
RelOp   ::= < | = | > | <= | >= | <>
Exp     ::= Term | Exp + Term | Exp - Term
Term    ::= Factor | Term * Factor | Term / Factor
Factor  ::= ( Prop ) | Number | true | false
Factor  ::= Ident | Ident () | Ident ( ArgList )
ArgList ::= Exp | Exp , ArgList

In questo caso si sono omesse le produzioni relative ai numeri e agli identificatori, in quanto uguali alla sintassi precedente. In questa nuova estensione lo scopo è costituito da una proposizione, che a seconda dei casi potrà restituire un valore logico (true o false) oppure numerico. In questo modo si è realizzata quindi una sintassi ibrida che comprende le caratteristiche sia delle espressioni aritmetiche che logiche. Inoltre è stata anche prevista la possibilità di usare delle funzioni. La rappresentazione è ancora ad albero binario. Seguono alcuni esempi:

Esempio 1: a=>b == not a or b
Questa è un 'espressione logica pura e può essere rappresentata internamente come in figura. Il risultato sarà di tipo booleano e in questo caso particolare sarà vero per ogni valore di a e b.

Esempio 2: m<=c+4 and b*2>e
Qui abbiamo una espressione ibrida contenente operatori aritmetici, relazionali e logici. Il risultato della valutazione sarà anche qui un valore booleano, vero o falso a seconda dei valori delle variabili.

Possiamo notare che la sintassi precedente presenta delle ricorsioni sinistre, e quindi a priori avremmo la impossibilità di usare l'analisi ricorsiva discendente per il riconoscimento. In realtà vedremo che non sarà difficile ricondursi ad una sintassi equivalente eliminando le ricorsioni sinistre. Possiamo inoltre notare la presenza di parecchi operatori, aventi caratteristiche e priorità diverse. In questo modo ogni volta che vorremo introdurre un nuovo operatore nella grammatica, dovremo anche inserire delle nuove produzioni apposite. Vediamo ora quindi una sintassi nuova (ispirata al Lisp) che generalizza il caso precedente dele espressioni aritmetico-logiche, nel caso funzionale.

Sintassi Lisp:

Sexp     ::= AtomSexp | ConsSexp
AtomSexp ::= Ident | Number | ( )
ConsSexp ::= ( PairSexp ) | ( ListSexp )
PairSexp ::= Sexp . Sexp
ListSexp ::= Sexp | Sexp ListSexp

Per quanto riguarda la rappresentazione interna, abbiamo sempre un albero, che però sarà realizzato seguendo lo stile del Lisp, in cui un albero può essere visto come una lista il cui primo elemento è la radice, il secondo elemento il sottoalbero di sinistra ed il terzo elemento il sottoalbero di destra. In Lisp convenzionalmente le liste sono coppie il cui secondo elemento è una lista, eventualmente vuota (nil).

Analizziamo ora il significato delle espressioni. Un'espressione simbolica (Sexp), può essere atomica (AtomSexp) oppure composta (ConsSexp). Le prime a loro volta si suddividono in identificatori predefiniti, simboli di variabile e notazioni che denotano dei valori (come ad esempio i numeri). Le espressioni strutturate invece vengono interpretate nel seguente modo:

(expr-operatore expr-operando1 expr-operando2 ...)

il primo elemento è sempre visto come un operatore seguito dalla lista dei suoi argomenti. In questo modo possiamo anche esprimere operazioni con un numero di operandi maggiore di due.

Riprendendo l'esempio precedente:
4*2+m/c
Questa espressione può essere riscritta con la nuova sintassi nel modo seguente:
(+ (* 4 2) (/ m c))
la cui rappresentazione interna è riportata in figura.

Le due sintassi precedenti possono essere considerate equivalenti e pertanto i rispettivi analizzatori sintattici daranno in uscita una forma interna dello stesso tipo, che poi potrà essere valutata da uno stesso valutatore. Perciò rappresenteremo internamente anche le espressioni in stile java con delle liste come per il Lisp. Da notare che nella sintassi Java tutti gli operatori (sia aritmetici che relazionali) possono essere considerati come casi particolari di funzioni a due operandi. Vale a dire che risulterà equivalente scrivere "2+3" oppure "+(2,3)". Per quanto riguarda la computazione relativa ai valori booleani, in accordo a quanto fa il Lisp, si considererà falsa un'espressione di tipo nil, mentre qualsiasi altra espressione sarà considerata vera. Perciò inserendo valori o variabili numeriche in un'operazione logica, essi verranno considerati come veri.

Vediamo ora come avviene la valutazione delle espressioni. Utilizzeremo il modello applicativo, che consiste in tre passi:

Valutazione, nell’environment corrente, della expr-operatore.
Valutazione, nell’environment corrente, delle expr-operando.
Applicazione dell'operazione agli operandi.

Da questo modello si evince la presenza di due distinte funzionalità di cui deve essere dotato l'interprete:

La valutazione (eval) che che valuta un'espressione in un dato environment, restituendo un'espressione come risultato. Dato un APT la eval può essere ottenuta nel seguente modo:
- ogni nodo operando dell'APT deve restituire il suo valore come risultato
- ogni nodo operatore deve eseguire un'apply relativa a se stesso ed i cui agomenti sono dati dai sottoalberi
L'applicazione (apply) che applica una funzione ai suoi argomenti, restituendo un'espressione come risultato. Può essere ottenuta nel seguente modo:
- commutazione dall'environment corrente all’environment di definizione della funzione
- estensione dell'environment di definizione della funzione con i nuovi binding dati dai parametri formali e attuali della funzione
- valutazione del corpo della funzione
- restituzione del risultato con ripristino dell’environment preesistente

Per quanto riguarda la valutazione si ha che:

Espressioni atomiche come i numeri, se valutate restituiscono se stesse (self evaluating).
Il valore di un simbolo può essere ricavato se nell'environment locale o gloabale esiste un binding che ha lo stesso nome. Ad esempio, quindi, l'environment globale dovrà contenere tutti i simboli di operatori primitivi visti in precedenza.
Le funzioni definite dall'utente possono essere rappresentati come chiusure, cioè oggetti computazionali formati da una tripla:
1. ambiente di definizione della funzione, cioè l'insieme dei binding presente al momento della definizione della funzione. Si è quindi scelto di di realizzare un binding lessicale. Se invece l'environment considerato fosse stato quello al momento della chiamata della funzione avremmo avuto un binding dinamico.
2. lista degli argomenti.
3. espressione che ne denota il corpo.

Abbiamo fin qui parlato di environment, senza però specificare cosa si intendesse di preciso. Un environment è definito come un insieme di legami (binding) simbolo-valore. Si tratta di una struttura dinamica che viene modificata durante il processo computazionale in due modi: con estensioni a tempo di vita limitato e politica LIFO è il caso dell'environment locale) oppure con modifiche permanenti (enviroment globale).

Operatori, primitive e forme speciali

Come risulta dalla sintassi astratta esposta in precedenza, nel nostro sistema avremo diversi operatori, con differenti significati e priorità. Nella tabella seguente vengono riportati tutti gli operatori riconosciuti dall'interprete.

Operatori:

*Operatore*	*Significato*	Tipo
+	somma	aritmetico
-	sottrazione	aritmetico
*	moltiplicazione	aritmetico
/	divisione	aritmetico
<	minore	relazionale
>	maggiore	relazionale
=	uguaglianza	relazionale
<=	minore o uguale	relazionale
>=	maggiore o uguale	relazionale
<>	non uguaglianza	relazionale
not	negazione	logico
and	prodotto logico	logico
or	somma logica	logico
=>	implicazione	logico
==	equivalenza	logico

Oltre agli operatori è opportuno considerare le classiche primitive Lisp per la gestione delle strutture dati (liste) e per l'input / output. Di seguito si riporta una tabella riassuntiva delle primitive che verranno implementate.

Primitive:

*Primitiva*	*Significato*
cons	permette di costruire una coppia o una lista
car	restituisce il primo elemento di una lista o di una coppia
cdr	restituisce il secondo elemento di una lista o di una coppia
null	controlla se una lista è vuota
eq	controlla se due espressioni sono uguali
atom	controlla se un espressione è atomica
eval	valuta un espressione
read	legge un'espressione da input
print	scrive un'espressione su output
prin1	analogo a print ma va a capo

Tutte le precedenti primitive saranno implementate usando la classe IdentSexp, cioè quella degli identificatori, ed in particolare saranno degli identificatori di funzione. Perciò in fase di valutazione verrà utilizzato il modello applicativo visto in precedenza. Da evidenziare che grazie alle primitive eval, read e print è possibile realizzare un metainterprete Lisp.

In Lisp/Scheme esistono alcune operazioni per la cui valutazione non si utilizza il modello applicativo e sono per questo dette forme speciali.

Forme speciali:

*Forma*	*Significato*
quote	restituisce il primo argomento senza valutarlo.
define	permette di definire un simbolo a livello di environment globale. Ha la forma (define ident expr), il risultato è la valutazione di expr e dell'inserimento del binding identificatore / valore nell'ambiente globale. L'espressione restituita è costituita dal nome dell'identificatore. Ad esempio un espressione del tipo (define a ( 7 6))* provoca l'inserimento del binding a / 42 nell'environment globale e la restituzione del simbolo a. Con la define è possibile soltanto assegnare un valore ad un identificatore, ma non è possibile modificarlo, cioè non sono possibili effetti collaterali sulle strutture dati. Da notare che contrariamente al modello applicativo, in questo caso il primo argomento non viene valutato, ma si controlla solo che sia un identificatore.
cond	permette di trattare espressioni condizionali. La forma è del tipo (cond (pred expr...)...) cioè l'operatore cond è seguito da una lista di coppie il cui primo elemento è un predicato ed il secondo una lista di espressioni. Appena si trova un predicato che restituisce true si valuta la relativa lista di espressioni e si ritorna come risultato la valutazione dell'ultima espressione della lista.
lambda	permette di definire delle chiusure, cioè degli oggetti computazionali di primo livello che corrispondono al concetto di funzioni. Una chiusura è formata dalla lista degli argomenti, dal corpo della funzione e dall'environment presente al momento della definizione. In questo modo si realizza un binding lessicale anzichè dinamico in quanto la valutazione degli argomenti viene fatta con riferimento al momento in cui la funzione è stata definita e non quello in cui è stata invocata.

Con le precedenti forme speciali si realizza un linguaggio computazionalmente completo, in grado di gestire assegnamento (anche se in una forma limitata dato che non è possibile modificare i valori), espressioni condizionali e funzioni. Alle precedenti possono poi essere aggiunte altre forme speciali che rappresentano zucchero sintattico, cioè che facilitano l'utente nella scrittura dei programmi.

Altre forme speciali (come zucchero sintattico):

*Forma*	*Significato*
setq	permette la definizione e la modifica di un simbolo. E' simile alla define, ma con questa è possibile ridefinire un simbolo già definito. Anche qui non si segue il modello applicativo poichè il primo simbolo non è valutato. E' molto importante segnalare che questa forma introduce degli effetti collaterali sul sistema, in quanto permette la modifica dei dati, che altrimenti non sarebbe possibile.
defun	permette di definire delle funzioni. Si tratta in pratica di zucchero sintattico perchè è costruibile a partire da define e lambda. E' stata introdotta per permettere all'interprete di riconoscere definizioni di funzioni in Lisp puro per le quali si usa appunta defun.
set	simile alla setq (la quale può essere vista come zucchero sintattico per (set (quote ...)) ), ma in questo caso il primo argomento viene valutato e la sua valutazione dovrà restituire un identificatore.
if	una variante della cond. In questo caso la sintassi è (if test-expr expr1 expr2). Se l'espressione di test è vera si valuta expr1 altrimenti si valuta expr 2. E' del tutto simile alla classica espressione condizionale test?expr1:expr2 alla quale sono molto abituati i programmatori c e java.
let	permette di creare dei binding nell'environment locale. La sintassi è (let (bindings) expr). La let valuta l'espressione expr dopo aver esteso l'environment locale con i bindings specificati, che sono rappresentati da una lista di coppie simbolo / valore. Ci sono due metodi per realizzare la let: normale e sequenziale. Nel primo la valutazione dei binding viene fatta tutta con lo stesso environment presente al momento della chiamata. Nel secondo ogni binding tiene conto dell'estensione dell'environment dovuta ai binding che lo precedevano in lista. (In lisp la distinzione tra le due è fatta con let e let*).

Prolog

Un programma Prolog è costituito da un insieme di clausole, che possono assumere la forma

oppure

A :- B1, B2, ..., BN.

A e Bi rappresentano formule atomiche (atom), A viene definita testa (head) della clausola, mentre la sequenza dei Bi è detta corpo (body) della clausola. Una clausola senza il corpo viene detta asserzione, se invece è dotata di testa e corpo, viene definita regola. Una formula atomica si rappresenta con

p(t1 ,t2 , ... , tm)

dove p indica il simbolo del predicato e ti i termini. Vediamo la definizione di termine, un termine può essere:

Una costante (le costanti possono essere numeri oppure identificatori aventi come primo carattere una lettera minuscola).
Una variabile (identificatori aventi come primo carattere una lettera maiuscola oppure il carattere "_").
Una funzione. (Si ha che f(t1, t2, ...,tk) è un termine se f è un simbolo di funzione a k argomenti e t1, t2, ..., tk sono termini. Un termine di questo tipo viene spesso chiamato struttura ).

Fatta questa premessa possiamo ora introdurre la sintassi che adotteremo.

Sintassi Prolog:

Program  ::= Clause | Clause Program
Query    ::= :- Body .
Clause   ::= Atom . | Atom :- Body .
Atom     ::= Symbol | FuncPred | OperPred
Body     ::= BodyElem | BodyElem , Body 
BodyElem ::= Atom | !
FuncPred ::= Symbol ( ArgList )
ArgList  ::= Term | Term , ArgList
OperPred ::= Term Operator Term
Operator ::= == | \== | =
Term     ::= Symbol | FuncPred | Var | List | ( Atom )
List     ::= [ ] | [ TermList ] 
TermList ::= Term | Term , TermList | Term | Term

Symbol   ::= Lettmin | Lettmin Rest | Number 
Var      ::= Lettmax | Lettmax Rest | _ 
Rest     ::= Letter | Digit | Letter Rest | Digit Rest 
Number   ::= Digit | Number Digit
Letter   ::= Lettmin | Lettmax
Lettmin  ::= a | ... | z
Lettmax  ::= A | ... | Z
Digit    ::= 0 | ... | 9

Lo scopo può essere Program oppure Query, a seconda che si voglia leggere una lista di clausole (in fase di acquisizione della base di conoscenza) oppure si voglia interrogare il sistema con un goal. Come si può notare, oltre alla normale sintassi del prolog, si sono introdotti anche gli operatori di confronto (\== e ==), di unificazione (=), il cut (!) e la notazione con le parentesi [] per indicare le liste di termini. Per quanto riguarda la rappresentazione interna essa sarà ancora ad albero, in accordo con quanto esposto precedentemente.