Stack -orientert programmering - Stack-oriented programming

Stack-orientert programmering , er et programmeringsparadigme som er avhengig av en stack- maskinmodell for å overføre parametere . Stabelorienterte språk opererer på en eller flere stabler , som hver kan tjene et annet formål. Programmeringskonstruksjoner på andre programmeringsspråk må modifiseres for bruk i et stabelorientert system. Noen stabelorienterte språk fungerer i postfiks eller omvendt polsk notasjon . Eventuelle argumenter eller parametere for en kommando angis før den kommandoen. For eksempel vil postfiks notasjon bli skrevet i 2, 3, multiplystedet for multiply, 2, 3( prefiks eller polsk notasjon ), eller 2 multiply 3( infix notasjon ). Programmeringsspråkene Forth , RPL , PostScript , BibTeX -designspråk og mange samlingsspråk passer til dette paradigmet.

Stabelbaserte algoritmer vurderer data ved å bruke ett stykke data fra toppen av stakken, og returnere data tilbake på toppen av stabelen. Behovet for stabelmanipuleringsoperatører, tillater stabelen å manipulere data . For å understreke effekten av en uttalelse, brukes en kommentar som viser toppen av stabelen før og etter uttalelsen. Dette er kjent som stabeleffektdiagrammet.

Postscript stabler vurdere egne stabler for flere formål. Dette tar for seg variabler, ordbøker, prosedyrer, anatomi av noen typiske prosedyrer, kontroll og flyt. Analysen av språkmodellen gjør at uttrykk og programmer kan tolkes enkelt og teoretisk.

Stabelbaserte algoritmer

PostScript er et eksempel på et postfix stack-basert språk. Et uttrykkseksempel på dette språket er 2 3 mul. Å beregne uttrykket innebærer å forstå hvordan stabelorientering fungerer.

Stabelorientering kan presenteres som følgende transportbånd-analogi. ved enden av en transportbåndet ( inngang ), plater merket 2, 3og mulplasseres i rekkefølge. Platen i enden av transportøren ( 2) kan tas, men andre plater kan ikke nås før platen i enden er fjernet. Platene kan bare lagres i en bunke, og kan bare legges til eller fjernes fra toppen av bunken, ikke fra midten eller bunnen. Blanke plater (og en markør) kan leveres og plater kan kastes permanent.

Ta tallerkenen 2og legg den på bunken, ta deretter tallerkenen 3og legg den på bunken. Ta deretter multallerkenen. Dette er en instruksjon om å utføre. Ta deretter de to øverste platene av bunken, multipliser etikettene ( 2og 3), og skriv resultatet ( 6) på en ny tallerken. Kast de to gamle platene ( 2og 3) og tallerkenen mul, og legg den nye platen på bunken. Uten flere plater igjen på transportøren, vises resultatet av beregningen ( 6) på platen på toppen av bunken.

Dette er en veldig enkel beregning. Hva om en mer kompleks beregning er nødvendig, for eksempel (2 + 3) × 11 + 1? Hvis den først skrives i postrettingsform, det vil si 2 3 add 11 mul 1 add, kan beregningen utføres på nøyaktig samme måte og oppnå riktig resultat. Trinnene i beregningen er vist i tabellen nedenfor. Hver kolonne viser et inngangselement (platen i enden av transportøren) og innholdet i bunken etter behandling av inngangen.

Etter å ha behandlet alle inngangene, inneholder bunken 56, som er svaret.

Fra dette kan følgende konkluderes: Et stabelbasert programmeringsspråk har bare én måte å håndtere data på, ved å ta ett stykke data fra toppen av stabelen, betegne pop- ping og sette data tilbake på toppen av stabelen, kalt push- ing. Ethvert uttrykk som kan skrives konvensjonelt eller på et annet programmeringsspråk, kan skrives i postfiks (eller prefiks) -form og kan dermed tolkes av et stabelorientert språk.

Stack manipulasjon

Siden stabelen er det viktigste middelet for å manipulere data på et stabelorientert språk, gir slike språk ofte en slags stablingsoperatører. Vanligvis er det dupå duplisere elementet oppå stakken, exch(eller swap), å bytte elementer på toppen av bunken (den første blir andre og den andre blir første) roll, å syklisk permutere elementer i bunken eller på en del av bunken, pop( eller drop), for å kaste elementet på toppen av stakken (push er implisitt) og andre. Disse blir nøkkelen i å studere prosedyrer.

Stabel effektdiagrammer

Som et hjelpemiddel for å forstå effekten av utsagn, brukes en kort kommentar som viser toppen av stabelen før og etter uttalelsen. Toppen av stabelen er lengst til høyre hvis det er flere elementer. Denne notasjonen brukes ofte på Forth -språket, der kommentarer er omsluttet i parentes.

( before -- after )

For eksempel er de grunnleggende Forth stack -operatørene beskrevet:

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

Og fibfunksjonen nedenfor er beskrevet:

fib  ( n -- n' )

Det tilsvarer forutsetninger og etterforhold i Hoare -logikk . Begge kommentarene kan også refereres til som påstander , tenkt ikke nødvendigvis i sammenheng med Stack-baserte språk.

PostScript -stabler

PostScript og noen andre stack -språk har andre separate stabler for andre formål.

Variabler og ordbøker

Evalueringen av forskjellige uttrykk er allerede analysert. Implementeringen av variabler er viktig for ethvert programmeringsspråk, men for stabelorienterte språk er det spesielt bekymringsfullt, da det bare er en måte å samhandle med data.

Måten variabler implementeres på stabelorienterte språk som PostScript, innebærer vanligvis en egen, spesialisert stabel som inneholder ordbøker for nøkkelverdipar . For å opprette en variabel må en nøkkel (variabelnavnet) først opprettes, som en verdi deretter blir knyttet til. I PostScript er et navnedataobjekt foran et a /, det samme /xer et navnedataobjekt som kan knyttes til for eksempel nummeret 42. Den definekommandoen er def, så

/x 42 def

assosierer seg med navnet xmed nummeret 42i ordboken på toppen av bunken. Det er en forskjell mellom /xog x- førstnevnte er et dataobjekt som representerer et navn, xstår for det som er definert under /x.

Prosedyrer

En prosedyre i et stabelbasert programmeringsspråk behandles som et dataobjekt i seg selv. I PostScript er prosedyrer angitt mellom {og }.

For eksempel i PostScript -syntaks,

{ dup mul }

representerer en anonym prosedyre for å duplisere det som er på toppen av bunken og deretter multiplisere resultatet - en kvadreringsprosedyre.

Siden prosedyrer behandles som enkle dataobjekter, kan navn med prosedyrer defineres. Når de blir hentet, blir de henrettet direkte.

Ordbøker gir et middel til å kontrollere omfang, samt lagring av definisjoner.

Siden dataobjekter er lagret i ordlisten som ligger øverst, oppstår en uventet evne naturlig: Når du ser etter en definisjon fra en ordbok, sjekkes den øverste ordlisten, deretter den neste og så videre. Hvis det er definert en prosedyre som har samme navn som en annen som allerede er definert i en annen ordbok, vil den lokale bli kalt.

Anatomi av noen typiske prosedyrer

Prosedyrer tar ofte argumenter. De håndteres av prosedyren på en veldig spesifikk måte, forskjellig fra andre programmeringsspråk.

For å undersøke et Fibonacci -nummerprogram i PostScript:

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

En rekursiv definisjon brukes på stabelen. Fibonacci -tallfunksjonen tar ett argument. Først testes den for å være 1 eller 0.

Dekomponere hvert av programmets viktigste trinn, reflektere stabelen, forutsatt beregning av 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

Siden uttrykket evaluerer til sant, evalueres den indre prosedyren.

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

(rekursiv samtale her)

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

(rekursiv samtale her)

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

som er det forventede resultatet.

Denne prosedyren bruker ikke navngitte variabler, bare stabelen. Navngitte variabler kan opprettes ved å bruke /a exch defkonstruksjonen. For eksempel,{/n exch def n n mul}

er en kvadreringsprosedyre med en navngitt variabel n. Forutsatt at /sq {/n exch def n n mul} defog 3 sqblir kalt, sqanalyseres prosedyren på følgende måte:

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

som er det forventede resultatet.

Kontroll og flyt

Siden det finnes anonyme prosedyrer, kan flytkontroll oppstå naturlig. Tre data er nødvendig for en if-then-else- setning: en betingelse, en prosedyre som skal utføres hvis betingelsen er sann, og en som skal gjøres hvis betingelsen er usann. For eksempel i PostScript,

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

utfører nær ekvivalent i C:

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

Looping og andre konstruksjoner er like.

Analyse av språkmodellen

Den enkle modellen som tilbys i et stabelorientert språk, gjør at uttrykk og programmer kan tolkes enkelt og teoretisk mye raskere, siden det ikke er nødvendig med syntaksanalyse, bare leksikalsk analyse . Måten slike programmer skrives på, gjør det lettere å tolke det av maskiner, og derfor passer PostScript godt for skrivere for bruk. Den litt kunstige måten å skrive PostScript-programmer på kan imidlertid danne en første barriere for å forstå stabelorienterte språk som PostScript.

Selv om muligheten til å skygge ved å overstyre innebygd og andre definisjoner kan gjøre programmer vanskelig å feilsøke, og uansvarlig bruk av denne funksjonen kan forårsake uforutsigbar oppførsel, kan det forenkle noen funksjoner sterkt. For eksempel i PostScript showpage-bruk kan operatøren overstyres med en egendefinert stil som bruker en bestemt stil på siden, i stedet for å måtte definere en tilpasset operatør eller å gjenta kode for å generere stilen.

Se også

• Liste over stabelbaserte programmeringsspråk
• Omvendt polsk notasjon
• Returrettet programmering

Referanser