Mewakili Bilangan Negatif dan Kompleks Menggunakan Lambda Calculus

Sebagian besar tutorial tentang Lambda Calculus memberikan contoh di mana Integer Positif dan Boolean dapat diwakili oleh Fungsi. Bagaimana dengan -1 dan saya?

data-structures lambda-calculus integers real-numbers zcaudate
sumber

Jawaban:

Pertama mengkodekan bilangan dan pasangan alami, seperti yang dijelaskan oleh jmad.

Mewakili integer sebagai pasangan bilangan asli sedemikian rupa sehingga . Kemudian Anda dapat mendefinisikan operasi pada integer sebagai (menggunakan notasi Haskell untuk -calculus): $k$ $(a,b)$ $k = a - b$ $\lambda$

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)

Kasus bilangan kompleks serupa dalam arti bahwa bilangan kompleks dikodekan sebagai pasangan real. Tetapi pertanyaan yang lebih rumit adalah bagaimana menyandikan real. Di sini Anda harus melakukan lebih banyak pekerjaan:

Encode bilangan rasional sebagai pasangan mana adalah bilangan bulat, adalah alami, dan . $q$ $(k,a)$ $k$ $a$ $q = k / (1 + a)$
Mengkodekan bilangan real dengan fungsi sedemikian rupa sehingga untuk setiap alam , mengkodekan bilangan rasional sedemikian rupa sehingga . Dengan kata lain, real dikodekan sebagai urutan rasional yang konvergen pada laju . $x$ $f$ $k \in \mathbb{N}$ $f k$ $q$ $|x - q| < 2^{-k}$ $k \mapsto 2^{-k}$

Pengkodean real adalah banyak pekerjaan dan Anda tidak ingin benar-benar melakukannya dalam -kalkulus. Tetapi lihat misalnya subdirektori Marshall untuk implementasi sederhana real di Haskell murni. Ini pada prinsipnya dapat diterjemahkan ke dalam -calculus murni . $\lambda$ etc/haskell $\lambda$

Andrej Bauer
sumber

Wow =) Saya bertanya-tanya secara intuitif apa artinya ... misalnya, menggunakan pengkodean angka gereja ... yaitu. sejumlah gereja nilai integer n diwakili oleh fungsi yang menerapkan fungsi ke nilai n kali. Apakah pasangan dan nilai lambda negatif memiliki perasaan intuitif yang sama tentang mereka?

zcaudate

Pengkodean gereja mengkodekan bilangan asli

, ... Itu tidak mengkodekan angka negatif. Dalam jawaban di atas saya berasumsi Anda sudah tahu tentang pengkodean bilangan alami, jadi saya menjelaskan cara mendapatkan bilangan bulat. Bilangan bulat ketika saya menyandikannya adalah konstruksi yang lebih formal, tidak seperti angka Gereja, yang lebih rumit terhubung dengan

-kalkulus. Saya tidak berpikir "nilai lambda negatif" adalah ungkapan yang bermakna.

0

$0$

1

$1$

2

$2$

λ

$\lambda$

Andrej Bauer

@zcaudate [Type penjelasan: i:ℤ, x:a, f,u,s:a→a, p:(a→a,a→a)] Jika Anda menyandikan ℤ sebagai (Sign,ℕ)kemudian, diberi sepasang fungsi (s,f)sebagai p, istilah λi.λp.λx.(fst i) (fst p) id ((snd i) (snd p) x)akan menghasilkan baik f(…f(x)…)atau s(f(…f(x)…))(jika hasilnya negatif). Jika Anda menyandikan ℤ as (ℕ,ℕ), Anda memerlukan fungsi yang memiliki invers - diberi pasangan (f,u)dan x, fungsi λi.λp.λx.(snd i)(snd p)((fst i)(fst p) x)akan menghasilkan u(…u(f(…f(x)…))…)yang akan membiarkan waktu yang fditerapkan . Keduanya bekerja dalam konteks yang berbeda (hasilnya dapat "dibalik" | | tidak dapat dibalik). ixf

tidak ada yang

@zcaudate Fungsi-fungsi tambahan diperlukan karena angka yang dikodekan Gereja "muncul kembali sendiri", tetapi pasangan hanya akan memberikan komponennya kepada Anda. Fungsi helper hanya merekatkan komponen bersama-sama dalam urutan "benar" (yang terjadi secara otomatis untuk nats.) Lihat juga: en.wikipedia.org/wiki/… - Pengkodean gereja pada dasarnya fold . ctoruntuk setiap konstruktor dan tipe itu fold( r). (Itulah sebabnya, untuk jenis rekursif, data akan "recurse sendiri" Untuk jenis non-rekursif itu lebih seperti. case/ Pola pertandingan.)

tidak ada yang

Lambda-calculus dapat menyandikan sebagian besar struktur data dan tipe dasar. Misalnya, Anda dapat menyandikan sepasang istilah yang ada dalam kalkulus lambda, menggunakan pengkodean Gereja yang sama yang biasanya Anda lihat untuk menyandikan bilangan bulat non-negatif dan boolean:

pasangan = λ x y z . z x y

$\mbox{pair}= λxyz.zxy$

pertama = λ hal . hal (λ x y . x)

$\mbox{fst} = λp.p(λxy.x)$

snd = λ hal . hal (λ x y . y)

$\mbox{snd} = λp.p(λxy.y)$

Maka pasangan adalah dan jika Anda ingin mendapatkan kembali dan Anda dapat melakukan dan . $(a,b)$ $p=(\mbox{pair }ab)$ $a$ $b$ $(\mbox{fst }p)$ $(\mbox{snd }p)$

Itu berarti bahwa Anda dapat dengan mudah mewakili bilangan bulat positif dan negatif dengan pasangan: tanda di sebelah kiri dan nilai absolut di sebelah kanan. Tanda itu adalah boolean yang menentukan apakah angka itu positif. Hak adalah nomor alami menggunakan pengkodean Gereja.

(s i g n, n)

$(sign,n)$

$\mbox{xor}$

{mult}_{ℤ} = λ Sebuah b . pasangan (xor (pertama Sebuah) (pertama b)) ({mult}_{ℕ} (snd Sebuah) (snd b))

$\mbox{mult}_ℤ=λab.\mbox{pair} ~~(\mbox{xor}(\mbox{fst }a)(\mbox{fst }b)) ~~(\mbox{mult}_ℕ(\mbox{snd }a)(\mbox{snd }b))$

Untuk mendefinisikan tambahan, Anda harus membandingkan dua bilangan asli dan menggunakan pengurangan ketika tanda-tanda berbeda, jadi ini bukan istilah λ tetapi Anda dapat menyesuaikannya jika Anda benar-benar ingin:

{add}_{ℤ} = λ a b . {\begin{cases} (true, {add}_{ℕ} (snd a) (snd b)) & if a \geq 0 \land b \geq 0 \\ (false, {add}_{ℕ} (snd a) (snd b)) & if a < 0 \land b < 0 \\ (true, {sub}_{ℕ} (snd a) (snd b)) & if a \geq 0 \land b < 0 \land | a | \geq | b | \\ (false, {sub}_{ℕ} (snd b) (snd a)) & if a \geq 0 \land b < 0 \land | a | < | b | \\ (true, {sub}_{ℕ} (snd b) (snd a)) & if a < 0 \land b \geq 0 \land | a | < | b | \\ (false, {sub}_{ℕ} (snd a) (snd b)) & if a < 0 \land b \geq 0 \land | a | \geq | b | \end{cases}

$\mbox{add}_ℤ=λab.\left\{\begin{array}{ll} (\mbox{true},\mbox{add}_ℕ(\mbox{snd }a)(\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}_ℕ(\mbox{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.$

tetapi pengurangan itu sangat mudah untuk didefinisikan:

{minus}_{ℤ} = λ a . pair (not (fst a)) (snd a)

$\mbox{minus}_ℤ=λa.\mbox{pair}(\mbox{not}(\mbox{fst } a))(\mbox{snd } a)$

{sub}_{ℤ} = λ a b . {add}_{ℤ} (a) ({minus}_{ℤ} b)

$\mbox{sub}_ℤ=λab.\mbox{add}_ℤ(a)(\mbox{minus}_ℤb)$

$(a,b)$ $a+b\mbox{i}$

{add}_{ℤ [i]} = λ z_{1} z_{2} . pair ({add}_{ℤ} (fst z_{1}) (fst z_{2})) ({add}_{ℤ} (snd z_{1}) (snd z_{2}))

$\mbox{add}_{ℤ[\mbox{i}]}=λz_1z_2.\mbox{pair} (\mbox{add}_ℤ(\mbox{fst }z_1)(\mbox{fst }z_2)) (\mbox{add}_ℤ(\mbox{snd }z_1)(\mbox{snd }z_2))$

jmad
sumber

k

$k$

(a, b)

$(a,b)$

k = a - b

$k = a - b$

Bilangan bulat kompleks baik-baik saja, tetapi ia meminta bilangan kompleks. Kemudian lagi, mereka tentu saja tidak pernah bisa diwakili karena ada yang tak terhitung.

HdM

@AndrejBauer: trik yang sangat bagus (mungkin tidak sesederhana itu) HdM: pasti bisa, bahkan tidak semuanya. Tetapi saya berpikir bahwa metode untuk membangun barang-barang dalam kalkulus λ dengan pengkodean Gereja lebih penting / sesuai di sini.

jmad

Saya berharap saya bisa memberikan dua jawaban yang benar =) Saya bahkan tidak berpikir bahwa real dapat diwakili ketika saya bertanya tentang bilangan kompleks tetapi begitulah!

zcaudate