Programación Funcional
Publicación de notas provisionales el miércoles 22 de Febrero de 2006
En esta página web se incluye información
sobre la asignatura optativa Programación Funcional, correspondiente
a las titulaciones de Ingeniero Técnico en Informática de
Sistemas e Ingeniero Técnico en Informática de Gestión.
La asignatura depende del Departamento
de Sistemas Informáticos y Programación de la
Facultad de Informática de la
Universidad
Complutense de Madrid.
El objetivo de la asignatura es introducir el estilo de programación
funcional, capacitando a los alumnos para aplicarlo al tratamiento de
algoritmos y estructuras de datos en aplicaciones de complejidad media.
Existen multitud de documentos describiendo las
ventajas de la
programación funcional .
Una motivación muy
clásica de la necesidad de utilizar
lenguajes funcionales puede encontrarse en el artículo de
John Hughes,
Why Functional Programming Matters,
y otra aún más clásica es la charla impartida
por John Backus
al ser galardonado en 1977 con el
premio Turing.
Su conferencia
Can Programming be Liberated from the Von Neumann Style? A Functional
Style and Its Algebra of Programs en el acto de entrega del mencionado
premio es todo un clásico.
El lenguaje de programación sobre el que se articula la asignatura
es el lenguaje funcional perezoso Haskell,
lenguaje para el que existen diversos compiladores e intérpretes
de libre distribución, y que se ha convertido en el estándar
de facto en el área de los lenguajes funcionales perezosos.
Puede encontrarse una muy buena introducción al uso del lenguaje
en A Gentle Introduction to Haskell.
Documentación del curso:
Temario de la asignatura
Introducción
Comenzando a programar
- Inicialmente, lo más recomendable es empezar utilizando
un intérprete en vez de un compilador. En este sentido, recomiendo
instalar hugs. Este intérprete
es fácil de instalar y usar. Además está disponible
para distintos sistemas operativos que incluyen Windows, Linux y Mac.
- Para facilitar la consulta de cuestiones básicas y simples del
lenguaje, estoy escribiendo unas páginas de ayuda
(en construcción) describiendo las principales construcciones del
lenguaje, así como algunos errores típicos que suelen cometerse.
- El fichero patata.hs contiene algunas definiciones de funciones que podeis utilizar para comenzar a utilizar el sistema. Probad a introducir errores intencionadamente para ver el tipo de mensajes que proporciona el sistema. Probad también a introducir las declaraciones de tipos para aquellas funciones en las que no se ha proporcionado. Comparad los tipos proporcionados con los que infiere el sistema (para ello, eliminad la declaración de tipos y preguntad el tipo al intérprete mediante :t nombre_funcion).
Utilidades para programar:
- Ayuda: Páginas con ayuda muy simple para los primeros pasos en el uso del lenguaje de programación
- Editor Emacs:
Aunque puede usarse cualquier editor de textos para escribir programas en Haskell,
Emacs cuenta con la ventaja de que además de ser un muy buen editor
permite adaptarlo fácilmente para que trate de forma especial la
sintaxis de cualquier lenguaje de programación. Así, existen
modos emacs para todo tipo de lenguajes (C, Java, etc) incluyendo
Haskell. El editor emacs suele venir preinstalado en linux, mientras que
si usas windows puedes descargártelo de la página de emacs.
- Emacs para windows
- Modo para Haskell: Si usas Linux-Debian sólo tienes que hacer apt-get install haskell-mode. Después de instalar el modo, cada vez que abras un fichero con extensión hs, el editor automáticamente usará colores distintos para los distintos tipos de construcciones del lenguaje, y además
te proporcionará ayuda sobre la sintaxis que debes utilizar cada
vez que estés declarando algo nuevo. Además, si has declarado
el tipo de una función cualquiera, cada vez que quieras usarla se te
informará del tipo que tiene.
Si usas Windows, sigue las instrucciones de la página web anterior.
Hojas de ejercicios:
Práctica:
El 20% de la nota final del curso vendrá dado por la realización de una práctica. Salvo excepciones debidamente justificadas, la práctica se realizará en grupos de 2 alumnos. Cada grupo deberá proponer la práctica que van a realizar, que deberá ser distinta de las práctica de todos los demás grupos. Ejemplos de posibles prácas son las siguientes:
- Programa que manipule autómatas finitos y expresiones regulares, y que por ejemplo transforme de expresión regular a autómata finito determinista mínimo.
- Programa que juegue a las 4 en raya.
- Repertorio de programas que incluya un conjunto suficientemente amplio de problemas típicos de MTP.
- Repertorio de estructuras de datos típicas de EDI, junto con algunos programas que las usen.
- Repertorio de algoritmos de manipulación de grafos (recorridos, búsqueda de caminos mínimos, etc).
- Manipulación de gramáticas incontextuales.
- Simulador de una máquina de Turing.
Cada grupo deberá presentar una propuesta de práctica no más tarde del 18 de enero, y la práctica realizada se entregará no más tarde del momento en el que se realice el examen final de la asignatura en Febrero.
Prácticas ya asignadas
Enlaces a páginas sobre programación funcional:
Dirección:
Fernando Rubio Diez
Departamento de Sistemas Informáticos y Programación
Facultad de Informática
Universidad Complutense
C/. Profesor José García Santesmases, s/n
28040 Madrid
Tfno: +34-91-3947629
Fax: +34-91-3947529
e-mail: fernando@sip.ucm.es