letrecの利点は何ですか？

Question

「味付けスキーマー」を読んでいる間、

私はletrecについて学ぶために始めました。私はそれが何をするかを理解する（Y-Combinatorのと重複することができます）が、本は静止したままの引数で動作し、既にdefined機能に繰り返しの代わりにそれを使用しています。

自体に繰り返しdefined機能（何も特別な）を使用して、古い機能の例：

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

次に、同じ関数の例が、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)))

さておき、彼らはletrecを使用するブック内の関数を書き換えている理由を私は知らない読み取るために少し長く、より困難であることから。あなたは??それを渡して保管しないため、静的変数の上にこの方法を繰り返し高速化があります。

は、（そのようなリストの要素を下に繰り返しなど）が低減される静止したままの引数が、1つの引数を持つ関数については、この標準的な慣行ですか？

より多くの経験を積んSchemers / LISPersからいくつかの入力が役立つだろう！

Answer 1

だからあなたは問題ないはず読みやすさの問題をカバーし、いくつかの答えを持っています。しかし、不明である一つの質問には、任意のパフォーマンスの問題があるかどうかです。浅い表情で、（実際には同じである）という名前-letrecのようなletバージョンは、ループ内で周り渡すために以下の引数がありますので、速くなければならないことと思われます。しかし、実際にはコンパイラは、プレーンバージョンのループは最初の二つの引数そのまま渡すことを図のように、あなたの後ろの最適化のすべての種類を行うことができ、かつ最初のもので単一引数のループにそれを回します。代わりに、特定のシステム上であなたに数字を示すのは、ここであなたが時間に四つの異なるバージョンを実行することができますPLTモジュールであり、そして、あなたは簡単に他のバリエーションを試すために、よりを追加することができます。短い要約は、私のマシン上で、名前付きletのバージョンが少し速くなり、そしてそれを末尾再帰を作ることは、より大きな全体的な利益を有していることである。

#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

あなたの具体的な例について：個人的に私はletrecバージョンに読みやすくを見つける：あなたは、再帰的なヘルパー関数を定義すると、あなたはトップレベルの関数の本体でそれを呼び出します。二つの形式の主な違いは、letrecフォームにあなたは私がきれいであることがわかり再帰呼び出し、中に何度も何度も静的引数を指定する必要がないことです。

コードがコンパイルされている場合は、発信者が新しいスタックフレームに引数をコピーする必要がなくなりますので、

、各再帰関数呼び出しに静的引数を渡すことを避けることは、おそらく、この場合にも、小さなパフォーマンス上の利点を提供します。再帰関数呼び出しが末尾位置にあった場合、コンパイラは何度も何度もスタックに引数をコピー回避するのに十分賢いかもしれません。

コードが解釈された場合に

同様に、再帰呼び出しに少ない引数を持つことが速くなります。

より一般的に、私はあなたが上記とは思わないletrecの主な利点の一つは、それが相互再帰関数の定義を可能にしているという事実です。私は、スキームにはかなり未経験だけど、私の知る限り理解し、これは例えばに比べletrecフォームの主な特徴の一つでありますdefineます。

Answer 3

一つには、letrecバージョンを使用すると、そのグローバル名は何か他のもの、例えばにリセットされた場合でも機能を使用することができます。

(define substitute
  ; stuff involving letrec
  )

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

それは非subバージョンではないでしょうに対し、

次にletrecはまだ、動作します。

（私はこれがそうであることを主張して本当に資格はないですけれども、また、それはとにかく実装依存です）前者はobservably異なるべきではありませんしながら、

パフォーマンスと読みやすさのためとして、後者は、おそらく好みの問題です。

また、私は実際に個人的に名前のletを使用すると思います：

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

私はこの方法でそれがより読みやすい見つけます。 YMMVます。