Unidad 5: Recursión y mutación

Conviene distinguir dos nociones que se confunden con facilidad:

Las estructuras cíclicas serán nuestra herramienta para implementar recursión, así que las estudiamos primero.

Para construir una estructura cíclica no podemos escribir el ciclo de un solo golpe, porque en el momento de mencionarse a sí misma la estructura aún no existe. La estrategia es:

Veamos la lista cíclica de unos y una caja que se contiene a sí misma. Este es el código real:

ones es un par mutable cuyo mcdr es él mismo: en la dirección 0 hay un par cuyo primer valor es 1 y cuyo segundo componente vuelve a la dirección 0. Podemos consumir tantos elementos como necesitemos sin caer en la impresión infinita:

La autorreferencia no tiene por qué ir en el «último» componente. Podemos combinar un prefijo finito con una sección cíclica —por ejemplo, la representación decimal del número periódico 1,4545… como (mcons 1 (mcons 4 (mcons 5 ⊡))), donde ⊡ es la autorreferencia al par que contiene el 4.

Nuestro objetivo, sin embargo, no es representar grafos: es construir un ambiente cíclico que nos permita implementar recursión. Antes veamos exactamente qué se rompe.

El parser desazucara el with en la aplicación de una función anónima:

Al interpretar la aplicación, E se evalúa en el ambiente vigente en ese punto —que aún no contiene fact. La clausura resultante captura ese ambiente:

El ambiente capturado por la clausura es vacío: no tiene ninguna asociación para fact. Por eso:

El problema no es un error nuestro: nace de las reglas de alcance de with/let. La asociación [fact → …] solo está disponible en el cuerpo del with, no dentro de la expresión nombrada. Racket sufre exactamente lo mismo:

La solución es la misma receta de las estructuras cíclicas: introducimos un nivel de indirección con una caja y cerramos el ciclo con mutación.

La caja fact sí es capturada por la clausura (está en un let externo), y como la mutación cambia el contenido sin alterar la identidad, la función encuentra su propia definición al invocarse. Racket, por supuesto, provee letrec, que hace exactamente esto de forma transparente:

Nuestra meta es dar a nuestro lenguaje-objeto su propio letrec.

A diferencia de with, rec no puede desazucararse a una aplicación de función (eso reintroduciría el problema del alcance). Necesitamos un nodo explícito en la sintaxis abstracta:

El parser construye ese nodo directamente (su sintaxis concreta es idéntica a la de with, pero la acción es distinta):

Así, {with {fact E} B} y {rec {fact E} B} producen árboles distintos: el primero es una aplicación (por el azúcar), el segundo es un nodo rec.

¿Cuál debe ser el ambiente capturado por la clausura de fact? Si extendemos el ambiente una sola vez con [fact → clausura], funciona para {fact 0} y {fact 1}. Si lo hacemos dos veces, funciona hasta {fact 2}. Para cualquier número fijo de niveles siempre existe una invocación más profunda que falla. Necesitamos que la clausura capture un ambiente que se refiera a sí mismo: un ambiente donde fact esté asociado a una clausura que captura ese mismo ambiente. Un ambiente cíclico.

Para poder cerrar el ciclo con mutación, extendemos el ADT de ambientes con una variante cuyo valor vive dentro de una caja:

Aplicamos la receta «nombrar y conquistar» al ambiente. Este es el código real:

El paso 3 es crucial: la función se interpreta dentro del nuevo ambiente, de modo que la clausura captura un ambiente donde id ya aparece (todavía apuntando al 'dummy). El paso 4 reemplaza el 'dummy por la clausura misma. Resultado:

La semántica de rec es simplemente interpretar el cuerpo bajo el ambiente cíclico:

Con esto, la definición recursiva funciona para cualquier número natural:

Cuando el intérprete evalúa {fact 5}, lo hace bajo el ambiente cíclico. La llamada recursiva {fact 4} se ejecuta bajo el ambiente clausurado por fact, que es el mismo ambiente cíclico; y así toda llamada recursiva sucesiva.

La expresión nombrada podría ser arbitraria, incluso el propio identificador que estamos ligando:

Para evitar estas inconsistencias, restringimos la expresión nombrada de rec a que sea una definición de función (por eso cyclic-env asume que fun-expr es una función). Racket impone una restricción análoga: reporta «cannot use identifier before its definition».

Ahora bien, la posibilidad de divergencia no es exclusiva de rec. Ya en FAE puro podíamos escribir el combinador Ω, que se reduce a sí mismo indefinidamente:

Evaluar Ω nunca termina, porque un paso de reducción produce exactamente la misma expresión. La no-terminación es un fenómeno independiente de tener o no un constructor recursivo.

Existe una forma puramente funcional de implementar recursión, sin mutación: la autoaplicación. El problema es que la función «no sabe» a quién llamar en el paso recursivo; la solución es pasarle esa función como argumento.

Cada paso recursivo vuelve a aplicar self a self, de modo que la función siempre dispone de sí misma. Este patrón puede automatizarse con el combinador Y, que abstrae la autoaplicación y permite escribir definiciones recursivas con sintaxis normal. En consecuencia, podríamos tratar rec como azúcar sintáctico apoyado en el combinador Y.

En el lenguaje con funciones de primer orden la recursión venía «gratis». Allí las aplicaciones siempre eran contra funciones con nombre, y los nombres se buscaban en una lista global de definiciones (lookup en FunDef), disponible durante toda la ejecución. Por eso una función podía referirse a sí misma —e incluso a otras (recursión mutua, como even/odd)— sin ninguna maquinaria adicional. En FAE, en cambio, los identificadores se buscan en el ambiente, y por eso necesitamos el ambiente cíclico para que la búsqueda siempre tenga éxito.

Cada invocación de función agrega un stack frame que contiene el estado del llamador (para restaurarlo al retornar), la dirección de retorno y otros metadatos. Habrá un frame por cada llamada no terminada. Al ejecutar una función recursiva, la pila crece en proporción a la profundidad de la recursión, hasta desbordarse.

Comparemos dos funciones. El factorial no optimizable:

Y el máximo común divisor, cuya llamada recursiva es el resultado final:

En ambos casos la pila crece con la profundidad; pero en el primero hay un contexto de control que crece alrededor de cada llamada (las multiplicaciones que quedan «recordadas» para hacerse al volver). En el segundo no hay contexto pendiente: el resultado de (gcd 14 21) es, sin más, el valor de (gcd 21 14). Este segundo perfil admite una optimización.

Una llamada a función está en posición de cola si su resultado se retorna inmediatamente como el valor de la función que la contiene, sin computación pendiente posterior. Es una propiedad estática: se observa en el código fuente, sin ejecutarlo, y aplica a cualquier llamada, no solo a las recursivas.

a(data) no está en posición de cola porque el if debe esperar su valor para elegir la rama; hay un contexto pendiente (la evaluación del condicional). b(data) y c(data) sí lo están: son el resultado final. Nótese que para que una función entera sea de cola, todas sus ramas deben terminar en llamadas en posición de cola.

Con TRO, el tamaño de la pila permanece constante sin importar si hay 10, 1000 o un millón de llamadas: el frame se reutiliza y solo cambian los argumentos.

La versión original de fact no es recursiva por la cola porque retornamos antes de multiplicar. La técnica general es agregar un acumulador donde realizamos el cálculo antes de la llamada recursiva, de modo que no quede contexto pendiente:

El desarrollo muestra que la pila ya no crece:

El valor inicial del acumulador depende de lo que calcula la función (para el factorial es 1); suele coincidir con el valor del caso base. La misma idea, con dos acumuladores, transforma Fibonacci:

Toda función recursiva puede traducirse a una versión recursiva por la cola. La idea general es pasar el contexto de control como un argumento adicional: qué hacer con el resultado de las llamadas recursivas (una continuación, en términos generales).

Que una llamada por la cola se optimice o no depende de la implementación (compilador/intérprete), no del código fuente. El mismo programa en C, recompilado con -O2, deja de desbordar la pila.

Una desventaja de la optimización: se pierde información de depuración, porque el historial de llamadas se colapsa al reutilizar los frames.

¿Qué hacer si la implementación soporta TRO pero no TCO general, o si la optimización no cubre funciones mutuamente recursivas (el clásico even/odd)? Usamos un trampolín: codificamos la computación en una estructura de datos y la conducimos con un bucle (o con una función recursiva por la cola). La computación es una estructura TailCall que es, o bien el valor final (done), o bien un thunk (una lambda sin argumentos) que encapsula el siguiente paso (call):

result es análoga a la función strict que vimos en evaluación perezosa: aplica un paso tras otro hasta obtener un valor. Se llama «trampolín» porque el control sube y baja entre result y los thunks: result invoca el thunk, el thunk devuelve otro TailCall a result, y así sucesivamente, siempre en un tamaño de pila fijo. Si el lenguaje no tuviera TRO, result se escribiría con un while en lugar de recursión. En síntesis: el trampolín consigue TCO a partir de TRO, de forma explícita.

Extendemos el lenguaje con cuatro expresiones nuevas:

El programa objetivo, que debe reducir a 1:

En la secuencia seqn hay una propagación implícita: cuando termina la primera expresión, la caja tiene un valor nuevo, y ese valor debe verse en la segunda expresión. ¿Qué es lo que «fluye»? El primer candidato es el ambiente —pero no puede ser, porque rompería el alcance estático:

Si la mutación se propagara por el ambiente, b en la segunda expresión estaría ligado y el programa daría 3; pero por alcance estático b es un identificador libre allí, y debe fallar. Considérese también:

Aquí conviven dos reglas en tensión: la caja a es capturada por la clausura de f mediante alcance estático (regla estática), pero la mutación {setbox a 2}, que ocurre fuera de la clausura, debe afectar lo que sucede dentro (regla dinámica). El ambiente por sí solo no puede expresar ambas a la vez.

Convertimos la asociación de valores a identificadores en un proceso de dos fases, introduciendo las ubicaciones de memoria (o celdas):

Para obtener el valor de un identificador, ahora componemos dos búsquedas: primero la ubicación (en el ambiente), luego el valor (en el store).

El store se implementa igual que el ambiente (una lista enlazada); la única diferencia es que las ubicaciones son números naturales en lugar de símbolos. El ambiente cambia: ahora asocia identificadores a ubicaciones, no a valores.

Necesitamos también reclamar ubicaciones frescas, para que dos identificadores distintos no colisionen en la misma dirección. next-location cuenta los elementos del store y devuelve el siguiente índice libre:

Extendemos los valores con las cajas (boxV), que no almacenan un valor sino la ubicación donde vive su contenido; y definimos el tipo de retorno del intérprete, Value*Store, que empareja un valor con el store resultante:

Los casos que no mutan simplemente reenvían el store tal cual:

En el condicional, las mutaciones de la condición deben propagarse a la rama elegida:

En las operaciones binarias, hilamos el store de un operando al otro (decisión de diseño: de izquierda a derecha) y retornamos el último store:

La aplicación es el caso más elaborado: evaluamos la función (obteniendo fun-sto), luego el argumento en fun-sto (obteniendo arg-sto), reclamamos una ubicación nueva sobre arg-sto, y evaluamos el cuerpo extendiendo el ambiente (arg-name → new-loc) y el store (new-loc → arg-val):

Con la infraestructura lista, las primitivas son directas. Este es el código real:

setbox retorna el valor asignado (toda expresión debe retornar algún valor), pero su efecto importante es extender el store asociando la ubicación de la caja al nuevo valor. Como lookup-sto busca desde el frente, la asociación más reciente enmascara a la anterior.

Un objeto con estado. switch es una caja (0 = apagado, 1 = encendido); toggle invierte el estado. La clausura de toggle captura la caja switch (alcance estático) y la muta en cada invocación:

La función toggle recibe un argumento (dummy) que no usa —en nuestro lenguaje toda función toma exactamente un argumento. La primera invocación enciende el interruptor y retorna 1; la segunda lo apaga y retorna 0; luego 1 + 0 = 1. El resultado es 1 independientemente del orden de evaluación (porque 1 + 0 = 0 + 1). La evolución del estado, tras la primera invocación:

El ambiente permanece constante entre invocaciones; solo cambia el contenido de la ubicación 0 en el store.

Cuando una operación binaria tiene un operando con efectos, el resultado depende del orden:

Con evaluación de izquierda a derecha (nuestra decisión de diseño), el operando izquierdo muta b a 5 y retorna 5; el derecho lee b y obtiene 5; total 10. Si evaluáramos de derecha a izquierda, el derecho leería 1 primero y el total sería 6. Ninguno es «más correcto»; es una decisión del diseñador del lenguaje.

¿A qué valor se reduce un programa que muta el parámetro formal de una función y luego consulta el parámetro real?

La respuesta depende de la semántica de paso de parámetros:

Extendemos el lenguaje con un segundo tipo de función, refun (call-by-reference), que se debe invocar con un identificador como parámetro real. Añadimos el valor refclosureV para distinguir ambas clausuras:

La aplicación ahora depende del tipo de la función. Para closureV se procede como antes (ubicación fresca con una copia del valor); para refclosureV se recupera la ubicación del parámetro real (que debe ser un identificador) y se liga el formal a esa misma ubicación:

En la rama call-by-reference, (id-x arg-expr) extrae el símbolo del nodo (id …) del parámetro real (por eso refun exige que se invoque con un identificador), y lookup-env obtiene su ubicación. El formal arg-name queda como alias de esa ubicación: no se crea memoria nueva ni se copia el valor.

La única diferencia entre ambos programas es fun vs. refun. En el primero, x recibe una ubicación fresca con una copia de 0; {set x 5} muta esa copia y a sigue valiendo 0. En el segundo, x comparte la ubicación de a; {set x 5} muta directamente la variable del llamador, y consultar a da 5. Toda la diferencia semántica se reduce a qué ubicación liga el ambiente al parámetro formal.