Algoritma inversi program untuk program tingkat tinggi

Istilah inversi program memiliki banyak corak makna, tetapi mungkin dimulai dengan karya J. McCarthy tahun 1956, The Inversion of Functions Defined oleh Turing Machines dalam konteks AI. Saat ini banyak koneksi antara inversi program dan bidang lain telah ditemukan, misalnya pemrograman reversibel (fisik dan logis), evaluasi parsial, verifikasi, pemrograman dua arah, pemrograman logika, dan pembelajaran mesin.

Apa itu inversi program? Dalam pendekatan pertama sesuatu itu seperti ini: Mengingat program mengambil argumen tipe A dan mengembalikan hasil tipe B , menghasilkan program P - 1 yang "entah bagaimana" kebalikan dari P . Saya sengaja tidak jelas di sini, karena konsepnya dapat (dan) diklarifikasi dengan berbagai cara: misalnya apakah P harus disuntik? Haruskah P - 1 ( b ) mengembalikan semua atau hanya beberapa yang seperti yang P ( a ) = $P : A \rightarrow B$$A$$B$$P^{-1}$$P$$P$$P^{-1}(b)$$a$$P(a) = b$?

Ada cara-cara umum untuk membalik suatu program, misalnya menggunakan diagonisasi seperti yang telah ditunjukkan oleh McCarthy, atau menggunakan evaluasi parsial, tetapi mereka cenderung tidak efisien. Juga sebagian besar bekerja pada inversi program yang saya kenal sepertinya tidak berurusan dengan bahasa pemrograman tingkat tinggi penuh (yaitu -calculi).$\lambda$

Permintaan referensi. Apa yang dimaksud dengan algoritma eksplisit dalam inversi program -calculi (tanpa batasan pada tingkat yang lebih tinggi)?$\lambda$

Belum ada banyak pekerjaan di ruang ini, tapi pekerjaan apa yang ada, cukup menarik.

1. Torben Mogensen telah mengatasi masalah ini. Ini dua makalahnya.

   Makalah pertama memberikan algoritma untuk program fungsional tingkat pertama, dan yang kedua meluas ke tingkat yang lebih tinggi. Karakterisasi yang tepat kapan algoritma ini akan berhasil diserahkan kepada pekerjaan di masa depan.

   • Semi-inversi dari Persamaan yang dijaga
   • Semi-Inversi Parameter Fungsional

2. Tetsuo Yokoyama, Holger Bock Axelsen, dan Robert Glück.

   Ini menjelaskan bahasa pemrograman RFun, yang membalikkan program fungsional orde pertama, tetapi menegakkan hambatan injektivitas dan determinisme mundur yang memastikan bahwa evaluasi mundur secepat ke depan. (Mereka telah menulis sejumlah makalah lain tentang hal ini, yang sulit saya dapatkan.)

   • Menuju Bahasa Fungsional yang Dapat Dibalik.

3. Stefan Bohne dan Baltasar Trancón Widemann.

   Ini kertas yang sangat rapi! Ia mengamati bahwa (a) Anda dapat membangun kategori di mana morfisme adalah fungsi yang dipasangkan dengan kebalikannya (untuk apa pun gagasan terbalik yang Anda gunakan), dan (b) kategori ini memiliki struktur kompak belati. Ini berarti Anda dapat menulis sebuah program dengan disiplin tipe linear yang sedikit funky, dan kemudian membacakan interpretasi maju dan mundur dari semantik.

   Mereka memberikan bahasa fungsional dengan sintaksis yang cukup liar: ekspresi hampir arbitrer dapat digunakan sebagai pola, dan reversibilitas membuatnya masuk akal.

   • Suatu Pendekatan untuk Pemrograman Fungsional Reversibel Umum

4. Francesco Tiezzia, Nobuko Yoshida

   Saya belum membaca yang ini, tetapi baru menemukannya ketika mencari di Google untuk makalah lain. Mengingat penulis dan subjeknya, saya curiga ini ada di depan Anda!

   • Pi-kalkulus berbasis sesi reversibel