Jakie są alternatywy dla używania stosu do przedstawienia semantyki wywołań funkcji?

Wszyscy wiemy i uwielbiamy, że wywołania funkcji są zwykle realizowane przy użyciu stosu; są ramki, adresy zwrotne, parametry, cała partia.

Jednak stos jest szczegółem implementacji: konwencje wywoływania mogą robić różne rzeczy (np. Rejestry szybkiego połączenia x86 używają (niektóre) rejestrów, MIPS i obserwatorzy używają okien rejestrów itd.), A optymalizacje mogą robić nawet inne rzeczy (wstawianie, pomijanie wskaźnika ramki, optymalizacja wywołania ogona ..).

Jasne, obecność wygodnej instrukcji stosu na wielu maszynach (maszyny wirtualne, takie jak JVM i CLR, ale także rzeczywiste maszyny, takie jak x86 z ich PUSH / POP itp.) Sprawiają, że wygodnie jest używać go do wywołań funkcji, ale w niektórych przypadkach jest to możliwe aby zaprogramować w taki sposób, że stos wywołań nie jest potrzebny (myślę tutaj o stylu przekazywania kontynuacji lub aktorach w systemie przekazywania komunikatów)

Zacząłem się zastanawiać: czy można zaimplementować semantykę wywołań funkcji bez stosu, lub lepiej, używając innej struktury danych (być może kolejki lub mapy asocjacyjnej?)
Oczywiście rozumiem, że stos jest bardzo wygodne (istnieje powód, dla którego jest wszechobecne), ale ostatnio wpadłem na implementację, która mnie zastanawiała ...

Czy ktoś z was wie, czy kiedykolwiek dokonano tego w jakimkolwiek języku / maszynie / maszynie wirtualnej, a jeśli tak, jakie są uderzające różnice i wady?

EDYCJA: Mam przeczucie, że różne podejścia do obliczeń mogą wykorzystywać różne struktury danych. Na przykład rachunek lambda nie jest oparty na stosie (idea zastosowania funkcji jest przechwytywana przez redukcje), ale szukałem prawdziwego języka / maszyny / przykładu. Dlatego pytam ...

W zależności od języka może nie być konieczne użycie stosu wywołań. Stosy połączeń są konieczne tylko w językach, które umożliwiają rekurencję lub wzajemną rekurencję. Jeśli język nie zezwala na rekurencję, w danym momencie może być aktywne tylko jedno wywołanie dowolnej procedury, a zmienne lokalne dla tej procedury mogą być przypisane statycznie. Takie języki muszą uwzględniać zmiany kontekstu, obsługę przerwań, ale nadal nie wymaga stosu.

Przykłady języków niewymagających stosów połączeń znajdują się w FORTRAN IV (i wcześniejszych) oraz we wczesnych wersjach języka COBOL.

Odwołaj się do Control Data 6600 (i wcześniejszych maszyn Control Data), aby zobaczyć przykład bardzo udanego wczesnego superkomputera, który nie zapewniał bezpośredniego wsparcia sprzętowego dla stosów połączeń. Zobacz PDP-8 jako przykład bardzo udanego wczesnego minikomputera, który nie obsługiwał stosów połączeń.

O ile mi wiadomo, maszyny stosowe Burroughs B5000 były pierwszymi maszynami ze sprzętowymi stosami wywołań. Maszyny B5000 zostały zaprojektowane od podstaw do pracy z ALGOL, co wymagało rekurencji. Mieli także jedną z pierwszych architektur opartych na deskryptorach, która położyła podwaliny pod architektury możliwości.

O ile mi wiadomo, to PDP-6 (który wyrósł na DEC-10) spopularyzował sprzęt stosu wywołań, kiedy społeczność hakerów w MIT dostarczyła jeden i odkryła, że ​​operacja PUSHJ (Push Return Address and Jump) pozwoliło zmniejszyć liczbę operacji drukowania dziesiętnego z 50 instrukcji do 10.

Najbardziej podstawowa semantyka wywołań funkcji w języku, który umożliwia rekurencję, wymaga zdolności, które ładnie pasują do stosu. Jeśli to wszystko, czego potrzebujesz, podstawowy stos jest dobrym, prostym dopasowaniem. Jeśli potrzebujesz więcej, struktura danych musi zrobić więcej.

Najlepszym przykładem potrzeby, z którą się spotkałem, jest „kontynuacja”, możliwość zawieszenia obliczeń w środku, zapisania ich jako zamrożonej bańki stanu i wystrzelenia go ponownie później, być może wiele razy. Kontynuacja stała się popularna w dialekcie schematu LISP, jako sposób na wdrożenie, między innymi, wyjść błędów. Kontynuacja wymaga możliwości wykonania migawki bieżącego środowiska wykonawczego i odtworzenia go później, a stos jest nieco niewygodny.

„Struktura i interpretacja programów komputerowych” Abelsona i Sussmana szczegółowo opisuje kontynuacje.

Nie jest możliwe wdrożenie semantyki wywołań funkcji bez użycia jakiegoś stosu. Można grać tylko w gry słowne (np. Użyj innej nazwy, np. „Bufor powrotu FILO”).

Można użyć czegoś, co nie implementuje semantyki wywołań funkcji (np. Styl przekazywania kontynuacji, aktorzy), a następnie zbudować na niej semantykę wywołań funkcji; ale oznacza to dodanie pewnego rodzaju struktury danych, aby śledzić, gdzie kontrola jest przekazywana, gdy funkcja powraca, a ta struktura danych byłaby rodzajem stosu (lub stosu o innej nazwie / opisie).

Wyobraź sobie, że masz wiele funkcji, które mogą się nawzajem wywoływać. W czasie wykonywania każda funkcja musi wiedzieć, do którego miejsca powrócić, gdy funkcja wyjdzie. Jeśli firstdzwonisz second, masz:

second returns to somewhere in first

Następnie, jeśli masz secondpołączenia third:

third returns to somewhere in second
second returns to somewhere in first

Następnie, jeśli masz thirdpołączenia fourth:

fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first

Gdy wywoływana jest każda funkcja, gdzieś trzeba przechowywać więcej informacji „gdzie zwrócić”.

Jeśli funkcja zwraca, wówczas używana jest informacja „gdzie zwrócić” i nie jest już potrzebna. Na przykład, jeśli fourthwróci gdzieś, thirdwówczas ilość informacji „gdzie wrócić do” wyniesie:

third returns to somewhere in second
second returns to somewhere in first

Gruntownie; „semantyka wywołania funkcji” oznacza, że:

• musisz mieć informację „gdzie zwrócić”
• ilość informacji rośnie wraz z wywoływaniem funkcji i jest zmniejszana, gdy funkcje powracają
• pierwsza przechowywana informacja „gdzie zwrócić” będzie ostatnią odrzuconą informacją „gdzie zwrócić”

Opisuje bufor lub stos FILO / LIFO.

Jeśli spróbujesz użyć typu drzewa, to każdy węzeł w drzewie nigdy nie będzie miał więcej niż jednego dziecka. Uwaga: węzeł z wieloma potomkami może się zdarzyć tylko wtedy, gdy funkcja wywołuje 2 lub więcej funkcji jednocześnie , co wymaga pewnego rodzaju współbieżności (np. Wątków, fork () itp.) I nie byłby to „semantyka wywołania funkcji”. Jeśli każdy węzeł w drzewie nigdy nie będzie miał więcej niż jednego dziecka; wtedy to „drzewo” byłoby używane tylko jako bufor FILO / LIFO lub stos; a ponieważ jest używany tylko jako bufor FILO / LIFO lub stos, można śmiało twierdzić, że „drzewo” to stos (a jedyną różnicą są gry słowne i / lub szczegóły implementacji).

To samo dotyczy każdej innej struktury danych, która mogłaby być prawdopodobnie zastosowana do zaimplementowania „semantyki wywołania funkcji” - będzie używana jako stos (a jedyną różnicą są gry słowne i / lub szczegóły implementacji); chyba że łamie „semantykę wywołania funkcji”. Uwaga: gdybym mógł, podałbym przykłady innych struktur danych, ale nie mogę wymyślić żadnej innej struktury, która byłaby nieco prawdopodobna.

Oczywiście sposób implementacji stosu jest szczegółem implementacji. Może to być obszar pamięci (gdzie śledzisz „aktualny stos”), może to być jakaś połączona lista (gdzie śledzisz „aktualny wpis na liście”) lub może być zaimplementowany w niektórych inny sposób. Nie ma również znaczenia, czy sprzęt ma wbudowane wsparcie, czy nie.

Uwaga: Jeśli w danym momencie może być aktywne tylko jedno wywołanie dowolnej procedury; możesz statycznie przydzielić miejsce na informacje „gdzie wrócić”. To wciąż stos (np. Połączona lista statycznie przydzielonych wpisów używanych w sposób FILO / LIFO).

Zauważ również, że niektóre rzeczy nie są zgodne z „semantyką wywołań funkcji”. Te rzeczy obejmują „potencjalnie bardzo różną semantykę” (np. Przekazywanie kontynuacji, model aktora); a także obejmuje popularne rozszerzenia „semantyki wywołań funkcji”, takie jak współbieżność (wątki, włókna itp.), setjmp/ longjmp, obsługa wyjątków itp.

Zabawny język konkatenatywny XY używa do wykonania kolejki połączeń i stosu danych.

Każdy krok obliczeniowy polega po prostu na wypróbowaniu następnego słowa, które ma zostać wykonane, aw przypadku wbudowanych poleceń, zasileniu jego funkcji wewnętrznej stosem danych i kolejką wywołań jako argumentami lub za pomocą userdefs, wypychając słowa tworzące je na początek kolejki.

Więc jeśli mamy funkcję podwajania górnego elementu:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Następnie funkcje komponowania +i dupnastępujące podpisy typu stosu / kolejki:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

I paradoksalnie doublebędzie wyglądać tak:

double [X Y] -> [X dup^+^Y]

W pewnym sensie XY nie ma stosów.