¿Cuáles son los beneficios de letrec?

Question

Mientras leía "The Seasoned Schemer", comencé a aprender sobre letrec. Entiendo lo que hace (puede duplicarse con un Y-Combinator) pero el libro lo está usando en lugar de recurrir en la función d ya define que opera en argumentos que permanecen estáticos.

Un ejemplo de una función de edad usando la función define d recurrentes sobre sí mismo (nada especial):

(define (substitute new old l) 
    (cond 
    ((null? l) '()) 
    ((eq? (car l) old) 
     (cons new (substitute new old (cdr l)))) 
    (else 
     (cons (car l) (substitute new old (cdr l)))))) 

Ahora un ejemplo de esa misma función pero utilizando letrec:

(define (substitute new old l) 
    (letrec 
    ((replace 
     (lambda (l) 
     (cond 
      ((null? l) '()) 
      ((eq? (car l) old) 
      (cons new (replace (cdr l)))) 
      (else 
      (cons (car l) (replace (cdr l)))))))) 
(replace lat))) 

Aparte de ser un poco más largo y más difícil de leer, no sé por qué están reescribiendo funciones en el libro para usar letrec. ¿Hay una mejora de velocidad cuando se repite sobre una variable estática de esta manera porque no la sigues pasando?

¿Es esta práctica estándar para funciones con argumentos que permanecen estáticos pero con un argumento reducido (como recurrir a los elementos de una lista)?

¡Alguna contribución de los Schemers/LISPers más experimentados sería útil!

Answer 1

Así que tiene algunas respuestas que cubren el problema de legibilidad, lo cual debería estar bien. Pero una pregunta que no está clara es si hay problemas de rendimiento. En un aspecto superficial, parece que la versión letrec, como la llamada con nombre let (que es realmente la misma) debería ser más rápida ya que hay menos argumentos para pasar en el ciclo. Sin embargo, en la práctica los compiladores pueden hacer todo tipo de optimizaciones a sus espaldas, como descubrir que el ciclo en la versión simple pasa los dos primeros argumentos sin cambios, y convertirlo en un ciclo de argumento único con el primero. En lugar de mostrarle los números en un sistema particular, aquí hay un módulo PLT que puede ejecutar para cronometrar cuatro versiones diferentes, y puede agregar fácilmente más para probar otras variaciones. El breve resumen es que en mi máquina, la versión let llamada es un poco más rápida, y por lo que es recursivo de cola tiene un beneficio general más grande.

#lang scheme 

;; original version 
(define (substitute1 new old l) 
    (cond [(null? l) '()] 
     [(eq? (car l) old) (cons new (substitute1 new old (cdr l)))] 
     [else (cons (car l) (substitute1 new old (cdr l)))])) 

;; letrec version (implicitly through a named-let) 
(define (substitute2 new old l) 
    (let loop ([l l]) 
    (cond [(null? l) '()] 
      [(eq? (car l) old) (cons new (loop (cdr l)))] 
      [else (cons (car l) (loop (cdr l)))]))) 

;; making the code a little more compact 
(define (substitute3 new old l) 
    (let loop ([l l]) 
    (if (null? l) 
     '() 
     (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) 
      (loop (cdr l)))))) 

;; a tail recursive version 
(define (substitute4 new old l) 
    (let loop ([l l] [r '()]) 
    (if (null? l) 
     (reverse r) 
     (loop (cdr l) 
      (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) r))))) 

;; tests and timings 

(define (rand-list n) 
    (if (zero? n) '() (cons (random 10) (rand-list (sub1 n))))) 

(for ([i (in-range 5)]) 
    (define l (rand-list 10000000)) 
    (define new (random 10)) 
    (define old (random 10)) 
    (define-syntax-rule (run fun) 
    (begin (printf "~a: " 'fun) 
      (collect-garbage) 
      (time (fun new old l)))) 
    ;; don't time the first one, since it allocates a new list to use later 
    (define new-list (substitute1 new old l)) 
    (unless (and (equal? (run substitute1) new-list) 
       (equal? (run substitute2) new-list) 
       (equal? (run substitute3) new-list) 
       (equal? (run substitute4) new-list)) 
    (error "poof")) 
    (newline)) 

Answer 2

En cuanto a su ejemplo específico: Personalmente, la versión letrec me resulta más fácil de leer: define una función auxiliar recursiva y la llama en el cuerpo de la función de nivel superior. La diferencia principal entre los dos formularios es que en el formulario letrec no tiene que especificar los argumentos estáticos una y otra vez en las llamadas recursivas, que considero más limpias.

Si se compila el código, evitar el paso de los argumentos estáticos en cada llamada de función recursiva probablemente también proporcionará un pequeño beneficio de rendimiento en este caso ya que la persona que llama evita tener que copiar los argumentos en el nuevo marco de pila. Si la llamada a la función recursiva estaba en la posición de cola, el compilador podría ser lo suficientemente inteligente como para evitar copiar los argumentos en la pila una y otra vez.

De forma similar, si se interpreta el código, tener menos argumentos en las llamadas recursivas será más rápido.

Más en general, uno de los principales beneficios de letrec, que no creo que hayas mencionado anteriormente, es el hecho de que permite definiciones de funciones mutuamente recursivas. Tengo bastante experiencia con el esquema, pero hasta donde yo entiendo, esta es una de las principales características del formulario letrec en comparación con, por ejemplo, define.

Answer 3

Por un lado, la versión letrec le permite usar la función incluso si su nombre global se restablece a otra cosa, p.

(define substitute 
    ; stuff involving letrec 
) 

(define sub substitute) 
(set! substitute #f) 

Entonces sub seguirá funcionando, mientras que sería no con la versión no letrec.

En cuanto a rendimiento y legibilidad, este último es probablemente una cuestión de gusto, mientras que el primero no debe diferir observablemente (aunque no estoy realmente calificado para insistir en que esto sea así, y también depende de la implementación).

Además, me gustaría en realidad utilizan named let personalmente:

(define (substitute new old lat) ; edit: fixed this line 
    (let loop (
      ; whatever iteration variables are needed + initial values 
      ) 
    ; whatever it is that substitute should do at each iteration 
    )) 

Me resulta más fácil de leer de esta manera. YMMV.