lambda calculus

• her şeyin fonksiyon olduğu bir matematik sistemi. sayıların ve booleanların gösterimleri için bile fonksiyonlar kullanılır. örnek vermek gerekirse genel olarak booleanlar:
  
  true = /x. /y. x
  false=/x. /y. y
  (/ işaretleri lambda sembolü olacak)
  
  olarak gösterilebilir. aslında bu iki fonksiyon her ne kadar da gerçekten doğru veya yanlışın karşılığı olmasa da seçim yapabilmek için bir mekanizma oluştururlar, true ilk argümanına indirgenirken false ise ikinci argümanına indirgenir. bu şekilde lojik devrelerin elemanlarının çalışma mantıkları da taklit edilebilir, örnek vermek gerekirse:
  
  not = /x. x false true
  
  fonksiyonu için eğer x için false verirseniz beta reduction ile
  
  false false true
  
  fonksiyonuna indirgenir. en soldaki false ikinci argümana indirgeneceği için sonuç true olur. aynısı true false true için de false’tur. and devresi için ise:
  
  and = /x. /y. xyx
  
  kullanılabilir. bu fonksiyonda ise eğer x true ise y’nin değerine indirgenir ve eğer y true ise sonuç true olur değilse olmaz. eğer x false ise x’e indirgenir ve otomatik olarak sonuç false’a indirgenir. not ve and kullanılarak aşağıdaki şekilde nand yapılabileceği için de oradan tüm devreleri oluşturabiliriz çünkü nand devresi turing completedir.
  
  nand = /x. /y. not ( and x y )
  
  bunun yanında sayıların gösterimi için ise kullanılan notasyon aşağıdaki şekildedir:
  
  0 = /f. /x. x (dikkat ettiyseniz false ile aynı fonksiyon)
  1 = /f. /x. f x
  2 = /f. /x. f (f x)
  3 = /f. /x. f ( f (f x))
  ...
  
  bu notasyon ise sayının argüman olarak aldığı x’in argüman olarak aldığı f’e kendi değeri kadar uygulanmasını sağlar.aritmetik işlemlerinden en basit olanı bir arttırma işlemidir ve şu şekilde gösterilebilir:
  
  incr = /n. /f. /x. f (n f x)
  
  bunu test etmek için bir değeriyle denersek:
  
  (/n. /f. /x. f (n f x)) ( /f. /x. f x) =
  /f. /x. f ( (/g. /y. g y )f x) =
  /f. /x. f(f(x))
  
  şeklinde iki değerini elde ederiz. bu fonksiyondan ve önce bahsettiğimiz kendi değeri kadar argüman aldığı fonksiyonu argüman aldığı diğer fonksiyona uygulayabilmesi özelliğiyle birlikte toplama işlemini:
  
  add = /n. /m. n incr m
  
  yada indirgenmiş haliyle:
  
  add = /n. /m. /f. /x. n f ( m f x )
  
  olarak yazabiliriz. çıkarma işlemi için ise bir eksiltme operatörünü tanımlayabilmemiz gerekir. bu işlem arttırma kadar kolay bir işlem değildir çünkü zaten uygulanmış bir fonksiyonu direk olarak geri alamayız. bu işlemi yapmanın bir yolu azaltacağımız sayıya kadar bir sayıyı teker teker arttırıp bir kademe önceki sayıyı almaktır.bunun için önce sayı çiftinin tanımını yapmamız gerekir:
  
  pair = /x. /y. /f. f x y
  
  şeklinde tanımlanabilir.
  
  pair 2 3
  
  dendiğinde bu pair fonksiyonuna x ve y değerleri olarak 2 ve 3 verir ve geriye:
  
  /f. 2 3
  
  kalır ki bu durumun adı partial applicationdur ve çoğu fonksiyonel dilde bulunan bir özelliktir. son olarak da bu sayı çiftinin değerlerinden birini alabilmek için bu fonksiyona en tepedeki true veya false değerini vermek yeter.
  
  bu işlemin çıkarma işlemi için olan önemi ise bizim bu sayı çiftinin sürekli olarak birinci değerini ikinci değerine eşitleyip ikinci değerini bir arttırarak bir azaltacağımız sayının bir azını bulacak olmamızdır, bu işlemin bir iterasyonu şu şekilde tanımlanabilir:
  
  iterate = /p. pair ( p false) (incr (p false))
  
  ve bu şekilde bir azı bulma fonksiyonu da:
  
  decr= /n. (n iterate pair (0 0)) true
  
  olarak tanımlanabilir ve çıkartma işlemi:
  
  sub = /n. /m. m decr n
  
  olarak tanımlanabilir.