Una sola gramática para los cinco retos, con las dos
abreviaturas que la notación permite: la estrella, que significa cero o más,
y la cruz, uno o más. Los argumentos de una operación dejan de ser una
cantidad fija, y eso cambia la forma del recorrido: en lugar de nombrar cada
hijo, hay que recorrer una tira.
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
La misma gramática leída cinco veces, y lo que
cada lectura produjo:
Procedimiento
Qué devuelve
El caso base de la tira
es-exp?
un booleano
la tira vacía pertenece, salvo donde la cruz lo impide
evalua
un número
cero para la suma; el único argumento para el mayor
cuenta-operaciones
un número
cero: no hay nada que contar
profundidad
un número
cero, y se compara en vez de sumar
hojas
una lista
la lista vacía, y se junta con append
La estrella y la cruz no son adornos de la notación: son
la diferencia entre un caso base que acepta la tira vacía y uno que exige
al menos un elemento. Y como el número de argumentos no está fijo, cada
procedimiento necesita un auxiliar que recorra la tira, con su propio caso
base y su propia forma de combinar.
Consola
Para probar cualquier cosa. Las definiciones se
acumulan entre corridas hasta que se reinicie la sesión.