call/cc

June 23, 2012 - Tagged as: lisp, lua, tr.

Son zamanlarda uğraştığım konulardan biri hakkında birşeyler karalayacağım. Genelde zor bir konspetle karşılaştığımda anladığımı anlamak için 2 şey yapıyorum, 1) programlıyorum, 2) anlatıyorum. Uğraştığım işlerle ilgilenen kimse olmadığından, anlatabiliyor olmamı bu blog sağlıyor. Bu sefer Scheme’in call/cc fonksiyonundan bahsedeceğim, epey ilginç bir iş yaptığını düşünüyorum.

call/ccde benim ilgimi çeken şey, Scheme’i bir yorumlayıcı ortamı olarak düşündüğümüzde, yorumlayacağımız dile exceptionlar, coroutineler gibi kontrol akışınıda değişiklikler yapması gereken yapıları kolayca ekleyebilmemizi sağlaması.

Continuation-passing style’a aşina olduğunuzu varsayıyorum. Aşina olmayanlar Google’dan kolaylıkla süper kaynaklar edinebilir. JavaScript gibi yaygın bir dilin CPS kullanabilmek için gereken fonksiyonelliği sağlıyor olması çok büyük şans, yoksa CPSı anlamak için Scheme kodu okumak zorunda kalabilirdiniz :P . Ben implementasyonu Common Lisp ile vereceğim.

call-with-current-continuation veya kısaca call/ccnin genel olarak iki farklı implementasyon yöntemi var¹ biri stack kopyalama işlemi, diğeri CPS conversion dediğimiz, benim birazdan anlatım Common Lisp ile yazacağım yöntem.

Tüm programlarımızın üstü kapalı bir şekilde(implicit) CPS yazıldığını düşünelim. Yani tüm fonksiyon çağrıları aslında bir değer dönmek yerine, bu döneceği değer ile continuation’ı çağırmalı² Bunu sağlamak için tüm fonksiyonlar ilk parametre olarak continuation alabilir ve diğer parametreleri fonksiyon tanımı sırasında verilen parametreler olur. Daha sonra fonksiyon döneceği değer ile ilk parametresini, yani continuation’ı çağırır. Bu fonksiyonları bir macro ile kolayca oluşturabiliriz³:

(defmacro defcont (name (&rest params) &body body)
  (let ((result (gensym)))
    `(defun ,name (continuation ,@params)
       (let ((,result ,@body))
         (funcall continuation ,result)))))

Bu macronun syntaxı defunun tamamen aynısı, sadece ekstradan ilk parametre olarak continuation alıyor ve dönüş değeriyle aslında continuation’ı çağırıyor. Bu şekilde yazılan fonksiyonlar CPS conversion a maruz kalıyor yani.

Örnek olarak bu şekilde basit bir toplama ve çarpma fonksiyonları oluşturalım:

(defcont multiply (&rest args)
  (apply #'* args))
(defcont add (&rest args)
  (apply #'+ args))

Burda fonksiyonların içinde CPS formatında olmayan, dilin kendi fonksiyonlarını çağırıyoruz ama bu sorun değil.

Bu durumda normalde (* 3 (+ 1 2)) şeklinde yazacağımız fonksiyonu şu şekilde yazmamız gerekiyor: (add (lambda (r) (multiply #'identity r 3)) 1 2). İşte bu dönüşümü yapmaya CPS conversion diyoruz. Ne yaptığına bakalım, çarpma işleminin sonucu (+ 1 2) çağrısının dönüş değerine bağlı, buna göre ilk başta toplama işlemi yapılıp, sonucu çarpma işlemine aktarılmalı. Çarpma işlemi de toplama işleminin sonucunu alıp, 3 ile çarptıktan sonra bir continuation’a aktarmalı. Burda bu son continuation olarak identity fonksiyonunu seçtim ki sonucu elde edebilelim. Normalde, eğer örneğin sonucu yazdırmak istiyorsak, orata prin1 gibi bir fonksiyon göndermemiz gerekir.

Bu şekilde yazılan programların nasıl çalıştığına bakarsanız, aslında fonksiyon çağrıları için stack modeline ne kadar benzediğini farkedersiniz. Stack modelinde, çarpma fonksiyonu çağırıldığında stack’de fonksiyon çağrısı hakkında gerekli verileri tutan bir kayıt oluşturulacak, daha sonra toplama işlemi çağırıldığında bunun üzerine bir kayıt daha eklenecek, ve fonksiyon çağrıları bittikçe bu kayıtlar stackten toplanarak bir alt seviyeye dönüş değerlerini bir şekilde aktaracak.

CPS’de tamamen aynı, toplama işlemi önce bitecek ve çarpma işlemine dönüş değerini aktaracak. Bunun için çarpma fonksiyonunu ilk parametresi olarak alacak, çarpma fonksiyonu da kendi sonucunu hangi fonksiyona aktaracaksa o fonksiyonu ilk parametre olarak alacak gibi.

Buraya kadar herşey anlaşıldıysa, call/ccyi yazmak çok kolay. call/ccnin yaptığı, o anki continuation’ı açık bir şekilde kullanıcıya vermek. Normalde yukarıda bahsettiğim tüm olaylar derlenme aşamasında CPS conversion veya başka yöntemlerle hallediliyor ve kullanıcı aslında fonksiyonlarını bizim örneğimizdeki gibi yazmıyor. Dolayısıyla fonksiyonuna aktarılan continuation’a erişme şansı yok. Fakat call/cc hariç, call/cc tam olarak bu işi yapıyor, o anki continuation’a erişim izni veriyor. Şu şekilde:

(defun call/cc (continuation fun)
  (funcall fun continuation))

Bu fonksiyonun defcont ile tanımlandmadığına dikkat. Bu şu anlama geliyor, programlama dili böyle bir fonksiyon sunmuyorsa, bu fonksiyonun yazılması imkansız. Kullanıcının tek sahip olduğunun defcont olduğunu düşünün, yani tüm fonksiyonları _CPS conversion_a mağruz kalıyor, ve fonksiyon çağrıları otomatik olarak CPS’e dönüştürülüyor. Programcı yazdığı fonksiyonlara continuation’ın nasıl aktarıldığını bilmiyor veya bilse bile buna erişmesinin hiçbir yolu yok.

call/cc, kendi aldığı continuation’ı fun parametresi olarka aldığı fonksiyona aktarıyor, ve daha sonra fun fonksiyonu o continuation ile her türlü çılgınlık yapabilir, örneğin bu continuation’ı bir yere kaydedip, bir daha bir daha çağırmak gibi. Bu continuation, dönüş değerinin aktarılacağı fonksiyonu tutuyor aslında.

Hemen basit birkaç örnek yapalım. Şu iki fonksiyon arasındaki fark ne?

(call/cc (lambda (r) (+ r 10)) (lambda (cont) (funcall cont 11)))
(call/cc (lambda (r) (+ r 10)) (lambda (cont) 11))

İlk çağrıda continuation’a 11 değerini gönderiyoruz ve sonuç beklenen gibi 21 oluyor, ikinci durumda ise continuation’ı yok sayıp 11 değerini dönüyoruz ve cevap 11 oluyor. Stack modelinde düşünürsek, ikinci örnekte yapılan şey, stackdeki bazı fonksiyon kayıtlarının atlanması aslında. Buna sanırım stack unwinding deniyor(emin değilim). Bu şekilde dil seviyesinde exception mekanizmaları yazılabilir, continuationlar kaydedilerek ve sırayla çağırılarak coroutineler⁴veya _lightweight thread_ler elde edilebilir(green thread de diyorlar sanırım).

Scheme bilenler için bu kodun Scheme karşılıkları şu:

(call/cc (lambda (cont) (+ 10 11)))
(call/cc (lambda (cont) (+ 10 (cont 11))))

Aralarındaki fark, Scheme kodu _CPS conversion_a mağruz kalmamış, Common Lisp kodu ise kalmış hali.

Bu aşamada yapılabilecek çok fazla fantastik iş var ve çoğu durumda neler olup bittiğini anlama çok güç. Zaten bu yüzden GOTOlarla karşılaştırılıyorlar bazen. Benim hoşuma giden bir kullanımını şu:

(defvar creturn nil)
(call/cc (lambda (r) (+ 1 r))
         (lambda (cont)
           (setf creturn cont)
           1))

Continuation’ı bir değişkene kaydediyorum ve daha sonra istediğim zaman o continuation’ı çağırıp işlemi kaldığı yerden devam ettiriyorum.

CL-USER> (funcall creturn 15)
16
CL-USER> (funcall creturn 20)
21

Kısaca, işlemi istediğim bir yerden durdurdum ve kopyaladım. Daha sonra durdurduğum andan itibaren istediğim bir değer ile devam ettiriyorum. Müthiş bir olay. Bu gösterdiğim örnekler en basit ve sıradan örnekler, neler yapılabileceği hakkında çok fazla güzel kaynak var, açıkçası ben çoğunun ne yaptığını anlamakta güçlük çekiyorum, bazı patternlara aşina olmak gerekiyor. call/ccnin Scheme’den kaldırılması da şu ortamda epey tartışılmış.

Çok bilinen iki implementasyon yöntemi demiştim, diğer yöntem de stack kopyalama. Bu örneği düşünelim, call/cc aslında stack’in o anki durumunu aktarıyor aslında. Burda yapılan işlem büyük ihtimalle en baştan beri tüm stackin kopyalanması değil. Sphagetti stack gibi bir yapı kullanılıyor olabilir.

Bu arada, coroutine demişken, implementasyon detaylarını merak eden varsa: Coroutines in Lua. Lua’yı seviyoruz.