Quais são os benefícios do letrec?

Question

Durante a leitura de "O Experiente Atacante" eu tenho começado a aprender sobre letrec.Eu entendo o que ele faz (pode ser duplicado com um Y-Combinator), mas o livro está usando ele no lugar do recorrente no já defined função operacional em argumentos que permanecer estático.

Um exemplo de uma função antigos usando o definefunção d recorrente em si mesmo (nada de 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))))))

Agora para um exemplo de que a mesma função, mas 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)))

Além de ser um pouco mais longo e mais difícil de ler, eu não sei por que eles estão a reescrever funções no livro para uso letrec.Há um melhoramento de velocidade ao recorrente através de uma variável estática desta forma, porque não continuar a passar??

É este padrão de prática para funções com argumentos que permanecer estático, mas um argumento que é reduzido (como o recorrente para baixo os elementos de uma lista)?

Algumas entradas do mais experientes Schemers/LISPers iria ajudar!

Answer 1

Então você tem algumas respostas que cobrem o problema de legibilidade, o que deve estar bem. Mas uma pergunta que não está clara é se há algum problema de desempenho. Em uma aparência superficial, parece que o letrec versão, como o nomeadolet Um (que é realmente o mesmo) deve ser mais rápido, pois há menos argumentos para passar no loop. No entanto, na prática, os compiladores podem fazer todos os tipos de otimizações pelas costas, como descobrir que o loop da versão simples passa os dois primeiros argumentos inalterados e transformá-lo em um loop de argumento único com o primeiro. Em vez de mostrar os números em um sistema específico, aqui está um módulo PLT que você pode executar para o horário de quatro versões diferentes, e você pode adicionar mais facilmente para experimentar outras variações. O breve resumo é que na minha máquina, o nomeadolet A versão é um pouco mais rápida, e torná-la recorde de cauda tem um benefício geral maior.

#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

Sobre a exemplo específico:Pessoalmente acho a letrec a versão mais fácil de ler:você definir uma recursiva função de auxiliar e chamar o corpo da função de nível superior.A principal diferença entre as duas formas é que no letrec formulário você não precisa especificar estático argumentos por mais de uma vez as chamadas recursivas, o que eu acho ser mais limpo.

Se o código é compilado, evitando a passagem de estática argumentos em cada chamada de função recursiva, provavelmente, também fornecem um pequeno benefício em termos de desempenho, neste caso, desde que o chamador evita ter de copiar os argumentos para o novo quadro de pilha.Se a chamada de função recursiva estava na cauda posição, o compilador pode ser inteligente o suficiente para evitar a cópia de argumentos na pilha e outra vez.

Da mesma forma, se o código é interpretado, tendo menos argumentos em chamadas recursivas será mais rápido.

Mais geralmente, um dos principais benefícios de letrec, que eu não acho que você mencionou acima, é o fato de que ele permite mutuamente recursivas definições de função.Eu sou muito inexperiente com o esquema, mas até onde eu entendo, esse é um dos principais recursos do letrec formulário comparado ao eg define.

Answer 3

Por um lado, o letrec A versão permite que você use a função, mesmo que seu nome global seja redefinido para outra coisa, por exemplo,

(define substitute
  ; stuff involving letrec
  )

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

Então sub ainda funcionará, enquanto não será com o nãoletrec versão.

Quanto ao desempenho e legibilidade, o último é provavelmente uma questão de gosto, enquanto o primeiro não deve diferir de forma observável (embora eu não esteja realmente qualificado para insistir em isso assim, e também depende da implementação).

Além disso, eu realmente usaria nomeado let pessoalmente:

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

Acho isso mais legível dessa maneira. Ymmv.