Unidad 1: Introducción y Racket

Podemos identificar tres componentes:

La sintaxis, por sí sola, dice muy poco sobre el comportamiento. Consideremos "acceder al i-ésimo elemento de un arreglo `x`" en tres lenguajes:

Dos expresiones sintácticamente idénticas (x[i] en C y Java) tienen semánticas distintas. A la inversa, la misma acción idealizada de sumar 3 y 4 puede escribirse de muchas formas:

Todas denotan lo mismo y todas se corresponden con un mismo árbol de sintaxis abstracta (AST). La moraleja: no hay que apegarse emocionalmente a una sintaxis en particular.

¿Cómo describimos la semántica de un lenguaje? El lenguaje natural es demasiado impreciso. Existen varios enfoques rigurosos:

Para explicar un lenguaje, escribimos un intérprete para él. Este enfoque tiene ventajas pragmáticas decisivas:

Ahora bien, un intérprete es a su vez un programa escrito en algún lenguaje. Conviene, por tanto, usar un lenguaje simple y con fundamentos matemáticos sólidos. Ese lenguaje será Racket.

La mayoría de los lenguajes trabajan sobre este flujo, y es exactamente el que construiremos en el curso:

Visto en términos de tipos, cada operación es una función:

El AST es la estructura central: sobre él se define la interpretación, el análisis y la transformación. Nosotros nos concentraremos en parse e interp. Empezaremos con una "calculadora que sólo suma" y terminaremos con un lenguaje que tiene variables, funciones, recursión y estado.

Comparemos la función factorial en ambos estilos. En C (estilo imperativo), el cálculo se expresa como una secuencia de comandos que modifican almacenamiento mutable (variables):

En Racket (estilo funcional), no hay variables ni asignación: hay evaluación de expresiones y aplicación de funciones sobre datos inmutables:

El estilo imperativo describe cómo hacer el cálculo (está cerca del hardware: registros, memoria mutable, tabla de ruteo de variables). El estilo funcional describe qué se quiere calcular y está más cerca de las definiciones matemáticas.

El entorno oficial es DrRacket, con dos zonas: la ventana de definiciones (arriba) y la ventana de interacción (abajo), que expone un REPL (read-eval-print loop). El botón Run evalúa las definiciones, limpia la interacción y deja las definiciones disponibles para probarlas.

La sintaxis de Racket se basa en paréntesis. Lo primero que aparece tras un paréntesis de apertura está en posición de aplicación (la operación o función a aplicar); lo demás son los argumentos (cero o más):

Definir funciones de varios argumentos es igual de directo:

Racket es de tipos chequeados dinámicamente. Sus datos primitivos incluyen:

Para el control de flujo tenemos dos condicionales. El if toma guarda, rama verdadera y rama falsa:

Cuando el análisis es caso por caso (muy común, y muy matemático), cond evita el anidamiento. Cada cláusula es [guarda resultado]; se evalúan de arriba hacia abajo y gana la primera guarda verdadera:

define introduce identificadores y funciones globales (disponibles sin anidación). Para nombrar resultados locales usamos let, que mejora la legibilidad y evita recomputar. Sin let, la fórmula cuadrática recomputa el discriminante y queda ilegible:

El identificador discriminant sólo existe en el cuerpo del let, se calcula una vez y se reutiliza. let* es como let pero cada ligadura puede usar las anteriores.

La estructura más simple es el par, que une dos valores arbitrarios con cons; se accede con car (primero) y cdr (segundo):

Una lista es, conceptualmente, una secuencia; internamente es una cadena de pares anidados que termina en la lista vacía '() (también empty). Estas tres definiciones son equivalentes:

Operan sobre listas first/car, rest/cdr, append, length, empty?, reverse, list-ref, …​ Como una lista es una cadena de pares, el acceso a una posición arbitraria no es O(1) (a diferencia de un arreglo): list-ref avanza secuencialmente.

Los vectores (vector, vector-ref, vector-set!) son arreglos de tamaño fijo, mutables y con acceso directo.

El operador quote (comilla simple ') le dice a Racket que considere lo que sigue como datos, sin evaluarlo. Esto es distinto de construir una lista con list, que sí evalúa sus argumentos:

map construye una nueva lista aplicando una función a cada elemento, respetando las posiciones (la lista resultante tiene el mismo largo). Primero, cómo se vería sin map, con recursión explícita sobre la lista:

La ejecución "desdobla" un cons por elemento hasta el caso base:

Este patrón (caso base + caso recursivo que reconstruye con cons) se repite en toda función que procesa listas. map lo abstrae:

Cuando la función que pasamos a un HOF es pequeña y no se reutilizará, no vale la pena nombrarla. Se escribe como valor literal con lambda (o λ):

filter construye una lista con los elementos que satisfacen un predicado (una función que retorna #t o #f), manteniendo el orden relativo. Por convención de Racket, los predicados terminan en ?: even?, odd?, string?, …​

El largo de la lista resultante es siempre menor o igual al de la original. Como con map, filter generaliza el patrón recursivo de "conservar unos, descartar otros".

map y filter no bastan para combinar los elementos de una lista en un único resultado (una suma, un producto, la propia lista reconstruida). Para eso están los folds, que capturan por completo el esquema de recursión sobre listas. En Racket, ambos reciben la función combinadora en el orden (elemento acumulador):

foldr calca el template natural de la recursión sobre listas (el caso cons es (f (first l) (recur (rest l)))), lo que lo conecta directamente con los tipos inductivos que veremos más abajo. Por ejemplo, "duplicar los elementos" se puede escribir con map o con foldr:

Cualquier función puede retornar otra función. Este patrón (una "fábrica" de funciones) permite construir funciones durante la ejecución, que dependen de valores no conocidos de antemano:

La clave está en el lambda: sólo porque las funciones pueden escribirse como valores literales es posible retornarlas. Si tuviéramos que darles nombre de antemano, no tendría sentido "retornarlas".

La currificación transforma una función de varios argumentos en una cadena de funciones de un argumento. Para el caso de dos argumentos:

Su beneficio es la aplicación parcial: fijar unos argumentos y dejar otros abiertos, lo que mejora la reutilización y composición.

Racket tiene un lenguaje de patrones rico. Los ingredientes básicos son:

La potencia surge de combinar estructura, literales y variables:

Como las cláusulas se prueban en orden, en j2 el segundo patrón (cons a b) sólo se alcanza si el primero falló: allí tenemos la garantía de que el par no empieza en 1.

Al procesar listas, casi siempre nos interesa uno de dos casos:

Podemos tratar una lista como pares anidados (cons) o con el constructor list. Ambas formas calzan la lista vacía con el literal '():

El caso de largo fijo es el que usaremos para parsear. Un patrón como (list '+ a b) calza cualquier suma binaria en la sintaxis concreta, ligando los operandos:

Esto es exactamente lo que necesita un parser: distinguir '{+ 1 2} de '{- 3 4} y extraer sus partes. Lo desarrollaremos en la Unidad 2.

A veces el requisito no es sólo estructural sino computacional. Podemos añadir una guarda #:when, que tiene acceso a las variables ya ligadas por el patrón:

De forma más compacta, en cualquier posición de patrón podemos aplicar un predicado con (? p):

Cuando sabemos que un valor tiene una única forma y sólo queremos acceder a sus componentes, un match de una sola cláusula queda anidado y feo. #lang play provee def (alias de match-define de Racket): liga las variables del patrón y las deja disponibles de ahí en adelante.

Los números naturales, las listas y los árboles binarios son conjuntos inductivos. Cada definición inductiva genera "ciegamente" dos cosas:

Por ejemplo, para las listas: el caso base es '() y el caso inductivo es (cons v l) con l lista. De ahí sale mecánicamente el esquema: toda función sobre listas trata el caso vacío y el caso cons, con una llamada recursiva sobre el resto (que es más pequeño, por lo que la recursión termina). Ya lo vimos en my-length.

Los árboles binarios (con valores en todos los nodos) se definen así:

#lang play provee deftype para crear tipos inductivos. La traducción de la gramática al deftype es mecánica: se copian el nombre y las variantes, dando un nombre a cada campo (incluidos los campos recursivos):

Cada variante define una función constructora (leaf, in-node) y deftype genera predicados (BinTree?, leaf?, in-node?). Se cumplen tres propiedades fundamentales:

Del deftype se deriva el template de toda función que procesa el tipo: un match con una cláusula por variante, y llamadas recursivas sobre los campos que son del mismo tipo:

Como las variantes son mutuamente excluyentes, el orden de las cláusulas no altera el resultado; por convención se respeta el orden de la gramática. Lo único que cambia entre una función y otra es la acción de cada caso y el valor de retorno; el andamiaje estructural es siempre el mismo. Este patrón aparece en cerca del 80% del curso.

Así como foldl/foldr capturan la recursión sobre listas, podemos capturar la recursión sobre árboles en una única función de orden superior: un fold. La receta "sigue la gramática" nos dice cuántos argumentos necesita: una función por variante. Para BinTree, fold-bintree recibe una función para las hojas (f) y otra para los nodos internos (g), y retorna una función BinTree → A:

Con fold-bintree, definir funciones se reduce a decir qué hacer en cada variante, sin volver a escribir el match ni las llamadas recursivas (que ya viven dentro del fold):

f dice qué hacer con el valor de una hoja; g dice cómo combinar el valor de un nodo con los resultados ya calculados de sus subárboles (vl, vr). Nótese que sum-bintree-fold se define sin paréntesis de aplicación extra: fold-bintree retorna la función, que luego aplicamos al árbol.