Alasan program tentang kode sumber sendiri

Inspirasi untuk pertanyaan ini adalah pertanyaan (tidak jelas) berikut: Apa bahasa pemrograman / fondasi logis untuk memiliki AI yang dapat beralasan tentang kode sumbernya sendiri dan memodifikasinya?

Ini sama sekali tidak ketat, jadi di sini adalah upaya saya untuk mengeluarkan pertanyaan konkret dari itu. Ada dua hal yang saya minati:

(A) Bahasa pemrograman P yang dapat mewakili dan memanipulasi programnya sendiri sebagai Program tipe data (misalnya, sebagai AST). (Jika diinginkan, objek bertipe Program dapat dikonversi menjadi String, yang merupakan teks dari program yang valid dalam bahasa itu. Ini akan menjadi kebalikan dari apa yang dilakukan oleh kompiler.)

(B) Metode untuk alasan tentang apa yang dilakukan oleh program dalam bahasa P. Berikut adalah dua level yang saya pikirkan:

1. Bahasa lain Q (dengan kemampuan pembuktian teorema) yang memodelkan apa yang dilakukan program-P. Seharusnya bisa mengekspresikan dan membuktikan pernyataan seperti "hasil menjalankan Program p adalah foo."
2. Cara untuk berpikir tentang apa yang program p: Program lakukan dalam bahasa P itu sendiri. (Jadi kami mengambil P = Q di atas.)

Sampai sejauh mana sesuatu seperti ini telah diterapkan, atau apa kemajuan ke arah ini? Apa saja kendala praktisnya? Mengingat niat awal pertanyaan, apa cara terbaik untuk memformalkan masalah?

*

Seperti yang ditunjukkan oleh jawaban (terima kasih!), Baik (A) dan (B1) dapat dilakukan secara terpisah, meskipun tampaknya melakukannya bersama-sama lebih merupakan pertanyaan penelitian.

Inilah beberapa pemikiran pertama saya tentang pertanyaan (peringatan: agak kabur). Lihat juga komentar saya tentang jawaban Martin Berger.

Saya tertarik pada pemodelan bahasa pemrograman dengan bahasa pemrograman yang sama , daripada yang lebih sederhana (jadi P = Q di atas). Ini akan menjadi "bukti konsep" dari suatu program yang dapat "alasan tentang kode sumbernya sendiri." Bahasa pemrograman yang diketik dengan tergantung dapat memberikan jaminan tentang output dari fungsinya, tetapi ini tidak dihitung sebagai "alasan tentang kode sumbernya sendiri" tidak lebih dari "Halo dunia!" dihitung sebagai quine dalam bahasa yang secara otomatis akan mencetak string telanjang --- perlu ada semacam kutipan / referensi sendiri. Analog di sini adalah memiliki tipe data yang mewakili Program.

Sepertinya proyek yang agak besar - bahasa yang lebih sederhana, semakin sulit untuk mengekspresikan segala sesuatu di dalamnya; semakin rumit bahasa, semakin banyak pekerjaan yang harus dilakukan untuk memodelkan bahasa.

Dalam semangat Teorema Rekursi, sebuah program kemudian dapat "mendapatkan" kode sumbernya sendiri dan memodifikasinya (yaitu, mengeluarkan versi modifikasi itu sendiri). (B2) kemudian memberi tahu kami bahwa program harus dapat mengekspresikan jaminan tentang program yang dimodifikasi (ini harus dapat berulang, yaitu, ia harus dapat mengungkapkan sesuatu tentang semua modifikasi masa depan-?).

Saya pikir Anda bertanya tentang dua hal yang berbeda.

• Kemampuan bahasa pemrograman untuk mewakili semua programnya sebagai data.
• Penalaran tentang program sebagai data.

Untuk tujuan analitis, penting untuk memisahkannya. Saya akan fokus pada yang pertama.

Kemampuan suatu bahasa pemrograman untuk mewakili, memanipulasi (dan menjalankan) program-programnya ketika data berjalan di bawah istilah-istilah seperti meta-programming atau homoiconicity .

Dengan cara (canggung), semua bahasa pemrograman terkenal dapat melakukan meta-pemrograman, yaitu dengan menggunakan tipe data string bersama dengan kemampuan memanggil program eksternal (kompiler, tautan, dll.) Pada string (misalnya dengan menuliskannya ke file sistem pertama). Namun, itu mungkin bukan yang Anda maksud. Anda mungkin memiliki sintaks yang bagus dalam pikiran. String bukanlah sintaks yang bagus untuk representasi program karena hampir semua string tidak mewakili program, yaitu tipe data string berisi banyak 'sampah' ketika dilihat sebagai mekanisme representasi program. Lebih buruk lagi, aljabar operasi string pada dasarnya tidak ada hubungannya dengan aljabar konstruksi program.

Apa yang mungkin ada dalam pikiran Anda adalah sesuatu yang jauh lebih baik. Misalnya jika adalah program, maka ⟨ P $P$$\newcommand{\QUOTE}[1]{\langle #1\rangle}\QUOTE{P}$ adalah , tetapi sebagai data, di tangan untuk manipulasi dan analisis. Ini sering disebut kutipan . Dalam praktiknya, kutipan tidak fleksibel, jadi kami menggunakan kuasi-kutip , yang merupakan generalisasi kutipan di mana kutipan dapat memiliki 'lubang' di mana program dapat dijalankan yang menyediakan data untuk 'mengisi' lubang. Misalnya ⟨ i $P$ adalah kuasi-kutipan mewakili bersyarat di mana bukan kondisi kita memiliki lubang [ ⋅ ] . Jika program M mengevaluasi data ⟨ x

(Perhatikan bahwa adalah program normal (bukan program sebagai data) yang mengembalikan program yang dikutip, yaitu program sebagai data.) Agar ini berfungsi, Anda memerlukan tipe data untuk mewakili program. Biasanya tipe data itu disebut AST (pohon sintaksis abstrak), dan Anda bisa melihat (kuasi-) kutipan sebagai mekanisme singkatan untuk AST.$M$

Beberapa bahasa pemrograman menawarkan kuasi-kutip dan fitur lain untuk meta-pemrograman. Itu Lisp dengan fungsi makro yang memelopori kemampuan ini untuk memperlakukan program sebagai data. Mungkin sayangnya, kekuatan macro berbasis Lisp telah lama dilihat untuk beristirahat sebagian besar pada sintaksis minimalis Lisp; Tidak sampai MetaML (1) yang modern, bahasa yang kaya secara sintaksis terbukti mampu meta-pemrograman. Sejak saat itu, MetaOCaml (2) (keturunan MetaML, penting untuk terobosannya dalam pencarian yang masih berlangsung untuk menyelesaikan masalah bagaimana mengetik program sebagai data), Template Haskell (3) dan Converge (4) (bahasa pertama untuk mendapatkan semua fitur meta-pemrograman kunci tepat menurut saya) telah menunjukkan bahwa berbagai bahasa pemrograman modern dapat menampung meta-pemrograman. Penting untuk menyadari bahwa kita dapat mengambilsetiap bahasa pemrograman dan mengubahnya menjadi bahasa meta-pemrograman L m p yang $L$$L_{mp}$$L$ bersama-sama dengan kemampuan yang mewakili (dan mengevaluasi) program sendiri sebagai data.

Mewakili hasil dari menjalankan program, diberikan sebagai data, dicapai dengan menambahkan fungsi yang mengambil program (diberikan sebagai data) sebagai input dan menjalankannya, mengembalikan hasilnya. Misalnya jika P adalah program evaluasi untuk 17 dan ⟨ P ⟩ , yang (kuasi) versi dikutip dari P , yaitu P sebagai data, maka e v a l ( ⟨ P ⟩ $\newcommand{\EVAL}{\mathsf{eval}}\EVAL(\cdot)$$P$$\QUOTE{P}$$P$$P$$\EVAL(\QUOTE{P})$ juga kembali 17. Ada segala macam seluk-beluk di sini bahwa saya mengabaikan di sini seperti pertanyaan kapanprogram meta-program sedang dievaluasi (memunculkan perbedaan antara waktu kompilasi dan meta-program terprogram), apa yang harus dilakukan dengan tipe atau evaluasi gagal, apa yang terjadi pada variabel terikat dan bebas dalam proses perpindahan dari ke ⟨ P $P$$\QUOTE{P}$ atau sebaliknya.

Adapun dimensi kedua, alasan tentang program yang diberikan sebagai data. Segera setelah Anda dapat mengubah program menjadi data, mereka adalah data 'normal' dan dapat dianggap sebagai data. Anda dapat menggunakan segala macam teknologi prover, misalnya tipe atau kontrak yang bergantung atau prover teorema interaktif atau alat otomatis, seperti yang ditunjukkan Joshua. Namun Anda harus mewakili semantik bahasa Anda dalam proses penalaran. Jika bahasa itu, seperti yang Anda butuhkan, memiliki kemampuan meta-pemrograman, hal-hal dapat menjadi sedikit rumit dan tidak banyak pekerjaan yang telah dilakukan dalam arah ini, dengan (5) menjadi satu-satunya logika program untuk tujuan ini. Ada juga karya Curry-Howard berdasarkan alasan tentang pemrograman-meta (6, 7, 8). Perhatikan bahwa pendekatan berbasis logika ini, dan pendekatan berbasis tipe (2) memang bisa mengekspresikan properti yang berlaku untuk semua tahap meta-pemrograman di masa depan. Terlepas dari (2) tidak ada kertas yang telah dilaksanakan.

Singkatnya: apa yang Anda minta telah diterapkan, tetapi cukup halus, dan masih ada pertanyaan terbuka, khususnya yang berkaitan dengan jenis dan penalaran yang efisien.

1. W. Taha. Pemrograman Multi-Tahap: Teori dan Aplikasi-nya .

2. W. Taha dan MF Nielsen. Pengklasifikasi lingkungan .

3. T. Sheard dan S. Peyton Jones. Meta-pemrograman template untuk Haskell .

4. L. Tratt. Kompilasi meta-pemrograman dalam bahasa OO yang diketik secara dinamis .

5. M. Berger, L. Tratt, Logika Program untuk Pemrograman Meta Homogen .

6. R. Davies, F. Pfenning, Analisis modal perhitungan bertahap .

7. R. Davies, Pendekatan Temporal-Logika untuk Analisis Binding-Time .

8. T. Tsukada, A. Igarashi. Dasar logis untuk pengklasifikasi lingkungan .

Tidak, tidak ada sistem saat ini yang melakukan keempat langkah dalam sistem Anda. Jika Anda ingin merancang sistem, salah satu persyaratan pertama adalah bahasa homoikonik. Minimal Anda ingin bahasa pemrograman inti Anda yang Anda miliki sekecil mungkin sehingga ketika Anda memasuki sistem dan mulai membuatnya menafsirkan sendiri itu akan berfungsi. Jadi karena itu Anda menginginkan penerjemah metacircular yang dipelopori dalam lisp. Bahasa lain telah melakukannya juga tetapi ada sejumlah besar penelitian yang ada tentang lisp.

Langkah pertama jika Anda ingin melakukan ini adalah memiliki bahasa homoikonik seperti Lisp atau kerangka kerja di mana Anda dapat alasan tentang program yang sedang berjalan. Lisp digunakan untuk ini karena satu-satunya alasan Anda dapat mendefinisikan juru metacircular dalam bahasa tersebut atau Anda bisa memperlakukan kode Anda sebagai data. Memperlakukan kode sebagai data adalah hal yang paling penting. Ada sepanjang diskusi tentang apa arti homoikonik pada c2 wiki.

Misalnya dalam Lisp, "Program" Anda, datatype Anda adalah program lisp yang valid. Anda meneruskan program-program lisp ke seorang juru bahasa dan itu menghitung sesuatu. Itu akan ditolak oleh penerjemah jika Anda tidak memprogram "Program" yang valid.

Oleh karena itu bahasa homoikonik melakukan tiga persyaratan Anda. Anda bahkan dapat menentukan ide program formal.

Bisakah Anda membuat model lisp di dalam lisp? Ya ini sering dilakukan terutama sebagai latihan di akhir buku pemrograman lisp untuk menguji kemampuan Anda. SICP

Pada saat ini masalah empat adalah pertanyaan penelitian dan di bawah ini adalah apa yang saya temukan yang mencoba menjawab pertanyaan ini.

Saya akan mengatakan ada banyak jenis program yang berusaha melakukan ini. Di bawah ini adalah semua program yang saya ketahui.

• JSLint adalah contoh alat analisis statis yang mengambil kode mesin atau bahasa lain dan mencari bug secara eksplisit. Kemudian ia meminta programmer untuk memperbaikinya.

• Coq adalah lingkungan yang memungkinkan Anda menentukan bukti menggunakan bahasa pemrograman. Ini juga memiliki taktik di mana itu menyarankan cara bagi Anda untuk menyelesaikan masalah. Tetap saja ini mengharapkan manusia untuk melakukan pekerjaan itu. Coq menggunakan tipe dependen untuk bekerja dan karenanya sangat berteori. Ini sangat populer di kalangan ilmuwan komputer dan orang yang bekerja pada Teori Tipe Homotopy.

• ACL2 di sisi lain adalah pembalas teorema otomatis. Sistem ini akan membuktikan pernyataan berdasarkan sesuatu yang Anda program.

• ACL2 dan Coq memiliki plugin perangkat lunak yang menghubungkan sistem mereka dengan sistem pembelajaran mesin . Apa yang digunakan untuk melatih sistem ini adalah program yang ditulis sebelumnya. Dari pemahaman saya, sistem ini menambahkan fitur lain di mana Anda tidak hanya memiliki taktik, tetapi juga teorema yang menyarankan pengembangan bukti.

Di bawah ini lebih merupakan dasar dari apa arti pertanyaan Anda.

• gcc adalah contoh dari kompiler optimizng yang dapat mengambil sendiri sebagai input dan kemudian mengeluarkan versi yang dioptimalkan sendiri. Ide kompiler yang menerjemahkan program dari satu representasi ke yang lain dan meningkatkan kecepatan karena beberapa flag optimasi sangat dipahami. Setelah Anda mem-bootstrap kompiler dan menghasilkan kode mesin yang valid maka Anda dapat menambahkan optimasi dan mengkompilasi ulang kompiler dan itu membuat versi yang lebih efisien dari dirinya sendiri.

Sebagai jawaban @ user217281728 menyebutkan ada jenis mesin yang lebih terkait dengan inferensi dan AI, yang disebut Mesin Gödel

Mesin Gödel adalah program komputer mandiri yang ditemukan oleh Jürgen Schmidhuber yang memecahkan masalah secara optimal. Itu menggunakan protokol perbaikan diri rekursif di mana ia menulis ulang kode sendiri ketika dapat membuktikan kode baru memberikan strategi yang lebih optimal. Mesin ini ditemukan oleh Jürgen Schmidhuber, tetapi dinamai Kurt Gödel yang menginspirasi teori matematika.

Publikasi yang direferensikan dari Jürgen Schmidhuber pada "Mesin Goedel: Self-Referential Universal Problem Solver Membuat Peningkatan Mandiri yang Terbukti Optimal", (2006) arXiv: cs / 0309048v5

Cara mesin bekerja untuk mengimplementasikan meta-learning memiliki dua fase:

1. Belajar dari data (level 1, belajar)
2. Menggunakan data yang dipelajari untuk memodifikasi / mengoptimalkan kode sumber / algoritma (level 2, belajar untuk belajar)

Karena mesin memodifikasi sumbernya sendiri itu adalah referensi diri, yaitu memiliki properti modifikasi diri (lihat juga di sini ).

Dalam hal ini dapat memodifikasi algoritma pembelajaran itu sendiri dalam arti yang ketat (membuktikan modifikasi diri yang optimal). Ada masalah dengan referensi diri dan ketidakpastian yang dalam hal ini berbentuk:

..a Mesin Gödel dengan sumber daya komputasi yang tidak terbatas harus mengabaikan perbaikan-diri tersebut yang efektivitasnya tidak dapat dibuktikan

Bahasa lain (dan mesin juru bahasa yang terkait) yang memiliki properti modifikasi diri adalah misalnya LISP .

Dalam kode LISP dan data dapat diubah-ubah, atau kode sumber AST tersedia sebagai data, dalam program LISP dan dapat dimodifikasi sebagai data. Di sisi lain, data dapat dilihat sebagai AST, untuk beberapa kode sumber.

memperbarui

Ada mesin lain juga , seperti mesin pemrograman mandiri (antara lain) yang menggabungkan referensi diri , reproduksi diri dan pemrograman diri .

Salah satu aspek menarik di atas adalah bahwa referensi-diri sama sekali tidak bermasalah , melainkan merupakan elemen yang diperlukan dalam automata reproduksi -diri / pemrograman mandiri .

Untuk perincian lebih lanjut (dan lebih banyak publikasi) lihat JP Moulin, CR Biologies 329 (2006)

abstrak

Sistem kehidupan mampu memiliki respons yang tepat terhadap lingkungan yang tidak terduga. Jenis organisasi mandiri ini tampaknya beroperasi sebagai mesin pemrograman mandiri, yaitu oprganisasi yang dapat memodifikasi dirinya sendiri. Sampai sekarang model pengorganisasian mandiri makhluk hidup yang diusulkan adalah solusi fungsi dari sistem diferensial atau fungsi transisi automata. Fungsi-fungsi ini diperbaiki dan model-model ini karenanya tidak dapat memodifikasi organisasi mereka. Di sisi lain, ilmu komputer mengusulkan banyak model yang memiliki sifat sistem adaptif makhluk hidup, tetapi semua model ini bergantung pada perbandingan antara tujuan dan hasil serta pilihan parameter yang cerdas oleh pemrogram, sedangkan tidak ada niat programmer. atau pilihan dalam sistem kehidupan.$\mathbb{m}_\mathbb{sp}$$\mathbb{M}_\mathbb{sp}$

Makalah ini oleh Jurgen Schmidthuber mungkin menarik:

http://arxiv.org/pdf/cs/0309048.pdf