-kalkulus dengan refleksi

23

Saya mencari kalkulus sederhana yang mendukung pemikiran tentang refleksi , yaitu introspeksi dan manipulasi program yang sedang berjalan.

Apakah ada ekstensi -calculus yang tidak diketik yang memungkinkan seseorang untuk mengkonversi -terms ke dalam bentuk yang dapat dimanipulasi secara sintaksis dan kemudian dievaluasi? $\lambda$ $\lambda$

Saya membayangkan bahwa kalkulus memiliki dua istilah tambahan utama:

$\mathtt{reflect}\ v$ : mengambil dan menghasilkan representasi dari bisa dikembangkan untuk manipulasi sintaksis. $v$ $v$
$\mathtt{eval}\ v$ : mengambil representasi sintaksis dari suatu istilah dan mengevaluasinya.

Untuk mendukung refleksi, diperlukan representasi sintaksis dari istilah-istilah. Itu akan terlihat seperti:

$\lambda x.e$ akan direpresentasikan sebagai sebuah istilah , di mana adalah versi yang direfleksikan dari , $(\mathsf{LAM}\ R(e))$ $R(e)$ $e$
$e\ e'$ akan direpresentasikan sebagai term , dan $(\mathsf{APP}\ R(e)\ R(e'))$
$x$ akan direpresentasikan sebagai . $(\mathsf{VAR}\ x)$

Dengan representasi ini, pencocokan pola dapat digunakan untuk memanipulasi istilah.

Tapi kami mengalami masalah. dan perlu dikodekan sebagai istilah, seperti halnya pencocokan pola. Berurusan dengan ini tampaknya mudah, menambahkan , dan , tetapi apakah saya perlu menambahkan istilah lain untuk mendukung manipulasi ini? $\mathtt{reflect}$ $\mathtt{eval}$ $\mathsf{REFLECT}$ $\mathsf{EVAL}$ $\mathsf{MATCH}$

Ada pilihan desain yang perlu dibuat. Apa yang harus dilakukan fungsi disinggung di atas dengan tubuh dan ? Haruskah mengubah tubuh atau tidak? $R(-)$ $\mathtt{reflect}$ $\mathtt{eval}$ $R(-)$

Karena saya tidak begitu tertarik untuk mempelajari refleksi itu sendiri - kalkulus akan berfungsi sebagai wahana untuk penelitian lain - saya tidak ingin menemukan kembali roda.

Adakah kalkuli yang ada yang cocok dengan yang baru saja saya jelaskan?

Sejauh yang saya tahu, kalkulus seperti MetaML, disarankan dalam komentar, berjalan jauh, tetapi mereka tidak termasuk kemampuan untuk pola pertandingan dan mendekonstruksi fragmen kode yang telah dibangun.

Satu hal yang ingin saya lakukan adalah sebagai berikut:

$\mathtt{let}\ x=\lambda y.y\ \mathtt{in}\ \mathtt{reflect}\ x \to (\mathsf{LAM}\ (\mathsf{VAR}\ y)\ (\mathsf{VAR}\ y))$

Dan kemudian lakukan pencocokan pola pada hasil untuk membangun ekspresi yang sama sekali berbeda.

Ini tentu saja bukan perpanjangan konservatif ke -kalkulus dan meta-teori cenderung jelek, tetapi ini adalah semacam titik untuk aplikasi saya. Saya ingin memecah -straksi terpisah. $\lambda$ $\lambda$

logic lambda-calculus semantics reflection Dave Clarke
sumber

MetaML adalah bahasa reflektif yang diketik dengan operator tanda kurung melakukan REFLECT Anda dan melepas tanda EVAL. Pengetikan dasar, tetapi Anda dapat melihat fragmen yang diwarisi dari modal S4 dalam pekerjaan seperti makalah ini yang dapat membantu Anda.

ex0du5

@ ex0du5: Terima kasih, tapi ini tidak cukup jauh, sejauh yang saya tahu. Tentu, saya dapat membuat kode dalam berbagai fase, tetapi sepertinya saya tidak dapat memisahkan istilah. (Saya akan membaca lebih dekat, untuk melihat apakah saya melewatkan sesuatu.)

Dave Clarke

Skema (tanpa sifat berubah-ubah dan komplikasi lainnya)?

Gilles 'SO- berhenti menjadi jahat'

@Gilles: Skema adalah bahasa pemrograman, bukan kalkulus. Selain itu, saya tidak berpikir itu bisa melakukan apa yang saya inginkan.

Dave Clarke

@DaveClarke Bahasa pemrograman adalah kalkulus dengan banyak kutil. Inti Skema tampaknya cocok pada pandangan pertama, tetapi saya belum memberikan persyaratan yang cukup untuk meyakinkan Anda. Menurut Anda apa yang tidak akan berhasil? (Mampir untuk mengobrol jika Anda mau.)

Gilles 'SO- stop being evil'

15

Jean Louis Krivine memperkenalkan kalkulus abstrak yang memperluas "Mesin Krivine" dengan cara yang sangat tidak sepele (perhatikan bahwa mesin Krivine sudah mendukung instruksi panggilan / cc dari lisp):

Dia memperkenalkan "quote" operator dalam artikel ini didefinisikan dengan cara berikut: jika adalah -istilah, catatan citra oleh beberapa bijection dari segi lambda untuk bilangan. Catatan angka gereja yang sesuai dengan . Krivine mendefinisikan operator berdasarkan aturan evaluasi: $\phi$ $\lambda$ $n_\phi$ $\phi$ $\pi: \Lambda \rightarrow \mathbb{N}$ $\overline{n}$ $n\in\mathbb{N}$ $\chi$

χ ϕ \to ϕ \bar{n_{ϕ}}

$\chi\ \phi \rightarrow \phi\ \overline{n_\phi}$ Saya percaya sihir Kleene akan menunjukkan bahwa ini cukup untuk melakukan apa yang Anda inginkan: yaitu mendefinisikan kutipan dan operator eval, jika

dapat dihitung.

π

$\pi$

Perhatikan bahwa Krivine terkenal sulit dibaca (tolong jangan marah jika Anda membaca ini, Jean-Louis!), Dan beberapa peneliti telah melakukan tindakan amal dengan mencoba mengekstraksi konten teknis dengan cara yang lebih mudah dibaca. Anda dapat mencoba melihat catatan ini oleh Christophe Raffali.

Semoga ini membantu!

Terjadi pada saya bahwa ada referensi lain yang mungkin relevan dengan minat Anda: Kalkulus Pola Murni oleh Jay dan Kesner memformalkan varian dari -kalkulus yang memperluas abstraksi sederhana atas variabel ke abstraksi atas suatu pola yang mewakili kalkulus pola diri. Ini sangat ekspresif dan khususnya memungkinkan seseorang untuk mendekonstruksi aplikasi itu sendiri: jika saya tidak salah, istilahnya: $\lambda$

(λ (x y) . x) ((λ x . x x) (λ y . y))

$(\lambda (x\ y). x)((\lambda x.x\ x)\ (\lambda y.y))$

berkurang menjadi . Sekali lagi, saya percaya bahwa ini lebih dari cukup untuk mengimplementasikan operator kutipan dan evaluasi . $\lambda x.x\ x$

cody
sumber

Saya ingin menghapuskan jawaban yang tampaknya masuk akal ini, tetapi saya tidak tahu apakah jawaban itu mulai menjawab pertanyaan.

Raphael

@Raphael membaca artikel dan mencari tahu :) Sebenarnya, ini hanya sebagian jawaban: artikel memang memformalkan fitur penting dariisp yang tidak ditemukan dalam kalkulus lambda: yaitu operator QUOTE. Namun, tidak ada studi meta-teoretis yang luas, mereka hanya memperkenalkannya sebagai sarana untuk mengekspresikan semacam perhitungan non-transparan yang aneh untuk mewujudkan aksioma rumit dari teori himpunan.

cody

1

Jika saya ingat dengan benar, di PPC, Anda tidak dapat mencocokkan pola pada redex, alasan yang mereka berikan adalah demi pertemuan. Juga, dalam PPC, pencocokan pola ketat pada pencocokan, sehingga

akan segera dinormalisasi menjadi

, maka upaya untuk mencocokkan terhadap pola

akan gagal.

(λ x . x x) (λ y . y)

$(\lambda x . x\ x)\ (\lambda y . y)$

λ y . y

$\lambda y . y$

(x y)

$(x\ y)$

hari

1

Satu-satunya kutipan yang saya tahu adalah yang Lisp. Tapi, seingat saya, itu hanya mengubah apa pun yang dikutip menjadi objek sintaksis. "Fungsi"

mengambil argumen unevaluated .. The

fungsi seharusnya mengambil nilai dari argumen (mengevaluasinya), dan mengubahnya kembali menjadi beberapa ekspresi sintaksis yang mengevaluasi (bagaimana ?) ke nilai itu. Jadi jika Krivine penawaran formalisme dengan LISP

, kita mendapatkan tempat di dekat apa yang disarankan dalam pertanyaan.

q u o t e

$\mathtt{quote}$

r e f l e c t

$\mathtt{reflect}$

q u o t e

$\mathtt{quote}$

babou

8

Melakukan hal itu sangat sulit, jika tidak mustahil, tanpa menyerah pada pertemuan. Artinya, saya curiga Anda benar tentang meta-teori berbulu. Di sisi lain, dimungkinkan untuk merancang kalkulus combinator yang dapat mengekspresikan semua fungsi yang dapat dihitung, dan yang memiliki kemampuan penuh untuk memeriksa persyaratannya: lihat Jay dan Give-Wilson .

Saya percaya bahwa memiliki kemampuan ini melakukan beberapa hal buruk pada teori persamaan Anda. Khususnya Anda akan cenderung hanya dapat membuktikan dua nilai yang sama jika nilai yang sama hingga kesetaraan alfa.

Saya belum membaca makalah Krivine yang ditautkan, tetapi saya harus mencatat bahwa dalam logika Klasik Anda pada dasarnya hanya memiliki dua hal: benar, dan salah. Semuanya setara dengan salah satunya. Artinya, Anda cenderung memiliki teori persamaan runtuh.

Philip JF
sumber

1

Perhatikan bahwa kalkulus Krivine bukanlah kalkulus proposisi tetapi lebih pada realizer untuk ini, yang memiliki teori persamaan yang sangat non-sepele.

cody

5

Dalam teori bahasa pemrograman fitur yang Anda bicarakan biasanya disebut sebagai "kutipan". Misalnya, John Longley menulis tentang itu di beberapa karyanya, lihat makalah ini .

Jika Anda hanya setelah pertimbangan teoritis (sebagai lawan dari implementasi yang benar-benar bermanfaat) maka Anda dapat menyederhanakan hal-hal dengan menyatakan bahwa quote(atau reflectseperti yang Anda sebut) memetakan ke dalam tipe bilangan bulat natdengan mengembalikan kode Gödel dari argumennya. Anda kemudian dapat menguraikan angka seperti yang Anda lakukan pohon sintaksis abstrak. Selanjutnya, Anda tidak perlu evalkarena itu dapat diimplementasikan dalam bahasa - itu pada dasarnya adalah juru bahasa.

$n \star m$ $\varphi_n(m)$ $\varphi_n$ $n$ $\lambda$ quote

Jika Anda memberi tahu saya apa yang Anda cari, saya mungkin bisa memberi Anda referensi yang lebih spesifik.

Omong-omong, ini adalah masalah terbuka:

$\lambda$ quote $\xi$

$\xi$

\frac{e_{1} \equiv e_{2}}{λ x . e_{1} \equiv λ x . e_{2}}

$\frac{e_1 \equiv e_2}{\lambda x \,.\, e_1 \equiv \lambda x \,.\, e_2}$

λ

$\lambda$

λ

$\lambda$ quotequote

\frac{e_{1} \equiv e_{2}}{q u o t e e_{1} \equiv q u o t e e_{2}},

$\frac{e_1 \equiv e_2}{\mathtt{quote}\,e_1 \equiv \mathtt{quote}\,e_2},$

q u o t e ((λ x . x) y) \equiv q u o t e y .

$\mathtt{quote}\,((\lambda x \,.\,x) y) \equiv \mathtt{quote}\, y.$ quote

λ

$\lambda$

Andrej Bauer
sumber

β

$\beta$ quote

λ

$\lambda$

ξ

$\xi$

ξ

$\xi$

β

$\beta$

Makalah berikut menunjukkan beberapa masalah dengan persamaan (ξ): Kalkulus Lambda adalah Aljabar, Peter Selinger. Menarik, sesuatu yang baru saya tidak sadari! Keren.

Nomor Transfinit

4

Inilah jawaban alternatif, alih-alih menggunakan pendekatan nominal saya yang masih eksperimental ada beberapa pendekatan yang lebih mapan yang kembali ke koran:

LEAP: Bahasa dengan eval dan polimorfisme
Frank Pfenning dan Peter Lee
https://www.cs.cmu.edu/~fp/papers/tapsoft89.pdf

Makalah ini dimulai dengan:

Ini kemudian membawa kami pada pertanyaan, yang pertama kali diajukan oleh Reynolds, tentang apakah bahasa yang diketik dengan kuat menerima penafsir metacircular. Kebijaksanaan konvensional tampaknya menunjukkan bahwa jawabannya adalah "Tidak". Jawaban kami adalah "Hampir".

Harap dicatat bahwa LEAP jauh lebih kuat dari yang diinginkan OP. Pertama-tama itu diketik. Dan kedua meminta metacircularity, yang berarti misalnya eval dapat menjalankan definisi sendiri. Di Prolog Anda mendapatkan metacircularity untuk mengatasi / 1:

solve(true).
solve((A,B)) :- solve(A), solve(B).
solve(H) :- clause(H,B), solve(B).

Jika Anda menambahkan klausa berikut untuk menyelesaikan / 1:

solve(clause(H,B)) :- clause(H,B).

Dan jika Anda memastikannya bahwa klausa / 2 juga mengembalikan klausa penyelesaian / 1. Anda kemudian dapat memanggil resol (memecahkan (...)) dan melihat bagaimana memecahkan mengeksekusi sendiri.

Pertanyaan tentang keterwakilan diri masih memacu beberapa penelitian, lihat misalnya:

Representasi diri dalam Sistem
Girards U Matt Brown, Jens Palsberg
http://compilers.cs.ucla.edu/popl15/popl15-full.pdf

Bilangan Transfinit
sumber

3

Masalahnya diidentifikasi dalam berbagai asisten bukti seperti Coq dan Isabelle / HOL. Ini berjalan di bawah singkatan HOAS . Ada beberapa klaim di sekitar λ-Prolog bahwa melalui ∇ kuantifier baru hal-hal seperti itu dapat dilakukan. Tapi saya belum bisa memahami klaim ini. Saya kira wawasan utama yang saya dapatkan sejauh ini adalah bahwa tidak ada pendekatan yang pasti, ada beberapa pendekatan yang mungkin.

Pandangan saya sendiri, belum selesai , terinspirasi oleh sebuah makalah baru-baru ini oleh Paulson tentang pembuktian ketidaklengkapan Gödels. Saya akan menggunakan pengikat tingkat objek sehubungan dengan beberapa struktur data yang memiliki nama meta-level. Pada dasarnya struktur data yang serupa namun berbeda dengan yang ada di OP, dan dengan pengkodean Gereja karena saya tertarik pada tipe dependen:

datatype Expr = var Name                 /* written as n */
              | app Expr Expr            /* written as s t */
              | abs Name Expr Expr       /* written as λn:s.t */

Ekspresi level meta dapat dibedakan dari ekspresi level objek karena kita menggunakan nama variabel n, m, .. dll. Untuk menunjukkan nama. Sedangkan kita menggunakan nama variabel x, y, .. dll. Pada tingkat objek. Penafsiran istilah meta dalam logika objek kemudian bekerja sebagai berikut. Mari kita menulis [t] σ untuk interpretasi istilah nominal t dalam konteks nominal σ, yang harus memberikan istilah objek. Kami kemudian akan memiliki:

 [n]σ = lookup σ n
 [s t]σ = [s]σ [t]σ
 [λn:s.t]σ = λx:[s]σ.[t]σ,n:x

Di atas akan menentukan apa OP sebut fungsi EVAL. Perbedaan kecil dengan Paulson, σ hanya daftar terbatas dan bukan fungsional. Menurut pendapat saya hanya mungkin untuk memperkenalkan fungsi EVAL dan bukan fungsi REFLECT. Karena pada level objek Anda mungkin memiliki beberapa persamaan sehingga ekspresi lambda yang berbeda adalah sama. Yang harus Anda lakukan adalah menggunakan eval sebagai alasan, mungkin juga tentang refleksi jika Anda merasa perlu.

Anda harus pergi ke ekstrem seperti Prolog di mana tidak ada yang diperluas, jika Anda ingin meruntuhkan tembok antara nominal dan non-nominal. Tapi seperti contoh sistem λ-Prolog menunjukkan, dalam kasus tingkat tinggi ada memikat masalah tambahan yang misalnya hanya dapat diatasi dengan cara yang logis dengan memperkenalkan cara baru seperti ∇ kuantifier!

Bilangan Transfinit
sumber

-kalkulus dengan refleksi

Jawaban: