Como um compilador pode ser escrito para uma linguagem que permite reescrever o código em tempo de execução (como macros Lisp)?

As macros têm a vantagem de serem expandidas em tempo de compilação

A idéia das macros Lisp é poder expandi-las completamente em tempo de compilação. Então nenhum compilador é necessário em tempo de execução. A maioria dos sistemas Lisp permitem que você compile completamente o código. A etapa de compilação inclui a fase de expansão macro. Não há expansão necessária em tempo de execução.

Muitas vezes, os sistemas Lisp incluem um compilador, mas isso é necessário quando o código é gerado no tempo de execução e esse código precisa ser compilado. Mas isso é independente da expansão de macro.

Você até encontrará sistemas Lisp que não incluem um compilador e nem mesmo um intérprete completo em tempo de execução. Todo o código será compilado antes do tempo de execução.

FEXPRs eram funções modificadoras de código, mas foram substituídas principalmente por macros

Em tempos antigos nos anos 60/70, muitos sistemas Lisp incluíam as chamadas funções FEXPR, que podiam traduzir o código em tempo de execução. Mas eles não puderam ser compilados antes do tempo de execução. As macros as substituíram principalmente, pois permitem a compilação completa.

Um exemplo de uma macro interpretada e compilada

Vamos dar uma olhada no LispWorks, que possui um interpretador e um compilador. Permite misturar código interpretado e compilado livremente. O Read-Eval-Print-Loop usa o Interpretador para executar código.

Vamos definir uma macro trivial. Mas a macro imprime o código com o qual é chamada toda vez que a macro é executada.

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

Vamos definir uma função que usa a macro acima. Lembre-se: aqui no LispWorks a função será interpretada.

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

Se você olhar acima, o sistema Lisp imprimiu apenas o nome da função. A macro não foi executada - caso contrário, a macro teria imprimido alguma coisa. Então o código não é expandido.

Vamos executar a função TESTE usando o Interpretador:

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)

Assim, você vê que, por algum motivo, a expansão da macro é executada duas vezes para cada uma das cinco chamadas a serem testadas. A macro é expandida pelo interpretador toda vez que a função TEST é chamada.

Agora vamos compilar a função TEST:

CL-USER 48 > (compile 'test)

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

Você pode ver acima que o compilador executa a macro uma vez.

Se agora executarmos a função TEST, nenhuma expansão de macro ocorrerá. A forma de macro (MY-IF ...) já foi expandida pelo compilador:

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

Se você usou alguns outros Lisps como SBCL ou CCL, eles compilarão tudo por padrão. A SBCL tem em novas versões também um intérprete. Vamos fazer o exemplo acima em uma SBCL recente:

Vamos usar o novo interpretador do 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> 

Você está confundindo dois conceitos diferentes em sua pergunta. As macros não são sobre o código compilar no tempo de execução . Eles são exatamente o oposto: eles são sobre código em tempo de compilação .

Então, em este caso, o problema é o oposto: não se trata de tornar o compilador parte do programa, mas sim de tornar a parte de macro-programa do compilador. Você pode fazer isso incorporando um interpretador no compilador, ou usar a compilação em estágios, onde você compila as macros primeiro, depois as vincula ao compilador e compila o código.

Em seu segundo parágrafo, você pergunta sobre uma coisa diferente, basicamente 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?

Sim, essa é uma possibilidade.

Or is there another way?

Existem outras maneiras:

• em vez de tornar o compilador uma parte do programa, você pode incluí-lo no sistema de tempo de execução
• você não precisa usar o mesmo compilador, você pode usar um compilador diferente (por exemplo, ter um compilador que seja muito grande, muito complexo, muito lento e use uma grande quantidade de memória, mas gere muito pequeno, eficiente, código rápido, de alto desempenho, agressivamente otimizado, e um segundo que você envia no sistema de tempo de execução ou como parte do programa compilado, que é pequeno, simples, rápido, leve, para não "roubar" muitos recursos (tempo de CPU e memória) do programa do usuário, no entanto, pode gerar código menos eficiente
• ou você poderia usar um intérprete e enviá-lo novamente como parte do programa ou como parte do sistema de tempo de execução

Uma típica "compilação de lisp" incluirá o compilador em uma imagem agrupada. Além disso, a maioria das chamadas de função (embora não todas) é feita através de indirecções de símbolos (basicamente, quando o compilador vê (+ a b) , emite código para "find symbol +" e "chama a função para a qual aponta").

Isso significa que a redefinição de função durante a execução do programa é possível gerando código executável, em algum lugar na memória, e então atualiza o ponteiro de função no símbolo que se refere à sua função.

Esta é uma razão pela qual "pequenos binários independentes" gerados a partir de um compilador Common Lisp tendem a ser grandes. No entanto, há uma técnica geralmente chamada de "trepidação de árvore" que pode analisar o programa compilado resultante e remover quaisquer bits da imagem padrão que nunca são referenciados e em tal binário não haveria nenhum compilador incluído, sem capacidade de compilar a execução de código -Tempo. Você ainda pode ter a modificação do código de tempo de execução, carregando outro arquivo (compilado), já que isso pode ser implementado simplesmente em termos de "colocar bytes na RAM, atualizar ponteiros em símbolos".

Sim. O tempo de execução deve incluir um interpretador ou compilador. É por isso que eval é tradicionalmente uma característica de linguagens interpretadas, já que o tempo de execução dessas linguagens (por definição) contém um interpretador de qualquer maneira. Agora, se a linguagem realmente interpreta a fonte ou just-in-time compila e então a executa (use várias etapas intermediárias como um formato de bytecode) - isto é basicamente detalhes de implementação. A linha inferior é que o tempo de execução tem que ser capaz de pegar o código fonte e executá-lo.

Claramente, a geração de código em tempo de execução é incompatível com a compilação anterior. Portanto, o ambiente de tempo de execução de linguagem deve incluir algum mecanismo para executar código dinamicamente: um interpretador ou um compilador just-in-time. Como um intérprete duplicaria o esforço, muitas implementações compiladas de tais linguagens preferem a compilação JIT.

Em qualquer caso, a compilação incremental requer que o código compilado retenha meta-informação suficiente para que o novo código possa ser executado neste contexto. Por exemplo, as variáveis podem não ser otimizadas quando seu escopo inclui uma avaliação. No entanto, isso pode ser facilmente verificado com análise estática durante a compilação do código circundante. Um eval pode ser implementado como uma chamada de ligação tardia para uma função separada que será compilada no tempo de execução. Isso evita ter que alterar o código já compilado.

Este não é apenas um problema com o Lisp. As implementações JITting JavaScript de alto desempenho modernas, como V8 , também precisam lidar com os evals.

Observe que eval, macros e compilação incremental representam o mesmo problema para o propósito desta discussão.

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?

Você diz que não consegue entender como isso é feito e descreve claramente como isso é feito; Eu acho que sua declaração de que você não pode entender é simplesmente falsa. Você entende muito bem.

Isso é exatamente o que eu e meus colegas fizemos ao implementar árvores de expressão em C # 3. Você pode dizer:

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 ei pronto, temos um objeto em tempo de execução que representa

(string p) => p.Length < 10

e quando compilamos:

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

Como o expr.Compile funciona? Eu escrevi um compilador que cospe o novo IL em tempo de execução e o compõe, com base no conteúdo da árvore de expressão. expr.Compile executa um compilador; isso não deve ser muito surpreendente!

Tivemos o benefício distinto de não ter que escrever outro analisador, pois a árvore de expressão já é uma árvore de sintaxe abstrata. Mas se quisesse pegar a string "(string p) => p.Length < 10" e transformá-la nessa árvore de expressão, asseguro que teríamos simplesmente escrito um analisador que produziu a árvore de expressão e depois executá-la através do compilador da árvore de expressão.

É apenas um lote de trabalho; Levei a melhor parte de um ano para conseguir que as lambdas trabalhassem bem. Não há mágica nisso. E é claro que todos nos apoiamos nos ombros dos gigantes; Já ter um tempo de execução, com um mecanismo para cuspir novo IL em tempo de execução e encaixá-lo, era de vital importância para esse recurso.