Rendszer

Rendszer
embléma
Alapadatok
Paradigmák : Multi-paradigma : funkcionális , eljárási , meta
Megjelenés éve: 1975
Tervező: Guy Lewis Steele junior , Gerald Jay Sussman
Fejlesztő: Guy L. Steele és Gerald Jay Sussman
Jelenlegi  verzió : R 7 RS (ratifikált szabvány)   (2013)
Gépelés : erős , dinamikus
Fontos megvalósítások : sok z. B. MIT / GNU rendszer
Befolyásolta: Lisp , ALGOL , MDL
Érintett: Közös Lisp , JavaScript , R , Ruby , Dylan , Lua , Racket , Snap! / BYOB
www.scheme-reports.org

A Scheme programozási nyelv egy Lisp -változat. Ez a funkcionális , hanem támogatja más programozási paradigmákat (például imperatív programozási ).

A sémát az jellemzi, hogy a szintaxis csak néhány programozási koncepciót határoz meg . Ezért viszonylag sokféleképpen írható le egy program a sémában.

Például a Scheme szabványban nincsenek eszközök az objektum-orientált programozásra, de a makróknak és a λ kifejezéseknek köszönhetően nagyon könnyű programozni őket a nyelvre: A Scheme egy programozható programozási nyelv, amely később bővíthető.

A rendszert Gerald Jay Sussman és Guy Lewis Steele Jr. fejlesztették ki a Massachusetts Institute of Technology-ban , ahol a hivatalos specifikáció is rendelkezésre áll, az úgynevezett Revised Report . A jelenlegi specifikáció az R 7 RS.

Szintaxis és szemantika

A séma szintaxisa nagyon szabályos és egyszerű. Az alap egy teljesen zárójeles előtag -jelölés (lásd még a lengyel jelölést ). A program kifejezésekből és definíciókból áll . A kifejezések vagy literálok, vagy összetett kifejezések , amelyek függvényhívást képviselnek: 

  (operator operand-1 operand-2 ... operand-n)

Az összetett kifejezés minden eleme egy kifejezés.

A kifejezések jelentését (vagy szemantikáját) az értékelésük határozza meg . A szó szerinti kifejezés jelentése (szemantika) a kifejezés állandó értéke. Például a karakterlánc 2értéke 2, a karakterlánc #tpedig az "igaz" logikai igazságértékét . Összetett kifejezések értékelésekor a kifejezésnek operator(matematikai operátorok alapján ) ki kell értékelnie egy függvényt. Az operátortól jobbra tetszőleges számú operandus található , amelyek viszont egyszerű vagy összetett formák.

A zárójelek ezért különösen fontosak, és a legtöbb más programozási nyelvvel ellentétben nem állíthatók be önkényesen. Az összetett forma 

(foo 42)

például egy kifejezés, amely szemantikai szinten azt jelenti, hogy a változóhoz fookapcsolt függvényt meg kell hívni az argumentummal 42. A kifejezés értékelése 

(foo (42))

azonban hibához vezet a futásidőben: (42)Ez egy összetett forma, és a szemantika előírja az operátor használatát. Mivel azonban 42ez egy szám, és nem függvény, hiba lép fel.

A teljesen zárójeles előtag -jelölés egyik előnye, hogy ennek a jelölésnek egyetlen előzménye van minden operátor számára . A séma szintaxisának gyakori kritikája a zárójelek nagy száma, amelyek megnehezítik a forráskód létrehozását és szerkesztését. A séma programozói ezt a nehézséget ellensúlyozzák olyan szerkesztők használatával , amelyek különleges módon támogatják a séma forrásszövegeinek feldolgozását (például Emacs ). Ezek a segédeszközök magukban foglalják a kód automatikus behúzását és a szerkesztés során egymáshoz tartozó zárójelek jelölését.

Néhány séma -megvalósítás, például a Racket, lehetővé teszi a szögletes zárójelek használatát a nyelvi szabvány mellett. Ennek célja az egyértelműség növelése. Példa: 

  (let ([x 42]
        [y 23])
     (+ x y))

Különleges formájú lambda

A lambda kulcsszó bevezeti az úgynevezett lambda kifejezések speciális formáját. A lambda kifejezés olyan eljárásnak minősül, amely a séma első osztályú értéke. Az eljárások tehát használhatók a programban, mint más típusú értékek, például nevekhez kötve, argumentumként átadva egy eljáráshívásban vagy egy eljárással visszaadva.

A lambda speciális forma meghatározása:

(lambda (érvelés) kifejezés) 

(lambda (x) (* x x)) ; Bildet das Quadrat von x

A fenti lambda kifejezés által generált eljárás meghívása: 

((lambda(x) (* x x)) 5) ; Bildet das Quadrat von 5
; (Rückgabe = 25)

Ennek a különleges űrlapnak a neve a lambda calculushoz nyúlik vissza .

Globális definíciók

A kulcsszót tartalmazó meghatározás defineértéket köt egy névhez. A név globálisan kötött, így a definíció után a programban bárhol használható. Mivel a séma eljárásai is értékek, a defineglobális eljárásokat a gombbal is definiálhatjuk. A kód következő szakaszában a név a-numbera 42 -es számhoz van kötve, majd a név squareegy függvényhez van kötve , amely négyzetet alakít: 

  (define a-number 42)

  (define square
     (lambda (x)
        (* x x)))

Egyszerűsített jelölés is használható globális eljárások meghatározására, amelyekben a lambdakifejezés kihagyásra kerül. A fenti definíció squarerövidítve az alábbiak szerint írható: 

  (define (square x)
    (* x x))

Az alábbi kifejezés példát mutat arra, hogy egy függvény hogyan adhat vissza egy másik függvényt: 

(define (sum-with x)
    (lambda (y) (+ y x)))

A sum-with függvény x paramétere határozza meg a visszaküldött függvény viselkedését: A visszaadott függvény hozzáad egy y argumentumot pontosan a sum-with által megadott x tényezővel. 

((sum-with 5) 1)
; (Rückgabe = 6)

Helyi kapcsolatok

A változók és függvények deklarálása kissé eltér a sémában, mint a hagyományos programozási nyelvekben. Először is a változókat és függvényeket (eljárásokat) nem kell azonosítókhoz kötni, másrészt a deklarálás eljárásokon keresztül történik, nincsenek külön kulcsszavak.

A definiálási és let -űrlapok rendelkezésre állnak a deklarációhoz ; szükség esetén a let * és letrec változatok is használhatók let helyett .

hagyja

lettöbb értéket köt a megadott azonosítóhoz. Ezek a kötések csak a törzs belsejéből letláthatók. leta következő szintaxissal rendelkezik: 

 (let ((name-1 ''ausdruck-1'')
       (name-2 ''ausdruck-2'')
       ...
       (name-n ''ausdruck-n''))
   ...
   ; Rumpf des let-Ausdrucks
   ; name-1, ..., name-n sind nur innerhalb des Rumpfes von '''let''' gebunden
   ...
 )

A kifejezések ausdruck-1a ausdruck-nértékeljük meghatározatlan érdekében, mielőtt a kapott értékek kötődnek az egyes elnevezések. Ezután a letkifejezés törzsét értékelik. A kötések name-1felfelé csak a törzsben alkalmazhatók name-n. Különösen letnem lehet másik nevet használni a kifejezésben , amely ugyanazon kifejezéshez kapcsolódik (vö. ). ausdruck-iletlet*

A testben lévő utolsó kifejezés értéke a teljes letkifejezés értékét adja meg . Mivel a kifejezések értékelési sorrendje nem rögzített, és elméletileg még az összes kifejezést is ki lehet értékelni egyszerre, párhuzamról beszélünk . ausdruck-ilet

Példák: 

 (let ((a 3)
       (b (+ 10 12))
       (c (lambda (n) (* n 2))))
      (c (+ a b)))
 => 50

 (let ((a 1))
      (let ((a 0)
            (b a))
           b))
 => 1

letegy egyszerűsített szintaxis, amelyet függvényhívássá alakítanak át. Példa: 

  (let ((a (+ 1 1)) (b (+ 2 2)))
    (+ a b))

kiterjed a következőre: 

  ((lambda (a b) (+ a b)) (+ 1 1) (+ 2 2))

hadd *

let*ugyanazzal a szintaxissal rendelkezik, mint a lethasonló szemantika. Ezzel szemben let, let*a sorrend, amelyben a kifejezéseket kiértékelése a nevét-expresszió pár rögzített: A kiértékelés balról jobbra. Az egyik tehát sorozatosróllet* beszél . Ezzel ellentétben leta kifejezésekben (a név-kifejezés párok jobb oldalán) a bal oldalon lévő kötőpárok nevei érhetők el.

Példa: 

 (let ((a 1))
      (let* ((a 0)
             (b a))
            b))
 => 0

Hogyan letis let*egyszerűsített szintaxis, és beágyazott függvényhívásokká alakul át: 

  (let* ((a (+ 1 1))
         (b (+ a 1)))
    (* a b))

kiterjed a következőre: 

  ((lambda (a)
     ((lambda (b) (* a b)) (+ a 1)))
   (+ 1 1))

letrec és let néven

letrecA kifejezéseknek ugyanaz a szintaxisa, mint a letkifejezéseknek. A bekötendő nevek láthatóságában azonban vannak különbségek. A nevek (azaz a kötőpárok bal oldala) használhatók a kötőpárok bármely kifejezésében. Az a let*jól ismert korlátozás, miszerint a kifejezésekben szereplő nevek csak a korábbi (azaz balra lévő) nevekre vonatkozhatnak, ezért már nem alkalmazható. Különösen letreca helyi rekurzív függvények meghatározására használható . Példa: 

  (letrec ((sum (lambda (lst s)
                 (if (null? lst)
                   s
                   (sum (cdr lst) (+ s (car lst)))))))
    (sum (list 1 2 3) 0))
  => 6

Kölcsönösen rekurzív függvények is meghatározhatók: 

  (letrec ((even? (lambda (n)
                  (if (zero? n)
                    #t
                    (odd? (- n 1)))))
           (odd? (lambda (n)
                  (if (zero? n)
                    #f
                    (even? (- n 1))))))
    (even? 42))
  => #t

Ennek egyik változata az letrecúgynevezett elnevezésűlet , amelyet kifejezetten ciklusok programozására használnak. A szintaxis az 

  (let ''name'' (''bindungen'') ''rumpf'')

, ahol bindungena letnévből és kifejezésből ismert párok találhatók. Az elnevezettlet törzs egy olyan eljárás törzseként használatos, amelynek a neve namepontosan annyi argumentummal rendelkezik, mint amennyi kötelező pár van megadva. A nevelet egy makró, amely namekiterjed ennek az eljárásnak a hívására . A kötőpárok jobb oldalait argumentumként használják. A példa letreclehet írni egy megnevezett, mintlet ez: 

  (let sum ((lst (list 1 2 3))
            (s 0))
    (if (null? lst)
        s
        (sum (cdr lst) (+ s (car lst)))))

meghatározni

defineleginkább függvények és állandók globális szintű deklarálására szolgál, de az eljárásokon belül is használható. Az így összekapcsolt változók láthatósága arra a testre korlátozódik, amelyben a definíció található. defineamelyek nem globális szinten vannak, belső definíciókat kapnak, és néha a jobb olvashatóság kedvéért használják őket letrec.

A szintaxis a következő: 

 (define bezeichner ausdruck)

A kifejezés rekurzívan azonosítóra is vonatkozhat.

Ebben a példában, fooés barbelsőleg vannak definiálva. Mindkét változó csak a letkifejezés törzsén belül látható . 

  (let ((x 5))

    (define (foo y)
      (bar x y))

    (define (bar a b)
      (+ (* a b) a))

    (foo (+ x 3)))

A fenti kód megfelel ennek a verziónak letrec: 

  (let ((x 5))
    (letrec ((foo (lambda (y) (bar x y)))
             (bar (lambda (a b) (+ (* a b) a))))
      (foo (+ x 3))))

Adattípusok

Eljárások

Az eljárások a rendszer egyik legfontosabb nyelvi eleme. Ezek lehet leírni egy lambda kifejezés ( lambda ). Mivel a rendszerben a többi adattípussal megegyezően kezelik őket , lehetséges, hogy let vagy define azonosítóhoz kössük őket.

Példa: Egy eljárás két argumentummal: 

 (define test
   (lambda (arg1 arg2)
         ... ))

Létezik egy egyszerűsített jelölés, amely a definíció és a lambda kifejezések kombinálására használható: 

 (define (test arg1 arg2)
  ...)

Ezt az eljárást a következőképpen hívják: 

 (test wert1 wert2)

Az eljáráshívásokat általában két zárójelbe kell tenni. A Séma hangsúlyozza az értékkel bíró kifejezések szerepét azokkal a parancsokkal szemben, amelyek valamit tesznek. Ezért - sok más nyelvvel ellentétben - nem szükséges az eljárásleírás törzsében lévő kifejezést visszatérési értékként megjelölni. Éppen ellenkezőleg: a konstrukcióhoz hasonló konstrukciókra van szükség a nyilatkozatok végrehajtásához anélkül, hogy visszaadnák értéküket.

Természetesen számos előre meghatározott eljárás létezik, például hátrányok , autó , cdr , + , - , * , < . Ezek az előre definiált eljárások újradefiniálhatók, ahogy az alábbi példa mutatja: 

 (define (+ x y)
     (- x y))

+ most nem összeadná, hanem kivonná.

Mivel a matematikai operátorokat eljárások is megvalósítják, a számításokhoz előtagjelölés tartozik . A séma nem rendelkezik operátorhierarchiával, minden képlet egyedi.

Párok és listák

A listákat viszonylag gyakran használják a Scheme programokban. A séma listáinak legfontosabb építőeleme a párok . A pár olyan adatstruktúra, amely tetszőleges két sémaértéket tartalmaz. Az consúj párt jön létre. Példa: 

  (cons 'sinn 42)

Ez a hívás consúj párt hoz létre, amelynek első mezője a szimbólumot 'sinn , a második mező pedig a 42. számot tartalmazza. A pár első mezője a beépített függvénnyel érhető el car(ejtsd: "carr"), második mezővel cdr(ejtsd: "Kudder"). A név car(" c ontent of a ddress r egister") és cdr(" c ontent of d ecrement r egister") a történelemben gyökereznek, de így megszerezték. Olyan műveletekre utalnak, amelyeket az IBM 704 első Lisp -implementációjában használtak . A beépített funkciók és a pár megfelelő mezőinek értékeit állítsa új értékre. A típus predikátum akkor és csak akkor tér vissza (igaz esetén), ha azt egy párra alkalmazták, azaz a következővel generált értéket. set-car!set-cdr!pair?#tcons

A listák meghatározása induktív : az írott üres lista '()lista. Ezenkívül egy pár, amelynek cdrlistája, lista. A definíció azt jelenti, hogy egy lista párokból áll: A pár carmezőjében van bármilyen érték, a cdrmezőben a pár, amely a következő listaelemet tartalmazza. A lista végét akkor érjük el, amikor cdraz üres lista megtalálható a mezőben, amelyet a beépített funkcióval null?ellenőrizhetünk. Példák listákra: 

  '()
  (cons 1 '())
  (cons 1 (cons 2 '()))

Van egy kényelmes funkció is a listák létrehozásához list, amely tetszőleges számú argumentumot felvesz és listaként ad vissza. A következő két lista egyenértékű: 

(list 1 2 3)
(cons 1 (cons 2 (cons 3 '())))

A listákat feldolgozó függvények többnyire rekurzív függvények. Ez a funkció használható például egy lista hosszának meghatározására: 

  (define (length lst)
    (if (null? lst)
       0
       (+ 1 (length (cdr lst)))))

A séma programozói szinte soha nem használják ki azt a lehetőséget, hogy a set-car!vagy a set-cdr!gombbal módosítsák a pár mezőit . A listák feldolgozása szinte mindig tisztán funkcionális , azaz. H. listákból új listák jönnek létre. Példa erre a függvény map, amely egy függvényt falkalmaz a lista minden elemére: 

  (define (map f lst)
    (if (null? lst)
       '()
       (cons (f (car lst)) (map f (cdr lst)))))

Más adattípusok

További adattípusok:

  • egész szám (egész számok, tetszőleges számú számjegy)
  • racionális (törtek, tetszőleges pontosság)
  • valós ( tizedes számok )
  • komplex számok
  • Szimbólumok
  • jel
  • Húrok
  • Párok
  • Vektorok
  • Port (bemeneti / kimeneti eszközök, fájlok stb. Ábrázolása)
  • Boolean

az igaz és hamis szimbólumok logikailag hamisak , #tés a #fScheme csak értelmezi #f(elavult implementációkban csak az üres lista szinonimáját '()); minden más érték igaznak tekinthető.

Az eset megkülönböztetése

Ha

ifkiértékeli a teszt kifejezést, és annak valós értékétől függően értékeli a második ( következő ) vagy a harmadik operandust ( alternatíva ). A teljes If kifejezés értéke a következmény vagy alternatíva értékeléséből származik. #fAz alternatíva csak akkor kerül kiértékelésre , ha a tesztkifejezés rendelkezik értékkel , ellenkező esetben a következõ. I. E. kivéve minden érték #flogikailag igaz.

Egy megfelelő kifejezés így néz ki, például: 

 (if (> x 0)
    'positive
    'not-positive)

Ez a kifejezés vagy a szimbólumra, 'positivevagy a szimbólumra vonatkozik 'not-positive. Mivel az If kifejezés, az If használható kifejezéseken belül: 

  (* 2 (if (> x max) max x))

Kond

Ezzel condtöbb esetet is meg lehet különböztetni. Egy eset egy tesztből és egy következményből áll . Az eseteket balról jobbra vizsgálják. Ha a teszt nem ad #fvissza egy esetet , akkor a megfelelő következmény kiértékelésre kerül: Ez az érték adja meg a teljes condkifejezés értékét . Ha a megadott esetek egyike sem érvényes, a többi esetet , ha van ilyen, kiértékeli. Ha nincs más eset, akkor a condkifejezés értéke nincs definiálva. Példa: 

 (cond ((= wert 65) 'a)
       ((= wert 66) 'b)
       (else 'unbekannt))

szalagok

A Scheme nem rendelkezik programozási nyelvi konstrukciókkal a ciklusokhoz (azonban az automatikusan beépített "Scheme Standard Libraries" lehetőséget kínál a ciklusok például a do konstrukcióval). A hurkokat általában rekurzív függvényhívások segítségével valósítják meg . A legegyszerűbb esetben egy végtelen ciklus így néz ki: 

 (define (loop)
  (loop))

Ennek bizonyítására gyakran bemutatott példa a faktoriális számítás : 

 (define (fak n)
    (if (= n 0) 1
        (* n (fak (- n 1)))))

Ennek az elméletileg vonzó koncepciónak a gyakorlati megvalósítása érdekében a Séma optimalizálja a végtörzs rekurziót (vagy általánosabban: az összes végtörzs függvényhívást). Nem terminális rekurzió esetén a funkció továbbra is működik az önhívás után. A példában a szorzás: 

 (fak 4)
 (* 4 (fak 3))
 (* 4 (* 3 (fak 2)))
 (* 4 (* 3 (* 2 (fak 1))))
 (* 4 (* 3 (* 2 (* 1 (fak 0)))))
 (* 4 (* 3 (* 2 (* 1 1))))
 (* 4 (* 3 (* 2 1)))
 (* 4 (* 3 2))
 (* 4 6)
 24

A folyamat során egyre több (memória) hely szükséges a köztes eredmények mentéséhez. A fenti példa farok-rekurzív változata a következő lenne: 

 (define (fak-iter n a)
  (if (= n 0) a
      (fak-iter (- n 1) (* n a))))

 (define (fak n)
  (fak-iter n 1))

A folyamat ekkor így nézne ki: 

 (fak 4)
 (fak-iter 4 1)
 (fak-iter 3 4)
 (fak-iter 2 12)
 (fak-iter 1 24)
 (fak-iter 0 24)
 24

A Séma felismeri, hogy az eljáráshívás eredménye csak visszaadásra kerül, és ezért ugyanazt a memóriaterületet használhatja minden eljáráshíváshoz. A kiegészítő változó egy az eljárásban FAK-iter felhalmozódik a közbenső eredményeket.

Hozzászólások

A megjegyzéseket pontosvesszővel (;) kell bevezetni, és a sor végéig terjednek.

A rendszer és a LISP összehasonlítása

Három fő jellemző különbözteti meg a sémát a Lisptől :

  • A sémában megtalálható a hívás-árammal-folytatás funkció . Lehetővé teszi az aktuális folytatás (azaz az aktuális program egyfajta végrehajtási állapota ) változóként való használatát . Ez lehetővé teszi, hogy a programsorozat későbbi szakaszában visszatérjünk a folytatás pontjára.
  • A Séma szabvány előírja a megfelelő farokrekurziót : A végső rekurzív pozícióban lévő eljáráshívások nem szabad memóriaterületet fogyasztaniuk a program híváskötegén . Ez azt jelenti, hogy korlátlan számú végleges rekurzív hívás lehetséges egy eljáráshoz.
  • A LISP -vel ellentétben a séma makrói "higiénikusak": A makrón belül bevezetett azonosítók nem rejtenek el más azonosítókat a lexikai környezetben a makrón kívül, azaz a hívó programon. Ezzel szemben a makrón belül használt azonosítók mindig a makró lexikális környezetében oldódnak fel, nem kívül. Ez azt jelenti, hogy a makró azonosítója csak maga a makró számára látható , és a makró nem fér hozzá a magasabb szintű program azonosítójához, és a program nem férhet hozzá a makró belső azonosítójához.

Megvalósítások és fejlesztési eszközök

Számos programozási nyelv megvalósítás áll rendelkezésre. Az alábbiakban csak néhány népszerű megvalósítást említünk:

  • A Bigloo a séma kódját számos más nyelvre lefordítja: C , Java és .NET .
  • A Chicken egy olyan megvalósítás, amely a sémát C -re fordítja, és ezért gyakorlatilag minden platformon fut. Mind tolmácsot, mind fordítót biztosít, és a C -vel való kapcsolat miatt kiterjedt kiterjesztési könyvtárral rendelkezik. A megvalósítás nagyrészt az R5RS-kompatibilis.
  • A séma értelmezőn kívül a Gambit C rendelkezik az egyik leghatékonyabb Scheme-to-C fordítóval is .
  • A Gauche egy R5RS -kompatibilis megvalósítás. Szkript tolmácsként készült a fejlesztők és a rendszergazdák számára. A fejlesztési célok egy része rövid indítási idő, beépített rendszerfelület, natív többnyelvű támogatás. Továbbá számos bővítmény integrálható, pl. B. OpenGL és GTK + esetén .
  • A GNU Guile könyvtárként integrálható tolmács. Az elsődleges cél az, hogy könnyedén hozzá lehessen adni szkriptképességeket a programokhoz.
  • A LispMe a PalmOS-kompatibilis PDA-k megvalósítása.
  • Racket (korábban PLT Scheme) egy széles körben elterjedt végrehajtását, amelyek amellett, hogy számos könyvtárak, tartalmazza a saját fejlesztési környezetet nevezett DrRacket (korábban DrScheme). A DrRacket kifejezetten a kezdő tréning programozására készült, és könnyen használható. A Racket számos fordítót tartalmaz, amelyek átalakítják a Racket / Scheme kódot bájtra vagy C kódra.
  • A 48. séma egy rendszer megvalósítás, amely teljes egészében a sémában van leírva. A PreScheme nevű, statikusan beírt Scheme dialektust használják a rendszerindításhoz . A 48. séma a séma kódját bájtkódmá alakítja le, amelyet memóriaképbe lehet menteni. A 48. séma különösen figyelemre méltó a séma kód hibakeresésének képessége miatt.
  • SIOD. Egy kicsi, gyors séma -értelmező, amelyet a GIMPs ScriptFu -ban használtak a 2.4 -es verzióig .

irodalom

web Linkek

Wikiforrás: Séma: An Interpreter for Extended Lambda Calculus  - Források és teljes szövegek (angolul)

Bevezetés

Nyelvi szabványok

Egyéni bizonyíték

  1. ↑ az R7RS szabvány oldala
  2. ↑ Az ismert megvalósítások listája
  3. ↑ Bigloo webhely
  4. ↑ Gambit C webhely
  5. ↑ Gauche weboldal
  6. ↑ LispMe weboldal
  7. ↑ Racket webhely
  8. ↑ A 48. séma honlapja
  9. ↑ SIOD honlapján ( Memento az az eredeti származó április 6, 2007 az Internet Archive ) Info: A archív linket helyeztünk automatikusan, és még nem ellenőrizték. Kérjük, ellenőrizze az eredeti és az archív linket az utasítások szerint, majd távolítsa el ezt az értesítést. @1@ 2Sablon: Webachiv / IABot / www.cs.indiana.edu