Compiling Datalog Programs by Interpreting Them

Partial evaluation: evaluating part of a program at compile-time; or, the equivalent of solving an algebra expression with what you know at build time and leaving the remaining formula as the program.

Applying partial evaluation to an interpreter is called the "first Futamura Projection."

Paper "compiles" datalog by having Souffle parse and optimize the query to a plan, then repackages the plan as Scala code to ask the compiler to optimize, then translates the optimized scala back to C.

Part of this process involves abstractions added to make code maintainable; partial evaluation then removes as much of the abstraction as possible.