¿Cómo se implementa "letrec" sin usar "set!"?

Question

¿Cómo se puede implementar letrec sin usar set!?

Me parece que set! es una construcción de programación imperativa, y que al usarla, uno pierde los beneficios de la programación funcional.

Answer 1

Sé que por lo general pedimos que se copie el contenido, pero no hay una respuesta breve a su pregunta. http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Answer 2

No solo porque una función funcional se implementa con un código imperativo entre bastidores, eso no hace que la característica sea imprescindible. Nuestras máquinas de computación son imperativas; ¡entonces en algún momento todo código funcional debe ser implementado por traducción al código imperativo!

La clave para entender aquí es la siguiente: la programación funcional se refiere a interfaz, no aplicación. Una pieza de código es funcional si ese código en sí no puede observar los efectos secundarios, incluso si los efectos secundarios de hecho ocurren detrás de escena. Es decir, si comprueba el valor de la misma vinculación de la misma variable varias veces, obtendrá el mismo valor, incluso si ese valor, detrás de las escenas, se puso allí mediante el uso de set!.

En el caso de letrec, hay un pequeño inconveniente aquí: el resultado es indefinido si la evaluación de cualquiera de los enlaces en el letrec hace que otro se desenderece. Por lo tanto, el resultado de este código no está definido:

(letrec ((foo bar) 
     (bar 7)) 
    (cons foo bar)) 

El valor de foo en el cuerpo de la letrec no está definido. El resultado de los siguientes, por otro lado, se define:

(letrec ((foo (lambda() bar)) 
     (bar 7)) 
    (cons (foo) bar)) 

Esto es porque la evaluación de la lambda captura la referencia a la barra, pero el valor real no se levantó hasta que el cierre se ejecuta en el cuerpo.