Stack -Oriented Programming - Stack-oriented programming

Programování orientované na zásobník je paradigma programování, které při předávání parametrů závisí na modelu zásobníku . Jazyky orientované na zásobník fungují na jednom nebo více svazcích , z nichž každý může sloužit jinému účelu. Programovací konstrukce v jiných programovacích jazycích je třeba upravit pro použití v systému orientovaném na zásobník. Některé jazyky orientované na zásobník fungují v postfixové nebo reverzní polské notaci . Před tímto příkazem jsou uvedeny všechny argumenty nebo parametry příkazu. Například zápis postfixu bude napsán místo ( předpona nebo polská notace ) nebo ( infixová notace ). Tomuto paradigmatu vyhovují programovací jazyky Forth , RPL , PostScript , BibTeX a mnoho dalších montážních jazyků . 2, 3, multiplymultiply, 2, 32 multiply 3

Algoritmy založené na zásobníku berou v úvahu data využitím jednoho kusu dat z vrcholu zásobníku a vrácením dat zpět na zásobník. Potřeba operátorů manipulace se zásobníkem umožňuje zásobníku manipulovat s daty . Pro zdůraznění účinku příkazu se používá komentář zobrazující horní část zásobníku před a za příkazem. Toto je známé jako diagram efektu zásobníku.

Postskriptové zásobníky zvažují oddělené zásobníky pro další účely. To zvažuje proměnné, slovníky, postupy, anatomii některých typických postupů, ovládání a tok. Analýza jazykového modelu umožňuje, aby výrazy a programy byly interpretovány jednoduše a teoreticky.

Algoritmy založené na zásobníku

PostScript je příkladem jazyka založeného na postfixovém zásobníku. Příklad výrazu v tomto jazyce je 2 3 mul. Výpočet výrazu zahrnuje pochopení toho, jak funguje orientace zásobníku.

Orientace zásobníku může být prezentována jako následující analogie dopravního pásu. na konci dopravníkového pásu (dále vstup ), označený desky 2, 3a muljsou umístěny za sebou. Deska na konci dopravníku ( 2) může být odebrána, ale ostatní desky nejsou přístupné, dokud není deska na konci odstraněna. Desky mohou být uloženy pouze ve stohu a lze je přidávat nebo odebírat pouze z hromádky, nikoli ze středu nebo zespodu. Lze dodat prázdné desky (a značku) a desky lze trvale vyřadit.

Vezměte talíř 2a položte jej na hromádku, poté vezměte talíř 3a položte jej na stoh. Dále vezměte multalíř. Toto je pokyn k provedení. Poté vyjměte horní dva talíře ze stohu, znásobte jejich štítky ( 2a 3) a výsledek ( 6) napište na nový talíř. Zlikvidujte dva staré talíře ( 2a 3) a talíř mula vložte nový talíř na hromádku. Když na dopravníku nezůstanou žádné další desky, výsledek výpočtu ( 6) se zobrazí na desce na vrcholu stohu.

Jedná se o velmi jednoduchý výpočet. Co když je zapotřebí složitější výpočet, například (2 + 3) × 11 + 1? Pokud je poprvé napsán ve formě postfixu, to znamená, 2 3 add 11 mul 1 addže výpočet lze provést přesně stejným způsobem a dosáhnout správného výsledku. Kroky výpočtu jsou uvedeny v tabulce níže. Každý sloupec zobrazuje vstupní prvek (deska na konci dopravníku) a obsah stohu po zpracování tohoto vstupu.

Po zpracování všech vstupů zásobník obsahuje 56, což je odpověď.

Z toho lze vyvodit následující: programovací jazyk založený na zásobníku má pouze jeden způsob, jak zpracovávat data, a to tak, že vezme jeden kus dat z vrcholu zásobníku, nazvaný pop ping, a vrátí data zpět na zásobník, nazvaný push ing. Jakýkoli výraz, který může být napsán konvenčně nebo v jiném programovacím jazyce, může být napsán ve formě postfixu (nebo prefixu), a proto může být interpretován jazykem orientovaným na zásobník.

Manipulace se zásobníkem

Protože zásobník je klíčovým prostředkem pro manipulaci s daty v jazyce orientovaném na zásobník, takové jazyky často poskytují nějaký druh operátorů manipulace se zásobníkem. Běžně jsou dupk dispozici duplikace prvku na vrcholu zásobníku exch(nebo swap), výměna prvků na vrcholu zásobníku (první se stává druhým a druhým prvním), rollcyklické permutování prvků v zásobníku nebo na části zásobníku, pop( nebo drop), zahodit prvek na vrchol zásobníku (push je implicitní) a další. Ty se stávají klíčovými při studiu postupů.

Diagramy efektu zásobníku

Jako pomůcka k pochopení účinku příkazu slouží krátký komentář zobrazující horní část zásobníku před a za příkazem. Pokud existuje více položek, horní část zásobníku je úplně vpravo. Tento zápis se běžně používá v jazyce Forth, kde jsou komentáře uzavřeny v závorkách.

( before -- after )

Například jsou popsány základní operátory zásobníku Forth:

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

A fibníže je popsána funkce:

fib  ( n -- n' )

Je ekvivalentní předpokladům a postkondicím v Hoare logice . Oba komentáře lze také označit jako tvrzení , která nemusí být nutně v kontextu jazyků založených na zásobníku.

Zásobníky PostScriptu

PostScript a některé další jazyky zásobníku mají jiné oddělené zásobníky pro jiné účely.

Proměnné a slovníky

Hodnocení různých výrazů již bylo analyzováno. Implementace proměnných je důležitá pro jakýkoli programovací jazyk, ale pro jazyky orientované na zásobník je to obzvláště důležité, protože existuje pouze jeden způsob interakce s daty.

Způsob, jakým proměnné jsou implementovány v zásobníku orientované jazyky, jako je PostScript obvykle zahrnuje samostatnou specializovanou svazek, který slouží jako slovníky z dvojic klíč-hodnota . Chcete -li vytvořit proměnnou, musíte nejprve vytvořit klíč (název proměnné), se kterým je potom spojena hodnota. V PostScriptu má datový objekt názvu předponu a /, stejně /xjako datový objekt názvu, který může být spojen například s číslem 42. definePříkaz def, takže

/x 42 def

spojuje jméno xs číslem 42ve slovníku na vrcholu zásobníku. Existuje rozdíl mezi /xa x- první je datový objekt představující jméno, což xznamená, co je definováno pod /x.

Postupy

Procedura v programovacím jazyce založeném na zásobníku je považována za datový objekt. V PostScriptu jsou procedury označeny mezi {a }.

Například v syntaxi PostScriptu

{ dup mul }

představuje anonymní postup pro duplikování toho, co je na vrcholu zásobníku, a poté znásobení výsledku - procedura kvadratury.

Protože jsou procedury považovány za jednoduché datové objekty, lze definovat názvy s procedurami. Když jsou načteny, jsou provedeny přímo.

Slovníky poskytují prostředky pro kontrolu rozsahu, stejně jako ukládání definic.

Protože jsou datové objekty uloženy v nejvyšším slovníku, vzniká přirozeně neočekávaná schopnost: při vyhledávání definice ze slovníku se kontroluje nejvyšší slovník, potom další atd. Pokud je definována procedura, která má stejný název jako jiný již definovaný v jiném slovníku, bude vyvolán místní.

Anatomie některých typických postupů

Procedury často vyžadují argumenty. Procedura je zpracovává velmi specifickým způsobem, odlišným od ostatních programovacích jazyků.

Prozkoumání Fibonacciho číselného programu v PostScriptu:

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

V zásobníku se používá rekurzivní definice. Fibonacciho číselná funkce má jeden argument. Nejprve se testuje, zda má hodnotu 1 nebo 0.

Dekompozice každého z klíčových kroků programu, odrážející zásobník, za předpokladu výpočtu 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

Protože je výraz vyhodnocen jako true, je vyhodnocen vnitřní postup.

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

(rekurzivní hovor zde)

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

(rekurzivní hovor zde)

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

což je očekávaný výsledek.

Tento postup nepoužívá pojmenované proměnné, čistě zásobník. Pojmenované proměnné lze vytvořit pomocí /a exch defkonstrukce. Například,{/n exch def n n mul}

je procedura kvadratury s pojmenovanou proměnnou n. Za předpokladu, že /sq {/n exch def n n mul} defa 3 sqje volán, je postup sqanalyzován následujícím způsobem:

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

což je očekávaný výsledek.

Řízení a tok

Protože existují anonymní postupy, řízení toku může vzniknout přirozeně. Pro příkaz if-then-else jsou vyžadovány tři údaje : podmínka, postup, který je třeba provést, pokud je podmínka pravdivá, a jeden, který je třeba provést, pokud je podmínka nepravdivá. Například v PostScriptu

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

provádí téměř ekvivalent v C:

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

Opakování a jiné konstrukce jsou podobné.

Analýza jazykového modelu

Jednoduchý model poskytovaný v jazyce orientovaném na stack umožňuje výrazům a programům interpretovat je jednoduše a teoreticky vyhodnotit mnohem rychleji, protože není třeba provádět žádnou syntaktickou analýzu , pouze lexikální analýzu . Způsob, jakým jsou tyto programy psány, usnadňuje jejich interpretace stroji, a proto PostScript dobře vyhovuje tiskařům pro jeho použití. Mírně umělý způsob psaní postskriptových programů však může tvořit počáteční bariéru pro porozumění jazykům orientovaným na stack, jako je PostScript.

Přestože schopnost stínovat přepsáním vestavěných a jiných definic může programy obtížně ladit a nezodpovědné používání této funkce může způsobit nepředvídatelné chování, může některé funkce výrazně zjednodušit. Například při použití PostScriptu showpagelze operátor přepsat vlastním, který na stránku aplikuje určitý styl, místo aby musel definovat vlastní operátor nebo opakovat kód pro generování stylu.

Viz také

• Seznam programovacích jazyků založených na zásobníku
• Reverzní polská notace
• Návratově orientované programování

Reference