¿Cuáles son los beneficios de letrec?

Question

Durante la lectura de "El sazonado Schemer" he empezado a aprender sobre letrec. Entiendo lo que hace (se puede duplicar con un Y-Combinator) pero el libro está utilizando en lugar de recurrir a la función ya defined que opera en argumentos que permanecen estáticos.

Un ejemplo de una función de edad usando la función defined 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, para 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)))

Además de ser un poco más largo y más difícil de leer que no sé por qué se están reescribiendo funciones en el libro para usar letrec. ¿Hay una mejora de la velocidad cuando se repiten más de una variable estática de esta manera porque no se mantienen al pasarlo ??

¿Es esta una práctica estándar para las funciones con argumentos que permanecer inmutable, sino un argumento que se reduce (como recurrente por los elementos de una lista)?

Algunos aportes de definitiva, los más experimentados / LISPers ayudarían!

Answer 1

Así que hay algunas respuestas que cubren el tema de la lectura, que debe estar bien. Pero una pregunta que no está claro es si hay cualquier problema de rendimiento. En un aspecto superficial, parece que la versión letrec, como el llamado let-uno (que en realidad es la misma) debe ser más rápido ya que hay menos argumentos para pasar alrededor en el bucle. Sin embargo, en la práctica, los compiladores pueden hacer todo tipo de optimizaciones detrás de la espalda, como darse cuenta de que el bucle en la versión normal pasa a los dos primeros argumentos sin cambios, y convertirlo en un bucle de un solo argumento con el primero. En lugar de mostrar que los números en un sistema en particular, aquí es un módulo PLT que se puede ejecutar en cuando cuatro versiones diferentes, y usted puede agregar fácilmente más para probar otras variaciones. El breve resumen es que en mi máquina, la versión de let llamado es un poco más rápido, y por lo que es recursiva de cola tiene un beneficio global 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 usted ejemplo específico: Personalmente, creemos que la versión letrec más fácil de leer: se define una función auxiliar recursiva y que lo haga en el cuerpo de la función de nivel superior. La principal diferencia entre las dos formas es que en forma letrec usted no tiene que especificar los argumentos estáticas una y otra vez en las llamadas recursivas, que me parece ser más limpio.

Si se compila el código, evitando el paso de los argumentos estáticos en cada llamada función recursiva es probable que también proporcionan una pequeña mejora en el 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 función recursiva se encontraba en la posición de la cola, el compilador podría ser lo suficientemente inteligente como para evitar la copia de los argumentos en la pila una y otra vez.

Del mismo modo, si se interpreta el código, que tiene menos argumentos en las llamadas recursivas será más rápido.

De forma más general, uno de los principales beneficios de letrec, que no creo que usted ha mencionado anteriormente, es el hecho de que permite la definición de funciones mutuamente recursivas. Estoy bastante experiencia con el esquema, pero por lo que tengo entendido, esta es una de las principales características de la forma letrec en comparación con, por ejemplo, define.

Answer 3

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

(define substitute
  ; stuff involving letrec
  )

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

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

En cuanto a rendimiento y facilidad de lectura, este último es probablemente una cuestión de gusto, mientras que el primero no debe diferir de manera observable (aunque no estoy muy cualificado para insistir en esto es así, y también es dependiente de la implementación de todos modos).

Además, en realidad haría uso de let llamado 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. Tu caso es distinto.