Lisp

Lisp
Druh	Funkcionálny
Dátum vzniku	1958
Typová kontrola	dynamická[1]
Tvorca	John McCarthy
Dialekty	Scheme, Racket, CLisp

Lisp je funkcionálny programovací jazyk. Vynašiel ho John McCarthy na MIT v 50. rokoch 20. storočia.^[2][3] LISP je skratka z anglických slov „LISt Processing“ (Spracovávanie zoznamov).^[4] Je druhým najstarším vyšším programovacím jazykom, ktorý sa dodnes používa; starší je iba Fortran.^[2][5]

Na zápis funkcií prevzal λ-notáciu z λ-kalkulu.^[3]

Jeho základným dátovým typom je zoznam (linked list).^[2]

Lisp sa stal obľúbený hlavne v oblasti výskumu umelej inteligencie v 70. a 80. rokoch 20. storočia.^[6]

Richard Stallman ho použil ako skriptovací jazyk pre Emacs; ako štandardný rozširovací jazyk slobodného operačného systému GNU neskôr zvolil dialekt Lispu Scheme, ktorého implementáciou je Guile.^[7][8]

Jeho výrazným rozlišovacím znakom je častý výskyt zátvoriek.^[2] Nasledujúca rekurzívna definícia faktoriálu je napísaná v dialekte Racket.

#lang racket

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

Lisp tiež zapisuje operácie v prefixovom tvare v zátvorkách (operátor stojí pred operandmi), ktorý sa podobá prefixovej notácii Jana Łukasiewicza a nazýva sa aj „Cambridge Polish“; napríklad výraz x + 3y + z sa zapíše ako (PLUS X (TIMES 3 Y) Z).^[3] Programy v Lispe sú zapísané ako zoznamy, teda v rovnakej podobe ako dáta, čo umožňuje pracovať so všetkými funkciami (operátormi) ako s dátami.^[3] Funkcia, ktorá zvýši hodnotu parametra o 1, zapísaná pomocou lambdy:

#lang racket

(define inc (lambda(x) (+ x 1)))

Potrebu algebraického jazyka na spracovanie zoznamov pre prácu v oblasti umelej inteligencie na počítači IBM 704 pocítil John McCarthy v lete 1956 počas Dartmouthského letného výskumného projektu o umelej inteligencii.^[3] Na jeseň 1958 sa stal odborným asistentom na Massachusetts Institute of Technology, kde spolu s Marvinom Minským založil projekt umelej inteligencie; v tom istom čase sa začala implementácia Lispu.^[3] Pri zápise funkcií použil McCarthy λ-notáciu Alonza Churcha.^[3]

Programy sa pôvodne mali zapisovať v neformálnej notácii M-výrazov, ktorá sa podobala Fortranu; keď však vznikol interpreter, presadil sa zápis programov priamo ako zoznamov (tzv. S-výrazov) a M-notácia nebola nikdy úplne definovaná.^[3] Interpreter vznikol tak, že Steve Russell si všimol, že funkcia eval môže slúžiť ako interpreter Lispu, a ručne ju naprogramoval.^[3] Základná operácia car dostala názov podľa výrazu Contents of the Address part of Register number na počítači IBM 704; analogicky vznikla operácia cdr pre dekrementovú časť slova.^[3] Na uvoľňovanie nepoužívanej pamäte sa v Lispe od začiatku počítalo so zberom odpadu (garbage collection).^[3]

McCarthy jazyk opísal v článku Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, ktorý vyšiel v apríli 1960 v časopise Communications of the ACM.^[9] Prvý úspešný kompilátor Lispu naprogramovali Timothy Hart a Michael Levin; bol napísaný v Lispe a pokladal sa za prvý kompilátor napísaný v jazyku, ktorý prekladá.^[3] Makrá do Lispu zrejme zaviedol Timothy P. Hart v roku 1963.^[6]

V rokoch 1960 – 1965 bol hlavným dialektom Lisp 1.5; koncom 60. rokov sa rozdelil na dva hlavné dialekty, Interlisp (pôvodne BBN Lisp) a MacLisp.^[4] Polslovné a zásobníkové inštrukcie počítačov PDP-6 a PDP-10 firmy Digital Equipment Corporation boli navrhnuté s ohľadom na potreby Lispu a tieto počítače sa stali hlavnými strojmi pre výskum umelej inteligencie.^[3] V druhej polovici 70. rokov navrhli Gerald J. Sussman a Guy L. Steele Jr. dialekt Scheme, ktorý do Lispu priniesol okrem iného lexikálny rozsah platnosti premenných a uzávery.^[10]

V apríli 1981 sa spoločnosť Symbolics a projekty SPICE, NIL a S-1 Lisp spojili pri definovaní jazyka Common Lisp.^[10] V roku 1986 vznikla pracovná skupina X3J13, ktorá z neho vytvorila formálnu normu ANSI X3.226-1994.^[11] Od konca 70. do polovice 80. rokov bola umelá inteligencia dôležitou súčasťou počítačového priemyslu; keď okolo roku 1988 nastal útlm (tzv. „AI winter“), dostali sa do finančných ťažkostí aj firmy zamerané na Lisp.^[6]

• Common Lisp – dialekt štandardizovaný normou ANSI X3.226-1994; jeho hlavnými vzormi boli Lisp Machine Lisp, MacLisp, NIL, S-1 Lisp, Spice Lisp a Scheme.^[11][10]
• Scheme – jednoduchý dialekt Lispu^[10], štandardizovaný aj normou IEEE 1178-1990.^[12]
• Clojure – dialekt Lispu nezaťažený spätnou kompatibilitou, ktorý stavia na platforme Java Virtual Machine a predvolene používa nemenné dátové štruktúry.^[13]
• Emacs Lisp – dialekt, ktorého interpreter je jadrom textového editora GNU Emacs; väčšina editora je napísaná práve v ňom.^[14][15]
• Guile – implementácia Scheme a oficiálny rozširovací jazyk projektu GNU.^[8]

Základným zápisom v Lispe je zoznam: jeho prvky sa píšu za sebou, oddelené medzerami, a celý zoznam sa uzatvára do okrúhlych zátvoriek. Napríklad (a b c) je zoznam troch symbolov a, b a c; zápis () je prázdny zoznam.^[16]

Aj príkazy sa zapisujú ako zoznam. Ak je prvým prvkom symbol, je to názov operátora (funkcie, makra alebo špeciálneho operátora) a ostatné prvky sú argumenty; pri volaní funkcie sa argumenty vyhodnocujú zľava doprava.^[17][18] Napríklad sčítanie zabezpečuje funkcia +, ktorá vráti súčet svojich argumentov:^[19]

(+ 1 2 3)   ; vráti 6

Špeciálny operátor quote vráti svoj argument bez vyhodnotenia; skrátene sa zapisuje apostrofom, napríklad '(1 2 3). Vďaka nemu môžu symboly a zoznamy, ktoré inak predstavujú časti programu, slúžiť ako dáta.^[20]

(quote (1 (+ 2 3 4) 5))   ; vráti (1 (+ 2 3 4) 5)
(list 1 (+ 2 3 4) 5)      ; vráti (1 9 5)

Funkcie sa v Common Lispe definujú makrom defun, ktoré v globálnom prostredí zavedie novú funkciu s daným názvom.^[21] Program „Hello, World!“ ako funkcia a jej zavolanie:

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

Rekurzívna funkcia fact vypočíta faktoriál zadaného čísla; volanie (fact 6) vráti 720:

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

Makro sa v Common Lispe definuje pomocou defmacro.^[22] Ak je prvým prvkom vyhodnocovaného zoznamu názov makra, makro dostane celý tento výraz a výsledok jeho rozvinutia (makroexpanzie) sa použije namiesto pôvodného výrazu.^[23] Na zostavovanie kódu v makrách slúži spätný apostrof (`, backquote): vytvára šablónu dátovej štruktúry, v ktorej sa výraz za čiarkou (,) vyhodnotí a jeho hodnota sa vloží na dané miesto.^[24]

`(1 2 ,(+ 3 4))   ; vráti (1 2 7)

Vlastnú podmienku if treba definovať ako makro, pretože funkcia by pred zavolaním vyhodnotila všetky svoje argumenty, a teda obe vetvy podmienky.^[18]

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

• Commons ponúka multimediálne súbory na tému Lisp
• Wikislovník ponúka heslo Lisp

• Practical Common Lisp – kniha Petra Seibela (po anglicky)
• Common Lisp HyperSpec (po anglicky)
• Jemný úvod do LISPu (Root.cz, po česky)

Tento článok je čiastočný alebo úplný preklad článkov Lisp (programming language) na anglickej Wikipédii a Lisp na českej Wikipédii.