Logika pemrograman

Templat:Paradigma Pemrograman

Logika Pemrograman adalah paradigma pemrograman yang sebagian besar didasari dalam logika formal. Seluruh program yang ditulis pada sebuah logika bahasa pemrograman adalah sekelompok kalimat-kalimat dalam bentuk logis, mengekspresikan fakta-fakta, dan peraturan-peraturan tentang beberapa permasalahan yang didalam bagian tersebut. Bahasa pemrograman logika sebagian besar termasuk Prolog, jawaban sekelompok pemrograman atau _answer set programming_ (ASP) dan Datalog. Dalam seluruh bahasa-bahasa berikut, peraturan-peraturannya ditulis dalam bentuk klausa:

H :- B₁, …, B_n.

dan telah dibaca secara deklaratif sebagai implikasi logis:

H if B₁ dan … dan B_n.

H disebut kepala atau _head_ dari peraturan dan B₁, ..., B_n dipanggil badan atau body. Fakta-fakta adalah peraturan-peraturan yang tak memiliki badan, dan ditulis dalam bentuk simpleks:

H.

Dalam kasus yang simpleks dimana H, B₁, ..., B_n adalah semuanya formula atomik, klausa-klausa ini dipanggil klausa definit atau Klausa Horn. Namun, ada banyak ekstensi dari kasus simpleks ini, untuk kasus yang paling penting adalah dimaan kondisi-kondisinya dalam tubuh dari sebuah klausa, bisa juga dari negasi dari formula atomik. Bahasa pemrograman logis termasuk dalam ekstensi ini memiliki ilmu pengetahuan yang merepresentasikan kapabilitas dari logika non-monoton.

Dalam ASP atau _Answer Set Programming_ atau jawaban sekelompok pemrograman dan Datalog, program logika hanya memiliki satu bacaan dari deklaratif, dan eksekusinya adalah dilakukan dengan melakukan bukti prosedur atau model generator yang perilakunya tidak dimaksudkan untuk dikontrol oleh programmer. Namun, dalam keluarga bahasa Prolog, program logis juga memiliki interpretasi Prosedural sebagai prosedur reduksi tujuan:

untuk menyelesaikan H, selesaikan B₁, dan ... dan selesaikan juga B_n.

Pertimbangkan juga klausa berikut sebagai contohnya:

bersalah(X) :- manusia(X).

Berdasarkan pada sebuah contoh digunakan oleh Terry Winograd ^[1] untuk mengiilustrasikan bahasa pemrograman Planner. Sebagai sebuah klausa dalam program logis, bisa digunakan sebagai prosedur untuk mengetes apakah X adalah bersalah dengan mengetes apakah X adalah manusia, dan sebagai prosedur untuk menemukan X dimana bersalah ditemukan sebuah X dimana seorang manusia Bahkan fakta-fakta memiliki interpretasi prosedural. Contoh, klausa:

manusia(sokrates).

bisa digunakan sebagai prosedur untuk menunjukkan bahwa sokrates adalah manusia, dan sebagai prosedur untuk mencari X adalah sebagai human dengan "memberikan" sokrates untuk X.

Pembacaan deklaratif untuk program logis bisa digunakan oleh programmer untuk memeriksa kebenarannya. Lebih lagi, berdasarkan logika program transformasi, teknik-tekniknya bisa dilakukan juga untuk mentransformasi program logika menjadi program ekuivalen secara logis yang sama-sama lebih efisien. Dalam keluarga bahasa pemrograman logika Prolog, seorang programmer bisa menggunakan perilaku penyelesaian masalah yang telah diketahui dari mekanisme eksekusi untuk meningkatkan efesiensi dari sebuah program.

Sejarah

Penggunaan logika matematika untuk merepresentasikan dan menjalankan program komputer juga merupakan fitur dari kalkulus lambda, yang dikembangkan oleh Alonzo Church pada tahun 1930-an. Namun, proposal pertama untuk menggunakan bentuk logika clausal untuk merepresentasikan program komputer dibuat oleh Cordell Green.^[2]. Ini menggunakan aksiomatisasi subset dari LISP, bersama dengan representasi relasi masukan-keluaran, untuk menghitung relasi dengan mensimulasikan eksekusi program di LISP. Di sisi lain, Foster dan Elcock, menggunakan kombinasi persamaan dan kalkulus lambda dalam bahasa pemrograman asersi yang tak membatasi urutan dari operasi yang dilakukan.^[3]

Pemrograman logika sekarang dapat ditelusuri kembali ke perdebatan akhir tahun 1960-an dan awalh 1970-an tentang representasi pengetahuan deklaratif dengan prosedural di kecerdasan buatan.Para pendukung representasi deklaratif terutama bekerja di Stanford, terkait dengan John McCarthy, Bertram Raphael dan Cordell Green, dan di Edinburgh, dengan John Alan Robinson (pengunjung akademik dari Universitas Syracuse), Pat Hayes, dan Robert Kowalski. Pendukung representasi prosedural terutama dipusatkan di MIT, di bawah kepemimpinan Marvin Minsky dan Seymour Papert^{[butuh rujukan]}

Meskipun didasarkan pada metode pembuktian logika, Planner, yang dikembangkan di MIT, adalah bahasa pertama yang muncul dalam paradigma prosedural ini.^[4] Perencana menampilkan pemanggilan rencana prosedural yang diarahkan pola dari tujuan (yaitu reduksi tujuan atau rangkaian mundur dan dari pernyataan asersi atau rangkaian maju. mplementasi Planner yang paling berpengaruh adalah bagian dari Planner, yang disebut Micro-Planner, yang diimplementasikan oleh Gerry Sussman, Eugene Charniak dan Terry Winograd. Dimaan itu digunakan untuk mengimplementasikan program pemahaman bahasa alami Winograd SHRDLU, yang merupakan mercusuar pada waktu itu.^[1] Untuk mengatasi sistem memori yang sangat terbatas pada saat itu, Planner menggunakan backtracking struktur kontrol sehingga hanya satu jalur perhitungan yang mungkin harus disimpan pada satu waktu. Planner melahirkan bahasa pemrograman QA-4, Popler, Conniver, QLISP, dan bahasa konkuren Ether.^{[butuh rujukan]}

Hayes dan Kowalski di Edinburgh mencoba mendamaikan pendekatan deklaratif berbasis logika untuk representasi pengetahuan dengan pendekatan prosedural Planner. Hayes (1973) mengembangkan bahasa persamaan, Golux, di mana prosedur yang berbeda dapat diperoleh dengan mengubah perilaku pembukti teorema.^[5] Sebaliknya, Kowalski mengembangkan resolusi SLD,^[6] varian resolusi SL,^[7] dan ditunjukkan bagaimana memperlakukan implikasi sebagai prosedur reduksi tujuan. Kowalski bersama dengan Colmerauer di Marseille, yang telah mengembangkan ide ini dalam desain dan implementasi bahasa pemrograman Prolog.

Asosiasi untuk Pemrograman Logika telah ditemukan untuk mempromosikan Pemrogramin Logika di tahun 1986.

Prolog memberikan kebangkitan kepada bahasa-bahasa pemrograman ALF, Fril, Gödel, Mercury, Oz, Ciao, Visual Prolog, XSB, dan λProlog, serta berbagai bahasa pemrograman logika konkuren,^[8] pemrograman logika konstrain ^[9]

Konsep

Semantik

Maarten van Emden dan Robert Kowalski mendefinisikan tiga semantik untuk program logika klausa Horn, model-theoretic, fixed-point, dan bukti teoritis, dan menunjukkan bahwa mereka lebih ekuivalen.^[10]

Logika dan Kontrol

Pemrograman logika bisa dilihat sebagai deduksi terkontrol. Sebuah konsep penting dalam pemrograman logika adalah separasi dari program kepada komponen logika dan kontrolnya. Dengan bahasa pemrograman logika yang murni, komponen logika sendirik dapat menentukan solusi yang dihasilkan. Komponen kontrol bisa bervariasi untuk memberikan jalan alternatif dalam mengeksekusi logika program. Notasi ini diambil dengan slogan

Algoritma = Logika + Kontrol

Dimana "Logika" merepresentasikan program logis dan "Kontrol" merepresenasikan strategi pembuktian teorema yang berbeda.^[11]

Penyelesaian Masalah

Dalam kasus proposisional yang disederhanakan di mana program logika dan tujuan atom tingkat atas tidak mengandung variabel, penalaran mundur menentukan AND-OR pohon, yang merupakan ruang pencarian untuk memecahkan tujuan. Sasaran tingkat atas adalah akar pohon. Diberikan node mana pun di pohon dan klausa mana pun yang kepalanya cocok dengan node, ada sekumpulan node anak yang sesuai dengan sub-tujuan di badan klausa. Simpul anak ini dikelompokkan bersama oleh "AND". Himpunan anak-anak alternatif yang sesuai dengan cara-cara alternatif untuk memecahkan simpul dikelompokkan bersama oleh "OR".

Strategi pencarian apa pun dapat digunakan untuk mencari ruang ini. Prolog menggunakan strategi backtracking berurutan, last-in-first-out, di mana hanya satu alternatif dan satu sub-tujuan yang dipertimbangkan pada satu waktu. Strategi pencarian lainnya, seperti pencarian paralel, penelusuran mundur yang cerdas, atau pencarian pertama terbaik untuk menemukan solusi optimal, juga dimungkinkan.

Dalam kasus yang lebih umum, di mana sub-tujuan berbagi variabel, strategi lain dapat digunakan, seperti memilih sub-tujuan yang paling banyak diinstansiasi atau yang cukup diinstansiasi sehingga hanya satu prosedur yang berlaku. Strategi seperti itu digunakan, misalnya, di pemrograman logika konkuren.

Negasi sebagai Kegagalan

Untuk sebagian besar aplikasi praktis, serta untuk aplikasi yang membutuhkan penalaran non-monotonik dalam kecerdasan buatan, program logika Klausa Horn perlu diperluas ke program logika normal dengan kondisi negatif. Sebuah "klausa" dalam program logika normal memiliki bentuk:

H :- A₁, …, A_n, tidak B₁, …, tidak B_n.

dan dibaca secara deklaratif sebagai implikasi logis:

H jika sebuah₁ dan … dan sebuah_n dan bukan B₁ dan … dan tidak B_n.

Dimana H dan semua dari A_i dan B_i adalah formula atomik. Negasi pada literal negatif not B_i

^ ^a ^b Winograd, Terry (1972). "Understanding natural language (Memahami Bahasa Natural)". Cognitive Psychology. 3 (1): 1–191. doi:10.1016/0010-0285(72)90002-3.
^ Green, Cordell. Application of Theorem Proving to Problem Solving (Penerapan Teorema Pembuktian untuk Pemecahan Masalah) (PDF). IJCAI 1969.
^ Foster, J.M.; Elcock, E.W. (1969). ABSYS 1:An Incremental Compiler for Assertions: an Introduction (Sebuah Penyusun Inkremental untuk Pernyataan: Sebuah Pengantar). Fourth Annual Machine Intelligence Workshop. Machine Intelligence. 4. Edinburgh, UK: Edinburgh University Press. hlm. 423–429.
^ Hewitt, Carl. Planner: A Language for Proving Theorems in Robots (Bahasa untuk Membuktikan Teorema pada Robot) (PDF). IJCAI 1969.
^ Hayes, Pat (1973). "Computation and Deduction (Komputasi dan Deduksi)". Proceedings of the 2nd MFCS Symposium (Kelanjutan dari Simposium MFCS ke-2). Czechoslovak Academy of Sciences. hlm. 105–118.
^ Kowalski, Robert (1973). "Predicate Logic as a Programming Language (Predikat Logika sebagai Bahasa Pemrograman)" (PDF). Department of Artificial Intelligence, Edinburgh University. Memo 70. Juga dalam kelanjutan kongres IFIP, Stockholm, Belanda utara Publishing Co., 1974, pp. 569–574.
^ Kowalski, Robert; Kuehner, Donald (Winter 1971). .ic.ac.uk/~rak/papers/sl.pdf "Linear Resolution with Selection Function (Resolusi Linear dengan Fungsi Seleksi)" Periksa nilai |url= (bantuan) (PDF). Artificial Intelligence. 2 (3–4): 227–260. doi:10.1016/0004-3702(71)90012-9.
^ Shapiro, Ehud (1989). The family of concurrent logic programming languages (Keluarga dari bahasa pemrograman logis konkuren) (PDF). International Summer School on Logic, Algebra and Computation. Diarsipkan dari versi asli (PDF) tanggal February 23, 2017. Juga muncul di Shapiro, E. (1989). "The family of concurrent logic programming languages (Keluarga dari bahasa pemrograman logis konkuren)". ACM Computing Surveys. 21 (3): 413–510. CiteSeerX 10.1.1.73.8108 . doi:10.1145/72551.72555.
^ Sáenz-Perez, Fernando; Caballero, Rafael; García-Ruiz, Yolanda (December 2011). A Deductive Database with Datalog and SQL Query Language (Sebuah Deduksi Basis Data dengan Datalog dan Bahasa Kueri SQL) (PDF). Asian Symposium on Programming Languages and Systems. Springer. hlm. 66–73.
^ Van Emden, M.H.; Kowalski, R.A. (October 1976). "The semantics of predicate logic as a programming language (Semantik dari Predikat Logika Sebagai Bahasa Pemrograman)". Journal of the ACM. 23 (4): 733–742. doi:10.1145/321978.321991.
^ R.A.Kowalski (July 1979). "Algorithm=Logic + Control (Algoritma = Logika + Kontrol)". Communications of the ACM. 22 (7): 424–436. doi:10.1145/359131.359136 .

[Winograd-1] Winograd, Terry (1972). "Understanding natural language (Memahami Bahasa Natural)". Cognitive Psychology. 3 (1): 1–191. doi:10.1016/0010-0285(72)90002-3.

[2] Green, Cordell. Application of Theorem Proving to Problem Solving (Penerapan Teorema Pembuktian untuk Pemecahan Masalah) (PDF). IJCAI 1969.

[3] Foster, J.M.; Elcock, E.W. (1969). ABSYS 1:An Incremental Compiler for Assertions: an Introduction (Sebuah Penyusun Inkremental untuk Pernyataan: Sebuah Pengantar). Fourth Annual Machine Intelligence Workshop. Machine Intelligence. 4. Edinburgh, UK: Edinburgh University Press. hlm. 423–429.

[4] Hewitt, Carl. Planner: A Language for Proving Theorems in Robots (Bahasa untuk Membuktikan Teorema pada Robot) (PDF). IJCAI 1969.

[5] Hayes, Pat (1973). "Computation and Deduction (Komputasi dan Deduksi)". Proceedings of the 2nd MFCS Symposium (Kelanjutan dari Simposium MFCS ke-2). Czechoslovak Academy of Sciences. hlm. 105–118.

[Kowalski-6] Kowalski, Robert (1973). "Predicate Logic as a Programming Language (Predikat Logika sebagai Bahasa Pemrograman)" (PDF). Department of Artificial Intelligence, Edinburgh University. Memo 70. Juga dalam kelanjutan kongres IFIP, Stockholm, Belanda utara Publishing Co., 1974, pp. 569–574.

[7] Kowalski, Robert; Kuehner, Donald (Winter 1971). .ic.ac.uk/~rak/papers/sl.pdf "Linear Resolution with Selection Function (Resolusi Linear dengan Fungsi Seleksi)" Periksa nilai |url= (bantuan) (PDF). Artificial Intelligence. 2 (3–4): 227–260. doi:10.1016/0004-3702(71)90012-9.

[8] Shapiro, Ehud (1989). The family of concurrent logic programming languages (Keluarga dari bahasa pemrograman logis konkuren) (PDF). International Summer School on Logic, Algebra and Computation. Diarsipkan dari versi asli (PDF) tanggal February 23, 2017. Juga muncul di Shapiro, E. (1989). "The family of concurrent logic programming languages (Keluarga dari bahasa pemrograman logis konkuren)". ACM Computing Surveys. 21 (3): 413–510. CiteSeerX 10.1.1.73.8108 . doi:10.1145/72551.72555.

[9] Sáenz-Perez, Fernando; Caballero, Rafael; García-Ruiz, Yolanda (December 2011). A Deductive Database with Datalog and SQL Query Language (Sebuah Deduksi Basis Data dengan Datalog dan Bahasa Kueri SQL) (PDF). Asian Symposium on Programming Languages and Systems. Springer. hlm. 66–73.

[10] Van Emden, M.H.; Kowalski, R.A. (October 1976). "The semantics of predicate logic as a programming language (Semantik dari Predikat Logika Sebagai Bahasa Pemrograman)". Journal of the ACM. 23 (4): 733–742. doi:10.1145/321978.321991.

[11] R.A.Kowalski (July 1979). "Algorithm=Logic + Control (Algoritma = Logika + Kontrol)". Communications of the ACM. 22 (7): 424–436. doi:10.1145/359131.359136 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]