ラムダ計算を使用した負と複雑な数値を表します

Question

Lambda Calculusのほとんどのチュートリアルは、正の整数とブール値を機能によって表現できる例を示しています。 -1と私はどうですか？

Answer 1

JMADによって説明されているように、最初に自然数とペアをエンコードします。

integer $ k $を自然数のペアとして表します$（a、b）$ $ k = a -b $を表します。次に、整数の通常の操作を（$ lambda $ -calculusのHaskell表記を使用）として定義できます。

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

複雑な数字の場合は、複雑な数字が一対の現実としてエンコードされるという意味で類似しています。しかし、より複雑な質問は、実際のものをエンコードする方法です。ここであなたはもっと仕事をしなければなりません：

1. 合理的な数字$ q $をペア$（k、a）$としてエンコードすると、$ k $は整数、$ a $は自然、$ q = k /（1 + a）$です。
2. function $ x $を関数$ x $をエンコードする$ f $すべての天然$ k in mathbb {n} $、$ fk $が$ | x -q | <2^{-k} $。言い換えれば、実際のものは、$ k mapsto 2^{-k} $のレートで収束する一連の合理的なものとしてエンコードされます。

本物のエンコードは多くの作業であり、$ lambda $ -calculusで実際にそれをしたくありません。しかし、たとえばを参照してください etc/haskell のサブディレクトリ マーシャル 純粋なHaskellでのレアルの簡単な実装のため。これは、原則として、純粋な$ lambda $ -calculusに翻訳される可能性があります。

Answer 2

Lambda-Calculusは、ほとんどのデータ構造と基本タイプをエンコードできます。たとえば、できます ペアをエンコードします 同じものを使用して、ラムダ計算の既存の用語の 教会のエンコーディング 通常、非陰性整数とブール値をエンコードすることがわかります。

$$ mbox {pair} =λxyz.zxy$$ $$ mbox {fst} =λp.p（λxy.x）$$ $ mbox {snd} =λp.p（λxy.y）$$

その後、ペア$（a、b）$は$ p =（ mbox {pair} ab）$です。および$（ mbox {snd} p）$。

つまり、ペアで正と負の整数を簡単に表現できます。左側のサインと右側の絶対値です。サインは、数値が正であるかどうかを指定するブール値です。権利は、教会のエンコーディングを使用する自然数です。

$$（記号、n）$$

そして今、あなたは相対的な整数を持っています。乗算は簡単に定義できます。 $ mbox {xor} $関数 サインと 自然数の乗算 絶対値について：

$$ mbox {mult}_ℤ=λab。 mbox {pair} ~~（ mbox {xor}（ mbox}（fst} a）（ mbox {fst} b））~~（ mbox {mult}_ℕ_ℕ （ mbox {snd} a）（ mbox {snd} b））$$

追加を定義するには、2つの自然数を比較し、標識が異なる場合に減算を使用する必要があります。したがって、これはλ項ではありませんが、本当にしたい場合は適応できます。

$$ mbox {add}_ℤ=λab。 left { begin {array} {ll}（ mbox {true}、 mbox {add}_ℕ（ mbox {snd} a）（ mbox {snd}}（ mbox {snd}） b））＆ mbox {if}a≥0∧b≥0（ mbox {false}、 mbox {add}_ℕ（ mbox {snd} a）（ mbox {snd} b）＆ mbox {if} a <0∧b<0 （ mbox {true}、 mbox {sub} _box {snd} a）（ mbox {snd} b））＆ mbox {if} a ≥0∧b<0∧| a |≥| b | （ mbox {false}、 mbox {sub}_ℕ（ mbox {snd} b）（ mbox {snd} a））＆ mbox {if}a≥0∧b<0∧| a | < | b | （ mbox {true}、 mbox {sub}_ℕ（ mbox {snd} b）（ mbox {snd} a））＆ mbox {if} a <0∧b≥0∧| a | < | b | （ mbox {false}、 mbox {sub}_ℕ（ mbox {snd} a）（ mbox {snd} b）＆ mbox {if} a <0∧b≥0∧| a |≥≥ | b | end {array} right。$$

しかし、その後、減算は本当に簡単に定義できます。

$$ mbox {minus}_ℤ=λa。 mbox {pair}（ mbox {not}（ mbox {fst} a））（ mbox {snd} a）$$ mbox {sub}_ℤ= λab。 mbox {add}_ℤ（a）（ mbox {minus}_ℤb）$$

正と負の整数ができたら、定義できます 複雑な整数 非常に簡単：$ a+b mbox {i} $を表す2つの整数$（a、b）$のペアです。その後、追加はポイントごとに行われ、乗算は行われます いつものように, 、しかし、私はそれを書きません、それは簡単なはずです：

$$ mbox {add} _ {ℤ[ mbox {i}]} =λz_1z_2。 mbox {pair}（ mbox {add} _box {fst} z_1）（ mbox {fst} z_2）））） （ mbox {add}_ℤ（ mbox {snd} z_1）（ mbox {snd} z_2））$$