Devamsal Geçiş Tarzı (Continuation-passing style, CPS)

Yazan: Şadi Evren ŞEKER

Fonksiyonel programlamada kullanılan fonksiyon tarzlarından birisidir. Buna göre bu tarzda yazılmış olan bir fonksiyon doğrudan değer döndürmek yerine, ilave bir parametre ile fonksiyondaki hesaplamaları taşır.

Devamsal geçiş tarzında yazılan bir fonksiyon çağrıldığı zaman ilave olarak bir prosedür verilerek bu fonksiyonun dönüş değerine yazılır. Doğrudan çağırmada dahili olark yapılan bazı işlemler devamsal geçiş tarzında harici olarak yapılmaktadır. Örneğin fonksiyonların dönüşleri, ara değerleri, parametrelerin çalıştırılma dereceleri ve kuyruk özyinelemeler (tail recursion) gibi.

Doğrudan çağırmalı bir fonksiyonun devamsal geçiş tarzına çevrilmesi otomatik olarak yapılabilmektedir. Bu sayede derleyiciler (compilers) bu özellikten faydalanarak iyileştirme (optimisation) yapabilmektedirler. İşin aslında bu özelliğinden dolayı devamsal geçiş tarzı programcılardan çok derleyiciler tarafından kullanılan bir tarzdır.

Scheme dilinde bazı örnek çevrimler aşağıda verilmiştir:

(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))

(define (pyth x y k)
 (* x x (lambda (x2)
         (* y y (lambda (y2)
                 (+ x2 y2 (lambda (x2py2)
                           (sqrt x2py2 k))))))))

(define (factorial n)
 (if (= n 0)
     1
     (* n (factorial (- n 1)))))

(define (factorial n k)
  (= n 0 (lambda (b)
          (if b
             (k 1)
             (- n 1 (lambda (nm1)
                     (factorial
                      nm1
                      (lambda (fnm1)
                       (* n fnm1 k))))))))

(define (factorial n) (f-aux n 1))
(define (f-aux n a)
 (if (= n 0)
     a
     (f-aux (- n 1) (* n a))))

(define (factorial n k)
 (f-aux n 1 k))
(define (f-aux n a k)
 (= n 0 (lambda (b)
         (if b
             (k a)
             (- n 1 (lambda (nm1)
                     (* n a (lambda (nta)
                             (f-aux nm1 nta k)))))))))

Yukarıda verilen iki farklı faktöriyel hesabından ilki (yani yukarıdaki 3 fonksiyondan ikincisi) doğrudan çağırmanın çevrilmiş haliyken ikincisi (yani yukarıdaki 3 fonksiyondan sonuncusu) yardımcı bir fonksiyon (f-aux) kullanarak birikimsel tarzda (accumulation style) yazılmış bir fonksiyonun devamsal geçiş tarzına dönüştürülmesini göstermektedir.

Ayrıca tembel programlama (lazy programming) kullanılarak bir fonksiyonun körilenmesi (curry) gerekirse faktöriyel hesabı aşağıdaki şekilde yazılmalıdır:

(define (factorial n k)
  (if (= n 0)
      (k 1)
      (factorial (- n 1) (compose k (curry * n)))))

>(factorial 5 (lambda (x) x))
>120

Yukarıda verilen bu fonksiyonun temel farkı k parametresi ile biriktirilen (Accumulate) değerlerin birer fonksiyon olmasıdır. Yani basitçe her çağırmada gelen fonksiyon bir önceki fonksiyon ile birleştirilmiş (compose) ve faktöriyelin başlangıç durumu (initial state) olan n = 0 durumuna gelindiğinde (n = 0 olunca 0! = 1 olduğunu hatırlayalım) bu fonksiyon birleşimlerine 1 parametresi verilerek çağrılmıştır. Bu durum daha basit şekilde aşağıdaki matematiksel gösterimde yer almıştır:

factorial(factorial(factorial(factorial(factorial(1))))

yani basitçe factorial fonksiyonları n kadar birleştirilmiştir. n = 0 olunca birleştirme işlemi durmuş bunun yerine bu birleştirilmiş fonksiyonlara 1 parametresi verilmiştir.