Common Lisp (3) - prvý kód

Zoberme si vzorec na π/4 (prvý nekonečný rad pre výpočet π podľa Mādhava of Sangamagrama, no nám nejde ani o presnosť ani o to ako rýchlo konverguje):

Ako prvá možnosť je zrejme jednoduchá rekurzívna funkcia, kde si budeme vypočítavať prvok radu. Povedzme, že 1 je nultý člen (n = 0) a tak prvok radu je (-1)ⁿ/(2×n + 1). Pretože v menovateli sa len strieda znamienko, môžeme použiť predikát evenp (zistí či je číslo párne, opak je oddp) a na základe neho dosadiť 1 alebo -1. Tu je výsledná funkcia:

(defun pi4 (n)
  (if (= n 0)
      1
      (+ (/ (if (evenp n) 1 -1)
            (1+ (* n 2)))
         (pi4 (- n 1)))))

Podmienka if (= n 0) je použitá na ukončenie rekurzie. Môžeme ju prepísať aj na koniec, pretože náš vzorec pracuje aj pre nultý člen, na konci by sme dostali (if (= n 0) 0 (pi4 (- n 1))). V kóde je použitá funkcia 1+, ktorá vráti nasledovníka, teda pre obyčajné číslo je ekvivalentná pričítaniu jednotky (protiklad tejto funkcie je 1-).

Rekurzia v tejto podobe nie je zadarmo, zásobník sa každým ďalším volaním zapĺňa a pri tejto funkcii potrebujeme mnoho volaní. Môžeme ju ale napísať v podobe vhodnej pre automatickú optimalizáciu, táto forma sa nazýva tail recursion. Názov je odvodený od toho, že ako posledné zavolá sama seba ("na chvoste"). Teraz si napíšeme riešenie pre výpočet π s tail recursion:

(defun pi4-tail (n acc)
  (if (= n 0)
      (1+ acc)
      (pi4-tail (1- n)
                (+ (/ (if (evenp n) 1 -1)
                      (1+ (* n 2)))
                   acc))))
 
(defun pi-madhava (n)
  (* 4 (pi4-tail n 0)))

pi4-tail používa parametre pre prvok radu a akumulátor, kde sa ukladá výsledok. Táto funkcia už na konci volá sama seba, tak ju upravíme a vyrobíme si umelú chybu:

(defun pi4-tail (n acc)
  (if (= n 0)
      (progn
        ;; overíme si, že sme naozaj ukončili rekurziu
        (format t "~f" (* 4 (1+ acc)))
        ;; a spôsobíme chybu
        (bla))
      (pi4-tail (1- n)
                (+ (/ (if (evenp n) 1 -1)
                      (1+ (* n 2)))
                   acc))))

CL-USER> (float (pi-madhava 1000))
3.1425917

0: (PI4-TAIL #)
1: (PI-MADHAVA #)

pi4-tail je vo svojom tisícom volaní a vidíme, že táto funkcia bola úspešne optimalizovaná. Ale ani toto riešenie nie je najelegantnejšie, pozrime sa na ďalšie možné riešenia. Predtým ale ešte upozorním, že som v kóde urobil prvú poznámku – v Lispe začína poznámka bodkočiarkou a končí na konci riadku. Tiež som použil progn na zoskupenie viacerých príkazov (obdoba zložených zátvoriek v C).

Skúsime teraz riešiť s použitím makra a anonymnej funkcie, vypočítame si všetky prvky:

(mapcar
 #'(lambda (n)
     (if (= n 0) 1 (/ (if (evenp n) 1 -1)
                      (+ 1 (* n 2)))))
 (loop for x from 0 to 10 collect x))
 
;; výsledok:
(1 -1/3 1/5 -1/7 1/9 -1/11 1/13 -1/15 1/17 -1/19 1/21)

Funkcia mapcar nám zozbiera všetky prvky, ktoré sú vypočítané aplikovaním našej anonymnej funkcie na prvky zoznamu, ktoré nám vygenerovalo makro loop. Anonymná funkcia (lambda) je obyčajná funkcia, ktorú sme definovali na mieste a nemá žiadne pomenovanie. Naša má jeden argument n a počíta n-tý prvok nekonečného radu. Teraz si spravíme makro a prepíšeme volanie mapcar aby počítalo určitý počet prvkov:

(defmacro pi-macro (n)
  `(+ ,@(mapcar
         #'(lambda (n)
             (if (= n 0) 1 (/ (if (evenp n) 1 -1)
                              (+ 1 (* n 2)))))
         (loop for x from 0 to n collect x))))

Makro vráti zoznam, ktorý sa až následne vyhodnocuje. Pri jeho zápise som použil niektoré špeciálne znaky: tzv. backtick `, čiarku a zavináč. Backtick zabráni okamžitému vyhodnoteniu výrazu pred ktorým stojí a čiarka naopak povolí vyhodnotenie jednému jeho prvku. Apostrof/úvodzovka s jednou čiarkou ' (respektíve funkcia quote) má rovnakú funkciu ako backtick, len nepodporuje vyhodnocovanie čiarkou. Zavináč vloží vyhodnotený výraz (t.j. zoznam vypočítaných prvkov) priamo do nadradeného zoznamu, nie ako samostatný zoznam. Nadradený zoznam obsahuje volanie funkcie sčítania, čo nám dá výsledok. S makrami sa treba pohrať a hneď bude všetko jasnejšie.

Ani toto riešenie nie je najelegantnejšie. Niektorí si možno všimli ako nám makro loop zozbieralo zoznam čísel od 0 po n. Toto makro dokáže omnoho viac, dokonca v našom prípade za nás môže oddrieť všetku robotu a zvýšiť zrozumiteľnosť:

(defun pi-madhava (n)
  (* (loop for x from 0 to n
        sum (/ (if (evenp x) 1 -1)
               (1+ (* x 2))))
     4))

Tentokrát sme toho stihli naozaj dosť – anonymné funkcie, makrá, tail recursion, v neposlednom rade sme poodhalili silu Lispu pri práci so zoznamami a dúfam, že sa Lisp začína zdať prístupnejší. Treba si kód vyskúšať a pozrieť v Emacse (zvýrazňovanie, automatické odsadenie tabulátorom veľmi pomáhajú).