Pemrograman Logika (Logic Programming)


Logika pemrograman, dalam arti luas, penggunaan logika matematika untuk pemrograman komputer. Dalam pandangan pemrograman logika, yang dapat ditelusuri setidaknya sejauh [1958] proposal saran-taker John McCarthy, logika digunakan sebagai bahasa representasi murni deklaratif, dan teorema-prover atau model-generator digunakan sebagai pemecah masalah. Tugas pemecahan masalah dibagi antara programmer, yang bertanggung jawab hanya untuk memastikan kebenaran program dinyatakan dalam bentuk logis, dan teorema-prover atau model-generator, yang bertanggung jawab untuk memecahkan masalah efisien.

Namun, logika pemrograman, dalam arti sempit yang lebih umum dipahami, adalah penggunaan logika baik sebagai bahasa representasi deklaratif dan prosedural. Hal ini didasarkan pada kenyataan bahwa penalaran mundur teorema-prover diterapkan pada kalimat deklaratif dalam bentuk implikasi:

 

Jika B1 dan … dan Bn kemudian H

memperlakukan implikasi sebagai prosedur tujuan-pengurangan:

untuk menunjukkan / memecahkan H, menampilkan / memecahkan B1 dan … dan Bn.

Misalnya, memperlakukan implikasinya:

Jika Anda menekan tombol sinyal alarm,

maka Anda waspada pengemudi kereta dari kemungkinan darurat

sebagai prosedur:

Untuk peringatan pengemudi kereta dari darurat mungkin,

tekan tombol sinyal alarm.

Perhatikan bahwa ini konsisten dengan interpretasi BHK logika konstruktif, di mana implikasi akan diinterpretasikan sebagai solusi solusi masalah H tertentu B1 … Bn. Namun, ciri pemrograman logika adalah bahwa set formula dapat dianggap sebagai program dan mencari bukti dapat diberikan arti komputasi. Hal ini dicapai dengan membatasi logika yang mendasari untuk sebuah fragmen “berkelakuan baik” seperti klausa Horn atau herediter Harrop formula. Lihat D. Miller et al., 1991.

Seperti dalam kasus murni deklaratif, programmer bertanggung jawab untuk memastikan kebenaran program. Tetapi karena pencarian bukti otomatis umumnya infeasible, logika pemrograman seperti umumnya dipahami juga bergantung pada programmer untuk memastikan bahwa kesimpulan yang dihasilkan secara efisien (lihat # Soal pemecahan). Dalam banyak kasus, untuk mencapai efisiensi, orang perlu untuk menyadari dan mengeksploitasi perilaku pemecahan masalah dari prover-teorema. Dalam hal ini, pemrograman logika adalah sebanding dengan pemrograman konvensional menggunakan program untuk mengontrol perilaku pelaksana program. Namun, tidak seperti program-program penting konvensional, yang hanya memiliki interpretasi prosedural, program logika juga memiliki interpretasi, deklaratif logis, yang membantu untuk memastikan kebenaran mereka. Selain itu, program-program tersebut, yang deklaratif, berada pada tingkat konseptual murni lebih tinggi daripada program-program penting, dan pelaksana program mereka, karena dalil-Prover, beroperasi pada tingkat konseptual lebih tinggi daripada konvensional kompiler dan interpreter.

SEJARAH

Pemrograman Logika dalam arti pertama dan lebih luas menimbulkan beberapa implementasi, seperti yang oleh Fischer Black (1964), James Slagle (1965) dan Cordell Green (1969), yang pertanyaan-menjawab sistem dalam semangat nasihat McCarthy -taker. Foster dan Absys Elcock’s (1969), di sisi lain, mungkin bahasa pertama yang secara eksplisit dikembangkan sebagai bahasa pemrograman assertional.

Logika pemrograman dalam arti sempit dapat ditelusuri kembali ke perdebatan di akhir 1960-an dan awal 1970-an tentang representasi deklaratif versus prosedural pengetahuan dalam Artificial Intelligence. Advokat representasi deklaratif yang terutama bekerja di Stanford, terkait dengan John McCarthy, Bertram Cordell Raphael dan Hijau, dan di Edinburgh, dengan Alan J. Robinson (seorang pengunjung akademik dari Syracuse University), Pat Hayes, dan Bob Kowalski. Advokat representasi prosedural terutama berpusat di MIT, di bawah kepemimpinan Marvin Minsky dan Seymour Papert.

Meskipun didasarkan pada logika, Planner, dikembangkan di MIT, adalah bahasa pertama yang muncul dalam paradigma ini proceduralist [Hewitt, 1969]. Perencana menampilkan pola diarahkan permintaan rencana prosedural dari tujuan (yaitu forward chaining) dan dari pernyataan (yaitu backward chaining). Pelaksanaan Planner paling berpengaruh adalah subset dari Planner, yang disebut Micro-Planner, dilaksanakan oleh Gerry Sussman, Eugene Charniak dan Terry Winograd. Itu digunakan untuk menerapkan pemahaman alam-bahasa Winograd’s program SHRDLU, yang merupakan tengara pada waktu itu. Dalam rangka mengatasi dengan sistem memori yang sangat terbatas yang tersedia ketika dikembangkan, Planner digunakan backtracking struktur pengendalian sehingga hanya satu jalur perhitungan mungkin harus disimpan pada suatu waktu. Dari Planner sana mengembangkan bahasa pemrograman QA-4, Popler, Conniver, QLISP, dan bahasa konkuren Eter.

Hayes dan Kowalski di Edinburgh mencoba mendamaikan pendekatan deklaratif logika berbasis representasi pengetahuan dengan pendekatan prosedural Planner’s. Hayes (1973) mengembangkan sebuah bahasa equational, Golux, di mana prosedur yang berbeda dapat diperoleh dengan mengubah perilaku prover teorema. Kowalski, di sisi lain, menunjukkan bagaimana SL-resolusi memperlakukan implikasi sebagai prosedur tujuan-reduksi. Kowalski berkolaborasi dengan Colmerauer di Marseille, yang mengembangkan ide-ide dalam desain dan implementasi bahasa pemrograman Prolog. Dari Prolog sana dikembangkan, antara lain, bahasa pemrograman ALF, Fril, Gödel, Mercury, Oz, Ciao, Visual Prolog, XSB, dan λProlog, serta berbagai bahasa pemrograman logika konkuren, (lihat Shapiro (1989) untuk survey), kendala bahasa pemrograman logika dan datalog.

 

Pada tahun 1997, Asosiasi Logika Pemrograman karuniakan kepada peneliti yang diakui lima belas dalam pemrograman logika Pendiri judul Logika Pemrograman untuk mengenali mereka sebagai pionir di lapangan. Para individu menerima penghargaan ini adalah: Maurice Bruynooghe (Belgia), Jacques Cohen (USA), Alain Colmerauer (Prancis), Keith Clark (Inggris), Veronica Dahl (Kanada / Argentina), Maarten van Emden (Kanada), Herve Gallaire (Prancis ), Robert Kowalski (Inggris), Jack Minker (USA), Fernando Pereira (USA), Luis Moniz Pereira (Portugal), Ray Reiter (Kanada), Alan Robinson (USA), Peter Szeredi (Hungaria), dan David HD Warren (Inggris).

PROLOG

Prolog bahasa pemrograman yang dikembangkan pada tahun 1972 oleh Alain Colmerauer. Ini muncul dari sebuah kolaborasi antara Colmerauer di Marseille dan Robert Kowalski di Edinburgh. Colmerauer bekerja pada pemahaman bahasa alami, menggunakan logika untuk mewakili semantik dan resolusi menggunakan untuk pertanyaan-menjawab. Selama musim panas 1971, Colmerauer dan Kowalski menemukan bahwa bentuk klausula logika dapat digunakan untuk mewakili tata bahasa formal dan resolusi Prover teorema yang dapat digunakan untuk parsing. Mereka mengamati bahwa Prover teorema beberapa, seperti hiper-resolusi, berperilaku sebagai parser bottom-up dan lain-lain, seperti SL-resolusi (1971), berperilaku sebagai parsing top-down.

Saat itu pada musim panas berikut 1972, yang Kowalski, sekali lagi bekerja dengan Colmerauer, mengembangkan penafsiran prosedural implikasi. Ini deklaratif ganda / penafsiran prosedural kemudian menjadi diformalkan dalam notasi Prolog

H: – B1, …, Bn.

yang dapat dibaca (dan digunakan) baik declaratively dan prosedural. Ini juga menjadi jelas bahwa klausula tersebut dapat dibatasi untuk klausul tertentu atau klausa Horn, di mana H, B1, …, Bn semua formula atom logika predikat, dan bahwa SL-resolusi bisa dibatasi (dan umum) untuk subur atau SLD-resolusi . interpretasi prosedural Kowalski dan subur digambarkan dalam, memo 1973 diterbitkan pada tahun 1974.

 

Colmerauer, dengan Philippe Roussel, digunakan interpretasi ganda dari pasal-pasal sebagai dasar Prolog, yang dilaksanakan pada musim panas dan musim gugur 1972. Program Prolog pertama, juga ditulis pada tahun 1972 dan dilaksanakan di Marseille, adalah sistem menjawab pertanyaan-Perancis. Penggunaan Prolog sebagai bahasa pemrograman praktis diberikan momentum besar oleh perkembangan sebuah kompiler oleh David Warren di Edinburgh pada tahun 1977. Percobaan menunjukkan bahwa Edinburgh Prolog bisa bersaing dengan kecepatan pengolahan lainnya bahasa pemrograman simbolik seperti Lisp. Edinburgh Prolog menjadi standar de facto dan sangat dipengaruhi definisi standar ISO Prolog.

NEGASI SEBAGAI GAGAL

Micro-Planner memiliki membangun, yang disebut “thnot”, yang bila diterapkan pada ekspresi mengembalikan nilai true jika (dan hanya jika) evaluasi ekspresi gagal. Operator setara biasanya built-in dalam implementasi Prolog modern dan telah disebut “negasi sebagai gagal”. Hal ini biasanya ditulis sebagai tidak (p), dimana p adalah sebuah atom yang variabel biasanya telah instantiated pada saat tidak (p) dipanggil. Sebuah samar lebih (tapi standar) sintaks adalah \ p +. Negasi sebagai literal kegagalan bisa terjadi sebagai kondisi tidak (Bi) dalam tubuh klausa program.

 

Status logis dari negasi sebagai kegagalan yang belum terselesaikan sampai Keith Clark [1978] menunjukkan bahwa, dalam kondisi alam tertentu, itu merupakan implementasi (dan kadang-kadang lengkap) yang benar dari negasi klasik sehubungan dengan selesainya program. Penyelesaian jumlah kasar mengenai himpunan semua klausa program dengan predikat yang sama di sisi kiri, berkata

 

H: – Body1.

H: – Bodyk.

 

sebagai definisi predikat

 

H iff (Body1 atau … atau Bodyk)

 

dimana “iff” berarti “jika dan hanya jika”. Menulis selesai juga membutuhkan penggunaan eksplisit dari predikat kesetaraan dan masuknya seperangkat aksioma yang tepat untuk kesetaraan. Namun, pelaksanaan negasi oleh kegagalan kebutuhan hanya jika-bagian dari definisi tanpa aksioma persamaan.

Gagasan penyelesaian terkait erat dengan semantik batasan McCarthy untuk penalaran default, dan dengan asumsi dunia ditutup.

Sebagai alternatif untuk penyelesaian semantik, negasi sebagai kegagalan juga dapat diartikan epistemically, seperti dalam model semantik stabil jawaban set pemrograman. Dalam penafsiran ini tidak (Bi) berarti harfiah bahwa Bi tidak diketahui atau tidak percaya. Penafsiran epistemis memiliki keuntungan yang dapat dikombinasikan dengan sangat sederhana dengan negasi klasik, seperti dalam “logika pemrograman diperpanjang”, untuk merumuskan frase seperti “Sebaliknya tidak dapat ditampilkan”, dimana “berlawanan” adalah negasi klasik dan “tidak dapat ditampilkan “adalah interpretasi epistemis dari negasi sebagai kegagalan.

PEMECAHAN MASALAH

Dalam kasus, disederhanakan proposisional di mana program logika dan tujuan atom tingkat atas tidak berisi variabel, penalaran mundur menentukan dan-atau pohon, yang merupakan ruang pencarian untuk menyelesaikan tujuan. Tujuan tingkat atas adalah akar pohon. Mengingat setiap node di pohon dan setiap ayat yang kepalanya cocok node, terdapat satu set node anak sesuai dengan sub-tujuan dalam tubuh klausa. Ini node anak dikelompokkan bersama-sama oleh “dan”. Alternatif set anak-anak sesuai dengan cara-cara alternatif pemecahan node dikelompokkan bersama-sama oleh seorang “atau”.

Setiap strategi pencarian dapat digunakan untuk mencari ruang ini. Prolog menggunakan, sekuensial terakhir-in-first-out, backtracking strategi, di mana hanya satu alternatif dan satu sub-tujuan dianggap pada suatu waktu. strategi pencarian lain, seperti pencarian paralel, mundur cerdas, atau mencari terbaik pertama untuk menemukan solusi optimal, juga mungkin.

Dalam kasus yang lebih umum, di mana sub-tujuan variabel berbagi, strategi lainnya dapat digunakan, seperti memilih subgoal yang paling tinggi instantiated atau yang cukup instantiated sehingga hanya satu prosedur berlaku. strategi tersebut digunakan, misalnya, dalam logika pemrograman konkuren.

Fakta bahwa ada cara alternatif menjalankan program logika telah ditandai oleh persamaan:

Algoritma = Logika + Control

dimana “Logika” merupakan program logika dan “Control” merupakan strategi membuktikan teorema-berbeda.

REPRESENTASI PENGETAHUAN

Fakta bahwa Tanduk klausa dapat diberikan interpretasi prosedural dan, sebaliknya, bahwa prosedur tujuan pengurangan dapat dipahami sebagai klausa Horn + mundur penalaran berarti bahwa program logika menggabungkan representasi deklaratif dan pengetahuan prosedural. Dimasukkannya negasi sebagai kegagalan berarti bahwa pemrograman logika adalah semacam logika non-monoton.

Meskipun kesederhanaan dibandingkan dengan logika klasik, ini kombinasi klausa Horn dan negasi sebagai kegagalan telah terbukti secara mengejutkan ekspresif. Misalnya, telah terbukti sesuai, dengan beberapa ekstensi lebih lanjut, cukup alami ke bahasa semi-formal undang-undang. Ini juga merupakan bahasa alam untuk menyatakan hukum-hukum yang masuk akal sebab dan akibat, seperti dalam situasi dan kalkulus kalkulus acara.

LOGIKA PEMROGRAMAN ABDUCTIVE

Abductive Logika Pemrograman merupakan perpanjangan dari Pemrograman Logika normal yang memungkinkan beberapa sebutan, dinyatakan sebagai predikat abducible, menjadi tidak lengkap ditetapkan. Pemecahan masalah dicapai dengan menurunkan hipotesis dinyatakan dalam predikat abducible sebagai solusi dari masalah yang harus diselesaikan. Masalah ini dapat berupa pengamatan yang perlu dijelaskan (seperti dalam penalaran abductive klasik) atau tujuan yang akan dicapai (seperti dalam pemrograman logika normal). Ini telah digunakan untuk memecahkan masalah dalam Diagnosa, Perencanaan, Alam Bahasa dan Machine Learning. Ini juga telah digunakan untuk menafsirkan Negasi sebagai Kegagalan sebagai bentuk penalaran abductive.

 

PEMROGRAMAN METALOGIC

Karena logika matematika memiliki tradisi panjang membedakan antara bahasa objek dan metalanguage, pemrograman logika juga memungkinkan pemrograman metalevel. The progam metalogic paling sederhana adalah apa yang disebut “vanili” meta-penerjemah:

memecahkan (true).

memecahkan ((A, B)): – menyelesaikan (A), memecahkan (B).

memecahkan (A): – ayat (A, B), memecahkan (B).

mana yang benar merupakan konjungsi kosong, dan ayat (A, B) berarti ada clause objek-tingkat bentuk A: – B.

pemrograman Metalogic memungkinkan objek-tingkat dan representasi metalevel untuk digabungkan, seperti dalam bahasa alami. Hal ini juga dapat digunakan untuk melaksanakan setiap logika yang ditentukan melalui aturan-aturan inferensi.

PEMROGRAMAN KENDALA

Kendala logika pemrograman merupakan perpanjangan dari Pemrograman Logika normal yang memungkinkan beberapa sebutan, dinyatakan sebagai predikat kendala, dapat terjadi sebagai literal dalam tubuh klausa. Literal ini tidak diselesaikan dengan tujuan-reduksi menggunakan klausa program, tetapi ditambahkan ke toko kendala, yang diperlukan agar sesuai dengan beberapa built-in semantik dari predikat kendala.

 

Pemecahan masalah dicapai dengan mengurangi masalah awal untuk satu set satisfiable kendala. Kendala pemrograman logika telah digunakan untuk memecahkan masalah dalam bidang-bidang seperti teknik sipil, teknik mesin, verifikasi sirkuit digital, penjadwalan otomatis, kontrol lalu lintas udara, dan keuangan. Hal ini terkait erat dengan pemrograman logika abductive.

LOGIKA PEMROGRAMAN SERENTAK

Keith Clark, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, dll mengembangkan keluarga dari pesan bersamaan Prolog-seperti pengoperan penyatuan sistem yang menggunakan variabel bersama dan struktur data stream untuk pesan. Upaya yang dilakukan untuk dasar sistem ini pada logika matematika, dan mereka digunakan sebagai dasar Generasi Kelima Jepang Proyek (ICOT). Namun, sistem konkuren-seperti Prolog didasarkan pada message passing dan akibatnya tunduk pada ketidakpastian yang sama dengan sistem bersamaan message-passing lainnya, seperti Aktor (lihat ketidakpastian dalam perhitungan konkuren). Akibatnya, bahasa ICOT tidak didasarkan pada logika dalam arti bahwa langkah-langkah komputasi tidak bisa logis disimpulkan [Hewitt dan Agha, 1988].

PEMROGRAMAN LOGIKA INDUKTIF

Pemrograman logika induktif berkaitan dengan generalisasi contoh positif dan negatif dalam konteks pengetahuan latar belakang. Generalisasi, serta contoh-contoh dan pengetahuan latar belakang, disajikan dalam sintaks logika pemrograman. kerja terbaru di daerah ini, menggabungkan pemrograman logika, belajar dan probabilitas, telah melahirkan bidang baru belajar pemrograman relasional statistik dan logika induktif probabilistik.

PEMROGRAMAN LOGIKA HIGH ORDER

Beberapa peneliti telah diperpanjang pemrograman logika dengan pemrograman tingkat tinggi yang berasal dari logika fitur tingkat tinggi, seperti variabel predikat. bahasa tersebut termasuk ekstensi Prolog HiLog dan λProlog.

LOGIKA PEMROGRAMAN LINIER

Mendasarkan logika pemrograman dalam logika linear telah menghasilkan desain bahasa pemrograman logika yang jauh lebih ekspresif daripada berdasarkan logika klasik. program klausa Horn hanya dapat mewakili mengubah negara dengan perubahan argumen untuk predikat. Dalam pemrograman logika linear, kita dapat menggunakan logika linier ambien untuk mendukung perubahan negara. Beberapa desain awal dari bahasa pemrograman logika berdasarkan logika linear termasuk LO [Andreoli & Pareschi, 1991], Lolli [Hodas & Miller, 1994], ACL [Kobayashi & Yonezawa, 1994], dan Forum [Miller, 1996]. Forum memberikan interpretasi goal-directed semua logika linier.

SUMBER:

www.google.com

www.wikipedia.org

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s