Clase 1. Inducción y recursión: especificación de datos y de programas¶
Martes 8 de septiembre de 2026.
Un procedimiento recibe valores de cierta clase y devuelve valores de cierta clase. Mientras esas clases sean finitas y pequeñas, describirlas es fácil: se enumeran. La sesión empieza donde eso deja de funcionar, cuando la clase tiene infinitos elementos, y termina con la pregunta de a cuál declaración pertenece cada aparición de un nombre.
Las diapositivas están en el Campus Virtual. Aquí quedan las notas y el código que se escribió en clase. El repaso del lenguaje va aparte, en Racket, lo que hace falta para empezar.
Referencia: Friedman y Wand, Essentials of Programming Languages, 3.ª edición, §1.1 a §1.3.
Conjuntos definidos por reglas¶
Primero el problema. De estos valores, ¿cuáles son listas de tuplas \((a\;b)\) con \(a\) par y \(b\) múltiplo de tres?
() sí, la lista vacía siempre cumple
((2 3) (4 9)) sí
((2 3) (8 2)) no, 2 no es múltiplo de 3
((8 27) (6 3)) sí
(8 27 6 3) no, eso no son tuplas
Un lector humano decide esto de un vistazo. Una máquina no, y ahí empieza el trabajo.
La primera idea es enumerar el conjunto: escribir todos sus elementos. No sirve. El conjunto es infinito, ninguna enumeración infinita cabe en un programa, y preguntar si \(1000\) es par obligaría a recorrer la lista hasta encontrarlo.
En lugar de decir cuáles son, se dice cómo se construyen. Una definición inductiva tiene siempre dos partes:
- Un caso base: ciertos valores están en el conjunto.
- Una regla inductiva: si ciertos valores están, entonces otros también.
Y el conjunto es el más pequeño que cumple las dos.
Para los pares:
Con eso se construye: \(2\) por el caso base, \(2+2=4\), \(4+2=6\), \(6+2=8\). Tres aplicaciones de la regla sobre el caso base.
Para las listas de tuplas hacen falta varios conjuntos encadenados:
donde \(T\) son los múltiplos de tres y \(L\) las listas de tuplas. La lista vacía es el caso base de \(L\). Recordando la estructura de una lista: cabeza y cola, donde la cola es a su vez una lista.
Del conjunto al reconocedor¶
Cada regla de la especificación se vuelve una cláusula del procedimiento:
- el caso base responde que sí;
- la regla inductiva deshace la construcción —aplica la operación inversa— y vuelve a preguntar;
- lo que no encaja en ninguna regla responde que no.
(define in-P?
(lambda (n)
(cond
[(= n 2) #t]
[(< n 2) #f]
[else (in-P? (- n 2))])))
La regla suma dos, así que el reconocedor resta dos. Al evaluar (in-P? 8):
ni es 2 ni es menor que 2, entonces (in-P? 6), luego (in-P? 4), luego
(in-P? 2), que responde verdadero. Ese último caso ya no se evalúa más.
La cláusula (< n 2) es lo que hace terminar al procedimiento. Sin ella,
(in-P? 3) resta dos indefinidamente y nunca alcanza el caso base. La
condición de terminación es parte del reconocedor.
Con el mismo cond —caso base, condición de terminación y el paso que
deshace la regla— salen in-T? para los múltiplos de tres, in-Tu? para las
tuplas —una lista no vacía cuyo primer elemento es par y cuyo segundo es
múltiplo de tres— y in-L? para las listas de tuplas, donde el caso vacío
responde verdadero y el otro pregunta si el car es una tupla y si el cdr
es una lista de tuplas.
Gramáticas BNF¶
Escribir las reglas en palabras se vuelve largo. La misma definición de las listas de enteros, en notación BNF:
<lista-de-enteros> ::= ()
::= (<int> . <lista-de-enteros>)
La notación fija los nombres de las categorías y hace visible la recursión: el no terminal reaparece dentro de su propia producción.
Tres ingredientes (EOPL §1.1.2):
- No terminales: las categorías sintácticas, entre ángulos.
- Terminales: los símbolos concretos —paréntesis, la palabra
lambda, un entero. - Producciones: las reglas
no terminal ::= cuerpo, donde el cuerpo mezcla las dos cosas.
Y tres abreviaturas: la barra | para alternativas, la cerradura de Kleene
\(\{\ldots\}^{*}\) para cero o más, y la cerradura positiva \(\{\ldots\}^{+}\) para
uno o más.
Un árbol binario:
<b-tree> ::= <int>
::= (<symbol> <b-tree> <b-tree>)
Así, (f (k 2 3) (l (s 2 4) 3)) pertenece: f es el símbolo, (k 2 3) es el
hijo izquierdo —que a su vez cumple la segunda producción, con dos enteros
como hijos— y (l (s 2 4) 3) es el derecho.
La gramática que va a acompañar todo el curso es la de las expresiones lambda:
<lc-exp> ::= <identificador>
::= (lambda (<identificador>) <lc-exp>)
::= (<lc-exp> <lc-exp>)
Con ella se decide qué pertenece y qué no:
| Expresión | ¿Pertenece? | Por qué |
|---|---|---|
(lambda (x) (x y)) |
sí | segunda producción; el cuerpo es una aplicación |
(lambda x x) |
no | al identificador le faltan los paréntesis |
(a b) |
sí | tercera producción, dos identificadores |
(x y w) |
no | la aplicación es binaria, no admite tres partes |
Las gramáticas del curso se leen de izquierda a derecha: la forma en que empieza una producción es lo que permite distinguirla de las demás. Cuando dos producciones empiezan igual, hay que transformarlas antes.
Seguir la gramática¶
La gramática no solo dice qué pertenece: dice cómo se escribe el procedimiento que la recorre. Tres reglas de diseño:
- Un caso por cada producción del no terminal.
- Una llamada recursiva por cada aparición del no terminal en la producción.
- Confiar en que la llamada recursiva devuelve lo que su especificación promete, siempre que su entrada cumpla la precondición.
Contar los elementos de una lista sale directo de ahí:
(define list-length
(lambda (lst)
(if (null? lst)
0
(+ 1 (list-length (cdr lst))))))
Dos producciones, dos casos. La lista vacía tiene cero elementos; en el otro
caso se suma uno y se sigue con el cdr. Termina porque una lista bien
formada llega siempre a la lista vacía bajando por los cdr, y ese es el caso
base de todo lo que estamos viendo.
Recursión sobre árboles¶
Las listas y los árboles se recorren igual. La diferencia está en cuántas llamadas recursivas pide la producción: una lista tiene un solo caso recursivo —cabeza y cola—; un árbol tiene dos o más.
Recorrer un árbol y devolver sus elementos en preorden:
(define arbol->lista
(lambda (arb)
(if (number? arb)
(list arb)
(append (list (car arb))
(append (arbol->lista (cadr arb))
(arbol->lista (caddr arb)))))))
Para el árbol (f (k 2 3) 4): f es el car, el hijo izquierdo es el cadr
y el derecho el caddr. Las llamadas se resuelven primero por la izquierda,
así que el resultado es (f k 2 3 4).
Cambiar de preorden a inorden o a postorden es cambiar el orden en que se juntan las tres partes: raíz-izquierda-derecha, izquierda-raíz-derecha, izquierda-derecha-raíz.
Ejercicio: dos reconocedores¶
Escritos en clase, en codigo/ejerciciosclase.rkt.
(define (in-lc-exp? e)
(cond ((symbol? e) #t)
((not (pair? e)) #f)
((eq? (car e) 'lambda)
(and (list? (car (cdr e)))
(symbol? (car (car (cdr e))))
(in-lc-exp? (car (cdr (cdr e))))))
(else
(and (= (length e) 2)
(or (in-lc-exp? (car e))
(in-lc-exp? (cadr e)))))))
Tres cosas que costaron al escribirlo. La primera: (not (pair? e)) va
enseguida del caso del símbolo, porque todo lo demás supone que hay al menos
un paréntesis. La segunda: preguntar por el identificador de la lambda exige
bajar dos veces, (car (car (cdr e))), y antes hay que verificar que
(car (cdr e)) sea una lista, cosa que and permite hacer sin riesgo porque
evalúa en corto circuito. La tercera: la condición (= (length e) 2) va
antes de mirar las partes, o una expresión de tres elementos entraría
donde no debe.
(define (in-b-tree? t)
(cond ((number? t) #t)
((not (pair? t)) #f)
(else
(and (= (length t) 3)
(symbol? (car t))
(in-b-tree? (car (cdr t)))
(in-b-tree? (car (cdr (cdr t))))))))
El mismo esqueleto con tres condiciones en lugar de dos: el tamaño, el símbolo de la raíz y los dos hijos.
Declaración, referencia y alcance¶
El mismo nombre puede aparecer muchas veces y significar cosas distintas. El
ejemplo de la sesión está en
codigo/ejercicio2clase.rkt:
(define x ; declara x1
(lambda (x) ; declara x2
(map (lambda (x) ; declara x3
(+ x 1)) ; referencia a x3
x))) ; referencia a x2
(x '(1 2 3)) ; referencia a x1
Cinco apariciones de x, tres declaraciones y tres referencias, y cada
referencia se resuelve con la declaración más cercana hacia afuera que la
contenga. Nada de esto depende de cómo se ejecute el programa: se decide
leyendo. Pegando ese código en DrRacket, las flechas del editor muestran
exactamente eso.
Cuatro términos que no son sinónimos:
- Declaración: la aparición que introduce la variable, como el parámetro
de una
lambdao el nombre en unlet. - Referencia: la aparición que la usa.
- Ligadura: la asociación entre una referencia y su declaración. El valor asociado es la denotación de la variable.
- Alcance: la región del programa donde las referencias a un nombre corresponden a una declaración dada.
Cuando las reglas se aplican leyendo el texto, el lenguaje es de alcance estático o léxico; cuando se aplican durante la ejecución siguiendo la cadena de llamadas, es de alcance dinámico, y ahí una variable declarada dentro de un procedimiento podría verse desde afuera.
El fenómeno que aparece en el ejemplo se llama ocultamiento: la x de la
lambda interna tapa a la externa, porque crea un contexto nuevo. Se llaman
igual y son variables distintas.
Ocurrencia libre y ocurrencia ligada¶
Sobre la gramática de expresiones lambda, la variable \(x\) ocurre libre en una expresión \(e\) cuando:
- \(e\) es el identificador \(x\); o
- \(e\) es
(lambda (y) e')con \(y \neq x\) y \(x\) ocurre libre en \(e'\); o - \(e\) es
(e1 e2)y \(x\) ocurre libre en \(e1\) o en \(e2\).
Tres casos porque la gramática tiene tres producciones. En (lambda (y) x) la
variable ocurre libre: \(y \neq x\) y en el cuerpo aparece sola. En
(lambda (x) x) no, porque el parámetro ya la liga.
Y ocurre ligada cuando:
- \(e\) es
(lambda (y) e')y \(x\) ocurre ligada en \(e'\), o bien \(y = x\) y \(x\) ocurre libre en \(e'\); o - \(e\) es
(e1 e2)y \(x\) ocurre ligada en \(e1\) o en \(e2\).
Un identificador solo nunca ocurre ligado.
Libre y ligada no son opuestas. Las dos pueden dar verdadero sobre la
misma expresión, y las dos pueden dar falso. En ((lambda (x) x) x) la x
del operando está libre y la del cuerpo de la abstracción está ligada: los dos
predicados hablan de ocurrencias, no del nombre.
Contar cuántas veces ocurre libre, escrito en clase con la misma estructura de tres casos:
(define (cuantas-libres exp var)
(cond ((symbol? exp)
(if (equal? exp var) 1 0))
((equal? (car exp) 'lambda)
(cond
[(equal? (car (car (cdr exp))) var) 0]
[else (cuantas-libres (car (cdr (cdr exp))) var)]))
(else
(+ (cuantas-libres (car exp) var)
(cuantas-libres (car (cdr exp)) var)))))
El caso del símbolo devuelve uno o cero, la lambda corta y devuelve cero cuando declara la variable buscada, y la aplicación suma lo que traigan sus dos partes. El caso de terminación es el símbolo.
let, let* y letrec¶
Las tres tienen dos áreas: la de declaraciones, donde van las ligaduras entre paréntesis, y el cuerpo donde se usan.
Un let es una aplicación de lambda escrita de otra forma:
(let ([x 10] [y 20]) (+ x y))
((lambda (x y) (+ x y)) 10 20)
Las expresiones de inicialización son los argumentos y se evalúan antes de
que exista cualquiera de las ligaduras nuevas, en el ambiente exterior. De ahí
que las variables de un mismo let no se conozcan entre sí: en
(let ([x 5] [y (+ x 1)]) ...) la referencia a x no se resuelve con la
ligadura de al lado, sino afuera, y si afuera no hay ninguna x el programa
falla con variable no ligada.
Se arregla anidando o con let*, que es lo mismo escrito más corto: cada
ligadura ve las anteriores.
El ejercicio de la sesión, en codigo/usolet.rkt:
(let ((x 3)
(y 4))
(+ (let ((x (+ y 5)))
(* x y))
x))
El let interno declara solo x, así que su y se busca afuera y vale 4.
Entonces la x interna vale \(4+5=9\) y el producto da \(36\). La x que queda
fuera del paréntesis interno sigue siendo la del let externo, que vale 3.
Total: 39. Pegar el código en DrRacket y seguir las flechas confirma a
cuál declaración apunta cada nombre.
letrec liga los nombres antes de evaluar las expresiones, y por eso es
la que sirve para procedimientos que se llaman a sí mismos o entre sí:
(letrec ([es-par? (lambda (n) (if (zero? n) #t (es-impar? (- n 1))))]
[es-impar? (lambda (n) (if (zero? n) #f (es-par? (- n 1))))])
(es-par? 10))
Con let*, es-par? no podría nombrar a es-impar?. Conviene reservar
letrec para procedimientos: (letrec ([x y] [y x]) ...) es una definición
recursiva que no tiene fin.
Ejercicio de cierre: devolver dos respuestas de un recorrido¶
quita-y-cuenta recibe un símbolo y una lista, y devuelve una lista de dos
elementos: la lista sin las apariciones del símbolo y cuántas quitó. En
codigo/ejercicio3clase.rkt:
(define (quita-y-cuenta s lst)
(cond ((null? lst) (list '() 0))
((eq? (car lst) s)
(let ([resto (quita-y-cuenta s (cdr lst))])
(list (car resto) (+ 1 (car (cdr resto))))))
(else
(let ([resto (quita-y-cuenta s (cdr lst))])
(list (cons (car lst) (car resto)) (car (cdr resto)))))))
(quita-y-cuenta 'a '(a b a c)) → ((b c) 2)
(quita-y-cuenta 'a '()) → (() 0)
(quita-y-cuenta 'z '(a b)) → ((a b) 0)
(quita-y-cuenta 'a '(a a a)) → (() 3)
Un solo recorrido produce las dos respuestas. La llamada recursiva se liga a un nombre porque hace falta dos veces: su primera parte es la lista y la segunda es la cuenta. Sin esa ligadura habría que escribirla dos veces, y escribirla dos veces la evalúa dos veces.
Las dos cláusulas arman la misma pareja y se diferencian en qué hacen con el
primer elemento: la que lo encuentra lo deja fuera y suma uno; la otra lo
conserva con cons y deja la cuenta como venía.
Para practicar¶
Las actividades de esta sesión están en Ejercicios interactivos, y el repaso del lenguaje en Ejercicios de Racket. Corren en el navegador, sin instalar nada.
El evaluador de esas páginas es pequeño y no reemplaza a DrRacket: no tiene
define-datatype ni cases. Lo que se entrega se escribe y se corre en
DrRacket.