31 Ocak 2012 Salı

Doğrusal Veri Kapları

Bu yazımızda, Veri Kapları Çerçevesi'nce (VKÇ) desteklenen doğrusal veri yapılarına değineceğiz. Bunu yaparken izleyeceğimiz yöntem, söz konusu veri yapılarının ortak özelliklerini anlattığımız giriş bölümünü takiben, anılan kategoriye giren kapları en geniş anlamda temsil eden genel liste veri yapısının desteklediği arayüzleri açıklamak ve kapların doğrusallaştırılmaları sonrasında ardışık erişimli görüntülerini sağlayarak dolaşılmasını olanaklı kılan gezicilere bakmak olacak. Yazımızın devamında ise, değişik doğrusal yapıların farklı gerçekleştirimlerine göz atarak işimizi bitireceğiz.


Giriş


Doğrusal veri yapıları, eleman ekleme, silme ve güncelleme işlemlerinin hangi sırada uygulandığının bilinmesi durumunda, elemanların nasıl sıralanacağının bilindiği kaplardır. Örnek olarak, 1, 2 ve 3 sayılarının bir genel listenin, sırasıyla, başına, sonuna ve başına eklendikten sonra elde edilen kaptan ikinci elemanın silindiğini düşünün. Bu işlemlerin sonrasında listemiz, ne tür bir gerçekleştirim kullanılırsa kullanılsın, [3, 2] sıralamasıyla gezilecektir. Halbuki, küme veya eşlemlerde elde edilecek sıralama gerçekleştirime bağlı olarak oluşacak ve dolayısıyla kestirilemeyecektir.

Genel Liste Arayüzü: java.util.List


Doğrusal veri yapılarını en geniş anlamda temsil eden soyut veri yapısı genel listedir. VKÇ'deki List arayüzü ile karşılanan bu yapı, gerçekleştirim biçiminden bağımsız olarak bir genel listenin desteklemesi beklenen işlemleri tanımlar. Yani, ister dizi gibi doğrudan erişimli bir yapı kullanılarak gerçekleştirilsin isterse bağlaçlı bir yapı kullanılarak, tüm genel listeler List arayüzündeki işlemleri desteklemek zorundadır.


Collection'dan kalıtlanmak suretiyle List arayüzünde gözüken iletilerin başında, equals ve hashCode gelir. Bu iletilerin List arayüzüne konulmuş olmasını başta yadırgayabilirsiniz. Ne de olsa, tüm sınıfların [dolayısıyla List arayüzünü gerçekleştirecek sınıfların da] kalıtladığı Object sınıfında bu iletilere dair gerçekleştirimler sağlanmaktadır. Ancak, buradaki amaç gerçekleştirimciye bir hatırlatma yaparak onu uyarmaktır; tanımlayıcıları List arayüzünü gerçekleştirmek isteyenlere şunu demektedirler:
Tutacakları karşılaştırmak yoluyla işini gören Object sınıfındaki equals metodu, muhtemelen senin işine gelmeyecektir. Ne de olsa, bu metot eşitlik denetimi yerine aynılık denetimi yapar. Bunun bir sonucu olarak, iki listenin eşit olması ancak ve ancak aynı olmaları durumunda mümkün olacaktır; eşit içeriğe sahip iki farklı liste eşitsiz ilan edilecektir. Dolayısıyla, sen iyisi mi, equals iletisini gerçekleştirmeyi bir daha düşün. Ha bu arada; hashCode iletisini de gözden geçirmeyi unutma. Malum, birbirine eşit farklı nesnelerin kıyım değerleri de eşit olmalıdır. Bu koşulu sağlayabilmenin yolu ise hashCode ile equals'ı birlikte ele almaktan geçer. Çünkü, Object sınıfındaki equals metodunu ezip de hashCode metodunu ezmezsen, eşit kapların farklı kıyım değerleri üretmesi durumu ortadan kalkmaz.
List arayüzündeki iletilerin çoğu VKÇ'yi daha önceden kullanmış olanlara tanıdık gelecektir. Bunun başlıca sebebi, VKÇ'de desteklenen kapların bir standardizasyon çabası kapsamında birlikte ele alınmış olmasıdır.1 Doğal olarak, aynı işlemler için olabildiğince aynı ileti adları seçilmeye çalışılmış ve ilintili işlemler kategorizasyon amacıyla aynı arayüze konulmuştur. Örneğin, ne tür bir kap olursa olsun, isEmpty hedef nesnenin boş olup olmadığını denetlerken size kaç eleman içerdiğini döndürür. Benzer bir şekilde, ilişkisel olmayan veri yapıları (genel liste, kuyruk, yığıt, çift-uçlu kuyruk, küme) Collection arayüzünde belirlenen işlevselliği paylaşırlar. Mesela, ister Vector olsun isterse TreeSet, bir nesnenin hedef kapta olup olmadığı contains iletisi ile sorgulanabilir; hedef kabın sonuna add ile eleman eklenirken, hedef kaptan verilen bir nesneye eşit ilk elemanın silinmesi remove ile sağlanır. Bunlara paralel olarak, containsAll, addAll ve removeAll/retainAll iletileri, sırasıyla, sorgulama, sona ekleme ve silme işlemlerini kendilerine geçirilen kapta var olan tüm nesneleri dikkate alarak yerine getirirler. clear iletisi ise, hedef kabın tüm elemenlarını siler.

List arayüzünün Collection'dan kalıtladığı diğer iletiler hedef kabın dizi şeklindeki görüntüsünü döndüren toArray iletileridir. Kap içeriğini baştan sona dolaşılma sıralarını koruyacak şekilde diziye kopyalayan iletilerden argümansız olanı, sonucu Object dizisi olarak döndürürken, kopyalamanın yapılacağı dizinin bileşen türünü argümanındaki dizinin bileşen türünü belirleyen tür argümanıyla alan ikinci uyarlama, sonucu dönüş değerinin yanısıra, yeterli yere sahip olması durumunda, argümanda geçirilen dizinin içinde de döndürür. Argümandaki dizinin yeterli yere sahip olması halinde, dönüş değeri için ikinci bir dizi yaratılmayacak, aynı dizi nesnesi paylaştırılacaktır.

Üst arayüzlerden kalıtlanmayıp List arayüzünün eklediği doğrusal kaplara özel tüm iletiler, kendilerine sağlanan indis değerlerini kullanarak ya da sonuçlarında indis değeri döndürerek işlerini görürler. Bunlardan get/set çifti, dizi erişim işleci ([]) görevini görür: get argümanında sağlanan indisteki elemanı döndürürken, set belirtilen konumdaki elemanı ikinci argümanındaki yeni değerle güncelledikten sonra söz konusu konumdaki eski değeri döndürür. get'in tersi olarak da görülebilecek indexOf ve lastIndexOf iletileri ise, contains iletisinin boolean yerine sorgulanan nesnenin, sırasıyla, kap içindeki ilk ve son geçiş yerlerini döndüren uyarlamaları olarak düşünülebilir. Argümandaki nesnenin kap içinde bulunmaması halinde her iki ileti de -1 döndürecektir.

List arayüzüne özel add, addAll ve remove iletilerinin yukarıda anılan adaşlarından şöyle bir farkı vardır: ekleme kap sonu yerine sağlanan ekstra argümanla belirtilen konuma yapılırken, silme nesne-eleman eşitliği denetlenerek bulunan konumu değil argümandaki indisin gösterdiği konumu etkiler.

Değineceğimiz son ileti, ilk başta göründüğünden çok daha hünerli olan subList. Hedef kabın argümanlar ile sınırlanan [kapalı-açık] dilimini bir List görüntüsü olarak döndüren bu ileti, dilim işlemlerinin gerçekleştirilmesini kolaylaştırır. İstersek, bir nesnenin kabımızın belirli bir diliminde var olup olmadığını sorgulayabiliriz; istersek, aşağıda olduğu gibi, kabımızın bir bölümünü silebiliriz.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
...
  List<Integer> ls = new LinkedList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  ls.subList(3, 7).clear(); // ls → [0, 1, 2, 7, 8, 9]

Geziciler: java.util.Iterator ve java.util.ListIterator


List arayüzünün Collection vasıtasıyla Iterable'dan kalıtladığı düşünüldüğünde, liste elemanlarının, tıpkı diziler gibi, gezici for döngüsü ile dolaşılabileceği görülecektir. Yani, gezici nesne yaratıp başa konuşlandıktan sonra hasNext ve next iletilerinden yararlanarak dolaşmaktansa, listemizi aşağıdaki gibi dolaşmak da mümkündür ve kodun anlaşılabilirliğini artırmak adına bu yöntem yeğlenmelidir.
import java.util.List;
import java.util.ArrayList;
...
  List<ElmTürü> ls = new ArrayList<>();
  ... // ls'yi doldur]
  for (ElmTürü elm : ls) { ... }
Ön-derleme sonrasında yukarıdaki for döngüsü J2SE 5.0 öncesinde programcının yazmak zorunda kaldığı şu şablon koda çevrilecektir. Dolayısıyla, gezici for döngüsünün, dolaşılabilir kapların kullanımında yararlanılan sözdizimsel bir kolaylık olduğunu söyleyebiliriz.
import java.util.Iterator;
...
  for (Iterator<ElmTürü> gzc = ls.iterator(); gzc.hasNext();) {
    ElmTürü elm = gzc.next();
    ...
  }
Gezicinin soyutlanarak doğrudan kullanımının önüne geçilmesi nedeniyle, gezici for döngüsünün gövdesinde kap içeriğinin güncellenmesi olanaksızdır; dolaşma esnasında kabın güncellenebilmesi için gezicinin bizzat programcı tarafından yaratılması gerekir. Bu durumda, geziciye gönderilecek bir remove iletisi, next ile döndürülen son elemanı silecektir.
...
  for (Iterator<ElmTürü> gzc = ls.iterator(); gzc.hasNext();) {
    ElmTürü elm = gzc.next();
    if (...) gzc.remove();
    ...
  }
iterator'ın döndürdüğü gezicinin anılan üç iletiye sınırlı olması bazen kısıtlayıcı olabilir. Doğru ya, ardışık elemanların ilişkilerini görebilmek için kabımız içinde ileriye doğru olduğu gibi geriye doğru da dolaşmak isteyebiliriz; gezme sırasında elemanları silmek isteyebileceğimiz gibi güncellemek, öncesine veya sonrasına yeni bir değer eklemek isteyebiliriz. Bu takdirde, List tutacağı aracılığıyla gönderilebilecek listIterator iletisinin kullanımı düşünülebilir. Hedef kabın ListIterator arayüzü tutacağı ile kullandırılan bir görüntüsünü döndüren bu ileti, geziciyi kabın başına veya argümanla belirtilen konuma konuşlandırabilir. İlkleme sonrasında, gezicinin sağladığı görüntü kullanılarak altyapıdaki kap ileri/geri yönde dolaşılabilir, uygun görülen yerlere yeni eleman eklenebildiği gibi, var olan elemanlar değiştirilebilir veya silinebilir. Bu noktada, yıkıcı (güncelleyici) işlemlerin etkisini altyapıdaki kap üzerinde göstereceği unutulmamalıdır. Örneğin, aşağıdaki kod parçasında gzc ls ile gösterilen kabın ortasına konuşlanmakta ve başa doğru dolaşırken değeri 3 olan elemanları 33 olacak şekilde güncellemektedir.
import java.util.ListIterator;
...
  List<Integer> ls = new ArrayList<>();
  // ls'yi doldur...
  int orta = ls.size / 2;
  for (ListIterator<Integer> gzc = ls.listIterator(orta); gzc.hasPrevious();) {
    int elm = gzc.previous(); // Derleyici Integer→int dönüşümünü yapıyor
    if (elm == 3) gzc.set(33);
    ...
  }
Kabın paylaşılması nedeniyle, yapılan değişikliklerin hem liste hem de gezici tutacağı ile görüleceği unutulmamalıdır. Bu noktanın gözden kaçırılması, çok-izlekli programlarda—mesela, kabın bir izlekte liste tutacağı yoluyla bir diğerinde ise gezici tutacağıyla değiştirildiği durumlarda—soruna yol açabilir.

Iterator arayüzünden kalıtlayan ListIterator aşağıdaki tabloda verilen iletileri içerir. Eklemenin yapılacağı nokta aynı kapıya çıkan iki şekilde tanımlanabilir: i) hasNext'in false döndürmesi durumunda listenin sonuna, aksi takdirde next ile döndürülecek elemanın öncesine, ii) hasPrevious'ın false döndürmesi durumunda listenin başına, aksi takdirde previous ile döndürülecek elemanın sonrasına. Ayrıca, remove ve set iletilerinin en son okunmuş olanın dışında bir elemanı etkilemeyeceği ve bu iletilerin add veya bir diğer remove iletisi sonrasında bir başka okuma yapılmaksızın kullanılamayacağı unutulmamalıdır. Aksi takdirde, gönderi IllegalStateException ayrıksı durumunun firlatılmasıyla sona erecektir.

ListIterator arayüzü
İletiİşlev
hasNextListe sonu sorgulama
nextBir sonraki eleman
removeEn son okunan elemanı silme
nextIndexBir sonraki elemanın indisi
hasPreviousListe başı sorgulama
previousBir önceki eleman
previousIndexBir önceki elemanın indisi
addEkleme
setEn son okunan elemanı güncelleme

Gezici kullanımı sırasında şu husus akılda tutulmalıdır: geziciler dolaştırdıkları listenin değişebilirlik, çok/tek-izleklilik ve tür güvenlilik gibi özelliklerini korur. Buna göre, aşağıdaki kod parçasında, lsGzc vasıtasıyla değişikliğe izin verilirken, sabitLsGzc'nin aynı kabı değiştirmek amacıyla kullanılması UnsupportedOperationException ayrıksı durumuna neden olacaktır.
import java.util.Collections;
...
  List<Integer> ls = new ArrayList<>();
  // ls'yi doldur...
  List<Integer> sabitLs = Collections.unmodifiableList(ls);
  ...
  ListIterator<Integer> lsGzc = ls.listIterator();
  ListIterator<Integer> sabitLsGzc = sabitLs.listIterator();
java.util.Enumeration arayüzüne değinerek geziciler bahsini kapatalım. İşlevsel olarak Iterator arayüzünün silme özelliği barındırmayan uyarlaması olarak düşünülebilecek bu arayüzün kullanımından kaçınılmalıdır. Daha önceden tanımlanmış olup ıslah edilerek VKÇ'ye katılan Hashtable ve Vector gibi kapların bu arayüzün tutacağı ile görüntü döndüren iletileri yerine, eşdeğer bir diğer iletinin kullanılması yerinde olacaktır. Örneğin, Vector nesnelerine elements yerine iterator iletisi gönderilmelidir. Bu, VKÇ ile birlikte tanımlanan Vector benzeri (ArrayList gibi) kapların elements'i desteklemeyip iterator'ı desteklemesi nedeniyle kodun yeniden kullanılabilirliği adına daha doğru olacaktır.

Genel Liste Gerçekleştirimleri


Altyapıda yararlanılan kabın erişim özelliğine bağlı olarak List arayüzünü gerçekleştiren sınıflar, doğrudan erişimli ve ardışık erişimli olmak üzere ikiye ayrılırlar. Bu ayrım, kimi iletilerin performanslarını etkilemesi ve desteklenebilecek ekstra iletiler nedeniyle, söz konusu kapların kullanıldıkları programların çalışma hızını ve anlaşılabilirliğini etkileyecektir; hangi somut sınıfın kullanılacağına dair yapılan seçimde bu nokta göz önünde bulundurulmalıdır. Kodun yeniden kullanılabilirliğini artırmak ve yapılacak muhtemel değişikliklerin etkisini en aza indirmek adına, tutacak türü olarak arayüz ve soyut sınıf adları kullanmaya çalışılmalı, somut sınıfların kullanımı nesne yaratma noktalarına sınırlı tutulmalıdır. Tercih edilen somut sınıfın kesinleşmesinden sonra bile arayüzlerde listelenen iletiler sınıfa özel eşdeğer iletilere yeğlenmeli, sınıfa özel iletiler ancak ek getirileri olmaları durumunda seçilmelidir. Örneğin, Vector'de karar kılınsa dahi List arayüzündeki get kullanılmalıdır, Vector sınıfına özel elementAt değil. Buna karşılık, subList ve tek argümanlı indexOf iletisinin birlikte kullanımı yerine iki argümanlı indexOf iletisinin kullanımı daha anlaşılabilir olması ve [marjinal] hız farkı nedeniyle tercih edilebilir.
adlar.indexOf("Ali", 5); // adlar.sublist(5, adlar.size()).indexOf("Ali") 
Java VKÇ, gerçekleştirimcinin işini kolaylaştırmak amacıyla somut sınıfların üzerine inşa edileceği soyut sınıflar sağlar. Doğrudan erişimli bir altyapı üzerine oturtulan bir genel liste için bu soyut sınıf AbstractList iken, ardışık erişimli altyapı kullanarak aynı işe soyunanların doğru adresi, AbstractList'ten kalıtlayan AbstractSequentialList'tir. İskelet görevi gören bu sınıflar, yararlanılacak altyapının ayrıntılarına dair varsayımlarda bulunulamaması nedeniyle, kimi iletilere karşılık gerçekleştirim sağlamazken kimi iletiler için genel [ve yavaş] gerçekleştirimler sağlar. Dolayısıyla, VKÇ'ye yeni bir kap gerçekleştirimi eklemek isteyenler, soyut sınıflardan uygun olanından kalıtlayarak iskeleti ete büründürmelidir.

VKÇ'ye yeni bir kap gerçekleştirimi eklemek isteyenlerin sabit içeriklilik ve değişken uzunlukluluk özelliklerini destekleyip desteklememelerine bağlı olarak sorumlulukları da değişir. Örneğin, tüm doğrudan erişimli listeler get ve size iletilerine karşılık gelen metotları sağlamak zorundayken, listenin değişken içerikli olmasının istenmesi durumunda, AbstractList'te UnsupportedOperationException ayrıksı durumu fırlatacak şekilde gerçekleştirilen set ezilmelidir. Benzer şekilde, listenin değişken uzunluklu olması isteniyorsa, iki argümanlı add ve int argüman alan remove metotlarının da ezilmesi gerekir. Ardışık erişimli listelerin gerçekleştiriminde de aynı ayrım geçerlidir: AbstractSequentialList'ten kalıtlayıp size ve listIterator iletilerini gerçekleştirmesi beklenen geliştiriciler, listIterator'ın döndürdüğü gezicinin alacağı iletileri gerçekleştirirken sabit içeriklilik ve değişken uzunlukluluk özelliklerini hesaba katmalıdırlar. Ardışık erişimli listelerden sabit içerikli [ve dolayısıyla sabit uzunluklu] olanlar, ListIterator arayüzünde bulunan next, hasNext, nextIndex, previous, hasPrevious ve previousIndex için gerçekleştirim sağlamak zorundayken, diğer iletilerin gerçekleştiriminde UnsupportedOperationException döndürmelidirler. Buna karşılık, değişken içerikli, sabit uzunluklu listeler, anılan arayüzün add adlı iletisini de gerçekleştirmek durumundadır. Son olarak, değişken uzunluklu listeler, arayüzde bulunan tüm iletileri gerçekleştirmelidir.

Doğrudan Erişimli Listeler: java.util.ArrayList ve java.util.Vector


VKÇ'de doğrudan erişimli genel liste gerçekleştirimi sağlayan iki sınıf vardır: ArrayList ve Vector🔎. Diziden yararlanarak işini gören bu sınıflar arasında işlevsellik ve performans açısından pek fark yoktur. Ancak, yine de şu noktaların akılda tutulmasında yarar olacaktır:

  • Java'nın ilk uyarlamasından bu yana var olan Vector, diğer J2SE 1.2 öncesi kaplar gibi, çok-izlekli iken ArrayList tek-izleklidir. Dolayısıyla, ArrayList türlü kapların çok-izlekli bir programda kullanılması durumunda, farklı izleklerden eşzamanlı erişimin sebep olabileceği tutarsızlıkları önlemek adına bazı kod bölgelerinin synchronized bloğu içine alınarak çok-izlekli hale getirilmeleri gerekir. Buna karşılık, kamuya açık tüm metotları synchronized olan Vector sınıfının tek-izlekli veya erişim serileştirme gereksiniminin düşük olduğu çok-izlekli programlarda kullanılması, çalışma hızının gereksiz yere yavaşlamasına neden olacaktır. Bu gibi durumlarda, ArrayList türlü bir kabın kullanımı ve gerekli noktalarda Collections sınıfındaki synchronizedList metodu ile döndürülen görüntü üzerinde işlem yapılması da bir çözüm olarak hesaba katılmalıdır.2
  • Her iki sınıf da, eleman sayısının artmasını gerektirecek bir işlem sırasında sığanın otomatik olarak büyümesini sağlar. Ne var ki, Vector sınıfında ilişkin kabın yaratılması esnasında sağlanacak bir argüman ile sığa artımına müdahale edilebilirken, ArrayList sınıfında böyle bir olanak yoktur.

Yukarıda da söylediğimiz gibi, her iki sınıf da benzer performansa sahiptir. get, set, size, isEmpty, iterator ve listIterator iletileri sabit zamanlı performans sergilerler. Ayrıca, kabın sığa artımına ihtiyaç duyduğu durumlarda yaşanan düşüşe karşın, kap sonuna eleman ekleyen add iletisi de ortalamada sabit zamanlı bir performans gösterir. Buna karşılık, diğer iletilerin arama temelli olanları, kap içeriğini dolaşmak zorunluluğu nedeniyle doğrusal veya daha pahalı bir performans sergileyecektir.

Kısıtlı Listeler: java.util.PriorityQueue ve java.util.ArrayDeque


C'den başka programlama dili bilmeyenlerin yaydığı bir efsanedir: liste denince akla bağlaçlar, bağlaç denince ise göstericiler gelir. Eğer bu bedbahtlardansanız, olasıdır ki yazımızın bağlaçlı listelerle başlamamış olması sizi şaşırtmıştır. Size kötü bir haber daha verelim, genel liste arayüzünün bir altkümesine sınırlı işlevsellik sunan kısıtlı listelere değinmeden bağlaçlı listelere geçmeyeceğiz.

VKÇ'de desteklenen ve tür sıradüzeni aşağıda verilen kısıtlı liste çeşitlerini anımsayarak başlayalım. Üç temel işlemin de üst olarak nitelenen aynı liste ucunu etkilediği bir kısıtlı liste olan yığıt (İng., stack), herhangi bir noktada çıkarılacak (veya sorgulanılacak) ilk elemanın en son eklenen eleman olması nedeniyle son giren ilk çıkar listesi olarak da adlandırılır. Bir diğer kısıtlı liste, gerçek yaşamdaki aynı adlı kavramı temsil eden ve uygarlıktan nasibini almış herkesin takdir edeceği nedenlerden ötürü ilk giren ilk çıkar listesi olarak adlandırılan kuyruktur (İng., queue). Kuyruğun elemanları arasında bir sıralamanın istenmesi halinde—yani, kuyruğun belirli bir ölçüte göre oluşturulması istendiğinde—ekleme işlemi kuyruğun sonu yerine herhangi bir yerine yapılabilir. Böylesine kuyruklara, öncelikli kuyruk (İng., priority queue) denir. Son olarak, temel işlemlerin aynı listenin her iki ucuna da uygulanabildiği kısıtlı listelere çift-uçlu kuyruk adı verilir.


Yukarıdaki şeklin incelenmesi kuyruk ve yığıt yapılarının VKÇ tarafından desteklenmediği kanısını yaratabilir. Java uzmanı olanlarınız ise, aslında bu desteğin var olduğunu, sorunun şeklin eksik olmasında yattığını iddia edeceklerdir. Her iki görüşte de haklılık payı olduğunu, duruma daha sonra açıklık getirileceğini söyleyelim ve Queue arayüzünün açıklaması ile devam edelim. Collection'dan kalıtlayan bu arayüz, aynı işlemin istisnai durumlarda iki farklı biçimde davranması nedeniyle, aşağıdaki tabloda listelenen altı iletiyi içerir. Sabit uzunluklu, dolu bir kuyruğa add ile ekleme yapılması IllegalStateException ayrıksı durumuna neden olurken, aynı kuyruğa offer ile eleman eklenmeye çalışılması, C fonksiyonlarını andırırcasına, null değerinin döndürülmesine neden olacaktır. Sorgulama ve çıkarma işlemleri de boş bir kuyruğa uygulanmaları halinde benzer bir davranış sergileyecektir.

Kuyruk: İlk giren ilk çıkar listesi
İşlemİleti (Queue)Başarısızlıkta döndürülen değerDenk ileti (Deque)
EklemeaddIllegalStateExceptionaddLast
offerfalseofferLast
SorgulamaelementNoSuchElementExceptiongetFirst
peeknullpeekFirst
ÇıkarmaremoveNoSuchElementExceptionremoveFirst
pollnullpollFirst

Queue arayüzüne dayalı kuyruk gerçekleştirimini kolaylaştırmak amacıyla sağlanan AbstractQueue'dan kalıtlayan sınıflara baktığımızda, değişken uzunluklu öncelikli kuyruk yapısını ikili yığın (İng., binary heap) kullanarak gerçekleştiren PriorityQueue sınıfını görürüz. Dizi üzerine ikili ağaç benzeri bir yapı oturtarak işini gören bu gerçekleştirim stratejisi sayesinde, temel işlemlerden sorgulama sabit zamanda sonuç verirken, ekleme ve çıkarma logaritmik zaman almaktadır. Öncelikli kuyruğun eleman sayısını öğrenme, boşluk yüklemi ve gezici yaratma da sabit zamanda mümkün olmaktadır. Buna karşılık, geri kalan iletiler doğrusal zaman gerektirmektedir.

PriorityQueue sınıfının yapıcılarına bakıldığında iki nokta dikkat çeker. Öncelikle, değişken uzunluklu olması hasebiyle taşmaması için büyütülen kuyruklar, istenildiği takdirde yaratıldıkları noktada belirli bir ilk sığaya sahip olacak şekilde yaratılabilir. Kuyruğun eleman eklenerek büyümesi sırasında altyapıdaki dizinin büyütülmesinden kaynaklanacak performans kaybını azaltacak bu parametre, sabit uzunluklu kuyruklarda yer ve zaman kayıplarını sıfıra indirecektir. Dikkatimizi çeken ikinci husus, iki argümanlı yapıcıdaki ikinci argümanın Comparator türlü olmasının hatırlattığı ayrıntıdır: öncelikli kuyruk içine konulmak istenecek nesnelerin, hangi sınıftan olurlarsa olsunlar, karşılaştırılabilir olmaları gerekir. Durup düşünüldüğünde bu önkoşulun çok doğal olduğu görülecektir: karşılaştırılamayan nesneler sıraya dizilemezler!3 Dolayısıyla, nesnelerin Comparable arayüzünü gerçekleştiren bir sınıfa ait olması veya nesneleri karşılaştırmayı bilen bir karşılaştırıcı nesnenin fazladan sağlanması zorunludur.

Gelelim ortalıkta gözükmeyen yığıt ve kuyruk gerçekleştirimlerinin nerede olduklarına. Bunun için, çift-uçlu kuyruk yapısının tanımlandığı Deque arayüzünü gerçekleştiren ArrayDeque sınıfına bakmak yetecektir. Çünkü, VKÇ'de bir kabın yığıt veya kuyruk gibi davranması, bu yapılara uyumlu iletilerin ArrayDeque nesnelerine gönderilmesiyle sağlanır.4
import java.util.Deque;
import java.util.Queue;
import java.util.ArrayDeque;
...
  Deque<Integer> yığıt = new ArrayDeque<>();
  Queue<Integer> kuyruk = new ArrayDeque<>();
Örneğimizdeki asimetrik kullanım dikkatinizi çekmiştir: tutacak türü olarak, kuyruk için Queue arayüzü kullanılırken, yığıt için çok-uçlu kuyruğa dair Deque arayüzü kullanılmaktadır. Dolayısıyla, kuyruk adlı kap kuyruklara özel iletilerle kullanılacakken, yığıt'ın kullanımında seçtiğimiz tanımlayıcı adı aldatıcı olacaktır. Zira, söz konusu tutacak Deque arayüzünde tanımlı olan ve aşağıdaki tabloda sağlanan yığıt iletilerinin yanısıra diğer tüm iletilere de izin verecektir.

Yığıt: Son giren ilk çıkar listesi
İşlemİletiBaşarısızlıkta döndürülen değerDenk ileti
EklemepushIllegalStateExceptionaddFirst
falseofferFirst
SorgulamapeeknullpeekFirst
NoSuchElementExceptiongetFirst
ÇıkarmapopNoSuchElementExceptionremoveFirst
nullpollFirst

Bu noktada, bazılarınız, Java'nın ilk uyarlamasından bu yana var olan Stack sınıfı nerelerde, diye soruyor olabilir. Hemen yanıtlayalım: eskiden olduğu yerde, emrinize amade sizi bekliyor. Ama, sakın ola ki, sırf adı yığıt sözcüğünün İngilizce karşılığı olduğu için bu sınıfı kullanmanın daha iyi bir fikir olduğunu düşünmeyin. Çünkü, geliştiricilerin, muhtemelen işi aceleye getirmeleri nedeniyle, Vector sınıfından kalıtlayarak gerçekleştirdiği bu sınıf, yığıt kavramıyla ilgili ilgisiz çok sayıda iletiyi desteklemektedir. Mesela, aşağıdaki kod parçasında yaratılan kap, yığıta dair iletilerin yanısıra, Vector sınıfının desteklediği diğer iletileri de, doğrudan erişimliler dahil olmak üzere, itiraz etmeden kabul eder.
import java.util.Stack;
...
  Stack<Integer> yığıt = new Stack<>();
  // List arayüzündeki tüm iletiler yığıt'a gönderilebilir!
Geldiğimiz noktada, üç farklı kısıtlı liste için sağladığı destek ve söz konusu yapıların farklı terminoloji kullanması nedeniyle, Deque arayüzünü (ve gerçekleştirimcisi ArrayDeque sınıfını) anlamakta zorluk çekiyor olabilirsiniz; bazı işlemlerin istisnai durumlarda iki değişik şekilde tepki vermesi işi daha da kötüleştirebilir. Ancak ürkmeyin, aşağıdaki tablonun yorumu sizi işinizin düşündüğünüz kadar zor olmadığına inandıracaktır.

Çift-uçlu kuyruktan yararlanarak kuyruk ve yığıt
Denk iletiler
C tarzı dönüşAyrıksı durum
KuyrukEklemeaddaddLast
offerofferLast
SorgulamaelementgetFirst
peekpeekFirst
ÇıkarmaremoveremoveFirst
pollpollFirst
YığıtEklemepushofferFirstaddFirst
SorgulamapeekpeekFirstgetFirst
ÇıkarmapoppollFirstremoveFirst

Çift-uçlu kuyruklarda üç temel işlemin—ekleme, çıkarma (silme) ve sorgulama (göz atma)—kabın her iki ucuna da uygulanabileceğini hatırlatarak başlayalım. Söz konusu altı işlemin istisnai durumlarda farklı tepki veren iki ileti ile karşılandığı da düşünüldüğünde, yedi tanesi tablomuzun sağ kısmında yer alan on iki iletinin gizemi çözülür. Bunlara, temel işlemlerin yığıt ve kuyruk terminolojisindeki karşılıkları olan üçüncü sütunda listelenen dokuz iletiyi de eklersek, toplamda yirmi bir iletiyi buluruz. Collection'dan gelenler ve Deque'in geri kalan üç iletisi (descendingIterator, removeFirstOccurrence ve removeLastOccurrence) ile beraber düşünüldüğünde, bu sayı başta korkutucu gelebilir. Ancak, çift-uçlu kuyruğu ne şekilde kullanacağınıza karar vermenizle birlikte yirmi bir ileti aniden yığıt için üçe, kuyruk için üç veya altıya, çift-uçlu kuyruk içinse altı veya on ikiye düşecektir.

ArrayDeque dairesel arabellek (İng., circular buffer) şeklinde kullanılan bir dizi ile gerçekleştirim sağlar. Bu sayede, temel işlemlerin her iki uca uygulanmasına karşılık gelen tüm iletiler sabit zamanda işlerini bitirirler. Aynı nedenden ötürü, temel işlemlerin toptan uygulanmaları da eleman başına sabit bir maliyet sergileyecektir. Buna karşılık, kabın taranmasını gerektiren arama iletileri doğrusal zamanlı performansa sahiptirler. Son olarak, altyapıda kullanılan dizinin yetersiz sığaya sahip olduğunun görülmesi dizinin genişletilmesine neden olacağı için, ekleme iletilerinin nadiren de olsa bazen reklam edilenden düşük bir performans sergileyebileceği unutulmamalıdır. Bu duruma düşmemek için ArrayDeque nesnesini muhtemel kullanıma uygun bir sığa ile yaratmak yardımcı olacaktır.

Bağlaçlı Liste: java.util.LinkedList


VKÇ'nin genel liste gerçekleştirimi olarak sunduğu ikinci seçenek, List ve Deque arayüzlerini ardışık erişimli bir yapı kullanarak gerçekleştiren LinkedList sınıfıdır. Baş ve son düğümlerin tutacaklarını barındıran çift bağlaçlı bir yapıya sahip bu sınıfta ekleme ve çıkarma, liste içindeki bağlaçların güncellenmesiyle tamamlanır. Bunun doğal bir sonucu olarak, herhangi bir elemana erişmenin tek yolu, get/set gibi iletiler kullanılıyor olsa bile, ardışık erişimdir; istenen bir elemana erişilmesi için, söz konusu eleman öncesindeki/sonrasındaki tüm elemanların ziyaret edilmesi zorunludur. Dolayısıyla, doğrudan erişim üzerine kurulu ikili arama gibi algoritmalarda bu sınıf yerine ArrayList veya Vector gibi bir sınıfın kullanılması daha mantıklı olacaktır. Buna karşılık, araya eklemenin sık yapıldığı ve ardışık erişime mecbur olunan durumlarda—mesela, ekleme sıralaması (İng., insertion sort) algoritmasının gerçekleştiriminde—seçimin LinkedList'ten yana olması gerekir. Çünkü, bağlaçlı bir yapı kullanılarak gerçekleştirilen bir kabın ortasına yapılan eklemeler/çıkarmalar doğrudan erişimli kapların neden olduğu gibi kaydırmanın getireceği olumsuzluktan etkilenmez. Son olarak, kabın iki ucuna erişimin sabit maliyetli olması, size yığıt ve kuyruk gibi kısıtlı listeler için LinkedList'in çekici bir seçenek olduğunu düşündürebilir.
...
import java.util.LinkedList;
...
  Deque<Integer> yığıt = new Linked<>();
  Queue<Integer> kuyruk = new LinkedList<>();
Yukarıda sağlanan çözümün ArrayDeque kullanılarak sağlanan çözümle daha sağlıklı bir şekilde karşılaştırılabilmesi için, ArrayDeque'in altyapıda kullanılan dizinin boş konumları için maliyet ödetmesine karşılık, LinkedList'in her bir eleman için fazladan iki bağlaç tutmak zorunda olduğu unutulmamalıdır. ArrayDeque nesnesinin duruma uygun bir ilk sığaya sahip yaratılması imkanı ile birlikte ele alındığında, bu durumun temel işlemlerin zaman maliyetini marjinal de olsa ArrayDeque lehine çevirdiği görülecektir. Dolayısıyla, yığıt ve kuyruk kullanımı için ilk önerdiğimiz yöntemin daha doğru olduğu söylenebilir.


  1. VKÇ'nin ortaya konduğu J2SE 1.2 öncesinde tasarlanıp gerçekleştirilmiş olan veri kaplarının dokümantasyonunda iki noktayı kafa karıştırıcı bulabilirsiniz. [Islah edilerek çerçeveye oturtulması olanaksız gözüken] Dictionary ve Stack sınıflarını kullanmaktan kaçınılması tavsiye edilirken, Hashtable ve Vector sınıflarında tamamıyla aynı şeyi yapan farklı adlara sahip pek çok ileti çifti göze çarpar. Her iki durumda da sebep, VKÇ'nin ortaya koyduğu standart ve söz konusu sınıfların bu standarda uyumdaki başarısı(zlığı)dır. Programcı olarak bizim payımıza düşen ise, dokümantasyonda önerildiği gibi, ilk iki sınıf yerine önerilen seçeneklerden yararlanmak ve diğer iki sınıfta standartta bulunan ada sahip iletileri kullanmaktır. Böyle bir yaklaşım, yazdığımız kodun yeniden kullanılabilirliğini artıracaktır.
  2. Metotlarının synchronized ilan edilmiş olması, Vector sınıfını tamamıyla izlek güvenlikli kılmaz. Bu şekilde sağlanan güvence metotların teker teker kullanımlarına ilişkindir; Vector sınıfındaki iki veya daha fazla sayıda metodun aynı atomik işlemin parçası olarak icra edilmesini gerektiren durumlarda, iş yine programcıya düşecektir.
  3. Aslına bakarsanız, sıralanmak istenen verinin ikillerini 0 veya 1 olmasına göre gruplara ayırarak işini gören bazı algoritmalar karşılaştırma işleminden yararlanmazlar. Ne var ki, bu algoritmaların uygulanabilirliği bazı ilkel türlere kısıtlı olduğu için, bu istisna genelleştirilerek vardığımız yargıyı boşa çıkarmak için kullanılamaz.
  4. Aslına bakacak olursanız, ayrıcalıklı kuyruktan yararlanarak yığıt ve kuyruk displinine sahip kapların oluşturulması mümkündür. Bunun için yapılması gereken, elemanların ekleme zamanlarına dair bilgi içermeleri ve bu bilginin ayrıcalıklı kuyruğun sıralama ölçütü olarak kullanılmasıdır.

11 Ocak 2012 Çarşamba

Clojure, Java Platformunun Fonksiyonel Programlama Dili

Bu yazımızda, daha önceden fonksiyonel programlamaya aşık olup da JSM aleminde aşklarının karşılıksız kaldığını düşünenlerin yanıldığını anlatmaya çalışacağız: JSM'nin fonksiyonel programlama dillerinden Clojure'a (okunuş: Klojur) göz atacağız. Yeni bir programlama dili öğrenmek fikrinden korkanlarınızın içi rahat olsun, Common Lisp, Scheme gibi dilleri bilenlerde karşı konulmaz bir déjà vu hissi uyandıracak Lisp ailesinin bu genç üyesinin sıfırdan öğrenilmesi, anılan ailedeki dillerin yalın sözdizimi ve az sayıdaki kuralı nedeniyle pek fazla zorlayıcı olmayacak. Yeter ki, programlamanın aslında eğlenceli bir şey olabileceğine ve bir problemin birden çok farklı şekilde çözülebileceğine inanın.


Peki Ama, Neden Clojure?


Çok yerinde bir soru. Zira, Clojure arkasında büyük bir şirket veya programcı topluluğunun bulunduğu bir programlama dili değil. Ancak; Java, Scala🔎, Jython, JRuby, BeanShell🔎, Groovy, vd. gibi, Clojure da bir JSM dili: Java programlama dilinin kullanımına hazır olan tüm kitaplıklar Clojure kaynak kodu içinden de kullanılabilir; Clojure kaynak kodu istenecek olursa sınıf dosyasına derlenerek Java platformunun parçası haline getirilebilir. Ayrıca, bazı diğer özelliklerinin Clojure'u önümüzdeki yıllarda daha çekici kılacağını söylemek falcılık olmayacaktır. Dolayısıyla, Clojure'u elinizin tersiyle itmeden önce biraz daha düşünmenizde yarar var.

Clojure'un Lambda Hesaplama Kuramı (İng., Lambda Calculus) üzerine inşa edilmiş bir fonksiyonel programlama dili olduğunu söyleyerek başlayalım. Süslü kısmı aradan çıkararak ifade edecek olursak, problem çözümünün matematikteki karşılıklarına benzer bir şekilde ele alınan ve fonksiyon adı verilen altyordamlar yoluyla sağlandığını söyleyebiliriz; doğal olarak, problemlerin fonksiyonların bileştirilmesiyle çözüldüğü bu paradigmada birimsellik aracı olarak fonksiyonlar kullanılır. Birinci sınıf vatandaş olan fonksiyonlar, diğer fonksiyonlara argüman olarak geçirilip, fonksiyonlardan sonuç olarak döndürülebilir ve herhangi bir bileşke türlü değerin bileşeni olarak tutulabilirler. Yani, C'de fonksiyon göstericileri, Java'da arayüzler vasıtasıyla zahmetli bir şekilde, kısmen elde edilebilen bir şey, Clojure'da çok daha kapsamlı bir paketin parçası olarak bedavaya gelir.1 Bu, Google tarafından geliştirilmiş olup yoğun bir biçimde kullanılan ve Apache'nin Hadoop projesi vasıtasıyla özgür yazılım dünyasına kazandırdığı MapReduce adlı bulut hesaplama çerçevesinin önümüzdeki aylar, yıllar içinde karşınıza çıktığında işinizin daha kolay olacağı anlamını taşır. Çünkü, MapReduce kullanılarak üretilecek çözümler, fonksiyonel programlama dillerinin vazgeçilmezi map, reduce ve filter gibi yüksek dereceli fonksiyonların—argüman olarak fonksiyon alan ve/veya dönüş değeri olarak fonksiyon döndüren fonksiyon—birlikte kullanımını andıracaktır. Buna Hadoop temelli yazılım çerçevelerinin gerçekleştirim dilinin Java olması da eklendiğinde, çok çekirdekli hesaplamaya ince ayarlı bir JSM dili olan Clojure'un farklılaştırıcı özelliği takdir edilecektir.

Gelelim Lisp ailesi dillerinin belki de ustaları için en çekici olan özelliğine: bu dillerde kaynak kod ve veri için aynı gösterim kullanılır. Bir diğer deyişle, Clojure'un da üyesi olduğu Lisp ailesi dilleri eşgösterimlidir (İng., homoiconic). Bu, kaynak kodun veri olarak ele alınmasına olanak tanıdığı gibi, çalışmakta olan bir programın kendisine sunulan girdiyi kod olarak ele alıp işlemesine olanak tanır. Örneğin—Java kaynak kodu içinden XML dosyalarındaki kurulum bilgilerinin okunmasında olduğu gibi—yazılım sevkiyatı (İng., software deployment) sırasında güvenlik, seyir defteri güncelleme gibi müşteriye özel olarak farklı icra edilmesi istenebilecek hizmetlere dair bilgileri kurulum dosyasına Clojure programı yazar gibi yazıp bir diğer Clojure programından okuyarak işinizi görebilirsiniz. Ya da, kullanıcının girdi olarak sağladığı veriyi kod olarak ele alıp işleyerek programınızı çalışırken değiştirme şansına sahip olabilirsiniz.

Clojure'u özendirmek amacıyla öne süreceğimiz son sebep, eşgösterimlilik özelliği sayesinde diğer programlama dillerindekilerin çok ötesine geçen makro olanağıdır. Clojure makro işlemcisi, programın çalıştırılması öncesinde kaynak kodu o anda tanımlı bulunan makrolara uygun bir biçimde dönüştürür ve programcıların gördüğü ile yorumlayıcının işlediği kaynak kodun birbirlerinden farklılaşmasını sağlar. Böylece, programlama dilinde bulunmayan bir denetleme yapısının—mesela, koşut işlemeli bir döngü—dile kusursuz bir biçimde yamanarak pek çok programın daha kolay yazılması mümkün olacaktır. Benzer şekilde, yinelenen kod parçalarının şablon görevi gören makrolar yoluyla yazımı kolaylaştırılabilir. Programcının problem alanına yönelik yüksek düzey denetim yapıları ve kod şablonları yaratmasına olanak tanıyan bu özellik, Clojure'u (ve diğer Lisp ailesi dillerini) alana özel dil (İng., domain-specific language) gerektiren durumlarda öne çıkarmaktadır.

Kurulum


Sisteminizde bulunmadığı takdirde clojure.org/download adresinden indirebileceğiniz Clojure ortamının kurulumu, indirilen arşiv dosyasının içindeki clojure-x.y.z.jar dosyasının sınıf yolu üzerine konulması kadar basit.2 Yorumlayıcı (Clojure komut kabuğu) anılan paketin veya bu paketteki main sınıfının JSM'ye geçirilmesi ile çalıştırılabileceği gibi, evvelden kurulu bir Clojure ortamının bulunması durumunda clojure komutu ile de çalıştırılabilir.3
$ # java -cp ".:/arşiv/yolu/clojure-1.3.0.jar:$CLASSPATH" clojure.main
$ # java -cp ".:$CLASSPATH" -jar /arşiv/yolu/clojure-1.3.0.jar
$ clojure
Clojure 1.3.0
user=>
Yorumlayıcının başlaması, oku-değerlendir-bas döngüsünün (İng., read-evaluate-print loop [REPL]) başladığı anlamına gelir. Bundan sonra yapmamız gereken, Clojure dilinin sözdizimine uygun bir şeyler girip basılan sonuçları gözlemlemektir.
user=> (+ 2 3) → 5
user=> (def sayı 5)
#'user/sayı
user=> (+ 2 3 sayı) → 10
user=> (* 2 (+ 3 4)) → 14
user=> (System/exit 0) ; Komut kabuğuna Ctrl-D ile de dönülebilir
$
Oturumu inceleyerek bazı saptamalarda bulunalım. Öncelikle; Clojure kaynak kodu, yorumu ilk konumundaki simgeye göre değişen, ayraçlarla çevrili formlardan oluşur. İstenecek olursa, bir form bir diğerinin içine gömülebilir. Böyle bir durumda, en son açılan ayracın ilk kapatılması ve dıştaki formun bittiği noktada eşleştirilmemiş ayraç olmaması gerektiği unutulmamalıdır.

Formlar, deyimler, makrolar ve özel formlar olmak üzere üçe ayrılır. Deyimler, ilk konumdaki simgenin geri kalanlara uygulandığı işlemler olarak ele alınırken, makrolar kodu dönüştüren işlemciler olarak görülebilir; özel formların işleyiş mantığı duruma göre değişir. Örneğin, (+ 2 3) toplamanın 2 ve 3 argümanlarına uygulandığı işleme karşılık gelen bir deyim iken, (def sayı 5) çalışma ortamını 5 değerine sahip sayı adlı tanımlayıcının varlığı ile güncelleyen bir özel formdur.

Kod ve veri gösterimi için işleç-önde gösterimin şaşkınlığını üzerinizden attıktan sonra, bu seçimin aslında bazı artılarının olduğunu görebilirsiniz. Örneğin, bu gösterimin bir sonucu olarak ortaya çıkan tüm deyimlerin ayraç çifti ile çevrelenmesi zorunluluğu, öncelik sırası sorununu ortadan kaldırır; her bir kapatıcı ayraç eşleştiği ayracın başlattığı formun değerlendirilmesi gerektiğini bildirir. Ayrıca, kapatıcı ayraca kadar her şey argüman olarak yorumlandığı için, aynı işleç argümansız kullanılabileceği gibi, 3 veya 5 argümanlı da kullanılabilir. Mesela, (*) çarpmanın etkisiz elemanı olan 1 değerini döndürürken, (* 1 2 3 4 5) 5!, yani 120, değerini döndürür.

Son olarak, System/exit Java platformundaki System sınıfının exit adlı metoduna atıfta bulunmaktadır. Yani, oturumun son satırında, bir Java programı olan yorumlayıcıya programdan 0 değeri döndürecek şekilde çıkmak istediğimizi söylüyoruz. Genelleştirecek olursak, Sınıf adlı bir Java platformu sınıfının üye adlı static bir özelliğini kullanmak istediğimizde yapmamız gereken, deyimimizin ilk konumuna Sınıf/üye koymaktan ibarettir.

Fonksiyonlar Birer Hesaplama Nesnesidir


Mesele fonksiyonel bir programlama dilini anlatmaya çalışmaksa, yapılması gereken ilk şeylerden biri, hiç kusku yok ki, birimsellik aracı olan fonksiyonun tanımı ve kullanımından bahsetmektir. Bahis esnasında fonksiyonların matematikteki adaşlarına benzediği ve diğer türden değerlerle birlikte birinci sınıf vatandaşlar olarak kullanılabileceği akıldan çıkarılmamalıdır. Gelin, ne kastedildiğini aşağıdaki tanımlardan görelim.
user=> (def çarp (fn [a b] (* a b)))
#'user/çarp
user=> (def çarp2 #(* %1 %2))) ; çarp ile aynı
#'user/çarp2
user=> (def arg1 3)
#'user/arg1
user=> (def arg2 (read)) ; standart girdiden veri alıyor
17
#'user/arg2
user=> (çarp arg1 arg2) → 51
user=> ((fn [x y] (* x y) 4 5) → 20
user=> (#(* % %2) 6 7) →42
user=> (def çarp3 (partial çarp 3))
#'user/çarp3
user=> (çarp3 20) → 60
çarp ve çarp2'nin arg1 ve arg2 ile aynı form kullanılarak tanımlandığına dikkatinizi çekerek başlayalım. Komutsal programlama dillerinden gelenlere başta aykırı gözükebilecek bu durum aslında çok doğal: ne de olsa, ister tamsayı olsun isterse fonksiyon, dört tanımlayıcı da birer değeri simgeliyor. Değerlerden ikisi sayma kavramının örnekleri iken, diğer ikisi hesaplama kavramının örneklerini veriyor; ikisi (arg1 ve arg2) matematikte bağımsız değişken olarak ifade edilirken, diğerleri iki argümanlı bağımlı değişkenler olarak adlandırılıyor. Dolayısıyla, heseplamayı soyutlayan fonksiyon değerlerinin, 11. ve 12. satırlarda olduğu gibi, ad verilmeksizin kullanılması da bir o kadar doğal. Ne de olsa, 3 sabitini arg1 değeri ile temsil etmeden de kendi başına kullanabiliyoruz, fonksiyon değerlerini de ad vermeden kullanabilmeliyiz.

çarp2'nin tanımı yüksek dereceli fonksiyonlara fonksiyon geçirilmesini kolaylaştıran #() ile yapılıyor. Tek kullanımlık fonksiyonların simgesel bir değişkene atanmadan adsız kullanımını kolaylaştıran bu gösterimde, % ilk argümanı temsil ederken, %n n nolu argümana karşılık gelir.

Bazı yüksek dereceli fonksiyonlar ve kullanımlarına dair örnekler aşağıdaki tabloda verilmiştir. Yorumlayıcının oku-değerlendir-bas döngüsünün değerlendirme aşamasında uyguladığı iki temel fonksiyondan biri olan apply—diğeri eval'dir—ilk argümanındaki fonksiyonu daha sonraki argümanlara uygular. Bu işlem sırasında, son argümandaki kap parçalanarak eleman sayısı kadar farklı argüman olarak uygulanması istenen fonksiyona geçirilir. comp fonksiyonu, matematikten bildiğimiz bileşke fonksiyon yaratma işlecidir ve aldığı 0 ya da daha fazla sayıda fonksiyonun bileşkesi olan bir fonksiyon döndürür. juxt parametre listesindeki fonksiyonları ayrı ayrı bilahare geçirilecek argümanlara uygulayacak bir fonksiyon döndürerek işini görür. memoize fonksiyonu argümanındaki fonksiyonun daha hızlı çalışmasını sağlayabilmek adına daha önce yapılan hesaplamaları önbellekte tutup tekrar hesaplamanın önüne geçerek hızlandırmaya çalışan bir fonksiyon döndürür. Son olarak, partial fonksiyonu ilk argümanındaki fonksiyonun istediğinden az sayıda argümanla uygulanmasını olanaklı kılarak geri kalan argümanları bekleyen bir başka fonksiyon döndürür.

Bazı yüksek dereceli fonksiyonlar
FonksiyonİşlevKullanım
applyFonksiyon uygulama(apply fn arg & diğer-arglar)değer
compFonksiyon bileştirme(comp & fnler)fn
juxtFonksiyon uygulama(juxt fn & diğer-fnler)fn
memoizeÖnbellekli fonksiyon uygulama(memoize fn)fn
partialKısmi fonksiyon uygulama(partial fn arg & diğer-arglar)fn

user=> (apply * 2 3 (range 4 10)) → 362880
user=> (def fog (comp #(* % %) #(+ %1 %2)))
#'user/fog
user=> (fog 3 4) → 49
user=> ((juxt * + /) 6 4) → [24 10 3/2]
user=> (def önbellekli-f (memoize f))
#'user/önbellekli-f
user=> (önbellekli-f ...) → ...
Seçtiğimiz örneğin basit olması nedeniyle yapılan tek deyim uzunluğundaki tanımlar sizi yanıltmasın; istenecek olursa, tıpkı kıvrımlı ayraçlarla ({}) belirtilen Java bloklarında olduğu gibi, do özel formunu kullanarak gövdeyi istediğimiz sayıda deyimden oluşacak biçimde uzatabiliriz. İçerdiği formları baştan sona ardışık bir şekilde işleyen bu form, sonucu olarak son işlenen formun döndürdüğü değeri döndürür. Mesela, çarp2'nin tanımının bir selamlama ile genişletilmesi istenecek olursa, bu #(do (println "Selam") (* %1 %2)) tanımı ile yapılabilir. Benzer bir değişikliğin fn formunun kullanıldığı örnekte yapılmasına gerek yoktur; bu form gizli bir do ile çevrelenmiş gibi çalışır.

Temel Veri Türleri


Desteklenen temel veri türlerine geçmeden şu noktayı vurgulayalım: Clojure dinamik türlü bir programlama dilidir. Yani, Clojure'da tanımlayıcılar dil işlemcisine yardım etmek amacıyla türe dair üstbilgi ile nitelenmezler; bir tanımlayıcının türü kendisine yapılan ilkleme/atama sonrasında temsil etmeye başlayacağı değere göre belirlenir. Statik türlemeli dillerde derleyicinin denetimi sonrasında yazılmasına izin verilmeyecek bazı işe yarar programların yazılıp çalıştırılabileceği anlamına gelen bu özellik, kimilerinin düşündüğünün aksine, Clojure'un zayıf bir tür denetimine sahip olması demek değildir. Kaynak kodun işlenmesi esnasında tüm işlemlerin tür denetimini yapan Clojure, türleme hatasına sahip herhangi bir işlemin icra edilmesine izin vermez. Özetlemek gerekirse, Clojure hem dinamik türlüdür hem de kuvvetli türlemeye sahiptir.4

Aşağıdaki tablodan da görülebileceği gibi, Clojure Java programlama dili ile ortak temel türlerden değerleri Java platformundaki sarmalayıcı sınıfların nesneleri olarak temsil eder. Biçimlendirme yapılmadığı müddetçe, tamsayılar Long, gerçel sayılar ise Double türüyle temsil edilirler. İstenecek olursa, Java'daki ilkel türlerle aynı adlara sahip fonksiyonlardan biri kullanılarak biçimlendirme yapılabilir. Örneğin, (byte 3) normalde Long olarak ele alınacak 3'ü Byte türlü bir sabite çevirecektir.

Clojure'daki temel türler
GösterimTürKavram
\ajava.lang.CharacterKarakter
"Katar"java.lang.StringKarakter katarı
5java.lang.LongTamsayı
5N*clojure.lang.BigInt
5.0java.lang.DoubleGerçel sayı
5.0Mjava.math.BigDecimal
22/7, (/ 22 7)clojure.lang.RatioKesirli sayı
(> 1 0)java.lang.BooleanMantıksal değer
'simgeclojure.lang.SymbolTanımlayıcı adı, simgesel sabit, anahtar değeri
:anahtarclojure.lang.KeywordSimgesel sabit, anahtar değeri
*: Clojure 1.3 ve sonrası.

Kayan noktalı sayı aritmetiğinde ortaya çıkabilecek taşmalar Java'da olduğu gibi kullanılmakta olan sayı formatındaki özel değerler ile temsil edilirken🔎, tamsayılarda sınır aşımı programcıya ArithmeticException ayrıksı durumu ile bildirilir. Bunun yerine Long'dan clojure.lang.BigInt'e bir genişletme istenecek olursa, aritmetik işlem adı sonuna ' eklenmesi yeterli olacaktır. Buna göre, (+ 1 Long/MAX_VALUE) ayrıksı duruma neden olurken, (+' 1 Long/MAX_VALUE) 9223372036854775808N değerini döndürecektir.5

İki tamsayının oranını temsil eden kesirler, pay ve paydanın sadeleştirilmesiyle elde edilen iki java.math.BigInteger (clojure.lang.BigInt değil!) nesnesi olarak tutulurlar. Her işlemin bu BigInteger nesnelerden yararlanarak yapılması ve nihai sonucun bunu takip eden sadeleştirmeden sonra elde edilmesi, kesirli sayılarla işlemlerin yavaş olmasına neden olur. Bundan dolayıdır ki, Clojure sadeleşme sonucu paydası 1 olan kesirleri tamsayıya dönüştürerek yoluna devam eder. Sizin de yüksek duyarlık gerektiren hesaplar dışında kesirleri kullanmaktan kaçınmanız yerinde olacaktır.

Lisp ailesi dışındaki programlama dillerinde pek görünmeyen simgeler, tanımlayıcı adlarının türü olarak tanımlanabilir. Bundan ne kastettiğimizi (def i 5) özel formunu inceleyerek açmaya çalışalım. Bu tanımlama sonrasında i simgesi 5 değerine sahip bir değişken olarak ortama eklenir. Bir diğer deyişle, bu tanımla birlikte i 5'i simgelemeye başlar. Bu noktadan sonra, i'ye atıfta bulunulduğunda yorumlayıcı i yerine i simgesinin ortamdaki değeri olan 5'i koyacaktır. Örneğin, (+ i 3) (+ 5 3) haline dönüştürülecektir. Ancak, istenecek olursa simgenin önüne ' konulmak suretiyle bu dönüşümün önüne geçilebilir ve simgelenen değer yerine simgenin kendisi kullanılabilir. Böylesine bir kullanım, hünerini içerdiği tutanak değerlerinin anahtarlar eşitliklerini denetleyerek sergileyen eşlemlerde (ve diğer arama yapılarında) oldukça sık görülür. Çünkü, simgelerde eşitlik denetimi çok hızlı yapılabilir. Aynı özellikten anahtar türü için de bahsedebiliriz. : ile başlayan anahtarlar, başka bir şeyi göstermeyen simgeler olarak düşünülebilir. Yani, yapılacak bir tanım yardımıyla bir değeri gösteren simgelerin aksine, anahtarlar herhangi bir değeri simgelemez. Aynı zamanda, simgelerin program metnindeki her geçişi diğer geçişlerinden farklı iken, herhangi bir anahtarın tüm geçişleri aynıdır.

Veri Kapları


Clojure tarafından sağlanan veri kapları doğrusal kaplar (liste, vektör🔎), kümeler, eşlemler🔎 ve karakter katarları🔎 olmak üzere dört kategoride incelenebilir. Kategoriler veri kaplarını eşitlik temelinde denklik sınıflarına ayırmakta da kullanılır. Eşit addedilmeleri için kapların aynı türden olması gerekmez; dolaşıldıklarında karşılıklı elemanlarının eşit olduğu görülen aynı kategorideki tüm kaplar birbirine eşittir.

Clojure'da desteklenen veri kapları, aşağıdaki tablodan da görülebileceği gibi, yapıcı görevi gören fonksiyonların yanısıra özel sözdizimi yardımıyla da yaratılabilir. Dikkat edilirse, küme ve eşlemler için, Java Veri Kapları Çerçevesi'ndekileri anımsatan, farklı yapıcılar sağlandığı görülecektir. Bu, aynı zamanda söz konusu kap için (class kap) deyimiyle keşfedilebilecek farklı bir gerçekleştirim seçildiği anlamına gelmektedir.

Clojure destekli kaplar
CinsYapıcıÖzel gösterim
Liste(list 1 2)'(1 2)
Vektör(vector 1 2)[1 2]
Eşlem{:Adana 1 :İzmir 35}
(hash-map :Adana 1 :İzmir 35)
(sorted-map :Adana 1 :İzmir 35)
Küme(hash-set :insan :şempanze)#{:insan :şempanze}
(sorted-set :insan :şempanze)
Kar. katarı(str \a \b \c)"abc"

Clojure'dakilere ek olarak, Java Veri Kapları Çerçevesi'nce sağlanan eşdeğer kaplardan da yararlanılabilir. Aynı kategoride addedilen bir Clojure kabı ile Java eşdeğerinin hemen hemen aynı olduğu söylenebilir. Eşit içeriğe sahip eşdeğer kaplar birbirine eşittir; Clojure kaplarına uygulanan fonksiyonlar Java eşdeğerlerine de uygulanabildiği gibi, Clojure kapları Java nesnesi olarak da kullanılabilir. İlişkin örnekler aşağıda verilmiştir.
user=> (import '(java.util ArrayList Vector))
java.util.Vector
user=> (def java-ls (ArrayList.))
#'user/java-ls
user=> (.add java-ls 1) → true
user=> (doto java-ls (.add 2) (.add 3)) → #<ArrayList [1, 2, 3]>
user=> (def java-vek (Vector. java-ls))
#'user/java-vek
user=> (= java-vek '(1 2 3) [1 2 3] java-ls) → true
user=> (= #{1 2} '(1 2)) → false
user=> (map #(* % %) java-vek) → (1 4 9)
user=> (reduce (fn [a b] (if (> a b) a b)) '(80 70 85)) → 85
user=> (filter odd? [1 2 3 4 5]) → (1 3 5)
user=> (remove odd? #{1 2 3 4 5})) → (2 4)
user=> (.size [1 2 3 4]) → 4
user=> (apply str (map #(Character/toUpperCase %) "Abc")) → "ABC"
Kodu incelerken şu noktaların bilinmesi yardımcı olacaktır: i) import bir veya daha fazla sayıda sınıf dosyasını içselleştirip çalışma ortamında görünür hale getirir, ii) . ile sonlanan sınıf adları Java platformundaki bir sınıfın yapıcılarından birini çağırır, iii) önüne . eklenmiş fonksiyon adları ilk argümanda belirtilen alıcıya ileti göndermekte kullanılır, ve iv) doto makrosu ikinci ve sonrasındaki argümanlarda belirtilen iletileri ilk argümanda belirtilen alıcıya yönlendirir.

Kaplar üzerinde çalışan bazı yüksek dereceli fonksiyonlar
FonksiyonİşlevKullanım
mapKap dönüşümü(map fn k & diğer-kaplar)kap
reduceİndirgeme, özetleme(reduce f k), (reduce f ilk-değer k)değer
filterSüzme(filter fn k)kap
removeSilerek süzme(remove fn k)kap

Clojure ve Java veri kapları arasındaki şu temel farklılık unutulmamalıdır: Java'da kap içeriği uygun iletiler yardımıyla değiştirilebilirken, Clojure'daki tüm kaplar değişmez içeriklidir. Bir başka deyişle, Clojure'da kaplar yaratılmaları sonrasında değiştirilemezler. Değişme etkisinin yaratılması için içerik güncelleme işlemleri yapan fonksiyonların dönüş değerlerinin kullanılması gerekir.
user=> (def çete '("Veli" "Selami"))
#'user/çete
user=> (def yeni-çete (conj çete "Ali"))
#'user/yeni-çete
user=> çete → ("Veli" "Selami")
Düşük maliyetli bir biçimde gerçekleştirilebilen bu stratejinin (bkz. 1, 2) temelinde programcıyı değişken içerikli kaplardan uzak tutmak suretiyle çok izlekli program yazma bağlamında daha kolay sınanabilir kod üretmeye sevketmektir. String sınıfının🔎 sabit içerikli olmasının temelinde de yatan bu yaklaşım, değişmeyecek bir kabın birden çok izlekten sakıncasız bir biçimde kullanılabileceği gerçeğinden yararlanır. Aslında, Java Veri Kapları Çerçevesi de dikkatle bakan gözlere aynı mesajı vermektedir: arayüzlerde yer alan tüm içerik güncelleyici iletilerin başlığı UnsupportedOperationException ayrıksı durumunu içerir. Clojure kapları buna dayanarak, Clojure'a özel fonksiyonlara ek olarak [Java kodu ile birlikte çalışmak adına] Veri Kapları Çerçevesi'nin ilişkin arayüzünü gerçekleştirdiklerinde söz konusu iletileri desteklemediklerini bildiren UnsupportedOperationException ayrıksı durumunu fırlatacak şekilde gerçekleştirir.
user=> (def vek [1 2])
#'user/vek
user=> (.size vek) → 2
user=> (.toString vek) → "1 2"
user=> (.add vek 3) → java.lang.UnsupportedOperationException (NO_SOURCE_FILE:0)
map, reduce gibi pek çok fonksiyonun ayırt etmeksizin tüm kaplara uygulanabilmesi, bu tür fonksiyonların diğer Lisp ailesi dillerinde olduğu gibi liste veya bir diğer türden kap almak yerine clojure.lang.ISeq arayüzünü gerçekleştiren bir kap alıyor olmasıyla mümkün olur. Buna göre, Clojure listelerinin gerçekleştirimini sağlayan Java sınıfının aşağıdaki gibi olduğunu söyleyebiliriz.
package clojure.lang;

public class PersistentList extends Obj implements ISeq, ... { ... }
ISeq arayüzü, eleman sayısını döndürüren count ve ilk argümanındaki kaba ikinci argümanındaki değerin eklenmiş halini döndüren conj'un yanısıra, yegâne argümanındaki kabın dolaşılmasına yarayan bir liste döndüren seq iletisini içerir.

Son olarak değineceğimiz nokta, vektör veya eşlem gösteren bir simgenin fonksiyon adı konumunda kullanılabilecek olmasıdır. Aşağıdaki kod parçasında olduğu gibi, bir vektöre indis, bir eşleme ise anahtar değeri verilecek olursa ilişkin kap içindeki o indis veya anahtar karşılık gelen değer döndürülür.
user=> ([1 2 3 4] 1) → 2
user=> (plaka-nolar :İzmir) → 35

Fonksiyon Tanımı, Yeniden


Tanımının uzamasıyla birlikte fonksiyon gövdesinin anlaşılması da zorlaşacaktır. Bu etkiyi azaltmak amacıyla, gerçekleştirimimize yorum ve üstbilgi eklemeyi düşünebiliriz. Böyle bir durumda, makro işlemcisi tarafından def ve fn formlarına dönüştürülecek olan defn makrosunu kullanmamız daha yerinde olacaktır.

Selamlar.clj
(import '(java.util Calendar GregorianCalendar))

(defn selamlar
  "Argümanında geçirilen kişilere selam verir. Bunu yaparken aşırı yüklemeden yararlanır."
  {:yazar "Tevfik AKTUĞLU" :tarih (GregorianCalendar. 2012 Calendar/JANUARY 7)}
  ([tanıdık] (println "Selam," tanıdık))
  ([x y & diğerleri] (println "Selam millet!"))
  ([] (println "Selam, kim olursan ol!")))
...
Yukarıdaki fonksiyon tanımı, üç farklı parametre listesine göre üç gövde sağlamaktadır. Bir bakıma, hepsinin adı selamlar olan üç ayrı fonksiyon tanımlanmaktadır. Bu fonksiyonlardan ilki tek argümanlı iken, ikincisi 2+ argüman beklemektedir; son gövde tanımı ise argümansız kullanım durumunda işlenecektir. Değişken sayıda argüman alan seçenekte, ikinci argüman sonrasında geçirilecek tüm değerlerin bir listeye konulup & imini takip eden parametreye (diğerleri) karşılık gelen argümanda geçirileceği söylenmektedir.

defn makrosu fonksiyon tanımında kullanılan diğer formların sunmadığı iki olanak sunmaktadır. Bunlardan ilki, tanımlanmakta olan fonksiyonun adını takiben sağlanan ve daha sonra doc fonksiyonuyla sorgulanabilecek dokümantasyon yorumudur. İkinci olanak ise, programcının gereksinimlerine göre seçeceği üstbilgilerin fonksiyon tanımına iliştirilmesidir. Örneğimizde, dokümantasyon yorumları sonrasındaki üstbilgi eşlemi vasıtasıyla kodu yazan kişi ve en son güncelleme tarihi bilgilerini selamlar simgesine iliştiriyoruz.
;;Sınıf yolu üzerinde bulunan Selamlar.clj dosyasındaki formları yükler. 
user=> (load "Selamlar") → nil
user=> (selamlar) → nil
Selam, kim olursan ol!
user=> (selamlar "Tevfik") → nil
Selam, Tevfik
user=> (selamlar "Ali" "Veli" "Selami") → nil
Selam millet!
user=> (doc selamlar) → nil
------------------------
user/selamlar
([tanıdık] [x y & diğerleri] [])
  Argümanında geçirilen kişilere selam verir. Bunu yaparken aşırı yüklemeden yararlanır.
user=> (meta (var selamlar))
{:ns #<Namespace user>, :name selamlar, :file "Selamlar.clj",..., :tarih ...}
selamlar'a alternatif olarak sunulan ve 0+ argüman geçirilerek çağrılabilecek aşağıdaki selamlar2 fonksiyonu, yeni bazı şeyler sunmakta. Bunlardan ilki, parametre listesi sonrasındaki önkoşul tanımıdır. Bilenlerin Eiffel programlama dilinden anımsayacağı sözleşme temelli tasarımın (İng., Design by Contract) bir parçası olan önkoşul (İng., precondition), fonksiyonun her çağrılışı öncesinde denetlenir. Sonucun olumsuz olması, sağlıklı çalışma için karşılanması zorunlu görülen bir koşulun oluşmadığı anlamına gelir ve bu bilgi fonksiyon çağrılmaksızın programın bitirilmesini takiben uygun bir mesajla kullanıcıya bildirilir. Mesela, selamlar2 örneğinde selam verilecek kişileri temsil eden argümanların toplandığı listenin 3 veya daha az sayıda elemanı olması bir önkoşul olarak tanımlanıyor. Tamamlayıcı bir denetim, fonksiyon çağrısının sona erdiği noktada karşılanması zorunlu görülen durumların belirtilmesini mümkün kılan sonkoşulları listeleyen :post ile yapılabilir.
...
(defn selamlar2
  "cond formundan yararlanarak argümanında geçirilen kişilere selam verir. Bu arada, önkoşul denetimiyle 4 ve daha fazla sayıda kişiden oluşan gruplara selam vermeyerek asayişi korur."
  {:yazar "Tevfik AKTUĞLU" :tarih (GregorianCalendar. 2012 Calendar/JANUARY 7)}
  [& ahali] {:pre [(< (count ahali) 4)]}
  (let [nüfus (count ahali)]
    (cond
      (> nüfus 1) (println "Selam millet!")
      (= nüfus 1) (println "Selam," (first ahali))
      :aksi-takdirde (println "Selam, kim olursan ol!"))))
Fonksiyon tanımında dikkat çekilmesi gereken bir diğer nokta, blok değişkenlerin tanımını olanaklı kılan let özel formudur. Kendisine sağlanan vektörün tek sayılı sıralardaki elemanlarını değişken adı olarak kabul eden let, değişkeni takip eden değeri ilkleme amacıyla kullanır. Buna göre örneğimizdeki let formu, nüfus adına sahip ve argümanda geçirilen listenin eleman sayısıyla ilklenmiş bir yerel değişken tanımlamaktadır. Tanımlanan blok içindeki cond makrosu ise, C-temelli dillerdeki switch-case yapısına benzer bir görev görür: koşulları tepeden aşağıya sıralı bir biçimde sınar ve doğru olduğunu gördüğü ilk kolun formunu işler. Tüm durumların kapsanması için son kola her zaman doğru olacağı bilinen bir koşul konmalıdır. false ve nil dışındaki tüm değerler doğru kabul edildiği için, örneğimizde bu görevi :aksi-takdirde anahtarı görmektedir.
user=> (selamlar "Ali" "Veli" "Selami" "Nuri") → nil
java.lang.AssertionError: Assert failed (< (count millet) 4) (NO_SOURCE_FILE:0)
user=> (find-doc "selamlar") → nil
------------------------
user/selamlar
([tanıdık] [x y & diğerleri] [])
  Argümanında geçirilen kişilere selam verir. Bunu yaparken aşırı yüklemeden yararlanır.
-------------------------
user/selamlar2
([& ahali])
  cond formundan yararlanarak argümanında geçirilen kişilere selam verir. Bu arada, önkoşul denetimiyle 4 ve daha fazla sayıda kişiden oluşan gruplara selam vermeyerek asayişi korur.

Özyineleme


Yazımızın son kısmında fonksiyonel programlama dillerinin birincil yineleme yöntemi olan özyinelemeye değineceğiz. Bu yapmamızın nedeni, Clojure'un komutsal dillerden gelenlere tanıdık gelecek türden döngüleri desteklememesi değil. Elbette ki, dilin kendisinde olmasa bile Clojure'daki gibi bir makro olanağınız varsa, bildik tüm döngüleri ve fazlasını özyineleme kavramını kullanarak tanımlayabilrsiniz. Derdimiz, fonksiyonel programlamadan optimize edilen özyinelemeli çağrılara alışmış olanlara ufak bir uyarıda bulunmak. Çok sallanmadan faktöryel fonksiyonunu gerçekleştiren aşağıdaki tanımla başlayalım.
(defn ! [n]
  {:pre (pos? (inc n))}
  (if (<= n 1)
    1
    (* n (! (dec n)))))
Argümanının eksi olmaması önkoşuluna sahip gerçekleştirimimiz, özyinelemenin bitiş koşulu olarak argümanının 1 veya 0 olmasını seçmiş ve bu durumda 1 döndürüyor. Aksi takdirde, tümevarım adımında ifade edildiği gibi, problem kendi türünden daha basit bir probleme indirgenerek çözüm sağlanıyor: argüman ile argümanın bir eksiğinin faktöryeli çarpılıp sonuç olarak döndürülüyor. Ancak, bildirimsel (İng., declarative) olması nedeniyle doğruluğu kolayca kanıtlanabilecek gerçekleştirimimizin—ne de olsa, çözümü programlama dünyasına özel yapıları kullanarak sağlamaktansa problem tanımını birebir çevirerek sağlıyoruz—sonsuz döngülerle boğuşmuş olanlara pek de yabancı gelmeyecek bir sorunu var: bitiş koşuluna uzak bir ilk durumun verilmesi durumunda, özyinelemeli çağrıların sayısı artacak ve argümanların yerleştirildiği çağrı yığıtı dolarak hesaplamamız sonuç döndürmeden StackOverflowError ile sona erecektir.
user=> (! 5) → 120
user=> (! 100000) → java.lang.StackOverflowError (NO_SOURCE_FILE:0)
Ortaya çıkan sorun iki şekilde çözülebilir: i) ürettiği ara sonuçları biriktirici argümanlar yoluyla bir sonraki çağrıya aktaran özyinelemeli bir çözümle, ii) özyineleme yerine döngü kullanarak. Gelin birinci şıkkın gerçekleştirimi olan aşağıdaki koda bir göz atalım.
(defn !2 [n]
  {:pre (pos? (inc n))}
  (letfn [
    (!-iç [n biriktirici]
      (if (<= n 1)
        biriktirici
        (!-iç (dec n) (* biriktirici n))))]
    (!-iç n 1)))
Örneğimizde, kullanıcının !2'ye sağladığı değer yerel fonksiyona o ana kadarki hesaplamanın özeti olarak niteleyebileceğimiz biriktiricinin ilk değeri ile birlikte geçiriliyor. Kullanıcının görmediği !-iç'i incelediğimizde, tümevarım adımının özyinelemeli çağrı sırasında ikinci argümanı o anki ilk argümanla çarparak güncellediğini ve bitiş koşulunun oluştuğu noktada ise 1 yerine biriktirilmiş değeri döndürdüğünü görüyoruz. Bu dönüşümü yapmaktaki amacımız, özyinelemeli çağrıyı fonksiyon içinde en son yapılan iş haline getirmek ve böylece fonksiyonel programlama dillerinde sıklıkla uygulandığını bildiğimiz kuyruk çağrısı eniyilemesinden yararlanmaktır. Gelin görün ki, kazın ayağı öyle değil! JSM üzerine inşa edilmiş olan Clojure, JSM'nin kuyruk çağrısı eniyileme desteği vermemesi nedeniyle bizi utandırıyor.
user=> (!2 100000) → java.lang.StackOverflowError (NO_SOURCE_FILE:0)
Derdimizin çaresi, Clojure'a işi JSM'ye bırakmadan kendi yapabildiği kadarıyla yapmasını söylemek. Bu ise, aşağıdaki gibi özyinelemeli çağrıların olduğu yerlerde, fonksiyon adı yerine recur yazmakla mümkündür. recur özel formu, kuyruk konumunda yapılan özyinelemeli çağrıları arka planda goto benzeri birer sıçrama komutuna çevirir. [Sadece özyinelemeli çağrılar eniyilenir; genel kuyruk çağrısı eniyilemesi yapılmaz!] Bu, çağrı yığıtında ilk çağrıdaki argümanların işgal ettiği yerlerin yeniden kullanılacağı ve dolayısıyla sabit bellekle işimizin halledileceği anlamına gelir; ayrıca, fonksiyon çağrıları yerini daha ucuz olan sıçrama komutlarına bırakacağı için çalışma hızı da olumlu etkilenecektir. Bunu time makrosu yardımıyla görebilirsiniz.
(defn !3 [n]
  {:pre (pos? (inc n))}
    (letfn [
      (!-iç [n biriktirici]
        (if (<= n 1)
          biriktirici
          (recur (dec n) (* biriktirici n))))]
      (!-iç n 1)))
user=> (time (!3 2000)) → "Elapsed time: 20.266474 msecs" 33162...
user=> (time (!2 2000)) → "Elapsed time: 24.969519 msecs" 33162...
Bir diğer çözüm yöntemi loop özel formundan yararlanır. Döngü tutkunu olanları özyinelemeye alıştırmak için önerilebilecek bu form, eniyilenmiş özyinelemeli kuyruk çağrısı çözümüne yakın, hatta daha iyi bir çalışma hızı sağlar. Hızı daha da iyileştirmek isteyenlere önbellekli fonksiyon uygulaması olanağını sağlayan memoize fonksiyonu önerilir. Ancak; önceden yapılmış bazı hesaplamaları tekrar hesaplamaktansa kaydettiği sonucu kullanarak işini gören bu yüksek dereceli fonksiyonun argümanları dışında çağrı ortamına bağımlılığı bulunan fonksiyonlarla çalışamayacağı akılda tutulmalıdır.
(defn !4 [n]
  {:pre (pos? (inc n))}
  (loop [i n, biriktirici 1]
    (if (<= i 1)
      biriktirici
      (recur (dec i) (* biriktirici i)))))
user=> (def !4-hızlı (memoize !4))
#'user/!4-hızlı
user=> (time (!4-hızlı 1900)) → "Elapsed time: 27.253187 msecs" 33162...
user=> (time (!4-hızlı 2000)) → "Elapsed time: 21.0582 msecs" 33162...
Tüm diğer zaman ölçümlerinde olduğu gibi, hıza dönük yorumların beklenen ortalama çalışma hızı düşünülerek yapıldığı unutulmamalıdır; döndürülen değerlerin sisteme ve yüke göre değişmesi, önbellekli uygulama örneklerinde önbellek yönetiminden kaynaklanan beklenmedik farkların oluşması sizi şaşırtmamalıdır.


  1. Java SE 8 ile birlikte, kod örtülerinin bu eksikliği büyük ölçüde gidereceğini söyleyebiliriz. Dolayısıyla, 2013'ün ikinci yarısında yargımızın Java bölümü geçerliğini yitirmiş olacak.
  2. Clojure programlama dilinin resmi sitesine gittiğinizde, Screencast etiketli bir bağlantı gözünüze çarpabilir. Gezegenimizin mutlu insanlarını Clojure diliyle ilgili bir video serisine götüren bu bağlantı, Türkiye'de yaşayanlar için—henüz farkına varılmayan üniversite ve benzeri ortamlardaki mutlu azınlık dışında—alıştık İnternet sansürlerinden birini simgeliyor. [Son kontrol tarihi: 29-Aralık-2011] İşin hazin tarafı, bu durum Wikipedia'nın blip.tv sayfasında, ülkemizin Çin'le birlikte—listede üçüncü bir ülke yok!—anılması yoluyla reklam ediliyor.
  3. İllaki bol pencereli bir geliştirme ortamı istiyorsanız, size bu sayfaya bakmanızı öneririm. Ayrıca, çalışma ortamınızın özelliklerine bağlı olarak, örneklerdeki Türkçe'ye özel harflerde sıkıntı yaşayabilirsiniz. Bunun olası nedeni, kullanmakta olduğunuz Java arşivinin Türkçe'deki bu karakterleri dışlayacak bir kodlama ile derlenip oluşturulmasıdır. Tavsiyem, clojure komutuna öncelik vermeniz; bu da çözüm sağlamıyorsa, Clojure ortamını UTF-8 kodlaması ile derlemeniz.
  4. Aslına bakılırsa, Clojure tanımlayıcılar hakkında tür bilgilerinin sağlanması için isteğe bağlı olarak kullanılabilecek bir düzenek sağlıyor. Ancak, yazımızda bu olanağa değinmeyeceğiz.
  5. Clojure 1.3 öncesinde durum farklıydı. Öncelikle, nitelenmemiş bir sabitin türü Long değil, Integer idi. Ayrıca, taşma ayrıksı duruma sebep olmaktansa söz konusu değeri Integer ise Long'a, Long ise java.math.BigInteger—Clojure 1.3'te olduğu gibi clojure.lang.BigInt değil!—türüne terfi ettirerek sessizce geçiştiriliyordu.

2 Aralık 2011 Cuma

Hızlı Arama Zamanlı Kaplar-2

Kaldığımız yerden devam ediyoruz. Dizimizin ikinci ve son yazısında, ilk yazıyı okuyanlara tanıdık gelecek aşağıdaki kısmi sıradüzenin eşlemler için dengeli ağaç temelli gerçekleştirim sağlayan kısmına değineceğiz. Buraya ilk yazıyı okumadan yolunuz düşüp de kavramsal olarak kendinizi hazır hissetmiyorsanız, size tavsiyem ilk yazıya bir göz atıp daha sonra buraya dönmeniz.🔎

TreeMap Sınıfı


Eşlem yapısı, altyapıda anahtar bilgisine göre oluşturulan bir dengeli ağaç kullanılarak da gerçekleştirilebilir. Bu yol izlenecek olursa çözüm, eşleme gönderilen iletilerin dengeli ağaca yönlendirilmesiyle sağlanır. Bu tür ağaçların ekleme, silme ve sorgulama işlemlerini O(lgn) zamanda yapması nedeniyle, anılan işlemlerin eşlemde de O(lgn) performanslı gerçekleştirilmesi mümkün olacaktır. Bu noktadan hareketle, standart Java kitaplığındaki TreeMap sınıfı eşlem yapısını kırmızı-siyah ağaçlardan yararlanarak gerçekleştirmiştir.1

Altyapıda dengeli ağaç kullanılıyor olması, TreeMap sınıfının pek çok ekstra iletiyi düşük maliyetli bir gerçekleştirimle desteklemesini olanaklı kılar. Bunun başlıca nedeni, kök-ortada (İng., inorder) dolaşmanın ağaç içindeki bilgileri anahtara göre sıralı vermesidir. Bu sayede eşlem içeriği anahtara göre sıralı bir şekilde oluşturulabilir; ayrıca sıralama aşamasına gerek yoktur. Bunun doğal bir sonucu olarak, TreeMap sınıfı SortedMap ve NavigableMap arayüzlerinde listelenen eşlem içeriğinin uç değerleri ve dilimlerine dair iletileri de destekler. Ayrıca, Map🔎 arayüzünde tanımlanmış olan entrySet, keySet ve values iletilerinin gerçekleştirimleri de sonuçlarını anahtara göre sıralı değerlerden oluşan birer kap içinde döndürürler.

Kök-ortada dolaşmanın düğümleri anahtara göre sıralı üretebilmesi, anahtar-tutanak çiftlerinin altyapıdaki dengeli ağacın anahtar değerine göre belirlenen uygun düğümlerine eklenmeleri ile mümkün olur. Bu ise, eklenmekte olan anahtar değerinin eşlemde var olanların bir kısmı ile karşılaştırılmasıyla olanaklıdır. Benzer şekilde, silme ve sorgulama işlemlerinde de söz konusu anahtara karşılık gelen düğümün karşılaştırma işlemleri yardımıyla saptanıp işlemin tamamlanması mümkün olacaktır. Bütün bunlar, anahtar türünün karşılaştırılabilir olması zorunluluğunu beraberinde getirir. Yani, anahtar türü ya Comparable kategorisinde olmalıdır ya da java.util.Comparator arayüzünü gerçekleştirilen bir sınıf anahtar türüne ait nesneleri karşılaştırma desteğini sağlamalıdır. Gelin bu konuyu TreeMap sınıfının yapıcılarına açıklık getirerek anlamaya çalışalım.
...
import java.util.TreeMap;

public class Eşlemler {
  public static void main(String[] ksa) {
    ...
    Map<String, String> sözlük3 = new TreeMap<>();
    sözlüğüDoldur(sözlük3);
    System.out.println("Sözlük içeriği: " + sözlük3);
    ...
  } // void main(String[]) sonu
  ...
} // Eşlemler sınıfının sonu
Yukarıdaki kod parçasının işaretli satırındaki yapıcı çağrısı sonucunda yaratılan eşlem, karşılaştırma amacıyla, herhangi bir bilgi verilmediği için, anahtar bilgilerinin üyesi olduğu String sınıfınca gerçekleştirilen Comparable arayüzündeki compareTo iletisini kullanacaktır. Bunun sonucunda, sözlük3 adlı eşlemi standart çıktıya basan komut, sözcükleri büyük harfler önce olmak üzere alfabetik sıraya göre dizecektir. Ayrıca, bu iş yapılırken Türkçe'ye özel harfler beklediğimiz sıranın aksine sona doğru yer alacaktır. Bu sorunun çözümü, Türkçe'ye özel bir sözcük karşılaştırma sınıfı gerçekleştirmektir.
...
import java.text.Collator;
import java.util.Comparator;
import java.util.Locale;

public class Eşlemler {
  public static void main(String[] ksa) {
    ...
    Map<String, String> trSözlük =
      new TreeMap<>(new TürkçeSözcükKarşılaştırıcı());
    sözlüğüDoldur(trSözlük);
    System.out.println("Sözlük içeriği: " + trSözlük);
    ...
  } // void main(String[]) sonu
  ...
} // Eşlemler sınıfının sonu

class TürkçeSözcükKarşılaştırıcı implements Comparator<String> {
  private final static Collator trKarşılaştırıcısı =
    Collator.getInstance(new Locale("tr"));

  public int compare(String s1, String s2) {
    return trKarşılaştırıcısı.compare(s1.toLowerCase(), s2.toLowerCase());
  }
} // TürkçeSözcükKarşılaştırıcı sınıfının sonu
Yukarıdaki kod parçasının işaretli satırları, dengeli ağaç altyapılı boş bir eşlem yaratırken ağacın, ve dolayısıyla eşlemin, oluşturulması amacıyla kullanılacak karşılaştırma ölçütünün argümanda geçirilen nesne tarafından belirlendiğini söylemektedir. Bu nesnenin sınıfına bakacak olursak, sözcüklerin büyük-küçük ayrımı yapılmaksızın Türkçe alfabeye göre karşılaştırılacağını ve sıranın Türkçe'den alıştığımız şekilde oluşacağını görürüz.

TreeMap sınıfının diğer yapıcıları kopyalayan yapıcı olarak çalışır. Bunlardan yegâne argümanında SortedMap arayüzünü gerçekleştiren bir eşlem alanı, yaratılmakta olan eşlemi argümanda geçirilenin içeriği ile dolduracaktır. Birbirinden bağımsız iki eşlem oluşmasına yol açan bu işlemin sonrasında yeni eşleme uygulanacak işlemler argümandaki eşlemin kullandığı karşılaştırma ölçütü ile aynı olacaktır. Sonuncu yapıcı da buna benzer bir mantıkla çalışır. Bu sefer, kopyalamanın kaynağı olan eşlem Map arayüzünü gerçekleştiren herhangi bir eşlem olabilir. Yani, argüman olarak TreeMap nesnesi geçirilebileceği gibi, diğer altbölümlerde göreceğimiz sınıfların nesneleri de geçirilebilir ki, bu yaratılmakta olan eşlemin taklit edeceği bir karşılaştırma ölçütünün olmayabileceği anlamına gelir. Dolayısıyla, bu yapıcı çağrısının kullanımı sonrasında yeni yaratılan eşlemin içeriğinin düzenlenmesinde ölçüt olarak anahtar sınıfının compareTo iletisi kullanılacaktır.

Yaratılan eşlemin içeriğini var olan bir eşlemden alırken farklı bir ölçüt kullanmak olanaklı değil mi, diye sorabilirsiniz. Hemen sorunuzun yanıtının olumlu olduğunu söyleyelim. Bunun için yapmanız gereken, eşlemi uygun bir karşılaştırma ölçütü ile boş yaratıp putAll iletisi ile doldurmaktan ibarettir.
...
public class Eşlemler {
  public static void main(String[] ksa) {
    ...
    Map<String, String> sözlük4 =
      new TreeMap<>(new TürkçeSözcükKarşılaştırıcı());
    sözlük4.putAll(sözlük3);
    System.out.println("Sözlük içeriği: " + sözlük4);
    ...
  } // void main(String[]) sonu
  ...
} // Eşlemler sınıfının sonu

SortedMap Arayüzü


Gelelim, SortedMap arayüzünde olup TreeMap sınıfınca gerçekleştirilen iletilere. Bunlardan comparator, hedef eşlemin hangi ölçüte göre düzenlendiğini döndürür. Ancak, aklınızda olsun: bu iletinin null döndürmesi herhangi bir ölçüt kullanılmadığı anlamına gelmez; sadece, Comparable arayüzünü destekleyen anahtar sınıfının compareTo gerçekleştiriminin kullanıldığı anlamına gelir.

SortedMap arayüzünde listelenen diğer iletiler uç değer ve eşlem dilimi döndürmek suretiyle görüntü sağlayanlar olmak üzere iki grupta toplanabilir. TreeMap türlü eşlemlerin dengeli ağaçlarla temsil edilmesi sayesinde ucuz maliyetlerle gerçekleştirilebilen bu iletilerden firstKey ve lastKey, sırasıyla, hedef eşlemin ilk ve son anahtar bilgisini döndürür. İkinci gruptaki iletiler, argüman veya argümanlarında belirtilen anahtar bilgileri ile belirlenen anahtar-tutanak çiftlerinden oluşan ve SortedMap tutacağı ile gösterilen eşlem görüntüleri döndürür. Bunlardan subMap, ilk argümanı ile başlayıp ikinci argümanının hemen öncesinde biten eşlem dilimini döndürürken, headMap başlangıçtan argümandaki anahtarın öncesine kadar olan dilimi, tailMap ise argümanındaki anahtar ile başlayıp eşlemin sonuna kadar giden dilimi döndürür.
SortedMap<String, String> adanbye = trSözlük.subMap("a", "b"); // "b" hariç!
SortedMap<String, String> jyeKadar = trSözlük.headMap("j");
SortedMap<String, String> jdenSonra = trSözlük.tailMap("j");
Her üç iletinin de, görüntüleme grubundaki diğer iletiler gibi, yeni bir eşlem yaratmaktansa ileti alıcının gösterdiği eşlemi paylaştırdığı unutulmamalıdır. Bundan dolayı, yukarıdaki kodun işlenmesi sonrasında trSözlük dört farklı tutacak yoluyla değiştirilebilecektir. Mesela, adanbye tutacağı ile gösterilen dilimin herhangi bir eşlemesinin değiştirilmesi trSözlük yoluyla gösterilen eşlemi de etkileyecektir. Ancak; trSözlük yoluyla sözlüğe "eşlem" anahtarı ve anlamının girilmesi sadece jyeKadar ile temsil edilen dilimi etkileyecektir, diğerlerini değil. Ayrıca, hiçbir eşlemin geçerli olduğu dilimin dışındaki herhangi bir anahtara dair bilgiyi eklemekte kullanılamayacağı da bilinmelidir. Örneğin, jdenSonra aracılığıyla "eşlem" anahtarı ve ilişkin anlamın girilmeye çalışılması IllegalArgumentException ayrıksı durumuna neden olacaktır.


Java SE6 ile birlikte eklenen NavigableMap arayüzü, SortedMap'tekilere benzer iletiler sunar; tanımlanan işlevsellik uç değer işleme ve görüntüleme iletilerinden oluşur. Örneğin, SortedMap'ten kalıtlanan firstKey ve lastKey iletilerine ceilingKey, floorKey, higherKey ve lowerKey iletileri eklenmiştir. ceilingKey argümanındaki anahtara eşit veya ondan büyük ilk anahtar değerini döndürürken, floorKey argümanındaki anahtara eşit veya ondan küçük son anahtar değerini döndürür; higherKey ve lowerKey iletileri ise eşitlik denetimi yapmayan, sırasıyla, ceilingKey ve floorKey gibi çalışır.
String cVeyaSonrasındakiİlkSözcük = trSözlük.ceilingKey("c");
String cSonrasındakiİlkSözcük = trSözlük.higherKey("c");
String cVeyaÖncesindekiSonSözcük = trSözlük.floorKey("c");
String cÖncesindekiSonSözcük = trSözlük.lowerKey("c");
Bir diğer ileti grubu, yukarıda adını andığımız iletilerle aynı şekilde çalışmakla birlikte anahtarı döndürmektense Map.Entry türlü bir tutacak aracılığıyla gösterilen eşlemeyi sarmalayan nesneyi döndürür. Bu iletilerin adları, ilişkin iletinin adındaki Key kısmı yerine Entry koymakla elde edilebilir. İstenecek olursa, bu noktadan sonra sarmalanan nesne Map.Entry arayüzündeki iletilerle sorgulanabilir.

NavigableMap arayüzünce eklenen görüntüleme iletilerinden olan descendingKeySet, adının da haykırdığı gibi hedef eşlemdeki anahtarları bir küme içinde döndürür. Ancak, döndürülen kümenin dolaşılması anahtarları keySet'in döndürdüğünün tersi sırada verecektir. Anahtarlara dair görüntüyü döndüren bir diğer ileti olan navigableKeySet, keySet'e daha da çok benzer; iki iletinin döndürdükleri kümenin içeriği ve sırası tümüyle aynıdır. Ne var ki, keySet Set dönüş türüne sahipken, navigableKeySet NavigableSet döndürür.

Tanıdık gelecek bir diğer ileti grubu dilim döndüren görüntüleme iletileridir. NavigableMap arayüzü, SortedMap'ten kalıtladıklarına ek olarak, uç değerlerin dahil edilip edilmeyeceğini belirleyen ekstra parametrelere sahip headMap, subMap ve tailMap adlı üç ileti destekler. Söz konusu iletiler, her bir uç değeri takiben geçirilen boolean değerlerle döndürülecek dilimin uç noktalarının nasıl ele alınacağını belirler; true geçirilmesi uç noktayı sonuca katarken, false geçirilmesi dışlar. Bu iletilerin bir diğer farkı, SortedMap'ten kalıtlanan aynı adlı iletilerin SortedMap döndürmesine karşılık, NavigableMap döndürmeleridir.

Bir önceki paragrafta anılanlarla ele alınabilecek bir ileti de, hedef eşlemi döndürülen NavigableMap tutacağı vasıtasıyla ters sırada görüntülemeye yarayan descendingMap'tir. Yani, sözlüğümüzü ters sırada işlemek isteyecek olursak, yapmamız gereken aşağıdaki tanımlamadan ibarettir.
NavigableMap<String, String> trSözlük2 = trSözlük.descendingMap();
Değineceğimiz son iletiler, uç değerleri denetleyerek [var olmaları halinde] silen pollFirstEntry ve pollLastEntry iletileridir. pollFirstEntry, hedef eşlemde ilk sırada bulunan eşlemeyi yoklayıp silerken, pollLastEntry son eşlemeyi siler. Her iki ileti de sildikleri eşlemeye dair bilgiyi Map.Entry tutacağı ile döndürürken, eşlemin boş olması halinde null döndürülür.

Uzmanlaşmış Eşlemler


Veri Kapları Çerçevesi, yukarıda anlatılanlara ek olarak içerebileceği anahtarların niteliklerinden dolayı özel bir şekilde gerçekleştirilmek suretiyle daha yüksek performanslı kullanılabilecek iki eşlem sınıfı daha sunar: EnumMap ve WeakHashMap.

Anahtar türünün bir sabit listesi (İng,. enum) olması durumunda, eşlemdeki anahtar sayısı ilişkin sabit listesindeki simgesel sabitlerin sayısı ile sınırlanacaktır. Bu gibi bir durumda, anlattığımız eşlem sınıflarından birini kullanmaktansa, anahtarlarının sabit listesi değerleri olduğunu varsayarak eniyileme yapan EnumMap sınıfının kullanılması daha doğru olacaktır.

WeakHashMap sınıfı da, tıpkı HashMap gibi, kıyım tablosu temelli bir gerçekleştirim sağlar. Ancak; WeakHashMap içine konulabilecek anahtar değerleri WeakReference türünden olmak zorundadır.2 Bu ise tutanakların, eşlem kullanıcısının göndereceği remove iletilerinin yanısıra, çöp toplayıcısının vereceği bir karar sonrasında [kullanıcı kontrolunun dışında] usulca silinebileceği anlamına gelir. Henüz silinmesi istenmeyen bir tutanağın bu sondan korunması kuvvetli bir tutacak ile gösterilmesi sayesinde sağlanabilir.


  1. Kırmızı-siyah ağaçlar, B-tree ailesindeki dengeli ağaçlardan [azami] dört düğümlü olanların, ki bu ağaçlara tepeden aşağıya 2-3-4'lü ağaçlar da denir, ikili ağaç şeklinde gerçekleştirilmiş biçimleridir.
  2. java.lang.ref paketinin Reference köklü sıradüzenindeki sınıfların tutacakları, bir nesne göstermektense bir başka nesnenin tutacağını sarmalayarak onu nesneye çevirir. JSM tarafından özel muameleye tabii tutulan bu nesnelerin kullanım amacı, çöp toplayıcı ile etkileşerek kaynak yönetim sürecine uygulama gereksinimlerine göre müdahele edilmesini olanaklı kılmaktır.