Speciální formy, lambda výrazy a makra v programovacím jazyku LISP

1. 4. 2010

Doba čtení: 17 minut

Líbí se vám článek?
Podpořte redakci

V dnešní části seriálu o historii výpočetní techniky dokončíme popis základních vlastností programovacího jazyka LISP. Ukážeme si, jakým způsobem se v LISPu (přesněji řečeno v dialektu Common Lisp) vytváří a volají uživatelské funkce, řekneme si, k čemu je možné využít lambda výrazy a nakonec si popíšeme základy tvorby maker v Common Lispu i způsob využití již hotových maker, které jsou programátorům dostupné v Common Lispovských knihovnách.

Obsah

1. Tvorba uživatelských funkcí

2. Lambda výrazy

3. Makra v Common Lispu

4. Makra a tajemné znaky ` , a @

5. Výpis expandovaného makra

6. Příklady použití knihovního makra „loop“: operace nad seznamy

7. Příklady použití knihovního makra „loop“: počítané smyčky

8. Literatura

9. Odkazy na Internetu

1. Tvorba uživatelských funkcí

V programovacím jazyce LISP je možné kromě základních (interních, primitivních) funkcí definovat a následně i volat funkce uživatelské, podobně jako v mnoha dalších programovacích jazycích. Ve skutečnosti je velká část programů napsaných v LISPu tvořena právě definicemi nových funkcí. V Common Lispu, což je jedna z nejrozšířenějších a také nejkomplexnějších implementací tohoto jazyka, se funkce vytváří pomocí speciální formy nazvané defun (define function). Formát volání formy defun při tvorbě nové funkce je velmi jednoduchý, programátor si ovšem musí dát pozor na správné uzávorkování:

(defun název_funkce(parametry funkce) tělo funkce)

Návratovou hodnotou nově vytvořené funkce (po jejím zavolání a vykonání) je hodnota výrazu tvořícího tělo funkce, což znamená, že není nutné používat nějakou formu příkazu return tak, jak je tomu v mnoha dalších programovacích jazycích. Ukažme si nyní způsob vytvoření dvou jednoduchých funkcí a následného zavolání těchto funkcí:

; funkce vracející druhou mocninu svého jediného parametru
(defun sqr(x) (* x x))

; funkce, která sečte hodnoty svých dvou parametrů a vrátí výsledek součtu
(defun plus(x y) (+ x y))

; zavoláme první funkci
(sqr 42)
1764

; a nyní druhou
(plus 2 3)
5

; funkce lze samozřejmě libovolným způsobem kombinovat
(plus (sqr 3) (sqr 4))
25

2. Lambda výrazy

Způsob vytváření nových funkcí, který byl ukázán v předchozí kapitole, není jediný možný, protože LISP obsahuje mnohem obecnější a v několika ohledech i zajímavější mechanismus nazývaný lambda definice nebo lambda výrazy představovaný speciální formou lambda. Slovo „lambda“ není zvoleno náhodně, protože princip lambda výrazů vychází ze slavné Churchovy teorie Lambda kalkulu. Zatímco funkce vytvořené pomocí speciální formy defun jsou pojmenované (a lze je tedy volat zápisem jejich jména v programu), funkce vytvořené pomocí speciální formy lambda jméno nemají, takže se taktéž označují termínem anonymní funkce. Na následující dvojici příkladů je ukázán způsob vytvoření anonymní funkce (která není nikde použita) a následně vytvoření a současně i zavolání anonymní funkce:

; pouze vytvoření anonymní funkce bez jejího dalšího použití
; (umělý příklad)
(lambda (x) (* x x))

; vytvoření anonymní funkce a její zavolání s parametrem 42
((lambda (x) (* x x)) 42)
1764

K čemu jsou ale lambda výrazy dobré, když lze pomocí nich vytvořit „pouze“ bezejmenná funkce? Použití bezejmenných funkcí je výhodné v tom případě, když funkce má být použita pouze na jednom místě v programu. Funkce je zde přímo explicitně definována, což může zlepšit čitelnost programu. Ukažme si to na jednoduchém příkladu. Prakticky všechny dialekty jazyka LISP obsahují primitivní funkci mapcar, která aplikuje nějakou jinou funkci na všechny prvky seznamu (použitím funkce mapcar lze nahradit velké množství programových smyček). Pokud například potřebujeme získat druhé mocniny číselných hodnot uložených v seznamu, můžeme nejdříve vytvořit funkci sqr, kterou potom pomocí mapcar aplikujeme na všechny potřebné hodnoty:

(defun sqr(x) (* x x))
(mapcar 'sqr '(1 2 3 4 5))
; výsledkem předchozího volání je nový seznam
(1 4 9 16 25)

Pokud by byla funkce sqr použita jen na jediném místě programu, je zbytečné, aby její jméno bylo uloženo v jeho jmenném prostoru a bude tedy výhodnější použít anonymní funkci, která se navíc vytváří přímo v místě, kde má být použita (nemusíme tedy hledat definici funkce v celém programu nebo v jeho knihovnách):

(mapcar (lambda (x) (* x x)) '(1 2 3 4 5))
(1 4 9 16 25)

Poznamenejme, že výsledkem lambda výrazu je plnohodnotný LISPovský objekt, který je například možné uložit do proměnné a následně lze takovou „pojmenovanou anonymní funkci“ zavolat pomocí funcall:

; vytvoříme anonymní funkci, kterou uložíme do proměnné "z"
(setq z (lambda(x) (* x x)))
#<FUNCTION :LAMBDA (X) (* X X)>
; výše uvedený řádek je vypsán protože se jedná o návratovou hodnotu
; speciální formy setq (set quote)

; zavolání funkce
(funcall z 42)
1764

3. Makra v Common Lispu

Jednou z nejzajímavějších vlastností LISPu (přesněji řečeno některých jeho implementací, jejíchž typickým zástupcem je v nadpisu této kapitoly zmíněný Common Lisp) je možnost tvorby maker. Vzhledem k tomu, že LISPovské programy jsou tvořeny, stejně jako data, pomocí rekurzivně vnořených seznamů, jsou LISPovská makra založena na manipulaci se seznamy tvořícími program, což je velký rozdíl například oproti makrům implementovaným v céčkovém preprocesoru, kde se jedná o poměrně jednoduché textové záměny. Vzhledem k tomu, že LISPovská makra dokážou manipulovat s vlastním programem, je možné pomocí nich vytvářet například úplně nové jazykové konstrukce (různé smyčky, podmíněné příkazy, částečně vyhodnocované formy atd.) s vlastní syntaxí, což je poměrně unikátní vlastnost, kterou u většiny dalších programovacích jazyků nenajdeme. Způsob definice maker se v některých ohledech podobá definici funkcí, ale mezi funkcemi a makry existuje jeden zásadní rozdíl.

LISPovské funkce získávají jako svoje argumenty LISPovské hodnoty, tj. většinou atomy, (anonymní) funkce nebo seznamy, a vrací taktéž nějakou LISPovskou hodnotu – opět se může jednat o atom, (anonymní) funkci nebo seznam. Funkce jsou vyhodnocovány (volány) až při spuštění programu. Makra jako svůj vstup získávají LISPovský kód (zapsaný formou rekurzivně zanořeného seznamu) a vrací taktéž LISPovský kód, což nepředstavuje oproti funkcím žádný zásadnější rozdíl. Ovšem na rozdíl od funkcí jsou makra volána již při prvotním zpracovávání programu, podobně jako jsou céčková makra zpracovávána céčkovým preprocesorem (cpp) ještě před vlastní kompilací. Teprve výsledek volání makra (nazývaný taktéž expanze makra) je považován za zápis výrazu, který může být dále zpracován, tj. buď vyhodnocen (interpretační varianty LISPu) nebo zkompilován (varianty LISPu vybavené překladačem). Poznamenejme ještě, že v těle makra se může vyskytovat volání dalšího makra, což znamená, že LISP musí při expanzi maker použít rekurzi.

4. Makra a tajemné znaky ` , a @

Při zápisu maker se poměrně často používají znaky ` (zpětný apostrof), , (čárka) a @ (zavináč). Zpětný apostrof se zapisuje před seznam, kde má podobný význam jako běžný apostrof, který, jak již víme, zabraňuje tomu, aby byl seznam vyhodnocen (jedná se o zkrácený zápis speciální formy quote). V případě zpětného apostrofu je taktéž zabráněno vyhodnocení seznamu, který se za apostrofem nachází, ovšem navíc lze uvnitř takového seznamu použít symbol čárka, který označuje ty položky seznamu, které se naopak vyhodnotit mají. Symbol zavináče zapsaný (společně s čárkou) před nějakou položku seznamu taktéž vede k vyhodnocení této položky, ale odlišným způsobem – položka (kterou může být například další seznam) se přímo vloží do seznamu uvozeného zpětným apostrofem. Zní to celé složitě? Nejlepší bude, když si způsob použití všech tří symbolů ukážeme na jednoduchých příkladech:

; vytvoříme si dvě proměnné x a y obsahující hodnoty 1 a 2
(setq x 1)
1
(setq y 2)
2

; pokus o vyhodnocení seznamu (x y) musí skončit chybou, protože
; x není jméno žádné funkce ale proměnné obsahující atom
(x y)
*** - EVAL: undefined function X

; použití normálního apostrofu zabraňuje vyhodnocení seznamu
'(x y)
(X Y)

; použití zpětného apostrofu taktéž zabraňuje vyhodnocení seznamu
`(x y)
(X Y)

; zabráníme vyhodnocení celého seznamu, ale naopak si vynutíme vyhodnocení y
`(x ,y)
(X 2)

; zabráníme vyhodnocení celého seznamu, ale naopak si vynutíme vyhodnocení x
`(,x y)
(1 Y)

; seznam jako celek vyhodnocen není (ty by vedlo k chybě - viz výše)
; ale jsou vyhodnoceny proměnné x a y
`(,x ,y)
(1 2)

Použití zavináče je poněkud komplikovanější:

; proměnná z obsahuje seznam se třemi symboly
(setq z '(www root cz))
(WWW ROOT CZ)

; zabráníme vyhodnocení seznamu obsahujícího z (tedy další seznam)
`(1 2 3 z 4 5 6)
(1 2 3 Z 4 5 6)

; seznam jako celek není vyhodnocen, ale proměnná z ano
`(1 2 3 ,z 4 5 6)
(1 2 3 (WWW ROOT CZ) 4 5 6)

; podobné předchozímu, ovšem s tím rozdílem, že je seznam uložený
; v proměnné z "rozpuštěn" (zmizí závorky okolo trojice symbolů
; www root cz)
`(1 2 3 ,@z 4 5 6)
(1 2 3 WWW ROOT CZ 4 5 6)

Nyní si konečně můžeme nějaké jednoduché makro ukázat. Namísto formy defun se při tvorbě maker používá forma defmacro:

(defmacro Square (x)
  `(* ,x ,x))

Toto makro funguje následujícím způsobem: při prvotním načítání LISPovských výrazů (forem) se jakýkoli výskyt (Square cokoli) nahradí formou (* cokoli cokoli). Teprve tato forma je předána interpretru nebo překladači pro další zpracování, například přímé vyhodnocení. Když je LISPovský program překládán, tak se přeloží až výsledek aplikace makra, což je opět shodné se způsobem překladu céčkového programu.

Makro si můžeme ihned vyzkoušet:

(Square 42)
1764

(Square (+ 1 2))
9

5. Výpis expandovaného makra

Při tvorbě maker se může stát, že makro kvůli nějaké chybě neprovádí přesně tu činnost, jakou programátor zamýšlel. Zatímco funkce jsou volány až v době běhu programu, tj. je možné do jejich těla vkládat různé ladicí příkazy (výpis hodnot, logování, aserce) či dokonce běh programu trasovat, u maker to není možné, protože jsou expandována již při překladu programu. Ovšem v Common Lispu je možné si pomocí zabudované funkce macroexpand nebo macroexpand-1 zobrazit výpis makra po expanzi, což může být velmi užitečné. Zatímco funkce macroexpand zobrazí plně expandované makro (tj. výsledný LISPovský kód po expanzi všech maker, i těch vnořených), je po zavolání makra macroexpand-1 zobrazeno makro pouze po první expanzi, což znamená, že uvnitř expandovaného kódu se může vyskytovat i volání dalších maker. V praxi se při ladění maker častěji používá právě funkce macroexpand-1, jejíž použití je velmi jednoduché:

; nejprve znovu vytvoříme pomocnou funkci Square
(defmacro Square (x)
  `(* ,x ,x)
)

; expanze makra při volání funkce Square s parametrem jenž je atomem
(macroexpand-1 '(Square 42))
(* 42 42) ;

; expanze makra při volání funkce Square s parametrem jenž je formou
(macroexpand-1 '(Square (+ 1 2)))
(* (+ 1 2) (+ 1 2)) ;

; makro se expanduje i v případě, že se použije neznámý symbol "plus"
(macroexpand-1 '(Square (plus 1 2)))
(* (PLUS 1 2) (PLUS 1 2)) ;

Až při pohledu na expandované makro nás může napadnout, že vlastně nepracuje dokonale, v některých případech dokonce pracuje chybně. Problém spočívá v tom, že se předaný parametr po expanzi makra vyhodnocuje dvakrát, což samozřejmě není větší problém v případě, že se předává atomická hodnota (číslo) nebo jednoduchý výraz, ovšem kdyby se jednalo například o funkci načítající hodnotu z databáze nebo ze souboru (popř. ze standardního vstupu), bylo by toto načítání prováděno dvakrát a ne jedenkrát, jak by každý programátor při pohledu na program volající makro očekával. Můžeme si to ostatně vyzkoušet (funkce read provádí načtení výrazu ze standardního vstupu):

(Square (read))
2 ; zadáno uživatelem z klávesnice
3 ; zadáno (druhá a jiná! hodnota) taktéž z klávesnice
6 ; výsledek volání makra = 2*3

Makro lze „opravit“ například tak, že se použije pomocná lokální proměnná temp:

(defmacro Square2 (x)
    `(let ((temp ,x)) (* temp temp))
)

; podíváme se na expanzi při jeho volání
; s parametrem (+ 1 2)
(macroexpand-1 '(Square2 (+ 1 2)))
(LET ((TEMP (+ 1 2))) (* TEMP TEMP)) ;
; vidíme, že se výraz (+ 1 2) vyhodnocuje pouze jedenkrát

; otestujeme volání makra při předání funkce read
(Square2 (read))
2 ; zadáno uživatelem z klávesnice
4 ; správný výsledek a navíc program vyžadoval pouze jediný vstup z klávesnice

Pomocí macroexpand-1 je možné prozkoumat i makra dostupná v základní knihovně jazyka:

; makra or a and jsou implementovány tak, aby podporovaly
; zkrácené vyhodnocení logických výrazů
(macroexpand-1 '(or foo bar))
(COND (FOO) (T BAR)) ;

(macroexpand-1 '(and (foo t) (foo nil)))
(COND ((NOT (FOO T)) NIL) (T (FOO NIL))) ;

6. Příklady použití knihovního makra „loop“: operace nad seznamy

Jedním z nejužitečnějších maker, které se nachází v knihovně Common Lispu, je makro nazvané prozaicky loop, jenž je doplněné o několik dalších pomocných maker a symbolů (ty jsou použity pro doplnění syntaxe o další „klíčová slova“). Pomocí makra loop lze v LISPu (tj. jazyku založeném částečně na funkcionálním paradigmatu, který původně vedl uživatele k používání rekurze namísto psaní programových smyček) realizovat značné množství různých typů programových smyček, například smyčky počítané (s možností změny kroku, o který se změní hodnota čítače či čítačů smyček při každé iteraci), smyčky s podmínkou (odpovídá například pascalovským smyčkám typu while-do a repeat-until) či iterační smyčky, která v každé iteraci operuje nad prvky seznamů, polí či asociativních polí (for-each). Na příkladu makra loop je pěkně a názorně ukázána jedna z největších výhod LISPovských maker – právě pomocí maker a některých dalších vlastností LISPu je možné vytvořit zcela nový jazyk s vlastní syntaxí. Na následujících demonstračních příkladech si ukážeme některé možnosti, které makro loop programátorům nabízí:

Smyčka, která postupně iteruje nad všemi elementy uloženými v seznamu (tj. postupně všemi prvky prochází):

(loop for i in '(a b c d) do (print i))

A
B
C
D

Poznámka: samotné makro loop vrací jako svoji návratovou hodnotu (většinou) atom NIL, který ve výpisech pro větší přehlednost neuvádím. Pokud si příklady budete sami spouštět v interpretru Common Lispu, bude po skončení smyčky na standardní výstup navíc vypsán řádek obsahující právě NIL.

Pokud se ve zpracovávaném seznamu nachází další rekurzivně vnořené seznamy, jsou při iterování seznamem chápány jako jeden prvek:

(loop for i in '(a (b c) d) do (print i))

A
(B C)
D

Smyčka, která postupně iteruje (prochází) přes CDR zvoleného seznamu. V první iteraci je do proměnné i přiřazen celý seznam s, ve druhé iteraci (cdr s), ve třetí iteraci (cdr (cdr s)) atd.:

(loop for i on '(a b c d) do (print i))

(A B C D)
(A B C)
(B C)
(C)

Zpracování seznamu obsahujícího ve druhém prvku podseznam:

(loop for i on '(a (b c) d) do (print i))

(A (B C) D)
((B C) D)
(D)

Iterace nad dvojicí seznamů a postupná konstrukce seznamu obsahujícího dvojice prvků ze seznamu prvního a druhého. Výsledek není v tomto případě tisknut, ale vrácen jako návratová hodnota smyčky, tj. lze ho například přiřadit proměnné:

(loop for x in '(a b c d e)
      for y in '(1 2 3 4 5)
      collect (list x y)
)

((A 1) (B 2) (C 3) (D 4) (E 5))

Přiřazení výsledného seznamu vytvořeného smyčkou do proměnné:

(setq a (loop for x in '(a b c d e)
              for y in '(1 2 3 4 5)
              collect (list x y)
        )
)
((A 1) (B 2) (C 3) (D 4) (E 5))

; tisk hodnoty proměnné a
a
((A 1) (B 2) (C 3) (D 4) (E 5))

7. Příklady použití knihovního makra „loop“: počítané smyčky

V předchozím textu jsme si řekli, že makro loop je možné použít mj. i pro tvorbu počítaných smyček, tj. smyček, které v každé iteraci zvyšují nebo naopak snižují hodnotu čítače (lokální proměnné platné v rámci smyčky). Syntaxe, kterou makro loop pro tento typ smyček používá, je v mnoha ohledech podobná syntaxi Pascalu či některých verzí Basicu, jak se ostatně můžete sami přesvědčit na následujících demonstračních příkladech:

Základní tvar počítané smyčky se zadáním horní a dolní meze čítače. Hodnota čítače se v tomto případě v každé iteraci zvětšuje o jedničku, jak je to ostatně u počítaných smyček běžné:

(loop for i from 1 to 10 do (print i))

1
2
3
4
5
6
7
8
9
10

Počítaná smyčka s čítačem, jehož hodnota se v každé iteraci zmenšuje. Povšimněte si použití slova downto, které se vyskytuje například i v Pascalu:

(loop for i from 10 downto 1 do (print i))

10
9
8
7
6
5
4
3
2
1

U počítaných smyček lze měnit krok, tj. hodnotu, o kterou se čítač smyčky v každé iteraci zvětší nebo naopak zmenší:

(loop for i from 1 to 10 by 1.5 do (print i))

1
2.5
4.0
5.5
7.0
8.5
10.0

V mnoha implementacích programovacího jazyka LISP je podporován i numerický datový typ „zlomek“, což je racionální číslo vyjádřené čitatelem a jmenovatelem odděleným znakem / (lomítko). V počítaných smyčkách lze samozřejmě zlomky využívat, jak je to patrné z následujících dvou příkladů:

(loop for i from 0 to 10 by 3/2 do (print i))

0
3/2
3
9/2
6
15/2
9

(loop for i from 10 downto 0 by 4/3 do (print i))

10
26/3
22/3
6
14/3
10/3
2
2/3

Hodnoty čítače lze omezit prakticky libovolnou podmínkou. V následujícím příkladu je použit predikát evenp, který vrací hodnotu T (pravda) v tom případě, kdy je parametr tohoto predikátu sudé číslo:

(loop for i from 1 to 10 when (evenp i) do (print i))

2
4
6
8
10

Hodnoty, kterých postupně nabývá čítač smyčky, lze mít uloženy v seznamu (i když tento příklad je poněkud umělý, protože lze napsat jednodušším způsobem):

(loop with a = '(1 42 3) for i in a do (print i))

1
42
3

Na závěr si ukážeme způsob zápisu smyčky, která současně prochází všemi prvky seznamu a navíc mění hodnotu čítače. Právě tento typ smyčky mnohdy citelně chybí v ostatních programovacích jazycích, které nabízí buď striktně počítanou smyčku nebo smyčku typu for-each:

(loop for x in '(a b c d e)
      for y from 1 do
      (format t "~s = ~s~%" y x)
)
1 = A
2 = B
3 = C
4 = D
5 = E

Poznámka: funkce format se v mnoha ohledech podobá například céčkové funkci printf. Prvním parametrem této funkce je výstupní proud, do kterého se má výsledek tisknout (s tou výjimkou, že nil značí, že se výsledek nikam netiskne, ale je navrácen ve formě řetězce, a T naopak odpovídá standardnímu výstupu), druhým parametrem je formátovací řetězec a další parametry jsou postupně tisknuty na výstup podle pravidel zadaných ve formátovacím řetězci. Ve výše uvedeném příkladu jsou použita dvě formátovací pravidla: ~s = tisk hodnoty, ~% = odřádkování.

8. Literatura

Hillis, D.
„New Computer Architectures and Their Relationship to Physics or Why CS is No Good“
Int J. Theoretical Physics 21 (3/4) 255–262.
Lewis W. Tucker, George G. Robertson,
„Architecture and Applications of the Connection Machine“
Computer, vol. 21, no. 8, pp. 26–38, August, 1988.
Arthur Trew and Greg Wilson (eds.) (1991)
„Past, Present, Parallel: A Survey of Available Parallel Computing Systems“
New York: Springer-Verlag. ISBN 0–387–19664–1.
W. Daniel Hillis and Lewis W. Tucker
„The CM-5 Connection Machine: A Scalable Supercomputer“
In Communications of the ACM, Vol. 36, No. 11 (November 1993)
Cliff Lasser, Jeff Mincy, J.P. Massar
„The Essential *LISP Manual“
Thinking Machines Corporation, 1986.
Anonymous
„Getting Started in *Lisp, Version 6.1“
Thinking Machines Corporation, Cambridge, Massachusetts, June 1991.
Anonymous
„*Lisp Dictionary“
Thinking Machines Corporation, Cambridge, Massachusetts.
Anonymous
„*Lisp Timesharing User's Guide“
Online at CMU AI Repository
Zdzislaw Meglicki
„The CM5 *Lisp Course“
Centre for Information Science Research, The Australian National University, 1994
McCarthy
„Recursive functions of symbolic expressions and their computation by machine, part I“
1960
Guy L. Steele
„History of Scheme“
2006, Sun Microsystems Laboratories
Kolář J., Muller K.:
„Speciální programovací jazyky“
Praha 1981
„AutoLISP Release 9, Programmer's reference“
Autodesk Ltd., October 1987
„AutoLISP Release 10, Programmer's reference“
Autodesk Ltd., September 1988
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
Carl Hewitt; Peter Bishop and Richard Steiger
„A Universal Modular Actor Formalism for Artificial Intelligence“
1973
Feiman, J.
„The Gartner Programming Language Survey (October 2001)“
Gartner Advisory