functional-programming - drracket - if racket documentation

¿Cuáles son los beneficios de letrec?

Question

Mientras leía "The Seasoned Schemer", comencé a aprender sobre letrec . Entiendo lo que hace (se puede duplicar con un Y-Combinator) pero el libro lo está utilizando 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 antigua que usa la función define d que se repite sobre sí misma (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 usando 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 las funciones del libro para usar letrec. ¿Hay una mejora de la velocidad cuando se repite sobre una variable estática de esta manera porque no sigues pasándola?

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

¡Algún aporte de Schemers / LISPers más experimentados ayudaría!

Answer 1

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

#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

Con respecto a su ejemplo específico: Personalmente, encuentro que la versión de letrec más fácil de leer: usted define una función de ayuda recursiva y la llama en el cuerpo de la función de nivel superior. La principal diferencia 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, lo que encuentro más limpio.

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 manera 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 haya mencionado anteriormente, es el hecho de que permite definiciones de funciones recursivas entre sí. No tengo mucha experiencia con el esquema, pero, según tengo entendido, esta es una de las características principales de la forma letrec comparación con, por ejemplo, define .

Answer 3

Por un lado, la versión letrec permite usar 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)

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

En cuanto al rendimiento y la legibilidad, esta última es probablemente una cuestión de gustos, mientras que la primera no debería diferir de manera visible (aunque no estoy realmente calificado para insistir en que esto sea así, y también depende de la implementación).

Además, en realidad usaría el nombre de 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 parece más legible de esta manera. YMMV.