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: 
You are confusing two different concepts in your question. Macros are *not* about *compiling* code at *runtime*. They are the exact opposite: they are about *running* code at *compile time*.

So, in *this* case, the problem is the opposite one: it's not about making the compiler part of the program, rather it is about making the macro-program part of the compiler. You can do *that* by embedding an interpreter in the compiler, or use staged compilation, where you compile the macros first, then link them into the compiler, then compile the code.

In your second paragraph, you ask about a different thing, basically `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?
> 
> 
> 

Yes, that is one possibility.

> 
> Or is there another way?
> 
> 
> 

There are other ways:

* instead of making the compiler a part of the program, you can include it in the runtime system
* you don't have to use the same compiler, you could use a different one (e.g. have one compiler which is very big, very complex, very slow and uses a large amount of memory, but generates very small, efficient, fast, high-performance, aggressively optimized code, and a second one that you ship either in the runtime system or as part of the compiled program, that is small, simple, fast, lightweight, so that it doesn't "steal away" too many resources (CPU time and memory) from the user program, however it may generate less efficient code
* or you could use an interpreter, and again, ship it as part of the program or as part of the runtime system
> 
> 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.