Untuk bahasa apa sudah ada teori kesetaraan pengamatan?

11

Untuk bukti kebenaran, saya mencari gagasan yang dapat digunakan tentang kesetaraan program untuk sistem tipe murni (PTS) Barendregt; hilang itu, untuk sistem jenis yang cukup spesifik. Tujuan saya hanyalah menggunakan gagasan itu, bukan untuk menyelidiki demi kepentingannya sendiri.≅

Gagasan ini harus " ekstensional " - khususnya, untuk membuktikan bahwa , harus cukup untuk membuktikan bahwa untuk semua nilai dari jenis yang sesuai.t 1t1≅t2vt1v≅t2vv

Kesetaraan denotasi

Kesetaraan denotasional dengan mudah memenuhi semua lemmas yang tepat, tetapi semantik denotasional untuk PTS yang sewenang-wenang tampaknya agak menantang - itu sudah terasa sulit untuk Sistem F.

Kesetaraan kontekstual / observasi

Alternatif yang jelas kemudian berbagai bentuk kesetaraan kontekstual (dua istilah adalah setara jika tidak ada konteks dasar yang dapat membedakannya), tetapi definisi tersebut tidak segera dapat digunakan; berbagai lemma tidak sepele untuk dibuktikan. Apakah sudah terbukti untuk PTS? Atau, akankah teori itu menjadi "perpanjangan yang jelas", atau adakah alasan untuk percaya bahwa teori itu akan sangat berbeda?

EDIT: Saya tidak mengatakan apa yang sulit di atas.

Bagian yang mudah: definisi

Mendefinisikan kesetaraan tidak terlalu sulit, dan definisi muncul di banyak makalah (dimulai setidaknya dari studi Plotkin 1975 tentang PCF, jika tidak sebelumnya - sumbernya mungkin tesis PhD Morris dari 1968). Kami jika untuk semua konteks dasar , - yaitu, dan memberikan hasil yang sama . Anda memiliki beberapa pilihan di sini dengan banyak alternatif: Misalnya, dalam bahasa yang sangat normal, jika Anda memiliki jenis dasar naturals, Anda dapat mengatakan bahwa konteks dasar adalah yang mengembalikan naturals, dan kemudian berarti bahwa dan C C [ t 1 ] ≃ C [ t 2 ] C [ t 1 ] C [ t 2 ] a ≃ b a bt1≅t2CC[t1]≃C[t2]C[t1]C[t2]a≃babmengevaluasi ke nomor yang sama. Dengan nontermination, untuk bahasa yang masuk akal cukup menggunakan "X terminates" sebagai observasi, karena jika dua program setara ketika mengamati terminasi, mereka juga sama ketika mengamati hasilnya.

Bagian yang sulit: buktinya

Namun, makalah-makalah itu seringkali tidak menjelaskan betapa sulitnya untuk benar-benar menggunakan definisi ini. Semua referensi di bawah ini menunjukkan bagaimana menangani masalah ini itu, tetapi teori yang dibutuhkan lebih sulit daripada yang dipikirkan orang. Bagaimana kami membuktikannya ? Apakah kita benar-benar melakukan analisis kasus dan induksi pada konteks? Anda tidak ingin melakukan itu.t1≅t2

Seperti yang ditunjukkan Martin Berger, Anda ingin menggunakan bisimulasi (seperti yang dilakukan oleh Pitts) atau hubungan kesetaraan logis (yang oleh Harper disebut "kesetaraan logis").

Akhirnya, bagaimana Anda membuktikan ekstensionalitas sebagaimana didefinisikan di atas?

Harper memecahkan pertanyaan-pertanyaan ini dalam 10 halaman untuk System T, melalui kepintaran dan hubungan logis yang cukup besar. Pitts mengambil lebih banyak. Beberapa bahasa masih lebih kompleks.

Bagaimana menghadapi ini

Saya sebenarnya tergoda untuk membuat pembuktian saya secara kondisional pada teori dugaan ekuivalensi untuk PTS, tetapi teori-teori yang sebenarnya memerlukan argumen nontrivial, jadi saya tidak yakin seberapa besar dugaan dugaan seperti itu akan bertahan.

Saya mengetahui (meskipun tidak secara mendetail) dari karya-karya berikut:

  • Andrew Pitts (misalnya dalam ATTAPL untuk Sistem F yang diperluas, dan dalam beberapa makalah, seperti 58 halaman "Teori Berbasis Kesamaan Kesetaraan Program").
  • Yayasan Praktis Bahasa Pemrograman (bab 47-48), yang terinspirasi oleh Pitts (tetapi mengklaim memiliki bukti yang lebih sederhana).
  • Sebuah studi logis tentang kesetaraan program . Saya tidak dapat menemukan abstrak bahasa Inggris, tetapi tampaknya menghabiskan banyak upaya untuk efek samping (referensi), yang tampaknya merupakan komplikasi ortogonal.
pl.programming-languages type-theory operational-semantics Blaisorblade
sumber
1
Untuk tipe-teori mendefinisikan kongruensi kontekstual operasional harus mudah, karena semua program berakhir. Tetapkan gagasan pengamatan pada tipe dasar (mis. Penghentian, tertulis , pada tipe Unit), dan kemudian ucapkan P ≅ Q untuk semua konteks yang diketik dan ditutup dengan baik C [ ⋅ ] dari tipe dasar, kita memiliki C [ P ] ⇓ iff C [ Q ] ⇓ . Dengan PTS, ini sedikit lebih rumit, karena mungkin mendapatkan non-terminasi. ⇓P≅QC[⋅]C[P]⇓C[Q]⇓
Martin Berger
@ MartinBerger: itulah ide yang saya sarankan, tetapi membuktikannya secara langsung ternyata sangat sulit, karena Anda perlu melakukan pembuktian untuk semua C (saya akan menjelaskannya dengan lebih baik dalam pertanyaan). Juga, jika semua program berakhir, definisi yang Anda gunakan, seperti yang diberikan, mengidentifikasi semua program.
Blaisorblade
Apakah PTS Anda hanya memiliki fungsi sebagai tipe komputasi? Jika kemudian, maka pertanyaan yang sangat bagus ini (dan jawaban) tampaknya menunjukkan bahwa -equivalence cukup untuk mengakhiri sistem jenis murni - dan itu baik menjelaskan bagaimana untuk menentukan kesetaraan kontekstual untuk mengakhiri bate. Saya pikir menggunakan nilai-nilai dasar adalah cara yang tepat untuk mendefinisikan kesetaraan kontekstual, dan penghentian hanyalah jalan pintas yang mudah bagi prestasi meragukan. βη
gasche
1
@ Blaisorblade Maaf ya, jika Anda menggunakan pemutusan hubungan kerja sebagai diamati, maka Anda benar. Maaf, saya memotong dan menempelkan definisi untuk turing bahasa deterministik lengkap. Jika Anda memiliki fungsi terminating Anda dapat menggunakan dasar yang bisa diamati. Misalnya di boolean: ... iff C [ Q ] ⇓ t r u e . Kuantifikasi atas semua konteks selalu menjadi masalah. Cara standar untuk menghadapinya adalah dengan mendefinisikan relasi kedua yang (1) adalah suara yang bagus ≅C[P]⇓trkamueC[Q]⇓trkamue≅dan (2) mudah ditangani, misalnya gagasan bisimilaritas, atau hubungan logis. Tergantung pada aplikasi.
Martin Berger
1
@ Blaisorblade Mungkin. Para ahli teori konkurensi telah melakukan ini secara intensif sejak lama, karena dengan proses-proses konkuren, tidak begitu jelas gagasan tentang kesetaraan yang digunakan. Ini mengarah pada pembagian kerja: gunakan semantik berbasis reduksi dengan kuantifikasi atas konteks untuk mendefinisikan gagasan kesetaraan dan kemudian gunakan bisimulasi atau jejak pada transisi berlabel untuk membuktikan kesetaraan (atau ketiadaan). Pertanyaan penelitian terbuka besar dalam teori konkurensi adalah bagaimana beralih dari yang pertama ke yang terakhir secara algoritmik.
Martin Berger

Jawaban:

4

Semantik denotasi komposisi dari bahasa pemrograman (teori domain atau teori permainan), misalnya)memadaijika istilah yang secara semantik sama menyiratkan bahwa mereka setara secara observasi: [[[-]]

[[t1]]=[[t2]]⟹t1≅t2.
Andrej Bauer
sumber
≅
Terima kasih atas jawabannya, tetapi -1: Sementara saya setuju, pertanyaannya menyebutkan sistem tipe murni - AFAICS, semantik denotasional untuk sistem tipe murni adalah masalah terbuka, jadi saya pikir jawaban harus mengarah ke beberapa semantik denotasional. (Bahkan, jika saya memiliki semantik denotasional, saya akan membuang yang operasional sama sekali, seperti yang disebutkan dalam pertanyaan). (Tapi maaf untuk pertanyaan yang terlalu panjang.)
Blaisorblade
@ MartinBerger, saya tidak mengerti kritik Anda. OP meminta metode untuk menunjukkan kesetaraan pengamatan, saya menyebutkan yang umum, dan kemudian Anda keberatan bahwa ada cara lain yang menghindari metode ini?
Andrej Bauer
2
@ Blororblade, maka Anda hanya perlu menciptakan semantik denotasi untuk sistem tipe murni, bukan? :-) Tetapi lebih serius, saya akan bertanya kepada Alex Simpson, dia akan tahu lebih baik tentang semantik denotasional untuk hal-hal seperti itu.
Andrej Bauer
@AndrejBauer Itu tidak dimaksudkan sebagai kritik, lebih sebagai tambahan.
Martin Berger
2

η

cody
sumber
1
Saya tidak berpikir PhD Streicher adalah tentang PTS. Ini tentang semantik Kalkulus Konstruksi dan hasil independensi melalui semantik reliabilitas. Lihat di sini .
Martin Berger
Terimakasih atas klarifikasinya! Saya khawatir tautannya rusak (dan sulit diperbaiki dengan tautan yang diperkecil).
cody
Tautannya adalah ke daftar isi buku di sini . Saya harap ini bekerja lebih baik.
Martin Berger
λ∗
@ MartinBerger: maksud Anda semantik realisasi?
Dominique Devriese
0

Jawaban ini menyarankan pendekatan untuk masalah tersebut. (Umpan balik diterima).

PFPL bab 49 membahas, sekaligus, gagasan ekuivalen kesetaraan pengamatan dan kesetaraan logis. Kesetaraan logis adalah hubungan yang sama digunakan untuk menyatakan parametrik, sehingga inti bab ini adalah bukti parametrik untuk Sistem F.

Bekerja pada parametrik untuk PTS, AFAICT, tidak membahas hubungan dengan kesetaraan pengamatan. Bahkan, untuk bahkan mendefinisikan kesetaraan pengamatan, kecuali Anda memiliki nonterminasi, Anda memerlukan beberapa jenis tanah positif (alami, boolean) untuk digunakan untuk pengamatan.

Namun, teorema kunci (PFPL 47.6, 48.3, 49.2) untuk menghubungkan dua relasi terbukti secara independen dari bahasa tertentu:

Kesetaraan pengamatan adalah kongruensi konsisten kasar pada ekspresi.

Kemudian, untuk menunjukkan bahwa kesetaraan logis menyiratkan kesetaraan pengamatan, orang hanya perlu menunjukkan bahwa kesetaraan logis adalah kongruensi yang konsisten. Namun, arah lain memerlukan beberapa pekerjaan lebih: khususnya, untuk menunjukkan bahwa kesetaraan logis adalah kongruensi, seseorang melanjutkan dengan induksi pada konteks.

n + 1 = 1 + nVecN nnVecNVecNn+1=1+nVec (n + 1)Vec (1 + n)n + 11 + n

Blaisorblade
sumber