Adakah yang Membuat Sistem yang Menulis Program Komputer dari spesifikasi?

17

Adakah yang pernah benar-benar menulis sebuah sistem (perangkat lunak atau penjelasan terperinci di atas kertas dengan contoh sederhana) yang menghasilkan program komputer? Saya memasukkan dan ia menciptakan sebuah program yang mencantumkan bilangan prima kurang dari 10. secara sederhana didefinisikan sebagai Profesor mengatakan mereka bisa tetapi tidak ada yang memberikan contoh lengkap aktual.P r i m e ( x ) 1 < x ∧ ∄ APrsayame(x)∧x<10Prsayame(x)

1<x∧∄SEBUAHs.t.1<SEBUAH∧SEBUAH<x∧x=SEBUAH×B, dengan SEBUAH,B∈N
logic type-theory coq proof-assistants cody
sumber
13
Maksud Anda seperti, Anda tahu, kompiler untuk bahasa pemrograman tujuan umum?
Sasho Nikolov
1
Hai - selamat datang di cstheory! Sayangnya pertanyaan Anda bukan pertanyaan tingkat penelitian dalam ilmu komputer teoretis dan di luar topik di situs ini.
Sebenarnya, ini adalah pertanyaan yang bagus, di bagian atas penelitian saat ini, dan sangat menjanjikan. Namun, seringkali sangat sulit untuk menentukan dengan tepat apa yang Anda inginkan. Jika Anda berhasil menentukannya, maka Anda memerlukan sistem yang akan membuktikan bahwa itu masuk akal, bahwa itu layak, dan itu akan membutuhkan bukti matematika. Dari bukti itu sebuah program yang melakukannya dapat diekstraksi. Tetapi penelitian untuk mengotomatisasi bukti dan ekstraksi program masih dalam tahap awal, meskipun membuat kemajuan yang bagus. Anda dapat melihat misalnya di Coq di wikipedia.- - - cc @LevReyzin
babou
2
Ini buku yang sesuai dengan pertanyaan Anda. Ada yang lain. Hal ini tidak mudah dimengerti. Kerumunan Coq dan Isabelle (sistem serupa lainnya) memang termasuk pengguna SE yang dapat memberi Anda lebih banyak informasi dan contoh jika pertanyaan tidak ditutup. Saya menemukannya dengan mencari di web untuk: coq contoh program sintesis.
babou
2
Bidang ilmu komputer yang menangkap apa yang Anda tanyakan disebut sintesis program dan merupakan bidang penelitian aktif.
Huck Bennett

Jawaban:

11

Ini adalah topik penelitian yang sangat aktif, sangat menjanjikan, meskipun otomatisasi penuh pembuatan program mungkin memiliki keterbatasan intrinsik (tetapi apakah manusia lebih baik?). Tetapi idenya masih sangat berguna dalam membantu pembuatan program dengan memekanisasi banyak langkah, dan dengan secara otomatis memeriksa kebenaran pembuatan program.

Ini sangat terkait dengan hasil dalam logika, yang disebut korespondensi Curry-Howard (atau isomorfisme), yang menunjukkan bahwa program komputer dan bukti matematika sangat mirip.

Jadi idenya adalah bahwa sistem akan mengambil spesifikasi program Anda sebagai teorema yang harus dibuktikan. Dalam contoh Anda, ini akan menjadi seperti (secara informal): "ada satu set semua bilangan prima yang lebih kecil dari 10".

Kemudian, Anda akan berusaha membuktikan teorema itu, dan sistem yang ada akan membantu Anda dalam melakukan pembuktian, mengotomatisasi beberapa bagian, mungkin seluruh pembuktian, dan memastikan Anda tidak pernah membuat kesalahan.

Dari bukti itu orang kemudian dapat mengekstrak program yang benar-benar menghitung daftar bilangan prima yang diinginkan yang telah ditentukan sebelumnya.

Beberapa sistem dikembangkan di masa lalu untuk menjelaskan ide-ide ini. Salah satu yang lebih dikenal adalah LCF oleh Robin Milner , yang menciptakan bahasa ML untuk tujuan itu. Salah satu sistem yang paling canggih saat ini adalah Coq .

Ada beberapa contoh yang sepenuhnya berhasil, beberapa di antaranya cukup rumit. Anda mungkin menemukan beberapa di artikel berikut ini , meskipun tidak mudah dibaca dan membutuhkan pengetahuan Logika yang canggih.

babou
sumber
9

Jawaban mengibas: Ya, tetapi pada saat penulisan, untuk sebagian besar program nontrivial spesifikasi tampaknya sama sulitnya untuk menulis dan debug seperti program akan.

Lebih serius, jawaban babou bagus, tapi aku juga akan menyarankan memeriksa area tipe dependen. Ada buku yang agak bagus menggunakan Coq (penafian penuh: ditulis oleh teman saya), tetapi ada juga Epigram, Agda, dan Idris. Isabelle / HOL juga layak untuk dicoba.

Ini semua didasarkan pada kalkulus konstruksi. Jika Anda ingin mengetahui dasar teoretis, lihat teori tipe Martin-Löf. Ada beberapa perkenalan yang bagus di sekitar.

Nama samaran
sumber
Saya sepenuhnya setuju dengan spesifikasi (dan juga sisa jawaban Anda, tetapi Anda tahu lebih baik daripada saya). Setiap programmer sejati tahu betapa sulitnya untuk menentukan sepenuhnya apa yang harus dilakukan suatu program. Ini adalah masalah utama dalam rekayasa perangkat lunak. Dan itu diterjemahkan juga di sini, meskipun masalah yang ditangani lebih bersifat matematis secara umum. Namun, saya tidak ingin terdengar terlalu mengecilkan hati (terutama mengingat sejarah pertanyaan ini, diilustrasikan oleh komentar pertama).
babou
4

Melangkah menyinggung di sini, generator program (yaitu, sistem yang memberikan deskripsi tingkat tinggi dari sesuatu dalam beberapa bahasa khusus) telah ada selamanya. Kompiler apa pun adalah salah satunya, seperti halnya salah satu dari banyak generator parser. Kembali pada hari sistem yang disebut "bahasa generasi ketiga," yang menghasilkan (sebagian besar) kode aplikasi bisnis yang khas memberikan deskripsi tingkat tinggi dan katalog data yang tersedia populer.

vonbrand
sumber
1

Pemrograman Logika dan, secara lebih umum, Pemrograman Deklaratif mengambil sebagai premis apa yang Anda usulkan: yaitu, dari spesifikasi logis, mengembalikan hasil yang memenuhi spesifikasi tersebut.

Salah satu area yang tampaknya secara khusus menangani contoh "primes kurang dari 10" yang Anda berikan adalah Constraint Programing yang mencoba mencari solusi untuk masalah yang melibatkan kendala tertentu, termasuk batasan integer seperti yang Anda berikan.

Anda mungkin ingin mencoba ECLiPSe untuk implementasi spesifik (open source) dari sistem seperti itu.

cody
sumber
Apakah benar untuk mengatakan bahwa paradigma logika / kendala lebih untuk menentukan jawaban daripada menentukan program. Tentu saja, Anda dapat mengatakan bahwa spesifikasi yang tidak lengkap adalah sebuah program. Tapi entah bagaimana, saya tidak yakin itu adalah permainan yang sama dengan sintesis program. Memang benar bahwa itu menjawab contoh, karena contoh itu sangat sederhana. Saya tidak bermaksud mengatakan bahwa kendala pemrograman hanya untuk masalah sederhana.
babou