Il
Prolog
(contrazione del
francese
PRO
grammation en
LOG
ique
) e un
linguaggio di programmazione
che adotta il
paradigma
di
programmazione logica
.
E stato ideato da
Robert Kowalski
(aspetto teorico),
Marten Van Emdem
(dimostrazione sperimentale) e implementato da
Alain Colmerauer
negli
anni settanta
, e costituisce un tentativo di costruire un linguaggio di programmazione che consenta l'espressione del problema in forma logica, invece che in forma di un
algoritmo
di soluzione eseguibile dalla macchina. L'attuale implementazione di Prolog e dovuta in gran parte all'efficiente codifica di
David H.D. Warren
, implementata tramite la sua
Warren Abstract Machine
(
1983
).
Il Prolog e impiegato in molti programmi di
intelligenza artificiale
; la sintassi e la semantica sono molto semplici e chiare, in quanto lo scopo per cui venne ideato era quello di fornire uno strumento di lavoro a linguisti privi di conoscenze informatiche.
Il Prolog si basa sul
calcolo dei predicati
(precisamente il calcolo di predicati del primo ordine); tuttavia la sintassi e limitata a formule dette
clausole di Horn
che sono disgiunzioni di
letterali
del primo ordine, quantificate universalmente, con al piu un letterale positivo.
L'esecuzione di un
programma
Prolog e comparabile alla dimostrazione di un
teorema
mediante la
regola di inferenza
detta risoluzione (introdotta da
Robinson
nel
1965
). I concetti fondamentali sono l'unificazione, la
ricorsione
in coda e il
backtracking
.
Molti linguaggi, come
Datalog
o
AnsProlog
, sono basati su Prolog.
Nel Prolog, la logica del programma e espressa sotto forma di relazioni, e le attivita di calcolo vengono attivate da un'interrogazione relativa a tali relazioni.
L'elemento generico del Prolog si chiama
termine
. I termini possono essere
costanti
(
atomi
o
numeri
),
variabili
o
termini composti
.
- Un
atomo
e un nome generico senza significato intrinseco, es.:
x
,
blu
,
'Taco'
,
'questo signore'
.
- Un
numero
puo essere intero o decimale.
- Una
variabile
e indicata per mezzo di una stringa di lettere, numeri e underscore (_) che comincia con una maiuscola o un trattino basso.
- Un
termine composto
e formato da un atomo detto "funtore" e da uno o piu argomenti - anch'essi termini - scritti tra parentesi e separati da virgole, p.es.
data(27,'marzo',1980)
anno_modello_auto('Mazda','cx 5',1986)
e
'Amici'(zelda,[tom,jim])
.
Casi speciali di termini composti:
- Una
lista
e una collezione ordinata di termini, separati da virgole; viene indicata per mezzo di parentesi quadre; e ammessa la lista vuota
[]
. Esempi:
[1,2,3]
e
[rosso,verde,blu]
.
- Una
stringa
e una sequenza di caratteri delimitata da doppi apici ("), p.es.
"essere o non essere"
.
Una
regola
ha la forma:
che si legge: "Testa e vera se Corpo e vero." (Si noti che la regola termina con un punto.)
Un singolo termine (anche composto), senza il segno
:-
, viene chiamato
fatto
. I fatti equivalgono a regole senza corpo, che sono considerate automaticamente vere. Un esempio di fatto e:
Al di la dell'uso strettamente previsto dalla teoria, il Prolog offre anche dei predicati speciali che servono per input/output e altre attivita accessorie. P.es.
write/1
visualizza un termine sullo schermo.
Il seguente esempio stampa il testo "
Hello world
".
?-
write
(
'Hello World'
),
nl
.
La potenza di Prolog non risiede comunque nella sua gestione dell'input/output, quanto nella possibilita di rappresentare semplicemente concetti complessi, ad esempio algoritmi
combinatori
. Ecco un programma che calcola tutte le possibili permutazioni di una parola data come lista di caratteri:
permutation
([],[]).
permutation
(
Xs
,[
Z
|
Zs
])
:-
select
(
Z
,
Xs
,
Ys
),
permutation
(
Ys
,
Zs
).
select
(
X
,[
X
|
Xs
],
Xs
).
select
(
Y
,[
X
|
Xs
],[
X
|
Ys
])
:-
select
(
Y
,
Xs
,
Ys
).
In Prolog e semplice scrivere interpreti e compilatori. Ad esempio, un meta-interprete di Prolog (cioe un interprete Prolog scritto in Prolog) e costituito da solo 3 linee di codice:
vanilla
(
true
).
vanilla
((
A
,
B
)):-
vanilla
(
A
),
vanilla
(
B
).
vanilla
(
X
):-
X
\==true
,
clause
(
X
,
B
),
vanilla
(
B
).
- Le basi logiche del Prolog
(
JPG
), in
LIST
, anno 5, n. 8/9, Roma, EDICOMP, settembre/ottobre 1987, pp. 28-30,
OCLC
955780660
.
- Il Prolog strumento principe
, in
Intelligenza Artificiale
, n. 1, Milano, Arcadia, 1988, pp. 8-12.
- (
EN
) Patrick Blackburn, Johan Bos, Kristina Striegnitz,
Learn Prolog Now!
Archiviato
il 26 agosto 2007 in
Internet Archive
.
, College Publications, 2006,
ISBN 1-904987-17-6
- (
EN
) J. A. Robinson,
A Machine-Oriented Logic Based on the Resolution Principle
, in
Journal of the Association for Computing Machinery
, 12(1), gennaio 1965.