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".
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.