WorksComputer Science
Python Code Generation for Isabelle/HOL
Abstract
The Isabelle theorem prover provides an environment for formalising mathematics and reasoning about programs. To make verified implementations practically usable, its code generator translates functions expressed in the executable fragment of its logic into conventional programming languages. Its targets have traditionally been functional languages (Standard ML, OCaml, Haskell, and Scala), recently joined by Go. Python, which is becoming the dominant language of scientific computing, data science, and education, has remained out of reach. In this work, we close this gap with a Python backend for Isabelle's code generator. This generator enables verified algorithms to be used in Python applications, or to serve as verified references against which established Python libraries can be differentially tested, without leaving the Python ecosystem. We validate the backend on regression suites covering large parts of the HOL library and by testing six verified data structures and algorithms against established Python libraries. The generated code is slower than hand-written libraries, but well suited as a verified reference.
2012 ACM Subject Classification Software and its engineering; Theory of computation → Logic and verification; Software and its engineering → Software testing and debugging
Keywords and phrases Isabelle/HOL, code generation, Python, interactive theorem proving, differential testing
Supplementary Material Software: https://doi.org/10.5281/zenodo.24106993 [15]
Funding This research received financial support from Schmidt Sciences and Bloomberg.
Acknowledgements We thank the Institute of Computing for Climate Science for providing a supportive working environment. Anthropic’s Claude was utilised during the design of the code generator backend, particularly for helping with the integration into the wider Isabelle framework, as well as for planning out and generating sections of the code.
Introduction
Isabelle/HOL [27] is an interactive theorem prover (ITP) based on higher-order logic (HOL), a typed -calculus with polymorphism and type classes. The user of Isabelle/HOL creates theory files, which can include datatype and type class declarations, inductive definitions, and functions. A fragment of HOL is executable, which means that it can be evaluated inside Isabelle, and also translated into programs in conventional programming languages. Isabelle’s code generation framework was reimplemented by Florian Haftmann in his PhD thesis [12, 13], replacing an earlier design [3], and has since featured a more modular setup, in which parts of the generator can be shared by different language backends. Traditionally, these backends covered functional programming languages, such as Standard ML, OCaml, Haskell, and Scala, as their evaluation schemes are also (at least loosely) based on the -calculus. Recently, another backend [32] for the programming language Go has been added, which for the first time allowed generating code in an imperative programming language.
Python is arguably one of the most widely used programming languages right now. It has ranked among the top ten of the TIOBE index for two decades, and has held first place since October 2021 [36]. Its usage covers almost all areas of computing, and includes scientific computing, data science, machine learning and AI, scripting, automation, testing, and web backends. It is also one of the most widely used programming languages in education, and often the first language students learn. However, Python is still not a common target for code generation from ITPs. To close this gap, we implemented a Python backend for Isabelle’s code generator. We hope that the possibility of dropping verified implementations of core algorithms into established Python applications will lower the barrier to adopting verified code. Moreover, generated code can serve as a verified reference against which existing Python libraries can be tested.
Several of Python’s design choices simplify code generation from HOL. Its integers have arbitrary precision, matching HOL’s int, and its match statement expresses most of HOL’s patterns directly. Since Python is dynamically typed, polymorphism and type classes need not be fitted into a static type system. Python, however, raises obstacles of its own: CPython, the reference implementation of the Python language [29], limits recursion depth and does not eliminate tail calls, closures capture variables rather than values, and if/else and pattern matching are statements, not expressions. § 3 describes how the backend addresses these issues.
In summary, this paper makes the following contributions:
A Python backend for Isabelle/HOL’s code generator, available as an Isabelle component (§ 3).
A library setup that maps HOL types to native Python equivalents, while preserving HOL’s semantics where Python’s built-in operations differ (§ 3.6).
A validation of the backend using regression suites covering large parts of the HOL library, together with a performance evaluation on CPython and PyPy (§ 4).
A demonstration that generated code can serve as a verified reference for testing established Python libraries, through differential testing of six verified data structures and algorithms, including against SymPy’s Hermite and Smith normal form implementations (§ 4).
The code for the backend is publicly available [15] under an open-source licence. The rest of this paper is structured as follows. § 2 introduces Isabelle’s code generator and Python as a target language. § 3 presents the translation of HOL constructs to Python, including the library setup for native types and the translation of tail calls into loops. § 4 validates the backend and evaluates its performance. § 5 surveys related work, § 6 discusses limitations and future work, and § 7 concludes.
Background
The Isabelle Code Generator
Figure 1 shows the overall pipeline of generating code from an Isabelle/HOL theory. A user implements functions and datatypes through different Isabelle/HOL definitions. These definitions give rise to code equations, i.e., equations whose left-hand sides pattern-match on datatype constructors. Code equations are typically derived from definitions in the executable fragment of HOL, but even certain non-executable definitions, such as inductive predicates, can be turned into code equations through additional translations [2]. After a preprocessing step that rewrites the equations, they are translated into a small intermediate language called Thingol [13]. Thingol is an ML-like functional language extended with type classes.

Figure 1. The Python backend within the Isabelle code generator. Code equations are translated into a Thingol program, which the new serialiser prints as a Python module, guided by the code_printing declarations of the library setup theories. The existing serialisers share the same front end (greyed out).
Its programs consist of datatypes, type classes and their instances, and functions defined by pattern-matching equations over constants, applications, abstractions, and case expressions. The translation from Isabelle/HOL to Thingol is part of the Isabelle distribution and is shared by all code generation backends.
Each language-specific backend is a serialiser, which translates each Thingol construct into a corresponding construct of the target language and prints the result. By default, the code originating from each theory becomes a separate Python module; alternatively, all code can be collected in a single module.
Part of the generation is controlled by theory files that set up the generation of Python code for specific HOL types and constants through dedicated code_printing declarations. This is further explained in § 3.6.
Since code equations are proven theorems, the generated code is correct with respect to the HOL definitions in the sense of partial correctness, provided that the serialiser and the code_printing declarations are correct; both are part of the trusted code base. A fully verified translation is possible, as demonstrated by the CakeML code generator [16], at the cost of considerably more effort. We return to this in § 6.
Python as a Target
At first glance, Python might seem an odd choice as the target for a code generator from a functional intermediate language such as Thingol. However, several of its design choices actually help during translation.
Dynamic typing. Python does not rely on a type checker to verify type correctness before execution. This greatly simplifies the translation of polymorphic functions, as parametric polymorphism is essentially free. Type classes, however, still require explicit dictionaries, and type errors in the generated code only surface when it is executed.
Pattern matching and dataclasses. While Python does not offer true algebraic data types, it does include dataclasses, which can be frozen to make instances immutable. Frozen dataclasses also automatically implement structural equality and hashing. Since Python 3.10, the language additionally includes structural pattern matching through match/case statements [4], and dataclass instances can be matched on in order to access their fields, as in case Some(n). This allows us to express most of Thingol’s pattern matching directly, without transforming it into nested conditionals.
Integers and functions. Python’s integers have arbitrary precision, matching HOL’s integer semantics without additional library support, as is needed in other backends such as OCaml. Even though Python is predominantly an imperative language, it offers anonymous functions through lambda expressions and treats functions as first-class values. However, Python also has idiosyncrasies that have to be dealt with during translation.
Statements and expressions. Unlike the functional target languages, Python distinguishes between expressions and statements, and putting a statement where an expression is expected (e.g., as the body of a lambda) leads to a syntactically ill-formed program. In particular, match, if, and assignments are statements, which § 3 accounts for.
Recursion. CPython does not eliminate tail calls. Together with its default recursion limit of 1000 stack frames, this quickly leads to errors, as Thingol does not include a loop construct and relies on recursion instead. § 3.7 shows how we handle simple cases of tail calls.
Division. Python raises an exception on division by zero, whereas HOL defines a div 0 = 0 and a mod 0 = a. The library setup in § 3.6 preserves HOL’s semantics.
x = 1
f = lambda: x
x = 2
print(f()) # prints 2, not 1
Late binding. A design choice that can surprise even seasoned programmers is Python’s late binding of variables. Take, for example, the program in Figure 2, where the variable x is bound late (after the definition of f), and therefore the output of the fragment is 2 rather than 1. Closures thus capture variables, not values, which must be accounted for when turning recursion into loops (§ 3.7).

Figure 2. Late binding in Python: the closure f looks up x when it is called, not when it is created.
Translating Thingol to Python
The translation from Thingol to Python happens in two phases. First, we translate the Thingol constructs into an internal representation of the corresponding Python definitions; then we pretty-print those definitions, taking care of Python’s indentation-based syntax.
To illustrate how HOL constructs are translated, we use the small example theory in Figure 3. It describes binary search trees with datatype tree = Leaf | Node ( tree) ($\alpha$ tree): a tree is either a Leaf or a Node l x r with left subtree l, value x, and right subtree r.
Figure 3. Running example: binary search trees in Isabelle/HOL (abridged, and without the quotation marks around terms and types).
The function ins is the standard insertion into a search tree. The type annotation ::linorder on its first argument restricts to instances of the sort linorder, i.e., to linearly ordered types. The function root_or returns a singleton list containing the value at the root of a tree, or a default value if the tree is a Leaf. It is introduced with definition, which defines a constant by a single, non-recursive equation, whereas fun allows recursive definitions by pattern matching over several equations, as in ins. The higher-order function fold_tree folds over a tree, and from_list builds a tree by repeatedly inserting the elements of a list.
Finally, the type class weight declares a single operation calc_weight :: ⇒ nat, which assigns a natural number to each value of an instance type. The instance for nat takes a number as its own weight. The instance for trees is parametric: tree :: (weight) weight states that tree is an instance of weight whenever is, and defines the weight of a tree as the sum of the weights of its elements, computed with fold_tree. The constant example_weight applies calc_weight to a tree whose single element is itself a tree of natural numbers, i.e., to a value of type nat tree tree. Evaluating it therefore requires both instances: the instance for trees at the outer and at the inner level, and the instance for nat for the innermost elements.
We will now demonstrate the translation of the various parts of this example theory, showing the generated Python code for each. Note that we have slightly simplified the presented Python code for brevity and readability: we removed redundant parentheses, renamed variables, merged nested conditionals into elif, and omitted the fallback cases discussed in § 3.1. Unless stated otherwise, the examples use the full setup described in § 3.6.
datatype α tree = Leaf | Node (α tree) α (α tree)
fun ins :: (α::linorder) ⇒ α tree ⇒ α tree where
ins x Leaf = Node Leaf x Leaf
| ins x (Node l y r) =
(if x < y then Node (ins x l) y r
else if y < x then Node l y (ins x r)
else Node l y r)
definition root_or :: α ⇒ α tree ⇒ α list where
root_or d t = [case t of Leaf ⇒ d
| Node _ x _ ⇒ x]
fun fold_tree :: (β ⇒ α ⇒ β ⇒ β) ⇒ β ⇒ α tree
⇒ β where
fold_tree f e Leaf = e
| fold_tree f e (Node l x r) =
f (fold_tree f e l) x (fold_tree f e r)
definition from_list :: (α::linorder) list
⇒ α tree where
from_list xs = foldr ins xs Leaf
class weight = fixes calc_weight :: α ⇒ nat
instantiation nat :: weight begin
definition calc_weight_nat :: nat ⇒ nat where
calc_weight_nat n = n
instance .. end
instantiation tree :: (weight) weight begin
definition calc_weight_tree :: α tree ⇒ nat where
calc_weight_tree =
fold_tree (λl x r. l + calc_weight x + r) 0
instance .. end
definition example_weight :: nat where
example_weight =
calc_weight (Node Leaf
(Node Leaf (7::nat) Leaf) Leaf)
Datatypes
The datatype tree is translated into one dataclass per constructor, as shown in Figure 4. The nullary constructor Leaf has no fields, while Node has three, one for each constructor argument. Each field is annotated with Any: dataclasses require an annotation, but Python does not check annotations at run time, so polymorphic datatypes need no special treatment. The price is that static type checkers such as mypy [17] cannot check the generated code, whose type correctness therefore rests on the code generator alone. We revisit this design choice in § 6.

Figure 4. The datatype tree from Figure 3 translated to one frozen dataclass per constructor.
@dataclass(frozen=True)
class Leaf:
pass
@dataclass(frozen=True)
class Node:
a: Any
b: Any
c: Any
Each dataclass is declared with frozen=True, which makes its instances immutable and generates structural equality (==) and hashing. Immutability matters because functional data structures are persistent: an update must leave older versions intact. Since we neither create a common base class (e.g., class tree) nor use precise type annotations, the generated code does not reflect that tree is closed, i.e., that Leaf and Node are its only constructors. Consequently, the backend ends every match whose last case is not a catch-all with a fallback case that raises an error. For readability, we omit this case in the figures of this section; we discuss it in § 6.
Constructor arguments are unnamed in Isabelle/HOL, so the generated fields get systematic names (a, b, c). These names are irrelevant for pattern matching, as dataclasses support positional class patterns, e.g., case Node(l, x, r).
Nullary constructors are instantiated anew at every use, as in Node(Leaf(), x, Leaf()). This is semantically harmless, because equality is structural, and it allows uniform class patterns.
Functions and Pattern Matching
Functions, introduced through fun or definition (among others), are translated depending on their inner structure. Those with a single equation that does not pattern-match on its arguments are translated to a plain def in Python, such as root_or in Figure 6. A definition without any arguments and without sort constraints (i.e., a constant), such as example_weight in Figure 13, is translated into a cached function without parameters (§ 3.5).

Figure 6. Translation of root_or: the case expression nested inside the list is hoisted out of it.

Figure 13. The instance of weight for nat and the constant example_weight: both are evaluated only once.
Multi-equation functions compile to a match over the tuple of input arguments with one case per equation. This can be seen in the translation of ins in Figure 5. In the generated code, we match over the input value x and the old tree t. The first equation ins x Leaf then turns into case (x, Leaf()). This illustrates the uniform class patterns mentioned in the previous subsection: Leaf() is written identically in patterns and expressions. A shared singleton object would avoid allocating a new Leaf() at each use and would still match the class pattern Leaf(); we return to this in § 6.

Figure 5. Translation of ins, a function defined by multiple equations.
def ins(d, x, t):
match (x, t):
case (x, Leaf()):
return Node(Leaf(), x, Leaf())
case (x, Node(l, y, r)):
less = (d.order_linorder.preorder_order
.ord_preorder.less)
if less(x, y):
return Node(ins(d, x, l), y, r)
elif less(y, x):
return Node(l, y, ins(d, x, r))
else:
return Node(l, y, r)
The additional argument d is the instance dictionary for the linear order. We use it to perform the comparison less when inserting the value x into the tree. This uses the well-known dictionary passing [39, 14] technique for compiling type classes, also used by the Standard ML, OCaml, and Go backends, as none of these languages has native type classes either. Thingol already makes explicit which dictionary is passed where, so the backend only has to print these instance dictionaries. The comparison less belongs to the superclass ord of linorder, which is reached through a chain of superclass dictionaries (§ 3.4).
def root_or(d, t):
match t:
case Leaf():
x = d
case Node(_, y, _):
x = y
return [x]
A more interesting example is the translation of root_or, which has a case inside a list constructor. The case expression is turned into a match in Python, which itself is a statement and not an expression, and therefore cannot be used inside a Python list constructor directly. The backend converts the term to A-normal form [10]: it hoists the match before the list construction, and assigns the result of each branch to a new temporary variable x, which the return then places in the list.
To embed a statement in an expression, the Go backend takes a different approach: it wraps the statement in an anonymous function that is called immediately [32]. Python could emulate this with a nested def that is called in place, but hoisting avoids the additional function definition and call.
Care is needed with the short-circuiting connectives , , and , which we print as Python’s equally short-circuiting and and or (Figure 7). Their right operand is only evaluated if the left one does not already determine the result, e.g., hd xs in xs \ne [] \land hd xs = 0 is never evaluated for the empty list.
However, hoisting a case out of the right operand would break this, as the hoisted statement runs unconditionally. If the right operand contains a case, we therefore translate the connective into nested matches (see fig:8, where a trivial match on a Boolean has been simplified to an if, as linters would otherwise flag it).
definition conj_eq :: nat list ⇒ bool where
conj_eq xs = (xs ≠ [] ∧ hd xs = 0)
def conj_eq(xs):
return not null(xs) and hd(xs) == 0
fig:7 A conjunction is printed as Python’s short-circuiting and.
definition conj_case :: nat list ⇒ bool where
conj_case xs =
(xs ≠ [] ∧
(case hd xs of 0 ⇒ True | Suc _ ⇒ False))
def conj_case(xs):
if not null(xs):
if hd(xs) == 0:
x = True
else:
x = False
else:
x = False
return x
fig:8 A conjunction whose right operand contains a case expression is turned into a conditional, so that hd xs is only evaluated for non-empty lists.
Higher-Order Functions and Partial Application
As functions are first-class values in Python, translating higher-order code is fairly straightforward. However, Isabelle/HOL is curried, whereas Python passes all arguments of a call at once.
Calls that supply all arguments of a known constant are printed as ordinary calls with multiple arguments, such as the recursive call fold_tree(f, e, l) in fig:9. Parameters such as f, however, are applied to one argument at a time.
def fold_tree(f, e, t):
match (f, e, t):
case (f, e, Leaf()):
return e
case (f, e, Node(l, x, r)):
return (f(fold_tree(f, e, l))(x)
(fold_tree(f, e, r)))
fig:9 Translation of fold_tree: the parameter f is applied to one argument at a time.
Conversely, a constant that receives fewer arguments than it expects is turned into a curried form using nested lambdas, as in from_list (Figure 10). Here, the first argument to foldr is ins, partially applied to the instance dictionary d, which still expects the value x to insert and the old tree t. foldr itself comes from Isabelle/HOL’s List theory, which the code generator includes automatically, as from_list depends on it. Its defining equations only take the operation and the list as arguments and return a closure that expects the start value, so the generated foldr has two parameters, and Leaf() is passed to its result.
def from_list(d, xs):
return foldr(lambda x: lambda t: ins(d, x, t),
xs)(Leaf())

Figure 10. Translation of from_list: the partially applied ins becomes a curried lambda.
Type Classes
We have already seen that sort constraints become dictionary arguments, such as d in ins. We now turn to how these dictionaries are defined and built.
Each type class becomes a frozen dataclass with one Callable field per operation and one field per superclass, which holds the dictionary of that superclass (Figure 11). For weight, the dataclass has a single field calc_weight.

Figure 11. The type class weight from Figure 3 as a dictionary type.
@dataclass(frozen=True)
class weight:
calc_weight: Callable
Each instance becomes a function that returns its dictionary. The parametric instance for trees, weight_tree, takes the dictionary for the element type as its argument d (Figure 12). In example_weight, the dictionary for nat tree is thus weight_tree(weight_nat()), which is passed to calc_weight_tree, the implementation of calc_weight for trees (Figure 13). Instances that take no dictionary arguments, such as weight_nat, are cached, as we describe in § 3.5.
Figure 12. The parametric instance of weight for trees.
# instance method for tree
def calc_weight_tree(d, t):
return fold_tree(lambda l: lambda x: lambda r:
l + d.calc_weight(x) + r, 0, t)
# returns tree instance of class weight
def weight_tree(d):
return weight(
calc_weight =
lambda a: calc_weight_tree(d, a))
Superclass projections become chains of attribute accesses. In ins (Figure 5), the comparison less belongs to the class ord, which linorder extends via order and preorder; it is therefore reached as d.order_linorder.preorder_order.ord_preorder.less. Each step of the chain selects the dictionary of the next superclass, so deeper class hierarchies only lead to longer chains and need no further support from the backend.
Certain sort constraints (such as linorder in ins) are used only to select the correct comparison function for the respective type. For native types like int, we could use Python’s comparison operators directly instead. We comment on this in § 6.
Caching
A constant without arguments is not translated into a module-level variable, but into a function without parameters, which is called wherever the constant is used, as for example_weight in Figure 13. Importing a generated module therefore evaluates nothing. Modules follow theories, and code equations may refer to constants of later theories, so generated modules can import each other cyclically; reading a value of a module that is still being imported would fail.
To still evaluate each value only once, the backend decorates these functions with @functools.cache. The same applies to instances that take no dictionary arguments, such as the instance of weight for nat, whose dictionary is thus built only once. Caching can be switched off with the option python_cache; we discuss its effect on performance in § 4.3.
@functools.cache
def weight_nat():
return weight(
calc_weight =
lambda a: calc_weight_nat(a))
@functools.cache
def example_weight():
return calc_weight_tree(
weight_tree(weight_nat()),
Node(Leaf(),
Node(Leaf(), 7, Leaf()),
Leaf()))
Library Setup and Native Types
Like the Go backend, our backend consists of two parts. The first part takes care of the general translation of Thingol into Python, and is written in Isabelle’s own implementation language Standard ML. The second part is an Isabelle/HOL theory, which loads this translation code and introduces code_printing declarations that map HOL types and constants to their Python counterparts. We provide two such setup theories, which a user of our backend can choose from. As code_printing declarations are part of the trusted code base, the basic setup requires less trust.
In the basic setup, we only cover the essential parts of HOL, roughly Booleans, the unit type, and strings; numbers are represented by HOL’s own datatypes, i.e., natural numbers in Peano encoding and integers in binary. This already allows generating code from a large part of the HOL library. All other types are translated like any other datatype; in particular, lists become the dataclasses Nil and Cons rather than Python lists (Figure 14).

Figure 14. Lists with the basic setup: they are translated like any other datatype, and list literals become nested constructor calls.
The full setup extends this with additional code printings: integers and natural numbers are mapped to Python’s native integer type, and HOL lists and tuples to their native Python counterparts. For lists, the function snoc from Figure 14 then operates on Python lists (Figure 15). A third, optional theory maps immutable arrays (iarray) to Python tuples, which gives constant-time indexing.

Figure 15. The function snoc from Figure 14 with the full setup: HOL lists are mapped to Python lists.
Python’s arbitrary-precision integers already match HOL’s integer semantics closely.
fun snoc :: α list ⇒ α ⇒ α list where
snoc [] y = [y]
| snoc (x # xs) y = x # snoc xs y
@dataclass(frozen=True)
class Nil:
pass
@dataclass(frozen=True)
class Cons:
a: Any
b: Any
def snoc(xs, y):
match (xs, y):
case (Nil(), y):
return Cons(y, Nil())
case (Cons(x, xs), y):
return Cons(x, snoc(xs, y))
def snoc(xs, y):
match (xs, y):
case ([], y):
return [y]
case ([x, *xs], y):
return [x] + snoc(xs, y)
However, HOL is total, and as such x div 0 is defined as 0, and x mod 0 as x. To align the semantics, we include a custom printer for these two operators (Figure 16).

Figure 16. Custom code printing for div and mod on integers in the full setup.
code_printing
constant (div) :: int ⇒ int ⇒ int ⇀ (Python)
"(lambda a, b: a // b if b else 0)(_, _)"
| constant (mod) :: int ⇒ int ⇒ int ⇀ (Python)
"(lambda a, b: a % b if b else a)(_, _)"
Similarly, subtraction on natural numbers is printed as max(0, a - b), as HOL’s subtraction on nat is truncated at 0, whereas Python’s integers would become negative.
HOL’s option type datatype α option = Some α | None does not receive a custom printer and is translated like any other datatype. Unwrapping Some, so that Some x becomes x and None becomes Python’s None, would not be injective, as Some None and None would both map to None. The backend’s documentation lists all custom printings.
Tail Calls as Loops
Purely functional programming languages, like Thingol, have no loop construct and rely on recursion instead. To avoid the stack growth of deep recursion, many functional languages use tail-call elimination: a call that is the last operation of a function reuses the current stack frame, as nothing is left to do in the current context once it returns.
CPython does not eliminate tail calls and has a default recursion limit of only 1000 stack frames, so even simple functions that recurse over lists raise a RecursionError on fairly modest inputs. Take, for example, the function sum_acc in Figure 17, which sums the elements of a list using an accumulator. Its default translation recurses once per list element, and therefore fails for lists of 1000 elements.
Figure 17. A tail-recursive function and its default translation, which recurses once per list element.
fun sum_acc :: int list ⇒ int ⇒ int where
sum_acc [] acc = acc
| sum_acc (x # xs) acc = sum_acc xs (acc + x)
def sum_acc(xs, acc):
match (xs, acc):
case ([], acc):
return acc
case ([x, *xs], acc):
return sum_acc(xs, acc + x)
To support deep tail recursion, the backend can optionally turn self tail calls into loops. The body of the function is then wrapped inside a while True: loop. Whenever the function calls itself in tail position, the arguments are reassigned instead, and continue jumps back to the beginning of the loop (Figure 18). The reassignment is simultaneous, so that all new arguments are computed from the old ones. The transformed function therefore no longer grows the stack, however long its input is.

Figure 18. The function from Figure 17 after the transformation: the self tail call becomes a loop.
def sum_acc(xs, acc):
while True:
match (xs, acc):
case ([], acc):
return acc
case ([x, *xs], acc):
xs, acc = xs, acc + x
continue
The transformation only applies to direct self tail calls; recursive calls in other positions, and mutual recursion, are left unchanged. Moreover, a function whose recursive call creates a closure remains recursive: as Python closures capture variables rather than values (Figure 2), a closure created in one iteration would observe the reassignments of the next. For such functions, users can raise the recursion limit with sys.setrecursionlimit (see also § 6).
Name Resolution
Python’s reserved words (e.g., def, case, while) and the built-in functions used by our library setup (e.g., len, map) are reserved, so the code generator never uses them as identifiers. Top-level name clashes are resolved with trailing underscores, following PEP 8 [38].
Evaluation
For evaluation, we look at three different but somewhat interconnected questions:
(RQ1) Does the backend accept a broad range of real Isabelle/HOL theories and produce valid Python code from them?
(RQ2) Does the generated code behave as expected?
(RQ3) How does the performance of generated code compare to hand-written Python code, and does the specific Python runtime that is used matter?
Regression Test Suites (RQ1)
Isabelle already contains a test session to stress-test existing backends. We adapted the test setup of the Go backend [32], which draws in a significant part of the full HOL library; our version generates Python code for both the basic and full setup described in § 3.6. This results in about 200 Python modules per setup, with roughly 50,000 lines of code in total. We check each generated Python module for syntactic correctness by compiling it with CPython (py_compile). For both setups, our backend produces syntactically valid Python code. As the session contains no unit tests, this does not cover execution behaviour.
Differential Testing (RQ2)
The regression suites only show that the generated code is syntactically valid. To check its behaviour, we use two forms of differential testing.
First, we extract over 200 small Isabelle examples to Standard ML and Python, run both, and compare the outputs. All tests pass, assuming the Standard ML backend is correct.
Second, we test verified data structures and algorithms from the AFP [1, 25, 7, 6] and Isabelle/HOL’s functional data structures library [26] against established Python libraries (Table 1). Each harness feeds the same random inputs, generated with Hypothesis [20], to both sides and compares the results; for data structures, it runs 300 random sequences of up to 60 operations, checking agreement after every step. No mismatch was found, which also indicates that the libraries agree with the verified specifications on the tested inputs.
| Harness | Isabelle source | Library |
| Splay tree | AFP Splay_Tree | SortedDict |
| RBT map | HOL-DS RBT_Map | SortedDict |
| Leftist heap | HOL-DS Leftist_Heap | heapq |
| Binomial heap | HOL-DS Binomial_Heap | heapq |
| Hermite NF | AFP Hermite | SymPy |
| Smith NF | AFP Smith_Normal_Form | SymPy |
Table 1. Differential test harnesses.
Verified Isabelle components can thus serve as test oracles for Python code, or be generated into Python and used directly, if performance permits (§ 4.3).
Performance (RQ3)
For the testing harnesses presented above, we investigated the performance of each generated code module, and compared it to the respective established Python library. We compared performance side by side on equivalent tasks, for example: insert keys into a map, look all of them up, delete half of them, and list the remaining entries; insert elements into a heap, and then remove them one by one; apply normal form algorithms to a random integer matrix. We compare two current implementations of Python, the reference interpreter CPython (version 3.14.6), and PyPy (version 7.3.23).
CPython is arguably the most widely used implementation of the Python language, and uses a bytecode interpreter under the hood. PyPy relies on JIT compilation to translate frequently executed routines to machine code in order to speed up execution along hot paths. All experiments were run on a MacBook Pro M4 Max with 36 GB of RAM.
For each input size, we report the median of 15 timed runs, preceded by 10 untimed warm-up runs to let PyPy’s JIT compiler settle. The interquartile range, i.e., the spread of the middle half of the runs (25th–75th percentiles), is shown as shaded bands around the median line in Figure 19. We use the interquartile range rather than the standard deviation, as run times are skewed by occasional slow runs, e.g., due to garbage collection or JIT compilation.
Figure 19. Generated verified references vs. Python libraries on CPython 3.14.6 and PyPy 7.3.23. Top: median time against input size (log-log). Bottom: slowdown at the largest size both sides completed. Grey dotted: references built without caching.
Unsurprisingly, the generated code is slower than the hand-written libraries (Figure 19). For the four data structures, performance of generated code scales similarly to that of the equivalent native Python libraries, but is – slower on CPython. JIT compilation seems favourable for the code we are generating, as the performance gap is much smaller when running PyPy, at –. The Hermite normal form shows a similar picture ( and at ). The Smith normal form is the outlier, with slowdowns of on CPython and on PyPy: the formalisation implements a generic algorithm for Euclidean domains on top of a general matrix library, whose run time also grows faster with the matrix size than SymPy’s.
The grey dotted lines in Figure 19 show the references built without caching (§ 3.5). For the data structures, caching makes little difference: at the largest size, it speeds them up by – on CPython, and on PyPy, the difference (–) is within the measurement noise. The matrix algorithms, which repeatedly use constants and dictionary-free instances, profit considerably: at , caching speeds up the Hermite normal form by on CPython and on PyPy, and the Smith normal form by and .
We believe that the exhibited slower performance is due to four reasons:
Operational overhead. The generated code relies heavily on recursive function calls, which are expensive in Python. Furthermore, pattern matching is used throughout, which functional language runtimes or compilers often optimise into fast decision trees [22], while Python’s match dynamically dispatches each case distinction. Table 2 shows the number of calls performed by the generated and the library code for each harness on one example input. It clearly shows the call overhead on all examples.
| Benchmark | Size | Generated Calls | Generated Objects | Library Calls | Ratio |
| splay_tree | 1,000 | 305k | 129k | 12k | 25 |
| rbt_map | 1,000 | 223k | 104k | 12k | 19 |
| leftist_heap | 1,000 | 120k | 45k | 2.0k | 60 |
| binomial_heap | 1,000 | 129k | 23k | 2.0k | 65 |
| hermite | 21k | 9 | 1.9k | 11 | |
| smith | 1.1M | 73k | 2.5k | 447 |
Table 2. Function calls for one run of each workload, generated vs. library (CPython). Objects: dataclass instances created by the generated code. The ‘Ratio’ column is the ratio of generated calls to library calls.
Immutability. We rely on immutable data structures, and therefore most of the operations we perform have to allocate new objects on the heap on every update, while hand-written code can update objects on the heap directly. This comes from the shift in paradigm, from functional Thingol to imperative Python. The Objects column in Table 2 shows the number of dataclass instances created by the generated code. For some tests (e.g., splay_tree, rbt_map) this amounts to over of the overall calls. This even includes constructors without arguments: each comparison in the red-black tree, for instance, returns a fresh instance of LT, EQ, or GT.
Type classes. Comparisons and arithmetic in the verified code are generic over type classes. Instead of performing x < y on two integers, the code therefore looks up the comparison in a dictionary argument and calls it, sometimes through nested lambdas for partial application.
In the red-black tree, for instance, each comparison becomes d[1].order_linorder.preorder_order.ord_preorder.less(x, y). The libraries compare native values directly.
Native library code. On CPython, heapq is implemented in C, and SortedDict relies on Python’s built-in lists, whose operations are also implemented in C. This explains why the heaps show the largest slowdowns on CPython. PyPy, in contrast, runs heapq as ordinary Python code, and the gap for the leftist heap shrinks to .
Overall, this makes code generation with our backend more suitable for differentially testing against established libraries than for using generated code directly inside applications where performance is important. While closing the performance gap completely will likely remain impossible, we highlight some opportunities for optimisation in § 6.
Threats to Validity
As already mentioned in § 3.6, much of the code generation pipeline is part of the trusted code base, and can only be validated through proper testing. While the agreement in behaviour between the generated code for various data structures and algorithms and established Python libraries gives a strong indication of correctness, certainty can only be achieved if the whole pipeline is verified down to the extracted Python code. We will remark on a possible future extension towards a verified Python backend in § 6.
Differential testing can only reveal disagreements on the inputs it generates; it cannot prove their absence. Our selection of case studies focuses on functional data structures and integer linear algebra, and does not cover, e.g., floating-point or rational arithmetic. Finally, all performance measurements were taken on a single machine, and parts of the compared libraries are implemented in C, so the slowdowns reflect both the generated code and the implementation language of the libraries.
Related Work
Isabelle backends. The standard Isabelle distribution ships with four code generation backends [13], targeting Standard ML, OCaml, Haskell, and Scala. The design is modular, so additional backends can be added, reusing parts of the overall generator pipeline. Recently, a new backend was added for the Go language [32], which is now also part of the Archive of Formal Proofs [31]. Go was the first non-functional programming language added as a target, and thereby paved the way for other imperative language backends, such as the one we present in this paper. While we have taken inspiration from the Go backend, certain peculiarities of Python also required different design choices. For example, while pattern matching translation is easier in Python, as it features a dedicated match statement, statement hoisting is different, as Python does not strictly follow static scoping rules.
Other provers and languages. Other interactive theorem provers offer code generation from verified formalisations as well. Rocq [35] can extract code to OCaml, Haskell, and Scheme [19]. Lean 4 [24] compiles to C. Nerodia, a fairly new project, is a foreign function interface that allows writing native Python modules in Lean [21]. The programming language Dafny [18] already has a Python backend. Most of the code expressed in Dafny is imperative and can be mapped directly to equivalent Python. Pulse [8], a proof-oriented language embedded in F* [33], allows extraction of programs to OCaml, C, and Rust.
Overall, very few provers or languages targeting verified implementations currently cover Python.
Python verification. There are multiple tools which cover verification of Python code directly. These range from type checkers such as mypy [17] to full static verifiers like Nagini [9]. These are complementary approaches, where Python code is verified post hoc, while our approach relies on generating code from verified models.
Testing. Differential testing [23] compares several implementations of the same specification on the same inputs, and property-based testing, as introduced by QuickCheck [5] and available for Python through Hypothesis [20], generates these inputs randomly. We combine both, with the difference that one of the compared implementations is generated from a verified formalisation, and thus serves as a reference for the established library.
Limitations and Future Work
Recursion depth. Only direct tail calls of a function to itself are translated into loops (§ 3.7). Mutual recursion and recursion that is not in tail position still consume Python stack frames, and deep inputs, such as long lists, run into CPython’s recursion limit. Trampolining [11], as used by compilers to targets without tail-call elimination [34, 30], possibly combined with a transformation into continuation-passing style [10], would lift this restriction, at the cost of further overhead per call.
Performance. § 4.3 shows that the generated code is considerably slower than hand-written libraries. Some of the overhead can be avoided within the backend: constructors without arguments, such as LT, EQ, and GT, could be shared instances instead of being created anew for every use, and type-class dictionaries for instances that are known at code generation time could be specialised away, so that, e.g., a comparison on integers becomes Python’s native <. Native lists also come at a cost: patterns such as [x, *xs] and concatenation ([x] + xs) copy the list, which makes linear recursion over a list quadratic. A persistent list representation, or offering both encodings, would avoid this. Finally, mapping further HOL constants to Python built-ins in the full setup could reduce the overhead, but also enlarge the trusted code base.
Type annotations. The generated code currently carries no type annotations beyond the fields of dataclasses. Generating annotations according to PEP 484 [37] would improve integration with IDEs and allow static checking with tools such as mypy [17]. Describing each datatype as a closed union of its constructors would also make the fallback cases described in § 3.1 unnecessary, as a static type checker could then verify that the patterns are exhaustive. Extending our code generator to include type annotations is left for future work.
Further types and code. The full setup maps integers and natural numbers to Python’s int, but does not cover rat or real yet; rationals could be mapped to Python’s fractions.Fraction. Monadic code in Imperative HOL, which works on a mutable heap, could be mapped to mutable Python objects. This would avoid copying in data structures that are updated in place, and address some of the performance losses due to immutability described in § 4.3.
Verified backend. Like the other serialisers of Isabelle’s code generator, our backend is part of the trusted code base. Hupel and Nipkow showed for CakeML how this gap can be closed with a verified compiler from Isabelle/HOL [16]. The code we generate largely targets PurePy [28], a pure, functional subset of Python, which is designed to have a formal semantics. Proving the translation into PurePy correct would make a verified pipeline from Isabelle/HOL down to Python possible, following the approach of Hupel and Nipkow.
Conclusion
In this paper, we have presented a Python backend for Isabelle/HOL’s code generator. It translates datatypes into immutable dataclasses, pattern-matching equations into Python’s structural pattern matching, and type classes into explicit dictionaries. Its library setup maps HOL’s numbers, lists, and immutable arrays to native Python values, while preserving HOL’s semantics where Python’s built-in operations differ, and self tail calls can optionally be translated into loops.
Our evaluation shows that the backend produces valid Python code for a large part of the HOL library. Differential testing of six verified data structures and algorithms against established Python libraries revealed no disagreement, further increasing trust in the correctness of our translation. As expected, the generated code is slower than the hand-written libraries, mainly due to call overhead, immutable data, and type-class dictionaries. The difference in performance also depends on the particular Python runtime used, where PyPy seems favourable to the style of code that is generated.
Even with slower performance, the generated code is suitable as a verified reference implementation against which existing Python libraries can be tested. For use inside applications, PyPy already narrows the gap, and the optimisations outlined in § 6 could narrow it further. In the long run, targeting a formally specified subset of Python such as PurePy could lead to a verified pipeline from Isabelle/HOL down to Python code.
With increased calls for verification and formal methods in software engineering, our approach provides an opportunity to leverage the power of Isabelle in concert with one of the most popular languages, Python, to increase trust in our software.
References
- [1]Archive of Formal Proofs. https://www.isa-afp.org. Accessed 2026-10-27.
- [2]Stefan Berghofer, Lukas Bulwahn, and Florian Haftmann. Turning Inductive into Equational Specifications. In Stefan Berghofer, Tobias Nipkow, Christian Urban, and Makarius Wenzel, editors, Theorem Proving in Higher Order Logics, volume 5674 of Lecture Notes in Computer Science, pages 131–146. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. doi:10.1007/978-3-642-03359-9_11.DOI
- [3]Stefan Berghofer and Tobias Nipkow. Executing Higher Order Logic. In Paul Callaghan, Zhaohui Luo, James McKenna, Robert Pollack, Robert Pollack, Gerhard Goos, Juris Hartmanis, and Jan Van Leeuwen, editors, Types for Proofs and Programs, volume 2277 of Lecture Notes in Computer Science, pages 24–40. Springer Berlin Heidelberg, Berlin, Heidelberg, 2002. doi:10.1007/3-540-45842-5_2.DOI
- [4]Brandt Bucher and Guido van Rossum. PEP 634 – Structural Pattern Matching: Specification. https://peps.python.org/pep-0634/, 2020. Python Enhancement Proposal, accepted for Python 3.10.
- [5]Koen Claessen and John Hughes. QuickCheck: A lightweight tool for random testing of Haskell programs. In Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming, pages 268–279. ACM, September 2000. doi:10.1145/351240.351266.DOI
- [6]Jose Divasón. A verified algorithm for computing the Smith normal form of a matrix. Archive of Formal Proofs, May 2020. https://isa-afp.org/entries/Smith_Normal_Form.html.
- [7]Jose Divasón and Jesús Aransay. Hermite Normal Form. Archive of Formal Proofs, July 2015. https://isa-afp.org/entries/Hermite.html.
- [8]Gabriel Ebner, Guido Martínez, Aseem Rastogi, Thibault Dardier, Megan Frisella, Tahina Ramanananandro, and Nikhil Swamy. PulseCore: An Impredicative Concurrent Separation Logic for Dependently Typed Programs. Proceedings of the ACM on Programming Languages, 9(PLDI):1516–1539, June 2025. doi:10.1145/3729311.DOI
- [9]Marco Eilers and Peter Müller. Nagini: A Static Verifier for Python. In Hana Chockler and Georg Weissenbacher, editors, Computer Aided Verification, volume 10981 of Lecture Notes in Computer Science, pages 596–603. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-319-96145-3_33.DOI
- [10]Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. The essence of compiling with continuations. ACM SIGPLAN Notices, 28(6):237–247, June 1993. doi:10.1145/173262.155113.
- [11]Steven E. Ganz, Daniel P. Friedman, and Mitchell Wand. Trampolined style. In Proceedings of the Fourth ACM SIGPLAN International Conference on Functional Programming, pages 18–27, Paris France, September 1999. ACM. doi:10.1145/317636.317779.DOI
- [12]Florian Haftmann. Code Generation from Specifications in Higher-Order Logic. PhD thesis, Technical University Munich, 2009.
- [13]Florian Haftmann and Tobias Nipkow. Code Generation via Higher-Order Rewrite Systems. In Matthias Blume, Naoki Kobayashi, Germán Vidal, David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, and Gerhard Weikum, editors, Functional and Logic Programming, volume 6009 of Lecture Notes in Computer Science, pages 103–117. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. doi:10.1007/978-3-642-12251-4_9.DOI
- [14]Florian Haftmann and Makarius Wenzel. Constructive Type Classes in Isabelle. In Thorsten Altenkirch, Conor McBride, David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, and Gerhard Weikum, editors, Types for Proofs and Programs, volume 4502 of Lecture Notes in Computer Science, pages 160–174. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. doi:10.1007/978-3-540-74464-1_11.DOI
- [15]Nikolaus Huber, Roly Perera, and Dominic Orchard. Python code generation for Isabelle/HOL – software artefact, November 2026. doi:10.5281/zenodo.24106993.DOI
- [16]Lars Hupel and Tobias Nipkow. A Verified Compiler from Isabelle/HOL to CakeML. In Amal Ahmed, editor, Programming Languages and Systems, volume 10801 of Lecture Notes in Computer Science, pages 999–1026. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-319-89884-1_35.DOI
- [17]Jukka Lehtosalo et al. mypy: Optional static typing for Python. https://mypy-lang.org. Accessed: Oct. 26, 2026.
- [18]K. Rustan M. Leino. Dafny: An Automatic Program Verifier for Functional Correctness. In Edmund M. Clarke and Andrei Voronkov, editors, Logic for Programming, Artificial Intelligence, and Reasoning, volume 6355 of Lecture Notes in Computer Science, pages 348–370. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. doi:10.1007/978-3-642-17511-4_20.DOI
- [19]Pierre Letouzey. Extraction in Coq: An Overview. In Arnold Beckmann, Costas Dimitracopoulos, and Benedikt Löwe, editors, Logic and Theory of Algorithms, volume 5028 of Lecture Notes in Computer Science, pages 359–369. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-69407-6_39.DOI
- [20]David MacIver, Zac Hatfield-Dodds, and Many Contributors. Hypothesis: A new approach to property-based testing. Journal of Open Source Software, 4(43):1891, November 2019. doi:10.21105/joss.01891.DOI
- [21]Mac Malone. Nerodia. https://github.com/leanprover/nerodia, 2026. Accessed: Oct. 27, 2026.
- [22]Luc Maranget. Compiling pattern matching to good decision trees. In Proceedings of the 2008 ACM SIGPLAN Workshop on ML, pages 35–46, Victoria BC Canada, September 2008. ACM. doi:10.1145/1411304.1411311.DOI
- [23]William M. McKeeman. Differential testing for software. Digital Technical Journal, 10(1):100–107, 1998.
- [24]Leonardo De Moura and Sebastian Ullrich. The Lean 4 Theorem Prover and Programming Language. In André Platzer and Geoff Sutcliffe, editors, Automated Deduction – CADE 28, volume 12699 of Lecture Notes in Computer Science, pages 625–635. Springer International Publishing, Cham, 2021. doi:10.1007/978–3–030–79876–5_37.DOI
- [25]Tobias Nipkow. Splay Tree. Archive of Formal Proofs, August 2014. https://isa-afp.org/entries/Splay_Tree.html.
- [26]Tobias Nipkow, editor. Functional Data Structures and Algorithms: A Proof Assistant Approach. ACM, New York, NY, USA, 1 edition, September 2025. doi:10.1145/3731369.DOI
- [27]Tobias Nipkow, Markus Wenzel, Lawrence C. Paulson, Gerhard Goos, Juris Hartmanis, and Jan Van Leeuwen, editors. Isabelle/HOL, volume 2283 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, Berlin, Heidelberg, 2002. doi:10.1007/3–540–45949–9.
- [28]PurePy contributors. PurePy: a functional subset of Python, 2026. Accessed: Oct. 27, 2026. URL: https://github.com/pure-py/pure-py-spec.
- [29]Python Software Foundation. Python glossary: CPython. https://docs.python.org/3/glossary.html#term-CPython. Accessed 2026-11-10.
- [30]Michel Schinz and Martin Odersky. Tail call elimination on the Java Virtual Machine. Electronic Notes in Theoretical Computer Science, 59(1):158–171, November 2001. doi: 10.1016/S1571–0661(05)80459–1.DOI
- [31]Terru Stübinger and Lars Hupel. Go code generation for Isabelle. Archive of Formal Proofs, January 2024. https://isa-afp.org/entries/Go.html.
- [32]Terru Stübinger and Lars Hupel. Extending Isabelle/HOL’s Code Generator with Support for the Go Programming Language. In Andre Platzer, Kristin Yvonne Rozier, Matteo Pradella, and Matteo Rossi, editors, Formal Methods, volume 14934 of Lecture Notes in Computer Science, pages 3–19. Springer Nature Switzerland, Cham, 2025. doi:10.1007/978–3–031–71177–0_1.DOI
- [33]Nikhil Swamy, Juan Chen, Cédric Fournet, Pierre-Yves Strub, Karthikeyan Bhargavan, and Jean Yang. Secure distributed programming with value-dependent types. In Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming, pages 266–278, Tokyo Japan, September 2011. ACM. doi:10.1145/2034773.2034811.DOI
- [34]David Tarditi, Peter Lee, and Anurag Acharya. No assembly required: Compiling standard ML to C. ACM Letters on Programming Languages and Systems, 1(2):161–177, June 1992. doi:10.1145/151333.151343.DOI
- [35]The Rocq Development Team. The Rocq Prover. Zenodo, September 2025. doi:10.5281/ZENODO.15149628.DOI
- [36]TIOBE Software. TIOBE Index for October 2026. https://www.tiobe.com/tiobe-index/, 2026. Accessed: Oct. 25, 2026.
- [37]Guido van Rossum, Jukka Lehtosalo, and Łukasz Langa. PEP 484 – Type Hints. https://peps.python.org/pep-0484/, 2014. Python Enhancement Proposal, accepted for Python 3.5.
- [38]Guido van Rossum, Barry Warsaw, and Alyssa Coghlan. PEP 8 – Style Guide for Python Code. https://peps.python.org/pep-0008/, 2001. Python Enhancement Proposal.
- [39]P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad hoc. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - POPL ’89, pages 60–76, Austin, Texas, United States, 1989. ACM Press. doi:10.1145/75277.75283.DOI


