invece un modello che parte dalla logica per arrivare agli oggetti. Ma prima di fare ciò dobbiamo porre le
basi per capire quello che vogliamo fare. In questa prima parte parleremo del perché gli oggetti sono così
importanti tanto che oggi si dà per scontato che i programmi siano ad oggetti, e delle peculiarità della LP.
Alla fine della esposizione dovremmo essere convinti dei seguenti fatti
• gli oggetti hanno proprietà tali da renderne giustificato l’ampio uso che se ne fa oggi,
• la LP ha delle interessanti caratteristiche assenti nella OOP e che la rendono per certi versi
complementare a questa;
• vale la pena tentare di integrare in maniera organica
OOP ed LP.
Parte Prima: Differenze tra OOP e LP
LP e OOP
5
Capitolo 1
Differenze tra OOP ed LP
Verranno illustrate le caratteristiche della LP e messe in risalto le differenze con la OOP. Inoltre
mostreremo gli usi naturali dei due strumenti.
1.1. Caratteristiche della LP
Vediamo le peculiarità della LP che la differenziano dagli altri modelli, per capire perché questo modello merita
attenzione, non solo sul piano concettuale, ma anche su quello pratico. Vogliamo cioè capirne l’utilità ed il tipo di
applicazioni per cui l’uso risulta più naturale. Una volta appreso che la LP ha molto da offrire nei confronti della OOP,
nel senso che per certe applicazioni ci dà dei vantaggi (in termini di semplicità di utilizzo, chiarezza, prestazioni, o
quant’altro), se vi sono delle limitazioni, avrà senso compiere sforzi al fine di porvi rimedio. Elenchiamo le
caratteristiche della LP dividendolo in peculiarità, che la differenziano da ogni altro tipo di modello, e caratteristiche
secondarie, che sono anche del modello funzionale ma non di quello imperativo.
Peculiarità:
• dichiaratività dei programmi
• invertibilità: uno stesso programma può risolvere più problemi
• possibilità di fare inferenze
• motore di ricerca su alberi già implementato con possibilità di backtracking
• unificazione
Caratteristiche secondarie:
• mancanza di tipi
• variabili senza assegnamento
• mancanza di stato e quindi di effetti collaterali
• mancanza di interazione
1.1.1. Peculiarità della LP
Per peculiarità intendiamo quelle caratteristiche della LP che la differenziano da ogni altro tipo di modello (imperativo
o funzionale). Vediamole una ad una.
1.1.1.1. Dichiaratività dei programmi
Per dichiaratività si intende che si specifica il cosa fare e non il come farlo. Mostriamo questo con il classico esempio
dell’append di due liste
append([],L1,L1).
append([H|T],L1, [H|L]) :- append(T,L1,L).
Il programma coincide con la specifica, non abbiamo menzionato strutture di nessun tipo né algoritmi. Il come è
nascosto dentro la macchina LP. Si provi a pensare ad un programma analogo in linguaggio imperativo, ad esempio il
C, si noterà immediatamente la differenza in termini di comprensibilità e di facilità di scrittura.
Dalla dichiaratività deriva la seguente interessante caratteristica:
• invertibilità: uno stesso programma può risolvere più problemi
1.1.1.1.1. Invertibilità: uno stesso programma può risolvere più problemi
Abbiamo costruito l’esempio dell’append pensandolo come programma che riceve in ingresso due liste (i primi due
parametri) e fornisce in uscita la lista concatenazione delle due nel terzo parametro. Un tipico goal può essere come il
seguente
:- append([3,5],[6,7,8,9],L).
yes, L/[3,5,6,7,8,9]
Ma possiamo usare lo stesso programma per fare la “differenza” di due stringhe:
:- append(L,[6,7,8,9], [3,5,6,7,8,9]).
yes, L/[3,5]
Lo abbiamo cioè usato in maniera inversa rispetto a quella in cui lo avevano progettato. Questa è una diretta
conseguenza della dichiaratività, non specificando il come non abbiamo neanche fatto commitment che pregiudicassero
l’invertibilità.
1.1.1.2. Possibilità di fare inferenze
La possibilità di fare inferenze significa che a partire da un certo insieme di informazioni e di regole possiamo derivarne
delle altre.
Parte Prima: Differenze tra OOP e LP
LP e OOP
6
fatti + regole di inferenza → informazioni derivate
E’ senz’altro la caratteristica più interessante ed usata della LP. Risulta del tutto naturale scrivere delle relazioni tra
termini, i quali rappresentano le entità del discorso, e cioè dei fatti che risultano sempre veri. Possiamo poi scrivere
delle “relazioni tra relazioni”, nel senso che una è vera se lo sono delle altre, usando la logica del primo ordine. Con un
numero di istruzioni (fatti e regole) finito possiamo rappresentare una quantità di conoscenza illimitata. Inoltre tali
informazioni possono non essere a priori a conoscenza di chi scrive la il programma, il quale si limita solamente a
descrivere il dominio del problema con fatti e regole, ed ad usando solo in un secondo momento la capacità inferenziale
della LP, per derivare informazioni di cui prima non era a conoscenza. Questa caratteristica è il motivo del successo
della LP in intelligenza artificiale.
1.1.1.3. Motore di ricerca su alberi già implementato con possibilità di backtracking
La risoluzione di un goal è per sua natura una ricerca su un albero. In tale ricerca, ad ogni bivio, si tengono memorizzati
i punti di scelta in modo da potere tornare indietro se il ramo preso si dovesse rivelare fallimentare. Quindi non vengono
mai fatti commitment, ma tutte le alternative vengono sempre lasciate aperte, questo permette non solo di tornare
indietro se si arriva ad un fallimento ma anche di trovare tutte le soluzioni se ve ne sono più di una. La ricerca su alberi
è un problema ricorrente, soprattutto in intelligenza artificiale, avendo questa caratteristica gratis incorporata nel motore
inferenziale LP, è ovvio che problemi di questo tipo sono facilmente specificabili usando tale modello.
1.1.1.4. Unificazione
L’unificazione è il meccanismo che sta alla base della LP e che permette la dichiaratività e l’invertibilità dei programmi
ed il backtracking. Permette di usare una semantica diversa per le variabili di quella dell’assegnamento a cui siamo
abituati. Permette di scrivere funzioni e predicati parzialmente specificati, nel senso che una stessa funzione (predicato)
con variabili può rappresentare una serie di funzioni ground. Quale di questo insieme verrà deciso solo durante la
risoluzione. Ad esempio la funzione
f(X,a)
è un modo per indicare tutta un insieme di funzioni ground come le seguenti
f(a,a)
f(b,a)
f(g(a),a)
…
Il secondo uso delle variabili è quello di passaggio dei parametri (si pensi all’interpretazione procedurale).
1.1.2. Caratteristiche secondarie della LP
Per caratteristiche secondarie intendiamo quelle che sono anche del modello funzionale ma non di quello imperativo.
Tutte le caratteristiche esposte sono date in senso negativo, come mancanze, ma lo sono rispetto ai linguaggi imperativi,
quindi non vanno visti come difetti, almeno per il momento, ma come differenze. Infatti una mancanza può risultare
utile perché semplifica certi usi. Discuteremo in seguito quali di esse sono realmente delle limitazioni. Ricordiamo che
comunque la LP è computazionalmente completa, è cioè equivalente alla TM. Vedremo però che in molti casi le TM
sono insufficienti. Discutiamo queste caratteristiche una ad una.
1.1.2.1. Mancanza di tipi
La mancanza di tipi non è una limitazione concettuale ma pratica. In realtà, in nessun linguaggio realmente utilizzabile
possiamo fare a meno dei tipi, ma quello che si intende per tipi in LP è ben diverso da quello che si intende in OOP. In
LP possiamo indicare gli interi con:
0, s(0), s(s(0)), …
una lista con:
[primo, secondo, terzo, quarto]
un albero con
[radice, SINISTRA, DESTRA]
il tipo “persona” con
persona(X).
e così via. Però il significato di tali termini viene dato da chi legge, per il motore inferenziale sono simboli (termini)
qualunque. La differenza è chiara se si pensa all’uguaglianza:
f(a)=f(a).
yes
f(a)=f(b).
no
X=f(a).
yes, X/f(a)
Parte Prima: Differenze tra OOP e LP
LP e OOP
7
Viene controllata solo l’uguaglianza sintattica e se uno dei due termini è una variabile non legata viene data la
condizione di unificazione affinché la relazione sia valida. Con il seguente predicato:
5=5.
yes
abbiamo semplicemente verificato che i due simboli sono uguali senza far riferimento ad alcun valore; difatti se
scriviamo:
2+3=5.
no
la risposta è no perché la stringa “2+3” è diversa dalla stringa “5”. In questo non c’è nulla di strano se non per il fatto
che a certi simboli (come quelli numerici) siamo abituati a dare sempre e solo uno stesso significato. Per usare i numeri
come tali e non come simboli è stato introdotto il predicato “is”:
2+3 is 5.
yes
Questo è un predicato non logico introdotto solo per motivi pragmatici e che lavora come nei sistemi imperativi. In
pratica “l’is” prima valuta il termine di sinistra e quello di destra e poi confronta i due valori associati ai simboli. Se
scriviamo:
2 # 3 is 5.
Il predicato fallisce perché il concetto di tipo è legato a quello di operazioni associate al tipo stesso. Quindi le
operazioni aritmetiche (come quella denotata da “+”) sono consentite tra numeri, mentre “#” non denota nessuna
operazione predefinita tra numeri. In LP per le “operazioni” si usano i predicati ma questi non sono associati a nulla.
Concludendo, in OOP i tipi definiscono dei sottoinsiemi nel dominio D dei significati (un dominio per ogni tipo) e a
ciascuno assegna delle operazioni proprie di quel dominio. In LP non esiste il concetto di tipo come in OOP: per il
motore inferenziale non c’è alcun dominio D, è il programmatore che considera il suo dominio D e che assegna alla lista
[radice, SINISTRA, DESTRA]
il suo “tipo” di albero. Non essendoci tipi non ci possono neanche essere operazioni associate e così, ad esempio, un
predicato (“operazione”) che ha come primo termine una lista a tre argomenti non può fare differenze se tale lista
rappresenta un albero o meno. Non vengono quindi fornite costrutti per lavorare in maniera semplice con dei tipi
predefiniti, ma è il programmatore a farsene carico.
1.1.2.2. Variabili senza assegnamento
La mancanza di assegnamento è una diretta conseguenza della mancanza di stato e di effetti collaterali. In LP le
variabili hanno un significato molto differente da quello a cui siamo abituati in linguaggi imperativi. In
programmazione imperativa quando scriviamo:
tipoX nomeVar;
nomeVar=valy;
nomeVar=<espressione>;
nella prima riga definiamo un simbolo (nomeVar) dicendo che è di tipo tipoX, cioè può assumere, in ogni momento,
uno (e un solo) valore nel domino di tipoX o nessun valore.
La seconda riga valuta il simbolo a destra dell’operatore di assegnamento e lo attribuisce a nomeVar. La terza elimina
il collegamento precedentemente creato e ne stabilisce uno nuovo tra nomeVar e il valore di <espressione> (valz).
sintassi semantica
nomeVar
tipoX
S
D
Parte Prima: Differenze tra OOP e LP
LP e OOP
8
Il concetto di variabile in LP è ben diverso. Innanzitutto non può essere di un tipo, come abbiamo già visto, e quindi il
suo dominio di valori è in pratica tutto D che coincide con S ovvero con l’universo di Herbrand H(P) più il simbolo di
underscore (_) per indicare l’assenza di legame. Ma la differenza principale è nella mancanza dell’operatore di
assegnamento, difatti scrivendo
X=a
la variabile X viene legata alla costante a. Viene legato proprio al simbolo e non al suo valore perché non ne ha, o
meglio, esso coincide con il simbolo stesso. Inoltre questo legame non si può sostituire, ad esempio scrivendo poi
X=b
vi sarebbe un fallimento. “L’assegnamento” è unico e può essere sciolto solo in backtracking. In pratica la variabile in
LP è solo un modo per dare un nome diverso ad un termine. E’ come le variabile nelle funzioni, ad esempio
f(x)=x
2
+3x+2
è un modo compatto per denotare una collezione di espressioni che appartengono ad una stessa classe (quelle la cui
struttura è come quella indicata):
f(0)=0
2
+3*0+2
f(1)=1
2
+3*1+2
f(2)=2
2
+3*2+2
…
Così anche la clausola
f(a, X) :- g(X).
denota una collezione
2
di clausole:
f(a, y) :- g(y).
f(a, f(y)) :- g(f(y)).
f(a, g(a,b)) :- g(g(a,b)).
…
Come per la funzione, in cui la visibilità della variabile x è l’espressione che segue, anche per le clausole la visibilità
della variabile è la clausola stessa. Questo mette in luce il significato denotazionale della variabile logica, in contrasto
con le variabili imperative che sono visibile all’interno di un blocco entro cui possono assumere valori diversi. In
linguaggi imperativi per visibilità si intende la porzione di codice entro cui si può usare la variabile (il suo valore). Si
ricorda che, a differenza delle funzioni, non vi è il passo successivo di valutazione (f(0)=0
2
+3*0+2=2) perché il valore è
la clausola stessa. In LP si possono legare due variabili
X=Y
se poi Y viene legata al termine “a” anche X lo sarà. Se in un linguaggio imperativo scriviamo
x=y
dove x e y sono due variabili dello steso tipo a cui non è stato assegnato ancora alcun valore, si verifica un errore perché
il simbolo y viene valutato per conoscere il suo valore e questo non esiste. Per una semantica simile a quella LP si
devono usare espressamente i puntatori.
1.1.2.3. Mancanza di stato e quindi di effetti collaterali
Questo concetto si ricollega al precedente quando abbiamo detto che i legami delle variabili possono essere eliminati
soltanto in backtracking e non si possono sostituire. Abbiamo dovuto farne a meno per potere fare computazioni con
semplici trasformazioni simboliche. Ad esempio con la clausola
f(a) :- g(a).
vogliamo che durante una derivazione f(a) sia sempre sostituibile con g(a) senza tenere conto di fattori contingenti,
rappresentabili tramite lo stato, che possono fare in modo che tale sostituzione sia lecita in certi casi e non in altri.
Consideriamo l’esempio
pioggia → bagnato(prato) (bagnato(prato) :- pioggia.)
A bagnato(prato) posso sostituire pioggia. Per decidere la verità di questo predicato potrei guardare fuori dalla
finestra ed osservare lo stato del tempo. Questo non è ovviamente esprimibile sintatticamente perché dipende da fattori
contingenti che possono variare nel tempo facendo variare la verità del predicato, mentre in LP si esprimono verità
2
La collezione può anche essere infinita ma è comunque numerabile.
sintassi semantica
nomeVar
valy
valz
S
D
tipoX
Parte Prima: Differenze tra OOP e LP
LP e OOP
9
assolute senza alcuna nozione di tempo: la stessa teoria interrogata con lo stesso goal darà sempre lo stesso risultato.
Questo non è compatibile con lo stato che è invece modificabile nel tempo direttamente dal programma stesso ma anche
e soprattutto da agenti esterni. Difatti quello di creare e modificare uno stato solo internamente è un modo di risolvere
un problema in stile imperativo, ma lo stesso problema è risolubile (almeno in principio, senza tenere conto
dell’efficienza) con metodi puramente trasformazionali (linguaggi logici e funzionali). L’uso più importante dello stato,
che non può essere sostituito con metodi trasformazionali, è quello di tenere traccia degli input esterni in modo di avere
una computazione history dependent. Di questo parleremo ancora molto in seguito.
1.1.2.4. Mancanza di interazione
Un programma LP, come una TM, prende in ingresso un input e fornisce un output, e durante tutto il processo di
computazione taglia fuori il mondo esterno che quindi non può modificare la computazione. Per ogni input si avrà
sempre lo stesso output. Questo aspetto è strettamente legato al precedente poiché attraverso l’interazione il sistema
viene a conoscere una parte dello stato esterno che può modificare la computazione, in genere modificando lo stato
interno. Nessun linguaggio può fare a meno di istruzioni di I/O infatti queste sono presenti in ogni implementazione
Prolog, il problema è che non hanno una semantica logica. Di interazione parleremo ancora molto in seguito.
1.2. Caratteristiche della OOP
Non è certo nostra intenzione dare una trattazione esauriente della OOP perché cioè va oltre i nostri scopi e perché vi
sono molti libri che già lo fanno. Inoltre non vi è ancora un totale accordo su cosa siano gli oggetti, tanto che si parla di
paradigma ad oggetti e nono di modello. Questa tesi vuole anche contribuire a fornire un modello di basso livello degli
oggetti che verrà presentato nella prossima sezione. Si danno comunque per scontati i concetti base che acquisisce
chiunque abbia mai usato un linguaggio OOP. I concetti più importanti verranno comunque brevemente introdotti nel
capitolo “Oggetti in LP”.
1.3. Usi “naturali” della OOP e della LP
Per evidenziare le differenze nella rappresentazione della conoscenza tra linguaggi logici ed ad oggetti consideriamo la
seguente informazione: “Mario e Paolo sono due impiegati. Mario è nato a Roma ed ha 30 anni, Paolo è nato a Bologna
ed ha 35 anni, Mario e Paolo sono colleghi. Antonio è il capo dell’ufficio dove lavorano Mario e Paolo. Gli impiegati
lavorano 40 ore alla settimana e sono tutti iscritti al sindacato. Inoltre Mario possiede una automobile Alfa Romeo”.
Possiamo rappresentare tale conoscenza con un diagramma UML.
Una possibile rappresentazione in Prolog può essere la seguente:
persona(X) :- impiegato(X). (∀X impiegato(X) persona(X) )
iscrittosindacato (X) :- impiegato(X). (∀X impiegato(X) iscrittosindacato(X) )
orelavorative (X,40) :- impiegato(X). (∀X impiegato(X) orelavorative(X,40) )
collega(X, Y) :- collega(Y, X).
impiegato(X) :- capoufficio (X). (∀X capoufficio (X) impiegato(X) )
automobile(X) :- alfaromeo (X). (∀X alfaromeo(X) automobile(X) )
impiegato (mario).
luogo_nascita(mario, roma).
eta(mario, 30).
alfaromeo(bo55364).
possiede(mario, bo55364).
impiegato (paolo).
luogo_nascita(paolo, bologna).
eta(paolo, 35).
collega(mario, paolo).
capoufficio(antonio).
In una rappresentazione ad oggetti avremmo invece definito le classi automobile, alfaromeo, persona,
impiegato e capo come segue:
class automobile {
…
}
Parte Prima: Differenze tra OOP e LP
LP e OOP
10
class alfaromeo extends automobile {
…
}
class persona {
String nome;
String luogo_nascita;
Int eta;
public automobile auto;
public persona(String nome, String luogo_nascita, Int eta) { //
costruttore
this.nome=nome;
this. luogo_nascita= luogo_nascita;
this. eta= eta;
}
} // persona
class impiegato extend persona {
persona[] colleghi;
Boolean iscritto=true;
int orelavorative=40;
int stipendio=500;
public impiegato (String nome, String luogo_nascita, Int eta, persona[]
colleghi) { // costruttore
persona(String nome, String luogo_nascita, Int eta);
this.colleghi=colleghi;
}
} // impiegato
class capo extend impiegato {
int stipendio=1000;
} // capo
e quindi creato 2 istanze di tale classe:
impiegato mario, paolo;
capo antonio;
mario = new impiegato (mario, roma, 30, paolo);
paolo = new impiegato (paolo, bologna, 35 ,mario);
antonio = new capo();
mario.auto=new alfaromeo();
Parte Prima: Differenze tra OOP e LP
LP e OOP
11
L’informazione totale contenuta nei due programmi è la stessa però alcune cose risultano più naturalmente esprimibili
in un modo piuttosto che nell’altro. Nei linguaggi ad oggetti il fuoco è sulle singole entità che vengono descritte in
maniera compatta e unitaria attraverso le classi mentre in Prolog l’accento è sulle relazioni tra le entità. Quindi mentre
risulta naturale usare il predicato “collega”, risulta meno naturale usare un predicato “eta” come relazione tra gli enti
“mario” e “30”. Viceversa mentre è naturale inserire tutte le proprietà delle persone (nome, luogo di nascita, età) entro
una stessa classe, è meno chiaro l’uso di un array di persone per i colleghi perché questa è una proprietà esterna ad una
singola persona che riguarda più persone. Inoltre con tale meccanismo si ha ridondanza di informazione (dentro
l’oggetto “mario” vi è l’informazione che “paolo” è suo collega e viceversa) con problemi di aggiornamento e di
consistenza delle informazioni stesse. Avremmo potuto usare anche un’altra implementazione che racchiude la
relazione “collega” in un oggetto separato ma la questione di fondo rimane: in OOP le relazioni sono sì rappresentabili
ma in maniera meno naturale di quanto avviene in LP.
OOP → entità
LP → relazioni
Si noti che la rappresentazione migliore sarebbe una mista in cui tutte le proprietà di una singola entità vengono
racchiuse entro un oggetto OOP ed esprimere poi le relazioni tra tali oggetti in LP.
1.4. Riepilogo
Sono state presentate le peculiarità e le caratteristiche secondarie delle LP evidenziando le differenze con la OOP:
Peculiarità:
• dichiaratività dei programmi
• invertibilità: uno stesso programma può risolvere più problemi
• possibilità di fare inferenze
• motore di ricerca su alberi già implementato con possibilità di backtracking
• unificazione
Caratteristiche secondarie:
• mancanza di tipi
• variabili senza assegnamento
• mancanza di stato e quindi di effetti collaterali
• mancanza di interazione
In seguito discuteremo quali delle caratteristiche “negative” (mancanze) della LP sono dei limiti effettivi.
Abbiamo poi mostrato come una stessa informazione sia rappresentabile in entrambi i modelli. Nei linguaggi ad oggetti
il fuoco è sulle singole entità che vengono descritte in maniera compatta e unitaria attraverso le classi mentre in Prolog
l’accento è sulle relazioni tra le entità.
OOP → entità
LP → relazioni
persona
nome
luogo
eta
impiegato
colleghi
iscritto=true
stipendio=500
orelavorative=40
capo
stipendio=1000
antonio
mar io
nome=Mario
luogo=Roma
eta=30
colleghi={paolo}
paolo
nome=Paolo
luogo=Bologna
eta=35
colleghi={mario}
automobile
alfaromeo
bo55364
collega collega
Parte Prima: Differenze tra OOP e LP
LP e OOP
12
E’ chiaro che la rappresentazione migliore sarebbe una mista, e questo è il risultato a cui vogliamo arrivare. E’
importante che siano chiare le differenze tra i due strumenti e cosa uno offre in più dell’altro, in vista di una possibile
integrazione. Dobbiamo anche capire quali siano le caratteristiche più importanti della LP e quali quelle di contorno
perché è possibile che in una integrazione LP-OOP si debba arrivare ad un trade-off rinunciando ad alcune in favore di
altre. La caratteristica più importante che distingue la LP, ed a cui non vogliamo assolutamente rinunciare, è la
possibilità di fare inferenze. Mentre è sicuramente secondaria l’invertibilità dei programmi, difatti questa non viene mai
usata nei programmi “reali”.
Parte Prima: Limiti della LP
LP e OOP
13
Capitolo 2
Limiti della LP
Nel capitolo precedente abbiamo visto le differenze tra LP ed OOP. Sappiamo già che tutto quello che si
può fare in LP lo si può (anche se con maggior sforzo) anche in OOP, difatti gli interpreti Prolog sono di
solito implementati in linguaggi OOP come il C++. In questa sezione vedremo che non vale il viceversa,
la LP è un modello di programmazione inferiore alla OOP, non permette cioè di esprimere tutto quello
che è possibile in OOP. Questo aspetto è già stato messo in luce da Wegner [We93], riprenderemo i
concetti esposti in tale articolo e li rielaboreremo in funzione degli sviluppi futuri. E’ importante mettere
chiaramente in luce i limiti e soprattutto le cause di tali limiti per cercare di porvi rimedio in seguito.
Previeni i problemi prima che
sorgano.
Coltiva l’ordine prima che nasca
il disordine.
Lao Tzu, Tao te Ching
2.1. Sintassi e semantica in LP
L’aspetto fondamentale della LP da cui derivano gli altri è il seguente:
la semantica è ridotta alla sintassi.
Tale restrizione è d’obbligo se si vogliono risolutori corretti e soprattutto completi. Questo perché una macchina non
può conoscere il significato dei simboli dato dal programmatore, ma se la semantica è data dalla sintassi può limitarsi a
manipolare simboli dimostrando ciò che è vero indipendentemente dal significato dei simboli stessi. Per il risolutore un
simbolo non denota altro che se stesso, è un puro segno che non rappresenta nulla. Questo è ben diverso, ad esempio,
dall’italiano scritto in cui dietro la stringa “persona” c’è un significato (dato non da regole ma da convenzioni e usi). Di
solito nei programmi LP non si usano stringhe qualsiasi ma nomi significativi, ma significativi solo per chi legge, per la
macchina è la stessa cosa sostituirvi simboli qualunque purché dove compaia un certo termine ne compaia un altro e
sempre lo stesso.
Si può meglio comprendere tale differenza confrontando la definizione di interpretazione con quella di interpretazione
di Herbrand di un programma logico, essendo le interpretazioni ad attribuire la semantica ai programmi.
Definizione 2.1.1 (interpretazione). Dato un linguaggio del primo ordine L=(C, F, P, V)
3
, un’interpretazione per L
definisce un dominio non vuoto D e assegna:
• a ciascun simbolo di costante in C una costante in D;
• a ciascun simbolo di funzione n-ario una funzione F:D
n
→D;
• a ciascun simbolo di predicato n-ario in P una relazione in D
n
, cioè un sottoinsieme in D
n
.
Ci sono quindi due insiemi distinti: quello dei simboli S e quello dei significati (valori) D. In particolare più simboli
potrebbero indicare lo stesso valore.
3
C è l’insieme delle costanti, F quello delle funzioni, P dei predicati e V delle variabili.
S D
sintassi semantica
Parte Prima: Limiti della LP
LP e OOP
14
Si noti che gli elementi del dominio D possono essere qualunque cosa, anche enti reali. In questo caso abbiamo usato
stringhe ma il “9” in S è diverso dal “9” in D: il primo è un disegno il secondo il concetto del numero nove. Lo stesso
vale per “caino”. La confusione nasce dal fatto che per rappresentare i concetti su carta possiamo usare solo dei segni e
non possiamo denotare altrimenti oggetti reali o astratti. In realtà nel dominio D è definita implicitamente un’altra
funzione di interpretazione che collega queste altre stringhe al mondo reale ma tale funzione è nella mente di chi legge.
La definizione di interpretazione data è del tutto generale e nella LP ne viene data una più specifica:
Definizione 2.1.2. (interpretazione di Herbrand). Dato un insieme di formule ben formate P, un’interpretazione di
Herbrand I di P è un’interpretazione tale che:
• il suo dominio di interpretazione è H(P);
• una funzione di interpretazione che associa ciascun simbolo di costante a se stesso;
• se f è un simbolo di funzione n-ario in P, la funzione di interpretazione F: H(P)
n
→H(P) mappa la sequenza di
termini ground (t
1
, … t
n
)∈H(P)
n
nel termine f(t
1
, … t
n
)∈H(P);
• se p è un simbolo di predicato n-ario in P, la funzione di interpretazione gli associa un sottoinsieme di atomi
p(t
1
, … t
n
)∈B(P).
Esiste in pratica un solo dominio essendo quello della semantica coincidente con quello della sintassi, ogni simbolo
indica sempre e solo se stesso, non c’è quindi modo per far corrispondere due stringhe diverse come “caino” e
“fratello(abele)” allo stesso concetto (significato). Non vi è quindi neanche la possibilità di cambiare interpretazione.
In pratica il dominio della semantica non esiste, è solo chi legge che dà dei significati ai simboli. In particolare non vi è
possibilità di cambiare interpretazione; poiché la semantica è data dalla sintassi per cambiare semantica dobbiamo
cambiare programma. Questo permette di computare tramite delle meccaniche trasformazioni di simboli. Ad esempio
consideriamo la seguente teoria:
f(a) :- g(b), f(c), h(a),
f(c).
g(b) :- h(b).
h(a).
h(b).
9
6+3
10-1
caino
f ratello(abele)
squadreDiBasketBolognesi/1
9
caino
virtus
fortitudo
S D
H(P) H(P)
sintassi semantica
H(P) D
sintassi semantica
programmatore
9
6+3
10-1
caino
fratello(abele)
squadreDiBasketBolognesi/1
S
9
6+3
10-1
caino
fratello(abele)
squadreDiBasketBolognesi/1
D=S
Parte Prima: Limiti della LP
LP e OOP
15
Possiamo interpretare ogni riga come una regola di riscrittura: quello che è a sinistra del simbolo “:-“ può essere
sostituito con quello che si trova a sinistra o con la stringa vuota se non vi è nulla. L’input (goal) sia:
f(a).
Secondo la prima regola della teoria questo viene sostituito con
g(b), f(c), h(a).
usando poi la terza regola possiamo sostituire il primo termine:
h(b), f(c), h(a).
le altre sostituzioni sono le seguenti:
f(c), h(a).
h(a).
.
La terminazione con stringa vuota viene considerata come successo altrimenti come fallimento. Si noti che poiché un
programma ha sempre una sola interpretazione invariabile risponderà sempre allo stesso modo agli stessi goal. Questo è
diverso da quanto avviene nella OOP in cui la chiamata ad un metodo può dare risposte diverse in momenti diversi.
Abbiamo detto che la riduzione della semantica alla sintassi è il punto cruciale della LP. Da questo non derivano
solamente i limiti di cui parleremo in seguito, ma anche le peculiarità della LP. Difatti senza tale caratteristica non
sarebbero nemmeno possibili l’unificazione (detta appunto sintattica), l’invertibilità, la dichiaratività che sono i punti di
forza della LP che la distinguono dagli altri modelli. All’assenza del dominio semantico è da attribuire la mancanza dei
tipi e delle variabili con assegnamento, ma questi non sono dei limiti. Vedremo invece che la mancanza di stato e di
interazione sono dei veri limiti. E’ chiaro anche che
nel momento in cui tentiamo di superare queste mancanze della LP introducendo lo stato e
l’interazione perdiamo anche alcune peculiarità.
Dovremo fare quindi un bilancio delle nuove funzionalità che si acquisiscono e di quelle che si perdono e valutare se
l’estensione può risultare vantaggiosa.
2.2. I veri limiti della LP
In questa sezione cercheremo di far capire perché l’assenza di stato e di interazione sono effettivamente dei limiti per la
LP. La trattazione sarà piuttosto informale ed intuitiva facendo appello ad idee che chiunque abbia mai avuto a che fare
con la programmazione logica ed ad oggetti ha avuto modo di conoscere. Nella seconda parte verranno formalizzati tali
concetti e si capirà meglio perché l’interazione e lo stato aggiungono una dimensione alla elaborazione.
2.2.1 Mancanza di stato
Sul fatto che la mancanza di stato sia veramente una mancanza certamente non saranno tutti d’accordo (“per computare
non abbiamo bisogno di stato”). Cercheremo ora di vedere in maniera intuitiva perché questa sia realmente una pecca
della LP mentre nella seconda parte approfondiremo tale questione con più precisione e daremo un significato più
preciso alla frase sopra citata.
Consideriamo il seguente esempio:
contatore(0).
incrementa :- contatore(X), retract(contatore(X)), assert(contatore(s(X))).
valore(X) :- contatore(X).
A tale programma poniamo i seguenti goal:
:- value(Y).
yes, Y/0
:- incrementa.
yes
:- value(Y).
yes, Y/s(0)
Lo stesso predicato (value(Y)) in interrogazioni diverse ha dato risposte diverse, cosa che è “illogica”. Questo perché
allo stesso programma corrispondono più teorie logiche diverse non equivalenti. Nell’esempio il goal value(Y) è stato
sottoposto la prima volta alla teoria:
contatore(0).
incrementa :- contatore(X), retract(contatore(X)), assert(contatore(s(X))).
valore(X) :- contatore(X).
e la seconda volta alla teoria:
contatore(s(0)).
incrementa :- contatore(X), retract(contatore(X)), assert(contatore(s(X))).
valore(X) :- contatore(X).
Consideriamo un altro esempio:
lunghezza_lista(LISTA, N) :- assert(contatore(0)), lunghezza_lista(LISTA), contatore(N),
retract(contatore(_)).
Parte Prima: Limiti della LP
LP e OOP
16
lunghezza_lista([]).
lunghezza_lista([HEAD|TAIL]) :- retract(contatore(X)), assert(contatore(s(X))),
lunghezza_lista(TAIL).
In questo caso l’uso dello stato è “interno” e lo stesso goal (ad esempio lunghezza_lista([a, b, c], N)) sottoposto
alla teoria in momenti diversi darà sempre lo stesso risultato. A differenza del primo esempio, irrisolubile in LP
classica, in questo caso la soluzione logica è molto più semplice e elegante:
lunghezza_lista([], 0)
lunghezza_lista([HEAD|TAIL], N) :- lunghezza_lista(TAIL, M), N=s(M).
Oppure nella versione tail recursive:
lunghezza_lista(LISTA, N) :- lunghezza_lista(LISTA, 0, N).
lunghezza_lista([], N, N).
lunghezza_lista([HEAD|TAIL]), ACC, N) :- ACC1=s(ACC), lunghezza_lista(TAIL, ACC1, N).
Nella versione tail recursive, nell’ultima clausola, abbiamo usato delle variabili accumulatore per tenere lo stato della
computazione, ma poiché non abbiamo voluto usare effetti collaterali abbiamo avuto bisogno di accumulatori (ACC e
ACC1): uno per il vecchio stato e uno per il nuovo. In entrambi gli esempi abbiamo parlato di stato ma con diverso
significato. Nel primo caso lo stato era esterno nel senso che serviva per collegare diverse computazioni
(interrogazioni), ogni richiesta di incrementa è asincrona ed ha l’effetto di influenzare le computazione future
(history dependent). Non esistono soluzioni a tale problema nella logica. Nel secondo esempio (in tutte e due le
versioni) lo stato era interno nel senso che esso non è permanente tra computazioni successive, quindi goal passati non
influenzano i futuri (history independent) e ogni goal darà sempre lo stesso risultato. Per ogni goal si sa già di quanto
deve essere incrementato il contatore. Su questi concetti torneremo in seguito. La prima soluzione del secondo esempio
è assolutamente da evitare poiché se si vuole risolvere un problema in stile imperativo tanto vale usare un linguaggio di
tale genere.
Come si sarà intuito si sono due modi diversi di usare lo stato: il primo serve per collegare le singole computazioni
mentre il secondo per effettuare una singola computazione. In entrambi i casi l’introduzione di effetti collaterali ci fa
uscire dal modello logico. Mentre il secondo uso si può evitare come abbiamo fatto nell’esempio ed anzi un suo uso in
LP è inutile (se non dannoso), nel primo caso non possiamo farne a meno. Notare che i due usi sono su due piani
diversi, tanto che sarebbe meglio usare termini diversi per evitare la confusione che nasce appunto dal parlare di cose
diverse con lo stesso termine.
usi dello stato:
esterno → collega le singole computazioni → non presente in LP
interno → collega i passi della computazione → non serve in LP
Accenniamo anche al fatto che lo stato può essere usato anche come meccanismo di comunicazione asincrona tra più
sistemi diversi. Difatti la risposta che riceve un utente è funzione dello stato che a sua volta è funzione degli ingressi
passati che possono essere stati prodotti da utenti diversi. Con lo stato non c’è bisogno che due entità siano in collegate
direttamente nello stesso momento per comunicare. Il mittente può lasciare il messaggio ed il ricevente prenderlo in un
secondo momento. Il meccanismo è simile a quello ben conosciuto di comunicazione tramite tuple.
2.2.2. Mancanza di interazione
Sul fatto che l’interazione sia un limite nessuno ha dubbi, difatti nessun programma che non sia solo un esercizio può
fare a meno di istruzioni di I/O. L’introduzione di questi predicati fa però perdere la logica del sistema, ad esempio i
programmi non sono più invertibili. Non a tutti è però chiaro se l’introduzione dei predicati di I/O è solo una necessità
pratica oppure una caratteristica indispensabile non rappresentabile in logica. A questa domanda ha risposto Wegner
[We97a], il quale ha mostrato che l’interazione è una diversa dimensione che si aggiunge alla elaborazione e che quindi
non è riconducibile a questa. Un programma LP, come una TM, è una macchina che tra un input ed un output taglia
fuori il mondo esterno ed è quindi completamente indipendente da esso. Un uso interattivo è invece più espressivo
perché riceve più informazioni dall’ambiente esterno e soprattutto informazioni che in genere non sono disponibili tutte
assieme nel momento in cui si riceve il primo input perché alcune saranno funzioni di output che fornirà
successivamente la macchina.
Un esempio classico che descrive bene questa idea è quello della automobile automatica che deve andare da un punto A
ad un punto B. Se la pianta della città è conosciuta e non ci sono altre macchine il problema è risolvibile con una TM
perché si conoscono tutte le informazioni a riguardo e queste sono immutabili. Se però non abbiamo la carta stradale
oppure ci sono anche altre macchine che circolano l’approccio precedente non è più praticabile perché ci mancano
informazioni e nel caso di presenza di altre macchine non solo mancano informazioni ma queste sono anche variabili. Il
problema è però risolvibile con un approccio interattivo: non conosciamo lo stato globale ma solo una parte, quindi
prendiamo decisioni compatibili con l’informazione correntemente disponibile, l’output corrispondente in genere
influenzerà anche l’input successivo che ci fornirà altre informazioni non disponibili in precedenza, quindi si itera il
procedimento. Il processo interattivo può anche essere illimitato e non portarci mai alla soluzione voluta ma, a
differenza del comportamento non interattivo, è comunque percorribile. Si noti che in alcuni problemi non solo
l’informazione è incompleta come nel caso della mancanza di una carta stradale, ma è anche non formalizzabile e quindi
Parte Prima: Limiti della LP
LP e OOP
17
non può essere racchiusa in una macchina come nel caso della presenza di altre automobili. Si faccia però attenzione
che la non formalizzabilità è esterna alla macchina.
In molti casi l’interazione è legata allo stato
4
, ed in particolare alla sua modifica. Di solito infatti, tramite l’interazione,
lo stato interno viene modificato in modo da rappresentare quello esterno, o meglio, quella parte di che viene trasmessa
tramite l’input. Si hanno così computazioni history dependent in cui il risultato di un input dipende anche dagli input
precedenti la cui informazione è racchiusa nello stato. Se alcuni degli input precedenti derivano da altre entità ecco che
l’insieme stato-interazione permette la comunicazione asincrona di cui abbiamo accennato nel punto precedente e di cui
parleremo ancora in seguito.
2.3. Il Prolog è un linguaggio logico?
A conferma che l’interazione e lo stato sono effettivamente dei limiti vi il fatto che tutte le implementazioni di linguaggi
LP introducono costrutti di I/O (ad esempio read e write) e di modifica permanente (ad esempio assert e retract). Come
sappiamo questi sono dei meccanismi non logici e quindi i programmi che ne fanno uso (la totalità se si escludono e
semplici programmi di esempio di presentazione della LP) perdono alcune delle peculiarità proprie della LP che ne
fanno un linguaggio così particolare. Difatti tutti sappiamo bene che un programma Prolog che “serve a qualcosa” non è
invertibile. E’ allora spontaneo chiedersi se sia ancora corretto parlare di programmazione logica. Il dubbio nasce dal
fatto che spesso si crede che i programmi perdono l’invertibilità non a causa di limiti intrinseci della LP, ma a causa del
suo uso pratico. Per motivi di efficienza si preferisce, ad esempio, usare i numeri ed il predicato “is” anche se
teoricamente potremmo farne a meno. L’uso di un semplice “is” è da sola causa di perdita di invertibilità. Il problema è
che spesso non si ha chiaro il confine tra la perdita di “logicità” dovuta a limiti intrinseci della LP e quella dovuta a
limiti pragmatici.
Per mettere chiarezza in tale campo proponiamo la seguente classificazione dei linguaggi “logici”.
• linguaggi logici, quei linguaggi con non fanno uso di nessun predicato extra logico, non usano termini “speciali”
come i numeri e sono corretti e completi. Non esistono interpreti commerciali per tali linguaggi che sono (erano) di
interesse solo a livello accademico. Con LP ci riferiremo a tali linguaggi.
• linguaggi basati sulla logica, per avere uno strumento che sia usabile, sia dal punto di vista pragmatico sia da
quello dell’efficienza, si è dovuto rinunciare alle caratteristiche della precedente categoria. Sono non completi a
causa della ricerca in profondità secondo l’ordine testuale; esiste il termine numerico e i relativi predicati (“l’is” in
particolare); ci sono predicati metalogici e alcuni extra-logici ma non esiste il concetto di stato e di interazione con
l’ambiente esterno.
• linguaggi orientati alla logica, ai precedenti aggiungono il concetto di stato e/o di interazione introducendo
predicati come read/1 e write/1, andando quindi oltre la TM. Il Prolog e la maggior parte di tutti i suoi dialetti
appartengono a questa classe.
• linguaggi ispirati alla logica, quelli che non appartengono alle classi precedenti poiché aggiungono ulteriori nuovi
costrutti. Comprende una vasta classe di linguaggi, molti dei quali sono stati solo proposti ma non realizzati, ma in
pratica anche tutti i linguaggi commerciali che nelle prime versioni si potevano considerare della terza classe ma
poi, nelle versioni successive, hanno aggiunto nuovi costrutti non logici per aumentare l’espressività del
linguaggio. In particolare linguaggi che usano altri tipi di logica o che permettono l’uso di oggetti C++ o Java.
La totalità dei “linguaggi logici” appartiene alle ultime due categorie, ma lo stato e l’interazione non hanno una chiara
semantica logica, si possono allora chiamare logici? Uno degli obbiettivi di questo lavoro è quello di introdurre le
caratteristiche citate nella LP rimanendo però in ambito logico. Discuteremo di questo nella seconda parte.
2.4. Riepilogo
Si è mostrato che la causa di tutti i limiti (e delle peculiarità) della LP è il fatto che la semantica è ridotta alla sintassi.
Questo non è imposto dalla logica, in cui l’interpretazione prevede il dominio semantico D, ma è dovuto alla
implementazione della LP che usa un sottocaso di interpretazione (quella di Herbrand). Abbiamo poi mostrato che i veri
limiti della LP sono due: stato e interazione. Non tutti sono disposto a considerare la mancanza di stato come un limite
della LP, ma questo è dovuto al fatto che il termine “stato” ha (almeno) due significati distinti.
usi dello stato:
esterno → collega le singole computazioni → non presente in LP
interno → collega i passi della computazione → non serve in LP
L’interazione invece permette di usare, durante l’elaborazione, informazioni esterne non disponibili all’inizio. So pensi
al classico esempio dell’automobile che deve andare da A a B.
Infine abbiamo proposto la seguente classificazione dei linguaggi “logici”
• linguaggi logici,
• linguaggi basati sulla logica,
• linguaggi orientati alla logica,
4
Vedremo meglio questo aspetto in seguito; per il momento facciamo notare che, anche se in certi casi vi è uno stretto legame tra stato e interazione,
non è corretto identificare le macchine con stato con le macchine interattive.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.