教会の数字を備えた算術

StackOverflow https://stackoverflow.com/questions/3912341

質問

私はSICPを通じて働いています 問題2.6 私を不快なものに入れました。教会の数字に対処する際に、特定の公理を満たす任意の関数であるゼロと1をエンコードするという概念は理にかなっているようです。さらに、ゼロの定義とADD-1関数を使用して個々の数値の直接定式化を導き出すことは理にかなっています。プラスオペレーターをどのように形成できるか理解できません。

これまでのところ、私はこれを持っています。

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

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

ウィキペディアのエントリを調べます ラムダ計算, 、Plusの定義はPlus：=λmnfx.mf（NFX）であることがわかりました。その定義を使用して、次の手順を策定することができました。

(define (plus n m)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

私が理解していないのは、以前に派生した手順で与えられた情報のみを使用して、その手順を直接導出する方法です。誰かがこれに何らかの厳密な証拠のような形で答えることができますか？直感的には、私は何が起こっているのか理解していると思いますが、リチャード・ファインマンがかつて言ったように、「それを構築できれば理解できない...」

役に立ちましたか？

解決

実際には非常に簡単です。これはおそらくFlameBaitと見なされますが、パレンズは見るのが難しくなります - 何が起こるかを見るためのより良い方法は、あなたがカレー言語であることを想像するか、スキームにマルチアーグメント関数があるという事実を使用することです。それを受け入れます...ここにラムダと便利な複数の議論を使用する説明があります：

  • すべての数値nがエンコードされています

    (lambda (f x) ...apply (f (f (f ... (f x)))) N times...)

  • これは、nのエンコードが実際にあることを意味します

    (lambda (f x) (f^N x))

    どこ f^N 機能的な指数です。

  • これを言うより簡単な方法（カレーを仮定する）：数nは次のようにエンコードされます

    (lambda (f) f^N)

    したがって、nは実際にはaです 「nの力に上がる」 働き

  • 今、あなたの表現を取ります（中を見る lambdasここ）：

    ((m f) ((n f) x))

    以来 n 数字のエンコードであり、その指数であるため、実際には次のとおりです。

    ((m f) (f^n x))

    そして同じです m:

    (f^m (f^n x))

    そして、残りは明らかなはずです...あなたは持っています m のアプリケーション f 適用されます n のアプリケーション f 適用されます x.

  • 最後に、去る いくつかの 楽しい - ここに定義する別の方法があります plus:

    (define plus (lambda (m) (lambda (n) ((m add1) n))))

    （まあ、これはおそらくもっと明白だからです。）

他のヒント

（あなたが理解していることを確認してください 高次関数). の アロンゾ教会's 型のないラムダ計算 関数は、唯一のプリミティブデータ型です。数字、ブール人、リストなど、機能のみが機能しません。関数には1つの引数しか持たませんが、関数はこれらの関数の値ではなく関数自体を受け入れたり返すことができます。したがって、数字、ブール人、リスト、その他の種類のデータを表すには、匿名の関数がそれらを支持するための巧妙な方法を考え出す必要があります。 教会の数 表現する方法です 自然数. 。 Untyped Lambda計算の3つの最も原始的な構成要素は次のとおりです。

  1. λx.x, 、an アイデンティティ関数, 、いくつかの機能を受け入れ、すぐに返します。
  2. λx.x x, 、自己適用。
  3. λf.λx.f x, 、関数アプリケーション、関数と引数を取り、関数を引数に適用します。

機能以外は何もないとして、0、1、2をどのようにエンコードしますか？どういうわけか、の概念を構築する必要があります 量 システムに。関数のみがあり、すべての関数は1つの引数にのみ適用できます。量に似たものはどこにありますか？ねえ、パラメーターに複数回関数を適用できます！関数の3つの繰り返しの呼び出しには、明らかに量の感覚があります。 f (f (f x)). 。それでは、Lambda Calculusでエンコードしましょう。

  • 0 = λf.λx.x
  • 1 = λf.λx.f x
  • 2 = λf.λx.f (f x)
  • 3 = λf.λx.f (f (f x))

等々。しかし、0から1、または1から2にどのように移動しますか？数字を与えられた数字を返す機能をどのように書きますか？私たちは教会の数字のパターンが常にから始まるのを見ます λf.λx. そして、あなたが有限の繰り返しの適用を持っている後 f, 、だから私たちはどうにかしての体に入る必要があります λf.λx. そしてそれを別のものに包みます f. 。削減せずに抽象化の本体をどのように変更しますか？さて、関数を適用し、ボディを関数に包み、新しいボディを古いラムダの抽象化に包むことができます。しかし、あなたは議論を変更することを望まないので、同じ名前の値に抽象化を適用します。 ((λf.λx.f x) f) x → f x, 、 しかし ((λf.λx.f x) a) b) → a b, 、それは私たちが必要とするものではありません。

それが理由です add1 は λn.λf.λx.f ((n f) x): ：あなたが適用します n に f その後 x 表現を体に減らすには、適用してください f その体に、それから再びそれを抽象化します λf.λx.. エクササイズ： それが本当であることを見て、すぐに学ぶ β還元 削減します (λn.λf.λx.f ((n f) x)) (λf.λx.f (f x)) 1 x 1を増やすには。

次に、身体を別の関数の呼び出しに包む背後にある直感を理解して、2つの数値を追加するにはどうすればよいですか？与えられた関数が必要です λf.λx.f (f x) （2）および λf.λx.f (f (f x)) （3）、戻ります λf.λx.f (f (f (f (f x)))) （5）。 2を見てください 交換 これは x 3のボディで、つまり f (f (f x))？ 3のボディを取得するには、それは明らかです、ただそれを適用してください f その後 x. 。次に2を適用します f, 、しかし、それを3のボディに適用します。 x. 。次に、ラップします λf.λx. また： λa.λb.λf.λx.a f (b f x).

結論： 2つの番号を追加します a と b 一緒に、どちらも教会の数字として表されます、あなたはしたい 交換 x の a の体で b, 、 となることによって f (f x) + f (f (f x)) = f (f (f (f (f x)))). 。これを実現するには、適用してください a に f, 、次に b f x.

Eliの答えは技術的には正しいですが、この質問が尋ねられる時点から #apply 手順は紹介されていません。著者が学生がこの質問に答えることができるようにカリーなどの概念について知識を持つことを意図していたとは思いません。

彼らは、1つが置換方法を適用することを提案することにより、一方を答えにほぼ導き、そこから添加の効果が一方の数値の構成であることに気付くはずです。構成は、演習1.42で導入された概念です。そして、これがこのシステムで追加の手順がどのように機能するかを理解するために必要なすべてです。

; The effect of procedure #add-1 on `one`, and `two` was the composition of `f` 
; onto `one` and `f` onto `two`.
;
; one   : (λ (f) (λ (x) (f x)))
; two   : (λ (f) (λ (x) (f (f x))))
; three : (λ (f) (λ (x) (f (f (f x)))))
;
; Thus one may surmise from this that an additive procedure in this system would
; work by composing one number onto the other.
;
; From exercise 1.42 you should already have a procedure called #compose.
;
; With a little trial and error (or just plain be able to see it) you get the
; following solution.

(define (adder n m)
  (λ (f)
    (let ((nf (n f))
          (mf (m f)))
      (compose nf mf))))
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top