Cinco retos sobre el marco recursivo de EOPL §3.4: contar las clausuras que fabrica apply-env, decidir qué declaración cabe en el marco, armar el árbol de llamadas como valor de un datatype, leer en un árbol las producciones que lo generan, y evaluar una producción nueva que declara un solo procedimiento recursivo.
Esto no es Racket. Es un evaluador pequeño que entiende define,
lambda, if, cond, let,
letrec, define-datatype y cases, con
las primitivas de listas y aritmética. No trae map,
filter ni apply: los recorridos se escriben con
recursión. Los valores de un datatype se imprimen como
(lit-exp 5) para poder leerlos, y car sobre uno
falla. Lo que se entrega se escribe y se corre en DrRacket.
Los cinco, resueltos
Lo que queda medido en cada uno:
Reto
Lo que se midió
clausuras
n+1 consultas en la recursión que baja de uno en uno; 15 en (fib 5) y 25 en (fib 6)
declaraciones
el marco acepta nombre, parámetros y cuerpo; una declaración de valor no tiene dónde ir
árbol de llamadas
(camina 5): 13 nodos, 9 hojas, profundidad 4
producciones
13 producciones en cuenta-atras, una sola de ellas nueva
evaluador
la clausura nace en la consulta y captura el marco donde vive su propio nombre
Una consulta de apply-env, una clausura, un
nodo del árbol de llamadas: los tres números del primer reto, del tercero y
del quinto son el mismo número contado de tres maneras. El marco recursivo
guarda parámetros y cuerpos en vez de valores, y por eso la recursión sale
sin ninguna asignación.
Consola
Para probar cualquier cosa. Las definiciones se
acumulan entre corridas hasta que se reinicie la sesión.