Lisp III: Funkce, vyhodnocování funkcí

…aneb funkcionálně programuje i strejda Google!
30. 07. 2008

Minule jsme probrali základní syntaxi Lispu a už víme, že se Lispový kód skládá převážně ze seznamů, které obsahují nějaké další výrazy. Také víme, že výraz může mít dvě vazby – hodnotu a funkci. V tomto díle se zaměříme právě na ty funkce.

Anonymní funkce

Jednoduchou funkci můžeme vytvořit pomocí makra lambda. Proč je lambda makro se dovíte později. Syntaxe je vcelku jednoduchá: (lambda (args) tělo-funkce). Argumenty funkce dáváme do seznamu, tělo v seznamu být nemusí, pokud to není žádané (tj. pokud se má vrátit pouze symbol nebo číslo). Argumenty se vyhodnotí při volání funkce. Pokud tedy zavoláme nějakou funcki (fun (+ 5 2)), funkci fun bude předána sedmička. Teď si musíme trochu osvěžit funkcionálního ducha. Protože je tento seriál o funkcionálním programování v Lispu, musíte si uvědomit, co ta funkce bude dělat. Nesmíte používat vedlejší efekt (pak by to nebylo funkcionální), takže jediné co můžete udělat je, že vemete nějaké argumenty, cosi s nimi provedete a vrátíte nějakou hodnotu. Naše funkce tedy budou vždy takto konstruované. Nebudou nic měnit, budou pouze vracet hodnoty.

Řekli jsme si, že funkce můžeme vytvořit pomocí lambdy. Pojďme teď na to – funkce vracející dvojnásobek předané hodnoty:

(lambda (x)
  (* 2 x))

Tento seznam se vyhodnotí na funkci. Konkrétně na anonymní funkci – ano, to je to, nad čím teď jásají PHPkáři :-). Tato anonymní funkce byla sice moc hezká, ale jaksi jsme ji zapomněli použít. Abyste rozuměli – když ten předešlý kód strčíte do posluchače, on vyhodnotí seznam a vrátí vám funkci. Jenže ta funkce není na nic navázaná, takže ji nemůžete nijak použít a je vám takhle sama o sobě na nic. To lze jednoduše spravit a bystří čtenáři ví jak. Minule jsme si řekli, že na prvním místě seznamu musí být funkce. Takže když náš lambda výraz dáme na první místo seznamu a za něj vložíme argument funkce, mělo by to fungovat. zkusíme:

((lambda (x)
  (* 2 x)) 10)

Funguje, že jo? Lisp by měl vrátit dvacítku. Co se tedy všechno stalo? Z našeho lambda výrazu se po vyhodnocení stala funkce – můžete si to obrazně představit, jako by se to přepsalo na (funkce 10). Lisp dále pokračoval ve vyhodnocování tohoto seznamu a protože se funkce nacházela na prvním místě seznamu, spustil ji (aplikoval na ni desítku). Desítka proběhla automatem a ten z ní udělal dvacítku.

Teď už vám můžu taky prozdradit, proč je lambda makro a ne standardní (vestavěná) funkce. Je to vcelku jednoduché – podívejte se znova na ten lambda výraz. Říkali jsme si, že v Lispu by měla být na začátku seznamu funkce, jinak systém neví s tím a vyhodí chybu. Proč tedy Lisp nevyhodil chybu na seznam (x) v lambda výrazu? Měl by, na x přece žádnou funkci navázanou nemáme. A přesně proto je lambda makro – aby se dělo to, co se má dít a ne aby nám to vyhazovalo standardní chyby; makra tedy mají odlišný způsob zpracování.

Vazby na funkce

OK, už tedy umíme vytvořit funkci, umíme ji aplikovat, ale neumíme ji uložit. K tomu se používá makro defun. Je to makro ze stejného důvodu, jako u lambdy. Makro defun má následující syntax: (defun název (args) tělo-funkce). Makro defun definuje novou uživatelskou funkci a ukládá vazbu do globálního prostředí. O prostředích bude řeč ke konci, prozatím není třeba se jimi znepokojovat. Vytvořenou funkci zavoláme takto: (název arg1 arg2 ...). Předchozí funkci si teď přepíšeme a uložíme:

(defun 2x (x)
  (* x 2))

Na symbol 2x máme nyní navázanou funkci, která nám zdvojnásobí předaný argument. Po zkompilování (v LispWorks je to jedno z těch žlutých tlačítek nad editorem) můžeme v posluchači tuto funkci používat:

> (2x 10)
20

> (2x -50)
-100

 > 2x
Error: The variable |2X| is unbound.

Poslední volání byla jen ukázka toho, že smybol má opravdu dvě vazby – do funkční jsme sice funkci umístili, ale jinak symbol 2x žádnou hodnotu nemá, proto když se ji snažíme použít jako hodnotu, dojde k chybě.

Cvičně si napíšeme funkci pro výpočet determinantu:

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

Funkci pro výpočet kořenů kvadratické rovnice ještě napsat nedokážeme, protože neumíme vracet více než jeden výsledek. I to se časem změní. Můžeme ale zkusit něco jiného: nejprve si napíšeme funkci pro druhou mocninu a tu poté aplikujeme ve funkci pro výpočet determinantu:

(defun na2 (x)
  (* x x))

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

Proč je tento druhý postup lepší? Má to v zásadě dvě výhody – kód bývá přehlednější. Čím více smysluplných částí kódu rozdělíte do samostatných funkcí, tím se vám v tom bude lépe orientovat. Když to správně rozdělíte, můžete kód číst jako pohádku :-). Například část (* 4 a c) smysluplná jako samostatná část moc není, takže přepisovat to do vlastní funkce význam nemá. Druhý důvod je, že nikdy nevíte, kdy tu funkci budete znova potřebovat. A jak známo – programátor nikdy nepíše stejnou část kódu dvakrát :-). I z toho důvodu se nevyplatí přepisovat (* 4 a c) – není pravděpodobné, že byste takovou funkci potřebovali jinde než ve výpočtu determinantu.

Prostředí

Docela klíčový pojem. Naštěstí je poměrně intuitivní. V Lispu pracujeme v různých prostředích. Primárně máme globální prostředí, to si můžeme představit jako jakýsi root. V tomto globálním prostředí se odehrává velká část kódu. Každý symbol může mít v různém prostředí jinou vazbu. Například symbol sym může mít v globálním prostředí hodnotu dvacet a v jiném prostředí hodnotu třicet. Na tom není nic zvláštního.

Všechny funkce vytvořené pomocí marka defun mají nastavenou vazbu v globálním prostředí. Jak se vytváří další prostředí? Většinou pomocí nějakých speciálních forem, ale stačí nám k tomu bohatě makro lambda. Pokud vytvoříte anonymní funkci pomocí lambdy, tak při vytvoření funkce dojde zároveň k vytvoření nového prostředí. V tomto prostředí mohou mít symboly jinou vazbu než stejné symboly v globálním prostředí. Zároveň se nastavuje vazba na prostředí předka. Klíčové je, kdo je ten předek. V Lispu existuje lexikální rozsah platnosti, takže platí, že předek je vždy prostředí vzniku dané funkce. Pokud funkce vznikla v globálním prostředí, má za předka globální prostředí. Pokud funkce vznikla například v jiné funkci, má za předka tuto funkci. Pozor! Neplést vznik funkce s aplikací funkce. Pokud se nacházíme v jednom prostředí a chceme znát hodnotu nějakého symbolu, jako vždy se první musíme podívat do téhož prostředí. Pokud v tomto prostředí vazbu nenajdeme, jdeme zpět za předkem. Pokud není ani v předkovi, jdeme dále, dokud nedojdeme do globálního prostředí. Pokud ani zde není žádná vazba, vyhodíme chybu. Ilustrační příklady:

(defvar a 10)

(defun x+a+10 (x)
  (+ 10 a x))

(defun a*b+a+10 (a b)
  (x+a+10 (* a b)))

Nejprve deklarujeme globální proměnnou a a nastavíme ji jako hodnotu desítku. Symbol a má tedy v globáním prostředí hodnotu deset. Poté vytvoříme funkci x+a+10, která bere jeden argument, ke kterému přičte desítku a symbol a. Poslední funkce bere dva argumenty, ty vynásobí a předá je předchozí funkci. Hmm, dosti nesmyslné funkce :-). Ale přichází otázka: Když v těle druhé funkce zavoláme funkci x+a+10, jakou hodnotu bude mít symbol a v těle první funkce? (V části (+ 10 a x)) Bude mít hodnotu argumentu a nebo bude mít hodnotu globální proměnné a?

No, je to jednoduché. Funkce vznikla v globálním prostředí, funkce x+a+10 nevidí do těla funkce a*b+a+10, která má své vlastní prostředí, takže hledá vazbu v globálním prostředí. Tam najde desítku. Další příklad:

(defun prostredi (a b c)
  ((lambda (a b)
     (+ a b c)) (* a 2) b))

; Jak se vyhodnotí následující výraz?
> (prostredi 1 2 3)

V těle funkce prostredi jsme vytvořili další, tentokrát anonymní, funkci, která si ovšem také vytváří vlastní prostředí. Symboly a a b tedy budou rovny předaným argumentům anonymní funkce. Zato symbol c nemá v prostředí anonymní funkce žádnou vazbu, takže se jde o úroveň výš. Předchozí prostředí je prostředí funkce prostredi, kde se již symbol c nachází a má hodnotu 3. Takže jak to celé bude vypadat? V těle funkce prostredi vznikne nová anonymní funkce, kterou okamžitě aplikujeme. Jako argumenty jí předáme dvojnásobek původního argumentu a a původní argument b. V těle anonymní funkce pak všechno sečteme (vychází tam tento výpočet: (+ 2 2 3)) a výsledek je sedm.

Jak probíhá vyhodnocování

Ještě trošku detailněji k systému vyhodnocování. Pokud zavoláte nějakou funkci, dojde v vyhodnocení seznamu. Lisp zjistí, jestli mají všechny symboly seznamu (tj. funkce a její argumenty) vazby. Pokud nemají, Lisp vrátí chybu. Pokud mají, Lisp je vyhodnotí. Do těla funkce už tak jdou pouze hodnoty. Ty se vždy ukládají do hodnotového chlívku.

Poté dojde k zavolání funkce, vytvoří se nějaká nová prostředí a začne se vyhodnocovat tělo funkce. Funkce jako taková vždy vrátí poslední vyhodnocený seznam. Je logické, že funkce nemůže vrátit dva výsledky, takže vždy vrátí výsledek posledního seznamu, předchozí výsledky zahazuje. Z tohoto principu je jasné, že pokud se chceme držet funkcionálního paradigma, budou mít naše funkce v těle vždy jen jeden seznam. Pokud by jich měly víc, tak by to buď nemělo smysl:

(defun nesmysl(a)
  (+ a 5)
  (* a 10)
  (- a 1))

> (nesmysl 10)
9

(V těle funkce proběhly dvě operace sčítání a násobení, ale jejich výsledek nic neovlivnil.) Nebo bychom museli použít vedlejší efekt:

(defun vedle(a)
  (format t "~%Predali jste ~s" a)
  (* 2 a))

> (vedle 5)

Predali jste 5
10

(Funkce nejprve vypíše na obrazovku předaný argument a poté vrátí dvojnásobek argumentu.)

Funkce jako argument jiné funkce

Představme si, že chceme napsat funkci, která bude brát jako jeden argument jinou funkci, kterou poté ve svém těle někde a nějak aplikuje. Například takto:

(defun normalize (fun num)
  (fun (abs num)))

Tato funkce bere jako první argument funkci a jako druhý argument číslo. Ve svém tělě pak nejdříve vezme absolutní hodnotu čísla a (funkce abs) a na to teprve aplikuje předanou funkci. Dále si napíšeme vlastní funkci, která vrátí třetí mocninu:

(defun na3 (x)
  (* x x x))

Zkusíme nyní zavolat první funkci normalize s druhou funkcí na3 a číslem –3:

> (normalize na3 -3)
Error: The variable NA3 is unbound.

Kde se stala chyba? Pamatujete si na to, kdy se bere ze symbolu funkce a kdy hodnota? Pokud stojí symbol na prvním místě seznamu, vyhodnotí se na funkci. V opačném případě se vyhodnotí na hodnotu. Symbom na3 má pouze funkční vazbu, nemá navázanou žádnou hodnotu. Proto nám Lisp vyhodil chybu. Jak to opravit? Potřebujeme nějaký prostředek, jak dostat ze symbolu funkci, přestože se nachází na místě, které je obvyklé pro symbol. K tomu slouží funkce function. Volání zapíšeme takto: (normalize (function na3) -3). Tímto jsme zajistili, že hrábneme do funkčního chlívku symbolu na3. Můžeme využívat i zkrácené verze pomocí #': (normalize #'na3 -3). Vyzkoušíme:

> (normalize #'na3 -3)
Error: Undefined function FUN called with arguments (3).

Kde se stala chyba teď? Pokud předáme nějaký argument, tak se vždy v těle funkce uloží jako hodnota. Funkci normalize jsme sice předali jako argument funkci, ale ona se – mrcha – uložila jako hodnota. Takže v těle funkce nemá symbol fun navázanou žádnou funkci, ale má v hodnotovém chlívku navázanou funkci. Jenže to Lisp neví a snaží se vyhodnotit funkční chlívek, který je prázdný. Proto ještě v těle funkce potřebujeme Lispu říci, že má sice brát tento symbol jako funkci, ale že má tu funkci hledat v hodnotové vazbě. K tomu slouží funcall:

(defun normalize (fun num)
  (funcall fun (abs num)))

funcall způsobí přesně to, co chceme. Spustí funkcí, která je uložená v hodnotě. Nyní už vše poběží jak má:

> (normalize #'na3 -3)
27
> (normalize #'na3 8)
512