L’idea di una subroutine è stata elaborata dopo che le macchine informatiche esistevano già da qualche tempo.Le istruzioni di salto aritmetica e condizionale sono state pianificate in anticipo e sono cambiate relativamente poco, ma le istruzioni speciali utilizzate per le chiamate di procedura sono cambiate notevolmente nel corso degli anni.I primi computer e microprocessori, come il Manchester Baby e l’RCA 1802, non avevano una singola istruzione di chiamata subroutine.Le subroutine potevano essere implementate, ma richiedevano ai programmatori di utilizzare la sequenza di chiamate—una serie di istruzioni—in ogni sito di chiamata.

Le subroutine furono implementate nello Z4 di Konrad Zuse nel 1945.

Nel 1945, Alan M. Turing usò i termini “bury” e “unbury” come mezzo per chiamare e tornare dalle subroutine.

Nel gennaio 1947 John Mauchly presentò note generali a “A Symposium of Large Scale Digital Calculating Machinery” sotto la sponsorizzazione congiunta dell’Università di Harvard e del Bureau of Ordnance, United States Navy. Qui discute l’operazione seriale e parallela suggerendo

…la struttura della macchina non deve essere complicata un po’. È possibile, poiché sono disponibili tutte le caratteristiche logiche essenziali per questa procedura, evolvere un’istruzione di codifica per posizionare le subroutine nella memoria in luoghi noti alla macchina e in modo tale che possano essere facilmente chiamate in uso.

In altre parole, si può designare la subroutine A come divisione e la subroutine B come moltiplicazione complessa e la subroutine C come valutazione di un errore standard di una sequenza di numeri, e così via attraverso l’elenco delle subroutine necessarie per un particolare problema. … Tutte queste subroutine verranno quindi memorizzate nella macchina e tutto ciò che è necessario fare è fare un breve riferimento a loro per numero, come sono indicati nella codifica.

Kay McNulty aveva lavorato a stretto contatto con John Mauchly nel team ENIAC e sviluppato un’idea per le subroutine per il computer ENIAC che stava programmando durante la seconda guerra mondiale. Lei e gli altri programmatori ENIAC usavano le subroutine per aiutare a calcolare le traiettorie dei missili.

Goldstine e von Neumann scrissero un documento datato 16 agosto 1948 che parlava dell’uso delle subroutine.

Alcuni primissimi computer e microprocessori, come IBM 1620, Intel 4004 e Intel 8008 e i microcontrollori PIC, hanno una chiamata di subroutine a istruzione singola che utilizza uno stack hardware dedicato per memorizzare gli indirizzi di ritorno: tale hardware supporta solo alcuni livelli di nesting delle subroutine, ma può supportare subroutine ricorsive. Le macchine prima della metà degli anni 1960-come UNIVAC I, PDP—1 e IBM 1130-in genere utilizzano una convenzione di chiamata che salvava il contatore di istruzioni nella prima posizione di memoria della subroutine chiamata. Ciò consente livelli arbitrariamente profondi di nidificazione delle subroutine ma non supporta le subroutine ricorsive. Il PDP-11 (1970) è uno dei primi computer con un’istruzione di chiamata di subroutine che spinge lo stack; questa funzione supporta sia il nesting arbitrariamente profondo delle subroutine che supporta anche le subroutine ricorsive.

Language supportEdit

Nei primissimi assemblatori, il supporto delle subroutine era limitato. Le subroutine non erano esplicitamente separate l’una dall’altra o dal programma principale, e in effetti il codice sorgente di una subroutine poteva essere intervallato da quello di altri sottoprogrammi. Alcuni assemblatori offrirebbero macro predefinite per generare la chiamata e restituire le sequenze. Negli anni ‘ 60, gli assemblatori di solito avevano un supporto molto più sofisticato sia per le subroutine in linea che per quelle assemblate separatamente che potevano essere collegate tra loro.

Subroutine librariesEdit

Anche con questo approccio ingombrante, subroutine dimostrato molto utile. Per prima cosa, hanno permesso l’uso dello stesso codice in molti programmi diversi. Inoltre, la memoria era una risorsa molto scarsa sui primi computer e le subroutine consentivano risparmi significativi nella dimensione dei programmi.

Molti primi computer caricavano le istruzioni del programma in memoria da un nastro di carta punzonato. Ogni subroutine potrebbe quindi essere fornita da un pezzo separato di nastro, caricato o giuntato prima o dopo il programma principale( o “mainline”); e lo stesso nastro subroutine potrebbe quindi essere utilizzato da molti programmi diversi. Un approccio simile applicato nei computer che utilizzavano schede perforate per il loro ingresso principale. Il nome subroutine library originariamente significava una libreria, nel senso letterale, che teneva raccolte indicizzate di nastri o mazzi di carte per uso collettivo.

Return by indirect jumpEdit

Per rimuovere la necessità di codice auto-modificante, i progettisti di computer alla fine fornirono un’istruzione di salto indiretto, il cui operando, invece di essere l’indirizzo di ritorno stesso, era la posizione di una variabile o di un registro del processore contenente l’indirizzo di ritorno.

Su quei computer, invece di modificare il salto di ritorno della subroutine, il programma chiamante memorizzava l’indirizzo di ritorno in una variabile in modo che quando la subroutine veniva completata, eseguisse un salto indiretto che dirigeva l’esecuzione nella posizione data dalla variabile predefinita.

Vai a subroutineEdit

Un altro avanzamento è stato l’istruzione jump to subroutine, che ha combinato il salvataggio dell’indirizzo di ritorno con il salto di chiamata, riducendo così significativamente il sovraccarico.

In IBM System / 360, ad esempio, le istruzioni di ramo BAL o BALR, progettate per la chiamata di procedura, salverebbero l’indirizzo di ritorno in un registro del processore specificato nell’istruzione, dal registro delle convenzioni 14. Per tornare, la subroutine doveva solo eseguire un’istruzione branch indiretta (BR) attraverso quel registro. Se la subroutine aveva bisogno di quel registro per qualche altro scopo (come chiamare un’altra subroutine), salverebbe il contenuto del registro in una posizione di memoria privata o in uno stack di registro.

In sistemi come HP 2100, l’istruzione JSB eseguiva un’attività simile, tranne per il fatto che l’indirizzo di ritorno era memorizzato nella posizione di memoria che era la destinazione del ramo. L’esecuzione della procedura inizierà effettivamente nella successiva posizione di memoria. Nel linguaggio assembly HP 2100, si scriverebbe, ad esempio

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

per chiamare una subroutine chiamata MYSUB dal programma principale. La subroutine sarebbe codificata come

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

L’istruzione JSB ha inserito l’indirizzo dell’istruzione SUCCESSIVA (vale a dire, BB) nella posizione specificata come suo operando (vale a dire, MYSUB), e poi si è ramificata nella posizione SUCCESSIVA dopo quella (vale a dire, AA = MYSUB + 1). La subroutine potrebbe quindi tornare al programma principale eseguendo il salto indiretto JMP MYSUB, I che si ramificava nella posizione memorizzata nella posizione MYSUB.

I compilatori per Fortran e altri linguaggi potrebbero facilmente utilizzare queste istruzioni quando disponibili. Questo approccio supportava più livelli di chiamate; tuttavia, poiché all’indirizzo di ritorno, ai parametri e ai valori di ritorno di una subroutine erano assegnate posizioni di memoria fisse, non consentiva chiamate ricorsive.

Per inciso, un metodo simile è stato utilizzato da Lotus 1-2-3, nei primi anni 1980, per scoprire le dipendenze di ricalcolo in un foglio di calcolo. Vale a dire, una posizione è stata riservata in ogni cella per memorizzare l’indirizzo di ritorno. Poiché i riferimenti circolari non sono consentiti per l’ordine di ricalcolo naturale, ciò consente una passeggiata ad albero senza riservare spazio per uno stack in memoria, che era molto limitato su piccoli computer come il PC IBM.

Call stackEdit

La maggior parte delle implementazioni moderne di una chiamata di subroutine utilizza uno stack di chiamate, un caso speciale della struttura dati dello stack, per implementare chiamate e ritorni di subroutine. Ogni chiamata di procedura crea una nuova voce, chiamata frame stack, nella parte superiore dello stack; quando la procedura ritorna, il frame dello stack viene eliminato dallo stack e il suo spazio può essere utilizzato per altre chiamate di procedura. Ogni frame dello stack contiene i dati privati della chiamata corrispondente, che in genere include i parametri e le variabili interne della procedura, e l’indirizzo di ritorno.

La sequenza di chiamata può essere implementata da una sequenza di istruzioni ordinarie (un approccio ancora usato nelle architetture RISC (Reduced Instruction set computing) e very long Instruction word (VLIW)), ma molte macchine tradizionali progettate dalla fine degli anni ‘ 60 hanno incluso istruzioni speciali per questo scopo.

Lo stack di chiamate viene solitamente implementato come un’area di memoria contigua. È una scelta di progettazione arbitraria se il fondo dello stack è l’indirizzo più basso o più alto all’interno di quest’area, in modo che lo stack possa crescere in avanti o indietro nella memoria; tuttavia, molte architetture hanno scelto quest’ultimo.

Alcuni progetti, in particolare alcune implementazioni Forth, utilizzavano due stack separati, uno principalmente per le informazioni di controllo (come indirizzi di ritorno e contatori di loop) e l’altro per i dati. Il primo era, o funzionava come, uno stack di chiamate ed era solo indirettamente accessibile al programmatore attraverso altri costrutti linguistici mentre il secondo era più direttamente accessibile.

Quando sono state introdotte le chiamate di procedura basate su stack, una motivazione importante è stata quella di risparmiare memoria preziosa. Con questo schema, il compilatore non deve riservare spazio separato in memoria per i dati privati (parametri, indirizzo di ritorno e variabili locali) di ciascuna procedura. In qualsiasi momento, lo stack contiene solo i dati privati delle chiamate attualmente attive (ovvero, che sono state chiamate ma non sono ancora state restituite). A causa dei modi in cui i programmi venivano solitamente assemblati dalle librerie, non era (ed è ancora) raro trovare programmi che includessero migliaia di subroutine, di cui solo una manciata sono attive in un dato momento. Per tali programmi, il meccanismo dello stack di chiamate potrebbe salvare quantità significative di memoria. In effetti, il meccanismo dello stack di chiamate può essere visto come il primo e più semplice metodo per la gestione automatica della memoria.

Tuttavia, un altro vantaggio del metodo call stack è che consente chiamate di subroutine ricorsive, poiché ogni chiamata nidificata alla stessa procedura ottiene un’istanza separata dei suoi dati privati.

Modifica stacking ritardato

Uno svantaggio del meccanismo dello stack di chiamate è l’aumento del costo di una chiamata di procedura e il suo ritorno corrispondente. Il costo aggiuntivo include l’incremento e la decrementazione del puntatore dello stack (e, in alcune architetture, il controllo dell’overflow dello stack) e l’accesso alle variabili e ai parametri locali tramite indirizzi relativi al frame, anziché indirizzi assoluti. Il costo può essere realizzato in tempi di esecuzione aumentati, o maggiore complessità del processore, o entrambi.

Questo overhead è più ovvio e discutibile nelle procedure foglia o funzioni foglia, che restituiscono senza fare alcuna procedura si chiama.Per ridurre tale sovraccarico, molti compilatori moderni cercano di ritardare l’uso di uno stack di chiamate fino a quando non è veramente necessario. Ad esempio, la chiamata di una procedura P può memorizzare l’indirizzo di ritorno e i parametri della procedura chiamata in determinati registri del processore e trasferire il controllo al corpo della procedura con un semplice salto. Se la procedura P ritorna senza effettuare altre chiamate, lo stack di chiamate non viene utilizzato affatto. Se P deve chiamare un’altra procedura Q, utilizzerà lo stack di chiamate per salvare il contenuto di qualsiasi registro (come l’indirizzo di ritorno) che sarà necessario dopo il ritorno di Q.