Saltar a contenido

Ejercicios · FLP · Procedimientos recursivos letrec

Procedimientos recursivos y letrec. Cada enlace abre una actividad que se trabaja directo en el navegador, sin instalar nada. Las secciones siguen las de la sesión y en su mismo orden.

Los programas están escritos como los recibe el interpretador del curso: letrec fact(n) = if ==(n,0) then 1 else *(n, (fact sub1(n))) in (fact 5). Las primitivas van antes del paréntesis y con comas: +(x, y), add1(n), ==(n, 0). La aplicación lleva paréntesis y va sin comas, (f z 2). El ambiente inicial liga x = 4, y = 2, z = 5 sobre otro eslabón con a = 4, b = 5, c = 6. Los programas no son los de clase: mismo lenguaje, ronda nueva. Lo que aquí se afirma sobre valores, ambientes, clausuras y número de llamadas se midió corriéndolo contra el interpretador de 6.Recursivos.

El factorial que no se encuentra a sí mismo

El procedimiento que no se encuentra a sí mismo

Cinco intentos de recursión con let y proc. El primero vale 7 y crea una clausura sin aplicar nada; el segundo es el mismo procedimiento, ahora aplicado, y se detiene. El cuarto es el que más cuesta: dos fact anidados, el de afuera devolviendo 1 para todo, y el programa no falla —da 3— porque la llamada recursiva encuentra al de afuera. El quinto muestra qué sí funciona sin letrec: nombrar un procedimiento declarado antes.

La expresión letrec

La producción de letrec

La producción nueva (EOPL §3.4) en los dos sentidos. Diez programas para decidir si la gramática los genera, y hay sorpresas en las dos direcciones: letrec in +(x,1) se parsea y vale 5, porque el arbno admite cero declaraciones, mientras letrec x = 5 in +(x,1) no se parsea. Después, el reparto de un programa en los cuatro campos de la variante, con el campo que llega como lista de listas. Y al final, cuatro árboles que la gramática no genera, con lo que habría que cambiarle para admitirlos: es lo que se hace al extender un lenguaje, y la dirección en que casi nunca se practica.

El ambiente extendido recursivo

El ambiente extendido recursivo

Qué guarda la variante nueva del tipo ambiente y qué deliberadamente no guarda, y la línea donde se decide todo: el tercer campo de la clausura que apply-env fabrica. Con old-env en ese campo el lenguaje quedaría igual que con let y proc, y el programa de la primera actividad se detendría. El tercer bloque mide una consecuencia que suele sorprender: la cadena de ambientes tiene los mismos cuatro eslabones con (g 3) que con (g 10), porque los marcos de llamada cuelgan del marco recursivo y no uno del otro.

Generación diferida de clausuras

Cuándo nace la clausura

Tres cuentas se confunden todo el tiempo: cuántas declaraciones hay, cuántas clausuras fabrica apply-env y cuántos procedimientos se aplican. Cinco programas las separan. Uno declara un procedimiento y no crea ninguna clausura; otro tiene por valor una clausura sin haber aplicado nada; en el recursivo las clausuras son tantas como llamadas. Se predicen los números y después se abre la traza.

Ejemplo trabajado

La traza de una recursión

Una de las cuatro vale 2 y no 50: su cuerpo nombra una variable libre que se liga después de la declaración, en un let que la clausura nunca llega a ver. Las otras tres tienen dos parámetros donde uno baja y el otro acumula, llegan al caso base con el resultado ya armado, o tienen un parámetro que tapa una ligadura de afuera. Al comprobar, la página abre la traza con el ambiente de cada paso, la cadena en su punto más hondo y cada clausura con el marco que capturó.

Un letrec dentro de un let

Dibujar la cadena con un marco recursivo

Al revés que las anteriores: en vez de leer la cadena hay que construirla. Para cada programa se señala un momento de la evaluación y se escriben los eslabones que existen entonces, uno por línea y del más nuevo al más viejo; la página los dibuja mientras se escriben y al comprobar señala la primera diferencia con la del interpretador. Uno de los cuatro tiene dos marcos recursivos en la misma cadena, y otro tiene t ligado a 10 y a 99 a la vez.

Recursión mutua

Recursión mutua

Varios procedimientos declarados en un mismo letrec que se nombran entre sí. El mismo programa vale 100 empezando por uno y 0 empezando por el otro, según cuál reciba el cero. Hay uno que encadena tres declaraciones sin que ninguna se llame a sí misma, y en todos el marco recursivo es uno solo: tres declaraciones no son tres marcos, son tres listas paralelas dentro del mismo.

Implementación con listas

El ambiente recursivo con listas etiquetadas

Aquí se escribe código. Seis retos que construyen el TAD desde abajo: el predicado y los cuatro extractores, el auxiliar que va del nombre a la posición, el constructor que solo empaqueta, y el caso de apply-env que decide entre fabricar la clausura y delegar en old-env. Las pruebas distinguen capturar el marco de capturar el ambiente que extiende, así que una implementación que confunda los dos falla y lo dice.

Práctica y cierre

Contar consultas y extender el lenguaje

La práctica final, también escribiendo código: el conteo de clausuras que fabrica apply-env durante una recursión completa, modelado como función para poder comprobarlo, y la extensión del lenguaje con una forma nueva: la producción, la variante y la cláusula del evaluador.