Rappresentazione del flusso di controllo

Per comprendere appieno il modo di operare delle procedure di debugging è necessario avere familiarità con il modo in cui l'interprete Prolog opera nel tentativo di soddisfare una congiunzione di goal. Un modello semplice ed efficace per rappresentare l'esecuzione di un programma è il modello a scatole proposto in Clocksin e Mellish [1981]. Questo modello permette di seguire agevolmente la traccia dell'esecuzione di un programma.

Secondo il modello a scatole, ogni invocazione di una procedura viene rappresentata con una scatola con quattro porte, come nella Figura 1.



              CALL  +------------------+  EXIT
             ------>|                  |------->
                    |    procedura     |
             <------|                  |<------
               FAIL +------------------+  REDO

Figura 1

Per la stessa procedura, a invocazioni diverse corrispondono scatole diverse. Ad esempio, per la procedura ancestor e per i fatti father

   ancestor(X,Y)\|:- father(X,Y).
   ancestor(X,Y)\|:-                                          
          father(X,Z)
          ancestor(Z,Y).


   father (john,jim).
   father (jim, mike).                                      
   father (john,charlie).

all'invocazione della procedura ancestor in seguito al goal

   ?- ancestor(john,mike).

corrisponde la scatola nella Figura 2 con le variabili X e Y istanziate rispettivamente con john e mike.


           CALL +------------------------+ EXIT
          ----->|   ancestor(X,Y) :-     |----->
                |        father(X,Y).    |
                |                        |
                |   ancestor(X,Y) :-     |
                |        father(X,Z),    |
          <-----|        ancestor(Z,Y).  |<-----
           FAIL +------------------------+ REDO


Figura 2

Attraverso le porte è possibile seguire il flusso di controllo nell'esecuzione di un programma. In particolare, il flusso può essere pensato come un puntatore che si muove lungo il codice all'interno della scatola entrando per le porte di ingresso e uscendo per le porte di uscita.

La porta CALL indica il punto di ingresso nella scatola all'atto dell'invocazione iniziale della procedura. Dopo l'ingresso da questa porta il puntatore si muove lungo il codice della procedura seguendo l'ordine con cui si tenta di soddisfare i singoli subgoal.
La porta EXIT indica il punto di uscita dalla scatola dopo un ritorno con successo dalla procedura.
La porta REDO indica il punto di ingresso nella scatola per la ricerca di una soluzione alternativa a seguito di un operazione di backtracking. Ciò vuol dire un tentativo di soddisfare in modo diverso uno dei subgoal nel corpo della clausola che aveva avuto successo prima. Dopo l'ingresso da questa porta, il puntatore si muove all'indietro lungo il codice a partire dal punto in cui aveva lasciato la scatola attraverso la porta EXIT nel tentativo di trovare una nuova soluzione per un subgoal. Se non ci sono soluzioni alternative, il puntatore passa a una nuova clausola.
La porta FAIL indica il punto di uscita dalla scatola nel caso in cui l'invocazione non ha successo. Il puntatore ritorna al codice da cui era stata invocata la procedura, muovendosi all'indietro alla ricerca di soluzioni alternative.
Per ogni invocazione vi è sempre un solo ingresso del puntatore attraverso la porta CALL e una sola uscita attaverso la porta FAIL, mentre il puntatore può entrare e uscire diverse volte attraverso le porte REDO e EXIT, rispettivamente, per effetto del backtracking.
E` opportuno indicare ogni scatola, e quindi ogni invocazione, con un numero diverso. Ciò è utile quando, soprattutto a causa di definizioni ricorsive, possono esserci più invocazioni della stessa procedura (come nel caso della (1).
Le scatole possono essere incastrate una nell'altra e collegate fra di loro. Ogni incastro corrisponde a un maggior dettaglio nella rappresentazione del flusso di controllo del programma. Ad esempio, per la procedura ancestor una rappresentazione più dettagliata è quella mostrata nella Figura 3.
```
     +-----------------+------------------------------+
     |1. ancestor(X,Y) |                              |EXIT
 CALL+-----------------+                            +-|--->
 --->|-+                                            | |
     | |CALL +-----------+ EXIT                     | |
     | +---->|     2.    |--------------------------+ |
     |+------|father(X,Y)|<-------------------------++|
     || FAIL +-----------+ REDO                     |||
     ||                                             |||
     ||CALL+-----------+EXIT CALL+-------------+EXIT|||
     |+--->|     3.    |-------->|      4.     |----+||
 <---|-----|father(X,Z)|<--------|ancestor(Z,Y)|<----+|<---
 FAIL| FAIL+-----------+REDO FAIL+-------------+REDO  |REDO
     +------------------------------------------------+


Figura 3
```
Come si vede dalla figura, le scatole vengono collegate fra loro nel modo seguente:
```
              FAIL --> REDO
              FAIL --> CALL
              EXIT --> CALL
```
Questi collegamenti determinano lo scorrere del flusso in due direzioni: una in avanti e una all'indietro. Il movimento all'indietro corrisponde a operazioni di backtracking.
La presenza del cut, interrompe il collegamento FAIL - REDO corrispondente e ridirige l'uscita FAIL all'uscita FAIL della porta più esterna. Il flusso può essere seguito con un puntatore lungo le frecce che collegano le scatole. L'ingresso attraverso una porta REDO provoca un movimento del puntatore all'indietro lungo le scatole attraverso le connessioni FAIL - REDO nel tentativo di soddisfare in modo diverso un subgoal. Un successo fa uscire il puntatore dalla porta EXIT ripristinando il movimento in avanti. Il movimento del puntatore si alterna in avanti e all'indietro, a seconda della porta da cui viene fatto uscire, finchè questo non esce definitivamente da una delle porte più esterne EXIT o FAIL.
La biforcazione della freccia REDO indica i due punti di ritorno in un'operazione di backtracking. Come regola, si ritorna alla scatola da cui si è usciti l'ultima volta attraverso la porta EXIT.
I fatti relativi alla procedura father possono essere anch'essi rappresentati con una scatola come nella Figura 4.
```
             CALL +----------------------+ EXIT
            ----->| father(john,jim)     |----->
                  | father(john,charlie) |
            <-----| father(jim,mike)     |<-----
             FAIL +----------------------+ REDO



Figura 4
```
Come esempio, mostriamo la traccia dell'esecuzione del programma in seguito al seguente goal
```
   ?- ancestor(john,Ans), fail.                             
```
Il fail finale forza un backtracking esaustivo. Il goal (3), che corrisponde all'invocazione in sequenza delle procedure ancestor e fail con le variabili instanziate con john e Ans può essere rappresentato con le scatole mostrate nella Figura 5.
```
   CALL +--------------------+ EXIT CALL +------+ EXIT
  ----->|                    |---------->|      |----->
        | ancestor(john,Ans) |           | fail |
  <-----|                    |<----------|      |<-----
   FAIL +--------------------+ REDO FAIL +------+ REDO


Figura 5
```
La traccia dell'esecuzione del programma consiste nell'indicazione delle porte lungo le quali scorre il flusso assieme al numero d'ordine dell'invocazione. Si ha quindi:
```
(1) CALL : ancestor(john,Ans)
(2) CALL : father(john,Ans)
(2) EXIT : father(john,jim)
(1) EXIT : ancestor(john,jim)
```
che corrisponde alla prima risposta, dopo di che si ha:
```
(3) CALL : fail
(3) FAIL : fail
```
che provoca un'operazione di backtracking:
```
(1) REDO : ancestor(john,Ans)
(2) REDO : father(john,Ans)
(2) EXIT : father(john,charlie)
(1) EXIT : ancestor(john,charlie)
```
che corrisponde alla seconda risposta. Ancora si ha:
```
(4) CALL : fail
(4) FAIL : fail
(1) REDO : ancestor(john,Ans)
(2) REDO : father(john,Ans)
(2) FAIL : father(john,Ans)
```
A causa del fallimento della prima clausola di ancestor. si passa alla seconda clausola:
```
(5) CALL : father(john,Z)
(5) EXIT : father(john,jim)
(6) CALL : ancestor(jim,Ans)
    ...
```