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

Cronograma

El cronograma más reciente es como sigue:

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 (Monad IO).
    • Combinadores monádicos básicos (>>, >>= y return).
    • Notación do.

  • Evaluación perezosa.

    • Laziness para evaluación parcial.
    • Recursión mutua.
    • Streams.

Prolog (Tres o Cuatro 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.

Rust (Dos o Tres sesiones)

  • Introducción a Rust

    • Ambiente de programación.
    • Sistema de tipos.
    • Mecanismo de propiedad única.

  • Programación orientada a roles.

Herramientas de Programación

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

Haskell

Debe trabajarse con GHC 8.8.4, el entorno interactivo del Glasgow Haskell Compiler. Adicionalmente, la herramienta de gestión de dependencias y aplicaciones stack.

Para instalar ambas herramientas:

  • En Debian GNU/Linux 11 (Bullseye), pueden instalar todo lo necesario haciendo

    apt install haskell-platform haskell-stack

    Otras distribuciones Linux podrían tener un paquete razonable — consulte la documentación de la distribución. En el caso de Debian 11 stack va a ser un poco más viejo, pero eso no es un problema para lo que vamos a hacer.

  • Para una instalación más «al día» en cualquier distribución Linux, no instalen ningún paquete de la distribución; instalen stack, y descarguen el compilador específico.

  • Para MacOSX o Windows, sigan las instrucciones para instalar stack.

Las instalaciones con stack descargan tanto el compilador como las librerías que van haciendo falta. Demoran tiempo en descargar, y ocupan espacio en disco -- no lo dejen para último momento.

Los proyectos tienen que ser entregados como un «stack distribution» (les mostraré cómo).

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.

Prolog

En el caso de Prolog trabajaré con SWI Prolog (8.2 u 8.4) el entorno interactivo y compilador.

Para instalarlo:

  • En Debian GNU/Linux 11 (Bullseye) 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 sólo 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.

Rust

En el caso de Rust debe trabajarse con rustc (1.48) y su librería estándar. Rust es un lenguaje que evoluciona muy rápido, y que libera versiones con mucha frecuencia -- en general le iría bien con cualquier versión superior a esa porque no vamos a explorar todo el lenguaje.

Para instalarlo:

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

    aptitude install rustc rust-doc cargo

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

  • Para MacOSX o Windows, o bien si quieren una instalación más «al día», instalen rustup

La evaluación de sus proyectos tomará en cuenta el uso correcto del estilo orientado a roles, siempre aprovechando el sistema de tipos del lenguaje y su librería estándar (no reimplantar cosas que existen), y con atención a la eficiencia algorítmica. No basta «que funcione»: tiene que estar implantado usando la técnica particular solicitada y además tiene que ser eficiente.

Equipos y Proyectos

Los equipos 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.

Evaluación

La evaluación consiste en varios proyectos para explorar los tres 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 conformados por dos o tres partes, generalmente independientes, y requieren esfuerzo de programación.

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.

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.

Si Ud. se pregunta «¿Cómo le entro a esto?», le recomiendo leer con atención «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.

  • prolog :- tutorial hace un recorrido por el lenguaje atacando problemas específicos. No es un tutorial «paso a paso» sino orientado a la resolución de problemas.

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 usando stack.
    • 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. Eso tiene como consecuencia, por un lado, que no haya un juego de 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.

Ediciones Anteriores