Declarative Programlamaya Giriş - 2 / Prolog'da Recursive Tanımlar

October 2021 · 3 minute read

Bence prolog’un zorlaştıĝı yerler birazdan girişeceĝim "recursive"-kurallar.

Diĝer programlama dillerinde recursion’u görüp sevmediyseniz veya zor geldiyse o ön yargınızı bir kenara bırakın. Biz prolog yazıyoruz ve recursion prolog’un ve declarative dillerin en temel silahlarındandır.

"recursive" demek kendine atıfta bulunan demek.

Mesela "GNU/Linux"taki GNU kısaltmasının açılımı "GNU (is) Not Unix" (GNU Unix Degildir).

Bu bölümü prolog öĝrenme niyetiyle okuyorsanız kenardan https://swish.swi-prolog.org 'i açıp alıştırma yapmanızı öneririm.

Recursive Kural Tanımlama

Recursive kuralları yine aile ilişkileri uzerinden örneklendirelim. Bir aile aĝacını, bir de bu grafiĝe denk gelen prolog kurallarını yazayım:

"muhsin"den "pelin"e ok gitmesi demek muhsin pelin’in evebeyn’i demek.

prolog’da iki aile
evebeyn(murat, muhsin).
evebeyn(gaye, muhsin).
evebeyn(muhsin, pelin).
evebeyn(zeynep, pelin).
evebeyn(pelin, fisun).
evebeyn(melih, fisun).
evebeyn(gokhan, zeynep).
evebeyn(guzide, zeynep).
evebeyn(deniz, melih).
evebeyn(eren, melih).
evebeyn(mehmet, deniz).
evebeyn(omer, eren).
evebeyn(tugba, eren).
evebeyn(irem, deniz).

ve ben bir kişinin bir başkasının soyundan gelip gelmediĝine bakan bir kural yazayım:

akraba(A, B)
ata(A, B) :- evebeyn(A, B).
ata(A, B) :- ata(A, C), evebeyn(C, B).

Sorularımızı soralım:

?-
?- ata(pelin, fisun). (1)

YES

?- ata(muhsin, fisun). (2)

YES

?- ata(murat, fisun). (3)

YES
1 A = murat, B = muhsin için; birinci kural (ata(A, B) :- evebeyn(A, B)) bu soruyu cevaplıyor
2 A = murat C = muhsin ve B = pelin ile ikinci kural (ata(A, B) :- ata(A, C), evebeyn(C, B) bu soruyu cevaplıyor
3 ata(murat, pelin)in doĝru olduğunu az evvel gosterdik. evebeyn(pelin, fisun) olduĝuna göre bu ata(murat, pelin) sorusunu da ikinci kural ile cevaplamış olduk.

ata(A, B) :- ata(A, C), evebeyn(C, B). tipindeki bir kurala recursive kural deniyor: ata kuralı kendini yine ata kuralı cinsinden tanımlamış.

Listeler

meyve(elma). yazarak " elma bir meyvedir" demiştik. Sonra da meyve(elma) sorusunu sorunca YES cevabı almıştık.

Diyelim ki benim elimde {elma, armut, patates, muz} şeklinde bir liste var ve bunların hepsinin meyve olup olmadıĝını sormak istiyorum. N’apacaĝız?

Kurallar

meyve(elma).
meyve(armut).
meyve(muz).

sebze(havuc).
sebze(patates).

Akla gelen ilk çözüm, hepsini tek tek sormak:

?-
?- meyve(elma).

YES

?- meyve(armut).

YES

?- meyve(patates).

YES

?- meyve(muz).

YES

Ama ben hepsini tek bir soru olarak sormak istiyorum. Bunun için bir liste tanımlayabilmem lazım ki meyveler(…​) deyip …​ gelen yere bu listeyi yazabileyim. meyveler(…​) de bu listedeki her şey meyve mi diye bakıp cevap versin.

Bunun için işe yarayan ama ilginç görünen şu gösterimi seçtim: elma(armut(patates(muz)))). . Bunu yazınca sırayla elma, armut, patates, muz kelimelerinden oluşan bir liste tanımlıyor olayım.

Yani;

  • {x1, x2, x3} listesini x1( x2( x3 ) ) olarak yazacaĝım,

  • {x1, x2} listesi x1( x2 ) olarak yazılacak,

  • sadece bir elemani olan {x1} listesi x1 olarak yazılacak,

  • boş bir liste tanımlayamıyoruz şu an :)

Yani ben sorgumu meyveler( elma( armut( patates( muz ) ) ) ) olarak yazacaĝım. Buna cevap verecek bi meyveler kuralı tanımlamam lazım önce:

verilen listedeki her şeyin meyve olup olmadıĝını cevaplayacak kural
meyveler(X) :- meyve(X). (1)
meyveler(X(Y)) :- meyve(X), meyveler(Y). (2)

  1. Ben meyveler(elma(armut(muz))) diye bir soru sorunca X = elma Y = armut(muz) ise 2’nci kurala denk gelecek. meyve(elma) kuralı mevcut, peki meyveler(armut(muz)) var mı?

  2. meyveler(armut(muz)) sorusu X = armut Y = muz ise 2’nci kurala denk gelecek. meyve(armut) diye bir kural mevcut, peki meyveler(muz) var mı?

  3. meyveler(muz) sorusu X = muz için 1’nci kurala denk gelecek. Bu kural ise meyve(muz) ise doĝru, ki meyve(muz) diye bir kural da zaten var. O zaman meyveler(muz) doĝruymuş. Yani meyveler(armut(muz)) de doĝruymuş. Yani meyveler(elma(armut(muz))) de doĝruymuş.

Deneyelim:

?-
?- meyveler(elma(armut)).

YES

?- meyveler(armut).

YES

?- meyveler(patates).

NO

?- meyveler(muz(armut(patates))).

NO

Ne Öĝrendik?

demek ki parantezleri kural tanımlarken veya soru sorarken de kullanabiliyormuşuz. Yeter ki bizim girdiĝimiz parantezli biçime denk gelen kurallar mevcut olsun.

Bu biçimdeki iç içe yazılan listelere Linked-List diyorlar

Devamı

Bir sonraki prolog yazısında bu yeni kural tanımlama biçimini kendi sayı sistemimizi kurarken kullanacaĝız.

Bir bilgisayara "3 + 5" dediĝimizde ne bilgisayar 3 ne demek, 5 ne demek, e peki + ne demek biliyor. Peki nasıl oluyor da biliyor? Bilmeseydi bunun nasıl üstesinden geliriz?

Bu soruların cevabı olan bir yazı.

Görüşmek üzere…​