Nota sulla tabella di esecuzione di un programma (trace

Nota sulla tabella di esecuzione di un
programma (trace-table)
La tabella di esecuzione di un programma (trace-table) è uno strumento
utilizzato per verificare la correttezza dell’esecuzione di una soluzione di un
problema con lo scopo di individuare errori logici contenuti nella soluzione.
La trace-table rappresenta la parte della memoria centrale utilizzata dal
calcolatore per l’esecuzione dei sottoprogrammi (funzioni/procedure). L’esecuzione di un programma con l’ausilio della trace-table deve quindi osservare le seguenti regole: ogni volta che l’esecuzione di un’istruzione necessita
il valore di una variabile, il valore deve essere prelevato dalla trace-table.
Ogni volta che un’istruzione modifica una variabile la modifica deve essere riportata nella trace-table. Nel seguito verrà mostrato come leggere/scrivere
i valori delle variabili.
Le colonne della trace-table rappresentano le variabili e/o i parametri contenuti nei sottoprogrammi. Le colonne vengono aggiunte/rimosse
ogni qualvolta inizia/termina l’esecuzione di un sottoprogramma osservando la seguente regola: ogni volta che un’istruzione richiede l’esecuzione di un
sottoprogramma, nella trace-table:
1. viene aggiunta una colonna per ogni parametro del sottoprogramma;
2. viene aggiunta una colonna per ogni variabile locale del sottoprogramma;
3. per il linguaggi tipo VBA, se il sottoprogramma è una funzione, viene
aggiunta una colonna che riporta il nome della funzione.
Ogni colonna inserita deve essere etichettata con il nome della variabile o parametro corrispondente e deve essere anche inserita una riga di intestazione
che raggruppa nelle nuove colonne inseite. La nuova riga deve riportare l’istruzione di chiamata del sottoprogramma e cioè il nome del sottoprogramma
e dalla lista degli argomenti (parametri attuali). I valori per gli argomenti
sono determinati dalle espressioni contenute nell’istruzione di chiamata di
1
funzione. Infine, deve essere inserita una riga che riporta i valori iniziali dei
parametri e delle variabili della funzione.
Al termine dell’esecuzione della funzione questa parte di tabella non deve
essere più considerata.
La trace-table è quindi dinamica nel senso che il numero di righe e
colonne della trace-table viene modificato durante l’esecuzione del programma.
1
Esempio in linguaggio C
Dato il seguente programma scritto in linguaggio C/C++
int A(int a, int *b)
{
int c;
c = a + (*b) + 2;
*b = a + 2;
return c + 2;
}
int main()
{
int y, x;
x = 4;
y = A(x, &x);
x = y + 2;
return 0;
}
mostriamo la sua esecuzione con l’ausilio della trace-table.
Inizio. Il programma inizia l’esecuzione eseguendo la funzione main, costruiamo la trace-table in modo che contenga una colonna per ogni variabile della funzione main, un’intestazione ed una riga che riporta, per ogni colonna, il valore iniziale della variabile corrispondente. Di seguito utilizzeremo
il simbolo - per indicare che una variabile ha un valore indefinito.
2
int A(int a, int *b)
Funzione
{
Variabili
int c;
c = a + (*b) + 2;
*b = a + 2;
main()
return c + 2;
}
x
y
-
-
int main()
{
valore indefinito
int y, x;
x = 4;
y = A(x, &x);
x = y + 2;
return 0;
}
Ogni volta che viene eseguita un’istruzione in cui non è richiesta l’esecuzione
di una funzione, si deve aggiungere alla tabella una nuova riga. In questa
nuova riga il valore di una colonna è:
• il valore della riga precedente se l’esecuzione dell’istruzione non cambia
il valore della variabile corrispondente alla colonna,
• il nuovo valore da assegnare alla variabile se l’esecuzione dell’istruzione
cambia il valore della variabile corrispondente alla colonna.
Ad esempio, l’esecuzione della prima istruzione x = 4; comporterà l’inserimento di una nuova riga nella tabella, che conterrà i valori della riga precedente in tutte le colonne ad eccezione del valore della colonna x dove verrà
scritto il valore 4.
3
int A(int a, int *b)
main()
{
int c;
x
y
-
-
4
-
c = a + (*b) + 2;
*b = a + 2;
return c + 2;
}
int main()
{
int y, x;
x = 4;
y = A(x, &x);
x = y + 2;
return 0;
}
Se l’istruzione da eseguire necessita l’esecuzione di un sottoprogramma ad
esempio y = A(x, &x);, si dovrà procedere in uno dei seguenti modi:
• il sottoprogramma da eseguire è una funzione (come nell’esempio). In
questo caso si dovrà
1. sospendere l’esecuzione dell’istruzione;
2. aggiungere alla trace-table una colonna per ogni parametro/variabile
del sottoprogramma da eseguire;
3. aggiungere una nuova riga per i valori delle colonne;
4. eseguire la funzione per determinare il suo valore;
5. sostituire il valore restituito dalla funzione al posto della sua chiamata;
6. riprendere l’esecuzione dell’istruzione.
• il sottoprogramma da eseguire è una procedura. In questo caso si dovrà
1. aggiungere alla trace-table una colonna per ogni parametro/variabile
del sottoprogramma da eseguire;
2. aggiungere una nuova riga per i valori delle colonne.
3. eseguire il sottoprogramma;
4. riprendere l’esecuzione dall’istruzione successiva.
4
In entrambi i casi, la nuova parte deve contenere un’intestazione che raggruppa le nuove colonne e che a loro volta devono essere etichettate con i
nomi della variabili/parametri corrispondenti. L’intestazione è composta dal
nome del sottoprogramma e dal valore dei parametri attuali. La nuova riga
deve riportare i valori della riga precedente e per la nuova parte i valori che
inizializzano i parametri e le variabili del sottoprogramma che deve essere
eseguito. Nel linguaggio C (C++) nella riga in corrispondenza di ogni nuova
colonna etichettata con il nome di una variabile deve essere posto il valore -.
Mentre nella riga in corrispondenza di ogni nuova colonna etichettata con il
nome di un parametro verrà inserito il valore del corrispondente parameetro
attuale riportato nell’intestazione della nuova parte1 .
Nel nostro esempio, l’esecuzione dell’istruzione y = A(x, &x); comporterà
• l’inserimento di tre nuove colonne: la prima per il parametro a della
funzione A() la seconda per il parametro b della funzione A() e la terza
per la variabile c della funzione A();
• l’inserimento di una riga d’intestazione A(4, &x main);
• l’inserimento della riga di inizializzazione delle colonne come mostrato
nella seguente figura.
dove la scrittura &x main significa riferimento alla colonna x nella parte della
tabella etichettata con main2 .
1
Nel linguaggio C il passaggio di parametri avviene solo per valore. In altri linguaggi
di programmazione è consentito anche il passaggio di parametri per riferimento, in questo
caso nella colonna corrispondente ad un parametro riferimento viene inserita l’etichetta
dalla colonna riferita.
2
Ricordiamo che, nel linguaggio C/C++ l’espressione &x ha come valore l’indirizzo
della variabile x.
5
int A(int a, int *b)
main()
parametri attuali
{
int c;
x
y
c = a + (*b) + 2;
-
-
4
-
a
b
c
4
-
4
&x main
-
A(4, &x main)
*b = a + 2;
return c + 2;
}
int main()
{
int y, x;
x = 4;
inizializzazione dei parametri
y = A(x, &x);
x = y + 2;
return 0;
}
L’istruzione successiva da eseguire è ”c = a + (*b) + 2;”. Non essendo
richiesta l’esecuzione di alcuna funzione si procederà inserendo una nuovo
riga nella tabella che riporterà i valori della riga precedente ad eccezione del
valore per la colonna c in cui verrà scritto il valore dell’espressione. Per
calcolare il valore dell’espressione, i valori delle variabili che la compongono
devono essere prelevati dalla trace-table considerando i valori dell’ultima
riga; quindi essendo 4 il valore della colonna a nell’ultima riga, ed essendo &x
main il valore della colonna b nell’ultima riga e conseguentemete 4 il valore
dell’espressione *b3 , l’espressione a + (*b) + 2 vale 10. Quindi nella nuova
riga in corrispondenza della colonna c si riporterà il valore 10.
3
Ricordiamo che, informalmente, *b significa utilizza la colonna indicata da b; nel
nostro caso la colonna x della parte main
6
int A(int a, int *b)
main()
{
int c;
c = a + (*b) + 2;
*b = a + 2;
return c + 2;
x
y
-
-
4
-
a
b
c
4
-
4
&x main
-
4
-
4
&x main 10
A(4, &x main)
}
int main()
{
int y, x;
x = 4;
y = A(x, &x);
x = y + 2;
return 0;
}
L’istruzione successiva da eseguire è *b = a + 2;. Essendo &x main
il valore della colonna b nell’ultima riga, il valore dell’espressione a + 2
verrà inserito nella nuova riga della tabella in corrispondenza della colonna
etichettata con x della parte main.
int A(int a, int *b)
main()
{
int c;
c = a + (*b) + 2;
*b = a + 2;
return c + 2;
x
y
-
-
4
-
a
b
c
4
-
4
&x main
-
4
-
4
&x main 10
6
-
4
&x main 10
A(4, &x main)
}
int main()
{
int y, x;
x = 4;
y = A(x, &x);
x = y + 2;
return 0;
}
L’esecuzione dell’istruzione return determina la terminazione dell’esecuzione della funzione A(). La parte della tabella relativa ad A(4, &x main)
7
ha esaurito il suo compito e non deve essere più utilizzata. L’esecuzione
del programma riprende dall’istruzione y = A(x, &x) della funzione main()
nella quale utilizzaremo il valore della funzione (12) al posto della chiamata
della funzione A(x, &x). Di conseguenza il nuovo valore per la colonna y è
12.
int A(int a, int *b)
main()
{
int c;
c = a + (*b) + 2;
*b = a + 2;
return c + 2;
x
y
-
-
4
-
a
b
c
4
-
4
&x main
-
4
-
4
&x main 10
6
-
4
&x main 10
6
12
A(4, &x main)
}
int main()
{
int y, x;
x = 4;
y = A(x, &x);
x = y + 2;
return 0;
}
Infine, seguendeo le stesse regole descritte precedentemente, l’istruzione
x = y + 2 modifica la trace-table come riportato nella seguente figura.
8
int A(int a, int *b)
main()
{
int c;
c = a + (*b) + 2;
*b = a + 2;
return c + 2;
x
y
-
-
4
-
a
b
c
4
-
4
&x main
-
4
-
4
&x main 10
6
-
4
&x main 10
6
12
14
12
A(4, &x main)
}
int main()
{
int y, x;
x = 4;
y = A(x, &x);
x = y + 2;
return 0;
}
9