Interpreter (computing)

An interpreter executes a program's operations according to its programming language semantics. It can recursively evaluate an abstract syntax tree, or follow an instruction sequence using an execution state such as a stack and an instruction pointer. It need not repeatedly read source code characters, and it need not use an abstract syntax tree at all.

Compilation and interpretation can coexist. In CPython, Python source code is compiled into bytecode for execution by an interpreter; its bytecode is not promised to remain stable between releases.^[ref] The Python 3.14 compile function accepts text or an abstract syntax tree and can produce a code object, which eval or exec can execute.^[ref] These operations make translation and execution separately accessible without requiring them to live in different applications.

Just-in-time compilation gives another combination: an interactive implementation can translate a submitted program expression into machine code and then execute it immediately. The LLVM 20.1.0 tutorial demonstrates this by adding an intermediate representation module to its just-in-time compilation facility, looking up the generated function, and calling it.^[ref] Thus calling a programming language permanently "compiled" or "interpreted" hides an implementation choice: ask which representation is translated, which is executed, and when.

An interpreter whose evaluator returns computations in a computational monad. Its semantic equations specify effect order by sequencing, while monad laws support proofs of program equivalence independently of the particular effects.

Use the compilation arithmetic example with input $x=7$. An abstract syntax tree interpreter first reads x, obtains $2+3=5$, forms $7\cdot 5=35$, and finally computes $35-4=31$. Interpreting the folded abstract syntax tree skips the addition but gives the same result. The compiled stack machine instructions instead produce the following trace; the top of the stack is written on the right:

instruction    stack after instruction
initial        []
LOAD x         [7]
PUSH 5         [7, 5]
MUL            [35]
PUSH 4         [35, 4]
SUB            [31]

The order in SUB is essential: reversing its two popped operands would give $4-35=-31$. The same stored instruction sequence works for input $x=-2$, yielding $(-2)\cdot 5-4=-14$, without repeating parsing or constant folding. An abstract syntax tree interpreter can likewise reuse its already-parsed tree. Reusing a representation is therefore useful to both approaches; it does not itself distinguish compilation from interpretation.

The pleasing part is that a nested rooted tree and a flat instruction sequence express the same computation. The structural induction in the compilation arithmetic example connects them by a precise stack property. This tiny language always terminates and has no side effects; richer programming language semantics require a correctness argument that also accounts for failures, externally visible actions, and possible nontermination.