non utilizzare Garbage Collector nell'implementazione Scheme/Lisp

Per il mio progetto di classe, devo implementare un (semplice) compilatore Scheme.non utilizzare Garbage Collector nell'implementazione Scheme/Lisp

A questo punto sto analizzando come implementare varie funzionalità.

Perché le tipiche implementazioni dello schema si preoccupano di un complicato GC? Se il codice è veramente funzionale (senza effetti collaterali), la funzione non attualmente in esecuzione non può essere conservata nella memoria allocata. Mai! (a meno che non si tratti di una perdita!)

Pertanto, perché non utilizzare solo la strategia seguono le lingue più imperative, come C, ad esempio le allocazioni dello stack. Ogni volta che viene immesso un nuovo contesto lessicale (ad esempio (define (foo ..) o (letrec ...), allocare lo storage variabile sullo stack e quindi regolare semplicemente il puntatore dello stack una volta che il contesto è stato chiuso.

Poiché lo schema non ha malloc() e consente l'allocazione solo di tipi predefiniti, un'implementazione semplice potrebbe utilizzare un pool o un allocatore di zona, quindi lo "stack" non dovrebbe mai frammentare.

Non devo implementare le chiusure, ma penso che anche quelle possano essere eseguite nello stesso modo copiando i valori associati in uno stack separato utilizzato esclusivamente per tenere traccia degli stati di chiusura.

Pensieri?

fonte

2013-04-26 Folksvagen

Ma il codice non è veramente funzionale, le operazioni che mutano lo stato come 'set!', 'Set-car!' E 'set-cdr!' Fanno parte di un'implementazione standard dello schema. Se il tuo (semplice) compilatore Scheme non consente queste operazioni e non devi implementare le chiusure, allora potrebbe essere possibile una semplice strategia GC –

Pensa ad un semplice esempio: una funzione restituisce una lista, che viene passata in un'altra funzione che crea una nuova lista di ogni secondo elemento della lista originale. Come verrà dedotta l'analisi della tua regione, quale parte degli elementi dell'elenco originale non è più richiesta al termine della seconda funzione? Non c'è assolutamente alcun modo di dedurre le regioni anche per il calcolo lambda più elementare. –

I problemi relativi all'implementazione di un compilatore di schemi "semplice" (la tua parola, non mia) sono molto, molto lontani dai problemi di implementazione del garbage collector di un runtime di Scheme. Concentrarsi innanzitutto sul compilatore "semplice". – GoZoner

Anche senza chiusure, l'aliasing è la parte difficile. In particolare, supponiamo che una procedura crei una parte strutturata di dati e ne restituisca una parte? Come si determinano le parti da liberare? Se riesci a risolvere questo problema ... beh, hai appena reinventato la raccolta dei rifiuti.

Per un approccio alquanto diverso, potresti dare un'occhiata a Rust (www.rust-lang.org), un linguaggio a livello di sistema che consente ai programmatori di evitare tutto il GC utilizzando le regioni e richiedendo programmatori per tracciare la proprietà in modo esplicito utilizzando diversi tipi di puntatore.

fonte

2013-04-26 16:43:19

L'OP non vuole usare un GC.Quindi non ne liberi nessuna parte: P. Non è diverso da quello che faresti in altre lingue senza GC e sicuramente non hai bisogno di reinventare GC. Proprio come i programmatori C/C++ non avevano bisogno di farlo. – MasterMastic

In linguaggi come C & C++ il programmatore è in genere responsabile della liberazione della memoria, utilizzando free(). Quindi, a meno che tu non stia proponendo uno schema con free() (o, forse, (gratuito)), o un linguaggio che semplicemente non rilasci mai memoria, la tua risposta non ha senso per me. –

Sì, una funzione libera è esattamente quello che sto dicendo. Se non si utilizza un GC che è in definitiva l'unico modo che conosco personalmente per rilasciare memoria. E no, non proporrei un linguaggio che non rilascia mai memoria. – MasterMastic

Funzioni che terminano l'esecuzione di oggetti restituiti al chiamante. Questi oggetti non possono essere allocati nei riquadri dello stack di quelle funzioni.

Quindi è necessario escludere il valore restituito (nel qual caso si hanno procedure che non sono di programmazione funzionale e per fare qualcosa di utile, tali procedure dovranno avere effetti collaterali).

Oppure è necessario creare tutto in base al valore: quando viene restituito un oggetto, viene copiato dallo stack frame della funzione restituita (successivamente deallocato), nel frame dello stack del chiamante.

I sistemi di valore hanno prestazioni e limiti semantici.

fonte

2013-04-26 18:03:07 Kaz

non utilizzare Garbage Collector nell'implementazione Scheme/Lisp

risposta

Problemi correlati