Programación Funcional

english version

Objetivos

El paradigma de programación funcional es uno de los fundamentales entre los llamados de programación declarativa. Como tal, permite aunar los componentes de especificación y programación en las tareas de solución automática de problemas.

Los lenguajes funcionales ofrecen al programador un buen número de recursos expresivos que permiten resolver problemas complejos mediante programas pequeños y robustos. Entre ellos cabe destacar: un sistema de tipos polimórficos que permite definir una amplia variedad de estructuras de datos de uso genérico, la posibilidad de definir funciones que aceptan otras funciones como argumentos y devuelven funciones como resultado, facilidades para definir y manipular estructuras de datos infinitas, un modelo computacional simple, claro y bien fundamentado, etc. De no menor importancia es la posibilidad de razonar, de forma sencilla, acerca de las propiedades de los programas: su corrección, su eficacia, su comportamiento en ejecución, ... Esto permite optimizar las tareas de implementación de los lenguajes funcionales.

Podemos encontrar, en casi todos los lenguajes de programación funcional, un núcleo común de conceptos y técnicas asentado sobre bases firmemente establecidas. En esta asignatura estudiamos los fundamentos de la programación funcional y su utilización en la definición de implementaciones correctas y eficientes de los lenguajes de programación que se enmarcan en este paradigma.

Temario

1. Introducción a la Programación Funcional.
   1.1. Lenguajes funcionales como lenguajes de programación.
   1.2. Historia y evolución de los lenguajes funcionales.
   1.3. Ventajas e inconvenientes de los lenguajes funcionales.
   1.4. Aplicaciones.
   

2. Un lenguaje funcional avanzado: Haskell.
   2.1. Introducción a Haskell.
   2.2. Nivel léxico.
   2.3. Expresiones.
   2.4. Declaraciones.
   

3. Estructuras de datos en los lenguajes funcionales.
   3.1. Tipos simples y tipos numéricos.
   3.2. Tipos algebraicos y polimorfismo.
   3.3. Tipos funcionales: orden superior, definición de funciones.
   3.4. Listas y árboles.
   3.5. Tipos abstractos de datos.
   

4. Modelos de ejecución de los programas funcionales.
   4.1. Reducción y evaluación en programas funcionales.
   4.2. El cálculo lambda.
   4.3. La lógica combinatoria.
   4.4. Estrategias de reducción en el cálculo lambda.
   

5. Significado de los programas funcionales.
   5.1. Semántica denotacional de los lenguajes funcionales.
   5.2. Razonamiento acerca de las propiedades de los programas funcionales.
   5.3. Interpretación abstracta de lenguajes funcionales.
   

6. Implementación y optimización.
   6.1. Técnicas de implementación de los lenguajes funcionales.
   6.2. Transformación de programas.
   6.3. Otras técnicas de optimización.
   

Prácticas

Las prácticas persiguen consolidar el conocimiento adquirido sobre los lenguajes funcionales y sus peculiaridades expresivas. Consistirán en la realización de pequeños programas que permitan bosquejar las posibilidades de aplicación de estos lenguajes a problemas de actualidad tales como el desarrollo de aplicaciones multimedia que incluyan gráficos, animaciones, música, etc. El entorno de programación utilizado es Hugs, una implementacion de Haskell sobre Windows95.

Evaluación

Examen sobre los contenidos teóricos de la asignatura y valoración de las prácticas realizadas. Trabajos personales.

Bibliografía

[Bir00] R. Bird. Introducción a la Programación Funcional con Haskell. Prentice-Hall, 2000.

[Dav92] A.J.T. Davie. An Introduction to Functional Programming Systems Using Haskell. Cambridge University Press, 1992.

[Hud00] P. Hudak. The Haskell School of Expression. Learning functional programming through multimedia. Cambridge University Press, 2000.

[PE93] R. Plasmeijer and M. van Eekelen. Functional Programming and Parallel Graph Rewriting. Addison-Wesley, 1993.

[Pey87] S.L. Peyton-Jones. The implementation of Functional Programming Languages. Prentice-Hall, 1987.

[Rea93] C. Reade. Elements of Functional Programming. Addison-Wesley, 1993.

[Tho99] S. Thompson. Haskell. The Craft of Functional Programming. Addison-Wesley, 1999.

URLs de interés

Programación funcional en la red:

http://cm.bell-labs.com/cm/cs/who/wadler/guide.html

http://haskell.org/

Otras URLs de interés

Grupo de programación funcional del RWTH Aachen (Alemania)
Grupo de programación funcional de la Universidad de Glasgow (Reino Unido)
Programación funcional en la Universidad Complutense de Madrid
Programación funcional en la Universidad de Málaga
Grupo de programación funcional de la Universidad de Nimega (Holanda)
Grupo de programación funcional de la Universidad de Yale (EEUU)