La maggior parte delle architetture che ho visto si basano su uno stack di chiamate per salvare / ripristinare il contesto prima delle chiamate di funzione. È un paradigma così comune che le operazioni push e pop sono integrate nella maggior parte dei processori. Esistono sistemi che funzionano senza stack? In tal caso, come funzionano e a cosa servono?
Un'alternativa (in qualche modo) popolare a uno stack di chiamate è continuazioni .
Parrot VM è basato sulla continuazione, ad esempio. È completamente senza stack: i dati sono tenuti in registri (come Dalvik o LuaVM, Parrot è basato su registri) e il flusso di controllo è rappresentato con continuazioni (a differenza di Dalvik o LuaVM, che hanno uno stack di chiamate).
Un'altra popolare struttura dati, usata tipicamente da Smalltalk e Lisp VMs è lo stack di spaghetti, che è come una rete di stack.
Poiché @rwong ha sottolineato , lo stile di passaggio continuo è un'alternativa allo stack di chiamate. I programmi scritti in (o trasformati in) stili di passaggio continuo non ritornano mai, quindi non c'è bisogno di uno stack.
Rispondere alla domanda da una prospettiva diversa: è possibile avere uno stack di chiamate senza avere uno stack separato, allocando i frame dello stack nell'heap. Alcune implementazioni Lisp e Scheme fanno questo.
Nei tempi antichi, i processori non avevano istruzioni di stack e i linguaggi di programmazione non supportavano la ricorsione. Nel tempo, sempre più lingue scelgono di supportare la ricorsione e l'hardware ha seguito la suite con capacità di allocazione dello stack frame. Questo supporto è notevolmente cambiato nel corso degli anni con diversi processori. Alcuni processori hanno adottato i registri stack stack e / o stack pointer; alcune istruzioni adottate che avrebbero portato all'assegnazione dei frame di stack in una singola istruzione.
Mentre i processori avanzavano con cache a livello singolo, quindi a più livelli, un vantaggio fondamentale dello stack è quello della località cache. La cima dello stack è quasi sempre nella cache. Ogni volta che puoi fare qualcosa che ha una grande percentuale di cache, sei sulla strada giusta con i processori moderni. La cache applicata allo stack significa che le variabili locali, i parametri, ecc. Sono quasi sempre nella cache e godono del più alto livello di prestazioni.
In breve, l'utilizzo dello stack si è evoluto sia nell'hardware che nel software. Esistono altri modelli (ad esempio, il calcolo del flusso di dati è stato provato per un lungo periodo), tuttavia, la localizzazione dello stack lo rende molto efficace. Inoltre, il codice procedurale è proprio ciò che i processori vogliono, per le prestazioni: un'istruzione che dice cosa fare dopo l'altro. Quando le istruzioni sono fuori dall'ordine lineare, il processore rallenta tremendamente, almeno fino ad ora, dal momento che non abbiamo capito come rendere l'accesso casuale veloce come l'accesso sequenziale. (A proposito, ci sono problemi simili ad ogni livello di memoria, dalla cache, alla memoria principale, al disco ...)
Tra le prestazioni dimostrate delle istruzioni di accesso sequenziale e il comportamento di caching vantaggioso dello stack di chiamate, abbiamo, almeno attualmente, un modello di prestazioni vincente.
(Potremmo anche lanciare la mutevolezza delle strutture dati nelle opere ...)
Questo non significa che altri modelli di programmazione non possano funzionare, specialmente quando possono essere tradotti nelle istruzioni sequenziali e nel modello di stack di chiamata dell'hardware di oggi. Ma c'è un netto vantaggio per i modelli che supportano dove si trova l'hardware. Tuttavia, le cose non sono sempre le stesse, quindi abbiamo potuto vedere dei cambiamenti in futuro, poiché le diverse tecnologie di memoria e transistor consentono un maggiore parallelismo. È sempre una battuta tra i linguaggi di programmazione e le capacità hardware, quindi vedremo!
TL; DR
Il resto di questa risposta è una raccolta casuale di pensieri e aneddoti, e quindi un po 'disorganizzati.
Lo stack che hai descritto (come meccanismo di chiamata di funzione) è specifico per la programmazione imperativa.
Sotto la programmazione imperativa, troverai il codice della macchina. Il codice macchina può emulare lo stack di chiamate eseguendo una piccola sequenza di istruzioni.
Sotto il codice macchina, troverai l'hardware responsabile dell'esecuzione del software. Mentre il microprocessore moderno è troppo complesso per essere descritto qui, si può immaginare che esista un design molto semplice che è lento ma è comunque in grado di eseguire lo stesso codice macchina. Un design così semplice farà uso degli elementi di base della logica digitale:
Le seguenti discussioni contenevano molti esempi di modi alternativi per strutturare programmi imperativi.
La struttura di tale programma sarà simile a questa:
void main(void)
{
do
{
// validate inputs for task 1
// execute task 1, inlined,
// must complete in a deterministically short amount of time
// and limited to a statically allocated amount of memory
// ...
// validate inputs for task 2
// execute task 2, inlined
// ...
// validate inputs for task N
// execute task N, inlined
}
while (true);
// if this line is reached, tell the programmers to prepare
// themselves to appear before an accident investigation board.
return 0;
}
Questo stile sarebbe appropriato per i microcontrollori, cioè per coloro che vedono il software come un compagno alle funzioni dell'hardware.
No, non necessariamente.
Leggi il vecchio documento di Appel Garbage Collection può essere più veloce di Stack Allocation . Utilizza lo stile di passaggio continuo e mostra un'implementazione senza stack.
Si noti inoltre che le vecchie architetture di computer (ad es. IBM / 360 ) non contenevano alcun registro di stack hardware. Ma il sistema operativo e il compilatore hanno riservato un registro per il puntatore dello stack per convenzione (correlato a chiamando le convenzioni ) in modo che potessero avere uno stack di chiamate del software
.In linea di principio, un intero compilatore C e un ottimizzatore del programma potrebbero rilevare il caso (un po 'comune per i sistemi embedded) in cui il grafo delle chiamate è staticamente noto e senza alcuna ricorsione (o puntatori di funzione). In un tale sistema, ciascuna funzione poteva mantenere il suo indirizzo di ritorno in una posizione statica fissa (e questo era il modo in cui Fortran77 funzionava nei computer dell'era del 1970).
In questi giorni, i processori hanno anche stack di chiamate (e chiamate e restituiscono istruzioni macchina) a conoscenza di cache della CPU .
Finora hai ricevuto delle buone risposte; lascia che ti dia un esempio pratico ma altamente educativo di come potresti progettare una lingua senza la nozione di pile o "flusso di controllo". Ecco un programma che determina i fattoriali:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)
Mettiamo questo programma in una stringa e valutiamo il programma con la sostituzione testuale. Quindi, quando stiamo valutando f(3) , eseguiamo una ricerca e sostituiamo con 3 per i, in questo modo:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)
Grande. Ora eseguiamo un'altra sostituzione testuale: vediamo che la condizione del "se" è falsa e sostituisce un'altra stringa, producendo il programma:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)
Ora facciamo un'altra sostituzione di stringa su tutte le sottoespressioni che coinvolgono le costanti:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)
E vedi come va; Non affronterò il problema ulteriormente. Potremmo continuare a fare una serie di sostituzioni di stringhe fino a quando non scendiamo a let x = 6 e avremmo finito.
Usiamo lo stack tradizionalmente per variabili locali e informazioni di continuazione; ricorda, una pila non ti dice da dove vieni, ti dice dove andrai dopo con quel valore di ritorno in mano.
Nel modello di sostituzione delle stringhe della programmazione, non ci sono "variabili locali" nello stack; i parametri formali vengono sostituiti per i loro valori quando la funzione viene applicata al suo argomento, anziché essere inserita in una tabella di ricerca nello stack. E non c'è "andare da qualche parte il prossimo" perché la valutazione del programma sta semplicemente applicando semplici regole per la sostituzione delle stringhe per produrre un programma diverso ma equivalente.
Ora, ovviamente, in realtà le sostituzioni di stringhe non sono probabilmente la strada da percorrere. Ma i linguaggi di programmazione che supportano il "ragionamento equazionale" (come Haskell) sono logicamente che usano questa tecnica.
Dalla pubblicazione di Parnas nel 1972 su sui criteri da utilizzare nei sistemi in decomposizione nei moduli è stato ragionevolmente accettato che l'informazione nascosta nel software sia una buona cosa. Questo fa seguito a un lungo dibattito durante gli anni '60 sulla scomposizione strutturale e sulla programmazione modulare.
Un risultato necessario delle relazioni black-box tra i moduli implementati da gruppi diversi in qualsiasi sistema multi-thread richiede un meccanismo per consentire la rientranza e un mezzo per tracciare il grafico dinamico delle chiamate del sistema. Il flusso controllato di esecuzione deve passare sia dentro che fuori da più moduli.
Non appena lo scope lessicale è insufficiente per tenere traccia del comportamento dinamico, per tenere traccia della differenza è necessario un po 'di contabilità di runtime.
Dato un thread (per definizione) ha solo un singolo puntatore di istruzioni corrente, uno stack LIFO è appropriato per tracciare ogni invocazione.
Quindi, mentre il modello di continuazione non mantiene una struttura di dati esplicitamente per lo stack, c'è ancora la chiamata nidificata dei moduli che deve essere mantenuta da qualche parte!
Anche le lingue dichiarative mantengono la cronologia delle valutazioni o, al contrario, appiattiscono il piano di esecuzione per motivi di prestazioni e mantengono i progressi in un altro modo.
La struttura ad anello infinita identificata da rwong è comune nelle applicazioni ad alta affidabilità con una programmazione statica che non consente molti comuni strutture di programmazione ma richiede che l'intera applicazione sia considerata una casella bianca senza nascondere informazioni significative.
Più loop infiniti concomitanti non richiedono alcuna struttura per contenere gli indirizzi di ritorno poiché non chiamano funzioni, rendendo la domanda discutibile. Se comunicano usando variabili condivise, queste possono facilmente degenerare in legacy analoghi di indirizzo di ritorno in stile Fortran.
Tutti i vecchi mainframe (IBM System / 360) non avevano alcuna nozione di stack. Sulla 260, ad esempio, i parametri sono stati costruiti in una posizione fissa in memoria e quando è stata chiamata una subroutine, è stata chiamata con R1 che punta al blocco parametri e R14 che contiene l'indirizzo di ritorno. La routine chiamata, se voleva chiamare un'altra subroutine, dovrebbe memorizzare R14 in una posizione nota prima di effettuare quella chiamata.
Questo è molto più affidabile di uno stack perché tutto può essere memorizzato in posizioni di memoria fisse stabilite in fase di compilazione e può essere garantito al 100% che i processi non finiranno mai nello stack. Non c'è nessuno di "Allocare 1 MB e incrocia le dita" che dobbiamo fare oggigiorno.
Le chiamate subroutine ricorsive erano consentite in PL / I specificando la parola chiave RECURSIVE . Significavano che la memoria utilizzata dalla subroutine era dinamicamente anziché allocata staticamente. Ma le chiamate ricorsive erano rare come allora.
Anche le operazioni senza pila rendono molto più semplice l'enorme multi-threading, motivo per cui i tentativi sono spesso fatti per rendere le lingue moderne stalkless. Non vi è alcun motivo, ad esempio, perché un compilatore C ++ non possa essere modificato in back-end per utilizzare la memoria allocata dinamicamente anziché gli stack.
Leggi altre domande sui tag computer-architecture