Common Lisp (3) - prvý kód

Common Lisp (3) - prvý kód
06.03.2008 13:00 | Články | Adam Sloboda

Prvý kód: rekurzia, makrá, zoznamy a anonymné funkcie.

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):

 

π/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - …

 

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)n/(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ú).

    • zatvorky 07.03.2008 | 00:36
      limbi   Návštevník
      no uz teraz viem preco si lisp jeho neprajnici vysvetluju ako "lots of idiotic silly parentheses", bez urazky :)
      • Re: zatvorky 07.03.2008 | 10:43
        autor   Návštevník
        Hehe, ved prave preto je to Lisp... a preto je tiez dolezite nepouzivat vim :D
        • Re: zatvorky 07.03.2008 | 18:31
          Avatar Matej Krajčovič Ubuntu 8.10  Používateľ
          praveze som videl male makro do vimu, ktore najde odpovedajucu zatvorku. bolo to niekde tu. btw je to perfektny navod vimu :)
          You are registered as user #457083 with the Linux Counter.<br/> Given enough eyeballs, all bugs are shallow.<br/>
          • Re: zatvorky 07.03.2008 | 19:13
            autor   Návštevník
            Som si isty, ze obycajne hladanie zatvoriek ma vim aj v zakladnej vybave, ale (a to je fakt) integracia s interpreterom je neporovnatelne horsia.
            • Re: zatvorky 08.03.2008 | 11:09
              Avatar Matej Krajčovič Ubuntu 8.10  Používateľ
              nasiel som to:
              Poslední ze základních pohybů je velmi cenný při hledání nesrovnalostí v závorkování. Pomocí příkazu % se můžete přesunout na odpovídající párovou konstrukci. Za párové jsou přitom považovány všechny tři typy závorek (...), [...], {...}, komentářové dvojznaky podle konvencí jazyka C /*...*/ a instrukce makroprocesoru #if, #ifdef, #else, #elif a #endif. Při hledání párového prvku se samozřejmě berou v úvahu případné vnořené konstrukce, takže se najde skutečně ta závorka (či jiný prvek), která je párová k té pod kurzorem.
              
                  Příklad:
                  Pokud v situaci
              
                      (  (  )  (  ()  ()  )  )
                               ^
              
                  použijete %, ocitnete se zde:
              
                      (  (  )  (  ()  ()  )  )
                                          ^
              
                  Když nyní znovu stisknete %, vrátí se kurzor na původní pozici. 
              You are registered as user #457083 with the Linux Counter.<br/> Given enough eyeballs, all bugs are shallow.<br/>
    • Zacina to byt klasika 12.03.2008 | 01:41
      Avatar stako SUSE  Používateľ
      Aby som vysvetlil ten nadpis.

      Je to jednoduche a inak povedane Prečo robiť veci
      jednoducho ked sa to da zložito! to je cele.
      • Re: Zacina to byt klasika 12.03.2008 | 01:53
        autor   Návštevník
        A keby si to precital cele, zistil by si, ze nikde neodporucam pouzivat rekurziu (navyse ked ANSI CL standard nezarucuje tail call optimisation, co som zabudol zmienit).

        Ale pokial mas krajsi jednoduchy priklad na rekurziu a tail call otimisation, kludne sa pochval...
        • Re: Zacina to byt klasika 12.03.2008 | 02:37
          Stako   Návštevník
          Poviem ktomu len tolko ze rekurziu pokial to je len kus mozne je lepsie ju nepouzit.
          • Re: Zacina to byt klasika 12.03.2008 | 09:35
            autor   Návštevník
            Tvoj vyrok je velmi kontroverzny, tiez by si to mal skusit povedat nejakemu Haskellistovi. A ziadne vyhovorky, "kus mozne" su velmi slabe zadne vratka...
            • Re: Zacina to byt klasika 14.03.2008 | 14:55
              Nathan   Návštevník
              Som haskellista, takze: Styl nepouzivat rekurziu sa da, avsak velmi rychlo sa narazi na limity toho, co sa da a neda naprogramovat. V skutocnosti je to velmi mala cast vycislitelnych funkcii, na druhu stranu bez rekurzie mame okrem malej pamatovej narocnosti aj istotu, ze program vzdy zastavi. Super nie? Tak sa zamyslime, ako zaistit, aby v imperativnom programovani program vzdy zastavil. V takom Pascale treba okrem rekurzie vyhodit cykly while, repeat - until, goto a zabranit aby sa v cykle for mohla menit riadiaca premenna v tele cyklu. Vela toho neostalo, co? Ekvivalenty funkcii ktore sme vyhodili su v ciste funkcionalnych jazykoch riesene rekurziou (to je povedane velmi hrubo a nepresne; a podotykam, ze Lisp ciste funkcionalny nie je).

              Pre zaujimavost, ako by sa v clanku spominana funkcia napisala v haskelli (ako anonymna funkcia): (\s->sum [(1/x)-(1/(x+2))|x<-[1,5..s]])

              Inak k serialu: Velmi sa mi nepaci, je dost chaoticky. Este v minulom dieli sa riesilo IDE a dnes uz su bez nejakeho blizsieho popisu jazyka uvadzane priklady.. Ak chce autor spominat funkcionalne techniky, mal by sa im venovat viac teoreticky atd.
              • Re: Zacina to byt klasika 14.03.2008 | 15:46
                autor   Návštevník
                V minulom dieli sa riesilo IDE do tej miery aby si to potencionalny zaujemca mohol aj vyskusat, lebo Emacs nema zrovna bezne ovladanie.

                Pokial ocakavas od serialu o Common Lispe tutorial na funkcionalne programovanie, tak budes aj nadalej sklamany. Na druhu stranu tento diel bol bez akehokolvek uvodu, co sa ti mozno javi ako chyba, no ja sam vzdy novy jazyk najprv trochu osaham (trochu sa prisposobim feelingu) nez zacnem studovat nieco do hlbky (rovnako vsimam, ze to tu asi necita ziadny Lisper, lebo by sa vyjadril aj k tomu makru :) ale o makrach este bude rec neskor). Jazyky umoznujuce REPL (ako Python, Ruby) su na taketo jednoduche skusanie od prirody vybavene.

                Dufam, ze dalsie casti sa ti budu pacit viac (ale ako vravim, necakaj ziadne teoreticke pojednania :)), este budem spominat aj nejake myslienky suvisiace s funkcionalnym programovanim (currying), ale je to len taka navnada pre ludi, co s tym este neprisli do styku. Common Lisp je prakticky jazyk a od cistej funkcialnosti ma daleko. Verim, ze ludia co chcu len vediet co je Lisp budu mat dost a vazny zaujemca bude mat dost na to aby ho nejaka kniha o Lispe len tak neprekvapila svojim obsahom. (Na zaver samozrejme odporucim aj nejaku tu literaturu ci uz priamo o Lispe alebo s nim uzko spojenu, ked mas o toto zaujem, mozem ti nejake linky dat aj hned.)
              • Re: Zacina to byt klasika 14.03.2008 | 19:50
                autor   Návštevník
                BTW vyskytujes sa pod tymto nickom aj na anglickych blogoch, ktore sa tykaju Lispu? :)
                • Re: Zacina to byt klasika 15.03.2008 | 18:22
                  Nathan   Návštevník
                  To bude niekto iny, ja som haskellista/prologista :)
                  • Re: Zacina to byt klasika 02.04.2008 | 20:58
                    autor   Návštevník
                    Nieco pre haskellistu :D
                    • Re: Zacina to byt klasika 06.04.2008 | 23:44
                      Nathan   Návštevník
                      Pobavilo :D
                • Re: Zacina to byt klasika 20.03.2008 | 21:51
                  termix   Návštevník
                  Nathan je, pokial viem, obycajne anglicke meno.
                  • Re: Zacina to byt klasika 20.03.2008 | 23:47
                    autor   Návštevník
                    To viem aj ja, lenze v jeden den 2x Nathan pod textom o Lispe...
    • Zle jazyky 17.03.2008 | 22:28
      mosi   Návštevník
      Zle jazyky tvrdia o lispe: necyklopedie.wikia.com/wiki/Lisp