Hlavní navigace

PicoLisp: užitečné funkce a speciální formy používané při tvorbě aplikací

Pavel Tišnovský 26. 4. 2016

Ve druhém článku o rychlém, zajímavém a přitom poměrně neznámém interpretru PicoLisp si popíšeme další funkce a speciální formy, které jsou dostupné všem vývojářům, kteří se rozhodnou tento interpret použít.

Obsah

1. PicoLisp: užitečné funkce a speciální formy používané při tvorbě aplikací

2. Práce s globálními proměnnými

3. Lokální proměnné

4. Pravdivostní hodnoty a základní booleovské operace

5. Další booleovské operace a predikáty

6. Význam konstanty NIL v PicoLispu

7. Konstruktory seznamů – cons a list

8. Funkce filter

9. Funkce mini, maxi, sumcnt

10. Řízení běhu programu – rozvětvení

11. Použití forem when a unless

12. Vícenásobné rozvětvení – forma condnond

13. Rozvětvení na základě dvou podmínek – forma if2

14. Sledování běhu programu s využitím funkcí trace, traceAll a untrace

15. Literatura

16. Odkazy na Internetu

1. PicoLisp: užitečné funkce a speciální formy používané při tvorbě aplikací

Ve druhé části článku o PicoLispu, tj. o minimalistickém interpretru programovacího jazyka LISP, si popíšeme další vlastnosti tohoto dialektu. Nejprve si řekneme, jakým způsobem se pracuje s proměnnými (především jak je řešena viditelnost lokálních proměnných), následně si popíšeme způsob práce s pravdivostními hodnotami (zejména s chápáním hodnoty NIL, které je zde odlišné od ostatních dialektů LISPu) a posléze si popíšeme funkce a speciální formy určené pro práci se seznamy, pro řízení běhů programů a taktéž pro sledování (trasování) aplikace – to je velmi užitečná vlastnost, zejména při ladění rekurzivních funkcí.

Před vysvětlováním významu nových funkcí a speciálních forem si připomeňme, jakým způsobem se v PicoLispu definují nové funkce, které jsou základním kamenem všech programů. Podobně jako v prakticky jakémkoli jiném programovacím jazyku, i zde můžeme definovat pojmenované funkce, a to s využitím de:

(de factorial
    (n)
    (apply * (range 1 n)))

V některých případech nám však bude postačovat definice funkcí anonymních, tj. funkcí, které nejsou nijak pojmenovány (přesněji řečeno nejsou navázány na žádný symbol). V dalším příkladu taková funkce slouží pro výpočet druhých mocnin (čtverců) sekvence celočíselných hodnot. Vidíme, že anonymní funkce jsou vytvářeny s využitím speciální formy quote a nikoli lambda:

(mapcar (quote (x) (* x x)) (range 1 10))
(1 4 9 16 25 36 49 64 81 100)

2. Práce s globálními proměnnými

Prozatím jsme se v demonstračních příkladech zabývali pouze funkcemi, které nějakým způsobem zpracovávaly své parametry a popř. vracely nějaký vypočtený výsledek. Ovšem PicoLisp není pouze akademický jazyk, takže umožňuje i práci s proměnnými, samozřejmě včetně proměnných globálních (jejichž výskyt by se měl v programech co nejvíce omezit). Globální i lokální proměnné jsou měnitelné, protože PicoLisp není, ostatně stejně jako většina ostatních LISPových dialektů, čistě funkcionální. Pro základní práci s proměnnými je určeno těchto pět funkcí:

# Funkce Význam
1 set nastavení proměnné na určitou hodnotu, proměnná musí být quotována
2 setq nastavení proměnné na určitou hodnotu, proměnná je quotována automaticky
3 val získání hodnoty určené proměnné (tato hodnota je výsledkem celé formy)
4 zero nastavení zvolené proměnné či proměnných na hodnotu 0
5 one nastavení zvolené proměnné či proměnných na hodnotu 1

Podívejme se nyní na způsob použití těchto funkcí. Nejdříve si vyzkoušejme, jak PicoLisp reaguje při pokusu vypsat hodnotu neexistující proměnné. Nestane se nic hrozného (nevyhodí se výjimka atd.), ale pouze se vrátí NIL:

neznamy-symbol
NIL

Pro nastavení hodnoty proměnné či proměnných se používá forma set. Jména proměnných musí být quotována (apostrof před jménem):

(set 'answer 42)
42
 
(set 'x 10 'y 20)
20
 
x
10
 
y
20

Pokud na quotování zapomenete, dostanete jednu z následujících chybových hlášení (v závislosti na tom, zde proměnná již existuje či nikoli):

(set x 10)
10 -- Variable expected
 
(set z 20)
NIL -- Protected symbol

Mnohem praktičtější je namísto funkce set použít formu setq, která quotování nepotřebuje. Proto se s touto formou setkáme v programech mnohem častěji:

(setq u 50 v (* u 2))
100
 
u
50
 
v
100

V některých případech se proměnné inicializují na hodnotu 0, což zařizuje funkce zero:

(zero a b c d)
0
 
a
0
 
b
0

Podobný význam má i funkce one, samozřejmě s tím rozdílem, že se nové proměnné nastaví na hodnotu 1:

(one x y z w)
1
 
x
1
 
y
1
 
z
1
 
w
1

Funkce val se pravděpodobně příliš často v praxi nepoužije – slouží k získání hodnoty proměnné, která je funkci předána jako symbol (je tedy quotována). Tato funkce tedy vlastně provádí „dequotaci“ a lze ji použít i v případě, že se jí předá neznámá proměnná:

(val 'x)
1
 
x
1
 
(val 'neznamy-symbol)
NIL

3. Lokální proměnné

V mnoha funkcích se používají lokální proměnné. Ty se nedefinují pomocí set ani setq, ale speciální formou let, která současně omezuje platnost takto vytvořených proměnných. Do formy let se zapisuje jak deklarace a inicializace proměnné, tak i vlastní tělo, tj. seznam výrazů. Návratovou hodnotou celého bloku je hodnota vrácená posledním výrazem. Nejjednodušší příklad s deklarací jediné lokální proměnné:

(let x 10 (* x 2))
20

Při deklaraci dvou proměnných (či ještě většího počtu proměnných) se používají závorky:

(let (x 6 y 7) (* x y))
42

Alternativně lze použít i hranaté závorky a umístit jednotlivé výrazy na samostatné řádky. Tento způsob zápisu vylepšuje čitelnost:

(let [x 6 y 7]
             (* x y))
42

Příklad použití speciální formy let uvnitř funkce. Zde je návratová hodnota let současně i návratovou hodnotou celé funkce:

(de prumer
    [seznam]
    (let [soucet (apply + seznam)
          pocet (length seznam)]
          (/ soucet pocet)))

Můžeme snadno provést otestování nové funkce:

(prumer (1 2 3))
2
 
(prumer (1 1 1))
1
 
(prumer (1 1 10))
4

Formy let je možné v případě potřeby libovolným způsobem rekurzivně zanořovat. Oblast viditelnosti proměnných je stále určena blokem let, ve kterém je proměnná deklarována. Zde má tedy proměnná nazvaná vysledek jen omezenou platnost viditelnosti:

(de prumer
    [seznam]
    (let [soucet (apply + seznam)
          pocet (length seznam)]
          (let [vysledek (/ soucet pocet)]
              vysledek)))

Proměnné, které jsou deklarovány a inicializovány dříve, je možné použít i ve výrazech sloužících pro inicializaci později deklarovaných proměnných. Co to znamená v praxi? Příkladem může být následující úprava funkce prumer, ve které je proměnná vysledek inicializována výrazem používajícím proměnné deklarované uvnitř stejného bloku let. S podobným kódem se v praxi setkáme poměrně často:

(de prumer
    [seznam]
    (let [soucet   (apply + seznam)
          pocet    (length seznam)
          vysledek (/ soucet pocet)]
              vysledek))

4. Pravdivostní hodnoty a základní booleovské operace

V dialektu PicoLisp se pro reprezentaci pravdivostních hodnot true a false používají globální konstanty nazvané T a NIL (tato konstanta je poněkud překvapivě psána verzálkami, na rozdíl od dalších dialektů LISPů). Jedna z těchto konstant je vždy výsledkem všech booleovských operací, ovšem jejich vstupní parametry mohou být libovolné (čísla, symboly atd.), s tím, že jakákoli hodnota rozdílná od NIL je považována za logickou pravdu. Při tvorbě programů jsou k dispozici všechny tři základní booleovské operace vypsané v následující tabulce:

# Funkce Význam
1 and logický součin
2 or logický součet
3 not logická negace

Všechny tři výše vypsané funkce jsou variadické, tj. lze jim předat libovolné množství parametrů. V případě funkce not má smysl použít jen jediný parametr:

(not)
T
 
(not NIL)
T
 
(not T)
NIL

Naproti tomu u funkcí and a or je možné (a mnohdy i vhodné) použít i větší počet parametrů, což je jasně patrné z následujících demonstračních příkladů

(and)
NIL
 
(and NIL)
NIL
 
(and T)
T
 
(and T NIL T NIL)
NIL
 
(and T T T T)
T
 
(or)
NIL
 
(or T T T T)
T
 
(or T T T NIL)
T
 
(or NIL NIL)
NIL
 

Pro zjednodušení některých logických výrazů jsou v PicoLispu implementovány i další logické funkce, které doplňují výše uvedenou základní trojici. Jedná se o negaci logického součinu (NAND), negaci logického součtu (NOR) a nonekvivalenci (XOR):

# Funkce Význam
1 nand negace logického součinu
2 nor negace logického součtu
3 xor nonekvivalence

Opět je jedná o variadické funkce, o čemž se můžeme přesvědčit například u funkce nand:

(nand T NIL)
T
 
(nand T T)
NIL
 
(nand T T T)
NIL
 
(nand T T T NIL)
T

U funkcí nor a xor je situace podobná. Povšimněte si, že kombinace těchto funkcí může být velmi užitečná a může navíc eliminovat některé složité výrazy, které můžeme znát například z céčkových jazyků:

if (!(a==b || c>0)) {...}

5. Další booleovské operace a predikáty

Kromě šestice logických funkcí popsaných ve čtvrté kapitole se můžeme setkat s dalšími užitečnými funkcemi orientovanými na zpracování pravdivostních hodnot. Tyto funkce jsou vypsány v tabulce:

# Funkce Význam
1 =T test na hodnotu T
2 nT test na hodnotu odlišnou od T
3 =0 test na nulu
4 =1 test na jedničku
5 n0 test na číselnou hodnotu odlišnou od nuly
6 on do předaných proměnných (libovolný počet) uloží hodnotu T
7 off do předaných proměnných (libovolný počet) uloží hodnotu NIL

K dialektům programovacího jazyka LISP samozřejmě patří i množina predikátů, tj. funkcí, které na základě nějaké vyhodnocené podmínky vrací pravdivostní hodnotu. Většina predikátů končí otazníkem, ale nalezneme zde i několik výjimek (není však samozřejmě nijak problematické si dodefinovat i ostatní predikáty končící otazníkem):

# Predikát Význam
1 atom test, zda je předaná hodnota atomem: NIL, číslo či symbol
2 pair test, zda je předaná hodnota tečkovým párem
3 num? test, zda je předaná hodnota číslem
4 fun? test, zda je předaná hodnota funkcí
5 flg? test, zda je předaná hodnota rovna T nebo NIL (ničemu jinému)
6 sp? test na NIL, prázdný řetězec či řetězec s bílými znaky
7 bool pro všechny hodnoty kromě NIL vrací T (tedy vlastně konvertuje na T či NIL)

Podívejme se na několik jednoduchých příkladů. U testu na funkci se nevrací T, ale buď parametry funkce či u nativní funkce nějaká jednoznačná číselná hodnota (prostě cokoli odlišného od NIL):

(fun? gcd)
NIL
 
(fun? prumer)
(seznam)
 
(fun? println)
271502
 
(fun? print)
271494
 
(fun? car)
268459
 
(fun? cdr)
268462

6. Význam konstanty NIL v PicoLispu

Konstanta NIL, která je jednou ze dvou možných návratových hodnot funkcí zmíněných ve čtvrté kapitolev kapitole páté, má v interpretru programovacího jazyka PicoLisp hned několik významů, které mohou být někdy až neobvyklé, zejména při porovnání s dalšími dialekty LISPu. První zajímavostí resp. odlišností je fakt, že se tato konstanta zapisuje verzálkami (NIL nikoli minuskami jako nil) a že se jedná o jeden ze dvou globálních symbolů nezačínajících hvězdičkou. Všechny ostatní globální symboly PicoLispu totiž právě podle oné hvězdičky poznáme (a programátoři jsou vedeni k tomu, aby dodržovali stejné pravidlo). Mezi mnohé další významy konstanty NIL patří například:

  1. Značka pro konec seznamu (například při jeho konstrukci pomocí tečkových párů, viz příklad pod odstavcem).
  2. Jiná forma reprezentace prázdného seznamu.
  3. Při práci s pravdivostními hodnotami se NIL používá namísto false (viz předchozí kapitolu).
  4. V aritmetických operacích představuje NIL nejmenší možné číslo.
  5. NIL taktéž značí řetězec nulové délky.
  6. Pokud je výsledkem nějaké operace NaN, opět lze použít i NIL.
  7. Při použití OOP je NIL prapředkem všech tříd v hierarchii (to je možná překvapivé, ale vychází to z dalších vlastností této konstanty).

Podívejme se na několik příkladů použití této konstanty:

; použití pro ukončení seznamu zapisovaného tečkovými páry
(1 . (2 . (3 . (4 . NIL))))
(1 2 3 4)
 
; NIL je považován za ekvivalent prázdného řetězce
(sp? NIL)
T
 
; NIL je ekvivalentem prázdného seznamu
(= () NIL)
T
 
; NIL je dokonce menší než jakékoli číslo
? (< NIL -100000000)
T

7. Konstruktory seznamů – cons a list

Vzhledem k tomu, že jediným strukturovaným datovým typem PicoLispu je seznam, není divu, že programátoři mají k dispozici hned několik konstruktorů seznamů. Jedná se především o dvojici funkcí nazvaných cons a list. Pojmenování těchto funkcí má historické důvody, neboť funkce s obdobnou sémantikou se v dialektech LISPu vyskytují padesát let. Obě funkce za všech okolností vrátí seznam (nikdy ne NIL či jiný atom):

# Funkce Význam
1 cons připojení dalšího prvku k existujícímu seznamu či vytvoření jednoprvkového seznamu
2 list vytvoření seznamu z předaných parametrů (počet parametrů je roven počtu prvků nového seznamu)

Nejprve se podívejme na použití funkce cons s několika variantami parametrů:

(cons)
(NIL)
 
(cons 1)
(1)
 
(cons 1 2)
(1 . 2)
 
(cons 1 (2))
(1 2)
 
(cons 0 (1 2 3 4))
(0 1 2 3 4)

Pozor je zapotřebí si dát především na to, že funkce cons nedokáže (alespoň ne přímo) spojit dva seznamy. Namísto jediného „plochého“ seznamu totiž získáme seznam, jehož prvním prvkem je první parametr funkce cons:

(cons (1 2 3 4) (1 2 3 4))
((1 2 3 4) 1 2 3 4)

Funkce nazvaná list akceptuje větší množství parametrů, z nichž sestrojí seznam. Neprovádí se zde tedy žádné připojení k již existujícímu seznamu, což je patrné z vyhodnocení třetího výrazu:

(list)
(NIL)
 
(list NIL)
(NIL)
 
(list 1 2)
(1 2)
 
(list 1 2 3 4)
(1 2 3 4)
 
(list 1 (2 3 4))
(1 (2 3 4))

Povšimněte si, že se skutečně za všech okolností vrací seznam, i kdyby se mělo jednat o seznam s jediným prvkem NIL.

8. Funkce filter

Již minule jsme se seznámili s funkcí vyššího řádu nazvanou mapcar, kterou je možné použít pro vytvoření nového seznamu ze seznamu původního, a to aplikací nějaké funkce na každý prvek původního seznamu. Jen pro připomenutí, jak se funkce mapcar může použít, si uveďme příklad:

(de inc
    (x)
    (+ x 1))
 
(mapcar inc (1 2 3))
(2 3 4)

Kromě mapcar mají vývojáři k dispozici i další poměrně užitečnou funkci, která se příhodně jmenuje filter. I filter je funkcí vyššího řádu, kde předaná funkce (ať už pojmenovaná či anonymní) určuje svojí návratovou hodnotou, zda daný prvek z původního seznamu má být přenesen do seznamu vytvářeného. Jedná se tedy o obdobu klauzule WHERE v jazyce SQL. Podívejme se na příklad. Nejprve vytvoříme predikát testující, zda je předané číslo kladné:

(de pos?
    [n]
    (> n 0))

Následně z předaného seznamu vyfiltrujeme pouze kladné prvky:

(filter pos? (-5 -4 -3 -2 -1 0 1 2 3 4 5))
(1 2 3 4 5)

Podobně můžeme postupovat při získání sudých prvků ze sekvence hodnot 1 až 10. Zde se používá anonymní funkce zapsaná ve speciální formě quote:

(filter (quote (n) (=0 (% n 2))) (range 1 10))
(2 4 6 8 10)

Při použití funkce filter se s anonymními funkcemi setkáme poměrně často.

9. Funkce mini, maxi, sumcnt

Další čtveřice funkcí vyššího řádu vlastně kombinuje funkci mapcar popsanou minule a funkci typu reduce, protože výsledkem není nový seznam, ale jediná hodnota získaná nějakou kombinací prvků. Základní popis zmíněných čtyř funkcí nalezneme v tabulce:

# Funkce Význam
1 mini aplikuje předanou funkci na seznam a vrátí ten prvek, pro nějž byla zjištěna (po aplikaci funkce) minimální výsledná hodnota
2 maxi aplikuje předanou funkci na seznam a vrátí ten prvek, pro nějž byla zjištěna (po aplikaci funkce) maximální výsledná hodnota
3 sum aplikuje předanou funkci na seznam a vrátí součet z výsledku
4 cnt aplikuje předanou funkci na seznam a vrátí počet prvků výsledku, které jsou odlišné od NIL

Podívejme se na demonstrační příklady, z nichž bude chování těchto čtyř funkcí vyššího řádu jasně patrné:

; zjištění, které číslo 1..1000 má nejmenší hashovací kód
(mini hash (range 1 1000))
384
 
; zjištění, které číslo 1..1000 má největší hashovací kód
(maxi hash (range 1 1000))
778
 
; nejprve se vytvoří meziseznam s hodnotami od 2 do 11
; posléze se prvky tohoto seznamu sečtou a vrátí se výsledná suma
(sum inc (range 1 10)) 
65
 
; suma čtverců číselné řady
(de sqr [n] (* n n))
sqr
 
(sum sqr (range 1 10))
385
 
; vrátí počet čísel mezi 1 a 100, která bezezbytku dělí 100
(de dividable [x y] (=0 (% x y)))
dividable
 
(cnt (quote [n] (dividable 100 n)) (range 1 100))
9

10. Řízení běhu programu – rozvětvení

Pro řízení běhu programu, tj. pro rozvětvení, nabízí PicoLisp poměrně velké množství různých speciálních forem. Základem je samozřejmě forma if s klasickým rozvětvením, ovšem skalní LISPaři v PicoLispu naleznou například i oblíbené cond či formy when a unless, jejichž použití může zpřehlednit zdrojový kód:

#
1 if rozdělení výpočtu do dvou větví na základě podmínky
2 ifn znamená if-not, tj. varianta if s negovanou podmínkou
3 when varianta if pro větší množství příkazů ve větvi „then“, viz též kapitolu 11
4 unless varianta if pro větší množství příkazů ve větvi „else“, viz též kapitolu 11
5 cond vícenásobné rozvětvení, viz též kapitolu 12
6 nond vícenásobné rozvětvení, viz též kapitolu 12
7 if2 rozvětvení na základě dvou podmínek, více viz kapitolu 13

„Klasické“ rozvětvení je řešeno formou if, kterou lze samozřejmě zanořovat:

(de gcd
    [x y]
    (if (= x y) x
                (if (> x y)
                    (gcd (- x y) y)
                    (gcd x (- y x)))))

11. Použití forem when a unless

V některé části aplikace většinou potřebujeme na základě nějaké podmínky vykonat sekvenci příkazů. I v tomto případě je samozřejmě možné použít if, ovšem celá sekvence příkazů musí být vytvořena v jiné funkci či „uzavřena“ do programového bloku tvořeného formou prog. Pokud například potřebujeme na základě vyhodnocené podmínky vypsat na standardní výstup zprávu a současně vrátit nějakou hodnotu, mohl by celý zápis vypadat například takto:

(setq a 20)
(setq b 10)
(if (=0 (- a a 10))
    (prog
         (println "nulovy vysledek")
         0))
 
"nulovy vysledek"
0

Pro zlepšení čitelnosti zdrojového kódu je možné použít formu when, která sice nedokáže provést úplné rozvětvení tak, jako forma if, ale zato se za ni může napsat libovolné množství forem (příkazů), které se postupně vyhodnotí při splnění zadané podmínky. Výše uvedený příklad se nám tedy zjednoduší:

(setq a 20)
(setq b 10)
(when (=0 (- a a 10))
      (println "nulovy vysledek")
      0)
 
"nulovy vysledek"
0

Opakem when je unless. Jediným rozdílem je zde negace podmínky, což znamená, že unless lze přepsat na when, ovšem samotnou podmínku je zapotřebí negovat, což je samozřejmě daleko méně čitelné, než přímé použití unless:

(unless (=0 (- 1 1))
      (println "nulovy vysledek")
      0)
 
NIL

12. Vícenásobné rozvětvení – forma condnond

Speciální forma cond je pravděpodobně skalním lispařům dobře známá, protože se vlastně jedná o zobecnění rozeskoku na libovolný počet podmínek a větví. Této formě se předává předem neomezený počet dvojic, kde první prvek dvojice představuje podmínku a druhý prvek pak tělo (výraz), který se zavolá při splnění této podmínky. Výsledek vybraného výrazu je současně i výsledkem vyhodnocení celé formy cond (další podmínky se tedy již netestují). Podmínek může být specifikováno libovolné množství a bývá zvykem u poslední podmínky pouze zapsat T (true), což by například v Javě či C odpovídalo větvi default v konstrukci switch:

(de sgn [n]
    (cond
        ((< n 0)        'negative)
        ((> n 0)        'positive)
        ((=0 n)         'zero)))
 
(sgn 10)
positive
 
(sgn -10)
negative
 
(sgn 0)
zero

Alternativně je možné namísto poslední podmínky vložit T (default):

(de sgn [n]
    (cond
        ((< n 0)        'negative)
        ((> n 0)        'positive)
        (T              'zero)))
 
(sgn 10)
positive
 
(sgn -10)
negative
 
(sgn 0)
zero

Funkce nond se chová stejně jako cond, ovšem s tím rozdílem, že všechny podmínky jsou negovány, tj. hledá se ta podmínka, která se vyhodnotí na NIL

(de sgn [n]
    (nond
        ((>= n 0)        'negative)
        ((<= n 0)        'positive)
        (NIL            'zero)))
 
(sgn 10)
positive
 
(sgn -10)
negative
 
(sgn 0)
zero

13. Rozvětvení na základě dvou podmínek – forma if2

Zajímavá a vlastně i velmi užitečná je forma nazvaná if2. Této formě se nepředává jedna podmínka, ale hned dvě podmínky, které jsou vždy obě vyhodnoceny. Výsledkem je tedy kombinace dvou konstant T a NIL (celkem čtyři možnosti). Proto také za oběma podmínkami následují čtyři výrazy, přičemž první výraz se vyhodnotí jen pokud jsou obě podmínky splněny (T T), druhý výraz se vyhodnotí, jen když je splněna první podmínka (T NIL), třetí při splnění pouze druhé podmínky (NIL T) a konečně čtvrtý výraz při nesplnění obou podmínek současně (NIL NIL). Funkci pro zjištění znaménka tedy můžeme zapsat i takto:

(de sgn [n] (if2 (<= n 0) (>= n 0) 'zero 'negative 'positive 'strange))
sgn
 
(sgn 10)
positive
 
(sgn -10)
negative
 
(sgn 0)
zero

Funkci pro výpočet největšího společného dělitele dvou čísel je možné zapsat i takto:

(de gcd
    [x y]
    (if2 (= x y) (> x y)
         NIL
         x
         (gcd (- x y) y)
         (gcd x (- y x))))

Povšimněte si, že první větev (ta s NIL) nikdy nebude provedena, protože obě podmínky nebudou platit současně). Ostatní tři větve však mohou být provedeny..

Poznámka: tím, že jsou vyhodnoceny obě podmínky, se if2 odlišuje od cond, kde se podmínky zkouší vyhodnocovat postupně.

14. Sledování běhu programu s využitím funkcí trace, traceAll a untrace

Při ladění programů, především pak algoritmů využívajících rekurzivní funkce, je důležité vědět, jaké funkce se volají, jaké parametry jsou jim předávány a taktéž způsob návratu z funkcí (výpočet návratových hodnot atd.). Kromě ručního ladění a krokování, které je interpretrem PicoLispu samozřejmě taktéž podporováno, je možné použít i funkci trace, kterou se povoluje trasování zvolené funkce či funkcí. Podívejme se na jednoduchý „školní“ příklad, konkrétně na rekurzivní funkci sloužící pro výpočet faktoriálu. Definice této funkce může vypadat následovně:

(de recursive-factorial
    [n]
    (if (=0 n)
       1
       (* n (recursive-factorial (dec n)))))

V případě, že budeme potřebovat trasovat tuto funkci, není nic jednoduššího, než funkci recursive-factorial zaregistrovat:

(trace 'recursive-factorial)
recursive-factorial

Při volání této funkce i při návratu do funkce (obecně z jiné části programu) se na standardní výstup zobrazí trasovací informace. Odsazením je naznačena hloubka zásobníku při volání. Povšimněte si zde vystřídání dvou fází – rekurzivního zanořování (zabalování, winding) a posléze postupného návratu s výpočtem (rozbalování, unwinding). Poslední řádek naznačuje, že se z funkce nakonec skutečně vrátila správně vypočtená návratová hodnota:

(recursive-factorial 10)
 recursive-factorial : 10
  recursive-factorial : 9
   recursive-factorial : 8
    recursive-factorial : 7
     recursive-factorial : 6
      recursive-factorial : 5
       recursive-factorial : 4
        recursive-factorial : 3
         recursive-factorial : 2
          recursive-factorial : 1
           recursive-factorial : 0
           recursive-factorial = 1
          recursive-factorial = 1
         recursive-factorial = 2
        recursive-factorial = 6
       recursive-factorial = 24
      recursive-factorial = 120
     recursive-factorial = 720
    recursive-factorial = 5040
   recursive-factorial = 40320
  recursive-factorial = 362880
 recursive-factorial = 3628800
3628800

Můžeme si odzkoušet trasovat i složitější funkci, které se předávají dva parametry. Jedná se o funkci pro výpočet největšího společného dělitele dvou celých (kladných) čísel:

(de gcd
    [x y]
    (if (= x y) x
                (if (> x y)
                    (gcd (- x y) y)
                    (gcd x (- y x)))))

Nejprve otestujeme chování této funkce na několika příkladech:

(gcd 1 1)
1
 
(gcd 2 1)
1
 
(gcd 12 16)
4
 
(gcd 54 24)
6

Následně povolíme výpis trasovacích informací při volání této funkce:

(trace 'gcd)
gcd

Podívejme se nyní na to, jak se vlastně výpočet největšího společného dělitele provádí – je to jasně patrné z parametrů, které se rekurzivně volané funkci gcd předávají:

(gcd 54 24)
 gcd : 54 24
  gcd : 30 24
   gcd : 6 24
    gcd : 6 18
     gcd : 6 12
      gcd : 6 6
      gcd = 6
     gcd = 6
    gcd = 6
   gcd = 6
  gcd = 6
 gcd = 6
6

Můžeme zkusit použít i větší vstupní hodnoty. K výsledku se v tomto případě konverguje poměrně dlouho (existují však i rychlejší algoritmy):

(gcd 1000 756)
 gcd : 1000 756
  gcd : 244 756
   gcd : 244 512
    gcd : 244 268
     gcd : 244 24
      gcd : 220 24
       gcd : 196 24
        gcd : 172 24
         gcd : 148 24
          gcd : 124 24
           gcd : 100 24
            gcd : 76 24
             gcd : 52 24
              gcd : 28 24
               gcd : 4 24
                gcd : 4 20
                 gcd : 4 16
                  gcd : 4 12
                   gcd : 4 8
                    gcd : 4 4
                    gcd = 4
                   gcd = 4
                  gcd = 4
                 gcd = 4
                gcd = 4
               gcd = 4
              gcd = 4
             gcd = 4
            gcd = 4
           gcd = 4
          gcd = 4
         gcd = 4
        gcd = 4
       gcd = 4
      gcd = 4
     gcd = 4
    gcd = 4
   gcd = 4
  gcd = 4
 gcd = 4
4

Možnosti trasování jsou však ve skutečnosti mnohem větší, protože lze sledovat i chování funkcí typu = (porovnání) či – (rozdíl). Opět si to můžeme snadno vyzkoušet:

(trace '-)
(trace '=)
(trace 'gcd)

Nyní se při zavolání funkce gcd vypíše mnohem větší množství informací (pro funkce + a – se vždy vypíšou dva řádky – vstupní hodnoty a výsledná hodnota):

(gcd 10 6) 
 gcd : 10 6
  = : 10 6
  = = NIL
  - : 10 6
  - = 4
  gcd : 4 6
   = : 4 6
   = = NIL
   - : 6 4
   - = 2
   gcd : 4 2
    = : 4 2
    = = NIL
    - : 4 2
    - = 2
    gcd : 2 2
     = : 2 2
     = = T
    gcd = 2
   gcd = 2
  gcd = 2
 gcd = 2
2

Trasování lze kdykoli selektivně vypnout s využitím funkce untrace:

(untrace '-)
(untrace '=)
(untrace 'gcd)

Volání funkce gcd již bude probíhat běžným způsobem:

(gcd 10 6)    
2

Poslední užitečnou funkcí je traceAll, která zapne trasování, ale pouze pro (zjednodušeně řečeno) všechny uživatelské funkce a nikoli pro funkce systémové. Můžeme si to ostatně jednoduše vyzkoušet:

(traceAll)
T
 
(gcd 10 6)    
 gcd : 10 6
  gcd : 4 6
   gcd : 4 2
    gcd : 2 2
    gcd = 2
   gcd = 2
  gcd = 2
 gcd = 2
2

15. Literatura

  1. Harold Abelson, Gerald Jay Sussman, Julie Sussman:
    Structure and Interpretation of Computer Programs (SICP)
    1985, 1996, MIT Press
  2. Daniel P. Friedman, Matthias Felleisen:
    The Little Schemer
    1995, MIT Press
  3. Daniel P. Friedman, Matthias Felleisen:
    The Seasoned Schemer
    1995, MIT Press
  4. McCarthy:
    „Recursive functions of symbolic expressions and their computation by machine, part I“
    1960
  5. Guy L. Steele:
    „History of Scheme“
    2006, Sun Microsystems Laboratories
  6. Kolář J., Muller K.:
    „Speciální programovací jazyky“
    Praha 1981
  7. „AutoLISP Release 9, Programmer's reference“
    Autodesk Ltd., October 1987
  8. „AutoLISP Release 10, Programmer's reference“
    Autodesk Ltd., September 1988
  9. McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I.
    „LISP 1.5 Programmer's Manual“
    MIT Press. ISBN 0 262 130 1 1 4
  10. Carl Hewitt; Peter Bishop and Richard Steiger:
    „A Universal Modular Actor Formalism for Artificial Intelligence“
    1973
  11. Feiman, J.:
    „The Gartner Programming Language Survey (October 2001)“
    Gartner Advisory

16. Odkazy na Internetu

  1. The German School of Lisp
    http://blog.fogus.me/2011/05/03/the-german-school-of-lisp-2/
  2. PicoLisp
    http://picolisp.com/wiki/?home
  3. A PicoLisp Tutorial
    http://software-lab.de/doc/tut.html
  4. Pico Lisp Documentation
    http://picolisp.com/wiki/?Do­cumentation
  5. The PicoLisp Machine
    http://software-lab.de/doc/ref.html#vm
  6. PicoLisp na OpenHubu
    https://www.openhub.net/p/PicoLisp
  7. Pico Lisp: A Case for Minimalist Interpreters?
    http://lambda-the-ultimate.org/node/2124
  8. PicoLisp na Wikipedii
    https://en.wikipedia.org/wi­ki/PicoLisp
  9. Programovací jazyk LISP a LISP machines
    http://www.root.cz/clanky/programovaci-jazyk-lisp-a-lisp-machines/
  10. Programovací jazyk LISP (druhá část)
    http://www.root.cz/clanky/programovaci-jazyk-lisp-druha-cast/
  11. Steel Bank Common Lisp
    http://www.sbcl.org/
  12. CLISP (implementace Common Lispu)
    http://clisp.org/
  13. PLEAC-PicoLisp
    http://pleac.sourceforge.net/ple­ac_picolisp/index.html#AEN4
  14. Rosetta Code – Category:Lisp
    http://rosettacode.org/wi­ki/Category:Lisp
  15. Emacs timeline
    http://www.jwz.org/doc/emacs-timeline.html
  16. EINE (Emacs Wiki)
    http://www.emacswiki.org/emacs/EINE
  17. EINE (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?EINE
  18. ZWEI (Emacs Wiki)
    http://www.emacswiki.org/emacs/ZWEI
  19. ZWEI (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?ZWEI
  20. Zmacs (Wikipedia)
    https://en.wikipedia.org/wiki/Zmacs
  21. Zmacs (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?Zmacs
  22. TecoEmacs (Emacs Wiki)
    http://www.emacswiki.org/e­macs/TecoEmacs
  23. Micro Emacs
    http://www.emacswiki.org/e­macs/MicroEmacs
  24. Micro Emacs (Wikipedia)
    https://en.wikipedia.org/wi­ki/MicroEMACS
  25. EmacsHistory
    http://www.emacswiki.org/e­macs/EmacsHistory
  26. Seznam editorů s ovládáním podobným Emacsu či kompatibilních s příkazy Emacsu
    http://www.finseth.com/emacs.html
Našli jste v článku chybu?

26. 4. 2016 20:07

the little schemer (neregistrovaný)

Jak je na tom PicoLisp s TinyScheme? http://tinyscheme.sourceforge.net/home.html

Ideálně bych chtěl vidět něco s REPL na Arduinu. Určitě by šel nějaký ten Forth, ale přecejen to je na mě už dneska hodně hardcore.

26. 4. 2016 15:07

No ve skutecnosti jsou nektere ty vlastnosti docela unikatni, kdyz to porovname ostatnimi dialekty (popr. se Scheme a Clojure).

Vlastnosti #1 az #3 jsou jasne (#1 neplati jen pro Clojure, #3 neplati pro Scheme, jinak asi jo).

Ovsem #4 a #6 uz tedy ne. S #7 si nejsem jisty, mozna to tak funguje v CL, ale nikde jinde ne.

Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Měšec.cz: Golfové pojištění: kde si jej můžete sjednat?

Golfové pojištění: kde si jej můžete sjednat?

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: I církev dnes vyrábí potraviny

I církev dnes vyrábí potraviny

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá