Cinco procedimientos que ya no responden sí o no: buscan un
elemento, arman una lista nueva, miden, cuentan. La gramática sigue diciendo
cuántas cláusulas van y sobre qué se llama la recursión; lo que cambia es
qué devuelve cada cláusula. Los dos últimos son los más exigentes y conviene
llegar a ellos con los tres primeros resueltos.
Esto no es Racket. Es un evaluador pequeño que entiende define,
lambda, if, cond, let,
letrec y las primitivas de listas y aritmética. No hay
define-datatype ni cases: para eso está DrRacket.
Sirve para probar una idea sin cambiar de ventana, y lo que se entrega se
escribe y se corre en DrRacket.
Los cinco, resueltos
Los cinco recorren conjuntos distintos con la misma
lectura, y lo que cambia entre ellos está en la última columna:
Procedimiento
El conjunto que recorre
Qué junta las partes
nth-element
listas
nada: una sola rama baja y la respuesta sube igual
subst
s-lists y s-exp, uno adentro del otro
cons, que rearma el nivel que se acaba de abrir
profundidad
árboles binarios
max entre las dos ramas, más uno
cuantas-libres
expresiones lambda
una suma entre las dos partes de la aplicación
camino
árboles binarios de búsqueda
cons del giro de este nivel, y baja una sola rama
La gramática fija el esqueleto y la especificación llena
lo que queda: qué devuelve el caso base y con qué operación se juntan los
resultados de las llamadas. Dos procedimientos con el mismo recorrido y
distinta respuesta se diferencian solo en esas dos decisiones.
Consola
Para probar cualquier cosa. Las definiciones se
acumulan entre corridas hasta que se reinicie la sesión.