Program Slicing
Program Slicing
Patrick Machado
Programação funcional avançada
Program Slicing
Conteúdo
•
•
•
•
•
O que é?
Dependências
Slicing estático
Slicing dinâmico
Métodos
– Equações de fluxo de dados
– Grafos de dependências
– Eficiência
• Aplicação
– Aplicação ao trabalho
• Bibliografia
Programação funcional avançada
Program Slicing
O que é?
• Mecanismo para particionar um programa
em partes independentes.
• Um slice ou partição consiste em todos os
‘statements’ do programa que podem afectar
o valor da computação num determinado
‘statement’.
• Essa partição é definida segundo o critério
de slicing.
Programação funcional avançada
Program Slicing
Dependências
• Dependências de dados
x = 1;
y = x;
• Dependêcias de controlo
if(n==2)
X = 3;
Programação funcional avançada
Program Slicing
Slicing estático
• É usada apenas
informação disponível
estaticamente
• Critério especifica o
statement e o conjunto
de variáveis relevantes.
x = 1;
y = x + 2;
x = 10;
output(x)
output(y)
C = ( 5, {y})
Programação funcional avançada
Program Slicing
Slicing dinâmico
• É utilizada uma
determinada instância
do programa.
• O critério tem em conta
o input, o statement
relevante e o conjunto
de variáveis.
Programação funcional avançada
x = 2;
if(x == 2)
{
y = x;
}
else
{
y = x + 1;
}
output(y)
C = ({x==2}, 10, {y})
Program Slicing
Métodos
• Equações de fluxo de dados
– Calculam-se conjuntos sucessivos de
‘statements’ indirectamente relevantes, de
acordo com as dependências
• Grafos de dependências
– Constrói-se um grafo com as dependências.
• Nos -> ‘statements’
• Arcos -> dependências
Programação funcional avançada
Program Slicing
Equações de fluxo de dados
No
Def
Ref
Infl
1
{x}
{}
{}
soma = 0;
2
{y}
{x}
{}
while(i < 10)
3
{soma}
{}
{}
4
{}
{i}
{5}
5
{soma}
{soma,
i}
{}
6
{}
{soma}
{}
x = 1;
y = x + 2;
soma = soma + i;
output(soma)
Programação funcional avançada
Program Slicing
Grafos de dependências
x = 1;
y = x + 2;
x = 10;
output(x)
output(y)
Programação funcional avançada
Program Slicing
Eficiência
• Tempo polinomial
– Equações de fluxo de dados
• O(v * n * e)
– Grafos de dependências
• O(n * e)
Programação funcional avançada
Program Slicing
• Debug
Aplicação
– Ignorar ‘statements’ que não interferem no resultado
pretendido
– Observar os ‘statements’ afectados por uma possível
alteração
• Manutenção (integração e diferenciação)
– Tratamento de diferentes versões. Verificação de
componentes equivalentes
– Integração de versões modificadas relativamente à base
• Paralelismo
– Determinar secções independentes do programa para
serem executados em paralelo.
• …
Programação funcional avançada
Program Slicing
Aplicação ao projecto
• Construção de grafos
de dependências
– Relações explícitas
entre tipos
– Relações implícitas
• Invocações de métodos
• Possivelmente ao nível
do ‘statement’
• Slicing e chopping
através do grafo de
dependências
Programação funcional avançada
Program Slicing
Bibliografia
• A Survey of Program Slicing Techniques,
Frank Tip, 19942.
• The Use of Program Dependence Graphs in
Software Engineering, Susan Horwits and
Thomas Reps, 19923.
• Graph Theoretic Foundations of Program
Slicing and Integration, Arun Lakhotia,
1993
Programação funcional avançada