Véget nem érő végtelen ciklus

Minimális Lisp interpretert készítő sorozatom előző részében arról számoltam be, hogy az értelmezőnek már lehetséges rekurzív procedúrákat megadni, amiket helyesen futtatni képes. Ma sikerült egy végtelen ciklust ábrázoló végtelen rekurzív függvényt úgy futtatni, hogy az "soha" nem ér véget, azaz a végtelen rekurzió nem szakad meg memóriaelfogyás, veremtúlcsordulás vagy egyéb probléma miatt, hanem stabil memóriafogyasztás mellett szépen pörgeti a processzort, amíg le nem lövöm a processt.

Ehhez alapvetően két összetevő volt szükséges: garbage collector és tail-call optimization. Garbage collector azért, hogy az "iterációk" során létrehozott, de később már fölösleges objektumok felszabaduljanak. Ellenkező esetben folyamatos memóriaszivárgás miatt utóbb elfogyna a memória, ami a program összeomlását okozná. Tail-call optimization pedig azért kell, hogy "visszacsinálja" azt, hogy egy ciklust rekurzióval írunk le, mivel (egy egyszerű) funkcionális nyelven csak így lehet. Ellenkező esetben, a rekurzió naív függvényhívásos implementációjával a stack folyamatosan növekedne új frame-ekkel, ami nem mehet a végtelenségig.

Elég sokat készültem, az átalakítás viszont rendkívül egyszerű volt. Sok olvastam a garbage collectorokról, a Boehm GC oldaláról elindulva rengeteg hasznos leírás elérhető. A Boehm GC (teljesebb nevén: Boehm-Demers-Weiser garbage collector) egy mark-and-sweep algoritmust használó konzervatív garbage collector C-hez és C++-hoz. Noha érdekes téma ez a garbage collection, nekem most nem az az elsődleges érdeklődésem, hogy garbage collectort implementáljak, ezért kézenfekvő volt, hogy a Boehm GC-t integráljam, lévén az interpreter host nyelve a C nyelv. Itt gyakorlatilag annyit kellett átalakítani, hogy:

A fájl elejére beírni a
```
#include <gc.h>
```
sort.
A main() elejére berakni egy GC_INIT() hívást. (Bár ez Linux/x86-on opcionális.)
Szövegszerűen lecserélni a malloc hívásokat GC_MALLOC-ra.
Fordításnál megadni az -lgc kapcsolót.
Amikor sztring számára foglalok le területet (a szimbólumok miatt kell), akkor a GC_MALLOC_ATOMIC-ot használom, ez jelzi a konzervatív GC-nek, hogy azon a területen ne keressen pointereket, mert nincsenek.

A tail-call optimizationhöz gyakorlatilag nem kellett a forráskódot módosítanom. Átolvastam a kódot és megállapítottam, hogy az eval-apply "ciklus" (technikailag kölcsös rekurzió) sikeresen delegálja a proto-Lisp nyelvem tail-calljait a C fordítónak. Eszerint mind a GCC, mint a Microsoft C/C++ compilere képes tail-call optimizationre. GCC-nél -foptimize-sibling-calls opció kapcsolja be ezt a feature-t, ami egyébként része az -O2 és az -O3 halmaznak. Így gyakorlatilag annyi dolgom volt csak, hogy fordításkor meg kell adni az "-O1 -foptimize-sibling-calls" vagy az "-O2" opciók valamelyikét. Itt látható pár teszt a tail-call optimizationről.

Végezetül jöjjön a teszteléshez használt ominózus végtelen "ciklus". A program rendkívül egyszerű, egy booleant toszogat oda-vissza, igazról hamisra és hamisról igazva, az idők végezetéig.


((lambda (begin invert)
   (begin
     (set! invert
           (lambda (b) (invert (not b))))
     (invert #t)))
 (lambda (one two) two)
 (quote unbound))

A kód úgy működik, ahogy kell: htop szépen kimutatja, ahogy 100%-on pörget egy magot; pmap-pal látható, hogy a memóriafogyasztás nem növekszik; továbbá gdb-vel kiírható a stacktrace, ami sekély.