Come si può scrivere un compilatore per una lingua che permetta di riscrivere il codice in fase di runtime (come le macro Lisp)?

Le macro hanno il vantaggio di essere espanse in fase di compilazione

L'idea delle macro Lisp è di essere in grado di espanderle completamente al momento della compilazione. Quindi nessun compilatore è necessario in fase di esecuzione. La maggior parte dei sistemi Lisp ti consente di compilare completamente il codice. La fase di compilazione include la fase di espansione della macro. Non è necessaria alcuna espansione in fase di runtime.

Spesso i sistemi Lisp includono un compilatore, ma questo è necessario quando il codice viene generato in fase di esecuzione e questo codice dovrebbe essere compilato. Ma questo è indipendente dall'espansione della macro.

Troverai persino sistemi Lisp che non includono un compilatore e nemmeno un interprete completo in fase di runtime. Tutto il codice verrà compilato prima del runtime.

I FEXPR erano funzioni di modifica del codice, ma erano per lo più sostituiti da Macro

In passato, negli anni '60 / '70 molti sistemi Lisp includevano le cosiddette funzioni FEXPR, che potevano tradurre il codice in fase di runtime. Ma non potevano essere compilati prima del runtime. Le macro li hanno sostituiti principalmente, poiché consentono la compilazione completa.

Un esempio di macro interpretata e compilata

Diamo un'occhiata a LispWorks, che ha sia un interprete che un compilatore. Permette di mescolare liberamente codice interpretato e compilato. Il Read-Eval-Print-Loop utilizza l'interprete per eseguire il codice.

Definiamo una macro banale. Ma la macro stampa il codice con cui viene chiamata, ogni volta che viene eseguita la macro.

CL-USER 45 > (defmacro my-if (test yes no)
               (format t "~%Expanding (my-if ~a ~a ~a)" test yes no)
               '(if ,test ,yes ,no))
MY-IF

Definiamo una funzione che utilizza la macro dall'alto. Ricorda: qui in LispWorks la funzione sarà interpretata.

CL-USER 46 > (defun test (x y)
               (my-if (> x y) 'larger 'not-larger))
TEST

Se si guarda in alto, il sistema Lisp ha stampato solo il nome della funzione. La macro non è stata eseguita, altrimenti la macro avrebbe stampato qualcosa. Quindi il codice non è espanso.

Eseguiamo la funzione TEST usando l'interprete:

CL-USER 47 > (loop for i below 5 collect (test i 3))

Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)

Quindi vedi che per qualche motivo l'espansione della macro viene eseguita due volte per ciascuna delle cinque chiamate da testare. La macro viene espansa dall'interprete ogni volta che viene chiamata la funzione TEST.

Ora compiliamo la funzione TEST:

CL-USER 48 > (compile 'test)

Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
TEST
NIL
NIL

Puoi vedere sopra che il compilatore esegue una volta la macro.

Se ora eseguiamo la funzione TEST, non si verificherà alcuna espansione della macro. Il modulo macro (MY-IF ...) è già stato espanso dal compilatore:

CL-USER 49 > (loop for i below 5 collect (test i 3))
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)

Se hai usato altri Lisp come SBCL o CCL, essi compileranno tutto per impostazione predefinita. SBCL ha in nuove versioni anche un interprete. Facciamo l'esempio dall'alto in un SBCL recente:

Usiamo il nuovo interprete SBCL:

CL-USER> (setf sb-ext:*evaluator-mode* :interpret)
:INTERPRET

CL-USER> (defmacro my-if (test yes no)
           (format t "~%Expanding (my-if ~a ~a ~a)" test yes no)
           '(if ,test ,yes ,no))
MY-IF
CL-USER> (defun test (x y)
           (my-if (> x y) 'larger 'not-larger))
TEST
CL-USER> (loop for i below 5 collect (test i 3))

Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)
CL-USER> (compile 'test)

Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
TEST
NIL
NIL
CL-USER> (loop for i below 5 collect (test i 3))
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)
CL-USER> 

Stai confondendo due concetti diversi nella tua domanda. Le macro sono non su che compila codice su runtime . Sono esattamente l'opposto: riguardano il codice in tempo di compilazione .

Quindi, nel caso di questo , il problema è l'opposto: non si tratta di rendere il compilatore parte del programma, piuttosto si tratta di rendere la parte del programma macro del compilatore. Puoi che incorporando un interprete nel compilatore, oppure usa la compilation staged, dove prima compili le macro, quindi collegale al compilatore, quindi compila il codice.

Nel tuo secondo paragrafo, chiedi di una cosa diversa, in pratica eval :

How is this done? Is the compiler itself basically included in the generated compiled program, such that it can compile new sections of code?

Sì, questa è una possibilità.

Or is there another way?

Ci sono altri modi:

• invece di rendere il compilatore una parte del programma, è possibile includerlo nel sistema di runtime
• non devi usare lo stesso compilatore, puoi usarne uno diverso (es. avere un compilatore che è molto grande, molto complesso, molto lento e che usa una grande quantità di memoria, ma genera molto piccolo, efficiente, codice veloce, ad alte prestazioni, ottimizzato in modo aggressivo e un secondo che spedisci nel sistema di runtime o come parte del programma compilato, che è piccolo, semplice, veloce, leggero, in modo che non "rubi" troppe risorse (tempo di CPU e memoria) dal programma utente, tuttavia potrebbe generare un codice meno efficiente
• oppure potresti usare un interprete e, ancora, spedirlo come parte del programma o come parte del sistema di runtime

Un tipico "lisc di compilazione" includerà il compilatore in un'immagine in bundle. Inoltre, la maggior parte (anche se non tutte) le chiamate di funzione vengono eseguite tramite riferimenti indiretti ai simboli (in pratica, quando il compilatore vede (+ a b) , emette il codice su "trova simbolo +", quindi "chiama la funzione a cui punta").

Ciò significa che la ridefinizione della funzione durante l'esecuzione del programma è possibile generando codice eseguibile, da qualche parte in memoria, quindi aggiorna il puntatore alla funzione nel simbolo che si riferisce alla tua funzione.

Questo è uno dei motivi per cui i "piccoli binari indipendenti" generati da un compilatore Common Lisp tendono ad essere grandi. Tuttavia, esiste una tecnica chiamata solitamente "scuotimento degli alberi" che può analizzare il programma compilato risultante e rimuovere tutti i bit dell'immagine standard a cui non viene mai fatto riferimento e in tale binario non vi sarebbe alcun compilatore incluso, senza possibilità di compilare il codice eseguito -tempo. Potresti ancora essere in grado di modificare il codice di runtime, caricando un altro file (compilato), poiché ciò può essere implementato semplicemente in termini di "mettere byte in RAM, aggiornare i puntatori nei simboli".

Sì. Il runtime deve includere un interprete o un compilatore. Questo è il motivo per cui eval è tradizionalmente una caratteristica dei linguaggi interpretati, poiché il runtime di questi linguaggi (per definizione) contiene comunque un interprete. Ora se la lingua interpreta effettivamente l'origine o la compilazione just-in-time lo esegue e poi la esegue (utilizzare l'uso di vari passaggi intermedi come un formato bytecode) - questo è fondamentalmente i dettagli dell'implementazione. La linea di fondo è che il runtime deve poter prendere il codice sorgente ed eseguirlo.

Chiaramente, la generazione del codice runtime non è compatibile con la compilazione in anticipo. Pertanto, l'ambiente di runtime della lingua deve includere alcuni meccanismi per eseguire dinamicamente il codice: un interprete o un compilatore just-in-time. Dal momento che un interprete duplica gli sforzi, molte implementazioni compilate di tali lingue preferiscono la compilazione JIT.

In ogni caso, la compilazione incrementale richiede che il codice compilato conservi una quantità sufficiente di metainformazioni in modo che il nuovo codice possa essere eseguito in questo contesto. Ad esempio, le variabili potrebbero non essere ottimizzate quando il loro ambito include una valutazione. Tuttavia, questo può essere facilmente controllato con l'analisi statica durante la compilazione del codice circostante. Una valutazione può quindi essere implementata come una chiamata tardiva a una funzione separata che verrà compilata in fase di esecuzione. Questo evita di dover effettivamente modificare il codice già compilato.

Questo non è solo un problema con Lisp. Le moderne implementazioni JITting di JavaScript ad alte prestazioni come V8 hanno anche a che fare con le valutazioni.

Si noti che eval, macro e compilazione incrementale pongono tutti lo stesso problema ai fini di questa discussione.

I cannot understand how it would be possible to write a compiler for a language that allows you to rewrite code at-runtime (and then execute that code). How is this done? Is the compiler itself basically included in the generated compiled program, such that it can compile new sections of code? Or is there another way?

Dici che non puoi capire come è fatto e poi descrivi chiaramente come è fatto; Penso che la tua affermazione che non puoi capirlo è semplicemente falsa. Lo capisci bene.

Questo è esattamente ciò che io e i miei colleghi abbiamo fatto durante l'implementazione di alberi di espressioni in C # 3. Puoi dire:

var p = Expression.Parameter(typeof (string), "p");
var len = Expression.Property(p, "Length");
var ten = Expression.Constant(10);
var lt = Expression.LessThan(len, ten);
var expr = Expression.Lambda<Func<string, bool>>(lt, p);

e ciao, abbiamo un oggetto in runtime che rappresenta

(string p) => p.Length < 10

e quando lo compiliamo:

var f = expr.Compile();
Console.WriteLine(f("hello")); // true

Come funziona expr.Compile ? Ho scritto un compilatore che sputa il nuovo IL in runtime e lo avvia, sulla base del contenuto dell'albero delle espressioni. expr.Compile esegue un compilatore; questo non dovrebbe essere troppo sorprendente!

Abbiamo avuto il chiaro vantaggio di non dover scrivere un altro parser, poiché l'albero delle espressioni è già un albero di sintassi astratto. Ma se volesse essere in grado di prendere la stringa "(string p) => p.Length < 10" e trasformarla in quell'albero di espressioni, ti assicuro che avremmo semplicemente scritto un parser che ha prodotto l'albero delle espressioni, e poi l'ho eseguito attraverso il compilatore di espressioni.

È solo un lotto di lavoro; mi ci è voluta la parte migliore di un anno per far funzionare correttamente Lambdas. Non c'è magia in esso. E naturalmente siamo tutti sulle spalle dei giganti; avere già un runtime, con un meccanismo per sputare il nuovo IL in fase di runtime e eseguirlo, era di vitale importanza per questa funzione.