Predicati Predefiniti

Operazioni su Termini e Strutture

Supponiamo di voler contare quanti atomi sono presenti in una lista. Potremmo scrivere un predicato

conta1(Atomo,Lista,N)

definito in questo modo:

conta1(_,[],0).
conta1(Atomo,[Atomo|Resto],N):-
  !,
  conta1(Atomo,Resto,N1),
  N is N1 + 1.
conta1(Atomo,[_|Resto],N):-
  conta1(Atomo,Resto,N).

Sottoponiamo all'interprete Prolog la domanda ?- conta1(a,[a,b,c,a,b]) il Prolog risponderà

N=2
Yes

tuttavia se facciamo la domanda ?- conta1(a,[a,X,Y,a,Z]) il prolog risponderà

N=5
Yes

Infatti le variabili X,Y,Z possono venire istanziate all'atomo a e vengono contate dalla seconda clausola di conta1. Se vogliamo ovviare a questo inconveniente dobbiamo controllare che l'elemento della lista sia effettivamente un atomo mediante il predicato predefinito atom(X) La nuova versione di conta sarà pertanto:

conta2(_,[],0).
conta2(Atomo,[Primo|Resto],N):-
  atom(Primo),
  Primo=Atomo, 
  !,
  conta2(Atomo,Resto,N1),
  N is N1 + 1.
conta2(Atomo,[_|Resto],N):-
  conta2(Atomo,Resto,N).

In questo caso prima controlliamo che l'elemento in testa alla lista sia un atomo e se coincide con l'atomo cercato lo contiamo. Ora se facciamo la domanda ?- conta2(a,[a,X,Y,a,Z]) il prolog risponderà

N=2
Yes

Confrontate il comportamento di conta1 e conta2.

%file: predefiniti/contaatomi.pl
%conta gli atomi in una lista
% lista vuota 0 atomi
conta1(_,[],0).
% Atomo e testa della lista coincidono
% conta l' atomo e fa una ricorsione
conta1(Atomo,[Atomo|Resto],N):-
  !,  
  conta1(Atomo,Resto,N1),
  N is N1 + 1.
% Atomo e testa della lista non coincidono
% fai la ricorsione senza contare
conta1(Atomo,[_|Resto],N):-
  conta1(Atomo,Resto,N).

% ?- conta1(a,[a,b,c,a,b],N)
% ?- conta1(a,[a,X,Y,a,Z],N)

conta2(_,[],0).
conta2(Atomo,[Primo|Resto],N):-
% Primo e' un atomo, fallisce altrimenti
  atom(Primo),
% Primo concide con Atomo, contalo!
  Primo=Atomo, 
  !,
  conta2(Atomo,Resto,N1),
  N is N1 + 1.
conta2(Atomo,[_|Resto],N):-
  conta2(Atomo,Resto,N).

% ?- conta2(a,[a,b,c,a,b])
% ?- conta2(a,[a,X,Y,a,Z])

Esercizio: tenendo presente che, come atom(X) controlla che X sia un atomo, possiamo controllare con integer(X) che X sia un intero e con var(X) che X sia una variabile scrivere un predicato conta_tutto(Lista,Atomi,Interi,Variabili) che conti quanti atomi, quanti interi e quante variabili ci sono nella lista L. Consideriamo ora il predicato membro visto in precedenza.

membro(X,[X|_]).
membro(X,[_|C]) :- membro(X,C).

e supponiamo do fare questa domanda: membro(a,[b,c,Z,d,e]) La risposta dell'interprete sarà Yes perchè, quando viene utilizzata la prima clausola, la variabile Z viene istanziata al valore a. Se non desideriamo che questo avvenda possiamo modificare la definizione di membro in questo modo:

membro_letterale(X,[Y|_]) :- X==Y.
membro_letterale(X,[_|C]) :- membro_letterale(X,C).

In questo caso il goal membro_letterale(a,[b,c,Z,d,e]) non avrà soluzioni. Confrontate, sottoponendo opportuni goal all'interprete Prolog, il comportamento di membro e dimembro_letterale .

%file: predefiniti/membrolett.pl
%  membro_letterale(X,L) 
%  controlla se X compare 
%  in modo 'letterale' nella lista L
%  usa il predicato predefinito "=="

membro_letterale(X,[Y|_]):-
  X==Y.
membro_letterale(X,[_|C]) :-
  membro_letterale(X,C).

% la definizione usuale di membro
membro(X,[Y|_]) :- X==Y.
membro(X,[_|C]) :- membro(X,C).

% ?- membro(a,[b,c,Z,d,e])
% ?- membro_letterale(a,[b,c,Z,d,e])
% ?- membro_letterale(x,[Y,f(z),X].
% ?- membro_letterale(x,[x,f(x),X].
% ?- membro_letterale(f(x),[x,f(z),X].
% ?- membro_letterale(f(x),[x,f(x),X].
% ?- membro_letterale(f(X),[x,f(Y),X].
% ?- membro_letterale(f(X),[x,f(X),X].

Decomposizione di atomi

Per decomporre un atomo in una lista di caratteri (o meglio dei loro codici ASCII), o per comporre un atomo da una lista di codici di caratteri, si può usare il predicato name(Atomo,Lista) Una possibile applicazione è quella di sapere se un atomo ha un certo prefisso. Al esempio gli studenti del corso di Diploma hanno un login name tipo dia241 mentre quelli del corso di Laurea hanno un login name tipo lie241. Possiamo distinguerli usando in predicato prefisso(Prefix,Atom). che dovra rispondere affermativamente ai due goal

?- prefisso(dia,dia241).
?- prefisso(lie,lie241).

Possiamo scrivere il predicato che ci interessa in questo modo:

prefisso(Prefix,Atom):-
  name(Prefix,Plist),
  name(Atom,Alist),
  conc(Plist,_,Alist).

prima scomponiamo con name Prefix in una lista di caratteri Plist, e analogamente facciamo per Atom ottenedo Alist. Poi con il predicato conc controlliamo che i caratteri di Plist siano quelli iniziali di Alist.

%file: predefiniti/atomprefix.pl

%  prefisso(Prefix,Atomo)
% controlla che Prefix sia un prefisso di Atomo

prefisso(Prefix,Atom):-
  % scompone Prefix
  name(Prefix,Plist), 
  % scompone Atom 
  name(Atom,Alist),
  % Plist e' la parte iniziale di Alist   
  conc(Plist,_,Alist). 

% concatena due liste 
conc([],L,L).
conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).
/*
?- prefisso(dia,dia241).
?- prefisso(lie,lie241).
*/

Esercizio: scrivere, sulla falsa riga del predicato prefisso, un predicato scomponi che estragga la parte dell'atomo che segue il prefisso es:

        ?- scomponi(dia,dia116,N).
        N=116
        Yes

Scomporre strutture

Possiamo scomporre strutture usando il predicato ..= Vogliamo per esempio sapere quanti atomi ci sono in una struttura come:

  sin(x)+y*sin(a*exp(b))/arctan(z/t)

Vogliamo quindi scrivere un predicato conta(Struttura,N) done N sia il numero di atomi, numeri o variabili presenti nella struttura (calcolando anche le duplicazioni). Le regole per scrivere il predicato conta sono

se è un atomo o una intero o una variabiel il conteggio eè 1
altrimenti sarà una struttura e la possiamo scomporre in una lista contenente funtore e argomenti con il predicato =... La lista degli argomenti viene passata al predicato contalista che provvede al conteggio nei singoli argomenti (in modo ricorsivo) e a calcolare il risultato totale.

Le regole per contalista sono

in una lista vuota il conteggio è 0.
altrimenti il conteggio si ottiene sommando il conteggio relativo al primo elemento e quello relativo al resto degli elementi.

%file containstruct.pl
/*
conta quanti atomi, numeri e variabili
sono presenti in una struttura
(contando anche le duplicazioni) 
*/

/* e' un atomo  */
conta(X,1) :- atom(X), !.
/* e' un numero */
conta(X,1) :- integer(X), !.
/* e' una variabile  */
conta(X,1) :- var(X), !.

/* e' una struttura viene divisa
   in funtore e lista di argomenti */
conta(Struct,N) :- 
  Struct =.. [_Func|ListaArgs],
/* conta nella lista degli argomenti */
  contalista(ListaArgs,N).

/* conta quanti atomi o numeri sono 
   presenti nel primo elemento
   e li somma a quelli presenti 
   nel resto della lista */

contalista([Primo|Altri],N):-
/* nell primo elemento */
  conta(Primo,NPrimo),
/* nel resto della lista */
  contalista(Altri,NAltri), 
/* il risultato e' la somma */
  N is NPrimo + NAltri. 
contalista([],0).

/*
?- conta(f(g(x,y),h(z)),N).
?- conta(sin(x)+y*sin(a*exp(b))/arctan(z/t),N)
*/

Operazioni su clausole

Supponiamo di voler tradurre una lista di parole italiane nelle corrispondenti parole inglesi. Un insieme di fatti ci dice come tradurre una singola parola:

parola('Maria','Mary').
parola('Giovanni','John').
parola(era,was).
parola(una,a).
parola(uno,a)
.....
.....

Ora vogliamo scrivere un predicato traduzione che prenda in ingresso una lista di parole italiane e produca in uscita una lista con le corrispondenti parole inglesi. ?- traduzione(['Giovanni',era,uno,studente],L). deve dare come risposta L=['John',was,a,student]. traduzione può essere scritto in questo modo:

traduzione([],[]).
traduzione([X|C],[X1|C1]):-
  parola(X,X1),
  traduzione(C,C1).

La prima clausola ci dice che per una lista vuota non dobbiamo fare nulla. La seconda, ci dice di prendere la traduzione della parola in testa alla lista, e inserirla nel risultato, davanti alla traduzione del resto della lista.

%file predefiniti/traduci.pl

% come si traducono le parole.
parola('Maria','Mary').
parola('Giovanni','John').
parola(era,was).
parola(una,a).
parola(uno,a).
parola(studente,student).
parola(studentessa,student).
% qualsiasi parola non prevista
parola(_,?).

traduzione([],[]).
traduzione([X|C],[X1|C1]):-
  parola(X,X1),
  traduzione(C,C1).

% ?- traduzione(['Giovanni',era,uno,studente]).
% ?- traduzione(['Maria',era,una,studentessa]).
% ?- traduzione([lui,era,uno,studente]).

Possiamo, tuttavia, affrontare il problema in termini più generali. Abbiamo un predicato con due argomenti che possono essere considerati il primo come input e il secondo come output e vogliamo che questo predicato sia usato per mappare tutti gli elementi di una lista di ingresso in una lista di uscita. Vogliamo allora scrivere un predicato mappaliste(Pred,Lingresso,Luscita) dove Pred è il nome di un predicato a due argomenti. Potremo così scrivere in goal del tipo


?- mappaliste(parola,['Giovanni',era,uno,studente],L).

e ottenere come risposta: L=['John',was,a,student] La procedura che ci interessa è la seguente:

mappaliste(_,[],[]).
mappaliste(Pred,[X|Resto],[X1|Resto1]):-
  Goal=..[Pred,X,X1],
  call(Goal),
  mappaliste(Pred,Resto,Resto1).

La prima clausola termina la ricorsione. Nella seconda con l' operatore =.. si crea una goal con funtore Pred e due argomenti l'input X e l'output X1. Quindi con il predicato call si sottomette il goal Goal all'interprete. Se Goal ha successo istanzierà X1 che viene inserito in testa alla lista di uscita. Altri esempi possiamo ottenerli pensando di Scrivendo due predicati per calcolare il quadrato e il cubo di un numero, possiamo vedere ultoriori esempi di uso del predicato mappaliste.

% calcola il quadrato  
quadrato(X,Y) :- 
  Y is X * X.

%calcola il cubo
cubo(X,Y) :-
  Y is X * X * X.

Formulate delle domande in modo da ottenere i quadrati o i cubi di una lista di numeri.

%file predefiniti/mappaliste.pl

mappaliste(_,[],[]).
mappaliste(Pred,[X|Resto],[X1|Resto1]):-
  Goal=..[Pred,X,X1],
  call(Goal),
  mappaliste(Pred,Resto,Resto1).

% come si traducono le singole parole.
parola('Maria','Mary').
parola('Giovanni','John').
parola(era,was).
parola(una,a).
parola(uno,a).
parola(studente,student).
parola(studentessa,student).
parola(_,?).


% ?- mappaliste(parola,['Giovanni',era,uno,studente],L).
% ?- mappaliste(parola,['Maria',era,una,studentessa],L).
% ?- mappaliste(parola,[lui,era,uno,studente],L).

% calcola il quadrato  
quadrato(X,Y) :- 
  Y is X * X.

%calcola il cubo
cubo(X,Y) :-
  Y is X * X * X. 


% ?- mappaliste(quadrato,[0,1,2,3,4,5,6,7,8,9],L).
% ?- mappaliste(cubo,[0,1,2,3,4,5,6,7,8,9],L).

Applica un operatore binario a una lista di numeri

Scrivere una predicato applica che prenda in input un operatore aritmetico e una lista di numeri e produca in output un unico numero, risultato dell'applicazio dell'operatore all'intera lista. Gli esempi che seguono illustrano il comportamento di applica

% ?- applica('+',[2,3,5],N). N=10. (N=2+3+5)
% ?- applica('-',[2,3,5],N). N=-6. (N=2-3-5) ((2-3)-5)  
% ?- applica('*',[2,3,5],N). N=30. (N=2*3*5) 
% ?- applica('/',[8,2,2],N). N=2.  (N=8/2/2) ((8/2)/2)

Le operazioni devono essere fatte da sinistra verso destra (importante per '-' e '/').

Manipolazione del database

Si voglia realizzare un libro degli ospiti, dove registrare ogni nuovo visitatore, assegnandogli un numero progressivo. Possiamo memorizzare nel database dei fatti che ci permettano di ricordare quale numero assegnare al prossimo ospite e di registrare il nome dell'ospite. Potremmo usare i fatti ospite(Nome,Num) per memorizzare il nome di un visitatore e il numero a lui associato e prossimo_ospite(Num) per memorizzare il numero da assegnare al prossimo ospite.
I fatti ospite verranno inseriti nel database ogni volta che si presenta un nuovo ospite mediante il predicato aggiungi_ospite(Nome,Num).

aggiungi_ospite(Nome,Num) :-
  retract(prossimo_ospite(Num)),
  !, 
  assert(ospite(Nome,Num)),
  Num1 is Num+1,
  assert(prossimo_ospite(Num1)).
aggiungi_ospite(Nome,1) :-
  assert(ospite(Nome,1)),
  assert(prossimo_ospite(2)).

La prima clausola, con il predicato retract controlla se esiste nel database il fatto prossimo_ospite(Num). In tal caso asserisce il fatto ospite(Nome,Num) per registrare il nuovo ospote e prepara il contatore da assegnare all'ospite successivo, asserendo prossimo_ospite(Num1) .
Se la regola precedente fallisce perchè il fatto prossimo_ospite(Num) mom era presente nel database, allora l'ospite è il primo e deve essere registrato col numero 1.

Per visualizzare il libro degli ospiti possiamo ricorrere al predicato predefinito listing(P) che visualizza tutti i fatti P e tutte le regole la cui parte sinistra si unifica con P.
Potremo così scrivere: ?- listing(ospite(X)). Un modo alternativo è quello di usare il fail per realizzare un ciclo.

stampa_libro :-
  ospite(Nome,Numero),
  write(Nome),tab(1),write(Numero),nl,
  fail.
stampa_libro.

write(X), tab(N), nl sono procedure di ingresso uscita per stampare il termine X, per avanzare di N spazi e per andare a capo.

Ecco il programma completo:

%file: predefiniti/libroospiti.pl

aggiungi_ospite(Nome,Num) :-
  retract(prossimo_ospite(Num)),
  !, 
  assert(ospite(Nome,Num)),
  Num1 is Num+1,
  assert(prossimo_ospite(Num1)).
aggiungi_ospite(Nome,1) :-
  assert(ospite(Nome,1)),
  assert(prossimo_ospite(2)).

stampa_libro :-
  ospite(Nome,Numero),
  write(Nome),tab(1),write(Numero),nl,
  fail.
stampa_libro.

/* uso
?- aggiungi_ospite('Rossi',N).
?- aggiungi_ospite('Bianchi',N).
?- aggiungi_ospite('Verdi',N).
?- stampa_libro.
*/

Un ulteriore esempio di uso dei predicati predefiniti - Filetto

Nel gioco del filetto due giocatori dispongono su una scacchiera 3x3 un simbolo "croce" o "zero". Vince chi riesce a disporre tre suoi simboli allineati su una riga, su una colonna o su una diagonale.
La scacchiera sia rappresentata dalla struttura s(X1,X2,X3,X4,X5,X6,X7,X8,X9) dove ogni Xi puo' essere 'x' 'o' o una variabile, se la casella non è occupata. Ogni argomento della struttura corrisponde a una tessera della scacchiera secondo questa numerazione.:

      1 2 3
      4 5 6 
      6 7 8

con functor(T,s,9) possiamo creare una struttura vuota T=s(_,_,_,_,_,_,_,_,_) successivanete con il predicato functor(N,T,Val) possiamo assegnare all'argomento N-esimo della struttura T il valore Val, o recuperare il valore precedentemente assegnato ad una casella.
Il predicato inizio crea una scacchiera vuota e la memorizza nel database per l'uso successivo.

inizio :-
  functor(T,s,9),   
  mostra(T),
  assert(scacchiera(T)).

Il predicato mossa(Simbolo,Pos) permette ad un giocatore di mettere il simbolo 'x' o '0' in una certa casella. S usa il fatto scacchiera(Scac) per ottenere la configurazione corrente, si controlla con il predicato vuoto che la casella prescelta sia vuota, e con arg(Pos,Scac,Simbolo> si istanzia l'ergomento relativo. Con retract e assert si elimina la vecchia configurazione e si asserisce la nuova.
Si noti che mossa fallisce se si cerca di giocare in una posizione occupata.

mossa(Pezzo,Pos) :-
  scacchiera(Scac),  % configurazione memorizzata
  vuoto(Pos,Scac),   % la posizione deve essere libera
  retract(scacchiera(Scac)),  % elimina vecchia configurazione
  arg(Pos,Scac,Pezzo),        % istanzia l'argomento
  assert(scacchiera(Scac)),   % memorizza nuova configurazione 
  mostra(Scac).               % visualizza

I predicati vuoto, croce e zero controllano che una certa posizione sia libera, oppure occupata da una croce o da uno zero. I predicati var e nonvar servono a controllare che un certo argomento sia variabile o istanziato.

% la posizione Pos in Scac e' vuota 
vuoto(Pos,Scac) :-
  arg(Pos,Scac,Val), var(Val).
% la posizione Pos in Scac e' 'x'
croce(Pos,Scac) :-
  arg(Pos,Scac,Val), nonvar(Val),Val=x.
% la posizione Pos in Scac e' '0'
zero(Pos,Scac) :-
  arg(Pos,Scac,Val), nonvar(Val),Val=0.

Questi predicati sono utilizzati anche da mostra che visualizza la scacchiera.

% file predefiniti/filetto0.pl

% gioco del filetto

/* rappresentazione della scacchiera:

     s(x1,x2,x3,x4,x5,x6,x7,x8,x9)

dove xi puo' essere 'x' 'o' o una variabile
gli argomenti corrispondono a queste
 posizioni sulla scacchiera

      1 2 3
      4 5 6 
      6 7 8

esempio di uso:

?- inizio.
?- mossa(x,3).
?- mossa(0,2).
?- mossa(x,5).
......
......
    
*/


%inizio crea una scacchiera vuota 
%e la asserisce nel database
inizio :-
  functor(T,s,9),  % T e' una scacchiera vuota 
  mostra(T),
  assert(scacchiera(T)).

% gestisce una mossa
% si mette Pezzo che puo' essere '0' o 'x'
% in Pos

mossa(Pezzo,Pos) :-
  scacchiera(Scac),  % configurazione memorizzata
  vuoto(Pos,Scac),   % la posizione deve essere libera
  retract(scacchiera(Scac)),  % elimina vecchia configurazione
  arg(Pos,Scac,Pezzo),        % istanzia l'argomento
  assert(scacchiera(Scac)),   % memorizza nuova configurazione 
  mostra(Scac).               % visualizza 

% la posizione Pos in Scac e' vuota 
vuoto(Pos,Scac) :-
  arg(Pos,Scac,Val), var(Val).
% la posizione Pos in Scac e' 'x'
croce(Pos,Scac) :-
  arg(Pos,Scac,Val), nonvar(Val),Val=x.
% la posizione Pos in Scac e' '0'
zero(Pos,Scac) :-
  arg(Pos,Scac,Val), nonvar(Val),Val=0. 


% visualizzazione della scacchiera
 
riga([1,2,3]).
riga([4,5,6]).
riga([7,8,9]).


mostra(Scac) :-
    riga([Pos1,Pos2,Pos3]),
    mostra_pos(Pos1,Scac), tab(2),
    mostra_pos(Pos2,Scac), tab(2),
    mostra_pos(Pos3,Scac), tab(2),
    tab(5),write([Pos1,Pos2,Pos3]),
    nl,nl,
    fail.
mostra(_). 

mostra_pos(Pos,Scac):-
  vuoto(Pos,Scac),
  write('-').
mostra_pos(Pos,Scac):-
  croce(Pos,Scac),
  write(x).
mostra_pos(Pos,Scac):-
  zero(Pos,Scac),
  write(0).

Esercizio: Scrivere due predicati per il gioco del filetto:

vince(Scacchiera,Giocatore) che deve avere successo se Scacchiera è una configurazione vincente per Giocatore
minaccia(Giocatore,Posizione) se Giocatore ha la possibilità di vincere alla mossa successiva. (Ci sono due posizioni con il suo simbolo e una posizione vuota allineate).

Suggerimento: definire una tabella delle posizioni allineate:

% tabella delle posizioni allineate

allineate([1,2,3]).  % righe
allineate([4,5,6]).
allineate([7,8,9]).
allineate([1,4,7]).  % colonne
allineate([2,5,8]).
allineate([3,6,9]).
allineate([1,5,9]).  % diagonali
allineate([3,5,7]).

e utilizzare i predicati già definiti vuoto, croce e zero.