Eta ekspansi dalam pola kalkulus lambda

12

Klop, van Oostrom, dan de Vrijer memiliki kertas tentang kalkulus lambda dengan pola.

http://www.sciencedirect.com/science/article/pii/S0304397508000571

Dalam beberapa hal, suatu pola adalah pohon variabel - meskipun saya hanya memikirkannya sebagai kumpulan variabel, misalnya, ((x, y), z), (t, s)).

Dalam makalah mereka menunjukkan bahwa jika polanya linier, dalam arti tidak ada variabel dalam polanya yang diulang, maka aturannya

(\p . m) n = m [n/p]

di mana p adalah pola variabel dan n adalah tupel istilah dengan bentuk yang sama persis dengan p, adalah pertemuan.

Saya ingin tahu apakah ada perkembangan serupa dalam literatur untuk kalkulus lambda dengan pola dan aturan eta tambahan (ekspansi, pengurangan, atau hanya kesetaraan).

Secara khusus, dengan eta, maksud saya 

m = \lambda p . m p

Lebih langsung, saya ingin tahu properti apa yang akan dimiliki kalkulus lambda. Misalnya, apakah itu pertemuan?

Ini memaksa kategori klasifikasi untuk ditutup karena memaksa properti itu

m p = n p implies m = n

Dengan menggunakan \ xi-rule di antaranya. Tapi mungkin ada yang salah?

type-theory lambda-calculus typed-lambda-calculus extensionality Jonathan Gallagher
sumber
Bisakah Anda menulis dengan kata aturan apa yang Anda maksud? Kecuali jika ini sangat aneh, Anda harus dapat menyandikannya menggunakan jumlah dan membuat argumen simulasi.
Maks Baru
2
@ MaxNew: sepertinya dia bertanya tentang kalkulus yang belum diketik. Segala sesuatu tentang pola bekerja dengan baik dengan tipe (saya oh-begitu-sederhana menyarankan saya Fokus pada Pencocokan Pola ), tetapi kalkulus lambda cukup berbeda dari mengetik LC (terutama wrt eta) yang saya tidak berani menjawab tanpa melakukan pembuktian .
Neel Krishnaswami
@ MaxNew: Apa yang akan dikodekan oleh jumlah?
Jonathan Gallagher
@NeelKrishnaswami: Saya sebenarnya tertarik pada keduanya. Saya pikir saya gugup memiliki variabel jenis produk bersama dengan aturan eta. Saya pikir ini dilakukan, misalnya, dicosmo.org/Articles/JFP96.pdf . Tetapi jika saya salah, tolong perbaiki saya. Maka Anda memiliki persamaan seperti \ lambda x .mx = m = \ lambda (p, q). m (p, q), misalnya. Terima kasih atas tautannya ke makalah Anda!
Jonathan Gallagher

Jawaban:

7

Ini bukan jawaban yang lengkap; itu adalah komentar yang terlalu besar.

Jika Anda memperpanjang kalkulus lambda yang diketik dengan produk dengan eliminator proyektif (yaitu, eliminator produk fst(e)dan snd(e)), pada dasarnya tidak ada masalah apa pun. Alasan butuh waktu lama untuk mencari tahu adalah karena ternyata lebih alami untuk melakukan ekspansi eta daripada pengurangan eta . Lihat buku Barry Jay, The Virtues of Eta Expansion .

Jika Anda ingin produk memiliki eliminator gaya-pola 

let (a,b) = e in t

Maka masalah menjadi lebih kompleks. Kesulitan utama dalam pencocokan pola adalah konversi perjalanan . Artinya, batu ini memiliki persamaan

C[let (a,b) = e in t] === let (a,b) = e in C[t]

dan mencari tahu (a) konteks mana yang C[-]digunakan dan (b) bagaimana mengarahkan persamaan ini menjadi rumit. IMO, negara seni untuk pendekatan penulisan ulang gaya adalah Sam Lindley's Extensional Menulis ulang dengan Jumlah dan Kesetaraan Memutuskan Gabriel Scherer dengan Jumlah dan Jenis Kosong , yang keduanya mempertimbangkan kalkulus lambda yang diketik dengan produk dan jumlah.

Neel Krishnaswami
sumber