Lisp

Z Multimediaexpo.cz

Lisp (nebo LISP) je funkcionální programovací jazyk s dlouhou historií. Jeho název je zkratka pro List processing (zpracování seznamů). Stále se používá v oboru umělá inteligence. Používá ho také například textový editor Emacs či konstrukční program AutoCAD.

Lisp byl původně specifikován v roce 1958. V současné době se jedná o druhý nejstarší vysokoúrovňový jazyk, který se stále ještě používá v praxi; starší už je pouze Fortran. Lisp byl původně navrhnut jako programovací jazyk pro matematické výpočty a byl silně ovlivněn syntaxí Lambda kalkulu. Rychle se stal favorizovaným programovacím jazykem ve světě umělé inteligence. Lisp se stal průkopníkem v mnoha programových technikách, například: stromové struktury, automatická správa paměti nebo dynamické typování. Lisp nevnímá rozdíl mezi kódem a daty, díky čemuž má jednoduchou syntaxi. Celý program je tak složen z s-výrazů nebo ozávorkovaných seznamů ve tvaru (f a b c), kde na prvním místě je operátor/funkce a na dalších argumenty funkce. Všechny další funkce jazyka mají identickou syntaxi.

Z Lispu jsou odvozeny i další jazyky - například Tcl, Smalltalk nebo Scheme. Tvůrce jazyka je John McCarthy.

Syntaxe

Základním zápisem v Lispu je seznam. Zapisuje se tímto způsobem:

(1 2 "ahoj" 13.2)

Tento seznam obsahuje čtyři prvky:

• celé číslo 1
• celé číslo 2
• řetězec znaků „ahoj“
• reálné číslo 13,2

Seznam v příkladu reprezentuje uspořádanou čtveřici. Závorky v jazyce Lisp nefungují tak jako v matematice, ale pouze označují začátek a konec seznamu.

Seznamy jsou v Lispu implementovány jako binární strom degenerovaný na jednosměrně vázaný seznam.

Co se seznamem Lisp udělá, záleží na okolnostech.

Příkazy

Příkazy jazyka Lisp se zapisují také jako seznam, jehož první prvek seznamu je název příkazu.

Například sčítání je realizováno příkazem +. Odpovídající konstrukce v jazyce vypadá takto:

(+ 1 2 3)

Interpret odpoví 6.

Ukázka kódu

Program hello world lze zapsat několika způsoby. Nejjednodušší vypadá takto:

(format t "Hello, World!")

Funkce se v Lispu definují pomocí klíčového slova defun:

(defun hello ()
  (format t "~&Hello, World!~%"))
(hello)

Na prvních dvou řádcích je definice funkce hello, na třetím řádku je tato funkce svým jménem zavolána.

Funkcím lze předávat i argumenty. V následujícím příkladu je ukázka funkce fact, která vypočítá faktoriál zadaného čísla:

(defun fact (n)
  (if (zerop n)
    1
    (* n (fact (- n 1)))))

Pro výpočet faktoriálu čísla 6 předáme tuto hodnotu jako argument funkci fact:

(fact 6)

Návratovou hodnotou funkce bude hodnota 720.

Makra

Lisp má jako jeden z mála jazyků propracovaný systém maker, díky kterým lze velmi výrazným způsobem ovlivnit celý jazyk. Makra jsou nejprve načtena v READ části REPLu, následně je provedena makroexpanze (tu provádí preprocesor) a až poté je celý výraz vyhodnocen běžnou EVAL částí. Nemá smysl uvažovat o aplikaci makra, v době vyhodnocení výrazu již žádné makro neexistuje. Makro pouze přepisuje text/kód předtím, než se předhodí k vlastnímu vyhodnocení. Zásadní rozdíl mezi makrem a funkcí pak je, že makro nevyhodnocuje své argumenty při zavolání funkce.

Quote, Unquote, Quasiquote

Abychom mohli makra vůbec používat, musíme mít nějaké nástroje k transformaci kódu. Běžně se používá speciální operátor quote, který vrátí následný výraz tak jak mu ho předáme — žádnou část nevyhodnotí. Jako syntaktický cukr můžeme použít apostrof '.

;; Mohlo by se zdát, že quote není potřebný operátor, když máme list,
;; ale jak je vidět, je mezi nimi zásadní rozdíl — funkce list vyhodnocuje
;; všechny své argumenty, quote nevyhodnotí nic.
> (quote (1 2 3))
(1 2 3)
 
> (list 1 2 3)
(1 2 3)
 
> (quote (1 (+ 2 3 4) 5))
(1 (+ 2 3 4) 5)
 
> (list 1 (+ 2 3 4) 5)
(1 9 5)
 
> (quote (a b c d))
(A B C D)
 
> (list a b c d)
Error: The variable A is unbound.
 
> '(1 2 3)
(1 2 3)

Abychom mohli i kvotované části nechat něco vyhodnotit, musíme mít mechanismus,kterým zrušíme ono kvotování a vrátíme se zpět k vyhodnocování. K tomu slouží speciální operátory unquote a quasiquote. Quasiquote se chová stejně jako quote, akorát s tím rozdílem, že ve svém těle umožňuje použít unquote, který vyhodnotí daný výraz. Syntaktický cukr pro unquote je čárka , a pro quasiquote zpětný apostrof `.

> `(1 2 ,(+ 3 4))
(1 2 7)
 
> `(list 1 2 ,(list 3 4))
(LIST 1 2 (3 4))
 
> `('a 'b ,(list (+ 1 2) (+ 3 4)) c d)
((QUOTE A) (QUOTE B) (3 7) C D)

Základní práce s makry

Makra se vytvářejí pomocí speciálního operátoru defmacro. Nejjednodušší příklad může být definice vlastní podmínky, vlastního ifu. Pomocí makra by to vypadalo následovně:

(defmacro my-if (cond true false)
  `(if ,cond
       ,true
     ,false))

Makro se chová stejně jako běžný if:

> (my-if 1 2 3)
2
 
;; Makro vrátí dvě jedničky, protože jednou se vytiskne 
;; a jednou se vrátí jako výsledek funkce print.
> (my-if 1 (print 1) (print 2))
1 
1
 
> (my-if nil (print 1) (print 2))
2 
2

Při definici „vlastního“ ifu musíme použít makro, protože nevyhodnocuje své argumenty. Kdybychom nadefinovali if jako funkci, nechovalo by se to stejně, protože argumenty už by se vyhodnotili při volání funkce a tím pádem by se vždy vyhodnotili obě větve podmínky.

(defun my-bad-if (cond true false)
  (if cond
      true
    false))
 
;; Příklady volání:
 
;; Zde proběhne vyhodnocení správně
> (my-bad-if 1 2 3)
2
 
;; Při tomto volání se chybně vytiskne jedna šestka
> (my-bad-if 1 (print 5) (print 6))
5 
6 
5

Problémy spojené s makry

Při používání maker si musíme dávat pozor na dva klasické problémy — dvojí vyhodnocení a symbol capture. Představme si if, který v true větvi automaticky vrátí výsledek podmínky a ve false větvi vrátí předaný argument. Ukázka, jak by to mělo fungovat:

; 1 je true, tak vrátí 1
> (if-false 1 2)
1
 
; Výsledný seznam je true, vrátí seznam
> (if-false (member 2 '(1 2 3 4 5)) 'nic)
(2 3 4 5)
 
; nil je false, vrátí symbol nic
> (if-false (member nil '(1 2 3 4 5)) 'nic)
NIC

Naivní implementace by mohla vypadat takto:

(defmacro if-false-1 (cond false)
  `(if ,cond
       ,cond
     ,false))

Toto makro zdánlivě funguje. Ovšem do doby, než na něj pustíme kód s vedlejším efektem:

;; Funguje jak má
> (if-false-1 (member 2 '(1 2 3 4 5)) 'nic)
(2 3 4 5)
 
;; Funguje jak má
> (if-false-1 (member nil '(1 2 3 4 5)) 'nic)
NIC
 
;; Makro incf zvyšuje hodnotu symbolu o jedna.
;; Nefunguje jak má — očekáváme, že volání vrátí dvojku.
> (let ((a 1))
    (if-false-1 (incf a) 'nic))
3

Kód (incf a) se v těle makra vyhodnotil dvakrát, proto nám to vrátí trojku. Kód po makroexpanzi vypadá takto:

(LET ((A 1))
  (IF (INCF A) 
      (INCF A) 
    'NIC))

Řešením je navázet vyhodnocenou podmínku na nějaký symbol:

(defmacro if-false-2 (cond false)
  `(let ((cond-help ,cond))
     (if cond-help
         cond-help
       ,false)))

Teď už se výraz vyhodnotí pouze jednou:

> (let ((a 1))
    (if-false-2 (incf a) 'nic))
2

Externí odkazy

• Jemný úvod do LISPu
• Hubičkova školička o Lispu
• Miniseriál o Lispu
• Common Lisp HyperSpec™ (anglicky)
• ANSI Common Lisp Implementation (anglicky)
• Visual LISP - vývojové prostředky AutoCADu