Lisp (programozási nyelv)

	Lisp
Paradigma	többelvű: funkcionális, procedurális, reflexív, meta programozás
Megjelent	1958
Tervező	John McCarthy
Fejlesztő	Steve Russell, Timothy P. Hart, and Mike Levin
Típusosság	dinamikus típusosság, erősen típusos
Dialektusok	Arc, AutoLISP, Clojure, Common Lisp, Emacs Lisp, ISLISP, Newlisp, Scheme, SKILL
Hatással volt rá	IPL
Befolyásolt nyelvek	CLU, Dylan, Falcon, Forth, Haskell, Io, Ioke, JavaScript, Logo, Lua, Mathematica, MDL, ML, Nu, OPS5, Perl, Python, Qi, Rebol, Racket, Ruby, Smalltalk, Tcl

A Lisp programozási nyelv (helyesebben nyelvcsalád) hosszú történetre tekint vissza. Eredetileg általános célú programnyelvnek tervezték az 50-es évek legvégén, de hamarosan a mesterséges intelligencia kutatás előszeretettel alkalmazott nyelvévé vált, amikor az 50-es, 60-as években ezen terület az első virágkorát élte. Ma a Lisp nyelveket számos területen alkalmazzák,^[1] és közkedvelt a számításelmélet oktatásában is.

A Lisp név az angol „List Processing” (listafeldolgozás) kifejezésre vezethető vissza (maga a lisp szó angolul pöszét, pöszítést jelent). A Lisp nyelvek fő adatstruktúrája ugyanis a láncolt lista. Az alapvető listakezelő műveletek az összes nyelvjárásban megegyeznek. Emellett közös sajátosság a zárójelezett prefix-jelölés, a futásidejű típusosság, a funkcionális programozásra jellemző jegyek (pl. rekurzív függvények, Lambda-kalkulus), és az, hogy a programkód adatként manipulálható, tehát végrehajtható. A változatok többsége értelmezőprogrammal fut, de sok közülük tartalmaz beépített fordítót is.

Tetszőleges Lisp nyelven írt program azonnal felismerhető a jellegzetes szintaktikájáról. A programkód ugyanis egymásba ágyazott listák, azaz zárójelezett, ún. S-kifejezések (S-expression, sexp) sorozata. Ennek a primitív szintaktikának köszönhetően a Lisp nyelveken írt programokhoz nagyon egyszerű elemzőt (parser-t) és kódot generáló (meta-) programokat írni, ugyanakkor emberi szemmel könnyű elveszni a nyitó- és csukózárójelek erdejében. A tömör kifejezőerején kívül a könnyű gépi elemezhetőség volt a másik oka a nyelv népszerűségének a 60-as években, amikor még sokszor monitor nélküli terminálokon vagy lyukkártyával, lyukszalaggal történt a bevitel, jellemzően nagygépes kötegelt végrehajtási (batch) környezetben, és nem mindenhol volt elegendő számítási kapacitás összetett, többmenetes fordító- és értelmezőprogramok futtatásához sem.

Formális specifikációjának első, 1958-ban készített változatával a Lisp a második legöregebb magas szintű programozási nyelv (a Fortran után). A megalkotása óta elmúlt bő 50 évben a nyelv sokat változott és számos nyelvjárással gazdagodott. A ma legelterjedtebb változatai az általános célú Common Lisp és Scheme nyelvek.

Történet

John McCarthy (fent) és Steve Russell

A Lisp (eredetileg az Information Processing Language, azaz Információfeldolgozó nyelv kifejezés rövidítése) volt az első, kifejezetten mesterséges intelligencia-algoritmusok leírására készített nyelv, amelynek alapötletét már 1955–56-ban megalkották, és amelyben már számos, a Lispben alapvető koncepció felbukkant, úgy mint a láncolt listák és a rekurzió.

A Lisp nyelvet John McCarthy alkotta meg 1958-ban a Stanford Egyetemen. Eredményeit 1960-ban publikálta („Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.”). Cikkében rámutatott, hogy pár egyszerű operátor és egy függvények ábrázolására alkalmas primitív szintaktika segítségével teljes értékű, általános programozási nyelv alkotható. A matematikában ez a gondolat Alonzo Church újfajta matematikai logikai rendszere, az 1930-as és 40-es években kidolgozott lambda-kalkulus révén már korábban ismert volt.

Az első Lisp értelmezőt John McCarthy és Steve Russel készítette a Stanford egyetemen, 1963-ban. Először az IBM cég FSQ-32 típusú kezdetleges gépére írták, de a Stanford University már abban az évben új gépeket vásárolt, amihez John McCarthyék azonnal alkalmazkodtak: az első teljes (LISP 1.5) értelmező program szinte egyszerre készült el az akkoriban új PDP-1 és az IBM 7090 típusú számítógépekre. A korai IBM-gépek két alacsony szintű utasítása a nyelv két legfontosabb, listák felbontására használt függvénye lett: car (Contents of Address Register) és cdr (Contents of Decrement Register, olvasd, mint: cooder). A legtöbb ma létező Lisp nyelvjárás még mindig ezt a két operátort használja listák fejének, azaz első elemének, ill. a lista farkának, azaz az összes többi elemének a lekérdezéséhez.

Az egyre növekvő felhasználói tábor igényeinek és a kormányzati támogatásnak is köszönhetően az 1970-es években megszületett a Lisp-gép (Lisp-Machine), azaz a célzottan Lisp programok futtatására készített számítógép, amely már a gépi utasítások szintjén is "Lispül gondolkodik". A két legfontosabb project (több típusfejlesztéssel): 1974-től az MIT AI LAB-on a (DEC) "CONS" Lisp-Machine (MacLisp-változattal), és 1978-tól Stanford University-n a Xerox "Alto" gép (InerLisp-dialektust használt). Mindkét rendszer "mikrokód-programozott" volt, azaz a gépi Lisp utasításokat Mikroprogramozással, a processzor(ok) eredeti mikrokódjának átírásával valósították meg. Ezek sok területen felülmúlták a "klasszikus" gépeket, így az újabb Lisp-gép generációk fejlesztése egészen a '80-as évek végéig tartott. Mára a hulladékgyűjtő algoritmusok, a fordító- és értelmezőprogramok fejlődésének, valamint a memória- és számítási kapacitás robbanásszerű növekedésének következtében a Lisp-gépekhez hasonló dedikált megoldások feleslegessé váltak, de hatásuk a mai napig érezhető (pl. CAD- és egyéb komplex grafikus tervezőrendszerek makró-programozása, ahol a Lisp szinte lingua francává vált, ld.AutoLISP).

Az 1980-as és 90-es években komoly energiát fordítottak a szabványosításra, az egyre jobban eltávolodó nyelvjárások egyesítésére. Ennek, a több tucat Lisp-szakértő által több év alatt elvégzett közös munkának lett az eredménye a Common Lisp, amely magába foglalta a vele kiváltani kívánt dialektusok összes lényeges tulajdonságát, egyúttal követhető kompromisszuma lett a szakértők sokszor ellentmondó álláspontjának. 1994-ben az Amerikai Szabványügyi Hivatal, az ANSI nyilvánosságra hozta a nyelvjárást specifikáló szabványt (ANSI X3.226-1994). Ekkorra azonban a Lisp használata a 70-es évek virágkorához képest már jelentősen visszaszorult. Ez a "pihenő" egészen a 2000-es években új erőre kapott MI megjelenéséig tartottm ám azóta a Lisp – újult erővel és tucatnyi új változattal (Gauche, Arc, Chicken, Gambit stb.) – ismét növekvő népszerűséggel része a programozók kelléktárának.

A Lisp kifejező erejének és rugalmasságának köszönhetően gyorsan népszerűvé vált, de már nem csak a mesterséges intelligencia kutatói közösségek körében. A '60-as évek második felétől egyetemi területen gyorsan elterjedt más, a Lisp nyelvi eszközeivel és interaktív környezetével könnyen megfogalmazható feladatok megvalósításánál is (pl. adatbázis lekérdezés, tételbizonyítás, parserek és interpreterek, természetes nyelvek feldolgozása stb.).

Számos előnye mellett a Lispnek természetesen megvannak az árnyoldalai is: szintaxisa a kezdők számára a sok zárójel miatt nehezen átlátható; a bonyolult makrók segítségével megírt komplex függvényeket (ld. a "program-író programot író program"-ot..) néha még egy hozzáértőnek sem könnyű követnie, értelmeznie; nagy programok írásánál a hagyományos nyelvek fentről-lefelé programozási módszerével szemben a Lisp a lentről-felfelé irányú szemantikai felépítéshez illeszkedik, ami az egyéb nyelvekhez szokott programozóknak nagyon szokatlan; valamint a programok jelentős mennyiségű, részeredményként szolgáló adatot gyártanak, amelyek foglalják a memóriát. Ezen utóbbi még komoly problémát jelentett a 70-es évek memóriában és számítási kapacitásban szűkölködő számítógépeinek. Az elterjedt megoldás azonban elég hatékony: egy szemétgyűjtő (garbage collector) segítségével a rendszer bizonyos időközönként "rendet rak" (az ilyen, rövid időre lefoglalt memóriaterületeket a Lisp rendszeresen felszabadítja – azóta más nyelvek, pl. a Java is ezt teszi).

A számítógép-programozásban ma alapvető és teljesen általános esetszétválasztásos (ha … akkor …, egyébként …) vezérlési szerkezetet McCarthy vezette be a Lispben, amelyet aztán az ALGOL átvett és népszerűsített.

Ugyancsak "Lisp-találmány" a magyarra még le nem fordított "continuation" programozási megoldás, ahol is egyfajta késleltetett kiértékelés történik (a függvények a "végrehajtó kódot" (kifejezést) is paraméterként (argumentum)ként kapják, majd azt a megfelelő pillanatban "futtatják" (kiértékelik) – azaz a számításokat csak akkor fejti ki a rendszer, amikor azok eredményére szükség van)

A Lisp nyelv kapcsán lett először konferencia-szintű téma a dinamikus kontra statikus változók kérdése, ahol az idő a Common Lisp-et igazolta: immár egyre több újabb nyelv is a változók statikus (lexikális) tárolását/előhívását részesíti előnyben.

Szintén a Lisp az első megjelenése a modern funkcionális nyelvek egyik legfontosabb eszközének, a farok-rekurziónak, de számos más, az imperatív nyelvekben is használt fontos eszköz is a Lisp-megvalósítását követően terjedtek el pl. az interaktív programozási környezet, az elöl/hátul/a blokkban feltételt vizsgáló ciklusok, az adatok és eljárások bezárásának fogalma, a mintaillesztés is végző makrók, a függvényeket értékül adó-kapó függvények, a hulladékgyűjtő algoritmus, a fordítás programozó általi befolyásolása, optimalizálás és még számos egyéb programozási, rendszertechnikai és felhasználói lehetőség.

Szintaxis

A Lisp kifejezésorientált nyelv. Ez annyit tesz, hogy a legtöbb nyelvvel ellentétben a Lispben nincs különbség „kifejezések” és „parancsok” között, minden adatot és utasítást kifejezések formájában írunk le. Amikor az értelmező kiértékel egy kifejezést, eredményként egy értéket (vagy értékek listáját) kapunk, amely aztán beágyazható újabb kifejezésekbe, vagy akár kifejezésként maga is kiértékelhető.

McCarthy 1958-as cikke két kifejezéstípust különböztetett meg: Az S-kifejezéseket (S-expression, sexp), vagyis szimbolikus kifejezéseket, és az M-kifejezéseket, vagyis meta kifejezéseket, amelyek S-kifejezéseket alakítanak át újabb S-kifejezésekké. Ez utóbbi típus azonban nem talált támogatókra, és a legtöbb mai Lisp változat S-kifejezéseket használ mind az adatok, mind a kód manipulálásához.

Sokan kritizálták a zárójelek túltengését az S-kifejezésekben (ezt tükrözi a Lisp mozaikszó ironikus kifejtése, a „Lots of Irritating Superfluous Parentheses”, azaz „rengeteg irritáló és felesleges zárójel” is), de az igazság az, hogy az egyszerű, rendkívül szabályos szintaktika adja a Lisp legfőbb erejét: a lehetőséget, hogy a kódot adatként kezeljük. A legtöbb Lisp-rendszerhez használható szövegszerkesztő ráadásul a helyes és átlátható zárójelezés érdekében számozza vagy azonos színekkel jeleníti meg az egyes szintekhez tartozó nyitó- és zárójeleket.

Az, hogy mindent S-kifejezésekkel írunk le, nagy rugalmasságot biztosít a nyelvnek. Mivel a Lispben magukat a függvényeket is listákként definiáljuk, akként is tudjuk kezelni őket, és nem okoz technikai nehézséget programot generáló programok írása (ezt hívjuk metaprogramozásnak). Számos Lisp nyelvjárás ki is aknázza ezt a tulajdonságot, és lehetővé teszi makrók készítését, amelyek némi jóindulattal függvényeket generáló, paraméterezhető függvények.

A Lisp-ben egy listát zárójelekkel határolunk, az elemeket szóközzel választjuk el egymástól:

(1 2 "izé")

Ezen lista elemei az 1, 2, és az "izé" értékek. Az értékek típusa implicite adott (azaz nem kell – nem is lehet – külön megadni a típusukat): az első kettő egész, a harmadik pedig szöveges (ún. karakterlánc, string). Az üres listát a () kódsorozattal vagy a nil kulcsszóval írhatjuk le.

A kifejezéseket szintén lista alakban írjuk, mégpedig prefix jelölést használva. A lista legelső eleme egy művelet (angolul form), azaz egy függvény, operátor, makró stb. neve. A lista további elemei adják a művelet argumentumait. A list függvény például visszaadja az argumentumaiból alkotott listát, tehát a

(list 1 2 "izé")

kifejezés az (1 2 "izé") értékké egyszerűsödik. Függvény- vagy operátor-művelet esetén az argumentumok a művelet elvégzése előtt rekurzíve kiértékelődnek, értékük behelyettesítődik az eredeti kifejezésbe, amely csak ezután értékelődik ki, például a

(list 1 2 (list 3 4))

kifejezés értéke (1 2 (3 4)). Az elemi, tovább már nem egyszerűsíthető értékek, mint az 1, 2, és az "izé" (Lisp-terminológiában "atomok") mindig önmagukat adják eredményül. Vegyük észre, hogy a lista harmadik eleme egy másik lista, a listák tehát egymásba ágyazhatóak.

A számtani műveletek hasonlóan működnek (itt szokatlan lehet a prefix jelölés):

(  1 2 3 4)

értéke 10.

Bizonyos rendhagyó műveletek (special form-ok) vezérlési szerkezetként szolgálnak. Az if művelet például három argumentumot vár. Ha az első argumentum nem az üres listát (azaz nem a nil értéket) adja eredményül, akkor a második, ellenkező esetben a harmadik argumentumát értékeli ki (klasszikus ha-akkor-egyébként típusú elágazó utasítás). Így tehát a

(if nil
  (list 1 2 "izé")
  (list 3 4 "bigyó"))

eredménye (3 4 "bigyó") . A NIL a logikai nem értéket jelöli a Lispben, az igaz értéket a T jelöli (a kis- és nagybetűk felcserélhetőek, azaz a legtöbb Lisp nem Case-szenzitív).

Vegyük észre, hogy itt az argumentumok nem értékelődnek ki a művelet elvégzése előtt (mivel nem függvényhívásról vagy operátor alkalmazásáról van szó), csak egyikük a feltétel vizsgálatát követő döntés után. Jelen esetben az sem okozna tehát gondot, ha az akkor ágon hibát okozó kifejezés állna.

Egy másik rendhagyó művelet, a defun, függvények definiálására szolgál. Argumentumai rendre a definiálni kívánt függvény neve, a névleges argumentumainak listája, valamint a függvény törzsét alkotó kifejezés (vagy ezek listája), amelynek értéke (kifejezéslista esetén az utolsóé) egyúttal a függvény eredménye is:

(defun miez (a b)
  (list 1 a 3 b))

függvénydefiníció után a (miez 2 4) kifejezés értéke (1 2 3 4) lesz.

Párok és listák

A Lisp nyelvben a listák egyszeresen láncolt listák, azaz a mutatókat követve egy irányban bejárhatók. A lista celláit cons celláknak (sokszor egyszerűen pároknak) nevezzük. Egy cons cella két mutatóból áll, amelyeket car-nak és cdr-nek hívunk, ahol car értéke a lista feje (azaz első eleme), míg cdr-é a lista farka (azaz a lista fejét követő összes többi elem). Ezen elnevezések eredete az első Lisp megvalósításig nyúlik vissza, az akkori IBM számítógépeken ugyanis így nevezték a Lisp értelmező által használt hivatkozásfeloldó műveleteket (amelyek elérték a mutatók által megcímzett memóriaterületet).

A cons cellákból tetszőleges adatszerkezet építhető, a leggyakoribb azonban a szabályos lista, amelynek car mutatója a lista első elemére, cdr mutatója pedig a farkára mutat, tehát kivétel nélkül vagy a nil szimbólumra vagy egy másik szabályos listára (amely ugye a így a fej nélkül egy már elemmel rövidebb változata az eredeti listának).

Mint látjuk, a listák nem atomi értékek, hanem cons cellák láncolt sorozatai. Egy listára hivatkozó változó nem más, mint a lista első cons cellájára hivatkozó mutató. Egy lista bejárása a cdr függvény sorozatos meghívásával lehetséges, amellyel tehát a listát alkotó cons cellákat látogatjuk sorra.

Egy zárójelezett S-kifejezés egy ilyen láncolt listát definiál. Ugyanazon lista ábrázolására S-kifejezésként számos lehetőség kínálkozik. Egy cons cellát felírhatunk az ún. pontozott pár jelöléssel (a . b) alakban, ahol a a car, míg b a cdr mutató. Ezt az alakot hívjuk kanonikus alaknak. Egy ebben az alakban felírt lista a (1 . (2 . (3 . (4 . nil)))) formát ölti. Ennek az egyszerűsített írásmódja a (1 2 3 4) forma.

A két alak keverhető is, azaz ugyanezt a listát felírhatjuk (1 2 . (3 4)) vagy (1 2 3 4 . nil) alakban is. A pontozott pár alak arra is lehetőséget ad, hogy nem szabályos listát alkotó cons cellákat hozzunk létre: (1 2 . 3): itt az első cella cdr mezője ugyan a második cellára mutat (2 . 3), a másodiké viszont a 3 értékre. Párokat létrehozhatunk a cons beépített függvény segítségével is, amely két argumentumot vár, rendre a car és a cdr mutatók értékét.

A párok sokrétű felhasználhatóságának köszönhetően elterjedt de téves az a vélekedés, hogy a Lisp-ben nincs is más összetett adatstruktúra. Valójában a legtöbb Lisp megvalósítás a számtalan skalár-típus mellett tartalmaz más típusokat is, például a vektorok és mátrixok (vagy tömbök), objektumok, tulajdonságlisták, hash táblák stb.

Megosztott struktúra

A Lisp-ben a listák, lévén, hogy egyszeresen láncolt listák, tartalmazhatnak közös, megosztott szakaszokat. Nevezetesen, két (vagy több) listának lehet ugyanaz a farka. Például az alábbi kód hatására

(setq ize (list 1 2 3))
(setq bigyo (cons 0 (cdr ize)))

az ize és bigyo változók rendre az (1 2 3) és a (0 2 3) értéket veszik fel. A (2 3) szakasz közös, ha ez valamilyen módon megváltoztatnánk, mindkét lista értéke megváltozna. Ez a megosztás nagyon kedvező hatással van a teljesítményre és a programok memóriaigényére, ugyanakkor könnyen válhat hibák forrásává, ha olyan függvényeket használunk, amelyek destruktív módon manipulálják a listákat.

A tisztán funkcionális programozás hívei éppen ezért elkerülik a destruktív függvények használatát. A Scheme-ben, amely a Lisp funkcionális jellegére nagy hangsúlyt fektet, a destruktív függvények neve egy-egy figyelemfelkeltő felkiáltójelben végződik, mint például set-car!, amely felülírja egy pár első tagját. A Common Lisp nyelvjárásban a desktruktív függvények jóval gyakoribbak, sőt, a nyelv definiál egy rendhagyó műveletet (a setf-et) is, amely desktruktív függvények létrehozását és használatát hivatott megkönnyíteni.

Önazonos kifejezések és az idézés

Amikor egy kifejezést kiértékelünk, egy másik, többnyire egyszerűbb kifejezést, értéket kapunk. A ( 2 3) kifejezés például 5-té egyszerűsödik. Bizonyos kifejezések azonban saját magukká értékelődnek ki. Ilyenek a már említett egészek és a füzérek, de ilyen a nil és a t kulcsszó is.

A Lisp-ben lehetőségünk van arra is, hogy egy értéket megvédjünk a kiértékeléstől. Erre szolgál az idézés, azaz a quote rendhagyó művelet, amelyet röviden egy felülvesszővel (´) is jelezhetünk. Ha például megpróbáljuk kiértékelni az ize kifejezést, akkor vagy az ilyen nevű változó értékét kapjuk, vagy hibát, ha nincs ilyen változó. Ha magát az ize szimbólumot akarjuk felírni, akkor idézetté kell tennünk: (quote ize) vagy egyszerűen ´ize. Ezzel már könnyen tudunk a nil-hez hasonló önazonos neveket definiálni:

(setq ize ´ize)

Ezután akármilyen mélységben értékeljük ki ize kifejezést, mindig önmagát fogjuk kapni. (Tehát ize értéke ize, aminek értéke megint csak ize stb.)

A makrókat lehetővé tevő nyelvjárások ennél bonyolultabb idézőjeleket is definiálnak, mint például a részleges idézést (backquote vagy quasiquote, jele a hátravessző, `). Ennek hatása majdnem azonos a hagyományos idézéssel, azt kivéve, hogy egy vesszővel lehetőség van "visszaváltani" idézett módból kiértékelendő módba egy-egy részkifejezés erejéig, ezzel kényelmesen változókat ágyazhatunk egy nagyobb idézett kifejezésbe.

Az önazonos és az idézett kifejezések alkotják a Lispben a konstansokat. (Bár ez az elnevezés nem pontos, mert a gyakorlatban lehetőség van ezek értékének megváltoztatására is, amely komoly félreértésekre és zavarokra adhat okot. Megoldható például, hogy az ´ize kifejezés egy előfordulása – tkp. egy hivatkozás – kiértékeléskor ne ize, hanem más értéket szolgáltasson, de ez mindenképp kerülendő.)

A programkód listaszerkezete

Az eddigi példákban szereplő karaktersorozatok szigorúan véve nem Lisp programok, csak azok írott reprezentációi. Amikor beírjuk őket a Lisp értelmezőbe, az elemző (a Lisp esetében a read függvény) azonnal átalakítja őket láncolt listakká (azaz fa struktúrákká).

A Lisp makrók ezeken a struktúrákon, nem pedig az írott reprezentáción manipulálnak. A legtöbb más nyelvnél az elemző kimenete szigorúan belső, csak a fordító- vagy értelmezőprogram által elérhető adat. A C-ben ugyan vannak makrók, ám ezek a programszöveg előfeldolgozása (preprocesszálása) során aktiválódnak, mielőtt az elemző megkezdené a munkáját.

Egyszerű Lisp megvalósításokban az értelmező közvetlenül ezt a belső formát dolgozza fel a program futtatásához, azonban a legtöbb létező implementáció a hatékonyság érdekében futtatás előtt egy alacsonyabb szintű byte-kódra (adott esetben gépi kódra) fordítja a függvényeket.

Kiértékelés és a OKK (REPL)-ciklus

A Lisp rendszereket gyakran egy interaktív parancssoron keresztül vezéreljük, amelyet adott esetben kiegészíthet egy integrált fejlesztői környezet (IDE). A felhasználó vagy közvetlenül a parancssorba írja be a kifejezéseket, vagy egy ablakba begépelve egy nagyobb program részeként, esetleg utasítja a környezetet, hogy tegye meg ezt helyette (mondjuk egy állományból).

A Lisp értelmező először beolvassa az adott kifejezést, ezután kiértékeli azt, végül kiírja az eredményt. Ennek megfelelően a Lisp parancssori végrehajtást gyakran "olvasás-kiértékelés-kiírás" vagyis OKK-ciklusnak, angolul "read-eval-print-loop"-nak, REPL-nek hívjuk.

A ciklus három ütemének egy-egy alapvető Lisp függvényt lehet megfeleltetni.

A read függvény beolvassa egy S-kifejezés írott reprezentációját, eredményként annak belső ábrázolását adja. Ha például bemenetként a ( 1 2) szöveget kapja, egy listát leíró, cons cellákból álló láncolt struktúrát ad eredményül, amelynek első eleme a szimbólum, második és harmadik eleme pedig rendre az 1 és 2 egészek. Ez történetesen érvényes programkód is, azaz kiértékelhető, mert az első helyen álló szimbólum egy operátor, amely alkalmazható a további elemekre, mint argumentumokra.

Az eval függvény kiértékeli az argumentumaként kapott listaszerkezetet, egy újabb struktúrát (S-kifejezést) adva eredményül. Ez technikailag nem feltétlenül értelmezést jelent, mivel a Lisp megvalósítások a programkódot először gyakran bájt-kóddá fordítják, majd az így kapott kód futtatását a processzorra bízzák. A gyakorlatban azonban kényelmes értelmezésként gondolni rá: elsőként rekurzívan kiértékelődnek az argumentumok (és az argumentumok argumentumai, sít.), majd az argumentumok értékével hívjuk meg a lista fejében hivatkozott függvényt vagy operátort, jelen esetben az összeadást. Az eredményként kapott érték (itt 3) a teljes kiértékelés végeredménye is egyben.

A print függvény feladata az argumentuma megjelenítése a felhasználónak. Egyszerű értékek esetén ez a feladat triviális, bonyolultabb struktúrák, listák esetében azonban a teljes struktúra bejárását igényli.

Ezen három függvény megléte esetén egy primitív OKK-ciklus írása nagyon egyszerű:

(loop (print (eval (read))))

ahol a loop rendhagyó művelet újra és újra kiértékeli az argumentumaként kapott kifejezést, a végtelenségig.

Példaprogramok

Alább olvasható pár jellegzetes Lisp példaprogram. Mivel a rekurzió, amely a Lisp nyelvnek jellegzetes vonása, számos matematikai definíció alapja is, a szintaktika elsajátítása után az ilyen definíciók lefordítása Lisp-re nem okoz különösebb nehézséget. A példák ilyen definíciók Lisp-beli megfelelői. Az első függvény a jól ismert faktoriális függvény egy lehetséges megvalósítása:

(defun factorial (n)
  (if (<code><=</code> n 1)
    1
    (* n (factorial (- n 1)))))

Álljon itt egy másik változat, amely a legtöbb Lisp megvalósításban hatékonyabb, mert jobbrekurzív, azaz a függvény törzsének, legutolsó, legkülső hívása a rekurzív hívás, és ez lehetőséget ad optimalizálásra:

(defun factorial (n &optional (acc 1))
  (if (<code><=</code> n 1)
    acc
    (factorial (- n 1) (* acc n))))

Vegyük észre, hogy itt a részeredmény egy külön argumentumban (az akkumulátorban) gyűlik.

Ellenpontként következzék egy iteratív változat a Common Lisp ciklusszervező loop makróját használva (ez a makró nem azonos az előbb látott loop-pal):

(defun factorial (n)
   (loop for i from 1 to n
         for fac = 1 then (* fac i)
         finally return fac))

Az alábbi függvény egy listát fordít meg (a Lisp-ben valójában van egy azonos nevű, azonos funkcionalitású beépített függvény):

(defun reverse (l &optional acc)
  (if (atom l)
    acc
    (reverse (cdr l) (cons (car l) acc))))

Megvalósítások

A Lisp nyelveknek számos megvalósítása készült. A legkorábbiak értelmezőprogramok voltak, habár a Lisp programok gépi kódra fordítása is hamar terjedni kezdett. Az 1970-es években néhány cég ún. Lisp-gépeket kezdett gyártani és forgalmazni. Ezek a számítógépek – az eredeti gépi utasításkészletüknek egyfajta Lisp-bájt-kóddá való átírása (ahol így a Lisp gépi-kóddá vált) után – Lisp programok futtatására voltak tervezve és optimalizálva. A modern Common Lisp rendszerek túlnyomó többsége bájt-kódra fordítja a programokat az interaktív rendszerben való futtatás előtt és gépi kódra, ha "kívülről" is futtatható programot kell készíteni. A legtöbb Scheme megvalósítás ugyanakkor ma is értelmezőprogram alapú. Lisp megvalósítások alapjául szolgálhat a SECD virtuális gép is.

Nyelvjárások és változatok

Közel ötvenéves története során a Lisp-nek számos nyelvjárása jött létre. Mindegyikben közös az S-kifejezések szerepe és szerkezete. Ezen túlmenően a legtöbb nyelvjárásnak több megvalósítása is készült, a népszerű CommonLisp-nek például több mint egy tucat implementációja ismert.

Az egyes nyelvjárások között komoly eltérések lehetnek. A Scheme és a Common Lisp például még az olyan alapvető kérdésekben is eltér, mint a függvényeket definiáló művelet neve. Ugyanazon dialektus különböző megvalósításai azonos szintaktikát követnek és ugyanazokat a beépített függvényeket definiálják, a könyvtári függvények készlete azonban már eltér.

(Figyelem: az alábbi lista vegyesen tartalmaz különféle nyelvjárásokat és megvalósításokat, távolról sem teljes, és nem tükröz fontossági, népszerűségi vagy időrendi sorrendet!)

Lisp – McCarthy eredeti megvalósítása, amely az MIT-n készült.
Common Lisp – Alapvetően a ZetaLISP-re és a Franz Lisp-re, kisebb mértékben az InterLISP-re támaszkodva hozták létre, ez ma a de facto ipari szabvány.
MacLisp – Az eredeti Lisp egyenes ági leszármazottja, az MIT-n fejlesztették ki. (A Mac előtag nem az Apple Macintosh számítógépre, hanem McCarthy nevére utal.)
ZetaLisp – A Lispgépek által használt nyelv, a MacLisp továbbfejlesztése.
InterLisp – Szintén az MIT fejlesztése a Xerox Lispgépeihez, "nyugati parti" (west coast) Lispként is hivatkoznak rá. A csökkentett, "InterLISP 65" névre hallgató változatát kiadták Atari 6502 típusú számítógépekre is.
Franz Lisp – eredetileg a Berkeley egyetem fejlesztése, később a Franz cég vette át.
Gold Hill Common Lisp – A Common Lisp egy korai PC-s megvalósítása.
Coral Lisp – Lisp értelmező Macintosh számítógépekre.
Scheme – Egy eredetileg oktatási célokra tervezett, minimalista Lisp megvalósítás.
AutoLISP/Visual LISP – Az AutoCAD testreszabáshoz használható nyelve.
Emacs Lisp (ELisp) – Az Emacs szövegszerkesztő szkriptnyelve.
Oaklisp – A Scheme objektumorientált kiegészítése, amelyben az osztályok is elsőrendű (azaz programból manipulálható) objektumok.
Guile – A Scheme GNU megvalósítása.
Cambridge Lisp – Eredetileg IBM mainframe számítógépekhez készült, később a Metacomo cég Amiga számítógépekhez is kiadta.
Lispkit Lisp – Egy tisztán funkcionális ("tiszta Lisp") nyelvjárás és megvalósítása a SECD virtuális gépre, leggyakrabban funkcionális programozási elvek kipróbálására és tesztelésére használják.
Symmetric Lisp – Egy párhuzamos programozást lehetővé tevő, Common Lisp-ben megvalósított Lisp nyelv, amelyben a környezetek elsőrendű objektumok.
STING – A Scheme egy párhuzamosított változata, amely szimbolikus programozási nyelvek operációs rendszereként hivatott szolgálni. Szolgáltatásai között megtalálhatók az elsőrendű szálak, processzorok és testreszabható ütemezési stratégiák.
*LISP (STARLISP) – A Common Lisp Egy adat-párhuzamos megvalósítása.

Lásd még

Bill Schelter (Lisp programozó)
Kent Pitman (Lisp programozó)
Paul Graham (Lisp programozó; az Arc (még nem létező) nyelvjárás értelmi szerzője; esszéista)
LISP atom