Fonksiyonel programlama: Scheme, lambda, map ve özyineleme

Fonksiyonel programlama, programı matematiksel fonksiyonların birleşimi olarak görür. Değişken yok, atama yok, döngü yok; bir fonksiyon aynı argümanla her zaman aynı sonucu verir. Bu dersin fonksiyonel dili Scheme (LISP’in küçük, temiz bir lehçesi). Sınavda iki soru tipi çıkar: Scheme ifadesinin değerini bulmak (car, cdr, cons zincirleri) ve kısa bir özyinelemeli fonksiyonun ne döndürdüğünü izlemek.

Altın kurallar:

1. İçten dışa değerlendir. Her adımda listeyi yeniden yaz.
2. car = ilk eleman, cdr = geri kalan liste, cdr her zaman liste döndürür (uygun girdide).
3. cons ikinci argümanın başına ekler. İkinci argüman liste değilse noktalı çift.
4. Özyineleme kalıbı: boş liste taban durum, car ile işle, cdr ile devam et.
5. Tırnak (') değerlendirmeyi durdurur.

Matematiksel fonksiyonlar

Bir matematiksel fonksiyon, tanım kümesinin her elemanını değer kümesinin bir elemanına eşler. Değerlendirme sırası yan etkilerle değil, yalnızca argümanlarla belirlenir:

$\text{cube}(x) \equiv x \cdot x \cdot x \qquad \text{cube}(2) = 8$

Lambda notasyonu isimsiz fonksiyon yazar: $\lambda(x)\, x \cdot x \cdot x$. Uygulama: $(\lambda(x)\, x \cdot x \cdot x)(2) = 8$. Scheme’in lambda’sı doğrudan buradan gelir.

Functional form (higher-order function): fonksiyonları parametre alan ya da fonksiyon döndüren fonksiyon. Üç klasik:

• Composition: $h \equiv f \circ g$, $h(x) = f(g(x))$.
• Apply-to-all: bir fonksiyonu listenin her elemanına uygula (map).
• Construction: bir argümana bir fonksiyon listesini uygula, sonuçları listele.

Imperative dillerle fark: imperative programda değişkenler bellek hücresidir ve durum (state) değişir. Saf fonksiyonel programda durum yoktur; bu yüzden referential transparency sağlanır ve eşzamanlı çalıştırma (concurrency) kolaylaşır. Bedeli: von Neumann makinesinde verimlilik.

LISP veri yapısı

LISP’te (1958, John McCarthy) iki tür veri nesnesi var: atom (a, 17, hello) ve liste ((a b c), (a (b c) d)). Listeler içeride cons hücreleri zinciri olarak tutulur: her hücrenin iki alanı var, car (eleman) ve cdr (sonraki hücre). Son hücrenin cdr’si boş liste ().

(a (b c) d)

[a|•]──►[•|•]──►[d|/]
          │
          ▼
        [b|•]──►[c|/]

Program da aynı biçimde yazılır: (+ 2 3) bir listedir ve değerlendirilince 5 olur. Kod ile verinin aynı biçimde olması LISP’in en ayırt edici özelliği.

Scheme temelleri

Yorumlayıcı bir read-evaluate-print döngüsüdür. Değerlendirme kuralı: liste görünce ilk elemanı fonksiyon olarak al, diğer elemanları değerlendir, fonksiyonu uygula. Sayılar kendilerine değerlendirilir.

car, cdr, cons

(car (cdr '(a b c)))          ; b
(cdr '((a b) c d))            ; (c d)
(car '((a b) c d))            ; (a b)
(cdr '(x))                    ; ()
(cons '(a) '(b))              ; ((a) b)
(cons 'a 'b)                  ; (a . b)
(car (car (cdr '(1 (2 3) 4))))  ; 2

b
(c d)
(a b)
()
((a) b)
(a . b)
2

Son ifadenin izlemesi:

(cdr '(1 (2 3) 4))   →  ((2 3) 4)
(car ((2 3) 4))      →  (2 3)
(car (2 3))          →  2

TUZAK · cons ile list farkı. (cons '(a) '(b)) iki elemanlı ((a) b) verir; (list '(a) '(b)) ise ((a) (b)). cons ikinci argümanı liste olarak alıp başına ekler; list her argümanı ayrı eleman yapar. (car '()) ise hata: boş listenin ilk elemanı yok.

Fonksiyon tanımlama ve kontrol

(define pi 3.14159)                         ; isim bağlama
(define (square x) (* x x))                 ; fonksiyon
(define square2 (lambda (x) (* x x)))       ; aynısı, lambda ile

(if (> x 0) x (- x))                        ; iki yönlü seçim
(cond ((< x 0) 'neg)
      ((= x 0) 'zero)
      (else 'pos))                          ; çok yönlü seçim

(let ((a 2) (b 3)) (+ a (* a b)))           ; 8, yerel isimler

Predicate fonksiyonlar boolean döndürür (#t, #f): null?, eq?, equal?, pair?, number?, zero?. eq? iki sembolün ya da aynı nesnenin eşitliğini, equal? iki listenin yapısal eşitliğini sorar: (equal? '(1 (2)) '(1 (2))) → #t.

Özyinelemeli liste fonksiyonları

Döngü yok; her şey özyineleme. Kalıp hep aynı:

(define (f lst)
  (cond ((null? lst) <taban değer>)
        (else (<birleştir> (car lst) (f (cdr lst))))))

(define (sum lst)
  (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))
(sum '(3 5 7))                               ; 15

(define (member atm lis)
  (cond ((null? lis) #f)
        ((eq? atm (car lis)) #t)
        (else (member atm (cdr lis)))))
(member 'c '(a b c d))                       ; #t

(define (rev l)
  (if (null? l) '() (append (rev (cdr l)) (list (car l)))))
(rev '(1 2 3 4))                             ; (4 3 2 1)

15
#t
(4 3 2 1)

(sum '(3 5 7)) izlemesi:

(sum '(3 5 7)) = 3 + (sum '(5 7))
               = 3 + 5 + (sum '(7))
               = 3 + 5 + 7 + (sum '())
               = 3 + 5 + 7 + 0 = 15

İç içe listelerde car da bir liste olabilir; o zaman iki yöne özyinelenir:

(define (count-atoms l)
  (cond ((null? l) 0)
        ((pair? (car l)) (+ (count-atoms (car l)) (count-atoms (cdr l))))
        (else (+ 1 (count-atoms (cdr l))))))
(count-atoms '(a (b c) ((d)) e))             ; 5

Yüksek mertebeden fonksiyonlar

(map (lambda (x) (* x x)) '(1 2 3))          ; (1 4 9)

(define (filter p lst)
  (cond ((null? lst) '())
        ((p (car lst)) (cons (car lst) (filter p (cdr lst))))
        (else (filter p (cdr lst)))))
(filter (lambda (x) (> x 2)) '(5 1 4 2 3))   ; (5 4 3)

(define (compose f g) (lambda (x) (f (g x))))
((compose car cdr) '(1 2 3))                 ; 2

(define (adder n) (lambda (x) (+ x n)))
(map (adder 3) '(1 2 3))                     ; (4 5 6)

(define (twice f) (lambda (x) (f (f x))))
((twice (lambda (x) (* x 3))) 2)             ; 18

(1 4 9)
(5 4 3)
2
(4 5 6)
18

Aynı fikirler bugün imperative dillerde de var:

console.log([1, 2, 3].map((x) => x * x), [5, 1, 4, 2, 3].filter((x) => x > 2), [1, 2, 3, 4].reduce((a, b) => a * b, 1));

[ 1, 4, 9 ] [ 5, 4, 3 ] 24

Java 8 stream’leri (list.stream().map(...).filter(...)), Python’un map, filter ve lambda’ları, C#‘ın LINQ’i fonksiyonel programlamadan alınmıştır.

Tail recursion

(define (fact1 n) (if (= n 0) 1 (* n (fact1 (- n 1)))))
(define (fact2 n acc) (if (= n 0) acc (fact2 (- n 1) (* n acc))))
(fact2 5 1)                                  ; 120

fact1’de özyinelemeli çağrıdan sonra bir çarpma bekliyor: her çağrının ARI’si yığında kalmalı, n büyükse yığın taşar. fact2’de çağrı son iş: sonucu doğrudan döndürülür. Scheme bunu bir döngüye çevirir (yeni çağrı eski ARI’yi yeniden kullanır). Bir fonksiyonu tail recursive yapmanın yolu genelde bir accumulator parametresi eklemek.

Diğer fonksiyonel diller

Sık yapılan hatalar

(car (cdr '(a b c)))

(cdr '((a b) c d))
(car '((a b) c d))
(cdr '(x))

(cons 'a '(b c))
(cons '(a) '(b))
(cons 'a 'b)

(car (car (cdr '(1 (2 3) 4))))

(define (f n)
  (if (= n 0)
      1
      (* 2 (f (- n 1)))))

(map (lambda (x) (* x x)) '(1 2 3))

(let ((a 2) (b 3)) (+ a (* a b)))

(define (filter p lst)
  (cond ((null? lst) '())
        ((p (car lst)) (cons (car lst) (filter p (cdr lst))))
        (else (filter p (cdr lst)))))

(define (compose f g) (lambda (x) (f (g x))))
((compose car cdr) '(1 2 3))

(define (count-atoms l)
  (cond ((null? l) 0)
        ((pair? (car l)) (+ (count-atoms (car l)) (count-atoms (cdr l))))
        (else (+ 1 (count-atoms (cdr l))))))

(define (fact1 n) (if (= n 0) 1 (* n (fact1 (- n 1)))))
(define (fact2 n acc) (if (= n 0) acc (fact2 (- n 1) (* n acc))))

(define (adder n) (lambda (x) (+ x n)))
(map (adder 3) '(1 2 3))