Fundamentos Lógicos de la Ingeniería del Software

Parte I: Métodos formales de transformación de programas. Evaluación parcial        Germán Vidal
Parte II: Programación Lógica Inductiva        María José Ramírez





Parte I: Métodos formales de transformación de programas. Evaluación parcial

Intoducción

En esta parte del curso de doctorado se estudian los fundamentos de las técnicas de transformación de programas. Desde un punto de vista general, estas técnicas estudian todos aquellos métodos que permitan modificar de algún modo los programas, preservando algún tipo de equivalencia entre la semántica (el significado) del programa original y el transformado. Este es el caso, por ejemplo, de los compiladores, ya que éstos transforman un programa fuente en un programa objeto (preservando su semántica). Al igual que en el caso de los compiladores, el objetivo general de estas técnicas es ganar eficiencia en ejecución. Otros ejemplos de técnicas de transformación son: los métodos para convertir procesos recursivos en iterativos (más eficientes), las técnicas de "desenrollado" de bucles, las técnicas de optimización basadas en plegado/desplegado de llamadas y las técnicas de evaluación parcial o especialización, entre otras.

En el curso, nos centraremos en las técnicas de evaluación parcial. El objetivo básico de la evaluación parcial consiste en, dado un programa y parte de sus datos de entrada, generar una versión especializada del programa original para dichos datos de entrada (por ello, a menudo se denominan también técnicas de especialización). Por supuesto, se espera que el programa especializado compute los mismos resultados que el programa original si se fijan los datos de entrada empleados para realizar la evaluación parcial. Es decir, si tenemos un programa P con dos parámetros, in1 e in2, y realizamos la evaluación parcial de P con respecto a in1, obteniendo el programa especializado P_in1, cabe esperar que P(in1,in2) compute los mismos resultados que P_in(in2).

Las técnicas de evaluación parcial se han aplicado a diferentes lenguajes de programación (Prolog, Haskell, Lisp, Scheme, C, Java, etc) y con diferentes propósitos: mejorar la eficiencia de programas (o procedimientos) de propósito general, optimizar bases de datos, mejorar la eficiencia de los algoritmos de cálculo científico, generar compiladores a partir de intérpretes de forma automática, etc.

El curso comienza con una panorámica general sobre la evaluación parcial y, posteriormente, se centra en las técnicas de evaluación parcial de programas funcionales. La simplicidad del lenguaje considerado (y de su semántica) nos permitirá describir los conceptos clave de forma sencilla y abordar, además, cuestiones de corrección, control, eficiencia, etc, lo cual sería muy complejo en el caso de lenguajes de programación más elaborados. De todos modos, muchos de los principios vistos en el curso se trasladan de manera natural al caso de lenguajes más complejos.


Contenidos

  1. Introducción
  2. Conceptos básicos de lenguajes de programación
  3. Evaluación parcial online
  4. Evaluación parcial offline


Material disponible


Para cualquier duda sobre el curso o sobre el material disponible: gvidal_at_dsic.upv.es