Appunti Uni

C3. Prolog Fast Track

5 minuti

C3. Prolog Fast Track

Slide: file:///C:/UNI/Magistrale/ISE/C3%20%E2%80%93%20Prolog%20Fast%20Track.pdf

Indice

Obiettivo del Modulo

Definizione

Prolog e un linguaggio di programmazione logica in cui un programma e una teoria di clausole di Horn e l’esecuzione consiste nel provare query tramite risoluzione e unificazione.

Il modulo e un percorso rapido sui concetti necessari per capire ragionamento simbolico, regole, unificazione, backtracking e rappresentazione dichiarativa della conoscenza.

In pratica: in Prolog non si descrive principalmente una sequenza di passi, ma un insieme di relazioni. Poi si fanno domande al sistema, che cerca sostituzioni di variabili capaci di rendere vere le query.

Basi di Prolog

Termini atomi e clausole

Definizione

Un termine Prolog e costruito da variabili e funtori; un atomo applica un predicato a termini; una clausola esprime un fatto, una regola o una query.

Regole sintattiche essenziali:

  • Le variabili iniziano con lettera maiuscola o underscore, per esempio X, Child, _Tmp.
  • _ da solo e variabile anonima: significa “non mi interessa il valore”.
  • I funtori e le costanti iniziano con minuscola, per esempio term, joey, f(X).
  • Un atomo ha forma predicate(t1, ..., tn).

Tipi di clausole:

father(joey,luca).                  % fatto
grandparent(G,N) :- parent(G,P), parent(P,N).  % regola
?- parent(joey,Child).              % query

Note

La stessa forma sintattica, come parent(lino,joey), puo essere vista come termine o come atomo a seconda del contesto. Questo abilita anche meta-programmazione.

Esecuzione e backtracking

Definizione

L’esecuzione Prolog cerca una sostituzione delle variabili che renda vera una query rispetto al programma.

Prolog usa SLD resolution con una strategia precisa:

  • i goal sono risolti da sinistra a destra;
  • le clausole sono provate dall’alto verso il basso;
  • la ricerca e depth-first;
  • in caso di fallimento, Prolog torna all’ultimo choice point disponibile.

In pratica: l’ordine delle clausole e dei sottogoal conta. Anche se la logica dichiarativa sembra simmetrica, l’esecuzione concreta puo terminare, non terminare o produrre risposte in ordine diverso.

Warning

Prolog e dichiarativo, ma non e magicamente indipendente dall’ordine. Con ricorsione e liste, mettere prima il caso base e spesso essenziale per terminare.

Rappresentazione della Conoscenza

Fatti e query

Definizione

Un fatto rappresenta una proposizione vera nel dominio; una query chiede se una proposizione e conseguenza del programma.

Esempio di knowledge base:

parent(joey,luca).
parent(joey,simone).
parent(lino,joey).
parent(mirella,joey).

Query possibili:

?- parent(joey,luca).
?- parent(joey,Child).
?- parent(Parent,joey).
?- parent(Grandparent,Parent), parent(Parent,Child).

In pratica: non ci sono parametri input/output fissati. La stessa relazione puo essere interrogata in direzioni diverse, grazie all’unificazione.

Regole

Definizione

Una regola Prolog definisce una relazione in termini di altre relazioni.

Esempio per i nonni:

grandparent(G,N) :-
    parent(G,P),
    parent(P,N).

Questa regola e universale: vale per ogni sostituzione di G, P e N che renda veri i due sotto-goal nel corpo.

Esempio per fratelli:

sibling(S1,S2) :-
    parent(P,S1),
    parent(P,S2),
    S1 \= S2.

\=/2 e un predicato built-in che ha successo quando i due termini non unificano.

Unificazione

Definizione

L’unificazione e il processo che rende due termini uguali trovando una sostituzione per le variabili.

Esempio:

parent(joey,Child)

puo unificare con parent(joey,luca) producendo la sostituzione Child = luca.

Lettura operativa

Una query non e solo una domanda vero/falso. Se contiene variabili, Prolog puo generare risposte alternative tramite backtracking.

Numeri e Ricorsione

Numeri naturali alla Peano

Definizione

I numeri naturali alla Peano rappresentano i naturali usando uno zero e un costruttore di successore.

In programmazione logica pura, simboli come 3 e + non hanno significato speciale. Possiamo quindi rappresentare i naturali con:

  • z per zero;
  • s(N) per il successore di N.

Esempi:

z          % 0
s(z)      % 1
s(s(z))   % 2

Rappresentazione ricorsiva:

nat(z).
nat(s(N)) :- nat(N).

In pratica: una sola regola finita rappresenta un insieme infinito di numeri. Questo mostra la forza dell’approccio intensionale rispetto a elencare infiniti fatti.

Somma come relazione

Definizione

In Prolog la somma puo essere rappresentata come relazione ternaria sum(X,Y,Z), cioe X + Y = Z.

Esempio:

sum(z, N, N).
sum(s(M), N, s(P)) :-
    sum(M, N, P).

Questa definizione non ha parametri input/output prefissati. Si puo chiedere il risultato di una somma, ma anche generare valori che soddisfano un’equazione.

Warning

La rappresentazione con s(s(...)) e molto espressiva dal punto di vista logico, ma poco pratica per gli esseri umani. Per questo Prolog reale include anche aritmetica built-in, come X is 1 + 3.

Liste

Notazione delle liste

Definizione

Una lista Prolog e una struttura ricorsiva formata da lista vuota [] e costruttore testa-coda [H|T].

Notazioni equivalenti:

[a,b,c]
[a|[b,c]]

In [H|T], H e la testa e T e la coda. L’unificazione permette di decomporre una lista:

[a,b,c] = [H|T]

produce H = a e T = [b,c].

member/2

Definizione

member/2 verifica o genera appartenenza: member(X,List) significa che X e elemento di List.

Definizione tipica:

member(X,[X|_]).
member(X,[_|T]) :-
    member(X,T).

Il primo caso dice che un elemento e membro se coincide con la testa. Il secondo caso scarta la testa e cerca nella coda.

Query utili:

?- member(b,[a,b,c]).
?- member(X,[a,b,c]).
?- member(blue(X),[red(a),blue(b),red(c),blue(d)]).

In pratica: member/2 puo controllare appartenenza, enumerare elementi o generare liste compatibili con una richiesta. Questa flessibilita deriva da unificazione e backtracking.

Prossimi Argomenti

Continueremo con:

Vista grafico

Link entranti