idea podprogramu została wypracowana po tym, jak maszyny obliczeniowe istniały już od jakiegoś czasu.Arytmetyczne i warunkowe instrukcje skoków zostały zaplanowane z wyprzedzeniem i zmieniły się stosunkowo niewiele, ale specjalne instrukcje używane do wywołań procedur zmieniły się znacznie na przestrzeni lat.Najwcześniejsze Komputery i mikroprocesory, takie jak Manchester Baby i RCA 1802, nie miały jednej instrukcji podprogramu.Podprogramy mogły być implementowane, ale wymagały od programistów użycia sekwencji wywołań—serii instrukcji-w każdym miejscu wywołania.

podprogramy zostały wdrożone w Z4 Konrada Zuse w 1945 roku.

w 1945 roku Alan M. Turing użył określeń „bury” i „unbury” jako sposobu wywoływania i powrotu z podprogramów.

w styczniu 1947 roku John Mauchly przedstawił uwagi ogólne Na „A Symposium of Large Scale Digital Calculating Machinery” pod wspólnym patronatem Uniwersytetu Harvarda i Bureau of Ordnance, United States Navy. Tutaj omawia operacje szeregowe i równoległe

…struktura maszyny nie musi być skomplikowana ani trochę. Ponieważ wszystkie cechy logiczne niezbędne do tej procedury są dostępne, możliwe jest opracowanie instrukcji kodowania do umieszczania podprogramów w pamięci w miejscach znanych maszynie i w taki sposób, aby można było je łatwo uruchomić.

innymi słowy, można wyznaczyć podprogram A jako dzielenie, podprogram B jako mnożenie złożone, a podprogram C jako ocenę standardowego błędu ciągu liczb, itd.poprzez listę podprogramów potrzebnych do konkretnego problemu. … Wszystkie te podprogramy będą następnie przechowywane w maszynie, a wszystko, co trzeba zrobić, to zrobić krótkie odniesienie do nich przez liczbę, jak są one wskazane w kodowaniu.

Kay McNulty ściśle współpracowała z Johnem Mauchly ’ m w zespole ENIAC i opracowała pomysł podprogramów dla komputera ENIAC, który programowała podczas II Wojny Światowej. ona i inni programiści ENIAC używali podprogramów do obliczania trajektorii pocisków.

Goldstine i von Neumann napisali artykuł z 16 sierpnia 1948 roku omawiający użycie podprogramów.

niektóre bardzo wczesne Komputery i mikroprocesory, takie jak IBM 1620, Intel 4004 i Intel 8008 oraz mikrokontrolery PIC, mają wywołanie podprogramu pojedynczej instrukcji, które wykorzystuje dedykowany stos sprzętowy do przechowywania adresów zwrotnych-taki sprzęt obsługuje tylko kilka poziomów zagnieżdżania podprogramów, ale może obsługiwać podprogramy rekurencyjne. UNIVAC i, PDP-1 i IBM 1130—maszyny sprzed połowy lat 60-tych—takie jak UNIVAC i, PDP-1 i IBM 1130-zwykle używają konwencji wywołania, która zapisywała licznik instrukcji w pierwszej lokalizacji pamięci wywołanego podprogramu. Pozwala to na dowolnie Głębokie poziomy zagnieżdżania podprogramów, ale nie obsługuje podprogramów rekurencyjnych. PDP-11 (1970) jest jednym z pierwszych komputerów z instrukcją wywołania podprogramu pchającego stosy; funkcja ta obsługuje zarówno arbitralnie Głębokie zagnieżdżanie podprogramów, jak i obsługuje podprogramy rekurencyjne.

wsparcie Językowedytuj

we wczesnych assemblerach wsparcie podprogramów było ograniczone. Podprogramy nie były wyraźnie oddzielone od siebie ani od głównego programu, a w rzeczywistości kod źródłowy podprogramu mógł być przeplatany z kodem innych podprogramów. Niektóre asemblery oferują predefiniowane makra do generowania sekwencji wywołania i powrotu. Do lat 60. assemblery miały zwykle znacznie bardziej wyrafinowane wsparcie zarówno dla wbudowanych, jak i osobno montowanych podprogramów, które można było ze sobą połączyć.

Biblioteki podprogramów

nawet przy tym uciążliwym podejściu podprogramy okazały się bardzo przydatne. Po pierwsze, pozwolili na użycie tego samego kodu w wielu różnych programach. Co więcej, pamięć była bardzo rzadkim zasobem na wczesnych komputerach, a podprogramy pozwalały na znaczne oszczędności w wielkości programów.

wiele wczesnych komputerów ładowało instrukcje programu do pamięci z dziurkowanej taśmy papierowej. Każdy podprogram może być następnie dostarczony przez oddzielny kawałek taśmy, załadowany lub połączony przed lub po głównym programie (lub „mainline”); i ta sama taśma podprogramu może być następnie używana przez wiele różnych programów. Podobne podejście zastosowano w komputerach, które używały kart perforowanych do ich głównego wejścia. Nazwa biblioteka podprogramu pierwotnie oznaczała bibliotekę, w dosłownym znaczeniu, która przechowywała indeksowane zbiory taśm lub talii kart do zbiorowego użytku.

Return by indirect jumpEdit

aby usunąć potrzebę samoczynnego modyfikowania kodu, projektanci komputerów ostatecznie dostarczyli pośrednią instrukcję skoku, której operand, zamiast być samym adresem zwrotnym, był lokalizacją zmiennej lub rejestru procesora zawierającego adres zwrotny.

na tych komputerach, zamiast modyfikować skok powrotny podprogramu, program wywołujący przechowywałby adres powrotny w zmiennej, tak aby po zakończeniu podprogramu wykonał pośredni skok, który skierowałby wykonanie do lokalizacji określonej przez predefiniowaną zmienną.

skok do podprogramuedytuj

kolejnym postępem był skok do podprogramu, który łączył zapisanie adresu zwrotnego ze skokiem wywołania, co znacznie minimalizowało narzut.

w IBM System/360, na przykład, instrukcje gałęzi BAL lub BALR, przeznaczone do wywoływania procedur, zapisywałyby adres zwrotny w rejestrze procesora określonym w instrukcji, według rejestru konwencyjnego 14. Aby powrócić, podprogram musiał jedynie wykonać pośrednią instrukcję branch (BR) za pośrednictwem tego rejestru. Jeśli podprogram potrzebował tego rejestru do jakiegoś innego celu (np. wywołania innego podprogramu), zapisywałby zawartość rejestru do prywatnej lokalizacji pamięci lub stosu rejestrów.

w systemach takich jak HP 2100, Instrukcja JSB wykonywałaby podobne zadanie, z wyjątkiem tego, że adres zwrotny był przechowywany w lokalizacji pamięci, która była celem gałęzi. Wykonanie procedury rozpocznie się w następnej lokalizacji pamięci. W języku asemblacji HP 2100 można by napisać, na przykład

 ... JSB MYSUB (Calls subroutine MYSUB.) BB ... (Will return here after MYSUB is done.)

, aby wywołać podprogram o nazwie MYSUB z głównego programu. Podprogram byłby zakodowany jako

 MYSUB NOP (Storage for MYSUB's return address.) AA ... (Start of MYSUB's body.) ... JMP MYSUB,I (Returns to the calling program.)

Instrukcja JSB umieściła adres następnej instrukcji (mianowicie, BB) w lokalizacji określonej jako jej argument (mianowicie, MYSUB), a następnie rozgałęziła się do następnej lokalizacji (mianowicie, AA = MYSUB + 1). Podprogram może następnie powrócić do głównego programu, wykonując pośredni skok JMP MYSUB, I który rozgałęził się do lokalizacji przechowywanej w lokalizacji MYSUB.Kompilatory

Dla Fortran i innych języków mogą łatwo korzystać z tych instrukcji, gdy są dostępne. To podejście obsługiwało wiele poziomów wywołań; jednak ponieważ adres zwrotny, parametry i wartości zwracane podprogramu zostały przypisane do stałych lokalizacji pamięci, nie pozwalało na rekurencyjne wywołania.

nawiasem mówiąc, podobną metodę zastosował Lotus 1-2-3 na początku lat 80., aby odkryć zależności przeliczania w arkuszu kalkulacyjnym. Mianowicie, lokalizacja została zarezerwowana w każdej komórce do przechowywania adresu zwrotnego. Ponieważ odwołania okrągłe nie są dozwolone dla naturalnej kolejności przeliczania, pozwala to na chodzenie po drzewie bez rezerwowania miejsca na stos w pamięci, co było bardzo ograniczone na małych komputerach, takich jak IBM PC.

Call stackEdit

większość współczesnych implementacji wywołań podprogramów używa stosu wywołań, specjalnego przypadku struktury danych stosu, do implementacji wywołań podprogramów i zwrotów. Każde wywołanie procedury tworzy nowy wpis, zwany ramką stosu, u góry stosu; gdy procedura powróci, ramka stosu zostanie usunięta ze stosu, a jej przestrzeń może być wykorzystana do innych wywołań procedur. Każda ramka stosu zawiera prywatne dane odpowiedniego wywołania, które zazwyczaj zawierają parametry procedury i zmienne wewnętrzne oraz adres zwrotny.

Sekwencja wywołania może być zaimplementowana przez sekwencję zwykłych instrukcji (podejście wciąż używane w architekturze reduced instruction set computing (RISC) I very long instruction word (VLIW)), ale wiele tradycyjnych maszyn zaprojektowanych od końca lat 60.

stos wywołań jest zwykle zaimplementowany jako przylegający obszar pamięci. Jest to dowolny wybór projektu, czy dno stosu jest najniższym lub najwyższym adresem w tym obszarze, tak że stos może rosnąć do przodu lub do tyłu w pamięci; jednak wiele architektur wybrało tę ostatnią.

niektóre projekty, w szczególności niektóre implementacje Forth, używały dwóch oddzielnych stosów, jeden głównie dla informacji sterujących (takich jak adresy zwrotne i liczniki pętli), a drugi dla danych. Pierwszy z nich był lub działał jak stos wywołań i był tylko pośrednio Dostępny dla programisty poprzez inne konstrukcje językowe, podczas gdy drugi był bardziej bezpośrednio dostępny.

Kiedy po raz pierwszy wprowadzono wywołania procedur oparte na stosie, ważną motywacją było oszczędzanie cennej pamięci. Dzięki temu schematowi kompilator nie musi rezerwować osobnej przestrzeni w pamięci dla prywatnych danych (parametrów, adresu zwrotnego i zmiennych lokalnych) każdej procedury. W każdej chwili stos zawiera tylko prywatne dane wywołań, które są aktualnie aktywne (mianowicie, które zostały wywołane, ale jeszcze nie wróciły). Ze względu na sposób, w jaki programy były zwykle składane z bibliotek, nie było (i nadal jest) rzadkością znaleźć programy zawierające tysiące podprogramów, z których tylko garstka jest aktywna w danym momencie. W przypadku takich programów mechanizm stosu wywołań może zaoszczędzić znaczne ilości pamięci. Mechanizm stosu wywołań może być postrzegany jako Najwcześniejsza i najprostsza metoda automatycznego zarządzania pamięcią.

jednak inną zaletą metody call stack jest to, że umożliwia ona rekurencyjne wywołania podprogramów, ponieważ każde zagnieżdżone wywołanie tej samej procedury otrzymuje osobną instancję swoich prywatnych danych.

Delayed stacking Edit

jedną z wad mechanizmu stosu wywołań jest zwiększony koszt wywołania procedury i jej odpowiadający zwrot. Dodatkowy koszt obejmuje zwiększanie i zmniejszanie wskaźnika stosu (a w niektórych architekturach sprawdzanie przepełnienia stosu) oraz dostęp do zmiennych lokalnych i parametrów za pomocą adresów względnych klatek, zamiast adresów bezwzględnych. Koszt może być realizowany w zwiększonym czasie wykonania lub zwiększonej złożoności procesora lub obu tych czynników.

Ten nadrzut jest najbardziej oczywisty i budzący zastrzeżenia w procedurach liścia lub funkcjach liścia, które zwracają się bez wywoływania procedur.Aby zmniejszyć to obciążenie, wiele współczesnych kompilatorów próbuje opóźnić użycie stosu wywołań, dopóki nie będzie to naprawdę potrzebne. Na przykład wywołanie procedury P może przechowywać adres zwrotny i parametry wywołanej procedury w niektórych rejestrach procesora i przekazywać kontrolę do ciała procedury za pomocą prostego skoku. Jeśli procedura P powróci bez żadnego innego wywołania, stos wywołania nie jest w ogóle używany. Jeśli P musi wywołać inną procedurę Q, użyje stosu wywołań do zapisania zawartości rejestrów (takich jak adres zwrotny), które będą potrzebne po powrocie Q.