Programovací jazyk LISP (druhá část)

Obsah

1. Malá rekapitulace – programovací jazyk LISP a seznamy

2. Vyhodnocování výrazů LISPem

3. Prefixový zápis aritmetických a relačních výrazů

4. Ale já chci používat „lidský“ zápis aritmetických výrazů!

5. Základní funkce pro práci se seznamy

6. Demonstrační příklady – přístup k prvkům seznamů a zjištění délky seznamu

7. Demonstrační příklady – predikát LISTP a konstrukce seznamů

8. Speciální formy a vyhodnocování podmínek

9. Literatura a odkazy na Internetu

1. Malá rekapitulace – programovací jazyk LISP a seznamy

V předchozí části seriálu o historii výpočetní techniky jsme se seznámili s některými základními vlastnostmi programovacího jazyka LISP. Řekli jsme si, že z hlediska programátorů se v LISPovských aplikacích zpracovávají data uložená v seznamech (odtud ostatně pramení i plný název tohoto jazyka: „List Processing“), přičemž tyto seznamy mohou obsahovat jak takzvané atomy (čísla, řetězce, symboly), tak i další, rekurzivně vnořené seznamy. Interně, tj. v operační paměti počítače, jsou seznamy reprezentovány zřetězenými dvojicemi hodnot (dot-pairs, tečka-dvojice). Každý seznam je ukončen dvojicí, jejíž druhý člen obsahuje namísto ukazatele na další dvojici konstantu nil (tato konstanta je atomem, který se tedy vyhodnocuje vždy sám na sebe, současně se ovšem taktéž jedná o seznam, konkrétně o prázdný seznam, což znamená, že nil má v LISPu zvláštní postavení). Pro přístup k prvnímu členu tečka-dvojice se používá funkce car, pro přístup ke členu druhému funkce cdr (názvy těchto funkcí jsou odvozeny z názvů makroinstrukcí sálového počítače IBM 704, kde sloužily k přístupu k jednotlivým částem 36bitového slova těchto mainframů). Následuje příklad zápisu seznamu pomocí tečka dvojic, následovaného zkráceným zápisem seznamu (který je nejpoužívanější) a taktéž interní reprezentace tohoto seznamu v operační paměti počítače:

; seznam zapsaný pomocí tečka-dvojic
(1.(2.(3.(4.(5.nil)))))

; běžný způsob zápisu téhož seznamu
(1 2 3 4 5)

; interní struktura seznamu v paměti
;         .
;        / \
;       1   .
;          / \
;         2   .
;            / \
;           3   .
;              / \
;             4   .
;                / \
;               5   nil

2. Vyhodnocování výrazů LISPem

Minule jsme si taktéž řekli, že programy jsou v LISPu zapisovány – podobně jako data, se kterými tyto programy pracují – taktéž pomocí seznamů a že interpretry LISPu jsou někdy označovány zkratkou REPL, která naznačuje, jakým způsobem jsou programy, resp. jednotlivé výrazy, ze kterých se programy skládají, zpracovávány: Read–Eval–Print–Loop. Ve skutečnosti však mnoho implementací LISPu obsahuje i plnohodnotné překladače, které mnohdy produkují optimalizovaný kód srovnatelný například s výsledky Céčkových překladačů. Dnes si způsob zápisu programů popíšeme do větších podrobností. Základem interpretace každého LISPovského programu je načtení a rozpoznání jednoho výrazu (read), vyhodnocení tohoto výrazu (eval) a následný tisk výsledné hodnoty výrazu na standardní výstup (print). Pravidla pro vyhodnocení výrazů (někdy se též můžeme setkat s termínem „vyhodnocení forem“) jsou v LISPu velmi jednoduchá a přímočará, na rozdíl od mnoha jiných programovacích jazyků. Tato pravidla lze ve zjednodušené podobě sepsat do několika bodů:

1. čísla a řetězce jsou vyhodnoceny samy na sebe (což je logické – jedná se o dále nedělitelné objekty)
2. hodnotou symbolu je objekt, který je na tento symbol navázán (analogie z jiných programovacích jazyků – hodnotou proměnné zapsané svým jménem je hodnota uložená do proměnné)
3. seznamy jsou vyhodnocovány tak, že se první prvek seznamu chápe jako jméno funkce (či speciální formy), které je předán zbytek seznamu jako parametry této funkce (formy)
4. pokud seznam obsahuje podseznamy, jsou tyto podseznamy vyhodnoceny nejdříve, přičemž úroveň rekurzivního zanořování při vyhodnocování podseznamů není teoreticky omezena (tj. podseznamy lze vnořovat do téměř libovolné úrovně)

Ukažme si vyhodnocování výrazů na několika příkladech. První řádek uvedený pod poznámkou (uvozenou znakem ;) představuje text zapsaný uživatelem na klávesnici, řádek druhý vypisuje samotný LISP:

; vyhodnocení číselné hodnoty (konstanty)
42
42

; vyhodnocení speciální konstanty nil
nil
NIL

; nil je ekvivalentní prázdnému seznamu
()
NIL

; vyhodnocení řetězce
"www.root.cz"

; vyhodnocení seznamu obsahujícího jako první prvek funkci
(max 10 20)
20

; vyhodnocení seznamu obsahujícího další seznamy (každý podseznam samozřejmě znamená volání funkce)
(max (min 10 20) (min 30 40))
30

Obrázek 1: Sálový počítač IBM-704, na němž vznikal první interpret programovacího jazyka LISP.

3. Prefixový zápis aritmetických a relačních výrazů

Zatímco v naprosté většině „mainstreamových“ programovacích jazyků, jakými jsou například Céčko, Java, JavaScript či Python, se aritmetické a logické výrazy zapisují v takzvané infixové notaci, při níž jsou binární operátory zapisovány mezi dvojici operandů, tvůrci jazyka LISP se od tohoto způsobu zápisu distancovali – namísto toho jsou v LISPu všechny základní aritmetické i logické (a samozřejmě též relační) operace zapisovány jako volání funkcí (přesněji řečeno se skutečně jedná o funkce), tj. vždy v prefixové podobě. Důvodů, proč byla zvolena tato forma zápisu výrazů, je více. Prvním důvodem je fakt, že syntaxe LISPu byl navrhována s tím, že později dojde k její změně, tj. samotná syntaxe nebyla pro tvůrce tohoto programovacího jazyka tak prioritní jako jeho sémantika (paradoxní přitom je, že se nakonec syntaxe LISPu nezměnila, takzvané M-výrazy se nedočkaly většího rozšíření, podobně jako další snahy o úpravu syntaxe LISPu tak, aby se eliminovalo množství závorek či právě prefixový zápis aritmetických výrazů).

Druhý důvod spočíval v tom, že zavedení infixových operátorů by do jazyka zavádělo další komplikace: musely by se například řešit a přesně specifikovat priority operací (a u některých operací i jejich asociativita), se zapsanými výrazy by se složitěji prováděly různé symbolické manipulace (integrace, derivace, zjednodušování výrazů), infixové operátory by nebylo možné předávat jako parametry do jiných funkcí atd. Vzhledem k tomu, že aritmetické operátory jsou v LISPu zapisovány jako volání funkcí, musí se znak či jméno příslušného operátoru uvádět ve vyhodnocovaném seznamu na prvním místě, podobně jako jméno jakékoli jiné funkce. Všechny dílčí podvýrazy se samozřejmě vyhodnocují dříve než celý výraz, což plně koresponduje s pravidly, která jsme si uvedli v předchozí kapitole (podvýraz je zapsán formou volání nějaké funkce). Většina aritmetických funkcí není omezena pouze na dva parametry, což znamená, že je například možné zavoláním jedné funkce nazvané + sečíst i více než dvě numerické hodnoty:

; začneme pozvolna jako na základní škole :-)
(+ 1 1)
2

; operace rozdílu - druhý argument funkce je odečten od prvního
(- 1 2)
-1

; součet řady čísel
(+ 1 2 3 4 5 6 7 8 9 10)
55

; níže uvedený výraz v infixové notaci odpovídá: 1-2-3-4-5....-10:
(- 1 2 3 4 5 6 7 8 9 10)
-53

; POZOR - závorky v LISPu nemají mnoho společného
; s vyjádřením priority aritmetických operací
; (nelze je použít tak volně jako například v céčku)
(* (+ 1 2) (+ 3 4))
21

(+ (* 1 2) (* 3 4))
14

; Některé implementace LISPu, například Common Lisp,
; dokážou pracovat se zlomky, tj. snaží se racionální
; čísla vyjádřit formou zlomku (ideální jazyk do škol :-)
(/ 1 2)
1/2

(/ 1 2 3)
1/6

(/ 3 2)
3/2

; zkusíme výpočet složitějšího zlomku
(/ (+ 1 2) (+ 3 4))
3/7

; neracionální (reálná) čísla se vypisují tak, jak to
; známe z ostatních programovacích jazyků (samozřejmě
; v případě speciálních požadavků programátora lze použít
; různé formátovací funkce na úpravu výstupu)
(* 0.3 (/ (+ 1 2) (+ 3 4)))
0.12857144

Programovací jazyk LISP obsahuje i úplnou sadu relačních operátorů, které v závislosti na hodnotách předaných parametrů (operandů) vrací hodnotu T (pravda) či nil (nepravda). Povšimněte si, že konstanta nil má v LISPu poměrně velké množství různých významů:

; porovnání dvou číselných hodnot
; relace "menší než"
(< 1 2)
T

; relace "větší než"
(> 1 2)
NIL

; relace "menší nebo rovno"
(<= 1 2)
T

; relace "větší nebo rovno"
(>= 1 2)
NIL

; porovnání dvou výrazů na ekvivalenci
(equal 1 2)
NIL

(equal 1 1)
T

; podvýrazy se nejprve vyhodnotí a posléze se porovnají
; vyhodnocené výsledky (v tomto případě dva atomy)
(equal (+ 1 1) (/ 4 2))
T

; na ekvivalenci lze porovnávat i seznamy, nikoli pouze atomy
(equal '(1 2) '(1 2))
T

(equal '(1 2) '(2 1))
NIL

; nil se sice v některých pohledech podobá klíčovému slovu
; NULL z SQL ovšem způsob vyhodnocování této konstanty
; v LISPovských výrazech je poněkud odlišný
(equal nil nil)
T

4. Ale já chci používat „lidský“ zápis aritmetických výrazů!

V případě, že se má v nějaké LISPovské aplikaci použít větší množství výpočtů, jež by mohly být při použití prefixové notace nepřehledné, je možné použít hned několik knihoven, které slouží k transformaci výrazů zapsaných infixově („tak jak nás to učili ve škole“) do prefixové podoby. Některé z těchto knihoven dokonce dokážou výrazy různým způsobem zjednodušovat či kombinovat. Například knihovna (spíše knihovnička, protože se skládá jen z několika málo funkcí a maker) infpre určená pro Common Lisp nabízí uživatelům funkci infix->prefix (ano, i takové názvy funkcí je možné v LISPu použít, a to z toho důvodu, že znaky - a > nemají díky absenci operátorů žádný speciální význam), kterou lze použít způsobem ukázaným na následujícím jednoduchém příkladu. Povšimněte si, že mezi operandy a operátory musí být zapsány mezery neboť se jedná o prvky seznamů (první seznam obsahuje sedm atomů – čtyři čísla a tři symboly):

(infix->prefix '(1 + 2 * 3 + 4) '(+ *))
(+ 1 (* 2 3) 4)

Z příkladu je patrné, že funkce infix->prefix vyžaduje dva parametry. Prvním parametrem je seznam obsahující zapsaný aritmetický (či jakýkoli jiný!) výraz, druhým parametrem seznam, v němž jsou uloženy použité operátory. Pořadí operátorů ve druhém seznamu určuje jejich prioritu, což znamená, že s pomocí funkce infix->prefix lze vytvářet i zcela nová pravidla pro vyčíslování aritmetických výrazů (postačuje pouze nadefinovat příslušné funkce a určit priority jednotlivých operátorů). Ve výše uvedeném demonstračním příkladu mohou pozorného čtenáře překvapit apostrofy zapsané před seznam představující aritmetický výraz i před seznam obsahující použité operátory. Tyto apostrofy zabraňují tomu, aby se interpret jazyka LISP snažil seznamy vyhodnotit, což by nutně skončilo chybovým hlášením, protože 1 (první prvek prvního seznamu) zajisté není jménem funkce, ale atom. Uvedení apostrofu (či použití speciální formy quote – viz další text) zabraňuje, aby se interpretr LISPu snažil seznam vyhodnotit, jedná se tedy o opak funkce eval.

5. Základní funkce pro práci se seznamy

Z popisu programovacího jazyka LISP uvedeného v předchozích kapitolách již víme, jakým způsobem se v tomto jazyku zapisují seznamy a dokonce známe i dvě funkce sloužící pro získání prvního prvku seznamu (car) a naopak zbytku seznamu bez jeho prvního prvku (cdr). Vzhledem k tomu, že práce se seznamy tvoří poměrně podstatnou část činnosti programátorů při psaní aplikací, obsahuje programovací jazyk LISP i mnohé další funkce, s jejichž pomocí je možné se seznamy různým způsobem pracovat. Některé z nejčastěji používaných funkcí jsou vypsány v následující tabulce. Jedná se o funkce dostupné v dialektu Common Lisp, proto se v některých jiných dialektech můžete setkat s odlišným pojmenování některých funkcí (například se namísto predikátu LISTP používá LIST?):

6. Demonstrační příklady – přístup k prvkům seznamů a zjištění délky seznamu

Ukažme si použití výše uvedených funkcí na jednoduchých demonstračních příkladech. Použití apostrofu před čtyřprvkovým seznamem opět zabraňuje tomu, aby se interpretr snažil seznam vyhodnotit, tj. volat (neexistující) funkci a s parametry b, c, d.

(car '(a b c d))
A

(cdr '(a b c d))
(B C D)

; cadr odpovídá výrazu (car (cdr seznam))
(cadr '(a b c d))
B
(car (cdr '(a b c d)))
B

(cdar '(a b c d))
nelze vyhodnotit, protože se volá funkce CDR na atom A

; pozor - zde Common Lisp vrací jednoprvkový seznam
(last '(a b c d))
(D)

; prvky seznamu jsou počítány od nuly
(nth 0 '(a b c d))
A

(nth 2 '(a b c d))
C

; pokus o přístup k neexistujícímu prvku seznamu
(nth 4 '(a b c d))
NIL

Zjištění délky seznamu:

(length '(a b c d))
4

7. Demonstrační příklady – predikát LISTP a konstrukce seznamů

Následují příklady použití predikátu LISTP. Vzhledem k tomu, že je LISP dynamicky typovaný jazyk, používají se predikáty v něm napsaných aplikacích poměrně často:

; test, zda je jednička (tj. atom) seznamem
(listp 1)
NIL

; test, zda je výsledek součtu dvou čísel seznamem
(listp (+ 1 2))
NIL

; test, zda je symbol A (atom) seznamem
(listp 'A)
NIL

; (a b c d) je zcela jistě seznam
(listp '(a b c d))
T

; i prázdný seznam je seznam :-)
(listp '())
T

; prázdný seznam a nil jsou ekvivalentní
(listp 'nil)
T

; nil se vyhodnocuje samo na sebe a navíc je
; ekvivalentní s prázdným seznamem - z toho
; vyplývá, že se před něj nemusí psát apostrof,
; protože se nemusíme "bát" vyhodnocení nil
; (trošku se nám to začíná komplikovat :-)
(listp nil)
T

Konstrukce seznamů může být na první pohled poněkud složitější, zejména v případě použití funkce cons (constructor). Když si však uvědomíme, že tato funkce nedělá nic jiného než konstrukci tečka-dvojice z obou předaných parametrů, je její chování zřejmé:

; vytvoření následující paměťové struktury
;   .
;  / \
; A   B
;
(cons 'a 'b)
(A . B)

; vytvoření jednoprvkového seznamu ze symbolu (atomu)
; vytvoří se tato struktura:
;   .
;  / \
; A   nil
;
(cons 'a nil)
(A)

; složitější příklady
(cons '(a b) 'c)
((A B) . C)
; výsledkem je následující struktura
;       .
;      / \
;     .   C
;    / \
;   A   .
;      / \
;     B   nil

; tento příklad je zajímavý, protože první i druhá část
; vytvořené tečka dvojice je sama o sobě seznamem
(cons '(a b) '(c d))
((A B) C D)

; asi nejtypičtější použití funkce cons: přidání
; prvku na začátek seznamu
(cons 'a '(b c d))
(A B C D)
; výsledkem je následující struktura:
;     .
;    / \
;   A   .
;      / \
;     B   .
;        / \
;       C   .
;          / \
;         D   nil

; pokus o přidání jediného prvku na konec seznamu
; pomocí funkce cons se nepodaří
(cons '(a b c) 'd)
((A B C) . D)
; výsledkem je následující struktura
;       .
;      / \
;     .   D
;    / \
;   A   .
;      / \
;     B   .
;        / \
;       C   nil
; která se seznamu podobá jen velmi vzdáleně

; funkce append je v tomto případě výhodnější,
; jen si musíme dát pozor na to, že se spojují
; dva seznamy, nikoli seznam a atom
(append '(a b c) '(d))

8. Speciální formy a vyhodnocování podmínek

Poslední důležitou vlastností jazyka LISP, s níž se dnes seznámíme, je použití takzvaných speciálních forem. Ze syntaktického hlediska jsou speciální formy zapisovány naprosto stejným způsobem jako běžné funkce, ovšem existuje zde jeden významný rozdíl – zatímco u funkcí jsou všechny jejich parametry nejdříve vyhodnoceny, u speciálních forem k tomuto vyhodnocení obecně nedochází, resp. jsou vyhodnoceny pouze některé parametry (které konkrétně, to závisí na tom, o jakou speciální formu se jedná). K čemu jsou speciální formy dobré? Typickým příkladem je zápis podmíněných bloků kódu. V tomto případě potřebujeme, aby se nějaká část programu vykonala pouze v případě, že je splněna (popř. nesplněna) nějaká podmínka, v opačném případě nemá být tato část programu vůbec vykonána. Pomocí běžných funkcí by nebylo možné tuto funkcionalitu splnit, protože by kód (předaný jako parametr – jinou možnost v LISPu ostatně nemáme) vykonal ještě před zavoláním „podmínkové“ funkce. Z toho vyplývá, že samotná podmínka (i když se syntakticky podobá volání funkce) je speciální formou.

Ve většině implementací jazyka LISP existuje speciální forma if, která očekává tři parametry:

1. podmínku (funkci, která se vyhodnotí na T či nil
2. funkci zavolanou v případě, že je podmínka splněna
3. funkci zavolanou v případě, že podmínka není splněna

Příklady použití speciální formy if:

; na základě podmínky se vyhodnotí (a vrátí jako výsledek)
; buď řetězec "mensi" nebo "vetsi"
(if (< 1 2) "mensi" "vetsi")
"mensi"

(if (> 1 2) "mensi" "vetsi")
"vetsi"

; test na ekvivalenci
(if (equal 1 2) "rovno" "nerovno")
"nerovno"

; test na ekvivalenci
(if (equal 1 1) "rovno" "nerovno")
"rovno"

; použití složitějších funkcí ve větvi "then" a "else"
(if (equal 1 1) (+ 10 20) (/ 10 20))
30
(if (equal 1 2) (+ 10 20) (/ 10 20))
1/2

; samotná speciální forma if může být volána uvnitř složitějšího výrazu
(* 84 (if (equal 1 2) (+ 10 20) (/ 10 20)))
42

; ještě jste se neztratili v závorkách? Zkusíme tedy vnořenou
; speciální formu if:
(* 112 (if (< (/ 2 3) (* 2 3)) (if nil (+ 10 20) (- 1 5/8)) (/ 10 20)))
42
; (že by Velká otázka zněla právě takto?)

Následující demonstrační příklad čeká po svém spuštění na vstup od uživatele, protože se volá funkce read (to je ono první písmeno v označení REPL). V případě, že uživatel zapíše na standardní vstup symbol a či A, je zavolána funkce print, v opačném případě je zavolána funkce format-disk (která neexistuje :-). Povšimněte si, že pokud uživatel zadá symbol A či a, je interpretru LISPu úplně jedno, že funkce format-disk ve skutečnosti neexistuje, protože se ji ani nepokusí vykonat:

(if (equal (read) 'A) (print "v poradku") (format-disk))

S dalšími speciálními formami se seznámíme v následující části seriálu.

9. Literatura a odkazy na Internetu

1. McCarthy
   „Recursive functions of symbolic expressions and their computation by machine, part I“
   1960
2. Guy L. Steele
   „History of Scheme“
   2006, Sun Microsystems Laboratories
3. Kolář J., Muller K.:
   „Speciální programovací jazyky“
   Praha 1981
4. „AutoLISP Release 9, Programmer's re­ference“
   Autodesk Ltd., October 1987
5. „AutoLISP Release 10, Programmer's re­ference“
   Autodesk Ltd., September 1988
6. McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I.
   „LISP 1.5 Programmer's Ma­nual“
   MIT Press. ISBN 0 262 130 1 1 4
7. Carl Hewitt; Peter Bishop and Richard Steiger
   „A Universal Modular Actor Formalism for Artificial Intelligence“
   1973
8. Feiman, J.
   „The Gartner Programming Language Survey (October 2001)“
   Gartner Advisory
9. Lisp (programming language)
   http://en.wiki­pedia.org/wiki/Lis­p_(programmin­g_language)
10. On Lisp
    http://paulgra­ham.com/onlis­ptext.html?as­df
11. Lambda calculus
    http://en.wiki­pedia.org/wiki/Lam­bda_calculus
12. A Short Introduction to the Lambda Calculus
    http://www.cs­.bham.ac.uk/~ax­j/pub/papers/lam­bda-calculus.pdf
13. A Tutorial Introduction to the Lambda Calculus
    http://www.inf.fu-berlin.de/leh­re/WS03/alpi/lam­bda.pdf
14. Scheme (programming language)
    http://en.wiki­pedia.org/wiki/Sche­me_(programmin­g_language)
15. An Introduction to Scheme and its Implementation
    ftp://ftp.cs.u­texas.edu/pub/gar­bage/cs345/sch­intro-v14/schintro_toc­.html
16. The latest version of the Scheme standard: R6RS
    http://www.r6rs­.org/
17. Humor on Computers, Systems and Programming
    http://www-crypto.htw-saarland.de/we­ber/misc/program­ming.html
18. Teach Yourself Scheme in Fixnum Days
    http://www.ccs­.neu.edu/home/do­rai/t-y-scheme/t-y-scheme.html
19. AutoLISP
    http://en.wiki­pedia.org/wiki/Au­toLISP
20. Rosetta Code – Category:Lisp
    http://rosetta­code.org/wiki/Ca­tegory:Lisp