Optimización automática de programas

El trabajo en el laboratorio está encaminado a ilustrar en la práctica los conceptos teóricos de la asignatura. El lenguaje empleado será Haskell y, en particular, el entorno Hugs.

Las prácticas a realizar en el laboratorio son:

• Desarrollo de una herramienta de especialización de programas funcionales simples

• Presentación (transparencias)
• Tema 1 (transparencias)
• Tema 2 (transparencias)
• Tema 3 (transparencias)
• Tema 4 (transparencias)
  
  
  
• Examenes de años anteriores:
  • parcial (2005/06)
  • final (2005/06)
  • parcial (2006/07)
  • final (2006/07)
  • parcial (2007/08) (soluciones)
  
  
• Soluciones: mandadme vuestra solución por correo electrónico o, mejor, pasad por el despacho y preguntarme cualquier duda...

Los siguientes recursos pueden ser útiles para el trabajo a desarrollar en el laboratorio

• El lenguaje Haskell
• El entorno Hugs y su manual de usuario
• Breve introducción a Haskell (Salvador Lucas)
• Introducción al lenguaje Haskell (José Labra)
• Haskell for C programmers

Prácticas

• Primera sesión: debéis familiarizaros con el entorno Hugs y escribir algunas funciones simples (usad practica1.lhs)
  Solución: ver enunciado de la siguiente práctica...
• Segunda sesión: se trata de seguir la práctica anterior realizando nuevos ejercicios de manipulación de programas y expresiones (usad practica2.lhs)
  Solución: ver enunciado de la siguiente práctica...
• Tercera sesión: se trata de continuar con la práctiva anterior e implementar el intérprete visto en clase de teoría (usad practica3.lhs)
  Solución: practica3_sols.lhs
• Cuarta sesión: el objetivo de esta sesión consiste en implementar las funciones Bv y Be vistas en clase de teoría. El orden a seguir puede ser, por ejemplo, este:
  1. Primero extiende la definición del tipo de datos Expr para que incluya dos nuevos valores: S y D. De este modo, podremos reutilizar muchas de las funciones ya desarrolladas (en particular, el tipo de datos Env que ahora nos servirá para representar un entorno de binding-times).
  2. Ahora, hay que definir una función que tome una variable y un entorno de binding-times y devuelva el valor S o D de dicha variable de acuerdo al entorno.
  3. Luego, podemos implementar el operador que calcula el lub (least upper bound o menor cota superior) sobre binding-times. Y, a continuación, extenderlo para entornos de binding-times.
  4. Finalmente, ya podemos pasar a implementar las funciones Be y Bv, en este orden.
• Para desarrollar la práctica del evaluador parcial, puedes partir del siguiente fichero conteniendo una versión incompleta del programa
  
  
• NOTA: las respuestas a las llamadas iniciales del fichero deben ser como sigue (al menos, en mi implementación):

  1) main = print (bta ppower [D,S])
  
     [("power",[D,S])]
  
  2) main = print (ann pexamen (bta pexamen [S,D]))
  
     [ADefine f[]["x","y"] = Calld "g" [] [Var "y"]
     ,ADefine g[]["x"] = Calld "f" [] [Var "x",Var "x"]
     ]
    
  3) main = print (mix (ann pexamen (bta pexamen [S,D])) [Con 1])
  
     [Define (f,[Con 1]) ["x","y"] = Call_ ("g",[]) [Var "x"]
     ,Define (g,[]) ["x"] = Call_ ("f",[]) [Var "x",Var "x"]
     ,Define (f,[]) ["x","y"] = Call_ ("g",[]) [Var "y"]
     ]
  
  4) main = print (ann ppower (bta ppower [S,D]))
  
     [ADefine power["x"]["n"] = Ifd (Opd "=" [Var "n",Con 0]) (Con 1) (Opd "*" [Var "x",Calld "power" [Var "x"] [Opd "-" [Var "n",Con 1]]])
     ]
  
  5) main = print (mix (ann ppower (bta ppower [S,D])) [Con 3])
  
     [Define (power,[Con 3]) ["n"] = If (Op "=" [Var "n",Con 0]) (Con 1) (Op "*" [Con 3,Call_ ("power",[Con 3]) [Op "-" [Var "n",Con 1]]])
     ]