1

相互に呼び出すことができるSchemeで複数の字句スコープ関数を定義することに興味がありました。SICPで作業し、演習1.8を解決するためにブロック構造を使用して次の関数を作成しました（ニュートン法を使用して立方根を計算します）。

(define (cbrt x)
  (define (good-enough? guess prev-guess)
    (< (/ (abs (- guess prev-guess))
          guess)
       0.001))
  (define (improve guess)
    (/ (+ (/ x (square guess))
          (* 2 guess))
       3))
  (define (cbrt-iter guess prev-guess)
    (if (good-enough? guess prev-guess)
        guess
        (cbrt-iter (improve guess)
                   guess)))
  (cbrt-iter 1.0 0.0))

これは問題なく動作しますが、Scheme（およびおそらくCommon Lisp）が字句スコープとletフォームを使用してこの同じシナリオをどのように処理するのか疑問に思いました。let私は次のkludgyコードを使用してそれを実装しようとしました：

(define (cbrt x)
  (let ((calc-cbrt
         (lambda (guess prev-guess)
           (let ((good-enough?
                  (lambda (guess prev-guess)
                    (< (/ (abs (- guess prev-guess))
                          guess)
                       0.001))))
             (good-enough? guess prev-guess))
           (let ((improve
                  (lambda (guess)
                    (/ (+ (/ x (square guess))
                          (* 2 guess))
                       3))))
             (improve guess))
           (let ((cbrt-iter
                  (lambda (guess prev-guess)
                    (if (good-enough? guess prev-guess)
                        guess
                        (cbrt-iter (improve guess)
                                   guess)))))
             (cbrt-iter 1.0 0.0)))))
    (calc-cbrt 1.0 0.0)))

以下に表示される問題は、プロシージャcbrt-iterを呼び出そうとしたときです。プロシージャは最初のネストされたブロックのスコープに対してのみローカルであるため、 good-enough?それにアクセスする方法はありません。これは、の囲みの中に関数をネストすることで解決できるようですが、これも非常に厄介で厄介なようです。good-enough?letcbrt-itercbrt-iterletgood-enough

defineこの場合、それを行うフォームは何が異なりますか？フォームは「letoverlambda」フォームではなく式にdefine拡張されていますか（フォームを使用してLittle Schemerの本で同様のことが行われたことを思い出しますが、これがどのように機能するかはわかりません）。また、比較として、Common Lispはこの状況をどのように処理しますか？字句スコープのを使用することは可能ですか？lambda((lambda (x) x x) (lambda (y) ...))defun

4

1 に答える 1

1

まず、新しい手順を導入する必要はありません。代わりcalc-cbrtに呼び出すことができます。calc-iter

define第二に、との意味letはまったく異なります。 例のように、定義をローカルスコープにDefine インストールします。ただし、let式は式の単なる構文糖衣ですlambda（詳細については、SICPセクション1.3を参照してください）。結果として（そしてあなたが言及したように）、を介して宣言された変数は(let (<decl1> ...) <body>)内にのみ表示され<body>ます。したがって、(let <decls1> <body1>) (let <decls2> <body2>) ...他のスコープで見られるように定義が「存続」しないため、のパターンは機能しません。

したがって、次のように記述する必要があります。

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...))
         (cbrt-iter (lambda ...)))
     (cbrt-iter 1.0 0.0)))

少なくとも、への呼び出しcbrt-iterはの定義を見ることができますcbrt-iter。

しかし、まだ問題があります。を評価するときは、 where(cbrt-iter 1.0 0.0)の本体を評価し、値1.0と0.0を取ります。ただし、の本体では、変数とはスコープ内にありません。cbrt-iterguessprev-guesscbrt-iterimprovegood-enough?

ネストされたsを使用したくなるかもしれませんがlet、これは多くの場合、適切な選択です。

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...)))
     (let ((cbrt-iter (lambda ...)))
       (cbrt-iter 1.0 0.0))))

問題は、cbrt-iterがそれ自体を呼び出す必要があるということですが、内部の本体までスコープ内にありませんlet！

ここでの解決策は、を使用することletrecです。これはlet、本文だけでなくすべての宣言内に新しいバインディングが表示されるようにします。

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...)))
     (letrec ((cbrt-iter (lambda ...)))
       (cbrt-iter 1.0 0.0))))

letrecと同じように、相互再帰的なプロシージャを作成するために使用することもできdefineます。

letrec残念ながら、実際にどのように機能するかを説明するには時間がかかりますdefineが、ここに秘密があります。どちらも内部でミューテーションを使用して環境データ構造に循環性を作成し、再帰を可能にします。（ Yコンビネータlambdaと呼ばれる、のみを使用して再帰を作成する方法もありますが、かなり複雑で非効率的です。）

幸いなことに、これらすべての秘密は第3章と第4章で明らかになります！

別の見方をすれば、ブラウン大学のオンラインPLクラスを見ると、基本的にこのトピックに直接進みます（ただし、省略されていますdefine）が、SICPの方が、作成される複雑な環境構造を理解するのに適していることがわかります。

于 2012-10-31T01:33:16.833 に答える