Program Slicing

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

Nella programmazione informatica, il program slicing è il calcolo dell'insieme di istruzioni del programma, chiamato program slice, che può influenzare i valori in un punto di interesse, denominato criterio di slicing . Lo slicing del programma può essere utilizzato nel debug per individuare più facilmente la fonte degli errori. Altre applicazioni dello slicing includono la manutenzione del software, l'ottimizzazione, l'analisi dei programmi e il controllo del flusso di informazioni .

Le tecniche di slicing hanno visto un rapido sviluppo sin dalla definizione originale di Mark Weiser . Inizialmente lo slicing era solo statico, cioè applicato al codice sorgente senza altre informazioni oltre al codice sorgente. Bogdan Korel e Janusz Laski hanno introdotto lo slicing dinamico, che funziona su una specifica esecuzione del programma (per una data traccia di esecuzione). [1] Esistono altre forme di slicing, ad esempio il path slicing. [2]

Slicing statico

[modifica | modifica wikitesto]

Basandosi sulla definizione originale di Weiser, informalmente, una porzione di slice statica S è costituita da tutte le istruzioni del programma P che possono influenzare il valore della variabile v in un'istruzione x. La sezione è definita per un criterio di slice C=(x,v) dove x è un'istruzione nel programma P e v è variabile in x. Una slice statica include tutte le istruzioni che possono influenzare il valore della variabile v nell'istruzione x per qualsiasi possibile input. Le slice statiche vengono calcolate ripercorrendo le dipendenze tra le istruzioni. Più specificamente, per calcolare la sezione statica per (x,v), troviamo prima tutte le istruzioni che possono influenzare direttamente il valore di v prima che venga incontrata l'istruzione x. Ricorsivamente, per ogni istruzione y che può influenzare il valore di v nell'istruzione x, calcoliamo le sezioni per tutte le variabili z in y che influenzano il valore di v. L'unione di tutte queste sezioni è la slice statica per (x,v) .

Esempio

[modifica | modifica wikitesto]

Ad esempio, considera il programma C di seguito.

Calcoliamo la slice per ( write(sum), sum ). Il valore di sum è direttamente influenzato dalle affermazioni "sum = sum + i + w" se N>1 e "int sum = 0" se N <= 1. Quindi, slice( write(sum), sum) è l'unione di tre slice e l'istruzione "int sum = 0" che non ha dipendenze:

  • slice (sum = sum + i + w, sum)
  • slice (sum = sum + i +w, i)
  • slice (sum = sum +i +w, w) , and
  • {int sum=0}

È abbastanza facile vedere che slice( sum = sum + i + w, sum) consiste di "sum = sum + i + w" e "int sum = 0" perché queste sono le uniche due istruzioni precedenti che possono influenzare il valore della somma in "sum = sum + i + w". Allo stesso modo, slice( sum = sum + i + w, i) contiene solo "for(i = 1; i < N; ++i) {" e slice( sum = sum + i + w, w) contiene solo l'istruzione "int w = 7".

Quando uniamo tutte queste istruzioni, non abbiamo codice eseguibile, quindi per rendere la slice eseguibile aggiungiamo semplicemente la parentesi graffa finale per il ciclo for e la dichiarazione di i. La sezione eseguibile statica risultante è mostrata sotto il codice originale riportato di seguito.

int i;
int sum = 0;
int product = 1;
int w = 7;
for(i = 1; i < N; ++i) {
 sum = sum + i + w;
 product = product * i;
}
write(sum);
write(product);

La slice eseguibile statica per i criteri ( write(sum), sum) è il nuovo programma mostrato di seguito.

int i;
int sum = 0;
int w = 7;
for(i = 1; i < N; ++i) {
 sum = sum + i + w;

}
write(sum);

In effetti, la maggior parte delle tecniche di slicing statiche, inclusa la tecnica di Weiser, rimuoveranno anche l'istruzione write(sum) . Poiché, nell'istruzione write(sum), il valore di sum non dipende dall'istruzione stessa. Spesso una slice per una particolare istruzione x includerà più di una variabile. Se V è un insieme di variabili in un'istruzione x, allora la sezione per (x, V) è l'unione di tutte le sezioni con criteri (x, v) dove v è una variabile nell'insieme V.

Approccio allo slicing statico rapido in avanti

[modifica | modifica wikitesto]

Un approccio di slicing molto veloce e scalabile, ma leggermente meno accurato, è estremamente utile per una serie di motivi. Gli sviluppatori disporranno di costi molto bassi e di mezzi pratici per stimare l'impatto di un cambiamento in pochi minuti invece che in giorni. Questo è molto importante per pianificare l'implementazione di nuove funzionalità e comprendere come un cambiamento è correlato ad altre parti del sistema. Fornirà inoltre un test poco costoso per determinare se è giustificata un'analisi completa e più costosa del sistema. Un approccio di slicing rapido aprirà nuove strade di ricerca nelle metriche e nell’estrazione di storie basate sullo slicing. Cioè, ora lo slicing può essere condotto su sistemi molto grandi e su intere cronologie di versioni in tempi molto pratici. Ciò apre la porta a una serie di esperimenti e indagini empiriche che in precedenza erano troppo costosi da intraprendere. [3]

Slicing dinamico

[modifica | modifica wikitesto]

Lo slicing dinamico utilizza le informazioni su una particolare esecuzione di un programma. Una slice dinamica contiene tutte le istruzioni che effettivamente influenzano il valore di una variabile in un punto del programma per una particolare esecuzione del programma piuttosto che tutte le istruzioni che potrebbero aver influenzato il valore di una variabile in un punto del programma per qualsiasi esecuzione arbitraria del programma.

Un esempio per chiarire la differenza tra slicing statico e dinamico. Consideriamo una piccola parte di un'unità di programma, in cui è presente un blocco di iterazione contenente un blocco if-else. Ci sono alcune istruzioni in entrambi i blocchi if e else che hanno effetto su una variabile. Nel caso dello slicing statico, poiché l'intera unità di programma viene considerata indipendentemente da una particolare esecuzione del programma, le istruzioni interessate in entrambi i blocchi verrebbero incluse nello slice. Ma nel caso dello slicing dinamico consideriamo una particolare esecuzione del programma, in cui il blocco if viene eseguito e le istruzioni interessate nel blocco else non vengono eseguite. Ecco perché in questo particolare caso di esecuzione la sezione dinamica conterrebbe solo le istruzioni nel blocco if .

Note

[modifica | modifica wikitesto]
  1. ^ vol. 29, DOI:10.1016/0020-0190(88)90054-3, https://oadoi.org/10.1016/0020-0190(88)90054-3.
  2. ^ Ranjit Jhala e Rupak Majumdar, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, PLDI '05, ACM, 2005, pp. 38–47, DOI:10.1145/1065010.1065016, ISBN 9781595930569.
  3. ^ (EN) vol. 26, DOI:10.1002/smr.1651, ISSN 2047-7473 (WC · ACNP), https://oadoi.org/10.1002/smr.1651.

Riferimenti

[modifica | modifica wikitesto]
  • Marco Weiser . "Speciatura del programma". Atti della 5a Conferenza Internazionale sull'Ingegneria del Software, pagine 439 – 449, IEEE Computer Society Press, marzo 1981.
  • Marco Weiser . "Speciatura del programma". IEEE Transactions on Software Engineering, Volume 10, Numero 4, pagine 352 – 357, IEEE Computer Society Press, luglio 1984.
  • Susan Horwitz, Thomas Reps e David Binkley, Affettamento interprocedurale mediante grafici di dipendenza, ACM Transactions on Programming Languages and Systems, volume 12, numero 1, pagine 26-60, gennaio 1990.
  • Frank Suggerimento. "Un'indagine sulle tecniche di slicing dei programmi". Journal of Programming Languages, Volume 3, Numero 3, pagine 121–189, settembre 1995.
  • David Binkley e Keith Brian Gallagher. "Speciatura del programma". Avanzamenti nei computer, volume 43, pagine 1–50, Academic Press, 1996.
  • Andrea di Lucia. "Program slicing: Methods and application", Workshop internazionale sull'analisi e la manipolazione del codice sorgente, pagine 142-149, 2001, IEEE Computer Society Press.
  • Mark Harman e Robert Hierons. "Una panoramica del program slicing", Software Focus, volume 2, numero 3, pagine 85–92, gennaio 2001.
  • David Binkley e Mark Harman. "Un'indagine sui risultati empirici sul program slicing", Advances in Computers, volume 62, pagine 105-178, Academic Press, 2004.
  • Jens Krinke. "Program Slicing", nel Manuale di ingegneria del software e ingegneria della conoscenza, volume 3: progressi recenti. Pubblicazione scientifica mondiale, 2005
  • Silva, Giuseppe. "Un vocabolario di tecniche basate sul program slicing", ACM Computing Surveys, volume 44, numero 3, Association for Computing Machinery, giugno 2012
  • Alomari HW et al. "srcSlice: affettamento statico in avanti molto efficiente e scalabile". Wiley Journal of Software: Evoluzione e processo ( JSEP ), DOI: 10.1002/smr.1651, vol. 26, n. 11, pp. 931-961, 2014.
[modifica | modifica wikitesto]

Template:Program analysis

Estratto da "https://it.wikipedia.org/w/index.php?title=Program_Slicing&oldid=139902999"