Quels sont les avantages de letrec?

Question

Lors de la lecture « Le assaisonné Schemer » J'ai commencé à en apprendre davantage sur letrec. Je comprends ce qu'il fait (peut être dupliqué avec un Y-Combinator) mais le livre est de l'utiliser en lieu et place de la fonction récurrente déjà defined opérant sur des arguments qui restent statiques.

Un exemple d'une ancienne fonction en utilisant la fonction defined récurrente sur elle-même (rien de spécial):

(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))))))

Voici donc un exemple de cette même fonction, mais en utilisant 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)))

En plus d'être un peu plus long et plus difficile à lire, je ne sais pas pourquoi ils réécrivent fonctions dans le livre d'utiliser letrec. Y at-il une amélioration de la vitesse lorsque récurrente sur une variable statique de cette façon parce que vous ne gardez pas le passer ??

Est-ce une pratique courante pour les fonctions avec des arguments qui restent statiques, mais un argument qui est réduit (comme les éléments récurrents en bas d'une liste)?

Certains commentaires des intrigants plus expérimentés / LISPers contribueraient!

Answer 1

Vous avez donc quelques réponses qui couvrent la question de la lisibilité, ce qui devrait être bien. Mais une question qui ne sait pas est de savoir s'il y a des problèmes de performance. Sur un regard superficiel, il semble que la version letrec, comme le nom-let un (qui est vraiment le même) devrait être plus rapide car il y a moins d'arguments pour passer autour de la boucle. Cependant, dans la pratique compilateurs peuvent faire toutes sortes d'optimisations derrière votre dos, comme la figure que la boucle dans la version simple passe les deux premiers arguments inchangés, et la transformer en une boucle simple altercation avec le premier. Au lieu de vous montrer les chiffres sur un système particulier, voici un module CPL que vous pouvez exécuter en temps quatre versions différentes, et vous pouvez facilement ajouter plus d'essayer d'autres variantes. Le bref résumé est que sur ma machine, la version nommée-let est légèrement plus rapide, et ce qui en fait récursive a un avantage global plus important.

#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 ce qui concerne vous exemple précis: Personnellement, je trouve la version letrec plus facile à lire: vous définissez une fonction d'aide récursive et que vous appelez dans le corps de la fonction de haut niveau. La principale différence entre les deux formes est que sous la forme de letrec vous ne devez pas spécifier les arguments statiques maintes et maintes fois dans les appels récursifs, que je trouve être plus propre.

Si le code est compilé, en évitant le passage des arguments statiques sur chaque appel de fonction récursive sera probablement fournir aussi un petit avantage de performance dans ce cas puisque l'appelant évite d'avoir à copier les arguments dans le nouveau cadre de pile. Si l'appel de fonction récursive était en position de queue, le compilateur peut-être assez intelligent pour ne pas copier les arguments sur la pile, encore et encore.

De même, si le code est interprété, ayant moins d'arguments dans les appels récursifs sera plus rapide.

De manière plus générale, l'un des principaux avantages de letrec, que je ne pense pas que vous avez mentionné ci-dessus, est le fait qu'il permet de définitions de fonctions mutuellement récursives. Je suis tout à fait sans expérience avec le schéma, mais pour autant que je comprends, c'est l'une des principales caractéristiques de la forme de letrec par rapport à, par exemple define.

Answer 3

D'une part, la version letrec vous permet d'utiliser la fonction même si son nom global est remis à zéro à autre chose, par exemple.

(define substitute
  ; stuff involving letrec
  )

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

Alors sub va toujours fonctionner, alors qu'il ne serait pas avec la version non-letrec.

En ce qui concerne les performances et la lisibilité, ce dernier est sans doute une question de goût, alors que le premier ne diffèrent pas observable (bien que je ne suis pas vraiment qualifié pour insister sur ce qui est ainsi, et aussi est dépendante de la mise en œuvre de toute façon).

En outre, je fait personnellement utiliser let nommé:

(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
    ))

Je trouve plus facile à lire de cette façon. YMMV.