Lispic düşünceler

Lisp ile uğraşmaya başladıktan sonra bilgisayar bilimlerine bakış açım tamamen değişti. Başlarda sadece Lisp ile uğraşıyordum. Ancak daha sonraları kendimi hesaplama teorileri içinde buldum. Haliyle programlamaya ve programlama dillerine de artık o taraftan bakıyorum. Programlamayı bir sanat olarak görmekle beraber, aslında sahip olduğu sadeliğin matematikten geldiğine inanıyorum. Bugün de lambda calculus ile ilgili yazılar okurken öğrendiğim ve çok hoşuma giden bazı olayları Python ile göstermeye çalışacağım.

Lambda Calculus

Birazdan anlatacaklarım baştan size çok saçma veya karmaşık gelebilir. Ancak olaylara biraz farklı bakmayı denediğinizde temelde yatan sadeliği göreceksiniz. Eminim benim kadar çok etkileneceksiniz.

Bu yazıdaki amacım çok basit ve temel yapıları kullanarak karmaşık yapıların nasıl inşa edilebileceğini göstermek. Elinizde Python dilinin sadece None sabiti, lambda ve if ifadesi olduğunu düşünün. Aslında if ifadesine de ihtiyacımız yok. Onu da sıfırdan yapabiliriz ama ben uzatmamak için Python'un kendi if ifadesini kullanacağım.

Elimizde yer alan bu 3 şey ile biraz ilginç şeyler yapalım. Öncelikle yokluğu tanımlayalım.

n0 = lambda : None

Burada lambda ifadesinin ne yaptığını biliyorsunuz. İsimsiz bir fonksiyon tanımlıyor. Biz hiç parametre almamasını ve geriye None döndürmesini istedik. Bu artık bizim yokluğumuz. Bir nevi 0 sayımız.

Şimdi yapmamız gereken bu yokluğumuzun birer birer artmasını ve azalmasını sağlayacak olan ifadeleri yazmak. Bunları da aşağıdaki şekilde tanımlayabiliriz.

inc = lambda x: lambda: x
dec = lambda x: x()

Ooops. Neler yaptık burada. Aslında abartılacak herhangi bir şey yok. Yukarıda olan olayları def ile birer fonksiyon haline getirebilirdik. Ancak yazının ruhuna uyması için onları da lambda ile tanımladım. Kısaca çalışmalarına gelirsek, inc ifademiz geriye bir fonksiyon döndürüyor. Ama bu dönen fonksiyon da bir fonksiyon döndürüyor. Daha doğrusu bu inc ifademize verdiğimiz fonksiyona bir fonksiyon halkası daha takıyor. Peki dec ne yapıyor dersiniz. O da tam tersi işlem yapıp bu halkadan bir tane fonksiyonu çağırıyor. Yani halkadan koparıyor.

Yukarıda yaptığımızdan yola çıkarak şimdi de fonksiyon halkamıza bir tane takalım ve buna n1 diyelim. Sonra da onun üzerine yeni halkalar ekleyelim.

n1 = inc(n0)
n2 = inc(n1)
n3 = inc(n2)
n4 = inc(n3)
n5 = inc(n4)

Buraya kadar olan kısımda ne yaptığımızı anlamadıysanız çok endişelenmeyin. Biraz sonra yazacaklarımızdan sonra bütünü incelerseniz anlamanız kolaylaşacaktır.

Şimdi bu kurduğumuz sisteme bir de eşitlik olayını ekleyelim. Çünkü biz n2 isminde bir büyüklük yaptık ancak bu gerçekten de n3 büyüklüğünün bir azı mı. Yani sistemimiz de herhangi bir terslik var mı yok mu test etmemiz gerekiyor.

is_zero = lambda x: x() is None

Bu oluşturuduğumuz ifade, ona verdiğimiz halkadan bir adet koparıyor ve None sabitine ulaşıp ulaşmadığımızı test ediyor. Şimdi bu ifade ile önceki yaptıklarımızın ufak bir kontrolunu yapalım.

is_zero(dec(n1))

Eğer yukarıdaki kodun çıktısı True ise doğru yoldayız demektir.

Şimdi geldik en can alıcı noktaya. Burada iki ifadenin eşit olup olmadığını kontrol edeceğiz. Bakalım nasıl oluyor bu iş.

def equal(x, y):
    if is_zero(x): return is_zero(y)
    elif is_zero(y): return is_zero(x)
    else: return equal(dec(x), dec(y))

Yukarıda yer alan kod göz korkutabilir. Ancak biraz içine girmekte fayda var. Öncelikle bu fonksiyon verdiğimiz iki halkadan herhangi birisinin boş olup olmadığını kontrol ediyor. Eğer ilk verdiğimiz halka boş ise geriye diğer ifadenin dolu mu boş mu olduğunu döndürüyor. Sonuçta eğer ilk ifademiz ile ikinci ifademiz farklı ise aynı anda bu iki koşula gireceklerdir. Bu işlem her bir ifade birer azaltılarak devam ediliyor. Eğer aynı anda 0'a ulaşırlarsa ikisi eşittir. Aksi takdir de is_zero false döndürecektir ve birbirlerine eşit olmayacaklardır.

Bu kodumuzu da anladıktan sonra şimdi biraz test edelim.

equal(dec(n5), n4) # 5-1 == 4
equal(n3, inc(n2)) # 3 == 2+1
equal(n3, n3) # 3 == 3
equal(n2, n5) # 2 == 5
equal(inc(n4), dec(n2)) # 4+1 == 2-1

Bunların üzerinde bir de iki ifadeyi toplayan ve çıkaran fonksiyonları yazalım.

sub = lambda x, y: x if is_zero(y) else sub(dec(x), dec(y))
plus = lambda x, y: x if is_zero(y) else plus(inc(x), dec(y))

Burada kurduğumuz yapı klasik olarak iki ifadenin toplaması ve çıkarmasında kullanılan yöntemdir. Toplarken bir ifadeyi sürekli arttırıp diğerini azaltıyoruz. Azalttığımız 0'a ulaştığında sürekli arttırdığımızı geri döndürüyoruz. Çıkarma işleminde de ikisini sürekli azaltıyoruz. Eğer birisi 0'a ulaştıysa diğerini döndürüyoruz. Burada çıkarma işlemindeki problemi farketmişinizdir umarım. Onu da sizlere bırakıyorum.

Şimdi elimizde toplama, çıkarma, bir arttirma, bir azaltma, eşitlik kontrolu, ve oluşturduğumuz halkalar var. Bunlar ile biraz işlem yapalım.

equal(plus(n3, n1), n4) # 3+1 == 4
equal(plus(n2, n1), plus(n3, n0)) # 2+1 == 3+0
equal(plus(n2, n0), sub(n4, n2)) # 2+0 == 4-2
equal(sub(n3, n1), sub(n2, n0)) # 3-1 == 2-0
n9 = plus(n4, n5)
equal(sub(n9, n1), plus(n4, n4)) # 9-1 == 4+4
equal(sub(n3, n1), n9) # 3-1 == 9

İşte Lambda Calculus böyle inanılmaz bir sadelik üzerine kurulu. İnanabiliyormusunuz bu şekilde tam bir programlama dili de yapabilirsiniz? Yıllardır çok da güzel bir şekilde yapıyorlar. Hatta bu dili kullanarak, bu dili yorumlayacak yorumlayıcıyı yazmak çok moda. İlginç geldiyse gerçek dil ile ilgili kaynakların bir kısmına aşağıdaki linklerden ulaşabilirsiniz.

1 2 3 4 5

comments powered by Disqus