Non è possibile implementare la semantica delle chiamate di funzioni senza utilizzare una sorta di stack. È possibile giocare solo ai giochi di parole (ad esempio, usa un nome diverso, come "FILO return buffer").
È possibile usare qualcosa che non implementa la semantica delle chiamate di funzione (ad esempio lo stile di passaggio di continuazione, gli attori), e quindi costruire la semantica delle chiamate di funzioni su di essa; ma questo significa aggiungere una sorta di struttura dati per tracciare dove viene passato il controllo quando la funzione ritorna, e quella struttura dati sarebbe un tipo di pila (o una pila con un nome / descrizione diverso).
Immagina di avere molte funzioni che possono chiamarsi a vicenda. In fase di esecuzione, ciascuna funzione deve sapere dove tornare quando termina la funzione. Se first chiama second , allora hai:
second returns to somewhere in first
Quindi, se second chiama third hai:
third returns to somewhere in second
second returns to somewhere in first
Quindi, se third chiama fourth hai:
fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first
Man mano che ogni funzione viene chiamata, più informazioni "dove restituire" devono essere memorizzate da qualche parte.
Se viene restituita una funzione, viene utilizzata l'informazione "dove restituire" e non è più necessaria. Ad esempio, se fourth ritorna a qualche parte in third , la quantità di informazioni "dove tornare a" diventerebbe:
third returns to somewhere in second
second returns to somewhere in first
In sostanza; "semantica chiamata di funzione" implica che:
- devi avere "dove restituire" le informazioni
- la quantità di informazioni cresce man mano che le funzioni vengono chiamate e viene ridotta quando le funzioni restituiscono
- il primo pezzo di "dove restituire" le informazioni memorizzate sarà l'ultimo pezzo di "dove restituire" le informazioni scartate
Questo descrive un buffer FILO / LIFO o uno stack.
Se si tenta di utilizzare un tipo di albero, ogni nodo dell'albero non avrà mai più di un figlio. Nota: un nodo con più figli può accadere solo se una funzione chiama 2 o più funzioni allo stesso tempo , che richiede una sorta di concorrenza (es. thread, fork (), ecc.) e non sarebbe "funzione chiamata semantica". Se ogni nodo dell'albero non avrà mai più di un figlio; allora quel "albero" verrebbe usato solo come buffer FILO / LIFO o stack; e poiché è usato solo come buffer FILO / LIFO o stack, è giusto pretendere che "l'albero" sia uno stack (e l'unica differenza sono i giochi di parole e / oi dettagli di implementazione).
Lo stesso vale per qualsiasi altra struttura di dati che possa essere concepita per implementare la "semantica delle chiamate di funzione" - verrà utilizzata come una pila (e l'unica differenza sono i giochi di parole e / oi dettagli di implementazione); a meno che non interrompa la "semantica chiamata di funzione". Nota: fornirei esempi per altre strutture di dati se potessi, ma non riesco a pensare ad altre strutture che siano leggermente plausibili.
Ovviamente, come viene implementato uno stack è un dettaglio di implementazione. Potrebbe essere un'area di memoria (dove si tiene traccia di uno "stack corrente"), potrebbe essere una sorta di elenco collegato (dove si tiene traccia di "voce corrente nell'elenco"), oppure potrebbe essere implementato in alcuni altro modo. Non importa se l'hardware ha il supporto integrato o meno.
Nota: se solo una chiamata di una procedura può essere attiva in qualsiasi momento; quindi è possibile allocare staticamente lo spazio per informazioni su "dove tornare". Questo è ancora uno stack (ad esempio un elenco collegato di voci allocate staticamente utilizzate in modo FILO / LIFO).
Si noti inoltre che ci sono alcune cose che non seguono la "funzione chiamata semantica". Queste cose includono "semantica potenzialmente molto diversa" (ad esempio continuation passing, actor model); e include anche estensioni comuni alla "semantica delle chiamate di funzioni" come la concorrenza (thread, fibre, qualunque cosa), setjmp / longjmp , gestione delle eccezioni, ecc.