Question: There are some programming languages, like the many dialects of Lisp, that allow for macro-metaprogramming: rewriting and altering sections of code before the code is run.

It is relatively trivial to write a simple interpreter for Lisp (mostly because there is only very little special syntax). However, 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?

Answer: 
Clearly, runtime code generation is incompatible with ahead-of-time compilation. Therefore, the language runtime environment must include some mechanism to dynamically execute code: either an interpreter or a just-in-time compiler. Since an interpreter would duplicate effort, many compiled implementations of such languages prefer JIT compilation.

In any case, incremental compilation requires that compiled code retains enough meta-information so that new code can be executed in this context. For example, variables may not be optimized away when their scope includes an eval. However, this can be easily checked with static analysis during compilation of the surrounding code. An eval can then be implemented as a late-bound call to a separate function that is going to be compiled at run time. This avoids having to actually change already-compiled code.

This is not just an issue with Lisp. Modern high-performance JITting JavaScript implementations such as [V8](https://github.com/v8/v8) also have to deal with evals.

Note that eval, macros, and incremental compilation all pose the same problem for the purpose of this discussion.
> 
> 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?
> 
> 
> 

You say you cannot understand how it is done and then clearly describe how it is done; I think your statement that you cannot understand it is simply false. You understand it just fine.

This is exactly what I and my colleagues did when implementing expression trees in C# 3. You can say:

```
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);

```

and hey presto, we have an object at runtime that represents

```
(string p) => p.Length < 10

```

and when we compile it:

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

```

How does `expr.Compile` work? I wrote a compiler that spits out new IL at runtime and jits it, on the basis of the contents of the expression tree. expr.Compile runs a compiler; this should not be too surprising!

We had the distinct benefit of not having to write another parser, as the expression tree is already an abstract syntax tree. But if had wanted to be able to take the string `"(string p) => p.Length < 10"` and turn it into that expression tree, I assure you we would have simply written a parser that produced the expression tree, and then run that through the expression tree compiler.

It's just a *lot* of work; it took me the better part of a year to get lambdas all working right. There's no magic to it. And of course we all stand on the shoulders of giants; already having a runtime, with a mechanism for spitting out new IL at runtime and jitting it, was of vital importance to this feature.