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 Hormon\text{Hormon}, Epinefrin\text{Epinefrin} ve Melatonin\text{Melatonin} isimlerinde üç farklı objenin arasındaki ilişki, Epinefrin\text{Epinefrin} ve Melatonin\text{Melatonin} objelerinin prototiplerinin Hormon\text{Hormon} objesi olarak tanımlanmasıyla oluşturulabilir. Sınıf bazlı paradigmada ise, verdiğimiz bu örnek, Hormon\text{Hormon} isminde bir sınıf ve bu sınıfın üyeleri olan Epinefrin\text{Epinefrin} ve Melatonin\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.
Evrim Ağacı'nın çalışmalarına Kreosus, Patreon veya YouTube üzerinden maddi destekte bulunarak hem Türkiye'de bilim anlatıcılığının gelişmesine katkı sağlayabilirsiniz, hem de site ve uygulamamızı reklamsız olarak deneyimleyebilirsiniz. Reklamsız deneyim, sitemizin/uygulamamızın çeşitli kısımlarda gösterilen Google reklamlarını ve destek çağrılarını görmediğiniz, %100 reklamsız ve çok daha temiz bir site deneyimi sunmaktadır.Kreosus
Kreosus'ta her 10₺'lik destek, 1 aylık reklamsız deneyime karşılık geliyor. Bu sayede, tek seferlik destekçilerimiz de, aylık destekçilerimiz de toplam destekleriyle doğru orantılı bir süre boyunca reklamsız deneyim elde edebiliyorlar.
Kreosus destekçilerimizin reklamsız deneyimi, destek olmaya başladıkları anda devreye girmektedir ve ek bir işleme gerek yoktur.Patreon
Patreon destekçilerimiz, destek miktarından bağımsız olarak, Evrim Ağacı'na destek oldukları süre boyunca reklamsız deneyime erişmeyi sürdürebiliyorlar.
Patreon destekçilerimizin Patreon ile ilişkili e-posta hesapları, Evrim Ağacı'ndaki üyelik e-postaları ile birebir aynı olmalıdır. Patreon destekçilerimizin reklamsız deneyiminin devreye girmesi 24 saat alabilmektedir.YouTube
YouTube destekçilerimizin hepsi otomatik olarak reklamsız deneyime şimdilik erişemiyorlar ve şu anda, YouTube üzerinden her destek seviyesine reklamsız deneyim ayrıcalığını sunamamaktayız. YouTube Destek Sistemi üzerinde sunulan farklı seviyelerin açıklamalarını okuyarak, hangi ayrıcalıklara erişebileceğinizi öğrenebilirsiniz.
Eğer seçtiğiniz seviye reklamsız deneyim ayrıcalığı sunuyorsa, destek olduktan sonra YouTube tarafından gösterilecek olan bağlantıdaki formu doldurarak reklamsız deneyime erişebilirsiniz. YouTube destekçilerimizin reklamsız deneyiminin devreye girmesi, formu doldurduktan sonra 24-72 saat alabilmektedir.Diğer Platformlar
Bu 3 platform haricinde destek olan destekçilerimize ne yazık ki reklamsız deneyim ayrıcalığını sunamamaktayız. Destekleriniz sayesinde sistemlerimizi geliştirmeyi sürdürüyoruz ve umuyoruz bu ayrıcalıkları zamanla genişletebileceğiz.Giriş yapmayı unutmayın!
Reklamsız deneyim için, maddi desteğiniz ile ilişkilendirilmiş olan Evrim Ağacı hesabınıza üye girişi yapmanız gerekmektedir. Giriş yapmadığınız takdirde reklamları görmeye devam edeceksinizdir.
Yukarıdaki Cell\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ı Cell\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 Cell\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, Cell\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 Cell\text{Cell} klasındaki aynı alan (İng: "field") ve metotları ayrı ayrı eklemek yerine, bu klassları Cell\text{Cell} klasıyla, Cell\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 Cell\text{Cell} klasının içeriğinin, Cell\text{Cell} sınıfını kalıtan bir çok alt sınıf tarafından kullanılması gibidir. Benzer şekilde, Cell\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 Cell\text{Cell} sınıfını kalıtan bütün klaslarda ayrı ayrı yapmak yerine, bu sınıflar zaten en başında Cell\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.
Flagellate\text{Flagellate} ve Ciliate\text{Ciliate} sınıflarının, Cell\text{Cell} sınıfından kalıttıkları move()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 YY hem de ZZ klasının altsınıfı olan CC, bu sınıfların her birinin bütün kalıtılabilir elemanlarını yani YY klasındaki f()f() ve g()g() metotlarını, ZZ klasındaki vv alanını ve h()h() metodunu ayrı ayrı kalıtıyor. Peki ya bu süpersınıflar aynı isme sahip iki farklı metot bulundursaydı?
Soru basitçe, CC klasının bir objesi tarafından m()m() metodu çağrıldığında, YY ve ZZ klaslarındaki, sırasıyla 00 ve 11 sonuçlarını döndüren, m()m() metodlarından hangisine ulaşılacağı ile alakalıdır.
Öncelikle, eğer CC klasının kendisi, herhangi bir m()m() metodu içerseydi, ulaşılacak ilk m()m() metodu tabii ki de bu metot olurdu. YY ve ZZ sınıfları arasında yapılacak olan seçim de, CC sınıfının ilanında (İng: "declaration") olduğu gibi, ilk kalıtılan YY sınıfı yönünde olurdu. Sonuç olarak, CC sınıfının herhangi bir objesi m()m() metodunu çağırdığında, ilk bakılacak yer CC sınıfının kendisidir. Eğer metot burada yoksa, sonraki bakılacak yer YY sınıfı, burada da bulunamaz ise en son bakılacak yer de ikinci süpersınıf olan ZZ sınıfıdır. Yani C→Y→ZC \rightarrow Y \rightarrow 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, CC sınıfı kendisinin direkt süpersınıfı olan YY klasından daha spesifik olduğundan dolayı, CC sınıfı YY'den önce geldiği gibi, YYde ZZ'den daha spesifik olduğu için ZZ'yi önceler. Yani bu durumda C→Y→ZC \rightarrow Y \rightarrow 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 YY klasından sonra ikinci süpersınıf olan ZZ sınıfına ulaşılması gerekirken, ikinci örneğe göre ise YY klasının da süpersınıfı olan WW sınıfına ulaşılması gerekmektedir. Belki YYsınıfındaki, WW sınıfından kalıtılan elemanlar aynı zamanda YY'nin de elemanları olduğu için, WW sınıfından devam edilmesi gerekecektir. Belki de ZZ sınıfı CC'ye WW'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, ZZ 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, WW ve ZZ 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, YY sınıfının CC sınıfından sonraki en spesifik sınıf olduğu açıktır. Ancak YY sınıfından sonra, YY sınıfının da süpersınıfı olan WW sınıfına mı, yoksa WW sınıfına ulaşmadan önce, tıpkı YY sınıfının yaptığı gibi, WW sınıfından gelen elemanları modifiye etmiş olma, yani WW sınıfındaki elemanların gerçek hallerinden daha yeni olan versiyonlarını içerme ihtimali olan ZZ 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 CC sınıfının süpersınıfı olan YY, diğer süpersınıf olan ZZ'den daha önce kalıtılıyorsa, bir diğer ifadeyle Lokal Öncelik Sıralaması'nda YY sınıfı, ZZ sınıfını önceliyorsa, CC ve CC'nin bütün altsınıflarının lineerizasyonlarında da YY sınıfı ZZ 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→Y→Z→WC \rightarrow Y\rightarrow Z \rightarrow W , Lokal Öncelik Sıralaması ile tutarlı olmakla birlikte; C→Y→W→ZC \rightarrow Y\rightarrow W \rightarrow Z ya da C→W→Y→ZC \rightarrow W\rightarrow Y \rightarrow 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, YY sınıfının lineerizasyonu Y→WY \rightarrow W iken, ZZ sınıfının lineerizasyonu ise Z→WZ \rightarrow W olduğundan ötürü, CC'nin lineerizasyonu da bu lineerizasyonların sıraları değiştirilmemiş bir genişletilmiş versiyonu olmalıdır. Eğer lineerizasyon C→Y→W→ZC \rightarrow Y\rightarrow W \rightarrow Z olursa, ZZ süpersınıfının lineerizasyonu olan Z→WZ \rightarrow W sıralaması değiştirildiği için, monotonluk prensibi ihlal edilmiş olacağı gibi, eğer C→W→Y→ZC \rightarrow W\rightarrow Y \rightarrow Z olursa da hem YY ve hem de ZZ 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, YY'nin lineerizasyonunda WW sınıfı VV sınıfını öncelediği için, CC'nin lineerizasyonunda da WW'nun VV'yi öncelemesi gerekirken, ZZ'nin lineerizasyonunda da VV klası WW klasını öncelediği için, CC'nin lineerizasyonunda da VV'nin WW'yu öncelemesi gerekir. Yani hem W<Dylan(C)VW <_{Dylan(C)} V hem de V<Dylan(C)WV <_{Dylan(C)}W - ki bu bir çelişkidir.
Bu paragraftan itibaren yazıda sadeliğin sağlanması için, herhangi bir CC klasının LL lineerizasyonunda X0X_0 sınıfının X1X_1 sınıfını önceliyor olduğu, X0<L(C)X1X_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, CC sınıfının iki süpersınıfı olan YY ve ZZ sınıflarının lineerizasyonları sırasıyla Y→W→S→UY \rightarrow W \rightarrow S \rightarrow U ve Z→V→SZ \rightarrow V \rightarrow S , yani CC sınıfının bütün SS ve UU sınıflarını lineerizasyonunda içeren, süpersınıfları için SS sınıf UU sınıfını öncelerken, yani S<CLOS(Y)US <_{CLOS(Y)} U, CC klasının lineerizasyonunda ise U<CLOS(C)SU <_{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→YC \rightarrow Y. Ancak daha sonrasında eğer WW ve ardından ZZ ile devam edilirse, Lokal Öncelik Sıralaması bozulmadığı gibi, Monotonluk Prensibi de herhangi bir şekilde ihlal edilmiş olmayacaktır. Tam tersi, yani önce ZZ ve ardından WW 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→YC \rightarrow Y dizisinin en son elemanı olan YY sınıfına en yakın altsınıfa sahip olan, zaten direkt olarak YY sınıfı kendisinin de bir altsınıfı olduğu için, WW sınıfı seçilir. Daha sonrasındaysa VV sınıfıZZ'nin süpersınıfı olduğu için, önce ZZ, sonrasında ise VV ile devam edilmesi gerekir. Böylece tam lineerizasyon, C→Y→W→Z→VC \rightarrow Y \rightarrow W \rightarrow Z \rightarrow 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 LLOOPS∗L^*_{LOOPS}, 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 WW 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 CC ile WW 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.
LLOOPS∗L^*_{LOOPS} algoritmasının CC sınıfı için ürettiği lineerizasyon ise C→Y→W→Z→V C \rightarrow Y \rightarrow W \rightarrow Z \rightarrow V olarak verilir. Yani W<LLOOPS∗(C)ZW <_{L^*_{LOOPS}(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 LLOOPS∗L^*_{LOOPS} 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.
LLOOPS∗L^*_{LOOPS} 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 EE ve FF klaslarını ele alalım. Bu klasların MEFM_{EF} olarak isimlendireceğimiz maksimal ortak altsınıfları (İng: "maximal common subclasses"), hem EE hem de FF 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 CC sınıfı hem EE hem de FF 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 EE veya EE'nin herhangi bir altsınıfı, FF veya FF'in herhangi bir altsınıfını, EE ve FF sınıflarının bütün maksimal ortak altsınıflarının Lokal Öncelik Sıralamasında önceliyorsa, aralarındaki yay EE sınıfındanFF sınıfına doğru yönlendirilmiş olur. Benzer şekilde, eğer FF veya FF'in herhangi bir altsınıfı, EE veya EE'nin herhangi bir altsınıfını, EE ve FF sınıflarının bütün maksimal ortak altsınıflarının Lokal Öncelik Sıralamasında önceliyorsa, aralarındaki yay FF sınıfından EE sınıfına doğru yönlendirilmiş olur.
Genişletilmiş Öncelik Grafı, yukarıdaki (3−4−5−3)(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)(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. HH sembolü ile global kalıtım grafını (İng: "global inheritance graph"), HCH_C sembolü ile de HH grafının sadece CC ve CC'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<_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, HH içerisindeki her JJ sınıfı için J<HJJ<_HJ olduğu anlamına gelir. Yani JJ 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 C0<HC1C_0 <_H C_1 ise C0≠C1C_0 \neq C_1 ve C0C_0 sınıfı C1C_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 uimuim 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)↦C(∋P)′uim: (C,P) \mapsto C'_{(\ni P)} notasyonu ile gösterilebilecek olan bu mekanizma, PP isimli bir özellik (İng: "property") ya da eleman, alan veya metot gibi, ile bu elemanı içeren CC klasından oluşan çifte karşılık olarak, bu sınıfın süpersınıflarından biri olup, bu PP elemanını içeren bir C′C' sınıfı çıktısı verir. Bu durumda CC klasının PP elemanını C′C' klasından kalıttığı söylendiği gibi, C.P==C′.PC.P == C'.P notasyonuyla gösterebileceğimiz şekilde CC klasındaki PP elemanın değeri ya da içeriği de kalıtılmış olduğu C′C' klasındaki PP elemanın değerine ya da içeriğine eşit olmuş olur.
LL ile göstereceğimiz lineerizasyon algoritması ise HH içerisindeki bir sınıf olan CC'yi girdi olarak alıp, CC'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, CC sınıfı PP elemanını bu liste içerisinde PP'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. HH içerisindeki herhangi bir CC sınıfının Lokal Öncelik Sıralamasını precCprec_{C}, HH grafındaki bütün sınıfların Lokal Öncelik Sıralamasınin birleşimini ise precprec sembolü ile göstereceğiz. Yani prec=⋃C∈HprecCprec = \bigcup_{C \in H} prec_C olarak verilir. Buna bağlı olarak, HH grafındaki herhangi iki C0C_0 ve C1C_1 sınıfı için C0<precC1C_0 <_{prec} C_1 olması, HH grafındaki en az bir CC sınıfı için C0<precCC1C_0 <_{prec_C} C_1 olduğu anlamına gelir.
precprec üzerinde tanımlı bir diğer bağıntı ise <path<_{path} bağıntısıdır. λ0=(ΠCC0...Cn)\lambda_0=(\Pi \enspace C\enspace C_0\enspace ...\enspace C_n) ve λ1=(ΠCC1...Cm)\lambda_1=(\Pi \enspace C\enspace C_1\enspace ...\enspace C_m) ortak ön bölüme (İng: "prefix") sahip, C0C_0 ve C1C_1 klaslarına kadarki ΠC\Pi \enspace C ile gösterilen altlisteleri aynı olan, graf içerisindeki yönlendirilmiş iki yol (İng: "path") olmak üzere, eğer C0<precCC1C_0 <_{prec_C} C_1 ise λ0<pathλ1\lambda_0 <_{path} \lambda_1 olur.
Şimdi, Genişletilmiş Öncelik Grafını oluşturmamızı sağlayan ve precprec'in bir genişletilmesi ya da uzantısı (İng: "extension") olan <e<_e bağıntısından bahsedebiliriz. J0J_0 ve J1J_1 sınıfları HCH_C içerisinde ve aralarında kalıtımsal bir ilişki olmayan, yani <H<_H bağıntısı ile karşılaştırılamayan ve HCH_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 M01M_{01} olsun, bu sınıflar ortak direkt altsınıflarının Lokal Öncelik Sıralaması yoluyla, yani <precM01<_{prec_{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, M01M_{01} sınıfı J0J_0 ve J1J_1 sınıflarının maksimal ortak altsınıfı ve λ0=(M01...J0)\lambda_0 = (M_{01} \enspace ... \enspace J_0) ve λ1=(M01...J1)\lambda_1 = (M_{01} \enspace ... \enspace J_1) olmak üzere, eğer λ0<pathλ1\lambda_0 <_{path} \lambda_1 ise J0<eJ1J_0 <_e J_1 deriz. Böylece HCH_C grafına, <e<_e bağıntısı ile oluşturulan yaylar eklenerek, TCT_C, yani CC 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, LLOOPS∗L^*_{LOOPS} 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→Y→Z→U→V→WC \rightarrow Y \rightarrow Z \rightarrow U \rightarrow V \rightarrow W verir. Yani CC'nin WW'ya ulaşmasını sağlayan YY sınıfı, VV'ye ulaşmasını sağlayan ZZ sınıfını öncelemesine rağmen, yine de V<Dylan(C)WV <_{Dylan(C)} W olur. Dolayısıyla CC klası, WW ve VV sınıfından kalıttığı ve farklı uygulamalara sahip bir eleman açısından birinci süpersınıfı olan YY gibi davranmaktansa, ikinci süpersınıfı olan ZZ 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ı, WW ile VV'nin maksimal ortak altsınıfı, aslında tek ortak altsınıfı olan CC sınıfının Lokal Öncelik Sıralamasında, WW'nun altsınıfı olan YY, VV'nin altsınıfı olan ZZ'yi öncelediği, yani Y<precMWV=CZY <_{prec_{M_{WV}=C}} Z olduğu için, Genişletilmiş Öncelik Grafında da W<eVW <_e V olup, CC'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 LLOOPS∗L^*_{LOOPS} 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.
Düzeltmeler: Bir bağlaç hatası düzeltildi, edilgen bir cümlede edilgen olmayan bir bağlaç kullanlarak akış bozulmuştu, düzeltildi, ekleyerek yerine eklenerek gibi.
Bu içeriğimizle ilgili bir sorunuz mu var? Buraya tıklayarak sorabilirsiniz.
İlginizi Çekebilecek SorularSoru & Cevap Platformuna Git
- 2
- 1
- 1
- 1
- 1
- 0
- 0
- 0
- 0
- 0
- 0
- 0
- R. Ducournau, et al. (2021). Proposal For A Monotonic Multiple Inheritance Linearization. OOPSLA '94. | Arşiv Bağlantısı
- K. Barrett, et al. (2021). A Monotonic Superclass Linearization For Dylan. OOPSLA '96. | Arşiv Bağlantısı
- P. Müller. (2017). Concepts Of Object-Oriented Programming.
- Wikipedia. Object-Oriented Programming. (17 Ağustos 2021). Alındığı Tarih: 18 Ağustos 2021. Alındığı Yer: Wikipedia | Arşiv Bağlantısı
- Wikipedia. Multiple Inheritance. (17 Ağustos 2021). Alındığı Tarih: 18 Ağustos 2021. Alındığı Yer: Wikipedia | Arşiv Bağlantısı
- A. Kay. The Early History Of Smalltalk. (1 Mart 1993). Alındığı Tarih: 16 Ağustos 2021. Alındığı Yer: Worrydream | Arşiv Bağlantısı
- S. Ram. Dr. Alan Kay On The Meaning Of “Object-Oriented Programming”. (31 Ağustos 2021). Alındığı Tarih: 31 Ağustos 2021. Alındığı Yer: | Arşiv Bağlantısı
- M. Simionato. The Python 2.3 Method Resolution Order. (1 Ocak 2021). Alındığı Tarih: 17 Ağustos 2021. Alındığı Yer: Python | Arşiv Bağlantısı
Evrim Ağacı'na her ay sadece 1 kahve ısmarlayarak destek olmak ister misiniz?
Şu iki siteden birini kullanarak şimdi destek olabilirsiniz:
kreosus.com/evrimagaci | patreon.com/evrimagaci
Çıktı Bilgisi: Bu sayfa, Evrim Ağacı yazdırma aracı kullanılarak 19/08/2022 11:13:01 tarihinde oluşturulmuştur. Evrim Ağacı'ndaki içeriklerin tamamı, birden fazla editör tarafından, durmaksızın elden geçirilmekte, güncellenmekte ve geliştirilmektedir. Dolayısıyla bu çıktının alındığı tarihten sonra yapılan güncellemeleri görmek ve bu içeriğin en güncel halini okumak için lütfen şu adrese gidiniz: https://evrimagaci.org/s/10674
İçerik Kullanım İzinleri: Evrim Ağacı'ndaki yazılı içerikler orijinallerine hiçbir şekilde dokunulmadığı müddetçe izin alınmaksızın paylaşılabilir, kopyalanabilir, yapıştırılabilir, çoğaltılabilir, basılabilir, dağıtılabilir, yayılabilir, alıntılanabilir. Ancak bu içeriklerin hiçbiri izin alınmaksızın değiştirilemez ve değiştirilmiş halleri Evrim Ağacı'na aitmiş gibi sunulamaz. Benzer şekilde, içeriklerin hiçbiri, söz konusu içeriğin açıkça belirtilmiş yazarlarından ve Evrim Ağacı'ndan başkasına aitmiş gibi sunulamaz. Bu sayfa izin alınmaksızın düzenlenemez, Evrim Ağacı logosu, yazar/editör bilgileri ve içeriğin diğer kısımları izin alınmaksızın değiştirilemez veya kaldırılamaz.