17

「TheSeasonedSchemer」を読みながら、私はについて学び始めましたletrec。私はそれが何をするのかを理解しています（Y-Combinatorで複製できます）が、本はdefine静的なままの引数で動作するすでにd関数を繰り返す代わりにそれを使用しています。

defineそれ自体で繰り返されるd関数を使用する古い関数の例（特別なことは何もありません）：

(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からのいくつかの入力が役立ちます！

4

3 に答える 3

16

したがって、読みやすさの問題をカバーするいくつかの答えがありますが、それは問題ないはずです。ただし、不明な質問の1つは、パフォーマンスの問題があるかどうかです。浅い見た目では、名前付きバージョン（実際には同じ）のletrecようなバージョンletは、ループ内で渡す引数が少ないため、より高速である必要があるようです。ただし、実際には、コンパイラは、プレーンバージョンのループが最初の2つの引数を変更せずに渡し、最初の引数を使用して単一の引数のループに変換するなど、あらゆる種類の最適化を実行できます。特定のシステムの数値を表示する代わりに、4つの異なるバージョンの時間を計測するために実行できる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))
于 2010-01-14T02:10:24.493 に答える
4

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

コードがコンパイルされている場合、各再帰関数呼び出しで静的引数を渡さないようにすると、呼び出し元が引数を新しいスタックフレームにコピーする必要がなくなるため、この場合はパフォーマンスがわずかに向上する可能性があります。再帰関数呼び出しがテール位置にあった場合、コンパイラーは、スタック上の引数を何度もコピーすることを回避するのに十分賢い可能性があります。

同様に、コードが解釈される場合、再帰呼び出しの引数が少ないほど高速になります。

より一般的には、letrec上記ではないと思いますが、の主な利点の1つは、相互再帰的な関数定義が可能になることです。私はスキームにかなり不慣れですが、私が理解している限り、これは、letrecたとえばと比較して、フォームの主な機能の1つですdefine。

于 2010-01-13T22:46:27.707 に答える
4

1つには、このletrecバージョンでは、グローバル名が別の名前にリセットされた場合でも、関数を使用できます。

(define substitute
  ; stuff involving letrec
  )

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

その後subも機能しますが、非letrecバージョンでは機能しません。

パフォーマンスと読みやすさに関しては、後者はおそらく好みの問題ですが、前者は目に見えて異なるべきではありません（私はこれを主張する資格はありませんが、とにかく実装に依存します）。

また、私は実際に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。

于 2010-01-13T22:49:19.373 に答える