Come funziona un linguaggio senza stack?

Question

Ho sentito parlare di lingue senza stack. Tuttavia, non ho idea di come verrà implementato un linguaggio del genere. Qualcuno può spiegare?

Answer 1

I moderni sistemi operativi che abbiamo (Windows, Linux) funzionano con quello che io chiamo il "modello big stack". E quel modello è sbagliato, a volte, e motiva la necessità di "impilare" lingue.

Il modello di "big stack" " presume che un programma compilato assegnerà "stack frame" per chiamate di funzione in una regione contigua di memoria, usando le istruzioni della macchina per regolare molto rapidamente i registri contenenti il ??puntatore dello stack (e il puntatore del frame dello stack opzionale). Questo porta ad una rapida chiamata / ritorno di una funzione, al prezzo di avere una grande area contigua per lo stack. Perché il 99,99% di tutti i programmi eseguiti con questi moderni sistemi operativi funziona bene con il modello big stack, i compilatori, i caricatori e persino il sistema operativo "noto". su questa area dello stack.

Un problema comune che hanno tutte queste applicazioni è "quanto grande dovrebbe essere il mio stack?" " . Con la memoria a buon mercato, soprattutto ciò che accade è che un grosso blocco viene messo da parte per lo stack (l'impostazione predefinita MS è 1 Mb) e la struttura tipica delle chiamate dell'applicazione non si avvicina mai all'utilizzo. Ma se un'applicazione lo usa tutto, muore con un riferimento di memoria illegale ("mi dispiace Dave, non posso farlo"), in virtù del fatto che ha raggiunto la fine del suo stack.

La maggior parte dei cosiddetti " stackless " le lingue non sono davvero impilabili. Semplicemente non usano lo stack contiguo fornito da questi sistemi. Quello che fanno invece è allocare un frame dello stack dall'heap su ogni chiamata di funzione. Il costo per chiamata di funzione aumenta leggermente; se le funzioni sono in genere complesse o la lingua è interpretativa, questo costo aggiuntivo è insignificante. (È anche possibile determinare i DAG di chiamata nel grafico delle chiamate del programma e allocare un segmento di heap per coprire l'intero DAG; in questo modo si ottengono sia l'allocazione dell'heap sia la velocità delle chiamate di funzioni big-stack classiche per tutte le chiamate all'interno del DAG di chiamata).

Esistono diversi motivi per utilizzare l'allocazione dell'heap per i frame dello stack:

1) Se il programma esegue una ricorsione profonda a seconda del problema specifico che sta risolvendo, è molto difficile preallocare un "big stack" area in anticipo perché la dimensione necessaria non è nota. Si possono organizzare goffamente chiamate di funzione per verificare se è rimasto abbastanza stack e, in caso contrario, riallocare una parte più grande, copiare il vecchio stack e riadattare tutti i puntatori nello stack; è così imbarazzante che non conosco nessuna implementazione. Allocare frame stack significa che l'applicazione non deve mai scusarsi fino a quando non c'è letteralmente nessuna memoria allocabile rimasta.

2) Il programma esegue il fork delle attività secondarie. Ogni sottoattività richiede il proprio stack e pertanto non può utilizzare quello "big stack" fornito. Pertanto, è necessario allocare stack per ogni attività secondaria. Se hai migliaia di sottoattività possibili, ora potresti aver bisogno di migliaia di "grandi stack" e la richiesta di memoria diventa improvvisamente ridicola. Allocare frame stack risolve questo problema. Spesso la sottoattività "impila" fare riferimento alle attività principali per implementare l'ambito lessicale; come fork delle attività secondarie, un albero di "sotto-stack" viene creato chiamato "stack di cactus".

3) La tua lingua ha delle continuazioni. Questi richiedono che i dati in ambito lessicale visibili alla funzione corrente siano in qualche modo conservati per un successivo riutilizzo. Questo può essere implementato copiando i frame dello stack genitore, arrampicandosi sulla pila di cactus e procedendo.

Il PARLANSE lingua di programmazione che ho implementato fa 1) e 2). Sto lavorando su 3).

Answer 2

Stackless Python ha ancora uno stack Python (sebbene possa avere l'ottimizzazione delle chiamate di coda e altri trucchi di fusione del frame di chiamata ), ma è completamente separato dalla pila C dell'interprete.

Haskell (come comunemente implementato) non ha uno stack di chiamate; la valutazione si basa sulla riduzione del grafico .

Answer 3

C'è un bell'articolo sul framework linguistico Parrot su http: // www .linux-mag.com / cache / 7373 / 1.html . Parrot non usa lo stack per chiamare e questo articolo spiega un po 'la tecnica.

Answer 4

Negli ambienti senza stack che conosco più o meno (macchina di Turing, assemblaggio e Brainfuck), è comune implementare il proprio stack. Non c'è nulla di fondamentale nell'avere uno stack incorporato nel linguaggio.

Nella più pratica di queste, assembly, basta scegliere una regione di memoria disponibile, impostare il registro stack in modo che punti verso il basso, quindi incrementare o decrementare per implementare push e pop.

EDIT: so che alcune architetture hanno stack dedicati, ma non sono necessari.

Answer 5

Esiste una descrizione di facile comprensione delle continuazioni di questo articolo: http: // www. defmacro.org/ramblings/fp.html

Le continuazioni sono qualcosa che puoi passare a una funzione in un linguaggio basato su stack, ma che può anche essere utilizzato dalla semantica di una lingua per renderla "impilabile". Naturalmente lo stack è ancora lì, ma come ha descritto Ira Baxter, non è un grande segmento contiguo.

Answer 6

Supponi di voler implementare lo stackless C. La prima cosa da capire è che questo non ha bisogno di uno stack:

a == b

Ma questo?

isequal(a, b) { return a == b; }

No. Poiché un compilatore intelligente incorporerà le chiamate a isequal , trasformandole in a == b . Quindi, perché non semplicemente incorporare tutto? Certo, genererai più codice ma se per te vale la pena sbarazzarsi dello stack, questo è facile con un piccolo compromesso.

Che dire della ricorsione? Nessun problema. Una funzione ricorsiva della coda come:

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

Può ancora essere integrato, perché in realtà è solo un ciclo for travestito:

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

In teoria un compilatore davvero intelligente potrebbe capirlo per te. Ma uno meno intelligente potrebbe ancora appiattirlo come un goto:

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

C'è un caso in cui devi fare un piccolo trade off. Questo non può essere sottolineato:

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

Stackless C semplicemente non può farlo. Ti stai arrendendo molto? Non proprio. Anche questo è qualcosa che C normale non può fare molto bene. Se non mi credi, chiama fib (1000) e vedi cosa succede al tuo prezioso computer.

Answer 7

Chiamami antico, ma ricordo quando gli standard FORTRAN e COBOL non supportavano le chiamate ricorsive e quindi non richiedevano uno stack. In effetti, ricordo le implementazioni per le macchine della serie CDC 6000 in cui non era presente uno stack e FORTRAN farebbe cose strane se provassi a chiamare una subroutine in modo ricorsivo.

Per la registrazione, invece di uno stack di chiamate, il set di istruzioni della serie CDC 6000 ha usato l'istruzione RJ per chiamare una subroutine. Ciò ha salvato il valore corrente del PC nella posizione di destinazione della chiamata e quindi si dirama nella posizione successiva. Alla fine, una subroutine eseguiva un salto indiretto nella posizione di destinazione della chiamata. Ha ricaricato il PC salvato, tornando effettivamente al chiamante.

Ovviamente, ciò non funziona con le chiamate ricorsive. (E il mio ricordo è che il compilatore CDC FORTRAN IV genererebbe un codice non funzionante se tentassi la ricorsione ...)

Answer 8

Sentiti libero di correggermi se sbaglio, ma penso che l'allocazione di memoria sull'heap per ogni frame di chiamata di funzione provocherebbe un arresto estremo della memoria. Dopo tutto, il sistema operativo deve gestire questa memoria. Penserei che il modo per evitare questo thrashing di memoria sarebbe una cache per i frame di chiamata. Quindi, se hai comunque bisogno di una cache, potremmo anche renderla contigua in memoria e chiamarla pila.