Chiamate di coda in architetture senza stack di chiamate

Question

La mia risposta per un recente domanda sui GOTO e sulla ricorsione della coda è stato formulato in termini di stack di chiamate.Temo che non fosse sufficientemente generale, quindi ti chiedo:in che modo la nozione di chiamata di coda (o equivalente) è utile nelle architetture senza stack di chiamate?

Nel passaggio continuo, tutte le funzioni chiamate sostituiscono la funzione chiamante e sono quindi chiamate in coda, quindi "chiamata in coda" non sembra essere una distinzione utile.Nelle architetture basate su messaggistica ed eventi, non sembra esserci un equivalente, anche se correggimi se sbaglio.Le ultime due architetture sono casi interessanti in quanto sono associate all'OOP, piuttosto che al FP.E le altre architetture?Le vecchie macchine Lisp erano basate su stack di chiamate?

Modificare:Secondo "Che diavolo è:Stile di passaggio della continuazione (CPS)" (e Alex sotto), l'equivalente di una chiamata in coda con passaggio di continuazione non è "la funzione chiamata sostituisce la funzione chiamante" ma "la funzione chiamante passa la continuazione che le è stata data, anziché creare una nuova continuazione".Questo tipo di richiamo della coda è utile, a differenza di quanto ho affermato.

Inoltre, non mi interessano i sistemi che utilizzano stack di chiamate a un livello inferiore, poiché il livello superiore non richiede uno stack di chiamate.Questa restrizione non si applica alla risposta di Alex perché sta scrivendo del fatto che altre architetture di invocazione (è questo il termine giusto?) spesso hanno uno stack di chiamate equivalente, non che abbiano uno stack di chiamate da qualche parte sotto il cofano.In caso di passaggio successivo, la struttura è come un arborescenza, ma con bordi in direzione opposta.Gli equivalenti dello stack di chiamate sono molto rilevanti per i miei interessi.

Answer 1

Nella remota possibilità che questa domanda interessi qualcuno diverso da me, ho un risposta ampliata per l'altra domanda che risponde anche a questa.Ecco la versione breve e non rigorosa.

Quando un sistema computazionale esegue sottocalcoli (ad es.un calcolo inizia e deve fermarsi mentre viene eseguito un altro calcolo perché il primo dipende dal risultato del secondo), nasce naturalmente una relazione di dipendenza tra i punti di esecuzione.Nelle architetture basate sullo stack di chiamate, la relazione è topologicamente a grafico del percorso.In CPS è un albero, dove ogni percorso tra la radice e un nodo è una continuazione.Nello scambio e nel threading dei messaggi, è una raccolta di grafici di percorso.La gestione degli eventi sincroni consiste fondamentalmente nello scambio di messaggi.Avviare un sottocalcolo comporta l'estensione della relazione di dipendenza, tranne che in una chiamata di coda che sostituisce una foglia anziché aggiungervi.

La traduzione delle chiamate alla coda nella gestione degli eventi asincrona è più complessa, quindi considera invece una versione più generale.Se A è iscritto a un evento sul canale 1, B è iscritto allo stesso evento sul canale 2 e il gestore di B attiva semplicemente l'evento sul canale 1 (traduce l'evento su tutti i canali), quindi A può essere iscritto all'evento sul canale 2 invece di abbonarsi B.Questo è più generale perché l'equivalente di una chiamata in coda lo richiede

• L'abbonamento di A al canale 1 verrà annullato quando A sarà iscritto al canale 2
• i gestori si auto-annullano l'iscrizione (quando richiamati, annullano l'iscrizione)

Ora per due sistemi che non eseguono calcoli secondari:lambda calcolo (o sistemi di riscrittura dei termini in generale) e RPN.Per il lambda calcolo, le chiamate alla coda corrispondono approssimativamente a una sequenza di riduzioni in cui la lunghezza del termine è O(1) (vedere i processi iterativi in SICP sezione 1.2).Prendi RPN per utilizzare uno stack di dati e uno stack di operazioni (al contrario di un flusso di operazioni;le operazioni sono quelle ancora da elaborare) e un ambiente che associa i simboli a una sequenza di operazioni.Le chiamate di coda potrebbero corrispondere a processi con crescita dello stack O(1).

Answer 2

"Architetture senza uno stack di chiamate" tipicamente "simulare" una ad un certo livello - per esempio, nel momento della IBM 360, abbiamo usato il S-Type Convenzione linkage utilizzando il registro-save aree e argomenti liste indicate, per convenzione, da parte di alcuni registri di uso generale.

Quindi, "chiamata di coda" può ancora importa: non la funzione chiamante necessità di preservare le informazioni necessarie per riprendere l'esecuzione dopo il punto di chiamata (una volta che la funzione chiamata è finito), o lo fa sapere che ci sarà nessuna esecuzione dopo il punto di chiamata, e così semplicemente riutilizzare del chiamante "info per riprendere l'esecuzione", invece?

Così, per esempio, un'ottimizzazione chiamata coda potrebbe significare non aggiungendo la continuazione necessaria per riprendere l'esecuzione su qualsiasi collegata elenco viene utilizzato per lo scopo ... che mi piace vedere come una "simulazione di stack di chiamate" (a un certo livello, anche se è ovviamente una disposizione più flessibile - non vuole avere continuazione-passing fan saltare tutta la mia risposta; -).