Come funziona un linguaggio senza pila?

Ho sentito parlare di lingue senza pila. Comunque non ho idea di come sarebbe stato implementato un tale linguaggio. Qualcuno può spiegare?

I moderni sistemi operativi che abbiamo (Windows, Linux) operano con quello che io chiamo il “modello di grande pila”. E quel modello è sbagliato, a volte, e motiva la necessità di linguaggi “senza stack”.

Il “grande modello di stack” presuppone che un programma compilato allochi “stack frames” per chiamate di funzioni in un’area contigua di memoria, utilizzando le istruzioni macchina per regolare i registri contenenti il ​​puntatore dello stack (e il puntatore opzionale dello stack frame) molto rapidamente. Ciò porta a una chiamata / ritorno di funzione veloce, al prezzo di avere una regione ampia e contigua per lo stack. Poiché il 99,99% di tutti i programmi eseguiti con questi sistemi operativi moderni funziona bene con il modello di stack di grandi dimensioni, i compilatori, i caricatori e persino il sistema operativo “sanno” di questa area di stack.

Un problema comune a tutte queste applicazioni è “quanto dovrebbe essere grande il mio stack?” . Considerando che la memoria è poco costosa, per lo più ciò che accade è che un grosso blocco viene messo da parte per lo stack (MS ha un valore predefinito di 1Mb) e la struttura tipica delle chiamate alle applicazioni non si avvicina mai al suo utilizzo. Ma se un’applicazione utilizza tutto, muore con un riferimento di memoria illegale (“Mi dispiace, Dave, non posso farlo”), in virtù del raggiungere la fine del suo stack.

La maggior parte delle cosiddette lingue “senza pila” non sono realmente impilabili. Semplicemente non usano lo stack contiguo fornito da questi sistemi. Quello che fanno invece è allocare uno stack frame dall’heap su ogni chiamata di funzione. La chiamata costo per funzione sale leggermente; se le funzioni sono in genere complesse o la lingua è interpretativa, questo costo aggiuntivo è insignificante. (Si possono anche determinare i DAG di chiamata nel grafo delle chiamate di programma e allocare un segmento heap per coprire l’intero DAG: in questo modo si ottiene sia l’allocazione dell’heap sia la velocità delle chiamate di funzione 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 in base al problema specifico che sta risolvendo, è molto difficile preallocare in anticipo un’area di “grossa pila” perché non è nota la dimensione necessaria. Si possono organizzare in modo maldestro chiamate di funzione da controllare per vedere se c’è ancora abbastanza stack, e se no, riallocare un blocco più grande, copiare il vecchio stack e regolare nuovamente tutti i puntatori nello stack; è così imbarazzante che non conosco nessuna implementazione. L’allocazione dei frame dello stack significa che l’applicazione non deve mai dire che è dispiaciuta fino a quando non rimane letteralmente memoria assegnabile.

2) Il programma supporta le attività secondarie. Ogni attività secondaria richiede il proprio stack e pertanto non può utilizzare l’unico “grande stack” fornito. Quindi, è necessario allocare gli stack per ogni attività secondaria. Se hai migliaia di possibili sottoattività, ora potresti aver bisogno di migliaia di “grandi stack” e la richiesta di memoria diventa improvvisamente ridicola. L’assegnazione di frame di stack risolve questo problema. Spesso il sottoattività “stack” fa riferimento alle attività parent per implementare lo scope lessicale; come fork secondario, viene creato un albero di “substacks” chiamato “stack di cactus”.

3) La tua lingua ha continuazioni. Questi richiedono che i dati in ambito lessicale visibili alla funzione corrente vengano in qualche modo preservati per il successivo riutilizzo. Questo può essere implementato copiando i frame dello stack genitore, salendo la pila di cactus e procedendo.

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

Stackless Python ha ancora uno stack Python (sebbene possa avere l’ottimizzazione della coda e altri trucchi per la fusione dei frame call), 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 .

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

Negli ambienti senza stack con cui ho più o meno familiarità (macchina di Turing, assemblaggio e Brainfuck), è comune implementare il proprio stack. Non c’è nulla di fondamentale nell’avere uno stack integrato nella lingua.

Nella maggior parte di questi, assemblaggio, è sufficiente scegliere una regione di memoria disponibile, impostare il registro dello stack in modo che punti verso il basso, quindi aumentare o diminuire per implementare i propri push e pop.

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

C’è una descrizione di continuazione di facile comprensione su questo articolo: http://www.defmacro.org/ramblings/fp.html

Le continuazioni sono qualcosa che puoi passare in una funzione in un linguaggio basato su stack, ma che può anche essere utilizzato dalla semantica di un linguaggio per renderlo “senza stack”. Ovviamente lo stack è ancora lì, ma come ha descritto Ira Baxter, non è un grande segmento contiguo.

Supponiamo che tu voglia implementare il C. senza pila. La prima cosa da capire è che questo non ha bisogno di uno stack:

a == b 

Ma questo?

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

No. Perché un compilatore intelligente invierà chiamate a isequal , trasformandole in a == b . Quindi, perché non solo in linea tutto? Certo, genererai più codice, ma se ti stai liberando dello stack vale la pena, allora è facile con un piccolo compromesso.

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

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

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

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

In teoria un compilatore davvero intelligente potrebbe capirlo. 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 scambio. 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. Questo è qualcosa di normale C non può fare molto bene neanche. Se non mi credi, basta chiamare fib(1000) e vedere cosa succede al tuo prezioso computer.

Chiamami antico, ma ricordo che 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 c’era uno stack e FORTRAN avrebbe fatto cose strane se si fosse tentato di chiamare una subroutine in modo ricorsivo.

Per la cronaca, invece di una pila di chiamate, il set di istruzioni della serie CDC 6000 utilizzava 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 eseguirà un salto indiretto verso la posizione di destinazione della chiamata. Questo ha ricaricato il PC salvato, tornando effettivamente al chiamante.

Ovviamente, questo non funziona con le chiamate ricorsive. (E il mio ricordo è che il compilatore CDC FORTRAN IV genera codice danneggiato se si tenta di ricorsione …)

Sentitevi liberi di correggermi se ho torto, ma penserei che allocare memoria sullo heap per ogni frame di chiamata di funzione provocherebbe un thrashing estremo della memoria. Dopotutto, il sistema operativo deve gestire questa memoria. Penserei che il modo per evitare questo thrashing della memoria sarebbe una cache per i frame di chiamata. Quindi, se hai bisogno di una cache, potremmo anche renderlo contiguo in memoria e chiamarlo stack.