Lisp (programozási nyelv)
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: 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. SzintaxisA 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 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 1 2 "izé")
kifejezés az (list 1 2 (list 3 4))
kifejezés értéke 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 nil
(list 1 2 "izé")
(list 3 4 "bigyó"))
eredménye 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 miez (a b)
(list 1 a 3 b))
függvénydefiníció után a Párok és listákA 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 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 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 két alak keverhető is, azaz ugyanezt a listát felírhatjuk 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úraA 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 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 Önazonos kifejezések és az idézésAmikor egy kifejezést kiértékelünk, egy másik, többnyire egyszerűbb kifejezést, értéket kapunk. A 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 (setq ize ´ize)
Ezután akármilyen mélységben értékeljük ki 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ő, 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 A programkód listaszerkezeteAz 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 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)-ciklusA 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 Az A 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 PéldaprogramokAlá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ő (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ásokA 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áltozatokKö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!)
Lásd még
JegyzetekTovábbi információk
|
||||||||||||||||||||||||||||
