Hlavní navigace

Jemný úvod do LISPu

Daniel Novotný 21. 4. 2004

Programovacích jazyků je velmi mnoho. Rád bych vám v tomto článku představil jeden z nich, jazyk LISP. Tento jazyk je určený zejména pro programování umělé inteligence - mezi jeho vestavěné datové typy patří totiž symboly a seznamy. Dá se však, díky své flexibilitě a ortogonalitě, použít i pro jiné úkoly než tvorbu AI. LISP je také vhodný vnitřní programovací jazyk nějaké aplikace: určitě víte, že jej používá editor EMACS, dále například hra Abuse, AutoCAD nebo prohlížeč fraktálů XaoS.

Jak už jsem psal, LISP se používá pro manipulaci se symboly. K tomu používá tzv. s-výrazy (s-expressions, zkratka z „symbolické výrazy“). Základním s-výrazem je atom. Atomem může být buď číslo, nebo symbol. Čísla se zapisují úplně normálně jako v libovolném programovacím jazyce a při vyhodnocení vracejí samy sebe:

[4]> 12
12
[5]> 0.432434
0.432434

Symboly se používají k tomu, k čemu v jiných programovacích jazycích proměnné. Se symbolem může být svázána jednak hodnota a jednak funkce. Při vyhodnocení se LISP snaží najít hodnotu, která je se symbolem svázána. Nyní nic nenajde, protože jsme si ještě neřekli, jak hodnoty symbolům přiřazovat:

[8]> A

*** - EVAL: variable A has no value
1. Break [9]>

Dalším datovým typem jsou seznamy. Podle nich je také LISP pojmenován: LISP je zkratka z LISt Processing – manipulace se seznamy. Seznamy se zapisují takto: (A B C 33). Toto je čtyřprvkový seznam, seznamy samozřejmě mohou rekurzivně obsahovat další seznamy: (FREEBSD SUNOS (DEBIAN REDHAT SUSE) HURD) je opět čtyřprvkový seznam, jedním z jeho prvků je tříprvkový seznam. Pokud se pokusíme takovýto seznam vyhodnotit, narazíme:

[10]> (FREEBSD SUNOS (DEBIAN REDHAT SUSE) HURD)

*** - EVAL: the function FREEBSD is undefined
1. Break [11]>

Z chybové hlášky vidíme, že LISP se při vyhodnocování snaží dívat se na první prvek seznamu jako na funkci. LISP totiž postupuje takto: pokud má vyhodnotit seznam, vyhodnotí nejdříve rekurzivně všechny prvky seznamu mimo prvního, potom se první prvek snaží interpretovat jako funkci, kterou zavolá a předá jí jako parametry zbytek seznamu. Jako příklad si vezmeme funkci +, která očekává jako argumenty čísla, a vrátí jejich součet:

[15]> (+ 1 1 1)
3

můžeme používat i další aritmetické funkce:

[16]> (* 2 2 (/ 15 3) (sqrt 4) )
40

a nejenom aritmetické – LISP obsahuje spoustu funkcí pro manipulaci se seznamy – zkusíme si jednoduchou funkci LIST, která prostě dá své argumenty do seznamu, funkci FIRST vracející první prvek seznamu, REST vracející zbytek a nakonec operaci množinového průniku:

[18]> (list 1 2 3 4)
(1 2 3 4)
[19]> (first (list 1 2 3 4) )
1
[20]> (rest (list 1 2 3 4) )
(2 3 4)
[21]> (intersection (list 1 2 3 4) (list 3 4 5) )
(3 4)

ovšem nyní narazíme:

[25]> (list x y z)

*** - EVAL: variable X has no value
1. Break [26]>

zkuste sami popřemýšlet, proč to nefunguje. No – nebudu vás napínat, je to proto, že se LISP snaží vyhodnotit argumenty funkce LIST, a narozdíl od čísel, která se vyhodnocují sama na sebe, u symbolů se LISP dívá na hodnotu, kterou jsme jim ještě nepřiřadili – ani jsme si zatím neřekli jak.

Slouží k tomu funkce SET, která má dva argumenty: první se vyhodnotí na symbol a druhý na jeho hodnotu. Ovšem toto opět fungovat nebude:

[1]> (set a 1)

*** - EVAL: variable A has no value
1. Break [2]>

LISP se zde snažil vyhodnotit A-čko. Ale my tam chceme A-čko „jako takové“. Pokud o tom tak přemýšlíme, musíme mít nějaký mechanismus, který řekne LISPu, že daný s-výraz nemá vyhodnocovat, ale předat „tak jak je“. K tomu slouží tzv. speciální formy. Speciální formy navenek vypadají jako funkce, ale liší se ve způsobu, jakým pracují s argumenty – každá speciální forma má svůj vlastní způsob, jak, kdy a zda vůbec své argumenty vyhodnotí. Například velmi jednoduchá speciální forma QUOTE svůj jediný argument nevyhodnocuje a prostě jej předá:

1. Break [2]> (QUOTE A)
A
1. Break [2]> (QUOTE (LINUX FREEBSD MAC_OS) )
(LINUX FREEBSD MAC_OS)
1. Break [2]> (set (quote a) 3)
3
1. Break [2]> A
3
1. Break [2]> (set (quote a) (quote b) )
B
1. Break [2]> a
B
1. Break [2]> (set (quote a) (quote (a b c) ) )
(A B C)
1. Break [2]> (rest a)
(B C)
1. Break [2]>

Tak – toto je v podstatě všechno, co se týče LISPu jakožto jazyka: přidáváním dalších funkcí, speciálních forem a primitivních datových typů už můžeme vybudovat celý zbytek. LISP je tím pádem velmi ortogonální: je zde pouze malé množství základních primitiv, co se týče definice jazyka, a jejich skládáním a definováním vzniká vše ostatní – i řídící struktury jako IF či WHILE jsou vhodné speciální formy a můžeme klidně další řídící struktury definovat.

Je tu také syntaktický cukr pro nejčastěji používanou speciální formu QUOTE – apostrof. 'X tedy znamená to samé jako (QUOTE X), pouze je zápis o hodně kratší. Protože první parametr funkce SET bývá většinou „quotován“, existuje další zkratka: speciální forma SETQ, která funguje jako SET až na to, že svůj první argument nevyhodocuje:

[3]> '(MONITOR DISK MYS)
(MONITOR DISK MYS)
[4]> (setq hardware '(MONITOR DISK MYS))
(MONITOR DISK MYS)
[5]> (length hardware)
3

Vestavěných funkcí je velmi mnoho. Paleta funkcí závisí na dialektu LISPu, já používám Common LISP, který je standardizován ANSI. Už jsme si ukázali aritmetické funkce, dále máme mnoho funkcí na manipulaci se seznamy – ukázali jsme si funkce FIRST a REST (které se z historických důvodů také jmenují CAR a CDR), funkci LENGTH vracející délku seznamu, množinovou funkci INTERSECTION (také jsou tu funkce UNION a SET-DIFFERENCE, sjednocení a množinový rozdíl), kromě funkce LIST se dají k tvorbě seznamů použít i jiné funkce APPEND (argumenty: libovolný počet seznamů, vrací seznam vzniklý jejich spojením) a CONS (argumenty: první prvek a seznam, přidává prvek do seznamu a vrací takto vytvořený seznam). Také tu jsou funkce PUSH a POP pro práci se seznamem jako se zásobníkem, funkce MEMBER, která hledá, zda je její první argument prvkem druhého… Nebo funkce MAPCAR, která aplikuje svůj první argument – funkci – postupně na všechny prvky druhého argumentu – seznamu:

[18]> (mapcar 'sin '(0 0.5 1) )
(0 0.47942555 0.84147096)
[19]>

Ještě jsem se nezmínil o predikátech – funkcích vracejících logickou hodnotu. Z hlediska logické hodnoty jsou zajímavé atomy T a NIL. NIL se používá jako nepravdivá hodnota (false) a je totožný s prázdným seznamem. Naproti tomu T je „kanonická“ pravdivá hodnota, ovšem jako pravdivá hodnota funguje vše různé od NIL. T i NIL se vyhodnocují samy na sebe. Používají se v „podmínkových“ speciálních formách jako např. IF:

[20]> (> 1 2)
NIL
[21]> (> 2 1)
T
[22]> (if (> 1 2) 'VETSI 'MENSI-NEBO-ROVNO)
MENSI-NEBO-ROVNO

Tak – vestavěné funkce už známe – a co takhle si definovat nějakou svoji? K tomu slouží DEFUN:

[22]> (defun add3 (x) (+ x 3) )
ADD3
[23]> (add3 1)
4
[24]> (mapcar 'add3 '(14 0 2) )
(17 3 5)
[25]>

můžeme samozřejmě používat i rekurzi:

[4]> (defun faktorial (x)
(if (> x 1)
    (* x (faktorial (- x 1) ) )
    1
)
)
FAKTORIAL
[5]> (faktorial 6)
720
[6]> (faktorial 100)
93326215443944152681699238856266700490715968264381621
46859296389521759999322991560894146397615651828625369
7920827223758251185210916864000000000000000000000000
[7]>

(Pozn. ed.: faktoriál natrhán kvůli sazbě –Johanka)

Obecně defun vypadá takto: (defun jméno-fce (param1 param2 … paramn) tělo) a ještě se tam mohou vyskytovat „vychytávky“ jako nepovinné parametry (&optional), „klíčové“ parametry (&key) nebo parametr &rest, který „pohltí“ všechny zbylé parametry a vytvoří z nich seznam, jenž je pak vevnitř ve funkci k dispozici.

Příklad na &key:

[32]> (defun foo (&key (x 'Linux) (y 'Dos) ) (list x y) )
FOO
[33]> (foo :x 1 :y 2)
(1 2)
[34]> (foo :y 'SUNOS :x 'BSD)
(BSD SUNOS)
[35]> (foo :x 1)
(1 DOS)
[36]> (foo :y 2)
(LINUX 2)
[37]> (foo)
(LINUX DOS)
[38]> 

Pěknou věcičkou jsou anonymní funkce, vytvářené pomocí atomu LAMBDA – jde o „jednorázovou“ funkci, použitelnou jako literál typu funkce na místě, kde se funkce očekává:

[37]> ( (lambda (x) (- x 1) )  2)
1
[38]> (mapcar (lambda (x) (* x 2) )  '(1 2 3 4 5) )
(2 4 6 8 10)
[39]>

Jistě si dovedete představit jakou vyjadřovací sílu tím dostáváme do rukou.

Možná jste si všimli, že v LISPu není v podstatě rozdíl mezi kódem a daty – obojí má stejnou strukturu s-výrazu. Této jednotnosti můžeme samozřejmě využít: funkce může analyzovat jinou funkci, nebo může jinou funkci „on-the-fly“ sestavit a pak pomocí funkce EVAL zavolat. Jednoduchý příklad:

[1]> (setq a () )
NIL
[2]> (push 2 a)
(2)
[3]> (push 3 a)
(3 2)
[4]> (push 8 a)
(8 3 2)
[5]> (push '+ a)
(+ 8 3 2)
[6]> a
(+ 8 3 2)
[7]> (eval a)
13
[8]>

To by bylo všechno k problematice funkcí. Dále bych se chtěl zmínit o tom, že datových typů je v současných LISPech více než jen čísla, symboly a seznamy. Common Lisp obsahuje stringy, pole, hashe, dokonce i objekty ve smyslu OOP. Už nemám prostor na to, abych se o těchto jevech zmínil, možná někdy příště.

Na závěr pár linků:

Common Lisp The Language 2nd edition
CLISP – implementace Common Lispu

Našli jste v článku chybu?

23. 4. 2004 15:29

iolover (neregistrovaný)

a poznate http://www.iolanguage.com?

23. 4. 2004 14:03

Jancll (neregistrovaný)

Ja chci taky!!! Parace za sebou jeste nemam a kdyz nebudu mit co delat napriklad ve vlaku...

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

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

Lupa.cz: Slevové šílenství je tu. Kde nakoupit na Black Friday?

Slevové šílenství je tu. Kde nakoupit na Black Friday?

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

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

Přehledná titulka, průvodci, responzivita

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

120na80.cz: Bojíte se encefalitidy?

Bojíte se encefalitidy?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET

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č?

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

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

Lupa.cz: Není sleva jako sleva. Jak obchodům nenaletět?

Není sleva jako sleva. Jak obchodům nenaletět?

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

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

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

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU