Krojenie programu

Aby zapoznać się z innymi zastosowaniami „krojenia”, zobacz Krojenie (ujednoznacznienie) .

W programowaniu komputerowym cięcie programu to obliczanie zestawu instrukcji programu, wycinka programu , który może wpływać na wartości w pewnym punkcie zainteresowania, określanym jako kryterium krojenia . Dzielenie programów może być używane podczas debugowania w celu łatwiejszego lokalizowania źródła błędów. Inne zastosowania dzielenia obejmują konserwację oprogramowania , optymalizację , analizę programu i kontrolę przepływu informacji .

Techniki krojenia szybko się rozwijają od czasu pierwotnej definicji Marka Weisera . Początkowo cięcie było tylko statyczne, tj. stosowane do kodu źródłowego bez żadnych innych informacji poza kodem źródłowym. Bogdan Korel i Janusz Laski wprowadzili dynamiczne cięcie , które działa na określone wykonanie programu (dla danego śladu wykonania). Istnieją inne formy krojenia, na przykład krojenie ścieżki.

Cięcie statyczne

Opierając się na oryginalnej definicji Weisera, nieformalnie statyczny wycinek programu S składa się ze wszystkich instrukcji w programie P, które mogą wpływać na wartość zmiennej v w instrukcji x. Wycinek jest zdefiniowany dla kryterium krojenia C=(x,v), gdzie x jest instrukcją w programie P, a v jest zmienną w x. Wycinek statyczny zawiera wszystkie instrukcje, które mogą wpływać na wartość zmiennej v w instrukcji x dla dowolnego możliwego wejścia. Wycinki statyczne są obliczane przez wycofywanie zależności między instrukcjami. Mówiąc dokładniej, aby obliczyć przekrój statyczny dla (x, v), najpierw znajdujemy wszystkie instrukcje, które mogą bezpośrednio wpływać na wartość v, zanim napotkamy instrukcję x. Rekurencyjnie, dla każdej instrukcji y, która może wpływać na wartość v w instrukcji x, obliczamy przekroje dla wszystkich zmiennych z w y, które wpływają na wartość v. Suma wszystkich tych wycinków jest przekrojem statycznym dla (x, v) .

Przykład

Rozważmy na przykład program C poniżej. Obliczmy wycinek dla ( write(sum), sum ). Na wartość sumy mają bezpośredni wpływ instrukcje „sum = sum + i + w”, jeśli N>1 i „int sum = 0”, jeśli N <= 1. Tak więc, slice( write(sum), sum) jest sumą z trzech wycinków i instrukcja „int sum = 0”, która nie ma zależności:

  1. wycinek( suma = suma + i + w, suma)
    2. ,
  2. wycinek( suma = suma + i + w, i)
    3. ,
  3. wycinek( suma = suma + i + w, w)
    4. , I
  4. { całkowita suma=0 }.

Dość łatwo zauważyć, że slice( sum = sum + i + w, sum) składa się z „sum = sum + i + w” i „int sum = 0”, ponieważ są to jedyne dwie wcześniejsze instrukcje, które mogą wpływać na wartość sumy w punkcie „suma = suma + i + w”. Podobnie, slice( sum = sum + i + w, i) zawiera tylko „for(i = 1; i < N; ++i) {”, a slice( sum = sum + i + w, w) zawiera tylko instrukcję "int w = 7".

Kiedy połączymy wszystkie te instrukcje, nie mamy kodu wykonywalnego, więc aby wycinek był wykonywalny, wystarczy dodać nawias końcowy dla pętli for i deklarację i. Wynikowy statyczny wycinek pliku wykonywalnego jest pokazany poniżej oryginalnego kodu.

 
   0
   
   
       
        
      

 int  ja  ;  int  suma  =  ;  int  iloczyn  =  1  ;  int  w  =  7  ;  dla  (  ja  =  1  ;  ja  <  N  ;  ++  ja  )  {  suma  =  suma  +  ja  +  w  ;  produkt  =  produkt  *  i  ;  }  napisz  (  suma  ); 
 pisać  (  produkt  );

Statyczny fragment pliku wykonywalnego dla kryteriów ( write(sum) , sum) to nowy program pokazany poniżej. 

 
   0
   
       
        


 int  ja  ;  int  suma  =  ;  int  w  =  7  ;  dla  (  ja  =  1  ;  ja  <  N  ;  ++  ja  )  {  suma  =  suma  +  ja  +  w  ;  }  napisz  (  suma  );

W rzeczywistości większość statycznych technik krojenia, w tym własna technika Weisera, usuwa również instrukcję write(sum) . Ponieważ w instrukcji write(sum) wartość sumy nie zależy od samej instrukcji. Często wycinek dla określonej instrukcji x będzie zawierał więcej niż jedną zmienną. Jeśli V jest zbiorem zmiennych w instrukcji x, to wycinek dla (x, V) jest sumą wszystkich wycięć z kryteriami (x, v), gdzie v jest zmienną w zbiorze V.

Lekkie podejście do statycznego krojenia do przodu

Bardzo szybkie i skalowalne, ale nieco mniej dokładne podejście do krojenia jest niezwykle przydatne z wielu powodów. Deweloperzy będą dysponować bardzo tanimi i praktycznymi sposobami oszacowania wpływu zmiany w ciągu kilku minut, a nie dni. Jest to bardzo ważne dla zaplanowania implementacji nowych funkcji i zrozumienia, w jaki sposób zmiana jest powiązana z innymi częściami systemu. Zapewni również niedrogi test w celu ustalenia, czy uzasadniona jest pełna, droższa analiza systemu. Podejście do szybkiego krojenia otworzy nowe możliwości badań w zakresie metryk i eksploracji historii w oparciu o krojenie. Oznacza to, że cięcie można teraz przeprowadzać na bardzo dużych systemach i na całych historiach wersji w bardzo praktycznych ramach czasowych. Otwiera to drzwi do wielu eksperymentów i badań empirycznych, które wcześniej były zbyt kosztowne.

Dynamiczne cięcie

Wykorzystuje informacje o konkretnym wykonaniu programu. Wycinek dynamiczny zawiera wszystkie instrukcje, które faktycznie wpływają na wartość zmiennej w punkcie programu dla określonego wykonania programu, a nie wszystkie instrukcje, które mogły wpłynąć na wartość zmiennej w punkcie programu dla dowolnego wykonania programu.

Przykład wyjaśniający różnicę między krojeniem statycznym i dynamicznym. Rozważmy mały fragment jednostki programu, w którym znajduje się blok iteracyjny zawierający blok if-else. Istnieje kilka instrukcji zarówno w if , jak i else , które mają wpływ na zmienną. W przypadku podziału statycznego, ponieważ cała jednostka programu jest rozpatrywana niezależnie od konkretnego wykonania programu, instrukcje, których to dotyczy, w obu blokach zostaną uwzględnione w wycięciu. Ale w przypadku dynamicznego krojenia rozważamy konkretne wykonanie programu, w którym if blok zostanie wykonany, a odpowiednie instrukcje w bloku else nie zostaną wykonane. Dlatego w tym konkretnym przypadku wykonania dynamiczny wycinek zawierałby tylko instrukcje w bloku if .

Zobacz też

Notatki

  • Marka Weisera . „Cięcie programu”. Materiały z 5. Międzynarodowej Konferencji Inżynierii Oprogramowania, strony 439–449, IEEE Computer Society Press, marzec 1981.
  • Marka Weisera . „Cięcie programu”. IEEE Transactions on Software Engineering, tom 10, wydanie 4, strony 352–357, IEEE Computer Society Press, lipiec 1984.
  • Susan Horwitz , Thomas Reps i David Binkley, Interprocedural cięcie przy użyciu wykresów zależności, ACM Transactions on Programming Languages ​​and Systems, tom 12, wydanie 1, strony 26-60, styczeń 1990.
  • Franek Porada. „Przegląd technik krojenia programów”. Journal of Programming Languages, tom 3, wydanie 3, strony 121–189, wrzesień 1995.
  • Davida Binkleya i Keitha Briana Gallaghera. „Cięcie programu”. Postępy w komputerach, tom 43, strony 1–50, Academic Press , 1996.
  • Andrzeja Łucji. „Podział programu: metody i zastosowania”, Międzynarodowe warsztaty dotyczące analizy i manipulacji kodem źródłowym, strony 142-149, 2001, IEEE Computer Society Press.
  • Marka Harmana i Roberta Hieronsa. „Przegląd krojenia programów”, Software Focus, tom 2, wydanie 3, strony 85–92, styczeń 2001.
  • Davida Binkleya i Marka Harmana. „Ankieta wyników empirycznych dotyczących krojenia programów”, Advances in Computers, tom 62, strony 105-178, Academic Press , 2004.
  • Jensa Krinkego. „Podział programu”, w Podręczniku inżynierii oprogramowania i inżynierii wiedzy, tom 3: Ostatnie postępy. Światowe wydawnictwa naukowe , 2005
  • Silva, Józef. „Słownictwo technik opartych na dzieleniu programów”, ACM Computing Surveys, tom 44, wydanie 3, Association for Computing Machinery , czerwiec 2012
  • Alomari HW i in. „srcSlice: bardzo wydajne i skalowalne cięcie statyczne do przodu” . Wiley Journal of Software: Ewolucja i proces ( JSEP ), DOI: 10.1002/smr.1651, tom. 26, nr 11, s. 931-961, 2014.

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Program_slicing&oldid=1142342542 ”