Czy stosy są jedynym rozsądnym sposobem na uporządkowanie programów?

Większość architektur, które widziałem, polegają na stosie wywołań do zapisywania / przywracania kontekstu przed wywołaniami funkcji. Jest to tak powszechny paradygmat, że operacje push i pop są wbudowane w większość procesorów. Czy istnieją systemy działające bez stosu? Jeśli tak, to w jaki sposób działają i do czego służą?

(Nieco) popularną alternatywą dla stosu wywołań są kontynuacje .

Na przykład maszyna wirtualna Parrot jest oparta na kontynuacji. Jest całkowicie bez stosu: dane są przechowywane w rejestrach (takich jak Dalvik lub LuaVM, Parrot jest oparty na rejestrach), a przepływ sterowania jest reprezentowany przez kontynuacje (w przeciwieństwie do Dalvik lub LuaVM, które mają stos wywołań).

Inną popularną strukturą danych, używaną zwykle przez maszyny wirtualne Smalltalk i Lisp, jest stos spaghetti, który przypomina swoistą sieć stosów.

Jak zauważył @rwong , styl przekazywania kontynuacji jest alternatywą dla stosu wywołań. Programy napisane w stylu przekazującym kontynuację (lub przekształcone w ten sposób) nigdy nie zwracają, więc nie ma potrzeby stosowania stosu.

Odpowiadając na twoje pytanie z innej perspektywy: możliwe jest posiadanie stosu wywołań bez osobnego stosu, poprzez przydzielenie ramek stosu na stosie. Robią to niektóre implementacje Lisp i Scheme.

W dawnych czasach procesory nie miały instrukcji stosu, a języki programowania nie obsługiwały rekurencji. Z czasem coraz więcej języków decyduje się na obsługę rekurencji, a sprzęt podąża za pakietem z możliwością alokacji ramek stosu. To wsparcie różniło się znacznie na przestrzeni lat w zależności od procesorów. Niektóre procesory przyjęły rejestry ramki stosu i / lub rejestry wskaźnika stosu; niektóre przyjęte instrukcje, które doprowadziłyby do alokacji ramek stosu w jednej instrukcji.

W miarę postępów procesorów z buforami jednopoziomowymi, a następnie wielopoziomowymi, jedną z kluczowych zalet stosu jest lokalizacja pamięci podręcznej. Wierzchołek stosu prawie zawsze znajduje się w pamięci podręcznej. Ilekroć możesz zrobić coś, co ma duży współczynnik trafień w pamięci podręcznej, jesteś na dobrej drodze dzięki nowoczesnym procesorom. Pamięć podręczna zastosowana do stosu oznacza, że ​​lokalne zmienne, parametry itp. Prawie zawsze znajdują się w pamięci podręcznej i cieszą się najwyższym poziomem wydajności.

Krótko mówiąc, wykorzystanie stosu ewoluowało zarówno w sprzęcie, jak i oprogramowaniu. Istnieją inne modele (na przykład wypróbowano obliczenia przepływu danych przez dłuższy czas), ale lokalizacja stosu sprawia, że ​​działa naprawdę dobrze. Co więcej, kod proceduralny jest dokładnie tym, czego oczekują procesory, dla wydajności: jedna instrukcja mówi mu, co robić po drugiej. Gdy instrukcje nie są uporządkowane liniowo, procesor co najmniej ogromnie zwalnia, ponieważ nie ustaliliśmy, jak uzyskać dostęp losowy tak szybko, jak dostęp sekwencyjny. (Przy okazji, istnieją podobne problemy na każdym poziomie pamięci, od pamięci podręcznej, do pamięci głównej, na dysku ...)

Pomiędzy zademonstrowaną wydajnością instrukcji sekwencyjnego dostępu a korzystnym zachowaniem buforowania stosu wywołań, mamy, przynajmniej obecnie, zwycięski model wydajności.

(Możemy również wrzucić zmienność struktur danych do prac ...)

Nie oznacza to, że inne modele programowania nie mogą działać, zwłaszcza gdy można je przełożyć na instrukcje sekwencyjne i model stosu wywołań współczesnego sprzętu. Istnieje jednak wyraźna zaleta dla modeli obsługujących miejsce, w którym znajduje się sprzęt. Jednak rzeczy nie zawsze pozostają takie same, więc mogliśmy zobaczyć zmiany w przyszłości, ponieważ różne technologie pamięci i tranzystorów pozwalają na większą równoległość. Zawsze jest to żart pomiędzy językami programowania a możliwościami sprzętowymi, więc zobaczymy!

TL; DR

• Stos wywołań jako mechanizm wywoływania funkcji:
  1. Zwykle jest symulowany sprzętowo, ale nie ma fundamentalnego znaczenia dla konstrukcji sprzętu
  2. Ma fundamentalne znaczenie dla programowania imperatywnego
  3. Nie ma fundamentalnego znaczenia dla programowania funkcjonalnego
• Stos jako abstrakcja „ostatnie wejście, pierwsze wyjście” (LIFO) ma fundamentalne znaczenie dla informatyki, algorytmów, a nawet niektórych domen nietechnicznych.
• Niektóre przykłady organizacji programu, które nie używają stosów połączeń:
  • Styl przekazywania kontynuacji (CPS)
  • Maszyna stanowa - gigantyczna pętla, z wszystko wstawionymi. (Podobno zainspirowany architekturą oprogramowania układowego Saab Gripen i przypisany komunikacji Henry'ego Spencera i odtworzony przez Johna Carmacka.) ^{(Uwaga 1)}
  • Architektura przepływu danych - sieć aktorów połączonych kolejkami (FIFO). Kolejki są czasami nazywane kanałami.

Reszta tej odpowiedzi jest przypadkowym zbiorem myśli i anegdot, a zatem nieco chaotycznym.

Opisany przez ciebie stos (jako mechanizm wywoływania funkcji) jest specyficzny dla programowania imperatywnego.

Poniżej programowania imperatywnego znajdziesz kod maszynowy. Kod maszynowy może emulować stos wywołań, wykonując niewielką sekwencję instrukcji.

Poniżej kodu maszynowego znajduje się sprzęt odpowiedzialny za uruchamianie oprogramowania. Podczas gdy nowoczesny mikroprocesor jest zbyt skomplikowany, aby go tu opisać, można sobie wyobrazić, że istnieje bardzo prosta konstrukcja, która jest powolna, ale wciąż jest w stanie wykonać ten sam kod maszynowy. Taki prosty projekt wykorzysta podstawowe elementy logiki cyfrowej:

1. Logika kombinacyjna, tj. Połączenie bramek logicznych (i, lub nie, ...) Należy zauważyć, że „logika kombinacyjna” wyklucza sprzężenia zwrotne.
2. Pamięć, tj. Przerzutniki, zatrzaski, rejestry, SRAM, DRAM itp.
3. Maszyna stanu, która składa się z logiki kombinacyjnej i pewnej pamięci, wystarczającej do implementacji „kontrolera” zarządzającego resztą sprzętu.

Poniższe dyskusje zawierały wiele przykładów alternatywnych sposobów konstruowania programów imperatywnych.

• http://number-none.com/blow/john_carmack_on_inlined_code.html
• https://news.ycombinator.com/item?id=8374345

Struktura takiego programu będzie wyglądać następująco:

void main(void)
{
    do
    {
        // validate inputs for task 1
        // execute task 1, inlined, 
        // must complete in a deterministically short amount of time
        // and limited to a statically allocated amount of memory
        // ...
        // validate inputs for task 2
        // execute task 2, inlined
        // ...
        // validate inputs for task N
        // execute task N, inlined
    }
    while (true);
    // if this line is reached, tell the programmers to prepare
    // themselves to appear before an accident investigation board.
    return 0; 
}

Ten styl byłby odpowiedni dla mikrokontrolerów, tj. Dla tych, którzy postrzegają oprogramowanie jako uzupełnienie funkcji sprzętu.

Nie, niekoniecznie.

Czytaj stary papier Appela Odśmiecanie może być szybsze niż alokacja stosu . Wykorzystuje styl przekazywania kontynuacji i pokazuje implementację bez stosu.

Zauważ też, że stare architektury komputerów (np. IBM / 360 ) nie miały żadnego rejestru stosu sprzętu. Ale system operacyjny i kompilator zarezerwowały rejestr wskaźnika stosu zgodnie z konwencją (związaną z konwencjami wywoływania ), aby mogły mieć stos wywołań programowych .

Zasadniczo cały kompilator i optymalizator programu C może wykryć przypadek (dość powszechny w systemach osadzonych), w którym wykres wywołań jest statycznie znany i nie ma rekurencji (ani wskaźników funkcji). W takim systemie każda funkcja mogła zachować swój adres zwrotny w stałej, statycznej lokalizacji (i tak działał Fortran77 w komputerach z 1970 roku).

Obecnie procesory mają również stosy wywołań (oraz instrukcje maszynowe wywoływania i zwracania) rozpoznające pamięć podręczną procesora .

Jak dotąd masz kilka dobrych odpowiedzi; dam ci niepraktyczny, ale bardzo edukacyjny przykład, w jaki sposób możesz zaprojektować język bez pojęcia stosów lub „kontroli przepływu”. Oto program, który określa silnie:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)

Umieszczamy ten program w ciągu i oceniamy go przez podstawienie tekstowe. Więc kiedy oceniamyf(3) , przeprowadzamy wyszukiwanie i zastępujemy 3 dla i, w ten sposób:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)

Wspaniały. Teraz wykonujemy kolejne podstawienie tekstu: widzimy, że warunek „if” jest fałszywy i zastępujemy kolejny ciąg znaków, tworząc program:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)

Teraz wykonujemy kolejny ciąg zastępujący wszystkie podwyrażenia obejmujące stałe:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)

I widzicie, jak to idzie; Nie będę dalej pracował nad tym. Moglibyśmy nadal wykonywać serię zamian łańcuchów, aż do tego dojdziemy let x = 6i skończymy.

Stosu tradycyjnie używamy do zmiennych lokalnych i informacji o kontynuacji; pamiętaj, że stos nie mówi, skąd przyszedłeś, ale wskazuje, dokąd zmierzasz z tą wartością zwrotną w ręku.

W modelu programowania łańcuchowego podstawiania łańcuchów nie ma „zmiennych lokalnych” na stosie; parametry formalne są zastępowane ich wartościami, gdy funkcja jest zastosowana do jej argumentu, a nie umieszczana w tabeli odnośników na stosie. I nie ma „gdzieś dalej”, ponieważ ewaluacja programu polega po prostu na zastosowaniu prostych reguł do podstawiania łańcuchów w celu stworzenia innego, ale równoważnego programu.

Teraz, oczywiście, faktycznie zastępowanie ciągów prawdopodobnie nie jest dobrym rozwiązaniem. Jednak języki programowania, które obsługują „rozumowanie równe” (takie jak Haskell) logicznie korzystają z tej techniki.

Od czasu publikacji przez Parnas w 1972 roku On kryteriów, które należy stosować przy rozkładaniu systemów na moduły zasadnie przyjęto, że ukrywanie informacji w oprogramowaniu jest dobrą rzeczą. Wynika to z długiej debaty w latach 60. na temat rozkładu strukturalnego i programowania modułowego.

Modułowość

Niezbędny wynik relacji czarnej skrzynki między modułami zaimplementowanymi przez różne grupy w dowolnym systemie wielowątkowym wymaga mechanizmu umożliwiającego ponowne wprowadzenie i środków do śledzenia dynamicznego grafu połączeń systemu. Kontrolowany przepływ wykonania musi przechodzić zarówno do, jak i do wielu modułów.

Dynamiczne określanie zakresu

Gdy tylko zakres leksykalny jest niewystarczający, aby śledzić zachowanie dynamiczne, wymagane jest pewne prowadzenie księgowości w czasie wykonywania w celu śledzenia różnicy.

Biorąc pod uwagę, że każdy wątek (z definicji) ma tylko jeden bieżący wskaźnik instrukcji, stos LIFO jest odpowiedni do śledzenia każdego wywołania.

Wyjątki

Tak więc, podczas gdy model kontynuacji nie utrzymuje struktury danych wprost dla stosu, nadal istnieje zagnieżdżone wywołanie modułów, które należy gdzieś utrzymywać!

Nawet języki deklaratywne zachowują historię oceny lub odwrotnie spłaszczają plan wykonania ze względu na wydajność i utrzymują postęp w inny sposób.

Struktura nieskończonej pętli identyfikowana przez rwong jest powszechna w aplikacjach o wysokiej niezawodności ze statycznym planowaniem, które uniemożliwia wiele popularnych struktur programowania, ale wymaga, aby całą aplikację traktować jako białą skrzynkę bez znaczącego ukrywania informacji.

Wiele współbieżnych nieskończonych pętli nie wymaga żadnej struktury do przechowywania adresów zwrotnych, ponieważ nie wywołują one funkcji, co sprawia, że ​​pytanie jest dyskusyjne. Jeśli komunikują się przy użyciu wspólnych zmiennych, mogą one łatwo przekształcić się w starsze analogiczne adresy zwrotne w stylu Fortran.

Wszystkie stare komputery mainframe (IBM System / 360) w ogóle nie miały pojęcia o stosie. Na przykład na 260 parametry zostały zbudowane w ustalonym miejscu w pamięci, a kiedy wywołano podprogram, wywołano go R1wskazując na blok parametrów i R14zawierający adres zwrotny. Wywoływana procedura, jeśli chce wywołać inny podprogram, musiałaby zapisaćR14 w znanym miejscu przed wykonaniem tego połączenia.

Jest to o wiele bardziej niezawodne niż stos, ponieważ wszystko można przechowywać w ustalonych lokalizacjach pamięci ustalonych w czasie kompilacji i można w 100% zagwarantować, że procesy nigdy nie zabraknie stosu. W dzisiejszych czasach nie ma żadnego z „Przydziel 1 MB i trzymajcie kciuki”.

Rekurencyjne wywołania podprogramów były dozwolone w PL / I przez określenie słowa kluczowego RECURSIVE. Oznaczały one, że pamięć używana przez podprogram była dynamicznie przydzielana, a nie statycznie przydzielana. Ale rekurencyjne połączenia były wtedy tak rzadkie, jak teraz.

Operacja bez stosu sprawia, że ​​masowe wielowątkowość jest znacznie łatwiejsze, dlatego często podejmowane są próby uczynienia współczesnych języków pozbawionymi stali. Nie ma na przykład żadnego powodu, dla którego kompilator C ++ nie może być modyfikowany przez back-end, aby używać dynamicznie alokowanej pamięci zamiast stosów.