Halo pembaca yang budiman. Artikel ini akan fokus pada satu pendekatan untuk pembuatan program secara otomatis sesuai dengan model blok masalah, untuk memecahkan masalah terbalik (memulihkan model masalah asli dari program yang sudah dibuat), dan juga untuk memecahkan masalah verifikasi program yang dihasilkan. Topiknya sendiri sangat serius, tetapi saya akan mencoba membuat artikel sepopuler mungkin (tanpa ulasan analog, bagian teoretis yang dirumuskan dengan ketat dan kesulitan lainnya), dengan contoh dan deskripsi berbagai aplikasi.

1. Pembuatan program secara otomatis

Untuk menghasilkan program apa pun, pertama-tama perlu untuk mengetahui masalah apa yang sedang kita pecahkan. Memiliki pernyataan masalah yang diformalkan dengan jelas, sudah dimungkinkan untuk membangun aturan tertentu untuk memperluas pernyataan ini menjadi rencana untuk memecahkan masalah dan aturan untuk mengubah rencana solusi ke kode akhir dalam bahasa algoritmik umum atau khusus. Dalam hal ini, pendekatan biasanya digunakan untuk membangun program akhir dari blok siap pakai yang dibuat sebelumnya - algoritma tipikal yang dihubungkan oleh kode panggilan / penyajian tertentu.

Biarkan perumusan awal masalah yang akan dipecahkan disajikan dalam bentuk diagram blok (blok dapat berupa elementer atau, pada gilirannya, menjadi sub-sirkuit), misalnya, jaringan objek, yang masing-masing milik kelas tertentu dari hierarki konsep kelas dari area subjek. Pernyataan seperti itu akan sangat jelas dan dapat dipahami oleh orang dan sistem yang menghasilkan program. Sistem harus mengubah pernyataan seperti itu menjadi rencana untuk menyelesaikan masalah sesuai dengan beberapa aturan logis. Jadi, akan lebih tepat untuk menulis aturan konversi semacam itu dalam beberapa bahasa pemrograman logis, saya memilih GNU Prolog. Dalam praktiknya, saya perhatikan, seringkali mungkin untuk "melewati" fase pertama ini (deskripsi tingkat tinggi masalah) dengan segera membangun deskripsi rencana solusi, juga dalam bentuk diagram jaringan blok.

Rencana solusi yang dihasilkan harus dikonversi menjadi program, seperti yang sudah saya tulis, yang merupakan kode yang menghubungkan algoritma khas untuk memecahkan "batu bata" masalah, diimplementasikan, misalnya, dalam bentuk perpustakaan fungsi. Di sini berbagai cara dimungkinkan, saya akan menjelaskan dalam beberapa kata pendekatan yang saya gunakan. Proses pembuatan direpresentasikan dalam bentuk urutan kejadian (misalnya, pembuatan deklarasi, pembuatan bagian inisialisasi, tahapan bagian utama, de-inisialisasi), untuk masing-masing dimana jaringan objek harus di-cascade (merujuk ke kaskade jaringan, skema ini menghilangkan perulangan model ketika memproses acara) untuk merespons oleh generasi fragmen kode yang sesuai. Dalam hal ini, objek bergantung pada pengidentifikasi peristiwa, nilai-nilai parameternya (ditetapkan oleh pengguna saat membuat pernyataan blok masalah), serta pada data yang dapat ditransmisikan satu sama lain melalui hubungan di antara mereka. Oleh karena itu, setiap objek dari paket solusi memiliki metode untuk merespons peristiwa yang menghasilkan kode (dan, dalam kasus umum, teks arbitrer). Untuk mengatasi masalah ini, saya memilih bahasa PHP - itu hanya dapat menghasilkan fragmen teks sewenang-wenang.

Penyesuaian sistem ke area subjek dilakukan dengan mengembangkan hierarki kelas-kelas pembangkit yang sesuai.

Contoh skrip penghasil yang menghasilkan kode untuk kelas "Pemrosesan vektor (minimum, maksimum, rata-rata aritmatika)":

<? if ($Stage == stInit) { $argumentID = $Arg["ID"][0]; $argumentSize = $Arg["Size"][0]; $resultID = GetNextMail("result" . $this->ID); if ($this->Op == "Min") { echo " " . $resultID . " = 1E300;\n"; } else if ($this->Op == "Max") { echo " " . $resultID . " = -1E300;\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " = 0.0;\n"; } ?> for (i = 0; i < <? echo $argumentSize; ?>; i++) <? if ($this->Op == "Min") { ?> if (<? echo $argumentID . "[i] < " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } else if ($this->Op == "Max") { ?> if (<? echo $argumentID . "[i] > " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " += " . $argumentID . "[i];\n"; } if ($this->Op == "Avr") { echo " " . $resultID . " /= " . $argumentSize . ";\n"; } } ?> 

Ini adalah skema yang relatif tidak rumit yang berfungsi. Suatu sistem yang mengimplementasikan skema pembangkitan seperti itu (PGEN ++) memungkinkan, misalnya, pembuatan program yang menentukan dalam bidang-bidang berikut:

a) memodelkan proses penyebaran polusi;
b) solusi dari beberapa masalah kinematika manipulator robot sederhana;
c) program pelatihan sederhana untuk bekerja dengan data vektor (mencari rata-rata minimum, maksimum, aritmatika);
d) pengembangan tes untuk sistem pengujian psikologis PROFTEST.

Berikut adalah contoh pernyataan awal masalah (program pemrosesan data vektor sederhana) dalam bentuk diagram blok:



Dan ini adalah hasil dari pembuatan program :

2. Masalah terbalik: rekonstruksi pernyataan masalah (model awal) sesuai dengan program yang dihasilkan. Verifikasi program yang dihasilkan

Pertama-tama, mengapa perlu untuk menyelesaikan masalah seperti itu. Ini langsung, dan, saya pikir, aplikasi yang paling jelas adalah verifikasi program yang dibuat secara otomatis. Jika kita memiliki model A, membangun program P di atasnya, dari mana model B direkonstruksi, maka program tersebut kemungkinan besar benar jika model A dan B bersamaan.

Solusi sederhana berikut ini diusulkan. Pada generasi otomatis dari program muncul menghasilkan objek milik suatu hierarki kelas tertentu dari area subjek. Mereka hanya memiliki metode generatif. Tambahkan metode mengenali mereka. Kemudian program sumber (atau, dalam kasus umum, teks apa saja) secara berurutan dipindai oleh metode pengenalan masing-masing kelas, yang, setelah pengakuan berhasil, menghasilkan objek / objek dari kelas ini. Kita mendapatkan serangkaian elemen model yang diurutkan (dalam urutan "membaca" teks). Tetap menentukan hubungan di antara mereka berdasarkan urutan objek dan hubungan antara parameter mereka. Untuk ini, aturan keputusan khusus dapat diterapkan.

Metode pengakuan, dalam implementasi saya, terdiri dari bagian pengakuan (ini adalah sekelompok ekspresi reguler yang dimodifikasi) dan bagian yang menentukan (ditulis dalam GNU Prolog). Ekspresi reguler dimodifikasi sedemikian rupa untuk melakukan beberapa pra-pemrosesan (pemeriksaan kamus, cek fuzzy untuk kesamaan menurut Levenshtein, memeriksa keseimbangan ekspresi dalam tanda kurung) pada tahap parsing, untuk ini mereka menambahkan kemampuan untuk memasukkan berbagai rantai (memeriksa, menambahkan, menghapus, melatih jaringan saraf) dari predikat "cepat".

Sirkuit ini juga berfungsi. Sebagai aplikasi langsung, itu digunakan untuk merekonstruksi kurikulum sederhana untuk bekerja dengan data vektor (mencari minimum, maksimum, rata-rata aritmatika), dalam hal ini cukup berhasil menunjukkan verifikasi yang mungkin dari program yang dihasilkan dengan membandingkan model asli dan model yang direkonstruksi. Tetapi ada aplikasi lain, tentang mereka lebih lanjut.

3. Antarmuka bahasa alami untuk sistem pembuatan program

Saat memecahkan masalah terbalik (dijelaskan di atas), tidak ada batasan pada jenis bahan sumber untuk merekonstruksi model masalah yang sedang dipecahkan. Mungkin juga teks dalam bahasa alami. Cukup tulis metode pengenalan yang tepat. Oleh karena itu, aplikasi tak terduga dari masalah terbalik mungkin adalah implementasi antarmuka bahasa alami ke sistem generasi:

a) pernyataan masalah ditulis dalam bahasa alami yang disederhanakan;
b) masalah terbalik diselesaikan - pernyataan formal diekstraksi dari pernyataan bahasa alami (jaringan objek-elemen dari area subjek);
c) sistem diluncurkan untuk menghasilkan program sesuai dengan pernyataan formal yang diperoleh.

Dan sirkuit ini juga berfungsi. Contoh dikembangkan untuk kasus yang sama dari program pelatihan sederhana untuk bekerja dengan data vektor.

Berikut adalah contoh metode pengenalan (dari kelas keypad “Enter a vector or a scalar”), yang terbagi menjadi dua versi (pengenalan teks program (mode Programmatic) atau pengenalan fragmen pernyataan masalah dalam bahasa Rusia (mode Rusia)). Di atas adalah bagian pengakuan, lalu predikat pada GNU Prolog.

 @versions(Programmatical) @global_unique(PROCESS,infinity):- (\s*for\s*\(i\s*\=\s*0\;\s*i\s*\<\s*(\d+)->{N}\;\s*i\+\+\)\s*\{\\n\s*printf\(\"(\w+)->{VECTOR} \[\%i\]\s*\=\s*\"\,\s*i\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{VECTOR}\[i\]\)\;\\n\s*\}\\n)| (\s*printf\(\"(\w+)->{SCALAR}\s*\=\s*\"\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{SCALAR}\)\;\\n). @versions(Russian) @nearest(db_vvedem,2,"db_vvedem.csv"). @fast(db_var,"db_var.csv"). @global_unique(PROCESS,infinity):- (()->{VAR}([--]+)?=>{db_vvedem($)}\s+((\s+\s+)?)->{KEYB} ([--]+)?=>{db_var($,$VAR)}\s+(\w+)->{ID}((\s+\s+)?)!=>{KEYB}\s*\.). @versions(Russian) handle:-xpath('PROCESS','//ID/text()',[VText]), xpath('PROCESS','//VAR/text()',['0']), simple_vector(_,VText,_), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//ID/text()',[SText]), xpath('PROCESS','//VAR/text()',['1']), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical) handle:-xpath('PROCESS','//VECTOR/text()',[VText]), xpath('PROCESS','//N/text()',[NText]), simple_vector(_,VText,NText), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//SCALAR/text()',[SText]), simple_scalar(_,SText), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical,Russian) @goal:- handle,!. @done:- clear_db. 

Contoh pernyataan masalah dalam bahasa Rusia:

  .   max.   min.   V  10 .   V  .    V      min.     V      max.   min  .   max  .   V  .      . 

Dan model masalah yang diperoleh oleh sistem dari deskripsi bahasa alami di atas :

4. Aplikasi lain dari masalah terbalik

Ketika memecahkan masalah terbalik, tidak ada yang mencegah kita untuk mempertimbangkan kasus tidak hanya mengenali program tertentu, tetapi mengenalinya “dengan perbaikan” atau pemrosesan (karakter sewenang-wenang) lainnya. Secara khusus, adalah mungkin untuk mengembangkan "penjajaran otomatis" dari program yang dikenali ditulis dalam C. Ia melakukan analisis statis dan sebagian dinamis dari kode yang dikenal dan memasukkan arahan paralelisasi dari ekstensi Cilk / Cilk ++ ke dalamnya. Tugas peningkatan ini diimplementasikan dengan mengenali metode (pada GNU Prolog).

Contoh program C komputasi yang diproses oleh penjajah (ia memasukkan arahan cilk_spawn dan cilk_sync):

 #include <stdio.h> #include <math.h> #include <omp.h> #define PI 3.14159265358 #define NX 100 #define NY 100 #define MaxT 0.001 #define h 0.01 #define tau 0.00001 #define cilk_spawn _Cilk_spawn #define cilk_sync _Cilk_sync void F( double x, double y, double t, double * val ){ double r = sqrt(x*x + y*y); double result = 0.0; int i; for ( i = 0; i < 300; i++ ) result += exp(-r*t)*sin(0.1*i*r + 0.5*PI); *val = result; } int main( ){ double f[NY][NX] = {0.0}; double v[NY][NX] = {0.0}; double v1[NY][NX] = {0.0}; double t; int x, y; double start = omp_get_wtime(); for ( t = 0.0; t < MaxT; t += tau ) { for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) cilk_spawn F(x*h, y*h, t, &f[y][x]); for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) { cilk_sync; v1[y][x] = v[y][x] + tau*((v[y-1][x]+v[y+1][x]+v[y][x-1]+v[y][x+1]-4.0*v[y][x])/h/h - f[y][x]); } for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) v[y][x] = v1[y][x]; } for ( y = 0; y < NY; y++ ) { for ( x = 0; x < NX; x++ ) printf("%lf ", v[y][x]); printf("\n"); } printf("Total time = %lf\n", omp_get_wtime() - start); return 0; } 

5. Sedikit fiksi. Verifikasi dan identifikasi program sewenang-wenang dengan kode sumber tertutup

Di sini kita berbicara tentang program sewenang-wenang yang ditulis oleh seorang programmer dan / atau program yang menghasilkan sistem yang tidak ada kode sumbernya. Biarkan diperlukan untuk memeriksa fungsi yang benar dari program semacam itu, atau bahkan untuk memahami apa yang dilakukannya. Dalam kasus ini, satu atau versi lain dari apa yang disebut "lapisan meta" dapat digunakan - komponen hipotetis dari sistem operasi yang melacak seluruh urutan program (fungsi panggilan, mengubah data dalam memori, dll.) Dan membangun model perkiraan logikanya di dalamnya. bentuk yang setara dengan fungsi suatu program dalam bahasa pemrograman apa pun. Maka tetap untuk memecahkan masalah terbalik untuk program semacam itu - untuk mengembalikan model awal yang mungkin (atau model) yang akan memungkinkan setidaknya untuk mengevaluasi kebenaran atau memahami tujuan program. Prototipe dari "metaslayer" semacam itu pernah dikembangkan oleh penulis untuk kasus program C / C ++, tidak begitu banyak yang mungkin, tetapi sesuatu berhasil. Mungkin suatu hari seseorang akan ingin melakukan pekerjaan seperti itu secara penuh.

6. Kesimpulan

Saya berharap bahwa saya dapat menunjukkan bahwa pembuatan program secara otomatis dan solusi dari masalah terbalik bukanlah masalah akademis semata, tetapi sesuatu yang bermanfaat dan memiliki konsekuensi praktis langsung. Pada saat yang sama, keputusan yang disajikan di sini tidak berpura-pura lengkap dan jelas, tetapi mereka diimplementasikan dan berpura-pura ke hal baru tertentu.