Dlaczego programy używają stosów wywołań, jeśli można wstawiać zagnieżdżone wywołania funkcji?

Dlaczego nie chcesz, aby kompilator pobierał program taki jak ten:

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

i przekonwertować na program taki jak ten:

function c(b) { return b^2 + 5 };

eliminując w ten sposób potrzebę zapamiętania przez komputer adresu zwrotnego c (b)?

Podejrzewam, że zwiększone miejsce na dysku twardym i pamięć RAM potrzebne do przechowywania programu i obsługi jego kompilacji (odpowiednio) są powodem, dla którego używamy stosów wywołań. Czy to jest poprawne?

Nazywa się to „wstawianiem” i wiele kompilatorów robi to jako strategia optymalizacji w przypadkach, w których ma to sens.

W twoim przykładzie ta optymalizacja pozwoliłaby zaoszczędzić zarówno miejsce, jak i czas wykonania. Ale jeśli funkcja została wywołana w wielu miejscach w programie (nierzadko!), Zwiększyłaby rozmiar kodu, więc strategia staje się bardziej wątpliwa. (I oczywiście, jeśli funkcja wywołała się bezpośrednio lub pośrednio, wstawienie byłoby niemożliwe, ponieważ kod stałby się nieskończony).

I oczywiście jest to możliwe tylko dla funkcji „prywatnych”. Funkcje udostępniane zewnętrznym dzwoniącym nie mogą być optymalizowane, przynajmniej w językach z dynamicznym łączeniem.

Pytanie to składa się z dwóch części: Dlaczego w ogóle istnieje wiele funkcji (zamiast zastępować wywołania funkcji ich definicją) i dlaczego implementować te funkcje za pomocą stosów wywołań zamiast statycznego przydzielania danych gdzie indziej?

Pierwszym powodem jest rekurencja. Nie tylko rodzaj „och, zróbmy nowe wywołanie funkcji dla każdego pojedynczego elementu na tej liście”, ale także skromny rodzaj, w którym możesz mieć dwa wywołania funkcji jednocześnie, z wieloma innymi funkcjami pomiędzy nimi. Aby to obsługiwać, musisz umieścić zmienne lokalne na stosie i ogólnie nie można wstawiać funkcji rekurencyjnych.

Jest też problem z bibliotekami: nie wiesz, które funkcje będą wywoływane z miejsca i jak często, więc „biblioteka” nigdy tak naprawdę nie mogłaby zostać skompilowana, tylko wysłana do wszystkich klientów w dogodnym formacie wysokiego poziomu, który następnie byłby wbudowany w aplikację. Oprócz innych problemów z tym, całkowicie tracisz dynamiczne łączenie ze wszystkimi jego zaletami.

Ponadto istnieje wiele powodów, aby nie wstawiać funkcji, nawet jeśli można:

1. To niekoniecznie jest szybsze. Konfigurowanie ramki stosu i burzenie jej może być tuzinem instrukcji pojedynczego cyklu, dla wielu dużych lub zapętlonych funkcji, które nie stanowią nawet 0,1% czasu ich wykonywania.
2. To może być wolniejsze. Powielanie kodu wiąże się z kosztami, np. Zwiększy presję w pamięci podręcznej instrukcji.
3. Niektóre funkcje są bardzo duże i wywoływane z wielu miejsc, dlatego wprowadzenie ich wszędzie zwiększa wartość binarną daleko poza rozsądne możliwości.
4. Kompilatory często mają trudności z bardzo dużymi funkcjami. Wszystko inne jest równe, funkcja rozmiaru 2 * N zajmuje więcej niż 2 * czas T, podczas gdy funkcja rozmiaru N zajmuje czas T.

Stosy pozwalają nam elegancko ominąć ograniczenia narzucone przez skończoną liczbę rejestrów.

Wyobraź sobie, że masz dokładnie 26 globalnych „rejestrów az” (lub nawet posiadasz tylko 7-bajtowych rejestrów układu 8080). I każda funkcja, którą piszesz w tej aplikacji, dzieli tę płaską listę.

Naiwnym początkiem byłoby przydzielenie kilku pierwszych rejestrów do pierwszej funkcji i wiedząc, że zajęło to tylko 3, zacznij od „d” dla drugiej funkcji… Szybko skończysz.

Zamiast tego, jeśli masz metaforyczny taśmę, jak maszyna Turinga, można mieć każda funkcja rozpocząć „wywołać inną funkcję” zapisując wszystkie zmienne to korzystania i forward () taśmę, a następnie funkcja wywoływany może radzić z tak wielu rejestruje się, jak chce. Po zakończeniu procesu odbiorca zwraca kontrolę funkcji nadrzędnej, która wie, gdzie w razie potrzeby zaczepić wyjście odbiorcy, a następnie odtwarza taśmę do tyłu, aby przywrócić jej stan.

Podstawowa ramka wywołania jest właśnie taka i jest tworzona i upuszczana przez znormalizowane sekwencje kodów maszynowych, które kompilator umieszcza wokół przejść z jednej funkcji do drugiej. (Minęło dużo czasu, odkąd musiałem pamiętać moje ramki stosu C, ale możesz przeczytać o różnych sposobach, które spadają z tego, co na X86_calling_conventions .)

(rekurencja jest niesamowita, ale jeśli kiedykolwiek musiałbyś żonglować rejestrami bez stosu, naprawdę doceniłbyś stosy).

Podejrzewam, że zwiększone miejsce na dysku twardym i pamięć RAM potrzebne do przechowywania programu i obsługi jego kompilacji (odpowiednio) są powodem, dla którego używamy stosów wywołań. Czy to jest poprawne?

Chociaż możemy teraz wstawiać więcej, („większa szybkość” jest zawsze dobra; „mniej kb zestawu” oznacza bardzo mało w świecie strumieni wideo) Głównym ograniczeniem jest zdolność kompilatora do spłaszczania określonych typów wzorców kodu.

Na przykład obiekty polimorficzne - jeśli nie znasz jedynego rodzaju obiektu, który zostanie ci przekazany, nie możesz spłaszczyć; musisz spojrzeć na tabelę funkcji obiektu i wywołać ten wskaźnik ... trywialne do wykonania w czasie wykonywania, niemożliwe do wstawienia w czasie kompilacji.

Nowoczesny łańcuch narzędzi może z radością wprowadzać funkcję zdefiniowaną polimorficznie, gdy spłaszczy już tyle osób wywołujących, aby dokładnie wiedzieć , jaki jest smak obiektu obj:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

powyżej kompilator może wybrać statyczne wstawianie, od InlineMe poprzez cokolwiek, co jest w środku act (), ani nie trzeba dotykać żadnych tabel w czasie wykonywania.

Ale jakakolwiek niepewność w jaki smak obiektu pozostawi je jako wezwanie do dyskretnej funkcji, nawet jeśli niektóre inne wywołania tej samej funkcji są wstawiane.

Przypadki, których to podejście nie obsługuje:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

Tam są języki i platformy z ograniczoną lub brak połączeń stosów. Mikroprocesory PIC mają stos sprzętu ograniczony do 2 do 32 pozycji . Stwarza to ograniczenia projektowe.

Rekurencja zakazów COBOL: https://stackoverflow.com/questions/27806812/in-cobol-is-it-possible-to-recursively-call-a-paragraph

Nałożenie zakazu rekurencji oznacza, że ​​możesz reprezentować cały callgraph programu statycznie jako DAG. Twój kompilator może następnie wyemitować jedną kopię funkcji dla każdego miejsca, z którego jest wywoływany, ze stałym skokiem zamiast powrotu. Nie wymaga stosu, po prostu więcej miejsca na program, potencjalnie całkiem dużo dla złożonych systemów. Ale w przypadku małych systemów wbudowanych oznacza to, że możesz zagwarantować, że nie wystąpi przepełnienie stosu w czasie wykonywania, co byłoby złą wiadomością dla reaktora jądrowego / turbiny odrzutowej / sterowania przepustnicą samochodu itp.

Chcesz wstawiania funkcji , a większość kompilatorów ( optymalizujących ) to robi.

Zauważ, że wstawianie wymaga znajomości wywoływanej funkcji (i jest skuteczne tylko wtedy, gdy wywoływana funkcja nie jest zbyt duża), ponieważ koncepcyjnie zastępuje wywołanie przez przepisanie wywoływanej funkcji. Tak więc generalnie nie można wstawić nieznanej funkcji (np. Wskaźnika funkcji - i który zawiera funkcje z dynamicznie połączonych bibliotek współdzielonych - co jest być może widoczne jako metoda wirtualna w niektórych vtable ; ale niektóre kompilatory mogą czasami zoptymalizować techniki dewirtualizacji ). Oczywiście nie zawsze jest możliwe wstawienie funkcji rekurencyjnych (niektóre sprytne kompilatory mogą korzystać z częściowej oceny, a w niektórych przypadkach mogą wstawiać funkcje rekurencyjne).

Zauważ też, że inlinizacja, nawet jeśli jest to łatwo możliwe, nie zawsze jest skuteczna: ty (właściwie twój kompilator) możesz zwiększyć tak duży rozmiar kodu, że pamięci podręczne procesora (lub predyktor gałęzi ) działałyby mniej wydajnie, a to sprawiłoby, że Twój program działał wolniej.

^{Trochę koncentruję się na funkcjonalnym stylu programowania , ponieważ oznaczyłeś swoje pytanie jako takie.}

Zauważ, że nie musisz mieć stosu wywołań (przynajmniej w sensie maszynowym wyrażenia „stos wywołań”). Możesz użyć tylko stosu.

Tak, warto spojrzeć na kontynuacje i przeczytaj więcej o kontynuacji przechodzącą stylu (CPS) i CPS transformacji (intuicyjnie, można użyć kontynuacji zamknięć jak reified „klatek nazywają” alokowanych na stercie, a są one sort-naśladując stos wywołań; potrzebujesz wydajnego śmietnika ).

Andrew Appel napisał książkę Compiling with Continuations, a stary zbiór śmieci papierowych może być szybszy niż przydzielanie stosów . Zobacz także artykuł A. Kennedy'ego (ICFP2007) Kompilacja z kontynuacjami, ciąg dalszy

Polecam także przeczytanie książki Lisp In Small Pieces Queinnec, która zawiera kilka rozdziałów związanych z kontynuacją i kompilacją.

Zauważ też, że niektóre języki (np. Brainfuck ) lub abstrakcyjne maszyny (np. OISC , RAM ) nie mają żadnych funkcji wywoływania, ale wciąż są kompletne Turinga , więc (teoretycznie) nawet nie potrzebujesz żadnego mechanizmu wywoływania funkcji, nawet jeśli jest to niezwykle wygodne. BTW, niektóre stare architektury zestawu instrukcji (np. IBM / 370 ) nie mają nawet stosu wywołań sprzętowych lub instrukcji maszyny wywołującej push (IBM / 370 miał tylko instrukcję maszyny rozgałęzienia i łącza )

W końcu, jeśli cały twój program (w tym wszystkie potrzebne biblioteki) nie ma żadnej rekurencji, możesz zapisać adres zwrotny (i zmienne „lokalne”, które faktycznie stają się statyczne) każdej funkcji w lokalizacjach statycznych. Stare kompilatory Fortran77 zrobiły to na początku lat 80. XX wieku (więc skompilowane programy nie używały wtedy żadnego stosu wywołań).

Inlining (zastępujący wywołania funkcji równoważną funkcjonalnością) działa dobrze jako strategia optymalizacji dla małych prostych funkcji. Narzut wywołania funkcji może być skutecznie zamieniony na niewielką karę w zwiększonym rozmiarze programu (lub w niektórych przypadkach w ogóle bez kary).

Jednak duże funkcje, które z kolei wywołują inne funkcje, mogą doprowadzić do ogromnej eksplozji rozmiaru programu, jeśli wszystko zostanie wstawione.

Głównym celem wywoływanych funkcji jest ułatwienie efektywnego ponownego użycia, nie tylko przez programistę, ale także przez samą maszynę, i obejmuje takie właściwości, jak rozsądna pamięć lub ślad na dysku.

Za to, co jest warte: możesz mieć funkcje wywoływalne bez stosu wywołań. Na przykład: IBM System / 360. Podczas programowania w takich językach, jak FORTRAN na tym sprzęcie, licznik programu (adres zwrotny) zostanie zapisany w małej części pamięci zarezerwowanej tuż przed punktem wejścia funkcji. Pozwala na funkcje wielokrotnego użytku, ale nie pozwala na kod rekurencyjny lub wielowątkowy (próba wywołania rekurencyjnego lub ponownego połączenia spowoduje nadpisanie wcześniej zapisanego adresu zwrotnego).

Jak wyjaśniono w innych odpowiedziach, stosy to dobre rzeczy. Ułatwiają rekurencję i połączenia wielowątkowe. Chociaż każdy algorytm zakodowany w celu użycia rekurencji może być kodowany bez polegania na rekurencji, wynik może być bardziej złożony, trudniejszy do utrzymania i może być mniej wydajny. Nie jestem pewien, czy architektura bez stosu mogłaby w ogóle obsługiwać wielowątkowość.