UNIFIKASI DAN LACAKBALIK

MODUL IV
UNIFIKASI DAN LACAKBALIK
( UNIFICATION AND BACKTRACKING )

A. TUJUAN
mengerti apa yang dimaksud unifikasi dan proses terjadinya.
mengerti cara kerja lacak balik dan prinsip-prinsipnya.
Dapat mengendalikan proses lacak balik menggunakan predikat fail, cut (!) dan not.


B. DASAR TEORI

1.Unifikasi (Unification)
Pada waktu Visual Prolog mencoba untuk mencocokkan suatu panggilan (dari sebuah subgoal) ke klausa (pada section clauses), maka proses tersebut melibatkan suatu prosedur yang dikenal dengan unifikasi (unification), yang mana berusaha untuk mencocokkan antara struktur data yang ada di panggilan (subgoal) dengan klausa yang diberikan. Unifikasi pada Prolog mengimplementasikan beberapa prosedur yang juga dilakukan oleh beberapa bahasa tradisional seperti melewatkan parameter, menyeleksi tipe data, membangun struktur, mengakses struktur dan pemberian nilai (assignment). Pada intinya unifikasi adalah proses untuk mencocokkan dua predikat dan memberikan nilai pada variabel yang bebas untuk membuat kedua predikat tersebut identik. Mekanisme ini diperlukan agar Prolog dapat mengidentifikasi klausa-klausa mana yang dipanggil dan mengikat (bind) nilai klausa tersebut ke variable.

Ada beberapa hal penting dalam proses pencocokan atau unifikasi, yaitu:
• Pada waktu Prolog berusaha untuk memenuhi sebuah goal, Prolog memulainya dari bagian paling atas (top) dari program dalam rangka mencari pencocokan.
• Ketika sebuah panggilan baru terjadi, pencarian pencocokan juga dimulai dari bagian paling atas dari program.
• Ketika sebuah panggilan mengalami pencocokan yang sukses, pemanggil kembali (is said to return), dan giliran subgoal berikutnya diuji.
• Ketika suatu variabel telah diikat (bound) pada sebuah klausa, cara-cara satu-satunya untuk membebaskan ikatan tersebut adalah melalui lacakbalik (backtracking).

2. Lacakbalik (Backtracking)
Pada waktu menyelesaikan masalah, seringkai seseorang harus menelusuri suatu jalur untuk mendapatkan konklusi yang logis. Jika konklusi ini tidak memberikan jawaban yang dicari, orang tersebut harus memilih jalur yang lain. Perhatikan permainan maze berikut. Untuk mencari jalan keluar dari maze, seseorang harus selalu mencoba jalur sebelah kiri terlebih dahulu pada setiap percabangan hingga menemukan jalan buntu. Ketika menemukan jalan buntu maka orang tersebut harus kembali ke percabangan terakhir (back-up) untuk mencoba lagi (try again) ke jalur kanan dan jika menemukan percabangan lagi maka tetap harus mencoba jalur kiri terlebih dahulu. Jalur kanan hanya akan sekali-sekali dipilih. Dengan begitu orang tersebut akan bisa keluar dari maze, dan memenangkan permainan.
Metode balik-ke-atas-dan-coba-lagi (backing-up-and-trying-again) ini pada Visual Prolog disebut lacakbalik (backtracking). Visual Prolog menggunakan metode ini untuk menemukan suatu solusi dari permasalahan yang diberikan.Visual Prolog dalam memulai mencari solusi suatu permasalahan (atau goal) harus membuat keputusan di antara kemungkinan-kemungkinan yang ada. Ia menandai di setiap percabangan (dikenal dengan titik lacak balik) dan memilih subgoal pertama untuk telusuri. Jika subgoal tersebut gagal (ekivalen dengan menemukan jalan buntu), Visual Prolog akan lacakbalik ke titik lacakbalik (back-tracking point) terakhir dan mencoba alternatif subgoal yang lain.

3. Pengendalian proses lacakbalik
Mekanisme lacak balik dapat menghasilkan pencarian yang tidak perlu, akibatnya program menjadi tidak efisien. Misalnya adanya beberapa jawaban yang muncul ketika kita hanya membutuhkan solusi tunggal dari masalah yang diberikan. Pada kasus lain, suatu kebutuhan untuk memaksa Visual Prolog untuk melanjutkan mencari jawaban tambahan walaupun goal tersebut sudah terpenuhi. Untuk kasus-kasus tersebut, kita harus mengontrol proses lacakbalik. Visual Prolog menyediakan 2 alat yang memperbolehkan kita untuk mengendalikan mekanisme lacak balik yaitu predikat fail yang digunakan untuk memaksa lacakbalik dan predikat cut (ditandai dengan !) yang digunakan untuk mencegah lacakbalik.

Predikat fail
Visual Prolog akan memulai lacakbalik jika ada panggilan yang gagal. Pada situasi tertentu, ada kebutuhan untuk memaksa lacakbalik dalam rangka mencari alternatif solusi. Visual Prolog menyediakan predikat khusus fail untuk memaksa kegagalan sehingga memicu terjadinya lacakbalik. Efek dari fail sama dengan efek memberikan perbandingan 2=3 atau subgoal yang tidak mungkin (impossible) lainnya.

Predikat Cut (!)
Visual Prolog memiliki cut yang digunakan untuk mencegah lacakbalik, ditulis berupa sebuah tanda seru (!). Efek dari cut adalah sederhana, yaitu tidak akan memungkinkan terjadinya lacakbalik melewati sebuah cut.Kita menempatkan cut dalam program sama persis seperti menempatkan sebuah subgoal pada body dari suatu rule. Ketika proses melewati cut, pemanggil ke cut dinyatakan sukses dan subgoal berikutnya (jika ada) dipanggil. Sekali sebuah cut dilewati, adalah menjadi tidak mungkin untuk melakukan lacakbalik pada subgoal yang berada pada sebelum cut pada klausa yang sedang diproses dan adalah menjadi tidak mungkin untuk melakukan lacakbalik ke predikat lain yang mendefinisikan predikat yang sekarang diproses (predikat yang mengandung cut).

4. Predikat Not
Program berikut memperlihatkan bagaimana penggunaan predikat not untuk mengidentifikasikan seorang mahasiswa teladan yaitu mahasiswa yang mempunyai Indeks Prestasi Kumulatif (IPK) minimal 3,5 dan tidak sedang dalam masa percobaan (sedang menjalani masa hukuman karena melakukan tindak kejahatan).

Ada satu catatan ketika menggunakan not yaitu predikat not akan sukses ketika subgoal tidak bisa dibuktikan kebenarannya. Hal ini untuk mencegah suatu situasi variabel yang belum diikat akan diikat menggunakan not. Jika subgoal dengan variabel bebas dipanggil melalui not, maka Visual Prolog akan mengeluarakan pesan kesalahan Free variables not allowed in ‘not’ or ‘retractall’.


C. PEMBAHASAN
Pada pertemuan praktikum kali ini, praktikan mempraktekkan tentang unifikasi dan lacakbalik yang di dalamnya terkandung pernyataan fail, cut dan not. Langkah awal yang dilakukan adalah mengaktifkan jendela Visual Prolog. Dari kelima program yang telah dipraktikan, praktikan akan membahas dua program, satu yang menggunakan unifikasi dan lacakbalik. tersebut.

Program pertama:
CLAUSES
ditulis_oleh (emha,”Markesot Bertutur”).
ditulis_oleh (kahlil, “Sang Nabi”)

buku (“Sang Nabi”, 132).
buku (“Markesot Bertutur”, 379).

buku_tebal(Judul):-
ditulis_oleh(_,Judul),
buku(Judul,Tebal),
Tebal > 300.

peng_buku_tebal(Nama):-
ditulis_oleh(Nama,Judul),
buku(Judul,Tebal),
Tebal > 300.

GOAL
buku_tebal ( X ).
Peng_buku_tebal(Nama).

Dari penggalan program di atas, dapat terlihat bahwa ada dua goal yang akan diuji. Pada goal pertama yang diinginkan adalah judul buku yang memiliki ketebalan lebih dari 300. Untuk memperoleh buku yang memiliki ketebalan lebih dari 300, pada awalnya Visual Prolog akan mencari pernyataan yang serupa dengan pernyataan goal, dalam hal ini adalah buku_tebal. Proses pencarian ini akan dimulai dari pernyataan fakta awal pada bagian clauses. Proses pencarian inilah yang disebut sebagai unifikasi. Fakta awal yang terdapat pada bagian clasues adalah ditulis_oleh dan tentu saja fakta ini mengalami kegagalan karena tidak memiliki kesamaan dengan pernyataan goalnya. Selanjutnya Visual Prolog mencari ke fakta berikutnya yakni buku, fakta ini juga tidak memiliki kesamaan dengan pernyataan goal. Pencarian terus dilanjutkan hingga fakta memiliki kesamaan dengan pernyataan goalnya. Fakta ketiga yang terdapat di bagian clauses program di atas adalah buku_tebal ( Judul ). Fakta tersebut memiliki kesamaan dengan pernyataan goalnya. Namun pada pernyataan goal terdapat argument X. Visual prolog akan mencocokkan argument ini terlebih dahulu bila faktanya sudah memiliki kesamaan. Dari program di atas dapat terlihat bahwa faktanya adalah: buku_tebal ( Judul ), sehingga dapat dimengerti bahwa argumen Judul sama dengan X. Sehingga X akan diikitkan dengan argument Judul.
Pada fakta buku_tebal ( Judul ), terdapat beberapa pernyataan syarat, karena fakta ini bertujuan untuk mengetahui judul buku yang memiliki ketebalan lebih dari 300. Syarat pertama akan dicek oleh visual prolog, yakni ditulis_oleh ( _, Judul ), maka akan dipanggil ditulis_oleh ( emha,”Markesot Bertutur” ). Dari fakta tersebut argumen judul yang sudah terikat dengan X akan mengikat fakta “Markesot Bertutur”. Argumen penulis tidak diikut sertakan karena hanya berupa argumen anonym. Selanjutnya Visual Prolog akan memanggil fakta syarat yang kedua, yakni: buku ( Judul, Tebal ). Selanjutnya visual akan mencari dari fakta awal buku, yakni ( “ Sang Nabi “, 132 ). Fakta ini gagal karena tidak memenuhi dengan syarat awalnya yaitu “ Markesot Bertutur ”. Selanjutnya visual akan mencek fakta berikutnya yakni ( “ Markesot Bertutur”, 379 ) dan fakta ini memiliki nilai yang sama dengan Judul, sehingga diikat kebenarannya. Clausa syarat berikutnya adalah Tebal lebih dari 300. Karena “ Markesot Bertutur” sudah memiliki nilai Tebal yang benar dan memenuhi maka hasil eksekusi program di atas adalah X = Markesot bertutur.
Pada goal yang kedua yang dicari adalah pengarang buku tebal yang memiliki ketebalan lebih dari 300. Untuk memperoleh pengarang buku yang memiliki ketebalan lebih dari 300, pada awalnya Visual Prolog akan mencari pernyataan yang serupa dengan pernyataan goal, dalam hal ini adalah peng_buku_tebal. Proses pencarian ini akan dimulai dari pernyataan fakta awal pada bagian clauses. Fakta awal yang terdapat pada bagian clauses adalah ditulis_oleh dan tentu saja fakta ini mengalami kegagalan karena tidak memiliki kesamaan dengan pernyataan goalnya. Selanjutnya Visual Prolog mencari ke fakta berikutnya yakni buku, fakta ini juga tidak memiliki kesamaan dengan pernyataan goal. Pencarian terus dilanjutkan hingga fakta memiliki kesamaan dengan pernyataan goalnya. Fakta ketiga yang terdapat di bagian clauses program di atas adalah peng_buku_tebal ( Nama ). Fakta tersebut memiliki kesamaan dengan pernyataan goalnya.
Pada fakta peng_buku_tebal ( Nama ), terdapat beberapa pernyataan syarat, karena fakta ini bertujuan untuk mengetahui pengarang buku yang memiliki ketebalan lebih dari 300. Syarat pertama akan dicek oleh visual prolog, yakni ditulis_oleh ( Nama, Judul ), maka akan dipanggil ditulis_oleh ( emha,”Markesot Bertutur” ). Dari fakta tersebut argumen Nama akan mengikat fakta emha. Selanjutnya Visual Prolog akan memanggil fakta syarat yang kedua, yakni: buku ( Judul, Tebal ). Selanjutnya visual akan mencari dari fakta awal buku, yakni ( “ Sang Nabi “, 132 ). Fakta ini gagal karena tidak memenuhi dengan syarat awalnya yaitu “ Markesot Bertutur ”. Selanjutnya visual akan mencek fakta berikutnya yakni ( “ Markesot Bertutur”, 379 ) dan fakta ini memiliki nilai yang sama dengan Judul, sehingga diikat kebenarannya. Clausa syarat berikutnya adalah Tebal lebih dari 300. Karena “ Markesot Bertutur” sudah memiliki nilai Tebal yang benar dan memenuhi maka hasil eksekusi dari goal yang kedua di atas adalah Nama = emha.


Program Kedua
Program kedua ini merupakan contoh program yang menggunakan lacakbalik.
GOAL
dapat_berenang ( Apa).
Program kedua ini ingin menemukan argumen Apa yang dapat berenang. Fakta dapat_berenang akan dicek kebenarannya dengan fakta-fakta yang terdapat pada clauses. Fakta jenis, adalah, dan hidup tidak memenuhi nilai kebenaran atau gagal. Fakta selanjutnya adalah dapat_berenang dan memenuhi nilai kebenaran ( true ). Argumen Y akan diikat dengan Argumen Apa. Pada fakta dapat_berenang terdapat pernyataan syarat, syarat pertamanya adalah jenis ( X, hewan ). Visual prolog akan memanggil klausa jenis. Pada bagian ini X akan terikat dengan vertebrata karena memiliki kebenaran ( true ). Pernyataan syarat kedua yakni adalah. Visua; Prolog akan memanggil klausa adalah ( zebra, vertebrata ). Klausa ini memiliki kebenaran karena argument X yang sudah terikat dengan vertebrata, sehingga Y akan terikat dengan Zebra. Pada langkah ini belum terjadi lacakbalik karena semua fakta dan klausa masih memiliki nilai kebenaran. Pernyataan syarat terakhir dari klausa dapat_berenang adalah hidup. Visual akan memanggil klausa hidup, hidup ( zebra, di_darat ). Klausa ini tidak memenuhi niali kebenaran atau gagal memenuhi goal karena Y yang terikat dengan zebra hidup di darat sehingga tidak dapat berenang.
Pada saat inilah visual akan melakukan langkah lacakbalik. Visual akan memanggil kembali klausa jenis yakni, jenis ( ikan, hewan ). Dengan demikian X yang tadinya sudah terikat dengan vertebrata kembali dilepas karena sudah tidak memenuhi nilai kebenaran ddan mengikat ikan. Selanjutnya visual akan memanggil klausa adalah ( lele, ikan ). Pada bagian ini Y yang tadinya sudah terikat dengan zebra kembali dilepas, sehingga Y mengikat lele. Sampai sejauh ini semua klausa masih memiliki nilai kebenaran true. Klausa yang menjadi syarat berikutnya adalah hidup. Hidup ( zebra, di_darat ), tidak lagi ikut dicek karena sudah gagal. Namun klausa yang mendeklarasikan bahwa lele hidup di_air tidak terdapat, sehingga fakta ini dinyatakan gagal. Karena fakta yang diinginkan oleh goal belum memenuhi nilai kebenaran, maka visual kembali mengadakan lacakbalik. Klausa jenis ( ikan, hewan ), masih digunakan karena masih memenuhi nilai kebenarannya. Sehingga X masih terikat dengan argument ikan. Visual akan memanggil klausa selanjutnya, yakni: adalah ( tuna, ikan ). Argumen Y yang sebelum lacakbalik terikat dengan lele akan mengikat tuna akrean tuna adalah ikan. Syarat selanjutnya adalah hidup ( Y, di_air ). Jadi Y hidup di air agar pernyataan goalnya terpenuhi kebenarannya. Sehingga visual akan memanggil klausa hidup. Pada klausa ini terdapat fakta yang menyatakan bahwa tuna hidup di air. Dengan demikian goal dapat_berenang ( Apa ) sudah terpenuhi kebenarannya. Hasil eksekusi program tersebut adalah Apa = tuna.

D. LISTING
Terlampir

F. KESIMPULAN
Unifikasi pada Prolog mengimplementasikan beberapa prosedur yang juga dilakukan oleh beberapa bahasa tradisional seperti melewatkan parameter, menyeleksi tipe data, membangun struktur, mengakses struktur dan pemberian nilai (assignment). Pada intinya unifikasi adalah proses untuk mencocokkan dua predikat dan memberikan nilai pada variabel yang bebas untuk membuat kedua predikat tersebut identik. Mekanisme ini diperlukan agar Prolog dapat mengidentifikasi klausa-klausa mana yang dipanggil dan mengikat (bind) nilai klausa tersebut ke variabel. Langkah yang perlu diperhatikan oleh praktikan maupun user bahwa prolog akan memulai pencarian untuk pencocokan mulai dari atas program sehingga goal yang diinginkan tercapai. Apabila panggilan yang ditemukan mengalami kegagalan nilai kebenaran, prolog akan mencocokkan panggilan berikutnya. Sementara itu lacak balik adalah proses mencocokkan predikat yang ada, namun apabila mengalami kebuntutan nilai kebenaran akan diulang dari klausa awalnya. Goal akan terpenuhi jika nilai kebenaran lacakbaliknya terdapat pada titik ekstrim pohon klausanya atau faktanya.

Secara umum, program Visual Prolog terdiri dari empat section dasar, yaitu section clauses, section predicates, section domains, dan terakhir section.
Dalam script program Visual Prolog terdapat beberapa aturan yang harus dipenuhi dalam pembuatan program ini. Pada bagian CLAUSES merupakan bagian yang penting tentang fakta dari program yang akan dijalankan. Untuk section Predicates dan Domains merupakan pendukung bagi section CLAUSES.
Prolog dalam menjalankan perintah eksekusi menggunakan cara berpikir deduktif (deductive reasoning) dan selalu melakukan lacak balik atau backtrackibg di setiap CLAUSESnya. Dalam Prolog, relasi antara object-object dinamakan predikat.
Pada waktu Visual Prolog mencoba untuk mencocokkan suatu panggilan (dari sebuah subgoal) ke klausa (pada section clauses), maka proses tersebut melibatkan suatu prosedur yang dikenal dengan unifikasi (unification), yang mana berusaha untuk mencocokkan antara struktur data yang ada di panggilan (subgoal) dengan klausa yang diberikan.
Dalam script program Visual Prolog terdapat beberapa aturan yang harus dipenuhi dalam pembuatan program ini. Pada bagian CLAUSES merupakan bagian yang penting tentang fakta dari program yang akan dijalankan. Untuk section Predicates dan Domains merupakan pendukung bagi section CLAUSES


TUGAS

GOAL
pembunuh(X).

setelah eksekusi GOAL dijalanakan maka Prolog akan memulai pelacakan dari fakta CLAUSES pertama yaitu data orang-orang yang terlibat dalam kasus pembunuhan, dan korban pembunuhan yaitu siti yang dibunuh dengan pentungan. Serta data-data orang yang berselingkuh. Sehigga visual prolog akan memulai dengan memberikan titik awal pada clauses pembunuh (Pembunuh ).
Dari fakta ini argument X akan diikat dengan argument Pembunuh. Dari fakta pembunuh ini terdapat penyataan syarat dan prolog akan melakukan unifikasi terhadap pernyataan syarat-syarat tersebut. Pernyataan syarat pertama orang ( Pembunuh,_,_ ). Prolog akan memanggil fakta orang untuk mengetahui pembunuh. Fakta pertama yang di dapat adalah budi.
Selanjutnya prolog akan memanggil fakta terbunuh dan didapat faktanya adalah siti.
kemudian prolog akan mencari fakta dari dicurigai(X), dari fakta ini kemudian akan dilakukan proses pencarian pernyataan bersyarat dan sekali lagi prolog akan melakukan unifikasi terhadap pernyataan syarat-syarat tersebut. Pernyataan syarat pertama terbunuh_dengan ( siti, Senjata ). Prolog akan memanggil fakta terbunuh_dengan untuk mengetahui senjata yang dipakai. Fakta yang di dapat adalah terbunuh_dengan( siti, pentungan ).
kemudian prolog akan mencari fakta dari benda yang cara kerjanya mirip senjata dari pernyataan bersyarat cara_kerja_mirip(Benda, Senjata). Lalu prolog akan memanggil fakta cara_kerja _mirip untuk mengetahui benda apa yang cara kerjanya mirip pentungan. Fakta yang didapat adalah cara_kerja_mirip(kaki_palsu, pentungan).
kemudian prolog akan mencari fakta dari kemungkinan_milik(X, Benda). Pada fakta ini ternyata ditemukan pernyataan bersyarat lagi yaitu pernyataan milik(X, Benda). Dari pernyataan ini akan dicari fakta bahwa siapa pemilik kaki palsu dan didapatkan fakta bahwa milik(budi, kaki_palsu).
setelah itu prolog kembali memeriksa fakta dari pembunuh karena masih ada pernyataan bersyarat yang belum diperiksa yaitu fakta ternodai(Pembunuh, Zat). Lalu prolog akan memanggil fakta ternodai untuk melihat zat apa yang menodai budi, dan didapat fakta bahwa ternodai(budi, darah).
setelah itu prolog akan memeriksa fakta terakhir yaitu ternodai(Terbunuh, Zat) dan didapat fakta bahwa ternodai(siti, darah). Dari fakta ini ditemukan bahwa siti mempunyai noda yang sama dengan budi.
berdasarkan kecocokan dari fakta-fakta diatas dari awal hingga akhir, sehingga prolog menetapkan bahwa pembunuh siti adalah budi.