Obje Odaklı Programlama Çerçevesinde Geliştirilen Lineerizasyon Algoritmaları, Elmas Problemi'ni Çözebilir mi?

Bu yazımızda, onyıllardır en öne çıkan programlama paradigmalarından biri olmaya devam eden Obje Odaklı Programlama'yı ve en temel konseptlerinden biri olan Kalıtım'ı, spesifik olarak "Çoklu Kalıtım" ve "Kalıtımsal Heterarşiler"i, inceleyip, "Diamond Problemi" ve bu problemi çözmek için oluşturulan Lineerizasyon Algoritmaları'nı ve bu algoritmaların prensiplerini olabildiğince detaylı bir şekilde ele alacağız. Bir sonraki yazımıza giriş olacak olan bu yazının ardından, C3 Lineerizasyonu'nun Python dilindeki implementasyonunu, çok daha spesifik ayrıntılarıyla inceleyeceğiz.

Obje Odaklı Programlama Nedir?

Programlama dilleri için esasında iki bileşenden oluştukları söylenebilir: Gramer (İng: "syntax") ve Yürütme Modeli (İng: "Execution Model"). Bunlardan ikincisi, programlama dilindeki ögelerin davranışlarını ve böylece bu dilde yazılan bir programın bilgisayar tarafından yürütme (İng: "execution") sürecini ve sonuçlarını spesifize eden modeldir. Programlama paradigmaları ise; gramerin stili, yürütme modelinin işleyiş prensipleri ve programdaki kodların organizasyonel yapısı gibi problemlere olan farklı yaklaşımlarıyla, programlama dillerini kategorize etmek için kullanılan yollardan biridir.

Obje Odaklı Programlama (veya kısaca "OOP"), MIT'de ilk ortaya çıktığı 1950'li yıllardan günümüze uzanan süreçte; Kalıtım, Abstraksiyon, Polimorfizm, Enkapsülasyon, Kompozison gibi konseptleri ile, programlamayı kolaylaştırması, ihtiyaç duyulan kod boyutunu azaltması, programın dizaynındaki entegriteyi ve kompleks yapılarla çok daha efektif bir şekilde çalışmayı sağlaması sayesinde, en iyilerden biri, hatta en iyisi, haline gelen bir programlama paradigmasıdır. PYPL Index'inin sıralamasına göre Ağustos 2021 itibariyle dünya çapında en popüler olan ilk 25 programlama dilinin hepsi, ya tamamen ya da kısmen obje odaklıdır.

Obje Odaklı Programlama'yı ve popülerliğini anlamak için, programlama sürecinin kendisini biraz incelemekte fayda vardır: Bir program yazarken yaptığımız şey, basitçe; gerçekliği, bilgisayarların yorumlayabileceği ve yanıt verebileceği bir şekilde modellemektir. Bu modelin tasfir ettiği şeyler; bir şirket çalışanı, geliştirilmekte olan bir robotun mekanik bir parçası veya mikrobiyal bir koloni gibi somut objeler olabileceği gibi, bir web sitesinin arkayüzündeki bağıntısal yapılar ya da bir varitabanının kayıtlarının çeşitli çerçeve (İng: "framework") ortamlarındaki temsilleri gibi oldukça soyut objeler de olabilir. Ancak nereden bakılırsa bakılsın; her "şey", statik ve dinamik karakteristikleri olan bir objedir.

Obje Odaklı Programlama'nın merkezindeki "obje" konsepti de, aynı bu şekilde, statik karakteristikler olan dataları "attributes" formunda, dinamik karakteristikleri oluşturan kodları "methods" formunda tutarak, bahsi geçen modellemenin en efektif şekilde oluşturulmasına olanak sağlıyor. Genel bir tasfir sunmak için, basmakalıp bir metafor olacak olsa da, insanların ten veya göz rengi gibi fenotipik karakteristiklerin "attribute" olarak, oturulan koltuktan kalkılıp mutfağa gidilip su içilmesi süreci için beynin oluşturduğu algoritmanın da "method" olarak modellenebileceği örnekleri verilebilir.

Öte yandan, objeler arasındaki ilişki, en az objelerin kendisi kadar gerçekliğin bir parçasıdır. Obje Odaklı Programlama ise bunu iki farklı şekilde sağlar: Bazı dillerde "prototip bazlı", diğerlerinde ise "sınıf bazlı". Prototip bazlı paradigmada esas olan objelerin kendileri, objlerin prototipleri ise başka objeler, böylece hem objeyle prototipi arasındaki ilişki, hem de denklik sınıfı (İng: "equivalence class") konseptiyle objenin, o objenin prototipini kendi prototipi olarak kabul eden diğer objeler ile ilişkisi sağlanmış olur. Yani $\text{Hormon}$, $\text{Epinefrin}$ ve $\text{Melatonin}$ isimlerinde üç farklı objenin arasındaki ilişki, $\text{Epinefrin}$ ve $\text{Melatonin}$ objelerinin prototiplerinin $\text{Hormon}$ objesi olarak tanımlanmasıyla oluşturulabilir. Sınıf bazlı paradigmada ise, verdiğimiz bu örnek, $\text{Hormon}$ isminde bir sınıf ve bu sınıfın üyeleri olan $\text{Epinefrin}$ ve $\text{Melatonin}$ objeleri halini alırdı. Örneğin bir sonraki yazımızda C3 implementasyonu üzerinde duracağımız Python dili de, bu şekilde sınıf bazlı olan dillerden biridir.

Obje Odaklı Programlama'nın öncülerinden, ve aynı zamanda bir biyolog olan, Alan Kay'in; objeleri, biyolojik hücreler gibi olan yapılar olarak düşündüğünden bahsetmesini esas alarak, üzerinden ilerleyeceğimiz örnekler zincirinin ilk halkası ile başlayalım.

Yukarıdaki $\text{Cell}$ ("hücre") sınıfı, oluşturulmak istenen herhangi bir hücre objesi için bir kalıp formunda, böylece spesifik hücre objeleri oluşturulabiliyor ve oluşturulan hücreler, klasın içinde tanımlanan replikasyon, metabolik reaksiyon, DNA onarımı, protein sentezi ve hareket etme metotlarını kullanabiliyor.

Obje Odaklı Programlamada "Kalıtım" Nedir?

Aslına bakarsak, örnekte verilen hücre objeleri aynı sınıfın üyeleri olabilmek için birbirlerinde oldukça farklıdır. Tabii eğer hücre çeşitlerinin farklılıklarının önemseneceği çözünürlüğe sahip bir ortamda çalışıldığı varsayılırsa... Yani her biri fonksiyonları ve insan fizyolojisinde oynadıkları rol açısından o kadar ayrılar ki ortak fonksiyonları olan, yukarıda verilen, metotların devamında verilebilecek olan daha spesifik metotlar her biri için farklı olurdu: epitel hücre için mukus sentezi veya sinir hücresi için de sinaps oluşturma gibi.

Ancak bütün bu birbirinden farklı metodları $\text{Cell}$ sınıfına eklemek, oluşturulan kas hücrelerine mukus sentezleme veya bağdoku hücrelerine sinaps oluşturma yetisi vermek anlamına geliyor. Her ne kadar, hücre objelerinin, normalde kendilerinin gerçekleştiremiyor olmaları gereken, başka çeşit hücre objelerinin prosesleri ile ilişkilerini engellemek için bu metodlar, sinaps oluşturma metodunun içeriğini sadece sinir hücresi objelerinin yürütmesini, yani sinir hücresi olmayan hücrelerin bu metodu çağırmasının sonuç üretmemesini sağlamak gibi modifikasyonlarla düzenlenebilecek olsa da; bu durum, objelerin metotlara erişimini tamamen engelleyemediğinden, tam bir spesifikasyon sağlayamazdı: Bir ortama bir kas hücresi objesi oluşturmak için $\text{Cell}$ sınıfı "import" edildiğinde ("çağrıldığında"), bu objeyle hiç bir alakası olmayan metotların hafızada yer kaplayacak olması gibi...

Dolayısıyla, eğer belirttiğimiz gibi hücre çeşitlerinin farklılıklarının önemseneceği çözünürlükte bir ortamda çalışılıyorsa, her bir çeşit obje için yeni bir sınıf oluşturmak daha mantıklıdır. Ancak oluşturulan bu dört yeni sınıf, kendi çeşitlerine özgü süreçleri ve verileri barındıracağı gibi, $\text{Cell}$ klasındaki, genel olarak hücre olmakla ilgili olan, proses ve dataları da içermelidir.

İşte tam bu noktada, dört farklı klasın her birisine $\text{Cell}$ klasındaki aynı alan (İng: "field") ve metotları ayrı ayrı eklemek yerine, bu klassları $\text{Cell}$ klasıyla, $\text{Cell}$ klasındaki bilgileri "miras almaları" veya "kalıtmaları" (İng: "inherit") için ilişkilendirerek Obje Odaklı Programlama'nın dört ana konseptinden biri olan Kalıtım'dan yararlanabiliriz.

Kalıtım ve Özellikleri

Obje Odaklı Programlama'da Kalıtım, benzer uygulamaları (İng: "implementation") sürdürebilmek için, bir sınıfın başka sınıflar için temel oluşturmasını sağlayan mekanizmadır.

İki temel uygulamasından biri olan kod yeniden kullanımı (İng: "code reuse"), yukarıdaki örnekteki "base class" olan tek bir $\text{Cell}$ klasının içeriğinin, $\text{Cell}$ sınıfını kalıtan bir çok alt sınıf tarafından kullanılması gibidir. Benzer şekilde, $\text{Cell}$ sınıfında bir değişiklik yapıldığında, bir alan veya metodun silinmesi veya yeni bir tanesinin eklenmesi ya da değerlerinin veya uygulamalarının değiştirilmesi gibi, bu değişikliği $\text{Cell}$ sınıfını kalıtan bütün klaslarda ayrı ayrı yapmak yerine, bu sınıflar zaten en başında $\text{Cell}$ sınıfı ile kalıtımsal olarak ilişkilendirildiği için, değişikliklerin simültane bir şekilde kalıtım yapan sınıflarda da gerçekleşmesi, kod yeniden kullanımıyla ilişkili olan uygulamalardan birisidir.

Diğeri ise "üzerine yazma" (İng: "overriding") olarak bilinen, kalıtılan metotlara yeni uygulamaların sağlanmasıdır. Böylece ortak bir takım prosesleri farklı şekillerde gerçekleştirecek olan klaslar bu prosesleri tek bir sınıftan kalıtıp, kendilerine göre modifiye edebilirler veya tamamen yeni bir uygulama sağlayabilirler.

$\text{Flagellate}$ ve $\text{Ciliate}$ sınıflarının, $\text{Cell}$ sınıfından kalıttıkları $move()$ metoduna sırasıyla, kamçıyla hareket etme ve sillerle haraket etme proseslerini implement etmeleri buna örnek verilebilir. Kendisinden kalıtılan sınıf, kalıtan sınıfın süper-sınıfı (İng: "superclass") veya temel sınıfı (İng: "base class") olarak, kalıtan sınıf da kalıtılan klasın alt-sınıfı (İng: "subclass") veya türev sınıfı (İng: "derived class") olarak isimlendirilir.

Yazımızın ilerleyen bölümlerinde bu terimler için, "süpersınıf" ve "altsınıf" kelimelerini kullanacağız.

Çoklu ve Çok Düzeyli Kalıtım

Obje Odaklı Programlama'ya ve Kalıtımsal ilişkilere genel bir bakışın ardından, artık esas problemimizin içerisinde bulunduğu konsepte giriş yapabiliriz. Çoklu Kalıtım, bir sınıfın birden fazla sınıfı kalıtıyor olmasına, Kalıtımsal Heterarşi de ilerde daha detaylı inceleneceği üzere, Çoklu Kalıtım içeren organizasyonel sınıf sistemlerine verilen genel isimdir.

Yukarıdaki görselde, aynı anda hem $Y$ hem de $Z$ klasının altsınıfı olan $C$, bu sınıfların her birinin bütün kalıtılabilir elemanlarını yani $Y$ klasındaki $f()$ ve $g()$ metotlarını, $Z$ klasındaki $v$ alanını ve $h()$ metodunu ayrı ayrı kalıtıyor. Peki ya bu süpersınıflar aynı isme sahip iki farklı metot bulundursaydı?

Soru basitçe, $C$ klasının bir objesi tarafından $m()$ metodu çağrıldığında, $Y$ ve $Z$ klaslarındaki, sırasıyla $0$ ve $1$ sonuçlarını döndüren, $m()$ metodlarından hangisine ulaşılacağı ile alakalıdır.

Öncelikle, eğer $C$ klasının kendisi, herhangi bir $m()$ metodu içerseydi, ulaşılacak ilk $m()$ metodu tabii ki de bu metot olurdu. $Y$ ve $Z$ sınıfları arasında yapılacak olan seçim de, $C$ sınıfının ilanında (İng: "declaration") olduğu gibi, ilk kalıtılan $Y$ sınıfı yönünde olurdu. Sonuç olarak, $C$ sınıfının herhangi bir objesi $m()$ metodunu çağırdığında, ilk bakılacak yer $C$ sınıfının kendisidir. Eğer metot burada yoksa, sonraki bakılacak yer $Y$ sınıfı, burada da bulunamaz ise en son bakılacak yer de ikinci süpersınıf olan $Z$ sınıfıdır. Yani $C\to Y\to Z$ şeklinde bir hiyerarşi vardır.

Çoklu Kalıtım içermeyen ama Çok Düzeyli Kalıtım, yani en az bir sınıfın hem süpersınıf hem altsınıf olduğu durumlara verilebilecek en basit örnek de aşağıdaki gibi:

Buradaki öncelik ilişkisi de oldukça yalındır: Bir önceki örnekte de olduğu gibi, $C$ sınıfı kendisinin direkt süpersınıfı olan $Y$ klasından daha spesifik olduğundan dolayı, $C$ sınıfı $Y$'den önce geldiği gibi, $Y$de $Z$'den daha spesifik olduğu için $Z$'yi önceler. Yani bu durumda $C\to Y\to Z$ hiyerarşisi mevcuttur.

Verdiğimiz bu iki örneği birletirdiğimizdeyse aşağıdaki gibi bir graf üretmemiz mümkün olmaktadır:

Böyle bir durumda, birinci örneğe göre $Y$ klasından sonra ikinci süpersınıf olan $Z$ sınıfına ulaşılması gerekirken, ikinci örneğe göre ise $Y$ klasının da süpersınıfı olan $W$ sınıfına ulaşılması gerekmektedir. Belki $Y$sınıfındaki, $W$ sınıfından kalıtılan elemanlar aynı zamanda $Y$'nin de elemanları olduğu için, $W$ sınıfından devam edilmesi gerekecektir. Belki de $Z$ sınıfı $C$'ye $W$'dan daha yakın olduğu ve dolayısıyla daha kuvvetli bir ilişkisi olduğu için, yani direkt süpersınıflarından biri olduğu için, $Z$ klası ile devam edilmesi gerekecektir.

Bu graf, belirsizliğin (İng: "ambiguity") ortaya çıkmaya başladığı ilk durumdur. Ancak asıl belirsizlik, graf daha da karmaşıklaşınca ortaya çıkacaktır. Daha doğrusu, sadece bir adım sonra, $W$ ve $Z$ sınıfları da kalıtımsal olarak ilişkilendirilince işler karışacaktır.

Elmas Problemi ve Lineerizasyon Algoritmaları

Elmas Problemi (İng: "Diamond Problem"), sınıfların, ortak süpersınıfları olan süpersınıflara sahip olduğu "heterarşiler"de (yani "heterojen hiyerarşiler"), bu süpersınıflara hangi sıralama ile ulaşılması gerektiğine dair belirsizliğe verilen isimdir.

Yukarıdaki elmas şeklindeki heterarşide, daha önceki örneklerde de olduğu gibi, $Y$ sınıfının $C$ sınıfından sonraki en spesifik sınıf olduğu açıktır. Ancak $Y$ sınıfından sonra, $Y$sınıfının da süpersınıfı olan $W$ sınıfına mı, yoksa $W$ sınıfına ulaşmadan önce, tıpkı $Y$ sınıfının yaptığı gibi, $W$ sınıfından gelen elemanları modifiye etmiş olma, yani $W$ sınıfındaki elemanların gerçek hallerinden daha yeni olan versiyonlarını içerme ihtimali olan $Z$ sınıfına mı ulaşılması gerektiği oldukça belirsizdir.

Makalemize de ismini veren bu problem; yukarıdaki heterarşi dışında aynı zamanda, genel olarak Kalıtımsal Heterarşiler'de ortaya çıkan ve az sonra incelemeye başlayacağımız Lineerizasyon Algoritmaları'nın uygulanmasını zorunlu kılan belirsizliklere de işaret etmektedir.

Esasında, kalıtımsal bir hiyerarşinin, Çoklu Kalıtım içerdiği zaman bir "heterarşi", yani derecelendirmenin (İng: "ranking") olmadığı ya da derecelendirmenin birçok farklı şekilde yapılabileceği organizasyonel sistem olarak isimlendirilmesinin sebebi, böyle bir yapının bir çok farklı şekilde lineerleştirilebilecek (veya "doğrusallaştırılabilecek") olmasıdır.

Yukarıda gösterildiği gibi, farklı lineerizasyon algoritmaları farklı lineerizasyonlar oluşturarak, kalıtımsal bir heterarşideki klasların metotlarına hangi sıralama ile ulaşılacağını belirlemektedir.

Lineerizasyon Algoritmaları, ürettikleri sonuçlarda birbirlerinden bazı durumlarda ayrılsalar da, çoğunluğu birkaç ortak prensibi takip ederek heterarşileri doğrusallaştırırlar. İlerleyen bölümde bunlardan en yaygın olan ikisini detaylıca inceleyeceğiz.

Lokal Öncelik Sıralaması ve Monotonluk Prensibi

Lokal Öncelik Sıralaması (İng: "Local Precendence Order"), yani sınıf deklerasyonundaki direkt süpersınıfların sıralaması ile tutarlı olan lineerizasyonlar, bu sıralamayı lineerizasyonda da korur. Yani eğer herhangi bir $C$ sınıfının süpersınıfı olan $Y$, diğer süpersınıf olan $Z$'den daha önce kalıtılıyorsa, bir diğer ifadeyle Lokal Öncelik Sıralaması'nda $Y$ sınıfı, $Z$ sınıfını önceliyorsa, $C$ ve $C$'nin bütün altsınıflarının lineerizasyonlarında da $Y$ sınıfı $Z$ sınıfını önceler.

İlk olarak ele alacağımız Dylan Lineerizasyonu ile Elmas Problemi'ne tekrar bakılırsa:

Dylan Lineerizasyonu'nun sonucu olan $C\to Y\to Z\to W$, Lokal Öncelik Sıralaması ile tutarlı olmakla birlikte; $C\to Y\to W\to Z$ ya da $C\to W\to Y\to Z$ sonuçları ile karşılamamasının sebebi ise bu lineerizasyonun monotonluğudur.

Bir lineerizasyonun "monoton" olması; lineerizasyonun uygulandığı herhangi bir sınıf için, o sınıfın kalıttığı bütün elemanların, direkt süpersınıflarından biri tarafından tanımlanmış ya da kalıtılmış olduğu anlamına gelir. Yani eğer lineerizasyon monoton ise, herhangi bir sınıfa uygulandığında elde edilen sonuç, süpersınıflarının lineerizasyonlarının, sıralamaları değiştirilmemiş olarak, genişletilmiş bir versiyonu olur.

Dolayısıyla, Elmas Problemi'ni tekrar ele alacak olursak, $Y$ sınıfının lineerizasyonu $Y\to W$ iken, $Z$ sınıfının lineerizasyonu ise $Z\to W$ olduğundan ötürü, $C$'nin lineerizasyonu da bu lineerizasyonların sıraları değiştirilmemiş bir genişletilmiş versiyonu olmalıdır. Eğer lineerizasyon $C\to Y\to W\to Z$ olursa, $Z$ süpersınıfının lineerizasyonu olan $Z\to W$ sıralaması değiştirildiği için, monotonluk prensibi ihlal edilmiş olacağı gibi, eğer $C\to W\to Y\to Z$ olursa da hem $Y$ ve hem de $Z$ süpersınıflarının lineerizasyonların sıralaması değiştirildiği (İng: "reordering") için, bu durumda da monotonluk prensibi ihlal edilmiş olur.

Lokal Öncelik Sıralaması ve Monotonluk Prensibi oldukça kullanışlıdır ve sezgilerimize uygun sonuçlar üretirler. Ne de olsa ilk olarak, sınıfı tanımlarken oluşturulan süpersınıf sıralamasında başlarda yazılan bir sınıfın metoduna ulaşılmasındansa, sonlarda yazılan bir sınıfın metoduna ulaşılması istenilmeyeceği ve sezgilere ters olduğu gibi, direkt olmayan süpersınıflara, onlar ile asıl sınıf arasında köprü görevi gören direkt süpersınıflardan daha önce ulaşılması da beklenilecek bir sonuç değildir. Ancak bu prensipler doğrultusunda lineerizasyon yapmanın, yani algoritmanın üretebileceği sonuçları sınırlandırmanın, elbette bir pahası vardır: tutarsız (İng: "inconsistent") heterarşiler.

Yukarıdaki heterarşiye Dylan Lineerizasyonu'nu uyguladığımızda, $Y$'nin lineerizasyonunda $W$ sınıfı $V$ sınıfını öncelediği için, $C$'nin lineerizasyonunda da $W$'nun $V$'yi öncelemesi gerekirken, $Z$'nin lineerizasyonunda da $V$ klası $W$ klasını öncelediği için, $C$'nin lineerizasyonunda da $V$'nin $W$'yu öncelemesi gerekir. Yani hem $W{<}_{Dylan(C)}V$ hem de $V{<}_{Dylan(C)}W$ - ki bu bir çelişkidir.

Bu paragraftan itibaren yazıda sadeliğin sağlanması için, herhangi bir $C$ klasının $L$ lineerizasyonunda $X_0$ sınıfının $X_1$ sınıfını önceliyor olduğu, $X_0{<}_{L(C)}{X}_1$ notasyonu ile gösterilecektir.

Ancak monoton olmayan, CLOS gibi lineerizasyonlar içinse bu heterarşiler herhangi bir sorun teşkil etmez.

Yukarıdaki heterarşide, $C$ sınıfının iki süpersınıfı olan $Y$ ve $Z$ sınıflarının lineerizasyonları sırasıyla $Y\to W\to S\to U$ ve $Z\to V\to S$, yani $C$ sınıfının bütün $S$ ve $U$ sınıflarını lineerizasyonunda içeren, süpersınıfları için $S$ sınıf $U$ sınıfını öncelerken, yani $S{<}_{CLOS(Y)}U$, $C$ klasının lineerizasyonunda ise $U{<}_{CLOS(C)}S$ olduğunu görürüz.

Bu monoton olmayan heterarşinin CLOS algoritması ile lineerizasyonu, bir sınıfın bütün süpersınıfları için ikincil olan bir sınıfı kendisi için birincil görmesi gibi sezgilerle tamamen ters bir duruma ve böylece, monoton olmayan algoritmalar ile daha fazla lineerizasyonlar yapılabilecek olsa dahi, monotonluğu ihlal etmenin çok da mantıklı sonuçlara yol açmadığına da güzel ve oldukça basit bir örnektir.

Lokal Öncelik Sıralaması ve Monotonluk Prensibi, önceki örneklerde de gösterildiği gibi, bir lineerizasyonun davranışını belirlemenin en etkili yollarından ikisidir. Ancak bu iki prensibin de ihlal edilmediği ve yine de bir belirsizlikle karşılaşıldığında lineerizasyonun nasıl davranması gerektiğini spesifize etmek için başka yöntemlere de ihtiyaç vardır:

Yukarıdaki heterarşinin lineerizasyonundaki ilk iki adım oldukça açıktır: $C\to Y$. Ancak daha sonrasında eğer $W$ ve ardından $Z$ ile devam edilirse, Lokal Öncelik Sıralaması bozulmadığı gibi, Monotonluk Prensibi de herhangi bir şekilde ihlal edilmiş olmayacaktır. Tam tersi, yani önce $Z$ ve ardından $W$ ile devam edilirse de yine aynı şekilde ne Lokal Öncelik Sıralaması ne de Monotonluk Prensibi açısından bir sorun çıkacaktır.

Böyle bir durumda CLOS ve Dylan aynı yöntemi izler: Çıktı sekansı (İng: "output sequence"), yani lineerizasyonun o ana kadar oluşturulmuş olan versiyonu, içerisindeki en son elemana herhangi bir direkt altsınıfı en yakın olan sınıfı seçer. Yani bu belirsizlikle karşılaşıldığı ana kadar üretilen lineerizasyon olan $C\to Y$ dizisinin en son elemanı olan $Y$ sınıfına en yakın altsınıfa sahip olan, zaten direkt olarak $Y$ sınıfı kendisinin de bir altsınıfı olduğu için, $W$ sınıfı seçilir. Daha sonrasındaysa $V$ sınıfı$Z$'nin süpersınıfı olduğu için, önce $Z$, sonrasında ise $V$ ile devam edilmesi gerekir. Böylece tam lineerizasyon, $C\to Y\to W\to Z\to V$ şeklinde ifade edilir.

CLOS ve Dylan lineerizasyonları ve monotonlukları ile ilişkilerine değinmiş olarak, bazı lineerizasyonların Lokal Öncelik Sıralaması ile ilişkilerini inceleyerek devam edebiliriz. LOOPS lineerizasyonun bir varyasyonu olan $L_{LOOPS}^{\ast }$, monotonluğu sağlamak için geliştirilmekle birlikte, Lokal Öncelik Sıralaması ile bazı durumlarda tutarlı olmayan lineerizasyonlardan da bir tanesidir:

Yukarıdaki heterarşide $W$ sınıfı hem üçüncü direkt süpersınıf iken hem de birinci direkt süpersınıfın süpersınıfı. Bu durumda $C$ ile $W$ arasındaki yay, geçişlilik (İng: "transitivity") yayı olarak isimlendirilir; çünkü birinden diğerine ulaşılmasını sağlayan başka bir yönlendirilmiş yol daha vardır.

$L_{LOOPS}^{\ast }$ algoritmasının $C$ sınıfı için ürettiği lineerizasyon ise $C\to Y\to W\to Z\to V$ olarak verilir. Yani $W{<}_{L_{LOOPS}^{\ast }(C)}Z$ olur. Böylece üçüncü direkt sınıfın ikinci direkt sınıfı öncelemesiyle, Lokal Öncelik Sıralaması ihlal edilmiş olur.

Belirtildiği gibi $L_{LOOPS}^{\ast }$ Lineerizasyonunun esas odağı monotonluğu sağlamaktır. Çünkü kendisinden önceki lineerizasyonlardan olan ne CLOS ne LOOPS ne de herhangi bir başkası, monotonluğu daima garanti eden, yani bu prensibi algoritmanın davranışına yerleştirebilmiş lineerizasyonlar değildir. Ancak Lokal Öncelik Sıralaması ile tutarsızlık, bir sınıfın lineerizasyonundaki süpersınıflarının sıralamasını sadece sınıfın deklerasyonundan anlayabilme ve sadece deklerasyonda değişiklikler yaparak lineerizasyon sürecini kontrol edebilme yetisini kaybetmek anlamına gelir.

$L_{LOOPS}^{\ast }$ algoritmasının yazarları ise, bu algoritmanın bir versiyonu olduğu LOOPS lineerizasyonun Lokal Öncelik Sıralaması ile tutarsızlığının, böyle bir tutarsızlığın daima, az sonra inceleyeceğimiz, EPG'nin çelişkili bir bölümüne dair olduğu için, anlamsız olduğunu ileri sürse de, bu tarz çelişkiler yalnızca heterarşiye EPG'yi oluşturmak için eklenen geçişlilik yaylarıyla ilgili ve döngü formunu alıyor.

Genişletilmiş Öncelik Grafı Nedir?

Genişletilmiş Öncelik Grafı (İng: "Extended Precedence Graph" ya da kısaca "EPG") sınıf heterarşisindeki aralarında süpersınıf/altsınıf ilişkisi olmayan klasların da yaylarla birleştirilmesi yoluyla oluşturulan yönlendirilmiş graflara verilen genel isimdir.

Genişletilmiş Öncelik Grafındaki yayların yönleri ise, aralarında süpersınıf/altsınıf ilişkisi olan sınıf çiftleri için süpersınıf yönünde olacak şekilde, aralarında kalıtımsal bir ilişki bulunmayan sınıflar içinse maksimal ortak altsınıflarının Lokal Öncelik Sıralamasına göre belirlenmiş olur.

Herhangi bir heterarşideki aralarında kalıtımsal bir ilişki bulunmayan $E$ ve $F$ klaslarını ele alalım. Bu klasların $M_{EF}$ olarak isimlendireceğimiz maksimal ortak altsınıfları (İng: "maximal common subclasses"), hem $E$ hem de $F$ sınıflarının altsınıfları olup, bu ikisinin altsınıfı olan herhangi bir süpersınıfa sahip olmayan sınıflar - ki heterarşideki esas sınıf olan $C$ sınıfı hem $E$ hem de $F$ sınıflarının altsınıfı olduğu için, bu tanıma uyan en az bir tane sınıf daima mevcuttur.

Eğer $E$ veya $E$'nin herhangi bir altsınıfı, $F$ veya $F$'in herhangi bir altsınıfını, $E$ ve $F$ sınıflarının bütün maksimal ortak altsınıflarının Lokal Öncelik Sıralamasında önceliyorsa, aralarındaki yay $E$ sınıfından$F$ sınıfına doğru yönlendirilmiş olur. Benzer şekilde, eğer $F$ veya $F$'in herhangi bir altsınıfı, $E$ veya $E$'nin herhangi bir altsınıfını, $E$ ve $F$ sınıflarının bütün maksimal ortak altsınıflarının Lokal Öncelik Sıralamasında önceliyorsa, aralarındaki yay $F$ sınıfından $E$ sınıfına doğru yönlendirilmiş olur.

Genişletilmiş Öncelik Grafı, yukarıdaki $(3-4-5-3)$ ilişkisinde olduğu gibi, döngüsel (İng: "cyclic") ilişkiler oluşturabilir. Sadece heterarşiye Genişletilmiş Öncelik Grafı oluşturmak için eklenen yaylardan meydana gelmiş olan bir döngüsel ilişki, aşağıdaki graftaki $(X-Y-Z)$ ilişkisi ile örneklendirilebilir.

Genişletilmiş Öncelik Grafı ve isminin anlamının daha iyi anlaşılabilmesi için, Graf (Çizge) Teorisi yoluyla, şu ana kadar anlatılan çoğu fenomene dair, çok daha teknik bir inceleme gerçekleştirilmelidir. $H$ sembolü ile global kalıtım grafını (İng: "global inheritance graph"), $H_C$ sembolü ile de $H$ grafının sadece $C$ ve $C$'nin süpersınıfları ile sınırlandırılmış kısmını göstereceğiz.

İçerisindeki düğümleri (İng: "node") obje odaklı bir programlama dilinin sınıfları olan bu grafın yönlendirilmiş yayları ise üzerine tanımlanmış olan ve ${<}_H$ ile gösterilen kalıtım bağıntısı (İng: "inheritance relation") ile belirlenir. Bu bağıntı dönüşlü (İng: "reflexive") bir bağıntıdır. Bu özelliği, $H$ içerisindeki her $J$ sınıfı için $J{<}_{H}J$ olduğu anlamına gelir. Yani $J$ sınıfının kendi elemanları, kendisi tarafından kalıtılmış gibidir.

Ancak biz, bu notasyonu bu durumun dışında kullanıyor olacağız. Yani $C_0{<}_H{C}_1$ ise $C_0\ne C_1$ ve $C_0$ sınıfı $C_1$ sınıfının bir altsınıfıdır. Burada kalıtımdan kastedilen konsept, kalıtımın en basit formu olan ve $uim$ olarak göstereceğimiz "standart kalıtım mekanizması" (İng: "uniform inheritance mechanism") yoluyla elde edilen kalıtımdır.

Genel olarak $uim:(C,P)\mapsto C_{(\ni P)}^{\prime }$ notasyonu ile gösterilebilecek olan bu mekanizma, $P$ isimli bir özellik (İng: "property") ya da eleman, alan veya metot gibi, ile bu elemanı içeren $C$ klasından oluşan çifte karşılık olarak, bu sınıfın süpersınıflarından biri olup, bu $P$ elemanını içeren bir $C^{\prime }$ sınıfı çıktısı verir. Bu durumda $C$ klasının $P$ elemanını $C^{\prime }$ klasından kalıttığı söylendiği gibi, $C.P==C^{\prime }.P$ notasyonuyla gösterebileceğimiz şekilde $C$ klasındaki $P$ elemanın değeri ya da içeriği de kalıtılmış olduğu $C^{\prime }$ klasındaki $P$ elemanın değerine ya da içeriğine eşit olmuş olur.

$L$ ile göstereceğimiz lineerizasyon algoritması ise $H$ içerisindeki bir sınıf olan $C$'yi girdi olarak alıp, $C$'nin süpersınıflarının sıralanmış bir listesini çıktı olarak veren bir fonksiyondur. Böylece bu liste, programlama dili tarafından tekli kalıtım hiyerarşisi (İng: "single inheritance hierarchy") olarak yorumlanabilip, $C$ sınıfı $P$ elemanını bu liste içerisinde $P$'yi içeren ilk süpersınıftan kalıtmış olur.

Lokal Öncelik Sıralaması ise, programda yazılı olan klas deklerasyonundaki süperklasların, genelde soldan sağa doğru en spesifik olandan en az spesifik olana doğru ilerleyen sıralamasıdır. $H$ içerisindeki herhangi bir $C$ sınıfının Lokal Öncelik Sıralamasını $pre{c}_C$, $H$ grafındaki bütün sınıfların Lokal Öncelik Sıralamasınin birleşimini ise $prec$ sembolü ile göstereceğiz. Yani $prec={\bigcup }_{C\in H}pre{c}_C$ olarak verilir. Buna bağlı olarak, $H$ grafındaki herhangi iki $C_0$ ve $C_1$ sınıfı için $C_0{<}_{prec}{C}_1$ olması, $H$ grafındaki en az bir $C$ sınıfı için $C_0{<}_{pre{c}_C}{C}_1$ olduğu anlamına gelir.

$prec$ üzerinde tanımlı bir diğer bağıntı ise ${<}_{path}$ bağıntısıdır. ${\lambda }_0=(\Pi C{C}_0...C_n)$ ve ${\lambda }_1=(\Pi C{C}_1...C_m)$ ortak ön bölüme (İng: "prefix") sahip, $C_0$ ve $C_1$ klaslarına kadarki $\Pi C$ ile gösterilen altlisteleri aynı olan, graf içerisindeki yönlendirilmiş iki yol (İng: "path") olmak üzere, eğer $C_0{<}_{pre{c}_C}{C}_1$ ise ${\lambda }_0{<}_{path}{\lambda }_1$ olur.

Şimdi, Genişletilmiş Öncelik Grafını oluşturmamızı sağlayan ve $prec$'in bir genişletilmesi ya da uzantısı (İng: "extension") olan ${<}_e$ bağıntısından bahsedebiliriz. $J_0$ ve $J_1$ sınıfları $H_C$ içerisinde ve aralarında kalıtımsal bir ilişki olmayan, yani ${<}_H$ bağıntısı ile karşılaştırılamayan ve $H_C$ içerisindeki ilişkileri yolu ile karşılaştırmak istediğimiz iki sınıf olsun. Eğer ortak bir direkt altsınıfları varsa, ismi $M_{01}$ olsun, bu sınıflar ortak direkt altsınıflarının Lokal Öncelik Sıralaması yoluyla, yani ${<}_{pre{c}_{M_{01}}}$ bağıntısı ile karşılaştırabilir.

Eğer ortak bir direkt altsınıfları yok ise, sezgisel olarak izlenmesi gereken yöntem, kendilerine en yakın ortak subklası yani maksimal ortak altsınıfı bulup bu klasın Lokal Öncelik Sıralaması yoluyla karşılaştırmayı yapmaktır. Bir ortak altsınıfın maksimal olması, daha önce de belirtildiği gibi, bu sınıfın hiçbir süpersınıfının bahsi geçen sınıf çiftinin ortak bir altsınıfı olmadığı anlamına geliyor. Yani, $M_{01}$ sınıfı $J_0$ ve $J_1$ sınıflarının maksimal ortak altsınıfı ve ${\lambda }_0=(M_{01}...J_0)$ ve ${\lambda }_1=(M_{01}...J_1)$ olmak üzere, eğer ${\lambda }_0{<}_{path}{\lambda }_1$ ise $J_0{<}_e{J}_1$ deriz. Böylece $H_C$ grafına, ${<}_e$ bağıntısı ile oluşturulan yaylar eklenerek, $T_C$, yani $C$ klasının Genişletilmiş Öncelik Grafı elde edilebilir.

Bir lineerizasyonun Genişletilmiş Öncelik Grafı ile tutarlı olması, lineerizasyondaki her bir sınıf ile lineerizasyonda bu sınıfın sonrasında gelen her bir sınıf arasında Genişletilmiş Öncelik Grafındaki yönlendirilmiş yayların oluşturduğu bir yol olduğu anlamına gelir. Genişletilmiş Öncelik Grafının döngüsel ilişkiler içerdiği durumlarda; kendisi ile tutarlı lineerizasyonları, döngülerin içerisindeki sınıflar arasında bir sıralama yapmaya zorlamazken, birlikte herhangi bir döngünün içinde bulunmayan sınıf çiftleri içinse belirtildiği şekilde bir sıralamayı gerektirir.

Genişletilmiş Öncelik Grafının döngüsel olmadığı durumlarda LOOPS ve CLOS aynı sonuçları ürettikleri gibi, bu sonuçlar aynı zamanda monotonluğu da korur. Ancak, $L_{LOOPS}^{\ast }$ Lineerizasyonu'nun aksine, Dylan Lineerizasyonu (ki CLOS için de aynısı geçerli), Genişletilmiş Öncelik Grafı ile daima tutarlı değildir ve bu durum, sezgilerle zıtlaşan bazı sorunlara yol açabilir:

Yukarıdaki heterarşi için Dylan Lineerizasyonu $C\to Y\to Z\to U\to V\to W$ verir. Yani $C$'nin $W$'ya ulaşmasını sağlayan $Y$ sınıfı, $V$'ye ulaşmasını sağlayan $Z$ sınıfını öncelemesine rağmen, yine de $V{<}_{Dylan(C)}W$ olur. Dolayısıyla $C$ klası, $W$ ve $V$ sınıfından kalıttığı ve farklı uygulamalara sahip bir eleman açısından birinci süpersınıfı olan $Y$ gibi davranmaktansa, ikinci süpersınıfı olan $Z$ gibi davranacaktır - ki bu durum Lokal Öncelik Sıralamasıyla tutumlu olan Dylan gibi bir lineerizasyondan beklenilecek bir sonuç olmaktan oldukça uzaktır.

Oysaki eğer Dylan Lineerizasyonu Genişletilmiş Öncelik Grafı ile tutarlı olsaydı, $W$ ile $V$'nin maksimal ortak altsınıfı, aslında tek ortak altsınıfı olan $C$ sınıfının Lokal Öncelik Sıralamasında, $W$'nun altsınıfı olan $Y$, $V$'nin altsınıfı olan $Z$'yi öncelediği, yani $Y{<}_{pre{c}_{M_{WV}=C}}Z$ olduğu için, Genişletilmiş Öncelik Grafında da $W{<}_{e}V$ olup, $C$'nin lineerizasyonu da bu duruma paralel bir sıralamaya sahip olacağı için, yukarıdaki gibi sezgilere zıt bir sonuç elde edilmiş olmayacaktı.

Sonuç olarak, gösterildiği üzere, Dylan Lineerizasyonu, Lokal Öncelik Sıralaması ve Monotonluk Prensibi ile tutarlıdır ama Genişletilmiş Öncelik Grafı ile tutarsızdır. Öte yandan $L_{LOOPS}^{\ast }$ Lineerizasyonu ise Monotonluk Prensibi ve kısmen Genişletilmiş Öncelik Grafı ile tutarlıdır ama Lokal Öncelik Sıralaması ile tutarsızdır.

Eğer bir şekilde bu üç prensibin hepsiyle aynı anda tutarlı bir algoritma oluşturulabilseydi, sözünü ettiğimiz bütün lineerizasyonların ürettiklerinden çok daha efektif sonuçlar üretilebilirdi. Bir sonraki yazımızda bu problemi inceliyor olacağız.