3

私は本「コンピュータープログラムの構造と実装」に取り組んでおり、章の1つに、数値の階乗を計算するために使用されるコードがいくつかありました。

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count)))

この本の前半で、次のように関数を別の関数にインラインで定義できることを学びました。

(define (factorial n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count)))
  (fact-iter 1 1 n))

2 番目のアプローチを使用するfact-iterと、の範囲外ではアクセスできないことはわかっていますfactorialが、2 番目のバージョンのfactorial?

シンボルの新しいローカル バインディングfact-iterが定義され、新しい関数が作成されるか、このバインディングはプログラムのコンパイル時に 1 回だけ作成されますか?

私はJavaのバックグラウンドから来ていますが、これはまだ明確ではありません。

4

2 に答える 2

4

むしろ、Scheme の実装に依存します (その戦略については、SICPの後続の章で説明します)。概念的には、新しい関数は、そのfactorial2 番目の定義ごとに各呼び出しで定義/コンパイルされます。ただし、優れたコンパイラはこのコードを変換して、最初の定義に近づけることができます。

この構文はSchemeで非常に一般的であるため(ループを記述する慣用的な方法は名前付きlet構文であり、その場で関数を定義することもできます)、Schemeコンパイラはこの最適化を行うのに非常に優れているはずです。実際、内部関数の定義は実際には外部関数によってバインドされた変数に依存しないため、オプティマイザの例は簡単に処理できるため、ほとんどそのまま持ち上げることができます(名前のみを変更する必要がある場合があります)。 .

于 2013-03-06T14:59:31.083 に答える
2

factorial を呼び出すたびに新しい関数がコンパイルされることは決してありません。関数は正式にはコードの一部であり、環境です。呼び出しごとに変化する環境です。例えば：

(define (find x l)
  (define (equal-to-x y) (equal? x y))
  ....)

上記では、「find」を呼び出すたびに、新しい関数「equal-to-x」が生成されます。「equal-to-x」関数の「環境」は、別のスコープで定義されている変数「x」を参照しています。ただし、適切に優れたコンパイラは、 equal-to-x が返されたり、範囲外の変数にバインドされたりしないことに気付く場合があります。したがって、コンパイラはコードを「インライン化」する可能性があります。したがって、新しい関数 (コード + 環境) は必要ありません。

あなたのコードでは、内部的に定義されたファクト イター (2 番目のケース) の自由参照 (+、*、および >) はすべてグローバルに定義されており、ファクト イター関数は返されません (またはバインドされます)。したがって、十分に優れたコンパイラはそれをインライン化します。

これはあまり良くないコンパイラのケースです。「find」の逆アセンブリで関数/クロージャ (コード + 環境) が作成され、「ex」の逆アセンブリで環境参照が使用されている (「x」で取得する) ことがわかります。

=> (define find (lambda (x l) 
     (define ex (lambda (y) (= x y))) 
     (ex (car l))))
(=>)
=> (sys:disassemble find)
;; Address  :  0x00327e90
;; Label    :  find
;; Constants:
;;         0:  #t
;;         1:  #[<code> ex 1]
;;         2:  (<cons> 6)
;; Code     :
;;       0-1:  explode 2
;;       2-3:  check 2
;;       4-5:  get-loc 0
;;       6-8:  closure 1, 1
;;      9-10:  get-loc 2
;;     11-13:  get-loc-res 1, 2
;;        14:  cons$car
;;     15-16:  call-tail-check 1
;;          :
;; Address  :  0x0031fb40
;; Label    :  ex
;; Constants:
;;         0:  #t
;;         1:  (<number> 1 142 42 154 158)
;; Code     :
;;       0-1:  explode 1
;;       2-3:  check 1
;;       4-6:  get-env-res 0, 1
;;       7-9:  get-loc-res 0, 1
;;        10:  number$=
;;     11-12:  return 1
;;          :
;; Env      :
#[<function> find 2]
于 2013-03-06T15:15:27.163 に答える