Programové krájení - Program slicing

Pro další použití „krájení“ viz Krájení (disambiguation).

v programování, krájení programu je výpočet množiny programových příkazů, programový řez, které mohou ovlivnit hodnoty v určitém bodě zájmu, označované jako a kritérium krájení. Programové krájení lze použít v ladění snadnější vyhledání zdroje chyb. Mezi další aplikace krájení patří údržba softwaru, optimalizace, programová analýza, a řízení toku informací.

Techniky krájení zaznamenávají rychlý vývoj od původní definice Mark Weiser. Zpočátku bylo krájení pouze statické, tj. Aplikováno na zdrojový kód bez jiných informací než zdrojového kódu. Bogdan Korel a Janusz Laski představen dynamické krájení, který pracuje na konkrétním spuštění programu (pro danou stopu spuštění).[1] Existují i ​​jiné formy krájení, například krájení cest.[2]

Statické krájení

Na základě původní definice Weisera,[3] neformálně se statický programový řez S skládá ze všech příkazů v programu P, které mohou ovlivnit hodnotu proměnné v ve výpisu x. Řez je definován pro kritérium krájení C = (x, v), kde x je příkaz v programu P a v je proměnná v x. Statický řez obsahuje všechny příkazy, které mohou ovlivnit hodnotu proměnné v v příkazu x pro jakýkoli možný vstup. Statické řezy se počítají zpětným sledováním závislostí mezi příkazy. Přesněji, pro výpočet statického řezu pro (x, v) nejprve najdeme všechny příkazy, které mohou přímo ovlivnit hodnotu v, než se setká s příkazem x. Rekurzivně pro každý příkaz y, který může ovlivnit hodnotu v v příkazu x, vypočítáme řezy pro všechny proměnné z v y, které ovlivňují hodnotu v. Spojením všech těchto řezů je statický řez pro (x, v) .

Příklad

Zvažte například níže uvedený program C. Pojďme vypočítat řez pro (write (sum), sum). Na hodnotu součtu mají přímý vliv příkazy „sum = sum + i + w“, pokud N> 1 a „int sum = 0“, pokud N <= 1. Takže slice (write (sum), sum) je sjednocení ze tří řezů a příkazu "int sum = 0", který nemá žádné závislosti:

  1. plátek (součet = součet + i + w, součet)
    2. ,
  2. plátek (součet = součet + i + w, i)
    3. ,
  3. plátek (součet = součet + i + w, w)
    4. , a
  4. {int součet = 0}.

Je docela snadné vidět, že řez (sum = sum + i + w, sum) se skládá z „sum = sum + i + w“ a „int sum = 0“, protože to jsou jediné dva předchozí příkazy, které mohou ovlivnit hodnotu součtu na „součet = součet + i + w“. Podobně řez (sum = suma + i + w, i) obsahuje pouze „for (i = 1; i

Když sjednotíme všechny tyto příkazy, nemáme spustitelný kód, takže aby se z řezu stal spustitelný řez, přidáme pouze koncovou závorku smyčky for a deklaraci i. Výsledný statický spustitelný řez je zobrazen pod původním kódem níže.

int i;int součet = 0;int produkt = 1;int w = 7;pro(i = 1; i < N; ++i) {  součet = součet + i + w;  produkt = produkt * i;}psát si(součet);psát si(produkt);

Statický spustitelný řez pro kritéria (napsat (součet), sum) je nový program zobrazený níže.

int i;int součet = 0;int w = 7;pro(i = 1; i < N; ++i) {  součet = součet + i + w;}psát si(součet);

Ve skutečnosti většina technik statického krájení, včetně Weiserovy vlastní techniky, také odstraní napsat (součet) prohlášení. Vzhledem k tomu, na prohlášení napsat (součet), hodnota součet není závislá na samotném prohlášení. Často řez pro konkrétní příkaz x bude obsahovat více než jednu proměnnou. Pokud V je sada proměnných v příkazu x, pak řez pro (x, V) je sjednocení všech řezů s kritérii (x, v), kde v je proměnná v sadě V.

Lehký přístup vpřed se statickým krájením

Velmi rychlý a škálovatelný, ale o něco méně přesný postup krájení je nesmírně užitečný z mnoha důvodů. Vývojáři budou mít velmi nízké náklady a praktické prostředky k odhadu dopadu změny během několika minut oproti dnům. To je velmi důležité pro plánování implementace nových funkcí a pochopení toho, jak změna souvisí s ostatními částmi systému. Poskytne také levný test k určení, zda je zaručena úplná a dražší analýza systému. Rychlý přístup k rozdělení otevře nové cesty výzkumu metrik a těžby historie založené na krájení. To znamená, že krájení lze nyní provádět na velmi velkých systémech a na celé historii verzí ve velmi praktických časových rámcích. Tím se otevírají dveře řadě experimentů a empirických výzkumů, které byly dříve příliš nákladné na to, aby byly provedeny.[4]

Dynamické krájení

Využívá informace o konkrétním spuštění programu. Dynamický řez obsahuje všechny příkazy, které skutečně ovlivňují hodnotu proměnné v bodě programu pro konkrétní provedení programu, spíše než všechny příkazy, které mohly ovlivnit hodnotu proměnné v bodě programu pro libovolné provádění programu.

Příklad k objasnění rozdílu mezi statickým a dynamickým krájením. Zvažte malý kousek programové jednotky, ve kterém je iterační blok obsahující blok if-else. V obou je několik prohlášení -li a jiný bloky, které mají vliv na proměnnou. V případě statického krájení, protože se na celou programovou jednotku pohlíží bez ohledu na konkrétní provedení programu, ovlivní se příkazy v obou blocích do řezu. Ale v případě dynamického krájení uvažujeme konkrétní provedení programu, kde -li blok se provede a ovlivněné příkazy v souboru jiný blok se nenechá provést. Proto by v tomto konkrétním případě provedení dynamický řez obsahoval pouze příkazy v -li blok.

Viz také

Poznámky

  1. ^ Korel, Bogdan; Laski, Janusz (1988). "Dynamické rozdělení programu". Dopisy o zpracování informací. 29 (3): 155–163. CiteSeerX  10.1.1.158.9078. doi:10.1016/0020-0190(88)90054-3.
  2. ^ Jhala, Randžít; Majumdar, Rupak (2005). Krájení cesty. Sborník konferencí ACM SIGPLAN 2005 o programování a implementaci programovacích jazyků. PLDI '05. New York, NY, USA: ACM. 38–47. doi:10.1145/1065010.1065016. ISBN  9781595930569.
  3. ^ Weiser, Mark David (1979). Plátky programu: Formální, psychologické a praktické vyšetřování metody automatické abstrakce programu (Disertační práce). Ann Arbor, MI, USA: University of Michigan.
  4. ^ Alomari, Hakam W .; Collard, Michael L .; Maletic, Jonathan I .; Alhindawi, Nouh; Meqdadi, Omar (19. 5. 2014). "srcSlice: velmi efektivní a škálovatelné dopředné statické krájení". Journal of Software: Evolution and Process. 26 (11): 931–961. CiteSeerX  10.1.1.641.8891. doi:10.1002 / smr.1651. ISSN  2047-7473.

Reference

  • Mark Weiser. "Programové krájení". Sborník z 5. mezinárodní konference o softwarovém inženýrství, strany 439–449, IEEE Computer Society Press, březen 1981.
  • Mark Weiser. "Programové krájení". Transakce IEEE v softwarovém inženýrství, svazek 10, vydání 4, strany 352–357, IEEE Computer Society Press, červenec 1984.
  • Susan Horwitz, Thomas Reps, a David Binkley, Interprocedural slicing using dependency graphs, ACM Transactions on Programming Languages ​​and Systems, Volume 12, Issue 1, pages 26-60, January 1990.
  • Frank Tip. "Přehled technik krájení programů". Journal of Programming Languages, svazek 3, číslo 3, strany 121–189, září 1995.
  • David Binkley a Keith Brian Gallagher. "Programové krájení". Advances in Computers, svazek 43, strany 1–50, Akademický tisk, 1996.
  • Andrea de Lucia. „Program slicing: Methods and applications“, Mezinárodní seminář o analýze a manipulaci zdrojového kódu, strany 142-149, 2001, IEEE Computer Society Lis.
  • Mark Harman a Robert Hierons. „Overview of program slicing“, Software Focus, svazek 2, vydání 3, strany 85–92, leden 2001.
  • David Binkley a Mark Harman. „An survey of empirical results on program slicing“, Advances in Computers, svazek 62, strany 105-178, Akademický tisk, 2004.
  • Jens Krinke. „Program Slicing“, In Handbook of Software Engineering and Knowledge Engineering, Volume 3: Recent Advances. World Scientific Publishing, 2005
  • Silva, Josepe. „Slovník technik založených na krájení programů“, ACM Computing Surveys, svazek 44, vydání 3, Sdružení pro výpočetní techniku, Červen 2012
  • Alomari HW et al. "srcSlice: velmi efektivní a škálovatelné dopředné statické krájení". Wiley Journal of Software: Evolution and Process (JSEP), DOI: 10,1002 / smr.1651, roč. 26, No. 11, pp. 931-961, 2014.

externí odkazy