Taller de Lenguajes de Programación I (CI-3661)

Cronograma

Haskell (cinco o seis sesiones)

• Introducción a Haskell
  • Ambiente de programación (stack, REPL)
  • ¿Cómo escribir funciones?
  • Recursión.
  • Tipos escalares básicos, Maybe e Either.
  • Tuplas como valor único compuesto.
  • Clases de Tipos — Num, Show, Eq, Ord y Read sobre tipos simples.
• Sistema de Tipos Haskell
  • Tipos recursivos (listas).
  • Recursión explícita sobre listas.
  • Recursión implícita map y fold sobre listas.
  • Listas por Comprensión.
  • Evaluación por sustitución.
• Programación Genérica
  • newtype vs data
  • Instancias Show y Read «a la medida».
  • Tipos Abstractos de Datos (Arboles y «Registros»).
  • Notación de registros.
  • Clase de Tipos Functor.
  • Tipos Maybe, Either y lista como Functor.
• Programación Genérica
  • Clase de Tipos Monoid.
  • Clase de Tipos Foldable.
  • Tipo lista como Foldable.
  • Tipos recursivos como Foldable
  • Clase de tipos Read – reconocedores simples.
• Interacción con el mundo exterior.
  • Acciones impuras (I/O, números al azar).
  • Construcción y secuenciación de acciones (IO).
  • Combinadores monádicos básicos (>>, >>= y return).
  • Notación do.
• Evaluación perezosa.
  • Laziness para evaluación parcial.
  • Recursión mutua.
  • Streams.

Prolog (cuatro o cinco sesiones)

• Introducción a Prolog
  • Ambiente de programación.
  • Resolución, unificación y backtracking.
  • Estrategia procedural vs. declarativa.
• Prolog Aplicado.
  • Estrategia «generate-test».
  • Control del backtracking.
  • Búsqueda generalizada (BFS o DFS genérico).
  • Aplicación a problemas de transición.
  • Manipulación de la base de datos.
• Prolog de Orden Superior.
  • Manipulación simbólica.
  • Meta-programación.
  • Predicados genéricos meta-programados.
• Prolog para Lingüística.
  • Definite Clause Grammars.
  • Reconocedores para lenguajes ambigüos.
  • Operadores como conectores.

Otros lenguajes

Ediciones previas de este curso incluyeron el uso de lenguajes como Racket o Ruby, para explorar algunos conceptos seleccionados como despacho doble, despacho múltiple, roles y comportamientos.

La inclusión de lenguajes adicionales depende de la cantidad de feriados nacionales que afecten las clases de laboratorio: no se incluirán lenguajes adicionales cuando sólo hay 10 sesiones de clase en el calendario; se incluirán dos sesiones sobre lenguajes adicionales si hay 11 o 12 sesiones de clase.

Herramientas de Programación

Usaremos al menos los lenguajes de programación Haskell y Prolog para desarrollar las soluciones a los proyectos propuestos en clase.

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.

Prolog

Trabajaremos con SWI Prolog, el entorno interactivo y compilador.

Para instalarlo:

• En Debian GNU/Linux y en Ubuntu reciente, pueden instalar todo lo necesario haciendo

  aptitude install swi-prolog swi-prolog-doc

  Otras distribuciones Linux podrían tener un paquete razonable — consulte la documentación de la distribución.

• Para MacOSX o Windows, visiten la página de descargas

Todos los archivos que formen parte de su proyecto deben estar completa y correctamente documentados siguiendo las mejores prácticas y reglas de estilo para el lenguaje.

La evaluación de los proyectos se efectuará utilizando SWI Prolog. Si Ud. utiliza cualquier otra implantación del lenguaje (GNU Prolog, por mencionar alguno), asegúrese que solamente usa predicados del estándar ISO y que esos están presentes en SWI Prolog. Hay algunos predicados que no es conveniente emplear mientras se aprende el lenguaje: en particular, está prohibido usar el predicado «implicación» (->/2)

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

Evaluación

La evaluación consiste en varios proyectos para explorar los estilos de programación. En general, la distribución de la evaluación es:

• Tarea Haskell (Semana 03) 15%
• Proyecto Haskell (Semana 07) 35%
• Tarea Prolog (Semana 09) 15%
• Proyecto Prolog (Semana 11) 35%

Las Tareas son individuales, están conformadas por preguntas cortas para confirmar su comprension sobre las técnicas del lenguaje, incluyen mínimo trabajo de programación, aunque pedirá correr cosas a mano.

Los proyectos son en equipo, están divididos en dos o tres partes, generalmente independientes, y requieren esfuerzo de programación y análisis considerable.

Equipos y Proyectos

Los equipos de trabajo son de dos (2) personas. Para la segunda sesión debo haber recibido de ustedes un mensaje de correo con la constitución de los equipos; caso contrario los asignaré al azar.

Copiar el proyecto de otro compañero será sancionado con el aplazamiento del proyecto, y el desenlace de la materia dependerá de la opinión del Profesor que coordine la asignatura. Independientemente de eso recibirán una amonestación en la Coordinación de la carrera que puede llevar a la expulsión de la Universidad.

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.

Bibliografía

Todos los lenguajes empleados incluyen documentación de referencia suficiente, que está disponible tanto en línea, como en su computador como parte del proceso de instalación.

Sin embargo, algunas personas prefieren tutoriales o libros con los cuales reforzar los conocimientos adquiridos en clase.

Haskell

No se alarme por las fechas de algunos de estos documentos. Muchas de las ideas fundamentales de programación funcional no han cambiado en fondo, simplemente en forma, en muchos años. Del mismo modo, las dificultades para aprenderlas siguen siendo las mismas.

Tutoriales introductorios.

• «A gentle introduction to Haskell» es el tutorial clásico más sencillo.

• «Learn you a Haskell for Great Good» es un tutorial más reciente, que incluye materiales avanzados.

• Lista de Tutoriales en el WiKi Haskell

Libros

• El WikiBook de Haskell es una referencia interesante tanto para comenzar como para avanzar con el lenguaje y sus fundamentos teóricos.

• «Haskell: The Craft of Functional Programming» (Thompson), publicado por Addison-Wesley, es el libro de texto usualmente recomendado para la materia.

• «Introduction to Functional Programming» (Bird) es un libro de apoyo útil para este curso, aunque algunos elementos del Haskell moderno difieran.

• «The Haskell School of Expression» (Hudak) es un libro muy interesante que complementa este curso, con una aproximación muy diferente a la enseñanza de la programación funcional, enfocándose en multimedios (gráficos, juegos, música).

• «Real World Haskell» no es para este curso, sino para una continuación. Además, está notablemente desactualizado, así que hay cosas que directamente no ayudan.

Una reacción absolutamente normal y muy frecuente al enfrentarse a la programación funcional por primera vez, es sentirse frustrado, inútil, e impotente, porque no funciona nada de lo que creías saber. Hace falta cambiar la manera de pensar acerca de los problemas de programación. Es posible encontrar solaz revisando el material en «Problem Solving in Haskell»

Prolog

Tutoriales

• El WikiBook de Prolog es una referencia interesante tanto para comenzar como para avanzar con el lenguaje y sus fundamentos teóricos.

Libros

• «Programming in Prolog» (Clocksin & Mellish), publicado por Springer-Verlag es el libro «clásico».

¿Cómo practico?

La única manera de dominar el tópico es practicando desde el primer día. Sin práctica, es muy difícil lograr tareas y exámenes convincentes de un día para otro. Procure intentar los experimentos hechos en clase, y modificar los programas ejemplo en búsqueda de ideas originales.

Para el cronograma actual, se recomienda:

• Introducción a Haskell (Semana 1)
  • Instale Haskell en su máquina.
  • Escriba las funciones descritas en clase, de nuevo. No las copie. Si comete errores al escribirlas, trate de interpretar los mensajes de error emitidos por el compilador.
  • Ejercicios 31 a 34, y 40 de los «99 Haskell Problems».
  • Explore la creación de tipos de datos, y los «typeclasses» más convenientes (Show,Eq,Ord,Read) para:
    • Colores del arcoiris
    • El juego «piedra, papel, o tijera». Escriba una función que reciba dos «jugadas» e indique el resultado diciendo GanaA, GanaB, o Empate.
  • Investigue las funciones provistas por el módulo Data.Maybe para tratar de que las funciones descritas en clase queden más cortas eliminando el «pattern-matching».
  • Lea sobre números en Haskell, para que aprecie las dificultades que hay en lograr consistencia y flexibildad en la organización de los tipos numéricos en Haskell. Con lo aprendido, extienda la función raices para soportar raíces complejas.
  • Explore los comandos :type, :info, :browse e :import en GHCi.
• Tipos recursivos – Listas (Semana 2)
  • Explore el Prelude para identificar funciones útiles sobre listas.
  • Explore el módulo Data.List para identificar aún más funciones. Para poder usar el módulo Data.List con comodidad:
    • En el REPL: :m Data.List
    • En su código fuente: import Data.List
  • Haskell provee el tipo Bool para representar valores lógicos True y False. Está definido en el Prelude. Revise el código fuente para notar que todos los operadores booleanos están implementados como funciones Haskell – no son «internas».
  • Haskell provee el tipo String que es idéntico a [Char]. Eso quiere decir que cualquier función que opera sobre listas, también se puede usar sobre String. Verifíquelo. Note que un String se escribe "entre comillas dobles" y un Char se escribe 'x' entre comillas simples. Haskell soporta Unicode, así que puede usar emojis en sus String.
  • Ejercicios 1 a 22, y 26 de los «99 Haskell Problems». Muchas de esas funciones ya existen en el Prelude, así que si se «tranca», consulte el código fuente para orientarse. Piense por qué el ejercicio 9 es «difícil». Escriba con recursión directa, listas por comprensión, map, y foldr.
  • Intente escribir map usando foldr.
  • Intente escribir filter usando foldr.
  • Intente escribir foldl usando foldr – ¡truculento!
  • Trate de instalar hoogle y adaptarlo a su REPL.
• Refinación de tipos y Programación Genérica – Listas (Semana 3)
  • Ensaye el uso de import para importar: todos los nombres, nombres específicos, todos los nombres excepto algunos, y todos los nombres de manera calificada, para el módulo Data.Char
  • Diseñe y refine tipos de datos para:
    • Listas no vacías. ¿Cómo implantaría las funciones head y tail?
    • Una «etiqueta» DNS: entre 1 y 63 caracteres, sólo puede tener letras, dígitos, el underscore y el guión, no puede comenzar con guión, y su representación interna tiene que garantizar que todo está en minúsculas.
    • Un intervalo en los números reales: límite inferior y superior, los límites pueden ser abiertos o cerrados. Provea fácil acceso a esos elementos, así como una instancia Show conveniente. Defina una función para crear intervalos, algún predicado para verifcar si un valor arbitrario está dentro de un predicado, y operaciones de union, intersección, y diferencia de intervalos.
  • Explore la interfaz de programación Functor sobre los tipos provistos en el Prelude (omita IO y el «curioso» ((->) r) por ahora).
  • Implante una instancia Functor para data Symtable k v = Sym [(k,v)]
• Programación Genérica (Semana 4)

  • Explore la interfaz de programación de Monoid sobre los tipos provistos en el Prelude.

  • ¿Puede construir un Semigroup sobre el conjunto Int usando la operación max? ¿Puede construir un Monoid? ¿Puede construir un Monoid incluso después de aprender sobre la clase de tipos Bounded?

  • Explore la interfaz de programación de Data.Set. Construya instancias Semigroup y Monoid aplicables a Data.Set.

  • Ejercicios 61 a 68 de los «99 Haskell Problems», pero usando Functor y Foldable.

  • Considere los tipos de datos

    data Meridien = AM | PM
    
    data Hora = Militar Int Int Int
              | Civil   Int Int Int Meridien

    proponga instancias Show para presentarlas como HH:MM:SS o HH:MM:SS AM, y las instancias Read correspondientes.

• Operaciones I/O y cómputos monádicos (Semana 5)
  • Escriba programas que transformen su entrada usando funciones puras:
    • Convertir de mayúscula a minúscula.
    • Eliminar espacios en blancos redundantes (más de un espacio en blanco seguido, más de una línea en blanco seguidas).
    • Contar la cantidad de líneas, palabras, y caracteres.
  • Escriba los programas usando notación do y >>=.
  • Escriba los programas uando interact y con operaciones I/O explícitas leyendo de entrada y salida estándar.
  • Escriba los programas recibiendo el nombre del archivo de entrada como un argumento en la línea de comandos.
  • Investigue los combinadores foldM, mapM, forM, sequence, y sus contrapartidas con _ al final.
  • Implemente el juego «Hangman».
• Introducción a Prolog (Semana 7)
  • Instale SWI-Prolog. Asegúrese de tener acceso a la documentación en HTML.
  • Escriba los predicados descritos en clase, de nuevo. No los copie. Si comete errores al escribirlas, trate de interpretar los mensajes de error emitidos por el interpretador.
  • Escriba el predicado fib(N,F) que triunfa cuando F es el N-ésimo Número de Fibonacci.
  • Escriba los predicados mutuamente recursivos even/1 y odd/1, que triunfan si su argumento es un número natural par e impar, respectivamente. ¿Puede usarlos para generar los infinitos números pares (impares)?
  • Ejercicios 1 a 22, y 26 de los «99 Prolog Problems».
  • Explore los predicados consult/1, listing/1 y help/1 provistos por el interpretador.
• Técnica «generate-test» (Semana 8)
  • Aplique la técnica «generate-test» para resolver el problema ABCDE * A = EEEEEE donde cada letra corresponde a un dígito diferente entre 0 y 9.
  • Ejercicios 46 a 48, 58 y 81, de los «99 Prolog Problems».
  • Explore los predicados once/1, findall/1 y setof/1 provistos por el interpretador.
• Búsqueda controlada. Metaprogramación. (Semana 9)

  • Implante una maquinaria de búsqueda para BFS, con la misma estructura de «predicados gancho», y compruebe la diferencia al aplicarlo a los dos problemas descritos en clase.

  • Convierta el problema de las Ocho Reinas a la infraestructura DFS. ¿Hace diferencia (espacio o tiempo), y por qué?

  • Implante un «meta-trazador» para Prolog, de manera que presente todos los pasos de una demostración, usando indentación para presentar las invocaciones recursivas, e.g.

    ?- traza(abuelo(miguel,X)).
    > abuelo(miguel,_55788)
     > padre(miguel,ernesto)
     < padre(miguel,ernesto)
     > padre(ernesto,santiago)
     < padre(ernesto,santiago)
    < abuelo(miguel,santiago)
    X = santiago 

  • Implante los predicados findall/1 y setof/1 usando técnicas de metaprogramación. Asegúrese de que sean idempotentes en su uso de la base de datos Prolog.

Material de Apoyo de Clases

Siendo este un curso práctico, todas las clases transcurren escribiendo programas y explorando lo que ocurre al aplicarles pequeñas transformaciones (live coding). Eso tiene como consecuencia, por un lado, que no haya láminas para seguir el curso, y por otro lado, que en cada clase suele haber una dosis importante de improvisación y adecuación: es posible que en clase se improvise un programa, modificaciones a programas existentes, o derivaciones surgidas de preguntas o sugerencias espotáneas.

Aquí puede encontrar una colección de los programas que usualmente muestro en clases (ni todos, ni siempre), agrupados según el lenguaje. Es perfectamente posible que en clase no muestre ninguno de estos programas, o muestre otros programas que no van a estar disponibles. Vaya a clase y tome notas.

• Ejemplos Haskell
• Ejemplos Prolog
• Ejemplos Ruby
• Ejemplos Racket — (para los curiosos)

Ediciones Anteriores

• Enero-Marzo 2022
• Septiembre-Diciembre 2016.
• Enero-Marzo 2016
• Septiembre-Diciembre 2015 — cancelado por paro de profesores.
• Enero-Marzo 2015
• Enero-Marzo 2014
• Enero-Marzo 2011
• Septiembre-Diciembre 2009