Ejemplo donde letrec/letrec * es mejor que dejarlo con definiciones internas o nombre dejado?

Question

Los dos ejemplos Kent Dybvig da en el esquema de lenguaje de programación para letrec y letrec * son:

(letrec ([sum (lambda (x) 
      (if (zero? x) 
       0 
       (+ x (sum (- x 1)))))]) 
    (sum 5)) 

y

(letrec* ([sum (lambda (x) 
      (if (zero? x) 
        0 
       (+ x (sum (- x 1)))))] 
     [f (lambda() (cons n n-sum))] 
     [n 15] 
     [n-sum (sum n)]) 
    (f)) 

La primera también se puede escribir como un let nombre:

(let sum ([x 5]) 
    ((lambda (x) 
       (if (zero? x) 
        0 
        (+ x (sum (- x 1))))) x)) 

y el segundo se puede escribir como un let con interno define:

(let() 
    (define sum (lambda (x) 
       (if (zero? x) 
       0 
        (+ x (sum (- x 1)))))) 
    (define f (lambda() (cons n n-sum))) 
    (define n 15) 
    (define n-sum (sum n)) 
    (f)) 

Las formas letrec/letrec * no parecen ser más concisas o más claras que las formas nombradas let o let con interna define.

¿Alguien me puede mostrar un ejemplo en el que letrec/letrec * mejora el código o es necesario en lugar del nombre let o let con internal define.

Answer 1

Sí, el primer ejemplo se puede reescribir usando un llamado let, pero tenga en cuenta que no hay necesidad de que la forma en que hay lambda:

(let sum ([x 5]) 
    (if (zero? x) 
    0 
    (+ x (sum (- x 1))))) 

Este tipo de transformación es un poco engañoso - es bien para hacer en caso de que esté definiendo una sola "función de bucle" (en el amplio sentido no recursivo de cola única) e inmediatamente utilícela en una entrada conocida. Pero generalmente, cuando ve ejemplos como el que dio, la intención es mostrar la definición y el uso de una función local, por lo que es posible hacer esta transformación solo porque es un ejemplo de juguete de demostración.

En segundo lugar, tenga en cuenta que una llamada let es por lo general no una forma primitiva - la estrategia de implementación que prácticamente todas las implementaciones Esquema utilizar es tener esa forma ampliar en un letrec. Por lo tanto, sigue siendo una buena idea entender letrec si quiere entender named- let s. (Y esta es una característica fundamental: poder hacer auto-referencia a través de un alcance recursivo.)

Finalmente, el ejemplo que dio con definiciones internas es similar a named-let s: es un azúcar sintáctico que se expande en un letrec (que puede ser letrec o letrec* con R5RS, y debe ser letrec* en R6RS). Entonces, para entender cómo funciona, debe comprender letrec. Tenga en cuenta también que algunas implementaciones que usan el estricto letrec también fallan en su segundo ejemplo y se quejan de que sum no está definido. Es este azucar sintáctico que está detrás del argumento principal para la semántica letrec* que se adoptó en R6RS: a muchas personas les gusta usar definiciones internas, pero luego hay un problema que las definiciones toplevel permiten usar definiciones previas pero las definiciones internas son menos convenientes en un inesperado camino. Con letrec*, las definiciones internas funcionan igual que las superiores. (Más precisamente, funcionan como nuevas definiciones de restricción de módulo, lo que significa que en realidad son como definiciones de módulo a nivel).

(Tenga en cuenta también que (a) Racket y Chez amplían los cuerpos internos para permitir definiciones y expresiones para ser mezclado, lo que significa que la expansión es tan directa.)

Answer 2

I segunda respuesta de Eli; llamado let y define interno se definen en términos de letrec.

Agregaré algunos anecddatos empíricos y numéricos a esto, sin embargo. Trabajo en una compañía que usa Scheme. Tenemos 981 archivos de códigos Scheme, que suman un total de 206,878 líneas (contando comentarios, líneas en blanco, todo). Esto fue escrito por un equipo que varió entre 8-16 personas durante unos 8 años.

Entonces, ¿cuántos usos de letrec se encuentran en esa base de código? 16. Esto se compara con aproximadamente 7.000 usos de let y let* (estimado porque no voy a molestarme en refinar la expresión regular que utilicé). También parece que todos los usos de letrec fueron escritos por el mismo tipo.

Por lo tanto, no me sorprenderá que no encontrará mucho uso práctico para letrec.

Answer 3

De algunos de los estudiantes de Kent, he aprendido lo siguiente: letrec se implementa en términos de let mediante macro expansión. Se expande el letrec en un let que usa set! dentro. Así que el primer ejemplo podría ampliar a esto:

(let 
    ([sum (void)]) 
    (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1)))))) 
    (sum 5)) 

Su segundo, de manera similar (tenga en cuenta que los anidados let s son el resultado de la let* - También, esto puede no ser una expansión del todo correcta, pero es mi mejor conjetura):

(let 
    ([sum (void)] 
    (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1)))))) 
    (let 
    [f (void)] 
    (set! f (lambda() (cons n n-sum))) 
    (let 
     [n (void)] 
     (set! n 15) 
     (let 
     [n-sum (void)]) 
     (set! n-sum (sum n)) 
     (f)) 

no estoy 600% seguro de cómo el llamado let expande, pero Eli sugiere que se llevaría a cabo en términos de letrec en sí (que tiene sentido y debe ser bastante obvio). Por lo tanto, su nombre let se mueve desde un nombre let en un letrec en un let sin nombre. Y su reescritura del segundo se ve casi exactamente como la expansión de todos modos.

Si está interpretándolo y buscando un buen rendimiento, me inclinaría hacia letrec porque es un paso más corto de expansión macro. Además, let se convierte en una lambda, por lo que está utilizando define s en su segundo ejemplo en lugar de set! s (que puede ser más pesado).

Por supuesto, si estás compilando, es probable que todo caiga en el compilador de todas formas por lo que sólo tiene que utilizar lo que usted piensa que se ve mejor (soy parcial a letrec porque let bucles me recuerdan a la programación imperativa, pero tu caso es distinto). Dicho esto, debe ser usted, estilísticamente (ya que son más o menos equivalentes).

Dicho esto, te voy a dar un ejemplo de que es posible que valga la pena:

(letrec 
([even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))] 
    [odd? (lambda (n) (if (zero? n) #f (even? (- n 1))))]) 
    (even? 88)) 

Usando su estilo interno define producirá:

(let() 
    (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))) 
    (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1))))) 
    (even? 88)) 

Así que aquí el código letrec es en realidad más corto. Y, sinceramente, si está haciendo algo así como este último, ¿por qué no conformarse con begin?

(begin 
    (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))) 
    (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1))))) 
    (even? 88)) 

Sospecho que begin es más de un built-in y, como tal, no va a conseguir-macro expandida (como let voluntad). Finalmente, a similar issue se ha generado en el desbordamiento de la pila Lisp hace un momento con más o menos el mismo punto.