Programación Funcional Avanzada (CI-4251)

Este es un curso electivo libre del área de Lenguajes de Programación que se ofrece una vez al año en el trimestre Abril-Julio. Como se trata de una electiva libre, supongo que Ud. está interesado en el tema, así que no se trata de «pasar» sino de ver cuán dedicado e interesado está en el tema, y la calidad del trabajo resultante. Por lo tanto, a menos que Ud. no haga absolutamente nada durante el trimestre, seguramente aprobará la asignatura con tres (3) si cumple con las tareas. Alcanzar el cuatro (4) o el cinco (5) dependerá de producir programas de maneras creativas y con desempeño notable.

Herramientas de Programación

Usaremos el lenguaje de programación Haskell para desarrollar las soluciones a las tareas propuestas. Dependiendo de la audiencia y el avance del curso, se estudiará Erlang para el nicho específico de programación concurrente distribuida.

Haskell

Trabajaremos con GHC, el entorno interactivo del Glasgow Haskell Compiler y su librería base. Adicionalmente, la herramienta de gestión de dependencias y aplicaciones stack. La versión particular de GHC será indicada durante la primera sesión.

Siga las instrucciones en la página de descargas para instalar GHC y stack.

Todos los archivos que formen parte de su proyecto deben estar completa y correctamente documentados (los errores ortográficos son inaceptables y serán penalizados) utilizando «Literate Haskell»:

• El programa se entrega como un archivo .lhs que incluye el código Haskell combinado con el texto e instrucciones LaTeX para formato.

• El archivo tiene que poder cargarse en ghci o compilarse con ghc --make sin inconvenientes.

• El archivo tiene que poder ser procesado con

  pdflatex solucion.lhs

  para generar un archivo PDF en el cual leer la descripción de la solución junto con el código fuente. Si usa Debian 8 o un Ubuntu reciente, la generación a PDF depende de los paquetes

  aptitude install texlive-latex-base texlive-latex-extra pgf

• Los errores ortográficos y el «va sin acentos» son inaceptables y serán penalizados.

Si alguna de las tareas incluye la construcción de uno o más módulos, estos deben estar completa y correctamente documentados usando Haddock:

• Descripción del módulo identificando propósito, materia, grupo y entrega.

• Descripción de todos los nombres exportados por el módulo.

• Descripción funcional (qué hace) de cada función exportada, incluyendo la descripción semántica (qué representa) cada argumento y el valor resultante de la función.

• Para funciones complejas, es conveniente que agregue una descripción operativa (cómo lo hace) como un comentario interno en el código fuente.

La documentación de Haddock abunda en detalles acerca de las marcas a utilizar para lograr estos resultados.

La evaluación de sus proyectos tomará en cuenta el uso correcto del estilo funcional, el aprovechamiento de las librerías del lenguaje (no reimplantar cosas que existen), y la eficiencia algorítmica. No basta «que funcione»; tiene que ser eficiente.

Tareas

Las tareas son individuales. Habrá seis o siete tareas a lo largo del trimestre.

Si encuentran en biblioteca, hemeroteca o Internet un artículo, fragmento o aplicación que resuelva total o parcialmente sus proyectos, es válido utilizarlo siempre y cuando cumpla con dos condiciones simultáneamente:

• Cite completa y correctamente el origen del trabajo (dónde lo encontró y quién lo escribió originalmente).

• Prepárese a explicarlo completamente en revisión personal.

Resolver problemas apoyándose en soluciones de otros es perfectamente válido, siempre y cuando se tenga el coraje académico de reconocerlo.

Cronograma Habitual y Material de Apoyo

El orden de las primeras doce sesiones siempre es el mismo. El resto de las sesiones puede variar dependiendo de los intereses del grupo y de los cambios en la tecnología.

Solamente están disponibles las láminas de la última oportunidad en que se dictó el curso. Las versiones de cursos anteriores no están disponibles, no insista. Si durante alguna clase se hacen correcciones o agregados, espere encontrar la versión corregida aquí eventualmente.

El material de apoyo consiste en fragmentos de código presentado en clase. La mayoría de los ejemplos en las láminas no están provistos, con la intención de que Ud. tenga que escribirlos para experimentar por su cuenta.

Láminas de Clase

• Pensamiento Funcional

• Contexto con tenedores

  • Monoid
  • Functor
  • Applicative

• Morfismos

  • Catamorfismos (fold).
  • Anamorfismos (unfold).
  • Hylomorfismos (refold fusion)
  • Data.Foldable

• Zippers

  • Focus, perform and refocus.

• Monads Simples

  • Definición.
  • Monad Maybe — cómputos que pueden fallar.
  • Monad Identity — cómputos encadenados.
  • Monad List — cómputos no-determinísticos.
  • Notación do.

• Monads con Efectos Colaterales

  • Monad Writer — cómputos con bitácora.
  • Monad State — cómputos con estado mutable.
  • Monad IO — cómputos con efectos de borde.

• Monad Aplicados

  • Máquina Virtual LOGO.
  • Interpretación con Monad State.
  • Gráficos con HGL a través del Monad IO.

• Transformadores

  • MonadPlus
  • Transformadores monádicos.
  • Construcción de MaybeT.
  • Transformador StateT.
  • Ortogonalidad en la composición.

• Todos los Transformadores

  • Repaso de todos los Monads por separado.
  • Construcción de un evaluador usando transformadores.
  • Monad RWST y Monad Exception.

• Pruebas Automatizadas

  • Pruebas unitarias tradicionales.
  • Pruebas automáticas (QuickCheck).
  • Monad Gen para generación de datos de prueba.
  • Análisis de Cobertura.

• Reconocedores

  • Dualidad Show/Read.
  • Reconocedores descendentes (Parsec).
  • Reconocedores ascendentes.

• Programación Concurrente Tradicional

  • Hilos explícitos.
  • Comunicación entre hilos.
  • Monad para concurrencia.

• Programación Concurrente Avanzada

  • Memoria Transaccional.
  • Monad STM.

• Paralelismo Semi-Implícito

  • Anotaciones paralelas.
  • Estrategias de cómputo.

• Paralelismo Aplicado

  • Abstracción Map-Reduce en Haskell.
  • Monad para paralelismo como flujo de datos.

• Análisis de Desempeño

  • Profiling.
  • Análisis de programas concurrentes.
  • Benchmarking.

• Análisis de Desempeño

  • Control de la flojera.
  • Tipos de datos eficientes.

• Programación Dinámica

  • Recursión, Monads y arreglos.
  • Arreglos mutables e inmutables.
  • Arreglos recursivos.

• Paralelismo de Datos

  • Vectorización con REPA.
  • Vectorización con Accelerate (CUDA).

• Lentes y Prismas

  • Lenses & Prisms.
  • Aplicación al procesamiento JSON.

• Programación Funcional Distribuida

  • Introducción a Erlang.
  • Modelo de Actor.
  • Programación distribuida elemental.

• Programación Distribuida de Orden Superior

  • Erlang Behaviors.
  • Servidor distribuido con supervisión.

Programas de Ejemplo

• Máquina Virtual LOGO y Programa Principal.

• ¿Qué hace cada Monad?

• «Sumador» — una pila de transformadores que:

  • Lee dígitos, ignorando espacios en blanco.
  • Lleva la suma acumulada.
  • Genera excepciones ante entrada incorecta o números de mala suerte.
  • Muestra el total al terminar.

• Evaluador «paso a paso» — paso a paso de la construcción de una pila de transformadores para hacer un evaluador de expresiones aritméticas.

• «Sumador» usando RWST.

• Pruebas con Tasty y QuickCheck.

• Cena de Filósofos usando STM

• Paralelismo de datos con REPA

  • Secuencial (baseline).
  • Paralelizado
  • Acelerado (CUDA)

Ediciones Anteriores

• Abril-Julio 2016
• Abril-Julio 2015
• Abril-Julio 2013
• Abril-Julio 2012
• Abril-Julio 2010