Rekurzív pillanatok

Így nézne ki a kód Scheme-ben:

(define (even-length l)
  (if (null? l)
      #t
      (not (even-length (cdr l)))))

Van azonban egy kis gond: nincs define, függvényt csak lambdákkal lehet megfogalmazni, és jelenleg az interpreter egyszerre csak egy kifejezést tud kiértékelni az alapértelmezett environment mellett. Szerencsére kb. tetszőleges program átírható ilyen formára. A fenti kód így nézne ki:

((lambda (even-length)
   (begin
     (set! even-length
           (lambda (l)
             (if (null? l)
                 #t
                 (not (even-length (cdr l))))))
     (even-length (quote 1 2 3))))
 (quote unbound))

A függvényt egy lambdán át adjuk át, hogy nevet kaphasson. A rekurzióhoz a függvénytörzsben kell hivatkozni magára a függvényre, ezért az even-lengthet definiáló lambdát abban a lambdában kell megírni, ahol az even-length név érvényes. Azonban ekkor az even-length kívülről kap értéket, ezért van szükség a set!-re, hogy ezt felülírhassuk. Ettől persze továbbra is kell külső értéket adni, ez most nemes egyszerűséggel az unbound szimbólum. A begin második paramétere már a kód, ami even-length működését teszteli.

Ezzel viszont van még egy apró bökkenő: nincs begin. Ezt gyorsan és egyszerűen orvosolhatjuk egy pontosan kétparaméteres beginnel.

((lambda (begin even-length)
   (begin
     (set! even-length
           (lambda (l)
             (if (null? l)
                 #t
                 (not (even-length (cdr l))))))
     (even-length (quote (1 2 3)))))
 (lambda (one two) two)
 (quote unbound))

Ezt a kódot már képes futtatni az interpreter:

> ((lambda (begin even-length)
   (begin
     (set! even-length
           (lambda (l)
             (if (null? l)
                 #t
                 (not (even-length (cdr l))))))
     (even-length (quote (1 2 3)))))
 (lambda (one two) two)
 (quote unbound))
#f
> ((lambda (begin even-length)
   (begin
     (set! even-length
           (lambda (l)
             (if (null? l)
                 #t
                 (not (even-length (cdr l))))))
     (even-length (quote ()))))
 (lambda (one two) two)
 (quote unbound))
#t
> ((lambda (begin even-length)
   (begin
     (set! even-length
           (lambda (l)
             (if (null? l)
                 #t
                 (not (even-length (cdr l))))))
     (even-length (quote (1 2 3 4)))))
 (lambda (one two) two)
 (quote unbound))
#t

A memóriát persze leakeli szorgalmasan:

==4573== HEAP SUMMARY:
==4573==     in use at exit: 8,077 bytes in 422 blocks
==4573==   total heap usage: 422 allocs, 0 frees, 8,077 bytes allocated
==4573== 
==4573== LEAK SUMMARY:
==4573==    definitely lost: 1,320 bytes in 55 blocks
==4573==    indirectly lost: 4,688 bytes in 247 blocks
==4573==      possibly lost: 0 bytes in 0 blocks
==4573==    still reachable: 2,069 bytes in 120 blocks
==4573==         suppressed: 0 bytes in 0 blocks

Persze egy normális begin tetszőleges számú paramétert fogadhat. Definiálása egyszerű, begin =

(lambda x (last x))

, ahol last visszadja a lista utolsó elemét, és last =

(lambda (l)
  (if (null? (cdr l))
      (car l)
      (last (cdr l)))))

Csakhogy ez megint rekurzív, ami miatt ehhez is kell egy begin. Ezért a last így írható meg:

((lambda (last begin)
   (begin
     (set! last
           (lambda (l)
             (if (null? (cdr l))
                 (car l)
                 (last (cdr l)))))
     (last (quote (1 2 3)))))
 (quote unbound)
 (lambda (one two) two))

Akkor most last és begin együtt:

((lambda (last begin)
   (begin
     (begin (set! last
                  (lambda (l)
                    (if (null? (cdr l))
                        (car l)
                        (last (cdr l)))))
            (set! begin (lambda l (last l))))
     (begin (quote ()))))
 (quote unbound)
 (lambda (one two) two))

Itt óvatosan a kódértelmezéssel, ugyanis a begin első két használata még a kétargumentumos definíciót használja (ezért kell egymásba ágyazni), a harmadik viszont már tetszőleges számú elemre működik és használható.

Rájöttem, hogy ezt így iszonyat nehéz debugolni, úgy hogy fogok írni a C-s interpreterben egy normális REPL-t, ami tud top-level definíciókat és a globális environment sorról sorra frissülhet. A másik következő feladat egy garbage collector integrálása. Ezzel majd működni fog az eredeti even-length definíció, persze szintaktikailag kevésbé cukros formában.

(define even-length 
  (lambda (l)
    (if (null? l)
        #t
        (not (even-length (cdr l)))))

Bejegyzés vége.