PROLOG

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, PROLOG diline giriş yapmak ve basit bazı yapay zeka problemlerinin PROLOG dilinde nasıl kodlanarak çözüldüğünü göstermektir.

Kurulum ve çalıştırma:

Bu yazı kapsamında SWI-PROLOG programı kullanılacaktır. Programı, www.swi-prolog.org adresinden temin etmek mümkündür.

Yazı kapsamında MAC OSX üzerinde örnekler çalıştırılarak gösterilecektir ancak kurulum ve sonrasında başarılı bir çalıştırma yapılabiliyorsa hangi işletim sisteminde olduğunuzun bir önemi yoktur, bütün sistemlerde aynı PROLOG komutları çalışır.

Siteden indirilip kurulum yapıldıktan sonra,

$ /opt/local/bin/swipl 

Dizini altında bulunan swipl komutu çalıştırılarak, PROLOG komut satırı açılabilir.

Program çalıştırıldığında, aşağıdakine benzer bir komut satırı ile komut girilmesini bekleyecektir:

?- _

Yardım

İlk ve en önemli komutumuz olan yardım komutu ile başlayabiliriz.

?- help(help).

Bu komut, X11 ekranında, yardım dokümanını görüntüleyecektir. Basitçe herhangi bir komut hakkında bilgi alınmak istendiğinde bu komutu help fonksiyonuna parametre olarak vermek yeterlidir. Yukarıdaki kullanımda help komutunun kendisi için yardım alınmıştır.

Çıkış

Prolog komut satırından çıkmak için

?- halt.

Yazılması yeterlidir. Bu komut programı sonlandıracaktır.

Basit Kaziyeler

Aşağıdaki komutları PROLOG üzerinde çalıştıralım ve ardından burada yapılan işlemleri yorumlayalım.

Sistemimizde kayıtlı olan bir dosyayı program tarafından açıp çalıştırılır bir şekilde yüklemek için dosya ismi köşeli parantezler içerisinde verilmelidir:

?- [‘ilkdosya.pl’].

Yukarıda, bilgisayarımızda bulunan “ilkdosya.pl” isimli dosyayı sisteme tanıtarak yükledik. Bu dosyada bulunan tanımlar da otomatik olarak yüklenmiş ve sorgulanmaya / çalışmaya hazır hale getirilmiş olacaktır. Ayrıca bu dosyada bulunan genel hatalar, yükleme sırasında ekrana basılır.

PROLOG ile Faktöriyel Kodu

PROLOG dili, yapısal olarak özyineli (recursive) bir yapıdadır ve döngülerin yerine özyineli fonksiyon (recursive function) kullanılması gerekir. Bu kullanımı göreceğimiz en basit uygulamalardan birisi olan faktöriyel kodunu yazıp kodlamaya çalışalım.

Herhangi bir editör açılarak (ben tercihen vi kullanıyorum, siz de istediğiniz bir editör ile dosyayı açıp içeriğini ) aşağıdaki şekilde yazabilirsiniz:

factorial(0,1).      

factorial(A,B) :- 

             A > 0,

             C is A-1,

            factorial(C,D),

            B is A*D. 

Ardından aşağıdaki şekilde dosyamızı sisteme yükleyelim:

?- [‘ilkdosya.pl’].

% ilkdosya.pl compiled 0.00 sec, 732 bytes

true.

 

Komut satırında dosyamızın yüklendiği ve yükleme süresi ve dosya boyutu gösterilmektedir. Son satırda yer alan true bilgisine kadar bir hata bulunmamış olması, dosyamızda bir hata olmadığını gösterir. Şimdi artık ilk fonksiyonumuzu kullanmaya başlayabiliriz.

?- factorial(5,X).

X = 120 ;

false.

 

Komut satırında, factorial(5,X) komutu verilerek, 5! Değerinin X değişkenine döndürülmesi istenmiştir. Burada öğrenilen birkaç önemli noktayı belirtelim. Birincisi X ile gösterilen değer bir değişkendir ve PROLOG dünyasında buna unbounded variable (bağlanmamış değişken) ismi verilir. Basitçe Prolog kodlarındaki bütün büyük harf ile başlayan ifadeler birer değişkendir ve ayrıca bir değişken tanımı yapılmaz. İkinci bir nokta, Prolog dilinde kod yazılırken girilen her satır bir emirdir ( declaration) ve yapısal olarak Prolog dili, haber mantığını (predicate calculus) barındırır. Buna göre yüklü olan dosyada bulunan komutlar yukarıdan aşağıya doğru çalıştırılırken üstte bulunan satır, alttakine gore öncelikli olur ve aynı zamanda birden fazla satırda emirin tanımlanması durumunda, sırasıyla bu emirler işlenir.

Örneğin yukarıdaki kodda, ilk satırda bulunan factorial (0,1). İfadesi, 0! = 1 anlamındadır ve bir şekilde birisi bize sıfır faktöriyeli sorarsa, ikinci değer olarak 1 sonucunu döndürmeyi gerektirir.

İkinci satırdan sonra başlayan tanımda ise, sırasıyla A>0 kontrolü yapılmış, ardından C değişkenine değer olarak A-1 değeri konmuş ve yeni bulunan C değerinin faktöriyeli hesaplanarak, B sonucuna hesaplanan bu C faktöriyel değeri ile A’nın çarpımı eklenmiştir.

Yukarıdaki şekilde kodumuzu ilkdosya.pl  dosyasına yazıp kaydettikten sonra prolog komut satırında dosyamızı yükleyip çalıştırabiliriz:

 

Yukarıda görüldüğü üzere faktöriyel kodumuz çalışmış ve sonucu doğru şekilde bulmuştur.

Kodun çalışmasını takip etmek için trace komutu kullanılabilir. Basitçe komut satırında:

trace.

Yazıldıktan sonra çalışmaya başlar ve bu çalışmadan sonra çağrılan fonksiyonların detayları ekrana basılır:

Görüldüğü üzere factorial fonksiyonumuzun her adımı ekrana basılmıştır.

Hanoi Kuleleri (Towers of Hanoi)

İkinci bir uygulama olarak çok klasik bilgisayar bilimleri problemlerinden olan Hanoi Kulelerini ( tower of hanoi ) kodlamaya çalışalım.

Oyunun kuralı gayet basit. Başlangıçta bir çubukta dizili olan bütün diskler her adımda tek bir disk hareket ettirerek diğer iki çubuktan birisine taşınacaktır. Bu taşıma işlemleri sırasında büyük bir disk, küçük olan bir diskin üzerine gelmeyecektir.

Ayrıca oyunun internetten oynan bir denemesi için daha önce hazırladığım aşağıdaki ödev sayfasına bakabilirsiniz:

http://www.sadievrenseker.com/c/odev5.html

Problemin çözümünde kullanacağımız kod aşağıdaki şekildedir:

SADIs-MacBook-Air:prolog sadievrenseker$ vi hanoi.pl

oyna(1,X,Y,_) :-

    write(X),

    write(‘ en üstteki diskini ‘),

    write(Y),

    write(‘ oynat ‘),

    nl.

oyna(N,X,Y,Z) :-

    N>1,

    M is N-1,

    oyna(M,X,Z,Y),

    oyna(1,X,Y,_),

    oyna(M,Z,Y,X).

Kod örneği yukarıda verilmiştir. Kodumuzun çalışmasını görüp ardından nasıl çalıştığını açıklamaya geçebiliriz.

 

?- oyna(4,a,b,c).

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

a en üstteki diskini c oynat

b en üstteki diskini a oynat

b en üstteki diskini c oynat

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

c en üstteki diskini a oynat

b en üstteki diskini a oynat

c en üstteki diskini b oynat

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

true .

?-

Yukarıdaki çalışmadan da görüldüğü üzere ilk baştaki 4 diskin dizili olduğu a çubuğundan bütün diskler sırasıyla b çubuğuna taşınmıştır.

Kodumuz, doğru sıra ile oynama yaklaşımı ile kodlanmıştır. Hanoi kulelerinin farklı çözümleri bulunur. Örneğin geri izleme algoritması (backtracking) kullanarak kaba kuvvetle (brute force) bütün ihtimallerin denendiği ve başarısızlık olması halinde en son iyi duruma geri dönen yaklaşımları kodlamak da mümkündür.

Bizim kodlamamızda ise her seferinde doğru çubuktan doğru diskin oynatılması esası kullanılmıştı. Bu yüzden hiç geri oynama veya yapılan hamleden vaz geçme olmamıştır.

Bu oynama esasını daha iyi anlatabilmek için daha ufak bir örnek üzerinden çalışmayı gösterelim :

?- oyna(2,a,b,c).

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

true

 

Görüldüğü üzere iki disklik bir dizilimde, c çubuğu geçici olarak kullanılmakta, esas büyük diskin b çubuğuna oynanması sırasında, küçük diskleri depolamak için kullanılmaktadır.

Bu durum disk sayısı artsa da değişmez. En büyük diskin a çubuğundan b çubuğuna oynanması sırasında,  diğer bütün küçük diskleri depolamak için c çubuğunu kullanırız. Buradan anlaşılacağı üzere ikinci büyük diskin c çubuğuna oynaması gerekir. Bunun için de b çubuğunu geçici depolama için kullanırız. Bu yaklaşım en büyük diskten en küçüğüne kadar aynı mantıkla işleyerek devam eder.

8 Vezir Problemi (8 Queens Problem)

Yeni bir problem olarak klasik sorulardan birisi olan 8 vezir problemini ( eight queens problem) ele alalım. Problem basitçe bir satranç tahtasına 8 veziri, birbirini yemeden nasıl yerleştireceğimizdir.

 

Problemin çözümü olan PROLOG kodu aşağıda verilmiştir.

perm([X|Y],Z) :- perm(Y,W), birinial(X,Z,W).

perm([],[]).

 

birinial(X,[X|R],R).

birinial(X,[F|R],[F|S]) :- birinial(X,R,S).

 

cozum(P) :-

     perm([1,2,3,4,5,6,7,8],P),

     birlestir([1,2,3,4,5,6,7,8],P,S,D),

     hepsifarkli(S),

     hepsifarkli(D).

 

birlestir([X1|X],[Y1|Y],[S1|S],[D1|D]) :-

     S1 is X1 +Y1,

     D1 is X1 – Y1,

     birlestir(X,Y,S,D).

birlestir([],[],[],[]).

 

hepsifarkli([X|Y]) :-  +member(X,Y), hepsifarkli(Y).

hepsifarkli([X]).

 

Kodun çalışan örneği aşağıdaki şekildedir:

?- cozum(P).

P = [5, 2, 6, 1, 7, 4, 8, 3] ;

P = [6, 3, 5, 7, 1, 4, 2, 8] ;

P = [6, 4, 7, 1, 3, 5, 2, 8] ;

P = [3, 6, 2, 7, 5, 1, 8, 4] ;

P = [6, 3, 1, 7, 5, 8, 2, 4] ;

P = [6, 2, 7, 1, 3, 5, 8, 4] ;

P = [6, 4, 7, 1, 8, 2, 5, 3] ;

P = [3, 6, 2, 7, 1, 4, 8, 5] ;

P = [6, 3, 7, 2, 4, 8, 1, 5] ;

…

 

Yukarıdaki örneklerde görüldüğü üzere her kolon için, o kolondaki kaçıncı satıra vezir yerleştirilebileceği ve bu yerleştirme işlemine göre bütün kuralları sağlayan bir dizilimin nasıl elde edileceği listelenmiştir. Problemin birden fazla çözümü olduğu için her satır, çözümlerden birisini göstermektedir. Örneğin ilk çözüm satırını ele alırsak, aşağıdaki gibi bir satranç tahtası elde ederiz.

 

P = [5, 2, 6, 1, 7, 4, 8, 3] ;

Kodda, kabaca bütün ihtimalleri deneyen bir permütasyon algoritması geliştirilmiştir. Ardından koşulların sağlanıp sağlanmadığı kontrol edilmiş ve buna göre koşulları sağlayan ihtimaller sonuç olarak döndürülmüştür.

Algoritma, bir arama algoritması (search algorithm) şeklinde probleme yaklaştığı için, problemin çözümü sırasındaki bütün ihtimaller sadece bir kere denenecek ve denenen bir ihtimal tekrar etmeyecektir. Bu deneme sırası, permütasyon fonksiyonu ile sağlanır.