Soyut Veri Tipleri

Programlama dillerinin, programcılarına, kendi veri yapılarını oluşturabilme yetkinliğini vermesinin ilk örneği 1975’te bir MIT profesörü olan Barbara Liskov tarafından geliştirilen CLU isimli programlama diliyle gerçekleşmiştir. Kullanıcı-tanımlı tip (user-defined type) ya da soyut veri tipi (abstract-data type) isimleri verilen bu yapılar ile kullanıcılar, dildeki integer, char gibi temel veri tiplerini kullanarak, daha karmaşık tipler oluşturabilmektedirler. Soyut veri tiplerinni en tipik örnekleri olan yığın (stack) ya da kuyruk (queue), programlarda ancak soyut veri yapılarıyla tanımlanabilirler. Modern uygulamalarda da örneğin bir müşteri kavramı ve onun adresi bu şekilde kurgulanan soyut veri tipleriyle ifade edilebilirler.

Soyut veri tipleri, sadece karmaşık verileri ifade etmekle kalmaz, aynı zamanda bu veri tipleri üzerinde uygulanabilecek operasyonları, yordamları ya da  fonksiyonları da ifade eder. Yığın soyut veri tipiyle oluşturulan bir tabak yığınına, en üste yeni bir tabak koymak, almak ya da kaç tane tabak olduğunu sormak gibi.  Çoğu zaman bu operasyonlara, soyut veri tipinin davranışları (behavior) ya da hizmetleri (services) denir. Bir soyut veri tipindeki operasyonların nasıl çalıştığı, o soyut veri tipi üzerinde çalışan müşteri kodundan (client code) bağımsızdır. Yani soyut veri tipinin operasyonlarının koduna, dışarıdan ulaşılamaz;  sadece operasyon, o tipin müşterileri tarafından çağrılabilir, soyut veri tipi üzerinde o operasyonu çağıran müşteri kodunun, operasyonun iç yapısını bilmesi mümkün ve gerekli değildir. Dolayısıyla soyut veri yapıları, tanımlarında ifade ettikleri veri yapılarını ve onlar üzerinde çalışacak operasyonları ya da o tipin dışarıya verdiği hizmetleri, bir paket içinde bir araya getirmektedir. Bu paketlemeye, kapsülleme (encapsulation) denir.

Programda ve çalışma zamanında (run-time), kapsüllenmiş bir soyut veri tipini kullanarak, o tipten üretilmiş bir değişkene  ise nesne (object ya da instance) denir. Örneğin, Müşteri, bir soyut veri tipidir ve no, isim ve soyisim gibi üç tane veri alanı vardır. Müşteri soyut veri tipinden çalışma zamanında, bilgileri (no=0, isim=Akın, soyisim=Kaldıroğlu) olan bir nesne oluşturulabilir. Benzer şekilde ayni tipten, bilgileri (no=1, isim=Salih, soyisim=Taşçı) olan bir başka nesne daha oluşturulabilir. Bu şekilde bütün müşteriler bu tipten nesneler olarak çalışma zamanında, Müşteri tipinden yaratılabilir. Dolayısıyla bütün müşteri nesnelerinin kendi no, isim ve soyisim değişkenleri ve bu değişkenlerin değerleri olacaktır.

Müşteri tipinin tanımladığı, örneğin alışVerişYap adındaki bir operasyon da bu tipten nesnelerin alış-veriş yapmalarını modeller. Bir soyut veri tipi üzerinde tanımlanan operasyonların hepsine birden, o tipin arayüzü (interface) denir. Dolayısıyla müşteri kodları (client code), bir soyut veri tipinden, o tipin arayüzünü kullanarak hizmet alır.

Aşağıda, yığın soyut veri tipi ile üzerindeki iki operasyon resmedilmiştir. Yığının, Son-Giren-İlk-Çıkar (Last-In-First-Out, LIFO) modelinde çalıştığını unutmayın.

Bu şekilde çalışan bir Yığın soyut-veri tipi geliştirdiğimizi düşünelim. Bu tipin üzerinde şöyle operasyonlar ya da davranışlar olacaktır:

• push: Gösterimdeki put operasyonuna karşılık gelmektedir ve yığına, operasyona geçilen nesneyi ekler
• pop:   Gösterimdeki remove operasyonuna karşılık gelmektedir ve yığından bir nesne çıkarır ki bu da en son konan nesnedir
• pop: Gösterimdeki remove operasyonuna karşılık gelmektedir ve yığından bir nesne çıkarır ki bu da en son konan nesnedir
• clear: Yığını temizler, içindeki bütün nesneleri siler.
• isEmpty: Yığının boş olup olmadığına cevap verir
• isFull: Yığının dolu olup olmadığına cevap verir
• size: Yığında o anda kaç tane nesne olduğunu bilgisini verir
• getCapacity: Yığındaki maximum kapasitesini görüntüler.
• showElements: Yığındaki nesneleri, yığın formatında görüntüler.

Dolayısıyla, Yığın’ın yedi operasyondan oluşan bir arayüzü var demektir. Bir Yığın nesnesi oluşturup, kendisinden bu arayüzler yardımıyla hizmet alan yalancı (pseudo) müşteri kodu ise muhtemelen şöyle olacaktır:

Yigin yigin = new Yigin;

Apple a = new Apple;

Orange b = new Orange;

boolean isEmpty = yigin.isEmpty();

yigin.push(a);

yigin.push(b);

isEmpty = yigin.isEmpty();

int count = yigin.size();

b = (Orange) yigin.pop();

a = (Apple) yigin.pop();

count = yigin.size();

Yukarıdaki yalancı kodda önce bir Yığın nesnesi yaratıldı, ardından da bu nesneye 2 tane, Apple ve Orange nesneleri eklendi. Dikkat edilmesi gereken şeylerden birisi Apple ve Orange’ın da birer soyut-veri tipi olup, a ve b değişkenlerinin bu tiplerden birer nesne oldukları. Ayrıca yalancı koddaki ilk isEmpty() çağrısının false ikincisinin true döndürdüğü, ilk size() çağrısının 2 döndürürken sonrakinin 0 döndürdüğü de açıktır.

Şimdi yukarıdaki yalancı kod yerine daha gerçek kodlarla uğraşalım. Bir yığın soyut veri tipi oluşturalım ve bu tip bizim için String nesneleri tutsun. Önce yukarıda sıraladığımız davranışları arayüz olarak ifade edelim:

. . .

// Stack manipulation operations

// Push element at rear

public void push(String newElement);

// Pop element from front

public String pop();

// Remove all elements from stack

public void clear();

// Stack status operations

// Is stack empty?

public boolean isEmpty();

// Is stack full?

public boolean isFull();

// How many elements in stack?

public int size();

// Capacity of stack?

public int getCapacity();

// Outputs the elements in the stack

// For testing/debugging purposes

public void showElements();

. . .

Yukarıdaki kod sizi şaşırtmış olabilir? Çünkü bu kodun kendi başına birşey yapması mümkün değildir. Neden? Çünkü yukarıdaki kod, sadece hizmetleri listeliyor, bir başka deyişle hizmetlerin arayüzleri var: Yani hizmetlerin her yerden çağrılabileceğini gösteren public anahtar kelimesi, hizmetin döndürdüğü nesnenin tipi (hiçbir şey döndürmüyorsa void anahtar kelimesi), hizmetin ismi ve “(” ile “)” arasında hizmete geçilen parametrelerin listesi. Evet zaten bir davranış ya da hizmet temelde iki şeyden oluşur: Arayüzü (interface) ile gerçekleştirmesi (implementation). Arayüz yukarıdaki dört elemandan oluşur ve hizmetin “ne”liğini ifade eder. Arayüz, tip ile ondan hizmet alan müşterileri arasındaki bir anlaşmadır (agreement ya da contract) ya da protokoldur (protocol). Bir tipten üretilen nesneler, o tipin arayüzünde listelenen ve söz verilen davranışları ya da hizmetleri yerine getirirler. Gerçekleştirme ise hizmetin “nasıl”lığıdır. Yani “hizmet nasıl yerine getirilecek?” sorusunun cevabı hizmetin gerçekleştirilmesidir. Örneğin Java’da yazılan hizmetler için ki bunlara biz Java’cılar metot demeyi tercih ederiz, gerçekleştirme kısmı “{” ile “}” arasında kalan kısımdır. Bunun dışındakiler o metotun arayüzüdürler.

Bu noktada daha fazla ilerlemeden bir konuyu açıklığa kavuşturmak gerekiyor. Davranış, hizmet, arayüz, fonksiyon (function), metot (method), yordam, alt yordam (subroutine), prosedür (procedure). Yetmedi, arayüz, anlaşma ve protokol çıktı 🙂 Nedir bunlar? Hepsi aynı şeyin farklı ifadeleri mi? Şöyle açıklayayım: Pek çoğunuzun fonksiyon dediği şeye benim davranış ya da operasyon demekte ısrar etmemin sebebi :), kavramsal ile somut dünyayı ayırma isteğimdir. Sizin de farkedeceğiniz gibi, soyut veri tiplerinin yetkinliklerini, ihtiyaçlar seviyesinde konuşurken davranış ya da servis olarak ifade ederken, tasarım seviyesine inince operasyon ya da servis olarak bahsediyorum. Kodlama yani gerçekleştirme (implementation) seviyesinde ise artık programlama dili seviyesindeyiz demektir. Dolayısıyla kullandığınız dilin kültürüne göre bir kelime kullanmanız gerekiyor. Örneğin Pascal yazanlar buna prosedür ya da C++, .Net ya da Cobol programcıları aynı şeye fonksiyon derlerken Fortran’cılar hem subroutine hem fonksiyon diyebilirler. Java’cılar ise Smalltalk geleneğine uyarak, nesnelerin davranışlarına metot demeyi tercih etmektedirler. Bir tipin ya da nesnenin (dikkat edin burada da nesne ile tipi birbirlerinin yerine kullandım 🙂 ) sağladığı hizmetlerin bütününe de kavramsal seviyede arayüz denir. Anlaşma ya da protokol ise arayüz kavramının anlaşılması için kullanılan diğer yakın anlamlı kelimelerden başka birşey değildir. Tek bir davranış ya da hizmetten konuşuyorsak, yine o hizmetin arayüzünden bir önceki paragrafta sayılan dört elementin toplamı olarak bahsedebiliriz.

Peki şimdi konumuza geri dönelim. Yığın tipimizin davranışlarını ya da arayüzünü belirledik. Şimdi de bu arayüzü gerçekleştirecek kodu yazalım. Aşağıdaki böyle bir yığın tipinin Java’da, iç yapısında dizi kullanarak gerçekleştirilmiş kodudur. Tipin ismi StringStackImplementation‘dır:

public class StringStackImplementation {
	// Default maximum stack size
	private static final int MAX_STACK_SIZE = 10;

	private String[] array = new String[MAX_STACK_SIZE];
	private int pointer = MAX_STACK_SIZE - 1;

	// Stack manipulation operations
	// Push element at rear
	public void push(String newElement) {
		if (pointer >= 0) {
			array[pointer] = newElement;
			pointer--;
		}
	}

	// Pop element from front
	public String pop() {
		String element = null;
		pointer++;
		if (pointer < MAX_STACK_SIZE) {
			element = array[pointer];
			array[pointer] = null;
		}
		return element;
	}

	// Remove all elements from stack
	public void clear() {
		for (int i = 0; i < MAX_STACK_SIZE; i++) {
			array[i] = null;
		}
		pointer = MAX_STACK_SIZE - 1;
	}

	// Stack status operations
	// Is stack empty?
	public boolean isEmpty() {
		if (pointer == MAX_STACK_SIZE - 1)
			return true;
		else
			return false;
	}

	// Is stack full?
	public boolean isFull() {
		if (pointer == -1)
			return true;
		else
			return false;
	}

	// How many elements in stack?
	public int size() {
		return MAX_STACK_SIZE - pointer - 1;
	}

	// Capacity of stack?
	public int getCapacity() {
		return MAX_STACK_SIZE;
	}

	// Outputs the elements in the stack
	// For testing/debugging purposes only
	public void showElements() {
		System.out.println("\n" + size() + " elements in the stack:");
		for (int i = 0; i < MAX_STACK_SIZE; i++) {
			System.out.println(i + ": " + array[i]);
		}
	}
}

Bu müşteri kodu, StackTest, çalıştırıldığında çıktısı aşağıdaki gibidir:

0 elements in the stack:

0: null

1: null

2: null

3: null

4: null

5: null

6: null

7: null

8: null

9: null

1 elements in the stack:

0: null

1: null

2: null

3: null

4: null

5: null

6: null

7: null

8: null

9: Selam

2 elements in the stack:

0: null

1: null

2: null

3: null

4: null

5: null

6: null

7: null

8: abi

9: Selam

Size of stack: 2

10 elements in the stack:

0: gidiyor

1: Nasil,

2: naber?

3: senden

4: Iyilik

5: ne yok?

6: Ne var,

7: naber?

8: abi

9: Selam

gidiyor

9 elements in the stack:

0: null

1: Nasil,

2: naber?

3: senden

4: Iyilik

5: ne yok?

6: Ne var,

7: naber?

8: abi

9: Selam

Nasil,

8 elements in the stack:

0: null

1: null

2: naber?

3: senden

4: Iyilik

5: ne yok?

6: Ne var,

7: naber?

8: abi

9: Selam

0 elements in the stack:

0: null

1: null

2: null

3: null

4: null

5: null

6: null

7: null

8: null

9: null

Size of stack: 0

2 elements in the stack:

0: null

1: null

2: null

3: null

4: null

5: null

6: null

7: null

8: naber?

9: abi

Size of stack: 2

Böylece soyut veri yapılarıyla, karmaşık veriler ve o veriler üzerinde çalışacak fonksiyonlar bir paket olarak modellenmiş olurlar. Bu yetkinlik bizi, yordamsal dillerinin makina-merkezli dünyasından daha gerçekçi ve tabi olan bir dünyaya götürür. Çünkü gerçek dünyada çok az şey örneğin sadece bir tamsayı (integer) olarak ifade edilebilir. Demek istediğim, yaş ya da sepetteki ürün sayısı gibi yordamsal dillerde sadece tamsayı tipiyle ifade edilen bütün bu değişkenler aslında bir üst katmanda daha karmaşık bir tipin ya da nesnenin bir alt özelliğidirler. Yani aslında çalışan nesnesi yoksa onun yaşı da yoktur ya da alış-veriş sepeti (shopping cart) yoksa sepette ürün de yoktur, sayısı da yoktur, gibi. Soyut veri tipleri ise bize, yordamsal dillerin sunduğu, int, real, double ya da char gibi basit veri tiplerinden birkaçını bir araya getirerek daha karmaşık ve tabi tipler kurgulamamızı sağlarlar. Bu şekilde ben bir Müşteri tipi oluşturup, yapısını, no, isim ve soyisim gibi üç farklı değişkenle ifade edebilirim. Aksi taktirde pek çok yordamsal dilde olduğu gibi karmaşık olan Müşteri yapısını, onun int tipindeki no’suna indirgemek zorunda kalacağız.

Görüldüğü gibi soyut veri tipleri, gerçek dünyadaki olguları aslına daha uygun resmetme noktasında programcılara çok ciddi bir yetenek kazandırmaktadır. Bu yetkinlik ile programcılar, karmaşık veri yapılarıyla onlar üzerinde çalışacak davranışları, iç yapıları ya da nasıl olduğu dışarıdan görünmeyecek şekilde paket olarak modelleyebilirler. Soyut veri tiplerinin iç yapılarını dışarıdan saklayabilme yeteneğine bilgi saklama (information hiding) denir. Soyut veri tiplerinin iç yapıları, tipin değişkenlerinden oluşur ve genel olarak gerçekleştirme (implementation) olarak adlandırılır.Soyut veri tipleri, değişik dillerdeki değişik mekanizmalarla, bilgi saklama prensibini yerine getirmek üzere iç yapılarına müşteri kodundan erişimi engelleyebilirler.

Erişim kontrolü (access control) yapıları dillerde public, private gibi anahtar kelimelerle ifade edilirler. Örneğin yukarıda örneğini verdiğimiz StringStackImplementation tipinin iç yapısında yani gerçekleştirmesinde bir dizi (array) var ve bu dizi müşteri kodunda, StackTest, StringStackImplementation’dan oluşturulan “stack” isimli nesneye konan String nesnelerini tutuyor. Ama bu tipi tasarlayan ve yazan programcı, erişim kontrolü mekanizmalarını kullanarak bu dizi nesnesine erişmemize izin vermemeli. Çünkü dizi nesnesi StringStackImplementation’ın iç yapısı ve bu iç yapı dışarıdan görülmemeli. Ayrıca StringStackImplementation iki değişkene daha sahip, birisi dizi üzerindeki o anki boş odayı gösteriyor, diğeri ise zaten bir sabit, yığının maksimum kapasitesini gösteriyor. Dizi giibi bu iki değişkene de dışarıdan ulaşım mümkün değil. Sebebi ise soyutlama: Müşteri kodları, StringStackImplementation’ın dışarıya vermeyi vaad ettiği hizmetlerle ki bu hizmetler gerçekleştirme öncesinde arayüz olarak ifade edilmişlerdi, StringStackImplementation nesnelerinden hizmet almalı, bu hizmetleri alırken StringStackImplementation nesnesinin arka tarafta hangi veri yapılarını kullandığını, ne gibi algoritmalara sahip olduğunu bilmemeli. Yani müşteri kodunu yazan programcı, StringStackImplementation nesnesinin arayüzüne dayalı bir programlama (programming to interface) yapmalı, gerçekleştirilmesine dayalı bir programlama (programming to implementation) yapmamalı.

Bu şekilde, hem programlarımızda gerçekliği resmetmede daha iyi bir noktaya gelmiş oluruz hem de farklı programlar arasında bağ (coupling) azalmış olur. Bağın azalması, programların yönetilmesini ve ileride değiştirilmesini kolaylaştırır. Bir program parçası, diğer parçalardan ne ölçüde bağımsızsa, o ölçüde kolayca değiştirilebilir ve değiştirildiğinde de diğer parçalarda sıkıntılar yaşanmaz. Örneğin, yukarıdaki StringStackImplementation nesnesinin iç yapısındaki diziyi kaldırıp yerine bir bağlı-dizi (linked list) koysak, müşteri programlarının değişmesi gerekmez. Çünkü StackTest müşteri kodu, StringStackImplementation ile sadece arayüzü üzerinde haberleşiyor, StringStackImplementation’ın iç yapıları hakkında bilgi sahibi değil. Dolayısıyla bu şekilde programcılar soyutladıkları kavramları önce davranış ya da hizmetleriyle soyutlamayı, tip olarak ifade ederken paketlemeyi (encapsualtion) ve paketin içine tip için gerekli veri yapılarını koymayı, paketlerken de paketin iç yapısını saklamayı (information and implementation hiding) öğrendiler.

Soyut Veri Tipleri ve Diller

1977-1983 yılları arasında ABD Savunma Bakanlığı’nın isteği üzerine, ısmarlama olarak geliştirilen ve ismini, şair Lord Byron’un kızı, aynı zamanda da ilk programcı olarak kabul edilen Ada Lovelace’dan alan ADA dili, gelişmiş bir soyut veri yapısı desteğine sahipti.

“Daha iyi bir C” (A better C) olarak düşünülen C++ ise, Bjarne Stroustrup tarafından 1980’li yılların başında geliştirildi. Daha iyi bir C olması, C++’ın, C’nin nesne-merkezli yapılarla zenginleştirilmiş hali olmasından kaynaklanıyordu. Nitekim bu yüzden C++’ın ilk adı “C with Classes” idi. C++ da soyut veri tiplerini daha zengin mekanizmalarla destekledi.

Bu konuda nesne-merkezli programlamanın nesnesiyle soyut veri tipleri ve onların nesnelerin karıştırılmaması gereklidir. Nesne-merkezli dillerin özellikleri açıklandığında daha iyi anlaşılacağı gibi soyut veri tipleri, karmaşık tipleri yakalamada çok faydalı ve gerekli yapılar olsa bile gerçek anlamda birer nesne değildirler. Daha doğrusu, her nesne bir gerçek veri tipidir ama tersi doğru değildir. Bu durum daha iyi bir şekilde şöyle açıklanabilir: En popüler nesne-merkezli dil olan Java’da soyut veri tipi kavramı çok da fazla söz konusu değildir. Çünkü Java’nın nesne yapıları, zaten en basit haliyle soyut veri tiplerine karşılık gelmektedir. Dahası, C++, Java, C# gibi nesne-merkezli diller, soyut veri tipi kavramını daha ileri götürerek, nesne-merkezli özellikleri bünyelerine katmışlardır. Bu dilleri ise bir sonraki yazımızda ele alacağız.

Toplam görüntülenme sayısı: 1054