Hispanopedia Wiki
Articulo de referencia

Segmentación de programas

En programación informática , el seccionamiento de programas consiste en calcular el conjunto de instrucciones del programa, denominado segmento , que pueden afectar a los valor...

Hispanopedia WikiContenido en espanolLectura gratuita

En programación informática , el seccionamiento de programas consiste en calcular el conjunto de instrucciones del programa, denominado segmento , que pueden afectar a los valores en un punto de interés, conocido como criterio de seccionamiento . El seccionamiento de programas se puede utilizar en la depuración para localizar con mayor facilidad el origen de los errores. Otras aplicaciones del seccionamiento incluyen el mantenimiento de software , la optimización , el análisis de programas y el control del flujo de información .

Las técnicas de segmentación han experimentado un rápido desarrollo desde la definición original de Mark Weiser . Al principio, la segmentación era estática, es decir, se aplicaba al código fuente sin más información que el propio código fuente. Bogdan Korel y Janusz Laski introdujeron la segmentación dinámica , que funciona en una ejecución específica del programa (para un rastro de ejecución determinado). [ 1 ] Existen otras formas de segmentación, como la segmentación de rutas. [ 2 ]

Segmentación estática

Según la definición original de Weiser, [ 3 ] informalmente, una porción estática de programa S consiste en todas las instrucciones del programa P que pueden afectar el valor de la variable v en una instrucción x. La porción se define para un criterio de segmentación C=(x,v), donde x es una instrucción del programa P y v es una variable en x. Una porción estática incluye todas las instrucciones que pueden afectar el valor de la variable v en la instrucción x para cualquier entrada posible. Las porciones estáticas se calculan rastreando las dependencias entre instrucciones. Más específicamente, para calcular la porción estática para (x,v), primero encontramos todas las instrucciones que pueden afectar directamente el valor de v antes de que se encuentre la instrucción x. Recursivamente, para cada instrucción y que puede afectar el valor de v en la instrucción x, calculamos las porciones para todas las variables z en y que afectan el valor de v. La unión de todas esas porciones es la porción estática para (x,v).

Ejemplo

Por ejemplo, consideremos el siguiente programa en C. Calculemos la porción para (write(sum), sum). El valor de sum se ve directamente afectado por las instrucciones "sum = sum + i + w" si N>1 y "int sum = 0" si N <= 1. Por lo tanto, slice(write(sum), sum) es la unión de tres porciones y la instrucción "int sum = 0", que no tiene dependencias:

  1. rebanada( suma = suma + i + w, suma),
  2. rebanada( suma = suma + i + w, i),
  3. rebanada( suma = suma + i + w, w), y
  4. { int suma=0 }.

Es bastante fácil ver que slice( sum = sum + i + w, sum) consta de "sum = sum + i + w" e "int sum = 0" porque esas son las únicas dos instrucciones previas que pueden afectar el valor de sum en "sum = sum + i + w". De manera similar, slice( sum = sum + i + w, i) solo contiene "for(i = 1; i < N; ++i) {" y slice( sum = sum + i + w, w) solo contiene la instrucción "int w = 7".

Al unir todas esas instrucciones, no obtenemos código ejecutable. Por lo tanto, para convertir la porción en una porción ejecutable, simplemente agregamos la llave de cierre del bucle for y la declaración de i. La porción ejecutable estática resultante se muestra debajo del código original.

int i ; int suma = 0 ; int producto = 1 ; int w = 7 ; for ( i = 1 ; i < N ; ++ i ) { suma = suma + i + w ; producto = producto * i ; } escribir ( suma ); escribir ( producto );

La porción ejecutable estática para criterios ( write(sum), suma) es el nuevo programa que se muestra a continuación.

int i ; int suma = 0 ; int w = 7 ; for ( i = 1 ; i < N ; ++ i ) { suma = suma + i + w ; } escribir ( suma );

De hecho, la mayoría de las técnicas de segmentación estática, incluida la técnica de Weiser, también eliminan la write(sum)instrucción. Dado que, en la instrucción write(sum), el valor de sumno depende de la instrucción en sí. A menudo, una segmentación para una instrucción particular x incluirá más de una variable. Si V es un conjunto de variables en una instrucción x, entonces la segmentación para (x, V) es la unión de todas las segmentaciones con el criterio (x, v) donde v es una variable en el conjunto V.

Enfoque de segmentación estática directa y ligera

Un enfoque de segmentación muy rápido y escalable, aunque ligeramente menos preciso, resulta extremadamente útil por varias razones. Los desarrolladores dispondrán de un medio práctico y de bajo coste para estimar el impacto de un cambio en cuestión de minutos, en lugar de días. Esto es fundamental para planificar la implementación de nuevas funcionalidades y comprender cómo se relaciona un cambio con otras partes del sistema. Además, proporcionará una prueba económica para determinar si se justifica un análisis completo y más costoso del sistema. Un enfoque de segmentación rápido abrirá nuevas vías de investigación en métricas y minería de historiales basados ​​en la segmentación. Es decir, ahora se puede realizar la segmentación en sistemas muy grandes y en historiales de versiones completos en plazos muy prácticos. Esto abre la puerta a una serie de experimentos e investigaciones empíricas que antes eran demasiado costosos de llevar a cabo. [ 4 ]

Segmentación dinámica

El segmentado dinámico utiliza información sobre una ejecución particular de un programa. Un segmento dinámico contiene todas las instrucciones que afectan realmente el valor de una variable en un punto específico del programa durante una ejecución determinada, en lugar de todas las instrucciones que podrían haber afectado el valor de una variable en un punto específico del programa durante cualquier ejecución arbitraria.

Un ejemplo para aclarar la diferencia entre segmentación estática y dinámica. Consideremos una pequeña parte de una unidad de programa, que contiene un bloque de iteración con una estructura if-else. Hay algunas instrucciones en ambos ifbloques elseque afectan a una variable. En el caso de la segmentación estática, dado que se considera toda la unidad de programa independientemente de la ejecución, las instrucciones afectadas en ambos bloques se incluirían en la segmentación. En cambio, en la segmentación dinámica, se considera una ejecución específica del programa, donde el ifbloque se ejecuta, pero las instrucciones afectadas elseno. Por lo tanto, en este caso particular, la segmentación dinámica contendría únicamente las instrucciones del ifbloque.

Véase también

Notas

  1. ↑ Korel, Bogdan; Laski, Janusz (1988). "Dynamic Program Slicing". Information Processing Letters . 29 (3): 155– 163. CiteSeerX 10.1.1.158.9078 . doi : 10.1016/0020-0190(88)90054-3 . 
  2. ↑ Jhala, Ranjit; Majumdar, Rupak (2005). "Path slicing". Actas de la conferencia ACM SIGPLAN de 2005 sobre diseño e implementación de lenguajes de programación . PLDI '05. Nueva York, NY, EE. UU.: ACM. págs. 38–47 . doi : 10.1145/1065010.1065016 . ISBN  9781595930569. S2CID 5065847 . 
  3. ↑ Weiser, Mark David (1979). Program Slices: Formal, Psychological, and Practical Investigations of an Automatic Program Abstraction Method (Tesis doctoral). Ann Arbor, MI, EE. UU.: Universidad de Michigan.
  4. ↑ Alomari, Hakam W.; Collard, Michael L.; Maletic, Jonathan I.; Alhindawi, Nouh; Meqdadi, Omar (2014-05-19). "srcSlice: segmentación estática directa muy eficiente y escalable". Journal of Software: Evolution and Process . 26 (11): 931– 961. CiteSeerX 10.1.1.641.8891 . doi : 10.1002/smr.1651 . ISSN 2047-7473 . S2CID 18520643 .   

Referencias

  • Mark Weiser . "Program slicing". Actas de la 5ª Conferencia Internacional sobre Ingeniería de Software, páginas 439-449 , IEEE Computer Society Press, marzo de 1981.
  • Mark Weiser . "Program slicing". IEEE Transactions on Software Engineering, Volumen 10, Número 4, páginas 352-357 , IEEE Computer Society Press, julio de 1984.
  • Susan Horwitz , Thomas Reps y David Binkley, Segmentación interprocedimental mediante grafos de dependencia, ACM Transactions on Programming Languages ​​and Systems, Volumen 12, Número 1, páginas 26-60, enero de 1990.
  • Frank Tip. "Un estudio sobre técnicas de segmentación de programas". Journal of Programming Languages, Volumen 3, Número 3, páginas 121–189, septiembre de 1995.
  • David Binkley y Keith Brian Gallagher. "Segmentación de programas". Advances in Computers, Volumen 43, páginas 1–50, Academic Press , 1996.
  • Andrea de Lucia. "Program slicing: Methods and applications", International Workshop on Source Code Analysis and Manipulation, páginas 142-149, 2001, IEEE Computer Society Press.
  • Mark Harman y Robert Hierons. "Una visión general de la segmentación de programas", Software Focus, Volumen 2, Número 3, páginas 85-92, enero de 2001.
  • David Binkley y Mark Harman. "Un estudio de los resultados empíricos sobre la segmentación de programas", Advances in Computers, Volumen 62, páginas 105-178, Academic Press , 2004.
  • Jens Krinke. «Program Slicing», en Handbook of Software Engineering and Knowledge Engineering, Volumen 3: Recent Advances. World Scientific Publishing , 2005.
  • Silva, Josep. "Un vocabulario de técnicas basadas en la segmentación de programas", ACM Computing Surveys, Volumen 44, Número 3, Association for Computing Machinery , junio de 2012.
  • Alomari HW et al. "srcSlice: segmentación estática directa muy eficiente y escalable". Wiley Journal of Software: Evolution and Process ( JSEP ), DOI: 10.1002/smr.1651, vol. 26, n.º 11, págs. 931-961, 2014.
  • Proyecto VALSOFT/Joana
  • Proyecto Indus (parte del tablero de ajedrez Bandera)
  • Proyecto de segmentación de programas de Wisconsin