An Enumerative Embedding of the Python Type System in ACL2s

Samuel Xifaras Panagiotis Manolios Andrew T. Walter William Robertson · 2025

Read An Enumerative Embedding of the Python Type System in ACL2s by Samuel Xifaras Panagiotis Manolios Andrew T. Walter William Robertson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19015.txt.

Introduction

Python is a top code tongue, yet tools that prove facts about Python code lag behind. Samuel Xifaras and co-authors take a first step in a 2025 study by building part of Python's type system inside a proof tool. Their slice covers the most used type notes plus user made types built from them.

The team also built type aware makers that spin out sample values of each type. Those samples feed fuzz tests that push real code with odd inputs. On four open code bases, the tests reached most lines of code and found slips that top Python type checkers miss. Hard branch rules and file calls were the main blocks to full reach.

Catalog record

CREATORSamuel Xifaras Panagiotis Manolios Andrew T. Walter William Robertson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19015

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Enumerative Embedding of the Python Type System in ACL2s Samuel Xifaras Panagiotis Manolios Andrew T. Walter William Robertson Abstract Python is a high-level interpreted language that has become an industry standard in a wide variety of applications. In this paper, we take a first step towards using ACL2s to reason about Python code by developing an embedding of a subset of the Python type system in ACL2s. The subset of Python types we support includes many of the most commonly used type annotations as well as user-defined types comprised of supported types. We provide ACL2s definitions of these types, as well as defdata enumerators that are customized to provide code coverage and identify errors in Python programs. Using the ACL2s embedding, we can generate instances of types that can then be used as inputs to fuzz Python programs, which allows us to identify bugs in Python code that are not detected by state-of-the-art Python type checkers. We evaluate our work against four open-source repositories, extracting their type information and generating inputs for fuzzing functions with type signatures that are in the supported subset of Python types. Note that we only use the type signatures of functions to generate inputs and treat the bodies of functions as black boxes. We measure code coverage, which ranges from about 68% to more than 80%, and identify code patterns that hinder coverage such as complex branch conditions and external file system dependencies. We conclude with a discussion of the results and recommendations for future work. 1 Introduction Python is an industry-standard language that is used in software engineering disciplines ranging from web development to machine learning [ 15 ] . Its versatility and ease of use have propelled it to its position as the second most popular programming language by usage on GitHub, behind only JavaScript [ 4 ] . With this popularity has come many proposed improvements to the language, including type annotations which were introduced in Python Enhancement Proposal (PEP) 484 [ 42 ] . This is a reasonable addition, as static typing in programming has been shown to have a host of benefits [ 18 ] . As these type annotations continue to be adopted by developers, they represent a rich source of data for application analysis. Since Python software has become ubiquitous, this paper is motivated by the need for robust software verification in Python. Python code is typically tested with unit testing, which tests a property of the code in a single example scenario. Although unit testing can be effective when done well, it has a reputation for being burdensome, and there is evidence that developers find it challenging–or are not motivated–to cover deeply nested code [ 54 ] . In this paper, we introduce an extensible , enumerative embedding of the Python type system that can generate representative examples of simple and complex Python types, and evaluate its effectiveness by measuring code coverage on real-world open source repositories. The representative examples generated by this embedding can drive fuzzing and property-based testing (PBT), among other techniques. Importantly, the goal of this work is not to model the semantics of the type system. This is mostly because it is unclear what the semantics of the type system of Python are. Rak-amnouykit et al. [ 39 ] , for instance, find that two of the most popular Python type checkers, mypy [ 47 ] and pytype [ 3 ] , implement and check different type systems. Nor is it the goal to model the semantics of Python, which are complex and subject to change in new Python versions. For a preview of the complex considerations involved in modeling the semantics of Python, including scoping and generators, see [ 36 ] . Instead, our goal is to facilitate fuzzing and PBT of Python programs with an embedding of the Python type system that supports extension and can be used to generate test cases. Our embedding is extensible in that it can be extended with new types. This is necessary as Python primitive types can be composed in infinitely many ways with compound types such as lists, tuples, and dictionaries. User-defined classes are also frequently used by Python programmers, and we support embedding classes as record types, as long as their field types are recursively representable in the embedding. The embedding also supports extension with union types. How the type system works and how it can be extended are discussed in Section 4 . Our embedding is enumerative because it leverages the enumerative data definition framework of ACL2s [ 13 ] . We say a data type is enumerative when it is associated with an enumerator function that maps natural numbers to elements of the type. After the embedding is extended to include user-defined types, the enumerative property of the embedding allows examples of these types to be generated immediately. This is useful for test data generation in unit testing, producing large numbers of test cases for PBT, and producing seed inputs for fuzzing. We discuss this aspect of the embedding further in Section 5 . We chose to implement this embedding in ACL2s because we view it as uniquely positioned to support the goals of this work. Its logical foundation enables formal reasoning and theorem proving for Python types and constructs, and the ACL2s defdata framework [ 13 ] grants the enumerative property of the embedding. Taken together, these enable seamless integration with dynamic approaches, such as fuzzing and PBT. Accordingly, the contributions of this paper are being used in ongoing work related to fuzzing in Python. In summary, we claim the following contributions in this paper: • An extensible, enumerative embedding of the Python type system in ACL2s. The code is open-sourced and available. 1 1 1 https://github.com/acl2/acl2/tree/master/books/projects/python/embedding • Custom enumerators for Python primitive types. The enumerators are designed to produce representative examples of Python types. • An evaluation of code covered in four open source repositories with inputs generated by the embedding’s enumerators. Note that conversion of the embedding’s generated examples to Python objects is not specified in this paper. Details are given in Xifaras’s master’s thesis [ 53 ] , and we also plan to publish a specification of the conversion process in a forthcoming software engineering paper. To motivate why this problem is interesting and nontrivial in the context of our ongoing work in fuzzing, consider the fact that pickle [ 2 ] , Python’s built-in object serialization protocol, does not flatly encode the data. It instead encodes objects as instructions to a virtual machine that, when played back, reconstruct the original object [ 46 ] . We have observed that this storage format is far from ideal for fuzzing and poses significant security concerns [ 53 ] . We invite the community to extend the embedding and implement new features or program analyses on top of it. There are many features of the type system that are missing from our embedding, such as protocol types [ 29 ] , and new features are added with every update to the Python language. This leaves many opportunities for future work. The remainder of the paper is organized as follows. In Section 2 , we discuss some background information

Read the complete text