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, multiply
zamiast 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ć.
Weź talerz 2
i połóż go na stosie, a następnie weź talerz 3
i połóż go na stosie. Następnie weź mul
talerz. To jest instrukcja do wykonania. Następnie zdejmij dwie górne płytki ze stosu, pomnóż ich etykiety ( 2
i 3
) i zapisz wynik ( 6
) na nowej płytce. Wyrzuć dwa stare talerze ( 2
i 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 add
obliczenia 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 fib
poniż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 /x
jak obiekt danych nazwy, który można skojarzyć na przykład z numerem 42
. define
Polecenia jest def
, tak
/x 42 def
kojarzy się z nazwą x
z numerem 42
w słowniku na szczycie stosu. Istnieje różnica między /x
i x
– pierwszy to obiekt danych reprezentujący nazwę, x
oznacza 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 def
konstrukcji. 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} def
i 3 sq
jest wywołany, procedura sq
jest 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 showpage
operator 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ż
- Lista języków programowania opartych na stosie
- Odwrotna notacja polska
- Programowanie zorientowane na zwrot
Bibliografia
- ^ Luerweg, T. (2015). Paradygmaty programowania stosowego. Koncepcje języków programowania – CoPL'15, 33.
- ^ Oren Patashnik, Projektowanie stylów BibTeX (PDF)