IT Laboratoř

V dnešním článku o Lispu si povíme něco o tečkových párech a o seznamech. Konečně budeme moci stvořit funkci, která vrátí trochu složitější výraz než pouze číslo.

Tečkové páry

Základní struktura v Lispu je tvořena tzv. tečkovými páry. O co jde? Jedná se o dvojici hodnot, která se navenek tváří jako jakási jednolitá struktura, je to tedy další výraz a jakožto takový ho můžeme například vrátit ve funkci. Jak vytvoříme tečkový pár? Obvykle se tvoří pomocí funkce cons, která bere dva argumenty: levou část tečkového páru a pravou část tečkového páru. Tečkový pár běžně zapisujeme takto: 1 . 2. Takovýto tečkový pár bychom vytvořili touto konstrukcí:

> (cons 1 2)
(1 . 2)

Samozřejmě jednotlivé složky můžeme také číst. K tomu slouží funkce car [kar] a cdr [kudr]. Funkce car vrací první složku tečkového páru, kdežto cdr vrací druhou část. Předvedeme si to na příkladech:

> (car (cons 1 2))
1

> (cdr (cons 1 2))
2

Argument předaný funkci cons se samozřejmě vyhodnocuje, takže když předáme (cons (+ 1 2) 3), tak dostaneme tečkový pár (3 . 3). Základy práce s tečkovými páry máme za sebou, takže už můžeme naprogramovat výpočet kořenů kvadratické funkce:

(defun na2(a)
  (* a a))

(defun deter(a b c)
  (- (na2 b) (* 4 a c)))

(defun x12(a b c)
  (cons
   (/ (+ (- b) (sqrt (deter a b c))) (* 2 a))
   (/ (- (- b) (sqrt (deter a b c))) (* 2 a))))

> (x12 1 5 6)
(-2.0 . -3.0)

Jak to celé funguje? První dvě funkce by měly být jasné – první počítá druhou mocninu a druhá funkce vrací determinant. Třetí funkce vrací tečkový pár, na jehož první pozici se nachází jeden kořen a na druhé pozici druhý kořen. Počítá se to podle klasického vzorečku, akorát převedeného do Lispových pravidel. Funkce sqrt vrací druhou odmocninu. Po zavolání funkce proběhnou výpočty a objeví se tečkový pár. Vzhledem k tomu, že tam dělíme a odmocňujeme, tak bude výsledek reálné číslo (proto ta nulová desetinná část).

Složené tečkové páry

Už se mílovými kroky blížíme k základnímu stavebnímu kameni všech Lispových programů – k seznamům. Jak už jsme si řekli, tečkový pár obsahuje dvě části – levou a pravou. Do těchto částí můžeme uložit prakticky cokoliv. Záleží jen na nás, co necháme na daná místa vyhodnotit. Takže se může stát, že třeba v pravé části tečkového páru bude další tečkový pár. Příklad:

> (cons 1 (cons 2 3))
(1 2 . 3)

Vidíme, že už to skoro vypadá jako seznam :-). Lisp používá takovou trochu zkrácenou verzi značení tečkových párů. Existuje více modelů, ten nejpřímější a nejsložitější vypadá takto: (1 . (2 . 3)). Ale značení není zase tak důležité, navíc bývá v případě potřeby intuitivní.

I na tento složený tečkový pár můžeme aplikovat naše staré známé funkce car a cdr. Jaké budou dávat výsledky? car vrátí jedničku, kdežto cdr vrátí zase tečkový pár:

> (car (cons 1 (cons 2 3)))
1

> (cdr (cons 1 (cons 2 3)))
(2 . 3)

Výsledky jsou očekávatelné. Na prvním místě tečkového páru je číslo jedna, na druhém místě je tečkový pár. Nejhezčí na těchto funkcích je, že je můžeme skládat. Takže pokud bychom z toho tečkového páru chtěli vytáhnout třeba dvojku, použijeme tento seznam:

> (car (cdr (cons 1 (cons 2 3))))
2

Jak bude probíhat vyhodnocování? Nejprve vznikne tečkový pár (1 . (2 . 3)). Z tohoto tečkového páru vememe cdr, což nám vrátí (2 . 3) a odtud pomocí car vytáhneme dvojku. A abychom nemuseli takto složitě skládat car a cdr, můžete používat zkráceniny ve tvaru CAAR, CADR, CDAR atd. Výraz (cadr x) je ekvivalentní složenině (car (cdr x)). Výraz (cdar x) je ekvivalent pro (cdr (car x)). Předchozí výraz bychom zkráceně zapsali jako:

> (cadr (cons 1 (cons 2 3)))
2

Seznamy

Poslední poznámka před tím, než si nadefinujeme seznam. V Lispu existuje false hodnota, které se říká NIL. Je to lispový ekvivalent pro nepravdu. Pravda se mimochodem značí pouhým t. Obdobnou hodnotu jako NIL může plnit prázdný seznam. Prázdný seznam vypadá docela intitivně takto: (). Jsou to ekvivalenty.

Jak tedy vypadá seznam? Seznam je vnitřně konstruován jako posloupnost do sebe vnořených tečkových párů, na jehož poslední místě je prázdný seznam / NIL. Příkladem jednoduchého seznamu může být výraz (cons 1 nil). Toto se vyhodnotí na jednoprvkový seznam (1). Víceprvkové seznamy bychom zapsali takto:

> (cons 10 (cons 15 (cons 20 nil)))
(10 15 20)

> (cons -5 (cons 5 nil))
(-5 5)

V minulých článcích jsme si říkali, že seznamy se do sebe mohou zanořovat. Jak to provedeme, by již mělo být jasné – zkrátka namísto přímé hodnoty vložíme další tečkový pár. Seznam ((1 2) (3 4)) bychom mohli zapsat takto:

> (cons (cons 1 (cons 2 nil)) (cons (cons 3 (cons 4 nil)) nil))
((1 2) (3 4))

Pozor na to, že i vnitřní seznamy musí být vždy ukončeny prázdným seznamem (NIL).

Protože seznamy jsou zakuklené tečkové páry, můžeme na ně používat klasické konstruktory car a cdr. Je si musíte uvědomit, co která funkce vrací. V případě jednoduchého seznamu (ve kterém není zanoření) vrací car vždy konkrétní číslo a cdr vrací seznam, tzv. ocas seznamu. Proto nemůžete u jednoduchého seznamu udělat dvakrát car za sebou, protože car z čísla udělat nejde. Příklady:

; pro jednoduchost uložíme seznam do proměnné
> (setf seznam (cons 1 (cons 2 (cons 3 nil))))
(1 2 3)

> (car seznam)
1

> (cdr seznam)
(2 3)

> (cadr seznam)
2

> (caddr seznam)
3

> (cddr seznam)
(3)

> (cdddr seznam)
NIL

Vidíme, že pokud jsme naposledy volali funkci car, bylo výsledkem číslo, kdežto když jsme volali pouze cdr, vrátil se nám seznam. Pouze v případě, kdy jsme provedli třikrát cdr, vrátilo se nám NIL (což je ale vlastně také seznam – prázdný). NIL se vrátilo proto, že výsledkem cdr u posledního tečkového páru v seznamu je zkrátka NIL.

Kvótování

Vytvářet seznamy pokaždé pomocí funkce cons může být velice kontraproduktivní, protože je to jednoduše zdlouhavé a nepřehledné. Proto existuje speciální operátor quote. Tento operátor ruší klasický vyhodnovací proces, což má mimojiné za následek to, že můžeme konečně vytvořit seznam jednoduchým a pohodlným způsobem. Operátor quote zkrátka převeme argument a vrátí ho v nevyhodnocené podobě. Příklady s jednoduchými výrazy:

> (quote a)
A

> (quote abrakadarba)
ABRAKADARBA

Abychom si to ještě více zjednodušili, můžeme namísto operátoru quote používat zkratku v podobě apostrofu:

> 'a
A

> 'abrakadabra
ABRAKADABRA

Jak to využijeme na tvorbu seznamů? Zkrátka předáme operátoru seznam a on ho nevyhodnotí a vrátí nám ho v nezměněné podobě:

> (quote (a 1 2 3))
(A 1 2 3)

> '(a 1 2 3)
(A 1 2 3)

Jak vidíme, seznam se skutečně nevyhodnotil. Kdyby se vyhodnocoval, Lisp by zařval, protože na symbolu a nemáme navázanou žádnou funkci.

Funkce list

Dnes si ještě představíme ještě jednu funkci na tvorbu seznamů. Tou je funkce list. Funkce list je trošičku podobná operátoru quote, akorát bere libovolný počet argumentů a jednotlivé argumenty před naházením do listu vyhodnocuje. Takže nejprve jednoduché příklady:

> (list 1 2 3)
(1 2 3)

> (list 5)
(5)

> (list)
NIL

A teď ten rozdíl oproti quote. Pokud zkusíte zakvótovat tento seznam: (+ 2 5), tak nedojde k jeho vyhodnocení a výsledný seznam bude vrácen v této nezměněné podobě.

> (quote (+ 2 5))
(+ 2 5)

> '(+ 2 5)
(+ 2 5)

Kdežto funkce list své argumenty vyhodnocuje, takže když listu předáme stejný argument, bude v seznamu pouze sedmička:

> (list (+ 2 5))
(7)

Proto taky nemůžeme pouze pomocí list vytvořit seznam tvořený ze symbolů. Pokud chceme vytvořit seznam (a b c), musíme jednotlivé symboly kvótovat:

> (list a b c)
Error: The variable A is unbound.

> (list 'a 'b 'c)
(A B C)

Quote zkrátka veme svůj argument a vůbec se nepárá s vyhodnocováním, na rozdíl od list, což není speciální operátor, ale obyčejná funkce, a proto tam probíhá klasický vyhodnocovací proces.

Další díly seriálu

• Lisp I: Funkcionální programování a Lispworks
• Lisp II: Úvod do jazyka
• Lisp III: Funkce, vyhodnocování funkcí
• Lisp IV: Tečkové páry, seznamy, kvótování (právě čtete)