Genelde blog yazılarımı yeni başlayanlara uygun olarak yazarım. Bu sefer bir değişiklik yapıp biraz bilgisayar bilimlerinin temellerine inmek ve bunu da JavaScript ile yapmak istiyorum. Daha önce Ruby ve Clojure ile Lambda Calculus implementasyonu yaptım ama JavaScript ile daha zevkli olacaktır.

JavaScript ile fonksiyonel programlamanın nimetlerinden faydalanabiliriz. Özellikle high-order fonksiyonları ve closure‘lar ile fonksiyonel programlama konseptlerine uyumluluğu, deney yapmak için güzel bir araç haline getiriyor.

Yazının bitiminde Lambda Calculus ile basit bir özyinelemeli(recursive) faktoriyel yazmış olacağız. Yazacak olduğumuz vanilya JavaScript faktoriyel kodu aşağıdaki gibidir:

var faktoriyel = function(n) {
  if (n === 0) {
    return 1;
  }
  return n * faktoriyel(n - 1);
}

Şimdi gelelim asıl konumuza:

Lambda Calculus Nedir?

Lambda(λ), Yunan alfabesindeki onbirinci harfe takabül eden ve özellikle üniversitede sayısal bölüm okumuş olanların sıkça haşır neşir olduğu bir semboldür. Lambda sembolünün özel bir anlamı olmamakla birlikte genellikle matematik dünyasında fonksiyonlara değer atamayı belirten bir semboldür. Calculus, latince hesap yapmak anlamına gelir, İngilizce calculate kelimesi de Latince calculus’ten alınmıştır. Matematikte ise calculus, fonksiyonlar, diziler, limit, türev ve integrali kapsayan matematiksel analitiğin giriş kısmını tanımlamak için kullanılır.

Kelimelerin kökenlerini inceledikten sonra artık Lambda Calculus’un daha kolay anlaşılacağını umuyorum. Lambda Calculus, ile kez Alonzo Church tarafından, matematiğin temellerini araştırırken 1930larda ortaya sunulmuş. Tarih konusunda çok detaylara girmek istemiyorum ama Vikipedi sayfasında dediğine göre, bilgisayar bilimlerinden başka; felsefe, dil ve matemetik alanlarında da kullanımı varmış.

Lambda Calculus ile tek veri tipi aslında fonksiyonlardır. Sadece fonksiyon kullanarak değişken tanımı, if koşulları ve hesaplama yapacağız. Bir nevi JavaScript içinde ayrı bir fonksiyonel programlama dili çıkarmış olacağız.

Lambda İfadeleri

λx.x bu ifade basit bir lambda ifadesi olup JavaScript versiyonu basitçe aşağıdaki gibidir. λ işaretinden sonra gelen x, parametre ve ardından gelen x ise dönüş değeri olarak düşünülebilir.

function(x) {
   return x;
}

Biraz daha karmaşığa doğru ilerlersek, JavaScript’te bulunan closure ve scope kavramlarını hatırlayalım. JavaScript’e çevireceğimiz lambda ifadesi λx.λ.y.x şeklinde. λ işaretinden sonra gelen x, parametredir ve ardından gelen başka bir lambda ifadesi ise fonksiyonun başka bir fonksiyon döndüreceğini gösteriyor.

λx.λ.x.y

function(x) {
  return function(y) {
    return x;
  }
}

Anonim Fonksiyonlarla İşlemler

Şimdi basit bir çarpma işlemi yapan fonksiyon yazalım.

function(x, y) {
  return x * y;
}(2, 3);

Gördüğünüz gibi değişken tanımlamadık ama ananim fonksiyonumuz iki parametre alıyor. Lambda Calculus’te sadece 1 parametre alabilir. Bu durumda kodu aşağıdaki gibi refaktor edebiliriz.

function(x) {
  return function(y) {
    return x * y;
  };
}(2)(3);

Faktoriyel Kodundaki Fonksiyon olmayan kısımlar

Lambda calculus’teki amacımız hesaplama işlemini sadece fonksiyon kullanarak tamamlamak, ancak basit bir recursive işleminde bile birden fazla fonksiyon olmayan öğe mevcut. Sonuca ulaşmak bunların hepsini fonksiyonlarla ifade etmemiz gerekecek.

  • Sayılar n, 1
  • Boolean değerler true, false
  • n - 1 çıkarma işlemi
  • === eşittir ifadesi
  • if ifadesi
  • n * çarpma işlemi
  • Yineleme için Y-Combinator

Sayılar

Lambda calculus tanımı yaparken tek veri tipinin fonksiyon olduğunu belirtmiştim. Bu durumda yukarıda verdiğim örneklerde 2 ve 3 number tipini kullandık. Ben anlaşılması basit olması açısından tam sayılar yerine sıfırdan beşe doğal sayıları kullanacağım.

Not: Fonksiyonel programlamanın temellerinden birisi de immutability (değişmezlik) olduğu için sayı tanımları yaparken ES6 standardı olan const deyimini kullanacağım. const deyimi bazı ortamlarda desteklenmiyor olabilir ancak bu yazıyı yazarken kullandığım Chrome sürümü tarafından destekleniyor. Eğer const ifadesini desteklemeyen bir ortamda deneme yaparsanız const yerine var kullanabilirsiniz.

Bir problemimiz daha var: Şu an için JavaScript, sadece fonksiyon ile nasıl aritmetik işlem yapacağını bilmiyor ve bunu bizim öğretmemiz gerek.

const sayi = function(f) {
  return f(function(x) {
    return x + 1;
  })(0);
};

Yukarıdaki fonksiyonu Lambda Calculus’te oluşturduğumuz saf fonksiyon değerlerini bildiğimiz ‘number’ tipine çevirmek için kullanacağız.

Şimdi fonksiyonel programlamanın nimetlerinden faydalanarak rakamsız sayılarımızı oluşturalım.

const sifir = function f() {
  return function(x) {
    return x;
  };
};

const bir = function(f) {
  return function(x) {
    return f(x);
  };
};

const iki = function(f) {
  return function(x) {
    return f(f(x));
  };
};

const uc = function(f) {
  return function(x) {
    return f(f(f(x)));
  };
};

const dort = function(f) {
  return function(x) {
    return f(f(f(f(x))));
  };
};

const bes = function(f) {
  return function(x) {
    return f(f(f(f(f(x)))));
  };
};

//...

Bu şekilde sayılarımızı tamamladık. Konsol üzerinde test etmek isterseniz:

console.log(sayi(sifir));
console.log(sayi(bir));
console.log(sayi(iki));
console.log(sayi(uc));
console.log(sayi(dort));
console.log(sayi(bes));

//...

sayi fonksiyonumuz işini iyi yapıyor ve yinemeli şekilde x+1 işlemi gerçekleştirerek istediğimiz fonksiyonları doğal sayıya çeviriyor. Sayıları tanımladığımız fonksiyonlara bakarsanız saf fonksiyonlardan meydana geldiklerini görürsünüz.

Boolean Değerler

JavaScript ile Lambda Calculus için sayıların nasıl implemente edildiklerini gördük. Mantığı biraz anladıysak fonksiyon kullanarak nasıl true, false değerlerinin elde edilebileceğini bulabiliriz.

λx.λy. ifadesi x döndürürse true, y döndürürse false kabul edeceğiz. Ancak fonksiyon boolen değerini, JavaScript boolean değerine çevirmek için ayrı bir fonksiyona ihtiyacımız var.

const boolean = function(f) {
  return f(true)(false);
};

boolean fonksiyonunu(arayüz de desek olur sanıyorum) yine iç içe geçmiş fonksiyonları parametre olarak alacak şekilde yazdık.

const dogru = function(x) {
  return function(y) {
    return x;
  };
};

const yanlis = function(x) {
  return function(y) {
    return y;
  };
};

If Ifadesi

Clojure ve diğer Lisp lehçelerinde if dahil tüm ifadeler için sürekli fonksiyon notasyonunu kullanmak (if true (...) (...) ) oldukça pratik ve okunaklı bir yöntem. Şimdi aynı gücü JavaScript ile elde etme zamanı.

const eger = function(bool) {
  return function(x) {
    return function(y) {
      return bool(x)(y);
    };
  };
};

Normal bir if’in yapması gerektiği gibi bool türünde bir parametre alacak ve bool değeri dogru veya yanlis olması durumuna göre iç içe geçmiş fonksiyonlarımızdan hangisinin önce çalışacağına karar verecek.

Konsol üzerinde test etmek için:

console.log(boolean(eger(yanlis)));
console.log(boolean(eger(dogru)));

Çıkarma İşlemi

Çıkarma işleminin bizim için ekstra önemli bir özelliği var o da eşittir işleminin temelini oluşturacak olması. Şöyle ki bir sayıdan bir sayı çıkarıldığında sonuç 0 ise o iki sayı birbirine eşittir. Bu bilgiyi aklımızda tutalım, daha sonra işimize yarayacak.

Lambda calculus ile basit aritmetik işlemleri gerçekleştirmek iki taban fonksiyon bulunuyor. Birisi arttırıcı diğeri ise azaltıcı. Toplama, çıkarma, çarpma ve bölme gibi işlemler bu temel fonksiyon üzerinden yürüyor.

const arttir = function(n) {
  return function(p) {
    return function(x) {
      return p(n(p)(x));
    };
  };
};
const azalt = function(n) {
  return function(f) {
    return function(x) {
      return n(function(g) {
        return function(h) {
          return h(g(f));
        };
      })(function(y) {
        return x;
      })(function(y) {
        return y;
      });
    };
  };
};

Arttırma ve azaltma için taban fonksiyonlarımız tamam, şimdi sıra çıkarma işleminde.

const cikar = function(m) {
  return function(n) {
    return n(azalt)(m);
  };
};

Gördüğünüz gibi cikar fonksiyonu ile daha okunaklı bir hale geldi.

Çarpma İşlemi

Çarpma işlemini gerçekleştirmek için daha önce tanımladığımız arttir taban fonksiyonundan toplama fonksiyonunu ve toplama fonksiyonundan ise çarpma fonksiyonunu gerçekleştireceğiz. Unutulmamalı ki çarpma işlemi yinelemeli bir toplama işlemidir. Örneğin n + n + n <=> 3n.

const topla = function(m) {
  return function(n) {
    return n(arttir)(m);
  };
};

const carp = function(m) {
  return function(n) {
    return n(topla(m))(sifir);
  };
};

console.log(sayi(carp(iki)(iki))); //dort

Eşittir Fonksiyonu

Eşittir fonksiyonu iki parametre alacak ve bu parametrelerle bir çıkarma işlemi gerçekleştirecek. Sonuc sifir olursa dogru, aksi halde yanlis sonucunu dondurecek. Sonucun sıfır olup olmadığını kontrol etmek bir fonksiyona daha ihtiyacımız olacak.

const sifirMi = function(n) {
  return n(function(x) {
    return yanlis;
  })(dogru);
};

Son olarak eşittir için fonksiyonumuz:

const esittir = function(sol) {
  return function(sag) {
    return eger(sifirMi(cikar(sol)(sag)));
  };
};

Yineleme için Y-Combinator

Y-Combinator deyince eminim hemen aklımıza ünlü startup destek şirketi veya Hacker News gelebilir ama burada bahsedeceğimiz Y-Combinator o değil. Aksine Lambda Calculus ile recursion(özyineleme) işlemlerini gerçekleştirmek için kullanılan önemli bir yardımcı fonksiyon.

Y-Combinator: Lambda Calculus ifadesi: λf.(λx.f (x x)) (λx.f (x x))

const yCombinator = function(f) {
  return (function(x) {
    return f(function(y) {
      return (x(x))(y);
    });
  })(function(x) {
    return f(function(y) {
      return (x(x))(y);
    });
  });
};

Burada dikkat ederseniz yCombinator içinde hiçbir yerde fonksiyonun kendisine referans vermedik. Aksi halde sonsuz döngüye girerek programın akışını kilitleyebilirdi.

Yeni Faktoriyel Kodumuz

Buraya kadar lambda calculus faktoriyel kodumuz için çok emek sarfettik. Artık ekmeğini yeme zamanımız geldi.

Yinemeli JavaScript kodunun yCombinator olarak çağırılması:

const orjFaktoriyel = function(fact) {
  return function(n) {
    if (n === 0) {
      return 1;
    }
    return n * fact(n - 1);
  };
};

Burada orijinal faktoriyel kodunu henüz lambda calculus formuna çevirmedik ancak yCombinator fonksiyonuna parametre olarak geçebileceğimiz bir forma soktuk. Yine burada dikkat etmeniz gereken faktoriyel fonksiyonun kendine referans vermeden yineleme işlemini deneyecek olmamız.

console.log((yCombinator(orjFaktoriyel))(5)) // 120

faktoriyel fonksiyonunu çağırmak için yCombinator’ü kullandık.

JavaScript’in Kıyısına Vurmak

Şimdi bütün bu yaptıklarımızı bir araya getirerek faktoriyel kodumuzun son halini oluşturalım.

const faktoriyel = function(n) {
  return eger(esittir(n)(sifir))(bir)(carp(n)(factoriyel(cikar(n)(bir))));
};

Saf Lambda Calculus kodunu yCombinator ile çağırdığımızda.

console.log((yCombinator(faktoriyel))(iki))

Edit:

“RangeError: Maximum call stack size exceeded” hatası alıyoruz :( Blog postun ilk taslağını hazırladığımda ve bu hatayı aldığımda aslında y-combinator ile ilgili kısımda bir implementasyon hatası yaptığımı düşünmüştüm. StackOverflow üzerinde sorduğum soruya yaklaşık 10 gün kimse cevap vermediğini görünce JavaScript deyince aklımıza gelen isim olan, sevgili Fatih Kadir Akın‘a Twitter üzerinden ulaştım ve sağolsun kodu inceledi, implemantasyon hatası olmadığını söyledi ve post’u yine de yayınlamamı tavsiye etti. Hızlı feedback için kendisine yeniden teşekkür ediyor ve an azından Lambda Calculus kodunun nasıl olduğunu göstermiş olduğuma inanıyorum. Umarım JavaScript üzerinde call stack limiti arttırılır ve bizde lambda calculus ile daha fazla deney yapabiliriz.

Kaynaklar

  • http://safalra.com/lambda-calculus/
  • http://codon.com/programming-with-nothing
  • http://en.wikipedia.org/wiki/Lambda_calculus