Podprogram
myšlenka podprogramu byla zpracována poté, co výpočetní stroje již nějakou dobu existovaly.Aritmetické a podmíněné skokové pokyny byly plánovány předem a změnily se relativně málo, ale speciální pokyny používané pro volání procedur se v průběhu let značně změnily.Nejstarší počítače a mikroprocesory, jako je Manchester Baby a RCA 1802, neměly jedinou instrukci pro volání podprogramu.Podprogramy by mohly být implementovány, ale vyžadovaly, aby programátoři používali sekvenci volání—řadu instrukcí-na každém místě volání.
podprogramy byly implementovány v Z4 Konrada Zuse v roce 1945.
v roce 1945 použil Alan M. Turing termíny „bury“ a „unbury“ jako prostředek volání a návratu z podprogramu.
V lednu 1947 John Mauchly prezentovány obecné poznámky na Sympozium ve Velkém Měřítku Digitální Počítací Stroje’under společného sponzorství Harvard University a Bureau of Ordnance, Námořnictvo Spojených Států. Zde pojednává o sériové a paralelní operaci, která naznačuje
…struktura stroje nemusí být složité jeden bit. To je možné, protože všechny logické vlastnosti nezbytné k tomuto postupu jsou k dispozici, vyvíjet kódování instrukce pro uvedení podprogramů v paměti na místech známo, že zařízení, a to takovým způsobem, že mohou snadno být nazýván do užívání.
V jinými slovy, lze jmenovat podprogram jako divize a podprogram B jako komplexní násobení a podprogram C jako hodnocení standardní chyba sekvence čísel, a tak dále v seznamu podprogramy potřebné pro konkrétní problém. … Všechny tyto podprogramy budou poté uloženy v počítači a vše, co musíte udělat, je na ně stručně odkazovat podle čísla, jak jsou uvedeny v kódování.
Kay McNulty měl úzce spolupracoval s John Mauchly na ENIAC týmu a rozvíjet nápad na podprogramy pro počítač ENIAC byla programování během druhé Světové Války. Ona a další ENIAC programátorů používá podprogramy pro výpočet pomoci raketové trajektorie.
Goldstine a von Neumann napsali článek ze dne 16. srpna 1948 o použití podprogramu.
Některé velmi brzy, počítače a mikroprocesory, jako je například IBM 1620, Intel 4004 a Intel 8008, a mikrokontroléry PIC, mají jeden-instrukce podprogramu call, která používá specializovaný hardware zásobníku pro uložení návratové adresy—takový hardware podporuje pouze několik úrovní vnoření podprogramu, ale může podporovat rekurzivní podprogramy. Stroje před střední-1960—jako UNIVAC I, PDP-1, a IBM 1130—obvykle používají konvence volání, které uložené instrukce čítače v prvním paměti volaný podprogram. To umožňuje libovolně hluboké úrovně vnoření podprogramu, ale nepodporuje rekurzivní podprogramy. PDP-11 (1970) je jedním z prvních počítačů s stack-tlačí podprogram volat instrukce; tato funkce podporuje i libovolně hluboké vnoření podprogramu a podporuje také rekurzivní podprogramy.
Language supportEdit
ve velmi raných assemblerech byla podpora podprogramu omezená. Podprogramy nebyly explicitně odděleny od sebe nebo od hlavního programu a zdrojový kód podprogramu mohl být skutečně rozptýlen s kódem jiných podprogramů. Některé assemblery by nabízely předdefinovaná makra pro generování sekvencí volání a návratu. V 1960ech měli montéři obvykle mnohem sofistikovanější podporu jak pro inline, tak pro Samostatně sestavené podprogramy, které by mohly být spojeny dohromady.
podprogram librariesEdit
i při tomto těžkopádném přístupu se podprogramy ukázaly jako velmi užitečné. Jednak umožnili použití stejného kódu v mnoha různých programech. Kromě toho byla paměť na raných počítačích velmi vzácným zdrojem a podprogramy umožnily významné úspory ve velikosti programů.
mnoho časných počítačů načetlo programové pokyny do paměti z děrované papírové pásky. Každý podprogram může pak být poskytována samostatný kus pásky, naložené nebo sestříhané před nebo po hlavním programu (nebo „mainline“); a tentýž podprogram pásku by pak mohly být použity mnoha různými programy. Podobný přístup aplikován v počítačích, které používají děrované karty pro jejich hlavní vstup. Název podprogramu knihovna původně znamenalo knihovna, v doslovném smyslu, který držel indexované sbírky pásky nebo karty paluby pro kolektivní použití.
odstranit potřebu pro self-modifikovat kód, počítač návrháři nakonec za předpokladu, nepřímý skok instrukce, jejichž operand, místo toho, aby zpáteční adresu sám, byla místo proměnné nebo procesor rejstřík obsahující zpáteční adresu.
Na těchto počítačích, místo úpravě podprogramu návrat skok, volání, program by uložit návratovou adresu v proměnné tak, že když podprogram úspěšně absolvováno, to by spustit nepřímý skok, který by přímé provedení k umístění dané předdefinované proměnné.
Skok na subroutineEdit
Další pokrok byl skok do podprogramu instrukce, které v kombinaci uložení návratové adresy se volá skok, čímž se minimalizuje režii výrazně.
V IBM System/360, například, pobočka pokyny BAL nebo BALR, určený pro řízení volání, by uložit návratovou adresu v procesoru rejstříku uvedeno v návodu, podle konvence rejstříku 14. Chcete-li se vrátit, podprogram musel provést pouze nepřímou instrukci větve (BR) prostřednictvím tohoto registru. Pokud podprogram potřeboval tento registr pro nějaký jiný účel (například volání jiného podprogramu), uložil by obsah registru do soukromého paměťového umístění nebo do zásobníku registru.
V systémech, jako například HP 2100, JSB instrukce by se provést podobný úkol, kromě toho, že zpáteční adresa byla uložena v paměti místo, které bylo cílem oboru. Provedení procedury by skutečně začalo na dalším paměťovém místě. V jazyce sestavy HP 2100 by se například zapisovalo
... JSB MYSUB (Calls subroutine MYSUB.) BB ... (Will return here after MYSUB is done.)
, aby se z hlavního programu zavolal podprogram s názvem MYSUB. Podprogram by být kódovány jako
MYSUB NOP (Storage for MYSUB's return address.) AA ... (Start of MYSUB's body.) ... JMP MYSUB,I (Returns to the calling program.)
JSB instrukce umístěna adresa PŘÍŠTÍ instrukce (konkrétně, BB) do umístění zadaného jako jeho operand (tedy, MYSUB), a pak se rozdělil na DALŠÍ místo po tom (tedy AA = MYSUB + 1). Podprogram se pak mohl vrátit do hlavního programu provedením nepřímého skoku JMP MYSUB, který jsem rozvětvil na místo uložené v místě MYSUB.
překladače pro Fortran a další jazyky by mohly snadno využít těchto pokynů, pokud jsou k dispozici. Tento přístup podporoval více úrovní volání; nicméně, protože návratová adresa, parametry, a návratové hodnoty podprogramu byly přiřazeny pevné paměti, neumožňoval rekurzivní volání.
mimochodem, podobná metoda byla použita Lotus 1-2-3, v časných 1980, objevit přepočet závislostí v tabulce. Konkrétně bylo v každé buňce vyhrazeno místo pro uložení zpáteční adresy. Od cyklické odkazy nejsou povoleny pro přírodní přepočtu pořadí, tím stromem chodit bez rezervace místa pro zásobník v paměti, který byl velmi omezený na malé počítače, jako je IBM PC.
Volání stackEdit
Většina moderních implementací podprogram volat použít zásobník volání, zvláštní případ zásobníku datové struktury, provádět volání podprogramů a návraty. Každé volání procedury vytvoří v horní části zásobníku novou položku, nazývanou rám zásobníku; když se procedura vrátí, její rámec zásobníku je odstraněn ze zásobníku a jeho prostor může být použit pro další volání procedur. Každý rámec zásobníku obsahuje soukromá data odpovídajícího volání, která obvykle zahrnují parametry procedury a vnitřní proměnné a návratovou adresu.
volání sekvence může být provedena posloupnost obyčejných instrukcí (přístup stále používá ve snížené instruction set computing (RISC) a velmi dlouho, instruction word (VLIW) architektury), ale mnoho tradičních stroje určené od pozdní 1960 zahrnovaly zvláštní pokyny pro tento účel.
zásobník volání je obvykle implementován jako souvislá oblast paměti. Je to libovolná volba návrhu, zda je spodní část zásobníku nejnižší nebo nejvyšší adresou v této oblasti, takže zásobník může růst dopředu nebo dozadu v paměti; mnoho architektur si však vybralo druhou.
Některé návrhy, zejména některé Dále implementace, používá dva samostatné komíny, jeden hlavně pro kontrolu informací (jako zpáteční adresy a smyčky čítače) a druhý pro data. První z nich byl, nebo pracoval jako, zásobník hovorů a byl programátorovi nepřímo přístupný pouze prostřednictvím jiných jazykových konstrukcí, zatímco druhý byl přímo přístupný.
když byly poprvé zavedeny volání procedur založené na zásobníku, důležitou motivací bylo ušetřit vzácnou paměť. S tímto schématem kompilátor nemusí vyhradit oddělené místo v paměti pro soukromá data (parametry, zpáteční adresu a místní proměnné) každé procedury. Zásobník v každém okamžiku obsahuje pouze soukromá data hovorů, které jsou aktuálně aktivní(jmenovitě, které byly vyvolány, ale ještě se nevrátily). Vzhledem k tomu, jak byly programy obvykle sestavovány z knihoven, nebylo (a stále je) neobvyklé najít programy, které obsahují tisíce podprogramů,z nichž je v daném okamžiku aktivní jen hrstka. U takových programů by mechanismus zásobníku hovorů mohl ušetřit značné množství paměti. Mechanismus zásobníku hovorů lze skutečně považovat za nejčasnější a nejjednodušší metodu automatické správy paměti.
Další výhodou metody zásobníku volání je však to, že umožňuje rekurzivní volání podprogramu, protože každé vnořené volání do stejného postupu získá samostatnou instanci svých soukromých dat.
zpožděná úprava stohování
jednou z nevýhod mechanismu zásobníku volání jsou zvýšené náklady na volání procedury a její odpovídající návrat. Navíc cena zahrnuje zvyšování a snižující ukazatel zásobníku (a v některých architektur, kontrola přetečení zásobníku), a přístup k místní proměnné a parametry rámu-relativní adresy, místo absolutní adresy. Náklady mohou být realizovány ve zvýšené době provádění, nebo zvýšená složitost procesoru, nebo obojí.
tato režie je nejzřetelnější a nejnepříznivější v procedurách listů nebo funkcích listů, které se vracejí, aniž by se samy volaly.Chcete-li snížit tuto režii, mnoho moderních kompilátorů se snaží odložit použití zásobníku hovorů, dokud to není skutečně potřeba. Například volání procedury P může uložit zpáteční adresu a parametry volané procedury do určitých registrů procesoru a přenést řízení do těla procedury jednoduchým skokem. Pokud se procedura P vrátí bez dalšího volání, zásobník hovorů se vůbec nepoužívá. Pokud P potřebuje zavolat jinou proceduru Q, použije zásobník hovorů k uložení obsahu všech registrů (například návratové adresy), které budou potřebné po vrácení Q.