Saltar a contenido

Ejercicios · FLP · Induccion y recursion

Inducción y recursión: especificación de datos y de programas. Cada enlace abre una actividad que se trabaja directo en el navegador, sin instalar nada. Los ejemplos no son los de la sesión: mismo tema, ronda nueva.

Son siete, en el orden en que la sesión ve los temas. Las dos primeras se alcanzan en clase; las demás quedan para volver sobre el tema, y entre las seis que piden código suman veintinueve procedimientos por escribir.

conjuntos

Tres bloques de decisiones. En los dos primeros hay que decir si un valor pertenece al conjunto que definen unas reglas: primero las listas de enteros, donde el estorbo son los valores de otro tipo y los pares impropios; después las s-lists, donde dos conjuntos se nombran mutuamente y el anidamiento no tiene fondo.

El tercero cambia la pregunta. Dada la misma gramática, se decide cuál llamada recursiva queda justificada: la que baja por el car cuando ahí hay un entero, la que no cambia el argumento, la que salta de dos en dos. Cada decisión muestra la razón, se acierte o no, y la razón nombra la regla que decide.

escribir y correr

Cuatro procedimientos por escribir, con el código corriendo en la página. suma-lista recorre una lista, duple recorre un número, elimina-primero necesita dos casos base y ocurre-libre? recorre expresiones lambda, que es donde ligadura y alcance dejan de ser una definición y se vuelven una cláusula.

Se llena el esqueleto y se presiona Probar. Cuando una prueba falla, el mensaje dice qué llamada se cayó, qué dio y qué debía dar; los tropiezos más frecuentes —devolver '() donde iba 0, usar append donde iba cons, quitar todas las apariciones en vez de la primera— traen además su explicación. Al final hay una consola libre para probar cualquier otra cosa.

El evaluador de la página entiende define, lambda, if, cond, let, letrec y las primitivas de listas y aritmética, y nada más: no hay define-datatype ni cases. Sirve para tantear una idea sin cambiar de ventana. Lo que se entrega se escribe y se corre en DrRacket.

de las reglas al reconocedor

Cinco conjuntos definidos por reglas y, para cada uno, el procedimiento que decide la pertenencia. Empieza por las potencias de dos, donde la regla multiplica y el reconocedor tiene que dividir; sigue con un conjunto de parejas, donde las dos componentes se mueven al tiempo y verificar una sola deja entrar valores ajenos; y con cuatro conjuntos encadenados, que dan cuatro procedimientos preguntándose entre ellos. Ahí aparece el caso del cero, que modulo acepta y las reglas no.

Los dos últimos toman gramáticas en lugar de reglas de inferencia: la de las expresiones lambda y la de los árboles binarios. Decidir si (lambda x x) pertenece es lo mismo que se hace a ojo mirando paréntesis, ahora escrito como procedimiento.

gramáticas BNF

Una sola gramática para los cinco retos, con las dos abreviaturas de la notación: 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 obliga a que cada procedimiento traiga un auxiliar que recorra la tira.

Primero el reconocedor, donde la diferencia entre las dos cerraduras se vuelve una condición concreta: (suma) pertenece y (mayor) no. Después evaluar la expresión, que ya es un intérprete de un lenguaje diminuto —sintaxis definida por una gramática, recorrido por casos, un valor por cada forma—, y contar operaciones, medir la profundidad y recoger los números que aparecen.

recorrer siguiendo la gramática

Cinco procedimientos que ya no responden sí o no: buscan un elemento, arman una lista nueva, miden. nth-element baja dos argumentos al tiempo, subst necesita dos procedimientos que se llaman entre sí porque la gramática nombra dos conjuntos, y profundidad compara las dos ramas en vez de sumarlas.

Los dos últimos son los más exigentes: contar cuántas veces ocurre libre una variable, que es la versión con números de lo que antes se respondía con booleanos, y encontrar el camino hasta un número en un árbol ordenado, donde la comparación descarta media estructura en cada nivel.

declaración, referencia y alcance

Cinco procedimientos que vuelven código la pregunta de a cuál declaración pertenece cada aparición de un nombre. Los dos primeros separan los dos tipos de aparición: declaradas recoge los identificadores que las lambdas introducen y referencias los que se usan, con sus repeticiones, porque cada aparición cuenta aparte.

Los tres siguientes se apoyan en esa separación. libres deja los usos que ninguna lambda declara, que es lo que después habrá que buscar en un ambiente. sombra? detecta un nombre que tapa a otro, llevando en un acumulador los nombres declarados hasta ese punto. Y renombra cambia las referencias libres de un identificador sin tocar las que pertenecen a otra declaración, que es la regla del alcance escrita como procedimiento.

ligaduras locales al recorrer la gramática

Cinco recorridos donde el nombre local deja de ser una comodidad. En rango y en quita-y-cuenta el resultado de la llamada se necesita dos veces, y escribirla dos veces la evalúa dos veces: el trabajo se duplica en cada nivel. El segundo además devuelve dos respuestas de un solo recorrido, la lista sin las apariciones y cuántas quitó.

Los otros tres reparten las tres formas. resumen arma con let* la cantidad de nodos y la altura de un árbol binario, por etapas sobre las dos ramas. con-posicion esconde con letrec el contador que empareja cada elemento con su posición, de modo que quien lo llama pase solo la lista. Y el último vuelve a la gramática de las s-lists: dos conjuntos que se nombran mutuamente dan dos procedimientos que se llaman entre sí, ligados en un mismo letrec.