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: 
A typical "compiling lisp" will include the compiler in a bundled image. Furthermore, most (although not all) function calls are done through symbol indirections (basically, when the compiler sees `(+ a b)`, it emits code to "find symbol +", then "call the function it points to"). 

This means that function re-definition during program execution is possible by generating executable code, somewhere in memory, then update the function pointer in the symbol that refers to your function.

This is one reason why "small free-standing binaries" generated from a Common Lisp compiler tend to be large. However, there's a technique usually called "tree-shaking" that can analyse the resulting compiled program and remove any bits of the standard image that are never referenced and in such a binary there would be no compiler included, with no ability to compile code run-time. You may still be able to have run-time code modification, by loading another (compiled) file, since that can be implemented simply in terms of "put bytes in RAM, update pointers in symbols".
> 
> 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.