Quali sono le alternative all'utilizzo di una pila per rappresentare la semantica delle chiamate di funzioni?

18

Sappiamo tutti e amiamo che le chiamate alle funzioni vengono solitamente implementate usando lo stack; ci sono frame, indirizzi di ritorno, parametri, tutto il lotto.

Tuttavia, lo stack è un dettaglio di implementazione: le convenzioni di chiamata possono fare cose diverse (es. x86 fastcall usa (alcuni) registri, MIPS e follower usano register windows, e così via) e le ottimizzazioni possono fare anche altre cose (inlining, frame pointer omission, ottimizzazione tail-call ..).

Certo, la presenza di istruzioni di stack convenienti su molte macchine (VM come JVM e CLR, ma anche macchine reali come x86 con i loro PUSH / POP ecc.) lo rendono comodo da usare per le chiamate di funzione, ma in alcuni casi è possibile programmare in un modo in cui non è necessario uno stack di chiamate (sto pensando a Continuation Passing Style qui o Attori in un sistema che trasmette messaggi)

Quindi, stavo cominciando a chiedermi: è possibile implementare la semantica delle chiamate di funzioni senza stack, o meglio, usando una struttura dati diversa (una coda, forse, o una mappa associativa?)
Certo, capisco che uno stack è molto conveniente (c'è una ragione per cui è onnipresente) ma di recente mi sono imbattuto in un'implementazione che mi ha fatto meravigliare ..

Qualcuno di voi sa se è mai stato fatto in una lingua / macchina / macchina virtuale e, in tal caso, quali sono le differenze e le carenze evidenti?

EDIT: I miei sentimenti istintivi sono che approcci di sotto-computazione diversi possono utilizzare strutture di dati differenti. Ad esempio, il calcolo lambda non è basato sullo stack (l'idea dell'applicazione della funzione è catturata da riduzioni) ma stavo guardando un vero linguaggio / macchina / esempio. Ecco perché sto chiedendo ...

    
posta Lorenzo Dematté 07.06.2013 - 11:38
fonte

3 risposte

19

A seconda della lingua, potrebbe non essere necessario utilizzare uno stack di chiamate. Gli stack di chiamate sono necessari solo in lingue che consentono la ricorsione o la ricorsione reciproca. Se la lingua non consente la ricorsione, solo una chiamata di qualsiasi procedura può essere attiva in qualsiasi momento e le variabili locali per quella procedura possono essere allocate staticamente. Tali linguaggi devono prevedere modifiche al contesto, per la gestione degli interrupt, ma questo non richiede ancora uno stack.

Fai riferimento a FORTRAN IV (e versioni precedenti) e alle prime versioni di COBOL per esempi di lingue che non richiedono stack di chiamate.

Fare riferimento a Control Data 6600 (e alle precedenti macchine Data di controllo) per un esempio di un supercomputer precedente di grande successo che non forniva supporto hardware diretto per gli stack di chiamate. Fai riferimento al PDP-8 per un esempio di minicomputer precoce di grande successo che non supportava stack di chiamate.

Per quanto ne so, le macchine stack Brough Burroughs B5000 sono state le prime macchine con stack di chiamate hardware. Le macchine B5000 sono state progettate da zero per eseguire ALGOL, che ha richiesto la ricorsione. Avevano anche una delle prime architetture basate su descrittori, che ha gettato le basi per architetture di capacità.

Per quanto ne so, è stato il PDP-6 (che è cresciuto nel DEC-10) a rendere popolare l'hardware dello stack delle chiamate, quando la comunità hacker del MIT ne ha preso uno e ha scoperto che il PUSHJ (Push Return Address e Salto) l'operazione ha permesso di ridurre la routine di stampa decimale da 50 istruzioni a 10.

La semantica delle chiamate di funzioni più elementari in una lingua che consente la ricorsione richiede capacità che si adattano bene a una pila. Se è tutto ciò di cui hai bisogno, uno stack di base è una partita semplice e buona. Se hai bisogno di più, allora la tua struttura dati deve fare di più.

Il miglior esempio di aver bisogno di più che ho incontrato è la "continuazione", la possibilità di sospendere un calcolo nel mezzo, salvarlo come una bolla di stato congelato e spegnerlo di nuovo più tardi, forse molte volte. Le continue divennero popolari nel dialetto Scheme di LISP, come modo per implementare, tra le altre cose, le uscite di errore. Le continuazioni richiedono la possibilità di eseguire un'istantanea dell'ambiente di esecuzione corrente e riprodurle in un secondo momento, e uno stack è alquanto inopportuno.

Abelson & La "Struttura e interpretazione dei programmi per computer" di Sussman entra nei dettagli sulle continuazioni.

    
risposta data 07.06.2013 - 14:24
fonte
6

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.

    
risposta data 07.06.2013 - 12:00
fonte
4

Il linguaggio concatenativo di giocattoli XY utilizza una coda di chiamata e uno stack di dati per l'esecuzione.

Ogni passo di computazione coinvolge semplicemente la dequing della parola successiva da eseguire e nel caso di builtin, alimentando la sua funzione interna lo stack di dati e la coda di chiamata come argomenti, o con userdefs, spingendo le parole che lo compongono in primo piano coda.

Quindi, se abbiamo una funzione per raddoppiare l'elemento superiore:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Quindi le funzioni di composizione + e dup hanno le seguenti firme di tipo stack / queue:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

E paradossalmente, double sarà simile a questa:

double [X Y] -> [X dup^+^Y]

Quindi in un certo senso, XY è senza stack.

    
risposta data 07.06.2013 - 23:32
fonte