Programowanie stosowe - Stack-oriented programming

Programowanie zorientowane na stos to paradygmat programowania, który opiera się na modelu maszyny ze stosem do przekazywania parametrów . Języki stosu zorientowanych działać na jednej lub kilku stosach , z których każda może służyć innemu celowi. Konstrukcje programistyczne w innych językach programowania muszą zostać zmodyfikowane w celu użycia w systemie zorientowanym na stos. Niektóre języki zorientowane na stos działają w notacji postfiksowej lub odwrotnej polskiej . Wszelkie argumenty lub parametry polecenia są podane przed tym poleceniem. Na przykład notacja przyrostkowa zostałaby zapisana 2, 3, multiplyzamiast multiply, 2, 3( przedrostek lub notacja polska ) lub 2 multiply 3( notacja infiksowa ). Języki programowania Forth , RPL , PostScript , język projektowania w stylu BibTeX i wiele języków asemblerowych pasują do tego paradygmatu.


Algorytmy oparte na stosie uwzględniają dane, wykorzystując jedną część danych ze szczytu stosu i zwracając dane z powrotem na stos. Potrzeba operatorów manipulacji stosem, pozwala stosowi manipulować danymi . Aby podkreślić efekt wypowiedzi, używa się komentarza pokazującego szczyt stosu przed i po instrukcji. Jest to znane jako diagram efektu stosu.


Stosy postscriptowe uwzględniają oddzielne stosy dla dodatkowych celów. Uwzględnia zmienne, słowniki, procedury, anatomię niektórych typowych procedur, kontrolę i przepływ. Analiza modelu językowego pozwala na prostą i teoretyczną interpretację wyrażeń i programów.

Algorytmy oparte na stosie

PostScript jest przykładem języka opartego na stosie Postfix. Przykładem wyrażenia w tym języku jest 2 3 mul. Obliczenie wyrażenia wymaga zrozumienia, jak działa orientacja stosu.

Orientację stosu można przedstawić jako następującą analogię przenośnika taśmowego. na końcu przenośnika taśmowego ( wejściowego ) kolejno umieszczane są tabliczki oznaczone 2, 3, i mul. Płytę na końcu przenośnika ( 2) można zabrać, jednak dostęp do innych płyt nie jest możliwy, dopóki płyta na końcu nie zostanie usunięta. Płyty można przechowywać tylko w stosie i można je dodawać lub usuwać tylko z góry stosu, a nie ze środka lub spodu. Można dostarczyć puste płytki (i marker), a płytki można trwale wyrzucić.

Stos człowieka.svg

Weź talerz 2i połóż go na stosie, a następnie weź talerz 3i połóż go na stosie. Następnie weź multalerz. To jest instrukcja do wykonania. Następnie zdejmij dwie górne płytki ze stosu, pomnóż ich etykiety ( 2i 3) i zapisz wynik ( 6) na nowej płytce. Wyrzuć dwa stare talerze ( 2i 3) oraz talerz mul, a nową połóż na stosie. Gdy na przenośniku nie ma już żadnych płyt, wynik obliczeń ( 6) jest wyświetlany na płycie na szczycie stosu.

To bardzo proste obliczenie. Co zrobić, jeśli potrzebne są bardziej złożone obliczenia, takie jak (2 + 3) × 11 + 1? Jeśli najpierw zostanie napisany w formie postfiksowej, czyli , 2 3 add 11 mul 1 addobliczenia można wykonać dokładnie w ten sam sposób i uzyskać poprawny wynik. Etapy obliczeń przedstawiono w poniższej tabeli. Każda kolumna pokazuje element wejściowy (płyta na końcu przenośnika) oraz zawartość stosu po przetworzeniu tego wkładu.

Wejście 2 3 Dodaj 11 mul 1 Dodaj
Stos 2 3
2
5 11
5
55 1
55
56

Po przetworzeniu wszystkich danych wejściowych stos zawiera 56, który jest odpowiedzią.

Z tego można wywnioskować, co następuje: język programowania oparty na stosie ma tylko jeden sposób obsługi danych, poprzez pobranie jednego fragmentu danych ze szczytu stosu, określanego jako pop ping, i umieszczenie danych z powrotem na stosie, określanego jako wypychanie . Każde wyrażenie, które można napisać konwencjonalnie lub w innym języku programowania, może być napisane w postaci przyrostka (lub przedrostka), a zatem może być interpretowane przez język zorientowany na stos.

Manipulacja stosem

Ponieważ stos jest kluczowym środkiem do manipulowania danymi w języku zorientowanym na stos, takie języki często zapewniają pewnego rodzaju operatory manipulacji stosem. Powszechnie przewidziane są dup, aby zduplikować element na szczycie stosu exch(lub swap), aby wymienić elementy na szczycie stosu (pierwszy staje się drugim, a drugi staje się pierwszym), roll, cykliczne permutowanie elementów w stosie lub na części stosu, pop( lub drop), aby odrzucić element na szczycie stosu (wypychanie jest niejawne) i inne. Stają się one kluczowe w badaniu procedur.

Diagramy efektu stosu

Jako pomoc w zrozumieniu wpływu instrukcji, stosuje się krótki komentarz pokazujący szczyt stosu przed i po instrukcji. W przypadku wielu elementów górna część stosu znajduje się najbardziej po prawej stronie. Ten zapis jest powszechnie używany w języku Forth, gdzie komentarze są ujęte w nawiasy.

( before -- after )

Na przykład opisano podstawowe operatory stosu 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 fibponiższa funkcja jest opisana:

fib  ( n -- n' )

Jest to odpowiednik warunków wstępnych i warunków końcowych w logice Hoare'a . Oba komentarze mogą być również przywoływane jako asercje , niekoniecznie w kontekście języków opartych na stosie.

Stosy PostScript

PostScript i niektóre inne języki stosu mają inne oddzielne stosy do innych celów.

Zmienne i słowniki

Ocena różnych wyrażeń została już przeanalizowana. Implementacja zmiennych jest ważna dla każdego języka programowania, ale w przypadku języków zorientowanych na stos ma szczególne znaczenie, ponieważ istnieje tylko jeden sposób interakcji z danymi.

Sposób, w jaki zmienne są realizowane w językach zorientowanych stosu takich jak PostScript zazwyczaj wiąże się osobny, specjalizującą stos, który przechowuje słowniki z par klucz-wartość . Aby utworzyć zmienną, najpierw należy utworzyć klucz (nazwę zmiennej), z którym następnie powiązana jest wartość. W PostScript obiekt danych nazwy jest poprzedzony znakiem /, podobnie /xjak obiekt danych nazwy, który można skojarzyć na przykład z numerem 42. definePolecenia jest def, tak

/x 42 def

kojarzy się z nazwą xz numerem 42w słowniku na szczycie stosu. Istnieje różnica między /xi x– pierwszy to obiekt danych reprezentujący nazwę, xoznacza to, co jest zdefiniowane w /x.

Procedury

Procedura w języku programowania opartym na stosie jest traktowana jako obiekt danych sam w sobie. W PostScript procedury są oznaczone pomiędzy {i }.

Na przykład w składni PostScript

{ dup mul }

reprezentuje anonimową procedurę powielania tego, co znajduje się na szczycie stosu, a następnie mnożenia wyniku — procedurę do kwadratu.

Ponieważ procedury są traktowane jako proste obiekty danych, można zdefiniować nazwy z procedurami. Kiedy są pobierane, są wykonywane bezpośrednio.

Słowniki umożliwiają kontrolowanie zakresu, a także przechowywanie definicji.

Ponieważ obiekty danych są przechowywane w słowniku najwyższego poziomu, w naturalny sposób pojawia się nieoczekiwana możliwość: podczas wyszukiwania definicji ze słownika sprawdzany jest słownik najwyższego poziomu, a następnie następny i tak dalej. Jeśli zostanie zdefiniowana procedura, która ma taką samą nazwę jak inna już zdefiniowana w innym słowniku, zostanie wywołana procedura lokalna.

Anatomia niektórych typowych procedur

Procedury często wymagają argumentów. Są one obsługiwane przez procedurę w bardzo specyficzny sposób, odmienny od innych języków programowania.

Aby zbadać program liczb Fibonacciego w PostScript:

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

Na stosie używana jest definicja rekurencyjna. Funkcja liczby Fibonacciego przyjmuje jeden argument. Najpierw jest testowany pod kątem wartości 1 lub 0.

Rozkładanie każdego z kluczowych kroków programu, odzwierciedlających stos, przy założeniu obliczenia 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

Ponieważ wyrażenie ma wartość true, oceniana jest procedura wewnętrzna.

                stack: 4
   dup 
                stack: 4 4
   1 sub
                stack: 4 3
   fib
(wywołanie rekurencyjne tutaj)
                stack: 4 F(3)
   exch 
                stack: F(3) 4
   2 sub 
                stack: F(3) 2
   fib
(wywołanie rekurencyjne tutaj)
                stack: F(3) F(2)
   add
                stack: F(3)+F(2)

co jest oczekiwanym rezultatem.

Ta procedura nie używa nazwanych zmiennych, tylko stosu. Nazwane zmienne można tworzyć za pomocą /a exch defkonstrukcji. Na przykład,{/n exch def n n mul}

to procedura do kwadratu z nazwaną zmienną n. Zakładając, że /sq {/n exch def n n mul} defi 3 sqjest wywołany, procedura sqjest analizowana w następujący sposób:

               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 jest oczekiwanym rezultatem.

Kontrola i przepływ

Ponieważ istnieją procedury anonimowe, kontrola przepływu może powstać w sposób naturalny. W przypadku instrukcji „ jeżeli-to-inaczej” wymagane są trzy elementy danych : warunek, procedura, którą należy wykonać, jeśli warunek jest prawdziwy, i jedna, którą należy wykonać, jeśli warunek jest fałszywy. Na przykład w PostScript

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

wykonuje bliski odpowiednik w C:

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

Zapętlanie i inne konstrukcje są podobne.

Analiza modelu językowego

Prosty model dostarczony w języku zorientowanym na stos pozwala na prostą interpretację wyrażeń i programów i znacznie szybszą teoretyczną ocenę, ponieważ nie trzeba przeprowadzać analizy składni , a jedynie analizę leksykalną . Sposób, w jaki takie programy są pisane, ułatwia ich interpretację przez maszyny, dlatego PostScript dobrze nadaje się do użytku na drukarkach. Jednak nieco sztuczny sposób pisania programów PostScript może stanowić początkową barierę w zrozumieniu języków zorientowanych na stos, takich jak PostScript.

Chociaż możliwość tworzenia cienia przez nadpisanie wbudowanych i innych definicji może utrudnić debugowanie programów, a nieodpowiedzialne użycie tej funkcji może spowodować nieprzewidywalne zachowanie, może znacznie uprościć niektóre funkcje. Na przykład w przypadku PostScriptu showpageoperator może zostać zastąpiony niestandardowym, który stosuje określony styl do strony, zamiast definiowania operatora niestandardowego lub powtarzania kodu w celu wygenerowania stylu.

Zobacz też

Bibliografia

  1. ^ Luerweg, T. (2015). Paradygmaty programowania stosowego. Koncepcje języków programowania – CoPL'15, 33.
  2. ^ Oren Patashnik, Projektowanie stylów BibTeX (PDF)