Quali sono i vantaggi di letrec?

Question

Durante la lettura di "The Seasoned Schemer" ho cominciato a conoscere letrec. Capisco ciò che fa (può essere duplicato con un Y-Combinator) ma il libro sta utilizzando al posto di correnti in funzione già defined operante su argomenti che restano statici.

Un esempio di una vecchia funzione utilizzando la funzione defined ricorrenti su se stesso (niente di speciale):

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

Ora, per un esempio di quella stessa funzione, ma con 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)))

Oltre ad essere un po 'più a lungo e più difficile da leggere non so perché sono funzioni riscrivendo nel libro per usare letrec. C'è un aumento di velocità quando ricorrenti su una variabile statica in questo modo perché non si tiene passarlo ??

È questo una pratica standard per le funzioni con argomenti che rimangono statiche, ma un argomento che viene ridotta (come ad esempio le ricorrenti elementi di una lista)?

Alcuni input da Intriganti più esperti / LISPers aiuterebbe!

Answer 1

In modo da avere alcune risposte che riguardano la questione leggibilità, che dovrebbe andare bene. Ma una domanda che non è chiaro è se ci sono eventuali problemi di prestazioni. Su uno sguardo superficiale, sembra che la versione letrec, come il nome-let uno (che in realtà è lo stesso) dovrebbe essere più veloce in quanto ci sono meno argomenti da passare in giro per il ciclo. Tuttavia, in pratica compilatori possono fare tutti i tipi di ottimizzazioni dietro la schiena, come la figura che il ciclo nella versione pianura passa i primi due argomenti invariato, e trasformarlo in un ciclo singolo argomento con il primo. Invece di mostrare i numeri su un particolare sistema, qui è un modulo PLT che è possibile eseguire in volta quattro versioni differenti, e si può facilmente aggiungere di più per provare altre varianti. La breve sintesi è che sulla mia macchina, la versione di nome-let è leggermente più veloce, e rendendo ricorsiva in coda ha un beneficio complessivo più 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

Per quanto riguarda voi esempio specifico: personalmente trovo la versione letrec più facile da leggere: si definisce una funzione di supporto ricorsiva e si chiamano nel corpo della funzione di primo livello. La differenza principale tra le due forme è che nella forma letrec non c'è bisogno di specificare gli argomenti statiche più e più volte nelle chiamate ricorsive, che trovo ad essere più pulita.

Se il codice viene compilato, evitando il passaggio degli argomenti statici su ogni chiamata di funzione ricorsiva probabilmente anche fornire un piccolo miglioramento delle prestazioni in questo caso, poiché il chiamante evita di dover copiare gli argomenti nel nuovo stack frame. Se la chiamata di funzione ricorsiva è stato nella posizione di coda, il compilatore potrebbe essere abbastanza intelligente per evitare di copiare gli argomenti sullo stack più e più volte.

Allo stesso modo se il codice viene interpretato, avendo un minor numero di argomenti nelle chiamate ricorsive sarà più veloce.

Più in generale, uno dei principali vantaggi di letrec, che non credo che lei ha citato sopra, è il fatto che esso permette di definizioni di funzioni ricorsive reciprocamente. Sono abbastanza inesperto con lo schema, ma per quanto ho capito, questa è una delle caratteristiche principali del modulo letrec rispetto a esempio define.

Answer 3

Per prima cosa, la versione letrec consente di utilizzare la funzione anche se il suo nome globale viene reimpostato a qualcos'altro, per esempio.

(define substitute
  ; stuff involving letrec
  )

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

Poi sub sarà ancora lavorare, mentre sarebbe non con la versione non letrec.

Per quanto riguarda le prestazioni e la leggibilità, il secondo è probabilmente una questione di gusto, mentre il primo non dovrebbe differire observably (anche se non sono veramente qualificato a insistere su questo essere così, e anche la sua implementazione-dipendente in ogni caso).

Inoltre, mi piacerebbe in realtà uso di nome 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
    ))

Lo trovo più leggibile in questo modo. YMMV.