slicing programa - Program slicing

Para outros usos de "fatiamento", ver fatiamento (disambiguation) .

Na programação de computador , programa de corte é o cálculo do conjunto de instruções do programa, a fatia programa , que pode afetar os valores em algum ponto de interesse, referido como um critério de corte . Slicing programa pode ser usado na depuração para localizar origem de erros mais facilmente. Outras aplicações de corte incluem manutenção de software , otimização , análise de programa e controle de fluxo de informações .

Técnicas que cortam têm visto um rápido desenvolvimento desde a definição original por Mark Weiser . Na primeira, o corte foi de apenas estática, ou seja, aplicada sobre o código-fonte com nenhuma outra informação do que o código-fonte. Bogdan Korel e Janusz Laski introduziu corte dinâmico , que trabalha em uma execução específica do programa (para um determinado traço de execução). Outras formas de corte existem, por exemplo corte caminho.

corte estática

Com base na definição original de Weiser, informalmente, uma estática fatia programa S consiste de todas as declarações no programa P que podem afetar o valor de v variável em uma instrução x. A fatia é definida para um critério de corte C = (x, v) onde X é uma instrução no programa P e v é variável em x. Uma fatia estática inclui todas as declarações que podem afetar o valor da variável v a declaração x para qualquer entrada possível. fatias estáticos são computadas pelo retrocesso dependências entre as declarações. Mais especificamente, para calcular a fatia estático para (x, v), primeiro encontrar todas as instruções que pode um afetam diretamente o valor de v antes de declaração x é encontrado. Recursiva, para cada declaração y que podem afetar o valor de v na declaração x, calculamos as fatias para todas as variáveis ​​z em y que afetam o valor de v. A união de todas essas fatias é a fatia estático para (x, v) .

Exemplo

Por exemplo, considere o programa C abaixo. Vamos calcular a fatia para (write (soma), sum). O valor da soma é diretamente afetado pelas declarações "soma = soma + i + W" se N> 1 e "soma int = 0" se N <= 1. Assim, fatia (write (soma), soma) é a união de três fatias eo "int sum = 0" declaração que não tem dependências:

  1. fatia (soma = soma + i + w, soma)
    2. ,
  2. fatia (soma = soma + i + w, i)
    3. ,
  3. fatia (soma = soma + i + w, w)
    4. e
  4. {Int sum = 0}.

É bastante fácil ver que fatia (soma = soma + i + W, sum) consiste em "soma = soma + i + w" e "soma int = 0", porque essas são as duas únicas declarações anteriores que podem afetar o valor da soma de "soma = soma + i + w". Da mesma forma, fatia (soma = soma + i + w, i) contém apenas "para (i = 1; i <N; i ++) {" e fatia (soma = soma + i + w, w) contém apenas a instrução "w = int 7".

Quando a união de todas essas declarações, não temos código executável, de modo a tornar a fatia de uma fatia de executável que simplesmente adicionar a chave final para o loop e a declaração do i. A fatia executável resultante estático é mostrado abaixo o código original abaixo. 

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);

A fatia executável estático para critérios ( write(sum), soma) é o novo programa mostrado abaixo. 

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

}
write(sum);

Na verdade, as técnicas de corte mais estáticos, incluindo própria técnica de Weiser, também removerá o write(sum)comunicado. Uma vez que, na declaração write(sum), o valor sumnão é dependente do próprio comunicado. Muitas vezes, uma fatia de um determinado declaração x irá incluir mais de uma variável. Se V é um conjunto de variáveis em um comunicado x, então a fatia para (x, V) é a união de todas as fatias com critérios (x, v) onde v é uma variável no V. set

abordagem de corte estática para a frente leve

Uma abordagem muito rápido e escalável, mas ligeiramente menos preciso, cortando é extremamente útil para uma série de razões. Promotores terá um custo muito baixo e meios práticos para estimar o impacto de uma mudança dentro de minutos, em função dos dias. Isto é muito importante para o planejamento da implementação de novas funcionalidades e entender como uma mudança está relacionada a outras partes do sistema. Também irá fornecer um teste barato para determinar se um completo mais caro, análise do sistema, se justifica. Uma abordagem de corte rápido irá abrir novos caminhos de pesquisa em métricas e da mineração de histórias baseadas em corte. Ou seja, corte agora pode ser realizado em sistemas muito grandes e em toda histórias versão em prazos muito práticas. Isso abre a porta para uma série de experiências e investigações empíricas previamente muito caro para empreender.

corte dinâmico

Faz uso de informações sobre a execução específica de um programa. Uma fatia dinâmico contém todas as instruções que realmente afetam o valor de uma variável em um ponto programa para uma execução particular do programa, em vez de todas as declarações que possam ter afetado o valor de uma variável em um ponto programa para qualquer execução arbitrária do programa.

Um exemplo para esclarecer a diferença entre fatiamento estático e dinâmico. Considere um pequeno pedaço de uma unidade de programa, em que há um bloco de iteração contendo um bloco de if-else. Existem algumas declarações em ambos os ife elseblocos que têm um efeito sobre uma variável. No caso de corte estática, uma vez que toda a unidade de programa é encarado independentemente de uma execução especial do programa, as demonstrações afetadas em ambos os blocos seriam incluídos na fatia. Mas, no caso de corte dinâmica que consideramos uma execução particular do programa, em que o ifbloco é executado e as demonstrações afetados no elsebloco não são executados. Então, é por isso que, neste caso, a execução particular, a fatia dinâmica conteria apenas as declarações no ifbloco.

Veja também

Referências

  • Mark Weiser . "Fatiamento Programa". Proceedings da 5ª Conferência Internacional de Engenharia de Software, páginas 439-449, IEEE Computer Society Press, Março de 1981.
  • Mark Weiser . "Fatiamento Programa". IEEE Transactions on Software Engineering, Volume 10, Issue 4, páginas 352-357, IEEE Computer Society Press, julho 1984.
  • Susan Horwitz , Thomas Reps , e David Binkley, Interprocedimental corte usando gráficos de dependência, ACM Transactions on linguagens de programação e sistemas, Volume 12, Issue 1, páginas 26-60, Janeiro de 1990.
  • Frank Tip. "Uma pesquisa de técnicas de programa de corte". Jornal de linguagens de programação, Volume 3, Issue 3, páginas 121-189, Setembro de 1995.
  • David Binkley e Keith Brian Gallagher. "Fatiamento Programa". Avanços em computadores, Volume 43, páginas 1-50, Academic Press , 1996.
  • Andrea de Lucia. "O programa de corte: métodos e aplicações", Workshop Internacional sobre a fonte de análise de código e manipulação, páginas 142-149, 2001, o IEEE Computer Society Press.
  • Mark Harman e Robert Hierons. "Uma visão geral do programa de corte", Foco Software, Volume 2, Issue 3, páginas 85-92, Janeiro de 2001.
  • David Binkley e Mark Harman. "Uma pesquisa com resultados empíricos sobre fatiamento programa", Advances in Computers, Volume 62, páginas 105-178, Academic Press , 2004.
  • Jens Krinke. "Programa fatiamento", no Manual de Engenharia de Software e Engenharia do Conhecimento, Volume 3: Avanços recentes. Mundo Publishing Scientific de 2005
  • Silva, Josep. "Um vocabulário do programa técnicas baseadas em fatiamento", ACM Computing, Volume 44, Issue 3, Association for Computing Machinery , Junho 2012
  • Alomari HW et al. "srcSlice: muito eficiente e cortar a frente estática escalável". Wiley Journal of Software: Evolução e Processo ( JSEP ), DOI: 10.1002 / smr.1651, Vol. 26, No. 11, pp. 931-961, 2014.
Específico
  1. ^ Korel, Bogdan; Laski, Janusz (1988). "Programa que corta o dinâmico" . Information Processing Letters . 29 (3): 155-163. doi : 10,1016 / 0020-0190 (88) 90054-3 .
  2. ^ Jhala, Ranjit; Majumdar, Rupak (2005). "Caminho fatiamento" . Anais da Conferência SIGPLAN ACM 2005 sobre o design linguagem de programação e implementação . PLDI '05. New York, NY, EUA: ACM: 38-47. doi : 10,1145 / 1.065.010,1065016 . ISBN  9781595930569 .
  3. ^ Weiser, Mark David (1979). Fatias do programa: investigações formais, psicológicos e práticos de um Programa Método Abstraction automática (Tese de Doutoramento tese). Ann Arbor, MI, EUA: Universidade de Michigan.
  4. ^ Alomari, Hakam W .; Couve, Michael L .; Maletic, Jonathan I .; Alhindawi, Nouh; Meqdadi, Omar (2014/05/19). "srcSlice: muito eficiente e cortar a frente estática escalável" . Journal of Software: Evolution and Process . 26 (11): 931-961. doi : 10.1002 / smr.1651 . ISSN  2047-7473 .

links externos