Programming Language Concept Session 13
- Programming yang menggunakan bentuk logika simbolik sebagai bahasa programming sering dikenal dengan logic programming
- Bahasa yang didasari pada logika simbolik dikenal dengan logic programming language, atau declarative language
Intro Singkat ke Predikat Kalkulus
- Proposition merupakan pernyataan logika yang berkemungkinan (atau tidak) bernilai true
- Proposition berisi objek dan hubungan objek dengan satu sama lain
- Logika yang dapat digunakan untuk keperluan dasar logika formal:
– Menyatakan proposition
– Menyatakan hubungan antar proposition
– Menjelaskan bagaimana proposition baru - Bentuk tertentu logika simbolik yang digunakan untuk programming logika dikenal predicate calculus
- Objek di proposition diwakilkan antara constant atau variable
- Constant merupakan simbol yang mewakili objek
- Variable merupakan simbol yang dapat mewakili objek berbeda di waktu yang berbeda
- Atomic proposition berisi compound term
- Compound term merupakan satu elemen relasi metematika, ditulis seperti fungsi matematika
– Fungsi matematika merupakan suatu pemetaan
– Dapat ditulis sebagai tabel - Compound term dibuat dari dua bagian:
– Functor: simbol fungsi yang menamakan hubungan
– Daftar berurut parameter (tuple)
– Contoh:student(jon)
like(seth, OSX)
like(nick, windows)
like(jim, linux)
- Proposition dapat dikondisikan di dua bentuk:
– Fact: proposition diasumsikan menjadi true- Query: kebenaran proposition akan ditentukan - Compound proposition memiliki dua atau lebih proposition atomic, dan proposition dihubungkan oleh operator
- Operator logika:
- Quantifier
Overview of Logic Programming
- Salah satu karakteristik esensial bahasa programming logika adalah semanticnya, yang dikenal dengan declarative semantic
- Declarative semantic lebih sederhana dari semantic di bahasa imperative
Term
- Term merupakan suatu constant, variable, atau structure
- Constant merupakan atom atau integer
- Atom merupakan nilai simbolik dari Prolog
- Atom berisi antara:
– Kumpulan huruf, digit, dan underscore yang dimulai dengan huruf kecil
– Kumpulan karakter ASCII yang dapat dicetak dibatasi oleh apostrophe - Variable merupakan kumpulan huruf, digit, dan underscore apapun yang dimulai dengan huruf capital
- Instantiation merupakan pengikatan variable ke nilai
- Structure mewakili atomic proposition
Fact Statement
- Digunakan untuk hipotesis
- Klausa Headless Horn:
female(shelley).
male(bill).
father(bill, jake).
Rule Statement
- Digunakan untuk hipotesis
- Kalusa Headed Horn
- Sisi kanan : antecedent (bagian if)
– Dapat berupa single term atau conjunction - Sisi kiri : consequent (bagian then)
– Harus berupa single term - Conjuntion merupakan multiple term yang dipisahkan oleh operator logika AND
- Contoh:
ancestor(mary,shelley):- mother(mary,shelley).
Goal Statement
- Untuk teorema pembuktian, teorema dalam bentuk proposition yang kita ingin system membuktikan atau tidak – goal statement
- Beberapa format sebagai headless Horn
man(fred)
- Proposition conjunctive dan proposition dengan variable juga legal goal
father(X, mike)
Inferencing Process of Prolog
- Quary disebut goal
- Jika goal merupakan compound proposition, tiap faktanya merupakan subgoal
- Untuk membuktikan suatu goal true, harus mencari rantai aturan inference dan atau fakta, untuk goal Q:
P2 :- P1
P3 :- P2
…
Q :- Pn
- Proses membuktikan subgoal dikenal dengan matching, satisfying, atau resolution
- Matching merupakan proses pembuktian proposition
- Membuktikan subgoal disebut satisfying subgoal tersebut
- Pendekatan mulai dengan fakta dan aturan database dan mencoba mencari rentetan match yang membawa ke goal disebut dengan bottom-up resolution, atau forward chaining
- Pendekatan mulai dengan goal dan mencoba mencari rentetan matching proposition yang membawa ke beberapa set fakta awal di database disebut top-down resolution, atau backward chaining
- Implementasi prolog menggunakan backward chaining
- Ketika goal memiliki lebih dari satu subgoal, dapat menggunakan antara:
– Depth-first search: mencari bukti lengkap untuk subgoal pertama sebelum mengerjakan yang lainnya
– Breadth-first search: mengerjakan semua subgoal secara pararel - Prolog menggunakan depth-first search
- Goal dengan banyak subgoal, jika gagal menunjukkan kebenaran salah satu subgoal, mempertimbangkan kembali subgoal sebelumnya untuk mencari solusi alternative, disebut backtracking
- Backtracking mulai mencari diamana pencarian sebelumnya ditinggalkan
- Backtracking dapat memakan banyak waktu dan tempat karena mungkin mencari semua kemungkinan bukti ke tiap subgoal
Aritmatika Sederhana
- Prolog mendukung variable integer dan aritmatika integer
- Operator is mengambil ekspresi aritmatika sebagai operand kanan dan variable sebagai operand kiri, contoh:
A is B / 17 + C
- Tidak sama dengan pernyataan assignment, berikut ini illegal:
Sum is Sum + Number.
- Contoh:
speed(ford,100).
speed(chevy,105).
speed(dodge,95).
speed(volvo,80).
time(ford,20).
time(chevy,21).
time(dodge,24).
time(volvo,24).
distance(X,Y) :- speed(X,Speed),
time(X,Time),
Y is Speed * Time.
A query: distance(chevy, Chevy_Distance).
Trace
- Merupakan struktur built-in yang menampilkan instantiation ditiap langkah
- Tracing model eksekusi – empat kejadian:
– Call (permulaan mencoba untuk satisfy goal)
– Exit (ketika goal sudah di-satisfy)
– Redo (ketika backtrack terjadi)
– Fail (ketika goal gagal) - Contoh:
likes(jake,chocolate).
likes(jake, apricots).
likes(darcie, licorice).
likes(darcie, apricots).
trace.
likes(jake, X), likes(darcie, X).
- 1 Call: likes(jake, _0)?
(1) 1 Exit: likes(jake, chocolate)
(2) 1 Call: likes(darcie, chocolate)?
(2) 1 Fail: likes(darcie, chocolate)
- 1 Redo: likes(jake, _0)?
(1) 1 Exit: likes(jake, apricots)
(3) 1 Call: likes(darcie, apricots)?
(3) 1 Exit: likes(darcie, apricots)
X = apricots
List Structure
- List merupakan rentetan elemen angka berapapun
- Elemen dapat berupa atom, atomic proposition, atau term lain (termasuk list lain)
[apple, prune, grape, kumquat]
[] (empty list)
[X | Y] (head X and tail Y)
- Contoh append
append([], List, List).
append([Head | List_1], List_2, [Head | List_3]) :-
append (List_1, List_2, List_3).
Kekurangan Prolog
- Resolution order control
– Di lingkungan programming logika murni, urutan matches yang dicoba adalah tidak deterministik dan semua match akan dicoba secara concurrent - Asumsi closed-world
– Satu-satunya pengetahuan hanya yang ada di database - Masalah negasi
– Apapun yang dinyatakan di database diasumsikan menjadi false - Pembatasan intrinsik
– Mudah untuk menyatakan proses pengurutan secara logika, namun susah untuk melakukannya
Aplikasi Programming Logika
- Sistem manejemen database relasional
- Sistem expert
- Pemrosesan bahasa natural
Sumber:
- Concept of Programming Languages 10th. Ed / Robert W. Sebesta (Chapter 16)
- Logic Programming Languages / Binus Powerpoint Presentation