3

Schemeのトリッキーなラムダ式に問題があり、インタープリターによってどのように評価されているかを確認したいと思います。

SICPセクション1.1.5「プロシージャアプリケーションの置換モデル」に示されているように、Schemeインタプリタにすべての評価ステップを印刷してもらいたい。

スキームインタープリターを使用した解決策を探しています。私はすでにRacketのトレースを試しましたが、すべての式ではなく、プロシージャ呼び出しのみをトレースします。

やる気を起こさせる例

SICP演習2.6からのチャーチ数の定義を考えると：

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

とタスク：

直接定義oneします（とではありません）。twozeroadd-1

との評価結果oneとの定義を確認したいと思います。two(add-1 zero)(add-1 (add-1 zero))

これは、Schemeインタープリターに印刷してもらいたいものです。

> (add-1 zero)
(add-1 (lambda (f) (lambda (x) x)))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))
>
4

2 に答える 2

2

ラケットの組み込みステッパーを試してみてください。この回答には少しハウツーがあります。

于 2013-02-16T00:40:32.537 に答える
1

これは、コンビネータのような方程式（かつて私が信じている応用スタイルと呼ばれていたもの）を使用すると非常に簡単です。

zero f x = x
add1 n f x = f (n f x)

one f x = add1 zero f x = f (zero f x) = f x         **(1)**
two f x = add1 one f x = f (one f x) = f (f x)       **(2)**

コンビネータを使用すると、すべてがカレーされます。a b c d実際(((a b) c) d)にa b c = dは、と同等(define a (lambda (b) (lambda (c) d)))です。

これで、意図された意味が明確にfなりxます。：xは、「ゼロ」データ要素fの具体的な実装を表し、「ゼロ」の特定の具体的な実装と互換性のある「後続」操作の具体的な実装を表します。fそして、x実際にはニーモニックに名前を付ける必要があります。

zero s z = z
add1 n s z = s (n s z)

それほどトリッキーな見た目ではなく、より便利な構文でしょ？lambdaとにかくそれ自体は活字事故でした。今、

one s z = s z         ; e.g. (1+ 0)
two s z = s (s z)     ; e.g. (1+ (1+ 0))

SICP 1.1.3の組み合わせ評価手順に従ってステップをトレースし、

  • 組み合わせを評価するには、次のようにします。
    1. 組み合わせの部分式を評価します。
    2. 左端の部分式（演算子）の値であるプロシージャを、他の部分式（オペランド）の値である引数に適用します。

および手順適用のための1.1.5置換モデル

  • 複合プロシージャを引数に適用するには、各仮パラメータを対応する引数に置き換えて、プロシージャの本体を評価します。

我々が得る

add1 zero = 
  ( n f x => f (n f x) ) ( f x => x ) =
  ( f x => f ( ( f x => x ) f x ) )

結果は単純なラムダ式、つまり組み合わせではないため、ここで置換は実際に停止します。さらに2つの引数が指定された場合にのみ、評価は完全に行われます。

add1 zero s z = 
  ( n f x => f (n f x) ) ( f x => x ) s z =
  ( f x => f ( ( f x => x ) f x ) ) s z =
  ( x => {s} ( ( f x => x ) {s} x ) ) z =    ; {s} is definition-of s
  {s} ( ( f x => x ) {s} {z} ) =             ; {z} is definition-of z
  ; must find the value of the operand in combination
  {s} ( ( x => x ) {z} ) = 
  {s} {z}

s次に、との実際の定義に従って計算が続行されzます。これが、上記の式（1）が短い表記で示していることです。

于 2013-02-16T21:11:23.473 に答える