Building effective symbolic execution engines is challenging in multiple dimensions: an engine must \emph{correctly} model the program semantics, provide \emph{flexibility} in terms of various symbolic execution strategies, and execute these strategies \emph{efficiently}.

This paper proposes a principled approach to building \emph{correct}, \emph{flexible}, and \emph{efficient} symbolic execution engines, directly rooted in the semantics of the underlying language expressed as a high-level definitional interpreter. Starting from this definitional interpreter, we use algebraic effects to model the semantics of symbolic execution, e.g., collecting path conditions as a state effect, and exploring multiple paths as a nondeterminism effect. Different handlers of these effects give rise to different symbolic execution strategies which make execution strategies orthogonal to the symbolic semantics, thus improving flexibility. Furthermore, by annotating the symbolic definitional interpreter with binding-times and specializing it to the input program via the first Futamura projection, we obtain a ``symbolic compiler,'' generating efficient code that is instrumented with the symbolic execution semantics. This staging approach reconciles the interpretation- and instrumentation-based approaches to building symbolic execution engines in a uniform framework.

We illustrate the approach for a simple imperative language step-by-step, and then scale up to a significant subset of LLVM IR. We also show effect handlers for a number of common path selection strategies. We evaluate the performance of our prototype and compare with KLEE, showing that the compiled symbolic execution is an order of magnitude faster than the pure interpretation-based counterpart, as well as being on par with KLEE on single execution path traversal.