Halom -orientált programozás - Stack-oriented programming

A veremorientált programozás egy olyan programozási paradigma, amely a veremgép modelljén alapul a paraméterek átadására . A veremorientált nyelvek egy vagy több veremen működnek , amelyek mindegyike más célt szolgálhat. A programozási konstrukciókat más programozási nyelveken módosítani kell a verem-orientált rendszerben való használathoz. Néhány veremorientált nyelv postfix vagy fordított lengyel jelöléssel működik . A parancs minden argumentuma vagy paramétere a parancs előtt szerepel . Például 2, 3, multiplyaz multiply, 2, 3( előtag vagy lengyel jelölés ) vagy az 2 multiply 3( infix jelölés ) helyett a postfix jelölést kell írni . A Forth , az RPL , a PostScript , a BibTeX stílusú tervezési nyelv és sok összeszerelési nyelv illeszkedik ehhez a paradigmához.

A verem-alapú algoritmusok figyelembe veszik az adatokat, felhasználva a verem tetején lévő adatokat, és visszaadva az adatokat a verem tetejére. A veremkezelő operátorok szükségessége lehetővé teszi a verem számára az adatok manipulálását . A kijelentés hatásának hangsúlyozására megjegyzést használunk, amely a verem tetejét mutatja az utasítás előtt és után. Ez a veremhatás diagram.

Az utólagos veremek további célokra külön veremeket vesznek figyelembe. Ez figyelembe veszi a változókat, szótárakat, eljárásokat, néhány tipikus eljárás anatómiáját, az irányítást és a folyamatot. A nyelvi modell elemzése lehetővé teszi a kifejezések és programok egyszerű és elméleti értelmezését.

Halom alapú algoritmusok

A PostScript egy példa a postfix verem alapú nyelvre. Egy kifejezési példa ezen a nyelven 2 3 mul. A kifejezés kiszámítása magában foglalja a verem-orientáció működésének megértését.

A kötegorientáció a következő szállítószalag-analógiaként mutatható be. a végén egy szállítószalag (a bemeneti ), lemezek jelölve 2, 3és mulkerülnek a sorrendben. A szállítószalag ( 2) végén lévő lemez felvehető, más lemezek azonban nem érhetők el, amíg a végén lévő lemezt nem távolítják el. A lemezeket csak egy kötegben lehet tárolni, és csak a köteg tetején lehet hozzáadni vagy eltávolítani, a közepétől vagy aljától nem. Üres lemezek (és jelölő) szállíthatók, és a lemezek véglegesen eldobhatók.

Fogja a lemezt, 2és tegye a veremre, majd vegye le a tányért 3és tegye a veremre. Ezután vegye a multányért. Ez egy végrehajtandó utasítás. Ezután vegye le a kötegről a két felső lapot, szorozza meg a címkéiket ( 2és 3), és írja az eredményt ( 6) egy új lemezre. Dobja el a két régi lemezt ( 2és 3) és a lemezt mul, és tegye az új lemezt a veremre. Mivel nincs több lemez a szállítószalagon, a számítás eredménye ( 6) megjelenik a verem tetején lévő lemezen.

Ez egy nagyon egyszerű számítás. Mi van, ha bonyolultabb számításra van szükség, például (2 + 3) × 11 + 1? Ha először postfix formában írják, vagyis 2 3 add 11 mul 1 adda számítás pontosan ugyanúgy elvégezhető, és a helyes eredmény érhető el. A számítás lépéseit az alábbi táblázat tartalmazza. Minden oszlop egy bemeneti elemet (a szállítószalag végén lévő lemezt) és a verem tartalmát mutatja a bemenet feldolgozása után.

Az összes bemenet feldolgozása után a verem tartalmazza 56, ez a válasz.

Ebből a következőkre lehet következtetni: a verem alapú programozási nyelvnek csak egy módja van az adatok kezelésére, azáltal, hogy egy adatot vesznek a verem tetejéről, ezt nevezik pop pingnek, és az adatokat a verem tetejére teszik vissza, ezt nevezik push ingnek. Bármely kifejezés, amelyet hagyományos módon vagy más programozási nyelven írhatunk, postfix (vagy előtag) formában írható, és így halomorientált nyelv értelmezhető.

Stack manipuláció

Mivel a verem a legfontosabb eszköz az adatok verem-orientált nyelven történő kezelésére, az ilyen nyelvek gyakran biztosítanak valamilyen verem-kezelő operátort. Általában dupa következőket kínálják: a verem tetején lévő elem megkettőzése, exch(vagy swap) elemek cseréje a verem tetején (az első második, a második pedig első), rollciklikus permutáció a veremben vagy a verem egy részén, pop( vagy drop), hogy eldobja a verem tetején lévő elemet (a push implicit), és mások. Ezek kulcsfontosságúak az eljárások tanulmányozásában.

Halomhatás diagramok

Az állítás hatásának megértéséhez segítséget nyújt egy rövid megjegyzés, amely bemutatja a verem tetejét a nyilatkozat előtt és után. A verem teteje a jobb szélső, ha több elem van. Ezt a jelölést általában a Forth nyelvben használják, ahol a megjegyzések zárójelben vannak.

( before -- after )

Például a Forth alapvető veremkezelők vannak leírva:

dup  ( a -- a a )
drop ( a -- )
swap ( a b -- b a )
over ( a b -- a b a )
rot  ( a b c -- b c a )

És az fibalábbi funkció leírása:

fib  ( n -- n' )

Ez egyenértékű a Hoare logika előfeltételeivel és utólagos feltételeivel . Mindkét észrevételeit is szerepelhet mint állításokat , gondoltam, hogy nem feltétlenül összefüggésben Stack-alapú nyelv.

PostScript -verem

A PostScript és néhány más veremnyelv más, más célokra szolgáló veremeket is tartalmaz.

Változók és szótárak

A különböző kifejezések értékelését már elemezték. A változók implementálása minden programozási nyelv számára fontos, de a veremorientált nyelvek esetében ez különös aggodalomra ad okot, mivel az adatokkal való interakciónak csak egy módja van.

Az út változókat végre stack-orientált nyelvek, például a PostScript általában magában foglalja a külön, speciális verem amely rendelkezik szótárak a kulcs-érték párokat . A változó létrehozásához először egy kulcsot (a változó nevét) kell létrehozni, amelyhez ezután egy érték társul. A PostScript -ben a névadat -objektum a -val van előtagolva /, így a névadat /x-objektum is, amely például a számhoz társítható 42. A defineparancs defígy van

/x 42 def

a névhez társítja a verem tetején található szótárban található xszámot 42. Különbség van /xés között x- az előbbi egy adatot reprezentáló adatobjektum, xami az alatt definiáltakat jelenti /x.

Eljárások

Egy verem alapú programozási nyelvben lezajló eljárást önmagában adatobjektumként kezelnek. A PostScript, eljárások jelöljük között {és }.

Például a PostScript szintaxisban

{ dup mul }

névtelen eljárást jelent, amely megkettőzi a verem tetején lévő tartalmat, majd megszorozza az eredményt - négyzeteljárás.

Mivel az eljárásokat egyszerű adatobjektumokként kezeljük, az eljárásokkal rendelkező nevek definiálhatók. Amikor lekérik, közvetlenül végrehajtják őket.

A szótárak biztosítják a hatókör szabályozását, valamint a definíciók tárolását.

Mivel az adatobjektumok a legfelső szótárban vannak tárolva, egy váratlan képesség természetesen felmerül: amikor egy definíciót keresünk a szótárból, a legfelső szótár kerül ellenőrzésre, majd a következő stb. Ha olyan eljárás van definiálva, amelynek ugyanaz a neve, mint egy másiknak, amelyet egy másik szótárban már definiáltak, akkor a helyi hívásra kerül.

Néhány tipikus eljárás anatómiája

Az eljárások gyakran érveket tartalmaznak. Ezeket az eljárás nagyon specifikusan, más programozási nyelvektől eltérően kezeli.

Fibonacci számprogram megvizsgálása PostScriptben:

  /fib
  {
     dup dup 1 eq exch 0 eq or not
     {
        dup 1 sub fib
        exch 2 sub fib
        add
     } if
  } def

A veremben rekurzív definíciót használnak. A Fibonacci -függvény egy érvet tartalmaz. Először azt tesztelik, hogy 1 vagy 0.

A program minden kulcsfontosságú lépésének felbontása, a verem tükrözése, feltételezve a következőket fib(4) :

                stack: 4
   dup 
                stack: 4 4
   dup 
                stack: 4 4 4
   1 eq 
                stack: 4 4 false
   exch 
                stack: 4 false 4
   0 eq
                stack: 4 false false
   or
                stack: 4 false
   not
                stack: 4 true

Mivel a kifejezés igaznak minősül, a belső eljárás kerül értékelésre.

                stack: 4
   dup 
                stack: 4 4
   1 sub
                stack: 4 3
   fib

(rekurzív hívás itt)

                stack: 4 F(3)
   exch 
                stack: F(3) 4
   2 sub 
                stack: F(3) 2
   fib

(rekurzív hívás itt)

                stack: F(3) F(2)
   add
                stack: F(3)+F(2)

ami a várt eredmény.

Ez az eljárás nem nevezett változókat használ, pusztán a veremet. A /a exch defkonstrukció használatával elnevezett változók hozhatók létre . Például,{/n exch def n n mul}

egy négyzetesítési eljárás nevezett változóval n. Feltételezve, hogy /sq {/n exch def n n mul} defés 3 sqmeghívják, az eljárást sqa következő módon elemzik:

               stack: 3 /n 
   exch 
               stack: /n 3
   def 
               stack: empty (it has been defined)
   n 
               stack: 3
   n 
               stack: 3 3 
   mul
               stack: 9

ami a várt eredmény.

Irányítás és áramlás

Mivel léteznek névtelen eljárások, az áramlásszabályozás természetesen felmerülhet. Az if-then-else utasításhoz három adat szükséges : egy feltétel, egy eljárás, amelyet akkor kell elvégezni, ha a feltétel igaz, és egy, ha a feltétel hamis. Például a PostScriptben

 2 3 gt { (2 is greater than three) = } { (2 is not greater than three) = } ifelse

Közel ekvivalenst végez C -ben:

 if (2 > 3) { printf("2 is greater than three\n"); } else { printf("2 is not greater than three\n"); }

A hurok és más konstrukciók hasonlóak.

A nyelvi modell elemzése

A veremorientált nyelven biztosított egyszerű modell lehetővé teszi a kifejezések és programok egyszerű értelmezését és elméleti értékelését sokkal gyorsabban, mivel nincs szükség szintaktikai elemzésre , csak lexikai elemzésre . Az ilyen programok írásának módja megkönnyíti a gépek értelmezését, ezért a PostScript jól illeszkedik a nyomtatókhoz. A PostScript programok írásának kissé mesterséges módja azonban kezdeti akadályt jelenthet a verem-orientált nyelvek, például a PostScript megértésében.

Bár a beépített és más definíciók felülbírálásával történő árnyékolás nehezítheti a programok hibakeresését, és ennek a funkciónak a felelőtlen használata kiszámíthatatlan viselkedést okozhat, egyes funkciókat azonban jelentősen leegyszerűsíthet. Például a PostScript használatában az showpageoperátort felül lehet írni egy egyénivel, amely egy bizonyos stílust alkalmaz az oldalra, ahelyett, hogy egyéni operátort kellene definiálnia, vagy meg kell ismételnie a stílust.

Lásd még

• A verem alapú programozási nyelvek listája
• Fordított lengyel jelölés
• Vissza-orientált programozás

Hivatkozások