arXiv:2605.18697v1 [cs.DC] 18 May 2026
PopPy: Opportunistically Exploiting Parallelism in Python Compound AI Applications Stephen Mell
David Mell
Konstantinos Kallas
University of Pennsylvania Philadelphia, Pennsylvania, USA [email protected]
Independent Researcher Juneau, Alaska, USA [email protected]
University of California, Los Angeles Los Angeles, California, USA [email protected]
Steve Zdancewic
Osbert Bastani
University of Pennsylvania Philadelphia, Pennsylvania, USA [email protected]
University of Pennsylvania Philadelphia, Pennsylvania, USA [email protected]
Abstract
invoke programmatic tools [11, 39, 52, 70]; or (2) workflows, where LLM calls and programmatic components are orchestrated as a dataflow graph [15, 16, 42, 48]. However, many compound AI applications do not fit cleanly into these categories, such as LLM-guided search [58, 74], multi-agent systems [6, 23], and agents that themselves generate workflows [20, 64, 76], thereby necessitating use of a generalpurpose language. In addition to flexibility, general-purpose languages also come with rich ecosystems of libraries and tooling. A key challenge with compound AI applications is that they perform multiple calls to ML models, leading to very slow end-to-end execution times. To address this issue, prior work has focused on optimizing individual model calls [18, 71]. However, this strategy ignores potential optimizations at the program level. A prominent instance is that these applications often exhibit substantial opportunities for parallelism— e.g., in a multi-agent system, each agent can be run in parallel between rounds of communication. While recent work has proposed custom frameworks and domain-specific languages that expose such parallelism in compound AI applications [11, 15, 16, 39, 42, 48, 52, 70], these frameworks have limited expressiveness and cannot support sophisticated applications—e.g., they all lack the control flow provided by general purpose languages. Perhaps more surprisingly, the long line of work optimizing general-purpose languages also fails to exploit parallelism in compound AI applications—the reason is that the main bottleneck is not in the code written in the language, but rather blackbox code in external calls. Thus, developers must manually parallelize their code using threading and asynchronous programming, wasting valuable programmer effort, increasing application complexity, and reducing maintainability. We propose PopPy1 , a system that exploits parallelism in compound AI applications written as sequential Python code, with minimal developer intervention. The developer annotates parts of the program either as “internal” for core program logic (written in an expressive Python subset) or
Compound AI applications, which compose calls to ML models using a general-purpose programming language like Python, are widely used for a variety of user-facing tasks, from software engineering to enterprise automation, making their end-to-end latency a critical bottleneck. In contrast to traditional applications, execution time is dominated by the external components, which cannot be handled by traditional language optimization systems, like optimizing compilers. To address this problem, we develop PopPy, a system that can uncover parallelization opportunities in Python applications that invoke these heavy external components, including those used in compound AI applications. PopPy supports a very expressive fragment of Python and requires minimal developer input to uncover parallelism. It combines an ahead-of-time compiler with a runtime, addressing three key challenges in extracting parallelism from Python applications: language complexity, dynamic dispatch, and variable mutation. On a set of real-world compound AI applications, PopPy achieves up to 6.4× speedups in end-to-end execution time compared to standard Python execution while preserving the sequential program semantics.
1
Introduction
Despite the tremendous progress in machine learning (ML), especially in large language models (LLMs), individual models still struggle to reliably solve complex tasks. As a result, there has been a shift toward compound AI applications [75] that programmatically compose multiple components including ML models. Prominent examples include retrieval-augmented generation [40], which combines LLMs with knowledge-base lookup; coding agents [73], which use shell utilities and spawn subagents; and AI mathematics systems, which leverage LLM-guidance for proof [58, 65]. While frameworks exist for building these applications, developers often resort to directly making LLM calls in a generalpurpose language such as Python [28]. Most notably, frameworks largely target one of two specific paradigms: (1) agents, where an LLM is placed in a loop and given the ability to
1 PopPy: Parallel Opportunistic Python
1
2.1
“external” for calls to blackbox code (e.g., LLMs). In addition, they annotate which external calls are reorderable—e.g., LLM calls are stateless and thus reorderable, but printing is not. At runtime, PopPy executes the internal program eagerly and out-of-order, enabling calls to external code (e.g., longrunning LLM calls) to be executed in parallel when possible. Crucially, PopPy guarantees that as long as the annotations are correct, then the program output is equivalent to standard Python execution. Finally, PopPy includes annotations for much of the Python standard library as well as common ML models, thereby minimizing the number of annotations that the developer must provide. To parallelize real Python code, PopPy solves three key challenges: (1) Python’s language complexity, (2) dynamic dispatch, which obscures the reorderability of method calls, and (3) variable mutation. Specifically, PopPy solves (1) by compiling Python to an existing minimal language 𝜆𝑂 that supports opportunistic out-of-order execution [46]; (2) by delegating reordering decisions to runtime controllers; and (3) by optimizing common patterns of variable mutation. We evaluate PopPy on a five compound AI applications from the literature, including the LLM-guided search application Tree-of-Thoughts [74] and the multi-agent application DiverseAgentEntropy [23]. We also evaluate on 30 programs generated by the CaMeL [20] agent. PopPy improves execution time of applications that have parallelization opportunities by up to 6.4× compared to standard Python execution, while preserving the sequential program semantics. In summary, PopPy contributes the following:
A compound AI application2 is a programmatic composition of AI components, including LLMs, computer vision models, knowledge bases, search procedures, and external tools. They have been shown to perform better than individual AI models, by breaking up problems into smaller components and solving each one individually. Because of this, they are now widely used in a variety of domains, from software engineering [31, 49] to enterprise automation [15, 48]. There are two particularly popular categories of compound AI application, each of which is supported by its own set of domain specific languages and programming frameworks: (1) agents, where the programmer provides the components to an LLM in a loop, and the LLM chooses when and how to invoke them [11, 39, 52, 70], and (2) workflows, where the programmer composes the components in a domainspecific language, typically as a dataflow graph [15, 16, 42, 48]. However, many applications do not fit cleanly into either of these categories—e.g., performing guided search over LLM outputs [58, 74], multi-agent applications where the agents communicate in complex ways to solve tasks [6, 23], and applications where agents may themselves generate workflows of LLM calls (possibly including recursive calls to other agents) [20, 64, 76]. Many realistic systems exhibit these kinds of complexity, leading developers to develop compound AI applications in general-purpose programming languages, such as Python, which lack expressiveness limitations [20, 23, 24, 41, 49, 64, 74]. In addition, Python comes with a rich ecosystem of existing libraries and tools that can be useful for building compound AI applications.
1. A two-phase compiler that handles Python’s complexity by transpiling all Python features to a core calculus 𝜆𝑂 [46], which can uncover parallelization opportunities between external calls at runtime (§5). 2. A dynamic concurrency control subsystem together with an annotation framework for external calls, which enables determining which calls can run in parallel at runtime in the presence of dynamic dispatch (§6). 3. Optimizations for key variable mutation patterns, enabling parallelism without changing the behavior of the original application (§7).
2.2
Example: Tree of Thoughts
A characteristic example of a compound AI application is Tree of Thoughts [74] (ToT), a search procedure that uses LLM calls to propose and prioritize search states to be explored. ToT has been used for a wide variety of tasks, including logical proof search [30], robot manipulation planning [72], and enterprise domain modeling [62]. Figure 1 shows the core of a ToT implementation in PopPysupported Python, slightly adapted from the original authors’ implementation [1]. It takes as input a string describing the task, e.g., to generate code to fix a bug, and then performs NUM_STEPS rounds of beam search.For each state, e.g., a bugfix candidate, it calls an LLM (llm_get_proposals) to get successor states, e.g., refined bug-fix candidates. Then get_ values is called to score each new state, the output of which is passed to topk, which returns the BEAM_WIDTH highestscoring candidate states to continue the searching from. The get_values function iterates over all states and scores them using another LLM call (llm_get_value), e.g., how likely is a candidate to actually fix the bug. It uses a cache to
Before diving into the key technical contributions, we show a motivating example (§2), provide an overview of (§3), and describe its user interface in detail (§4). After the technical contributions we evaluate PopPy (§8), and provide a discussion of related work (§9).
2
Building Compound AI Applications
Motivating Example
We begin providing some background on compound AI applications (§2.1). We then describe Tree of Thoughts [74], a characteristic example of a compound AI application (§2.2), and show how PopPy can extract parallelism from it (§2.3).
2 Sometimes called compound AI systems; we use “applications” to avoid
confusion with the system we are proposing, PopPy. 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
@poppy def tree_of_thoughts(task): states = ("",) for step in range(NUM_STEPS): new_states = tuple() for s in states: new_states += llm_get_proposals(task, s) values = get_values(task, new_states) states = topk(states, values, BEAM_WIDTH) print(states) return states @poppy def get_values(task, states): value_cache = frozenset() values = tuple() for idx, state in enumerate(states): if state in value_cache: value = 0 print(f"{idx}: duplicate") else: value = llm_get_value(task, state) value_cache |= {state} print(f"{idx}: {value}") values += (value,) return values @poppy def llm_get_proposals(task, state): ... @poppy def llm_get_value(task, state): ...
30 31 32 33 34 35
# Library Functions @sequential def print(line): ... @unordered async def llm(prompt): ...
idx=0
idx=1 14 value_c] 15 values ] 16 for idx] 25 return ] idx=2
idx=3
17 if stat] 24 values ] 17 if stat] 24 values ] 17 if stat] 24 values ] 17 if stat] 24 values ]
False
21 value =] 22 value_c] 23 print(f]
True
18 value =] 19 print(f]
False
21 value =] 22 value_c] 23 print(f]
True
L P P L P
18 value =] 19 print(f]
P
Figure 2. Illustration of the execution of get_values with states = ("a", "a", "b", "b"), after queueing all external calls but before any have resolved. Internal code execution tree (left): Each code block that is executed at runtime is shown, including duplicates from different loop iterations; block borders are colored to correspond to source blocks in Figure 1; statements are shown with line numbers; bold line numbers indicate statements that execute without waiting for external calls to resolve. Blocks for calls to False 20 value = llm_ge…] 16 for if state in External en…] value_cache |=…] llm_get_value are idx=0 omitted space. call21depen23 values += (val…] 22 print(f"{idx}:…] dency graph (right): node represent queued external calls, True 17 value = 0 ] idx=1 16 if state and edges indicate dependencies that block in en…]execution; solid 13 value_cache = …] 18 print(f"{idx}:…] 23 values += (val…] 14 values = tuple…] border means the call has been dispatched, dashed means it 15 for idx, state…] value = llm_ge…] is24waiting; “L” is a] call to llm, “P” is a call to False print.20 return values idx=2 16 if state in en…] 21 value_cache |=…] 23
values += (val…]
22
print(f"{idx}:…]
True value ] time is spent blocking, waiting the LLM17API to = 0 idx=3 16 if for state in remote en…] 18 print(f"{idx}:…] 23 values += (val…] return a response. Since the performance bottleneck for ToT is outside of the program, standard language optimizations like just-in-time compilation are ineffective—they optimize the Python code but not external calls.
Opportunity: Parallelism. Even though the LLM calls are the bottleneck of this application, many of them are actually independent, and so could be executed in parallel, as soon as their arguments (prompts) are ready. Achieving such parallelism would require aggressive rewriting of the application, using threading and async/await, while also being careful to preserve dependencies across calls and loop iterations to not violate the original sequential semantics.
Figure 1. Tree-of-Thoughts [74] implementation in Python. The @_ lines are the annotations that need to be added to a program to be supported by PopPy. L1-L29 are provided by the application developer, while L32-L35 are provided by library developers. The colored bars indicate specific code blocks referenced in Figure 2.
2.3 avoid redundant LLM calls for already scored states, and calls print to log new and duplicate states. The functions llm_ get_proposals and llm_get_value first format a prompt, then call llm, which makes an HTTP request to a remote LLM API (e.g., GPT [51], Claude [5], or Gemini [27]), and finally parse the result into the desired output type.
Parallelizing with PopPy
Before describing how PopPy can be used to parallelize this application, it is important to note that PopPy draws a distinction between external calls, such as ML models, other remote APIs, file operations, and native code, and internal code that is used for orchestration and does not perform any side-effects. In compound AI applications, external calls tend to be the bottleneck due to the high cost of calling ML models, while internal code is lightweight orchestration. With this distinction, PopPy’s goal is to execute internal code with maximal parallelism while preserving the order of external calls that depend on one another, e.g., the print calls in Fig. 1.
Problem: Performance. The ToT application shown in Fig. 1 is very slow: solving a challenging arithmetic reasoning task [74] on a 24-core Intel(R) Xeon(R) Gold 6342 CPU @ 2.80GHz machine with Python 3.13.7 and gpt-3.5-turbo as the model, it takes 142 seconds, out of which 135 seconds are spent waiting for LLM calls to complete. Virtually all of this 3
To use PopPy, the developer annotates functions in their code that should be considered external using @unordered, @readonly, and @sequential; the choice of annotation indicates whether calls to them can be executed early or must execute in the original sequential order. Functions that may block, such as llm, can be defined with Python’s async machinery to avoid blocking the Python interpreter and enable multiple such calls to execute in parallel. The developer also annotates code that PopPy should execute internally with @poppy. In Fig. 1, llm calls should run both early and parallel, while print calls need to execute in the same order as in the sequential program. Developers can import PopPy’s annotations for standard libraries, including functions such as print and llm, and data structures such as tuple and frozenset. While application developers can write their own asynchronous external code, we envision it largely being provided by libraries, allowing application code to remain synchronous. Parallel Execution. As an example, consider executing get_values from Figure 1 with states set to ("a", "a", "b", "b"). Figure 2 shows the tree of executed code blocks. Initially, execution proceeds as normal: L14, L15, L16, into the first iteration of the loop (for idx = 0, state = "a"), L17, and into the else branch of the conditional. L21 is then reached, containing an external call to llm_get_values. (In the execution tree, this is the top-most path.) Rather than executing the external call in a blocking fashion, it is queued: the result variable, value, is assigned to a placeholder, and the call is added to a dependency graph of queued external calls, also shown in Figure 2. Because llm_get_value was annotated @unordered and the call arguments are known, the call has no dependencies. Thus it is immediately dispatched, beginning execution of the external code in the ordinary Python interpreter. (In this case, a network request is sent to the remote API.) Execution of internal code then continues, skipping past the outstanding external call. Since L22 doesn’t depend on the result (value), it executes immediately. L23 is another external call, to print, and so it is queued as before. However, this call does not dispatch immediately, for two reasons: (1) value is part of its argument, and thus it depends on the previous external call; (2) print is annotated @sequential, and so it depends on any preceding sequential calls finishing. Execution again continues past the outstanding external call, exiting the conditional and moving to L24, which appends value to values, and is skipped because it depends on the first outstanding LLM call. Execution proceeds in the second loop iteration, which now enters the if branch because value ("a") is in value_cache ({"a"}), allowing the next print to be queued as well. After stepping through the final two loop iterations and queueing more external calls, execution is stuck, as all unevaluated statements depend on some outstanding external call. This state, after queueing
AI Component Library (§6.1) Annotations (§4.2)
Compound AI Application (§4)
Internal Code (Poppy Python; §4.1)
External Code (Async Python)
Compiler Phase I (§5.2)
Bezoar IR (§5)
Compiler Phase II (§5.3)
Variable Optimizer (§7) Static Dynamic
λO Interpreter (§3.1)
Concurrency Controllers (§6.2)
Python Interpreter
Figure 3. The PopPy system architecture. Code (static) and processes (dynamic) are shown in boxes; transformations are shown in bubbles. all external calls but before any have finished, is depicted in Figure 2. When an external calls returns (e.g., the remote LLM API returns a response), it resolves, replacing its placeholder with the return value. This frees up dependent operations to execute. Suppose the first LLM call resolves, and there are no outstanding preceding sequential external calls. Then, the first print call (L23) becomes unblocked and executes, as Input Program does the operation appending value to values (L24). Calls the complete SpeedupsInternal with Code PopPy. Running ToT appliExternal Code (Python) cation with (Ocelot) PopPy, the end-to-end execution time reduces from 142 seconds with Python to 23 seconds (6.1× speedup) through the parallelization of the LLM calls.
3
Compiler Phase I
Bezoar
System Overview
Fig. 3 shows the architecture of PopPy, which includes a Compiler static component and a dynamic component. The user proλO Code Phase II vides a Python program such as the one shown in Fig. 1, inStatic cluding both external code (annotated with its concurrency behavior, e.g., @sequential or @unordered) and internal Dynamic code (annotated with @poppy). First, before execution, the Python internal code is compiled to an intermediate representation Interpreter λO Interpreter called Bezoar (§5) which is in turn compiled to 𝜆𝑂 , a core External Wrapper Threads calculus for extracting external-call parallelism. A variable optimization pass is applied to the Bezoar code to improve parallelizability (§7). The compiled internal code is executed by the 𝜆𝑂 interpreter, while the external code is executed 4
Describes
with a standard Python interpreter. Whenever an external call is queued, a concurrency controller (§6) is spawned for it to coordinate execution order with other external calls. A key property of PopPy is soundness (§4.3): assuming the annotations are correct, then applications have the same behavior as if they were executed with the standard Python interpreter. It achieves soundness by guaranteeing that external calls are all executed in the order produced by the sequential execution, modulo reorderings that are explicitly allowed by the annotations (e.g., executing @unordered LLM calls early). Users have to provide annotations for any external functions they define, but PopPy provides annotations for commonly-used parts of the Python standard library. In the rest of this section, we describe the key challenges to “opportunistically” executing Python code, and how the components of PopPy address these challenges. 3.1
challenges. To bridge the gap, we split the compiler into two phases, with a novel intermediate representation (IR) between them called Bezoar (§5). Like 𝜆𝑂 , Bezoar is minimal and explicit, but like Python, it is sequential and has variable mutation. The first phase converts complex features of Python into the minimal Bezoar language (§5.1); the second phase converts the imperative (sequential, mutable) Bezoar into the functional (opportunistic, immutable) 𝜆𝑂 (§5.2). 3.3
Extracting Parallelism with 𝜆𝑂
As illustrated in Section 2.3, PopPy leverages on out-of-order execution to extract parallelism, continuing evaluation past parts of the program that are blocked by outstanding external calls. To do this, PopPy relies on 𝜆𝑂 [46], a core calculus that crystallizes this idea, called opportunistic evaluation. Execution under opportunistic evaluation is highly nondeterministic, but guarantees confluence—i.e., any evaluation order of 𝜆𝑂 matches sequential execution. This allows 𝜆𝑂 to take advantage of parallelization opportunities that could not be leveraged statically—in different runs of the same program, external calls may have different durations and return in different orders; 𝜆𝑂 will always execute as much as possible, varying at runtime based on what calls have actually returned. While 𝜆𝑂 ’s interpreter obtains the desired parallelism, it is a functional, immutable, and non-sequential language, making it very different from Python, which is imperative, mutable, and sequential. Additionally, it assumes the behavior of external calls depends only on their arguments—there can be no hidden dependencies, which is not true of operations like print. This discrepancy raises several challenges that PopPy must address. 3.2
Challenge: Dynamic Dispatch (§6)
To soundly extract parallelism, PopPy must execute sequential calls (e.g., print) in order, while executing unordered calls (e.g., LLMs) early. In 𝜆𝑂 , sequential versus unordered behavior is determined at the call site: calls are only sequenced if they have a data dependency. Naïvely, our compiler could automatically introduce data dependencies to enforce sequencing where necessary; however, this strategy requires the reordering behavior of a call site to be known statically, which is not true for Python, since it supports dynamic dispatch. For example, the += operator (L24) is dynamically dispatched based on the type of the left-hand side: for (immutable) tuples, it can be unordered, but for (mutable) lists, it must be sequential. Sequencing every dynamically dispatched call would be sound, but also removes almost all parallelism opportunities. Instead, PopPy delegates concurrency control to the runtime. When an external call is queued, instead of having the 𝜆𝑂 interpreter launch the call directly, the interpreter launches a concurrency controller, a lightweight thread that wraps the external call. This controller knows what function is actually being called, and thus knows the desired concurrency behavior. The compiler encodes the original sequential order of calls into the 𝜆𝑂 code, which the concurrency controllers use to coordinate among themselves and determine when it is sound to actually dispatch their external call. 3.4
Challenge: Variable Scoping and Mutation (§7)
Concurrency and mutation are known to interact poorly. 𝜆𝑂 solves this by only supporting immutable variables, but Python code makes heavy use of variable mutation. Because Python allows non-local uses of variables, mutations are hard to analyze and soundness, in the worst case, requires them to be strictly sequenced, preventing parallelization. To address this challenge, PopPy makes the following observation: most variables in practical compound AI applications fall into one of two analyzable categories: (1) variables that are mutated but only used locally, and (2) variables that are used non-locally but only assigned once. PopPy translates the assigned-once variables directly to 𝜆𝑂 and implements a variable “promotion” pass that turns mutable local variable writes and reads into immutable variables. This avoids the need for unnecessary sequencing in most cases, enabling parallelization while retaining soundness.
Challenge: Python Complexity (§5)
𝜆𝑂 is able to provide confluence for opportunistic evaluation in a provable manner by being extremely minimal: like 𝜆 calculus, its only language constructs are function definitions and function calls. In contrast, Python is a complex language with many interacting features. While it is in principle possible to directly devise an opportunistic evaluation strategy for Python, it would be quite challenging. Instead, PopPy relies on 𝜆𝑂 ’s interpreter for the execution of internal code. To apply it to Python, PopPy compiles the internal Python code to 𝜆𝑂 . However, 𝜆𝑂 and Python have conflicting features (immutable vs. mutable, functional vs. imperative, parallel vs. sequential, etc) raising several 5
4
System Interface
4.3
In this section, we describe PopPy’s interface: the user provides a Python program, where functions are either annotated as internal (restricted to a fragment of Python, albeit an expressive one; see §4.1), or external (with the appropriate reordering rule; see §4.2). We also discuss PopPy’s correctness guarantee—it preserves the original sequential semantics modulo reorderings allowed by annotations (§4.3). 4.1
PopPy optimizes Python programs without affecting their observable behavior—i.e., the sequence of external calls made is the same as that made when running with standard Python, modulo the reorderings allowed by the annotations. Formally, we call a sequence of external calls a trace. For external call annotations 𝐴, we define the equivalence relation over traces ≡𝐴 such that 𝑡 1 ≡𝐴 𝑡 2 iff 𝑡 1 can be transformed into 𝑡 2 via external call reorderings allowed by 𝐴. We define the semantics ⟦𝑃⟧𝑆 to be the trace produced by 𝑃 when executed with system 𝑆. Let PopPy(𝐴) be PopPy running with annotations 𝐴.
Python Fragment for Internal Code
For internal (@poppy) code, PopPy supports an expressive subset of Python including if statements, for loops, function definitions and calls, variable assignments, tuples, and operators. Statements causing non-local control flow, such as break, continue, return (except at the end of a function), and exceptions, via raise or propagated from an external call, are only currently supported in external and not internal code. All unsupported cases, except exceptions propagated from external calls, can be detected statically, in which case PopPy can fall back to treating such code as external and delegating it to the Python interpreter for sound, albeit not parallel, execution. PopPy wraps all external calls with a general exception handler; if it catches an exception, it terminates and issues an error to the user, making sure to not silently execute unsupported code. PopPy’s restrictions do not limit its ability to handle many real-world compound AI applications, and could also be lifted by extending the compiler with a continuation passing style translation [8], which we leave as future work. 4.2
Correctness Guarantee
Proposition 1 (Soundness). For all programs 𝑃 and annotations 𝐴, ⟦𝑃⟧PopPy(𝐴) ≡𝐴 ⟦𝑃⟧Python . Proof sketch. 𝜆𝑂 ’s semantics are confluent [46], i.e., the order in which internal computation is evaluated does not affect the final result. Thus, any 𝜆𝑂 evaluation order will queue the same external calls as sequential 𝜆𝑂 evaluation. The translation of Python into 𝜆𝑂 via Bezoar introduces data dependencies that faithfully capture the sequential source semantics; thus, sequential execution in PopPy produces the same trace as Python execution. The treatment of external calls via the concurrency control object may reorder calls, but only in ways that are 𝐴-equivalent to sequential PopPy execution. Therefore, PopPy execution is 𝐴-equivalent to Python execution. □
5
Compiler
PopPy transforms user-written internal Python code into 𝜆𝑂 , two languages with very different characteristics: (1) Sequentiality: Python executes sequentially and has control-flow constructs like if and for; 𝜆𝑂 executes statements in arbitrary order and only has functions. (2) Mutability: Python variables are mutable whereas 𝜆𝑂 ’s are immutable. (3) Scoping: Python’s variable scoping is implicit, complex, and unusual [55]; 𝜆𝑂 ’s is explicit and straightforward. (4) Redundancy: Python has many language features with overlapping semantics, while 𝜆𝑂 is a minimal calculus, for simplify analysis and execution. This section describes how PopPy bridges these characteristics with its two-phase compiler: we first describe the Bezoar intermediate representation and then the two phases, from Python to Bezoar (§5.1) and Bezoar to 𝜆𝑂 (§5.2).
Annotations for External Code
Users annotate external functions with Python decorators based on their reordering class:@sequential must execute in the original program order—e.g., writing the filesystem and mutating Python objects; @readonly may be reordered among themselves, but must preserve their ordering with respect to sequential calls—e.g., reading the filesystem and reading properties of mutable Python objects; @unordered may execute in any order–e.g. stateless external requests and pure operations on immutable datastructures. If a function is not annotated, it defaults to @sequential. External functions can also be marked as async to indicate that they should execute with Python’s async/await machinery; long-running external calls should use this to avoid blocking the Python interpreter. Many common libraries, including the OpenAI SDK, offer asynchronous versions of functions. PopPy provides annotations for many standard library functions (Cf. §6). Note that PopPy’s annotations are different from “parallelization annotations” in systems like Mozart [54] and PaSh [66], which primarily focus on describing whether there exists parallelization opportunities inside a single external call— e.g., by splitting a call’s inputs and then merging the outputs (Cf. §9).
Bezoar Intermediate Representation. Bezoar sits in between Python and 𝜆𝑂 , sharing features with both languages: it retains the core semantic challenges of Python—sequentiality and mutability—while making semantics explicit and only supporting minimal program constructs—if statements, for loops, function definitions, and calls. It has both mutable variables (x = ...; like Python) and immutable variables (r := ...; like 𝜆𝑂 ). Like Python, Bezoar executes sequentially, and has control-flow constructs. However, the 6
1
sequence of operations is made explicit through the use of A-normal form [26]: Bezoar lacks nested expressions (e.g., z := g(f(x))), and instead expresses each operation as a separate statement (e.g., y := f(x); z := g(y)) to facilitate encoding statement sequencing as 𝜆𝑂 data-dependencies.
2 3 4 5
Compiling PopPy to Bezoar
8
The first phase can be viewed as consisting of three steps, performed in order.
2 3
x = "foo" def f(): print(x)
4 5 6
1 2 3 4
foo() # Prints "foo"
5 6
5.2
4 5 7 8
9
9
10
10
(b) 𝜆𝑂 code, output
Sequencing of External Calls. The second challenge is that 𝜆𝑂 has no execution order—i.e., it can run code in parallel as long as data dependencies are respected. Thus, to encode the original, sequential order of external calls, we introduce “sequence variables” S. Similar to memory variables, each external call receives the previous sequence variable as input and returns a new one as output. In Fig. 4, the two print calls are sequenced through their dependency via S1. PopPy also handles Python object mutability, e.g., x.f = y, by treating Python’s getattr and setattr functions as external calls and sequencing them in the same way.
A-Normalization. PopPy makes the order of execution explicit by unfolding nested expressions, converting each subexpression to a Bezoar statement and binding the result to a new immutable variable. As an example, the method call z = x.f(y) compiles to: 2
3
M1 := store(M0, x, "foo") S1, r1 := print(S0, "bar") def _then(): r2 := load(M1, x) S2, r3 := print(S1, r2) return M1, S2 def _else(): M2 := store(M1, x, "baz") return M2, S1 M3, S3 := ite(r0, _then, _else)
the program state during execution. The call to store takes a memory state M0 and returns a new memory state, but where the key x has value "foo".
x = "foo" def f(): print(x) x = "bar" foo() # Raises NameError for x
PopPy’s first compilation pass makes Python’s scoping semantics and mutable variables explicit, with distinct declaration, load, and store constructs, facilitating later analysis and optimization of variable mutation (§7).
1
2
Figure 4. An example of the second compiler phase. Mutation, sequencing, and control-flow are converted to function calls. In 𝜆𝑂 , load, store, and ite are external functions.
Variable Scope Elaboration. Python scoping is implicit, i.e., variable declarations are determined by whether there exists an assignment in a specific scope. This leads to subtle scoping semantics, illustrated by the two snippets below that behave differently: 1
else: store x "bar"
(a) Bezoar code, input
Desugaring. PopPy first directly desugars many Python features. For example, object field access, x.y, is replaced by getattr(x, "y") and indexing, x[y], by getitem(x, y). This also includes operators, such as x += y, which becomes x = iadd(x, y).
1
6
6 7
5.1
store x "foo" r1 := print("bar") if r0: r2 := load x r3 := print(r1)
Conditionals. To address the lack of control flow constructs in 𝜆𝑂 , PopPy “functionalizes” control flow statements— i.e., it transforms them into function calls using Church encodings [17]. For if statements, each branch gets compiled into a function. The two branches, along with the condition, are then passed to a function ite (Fig. 4b, L10) that calls the _then function if the condition is true and the _else function otherwise. Note that the M and S variables also need to be passed through control flow to account for branches performing different memory accesses or external calls. As an example, the _then branch in Fig. 4b performs an external call, while the _else branch modifies a mutable variable.
r0 := load x; r1 := getattr(r0, "f"); r2 := load y; r3 := r1(r2); store z r3
Bezoar to 𝜆𝑂
The second phase of PopPy’s compiler transforms Bezoar programs to 𝜆𝑂 programs—in particular, encoding Bezoar’s mutation, sequencing, and control flow into 𝜆𝑂 , which is immutable, does not have a sequential execution order, and only supports functions. Figure 4 shows an example. Variable Mutation. The first key challenge that needs to be addressed is that 𝜆𝑂 does not have a notion of state or mutable variables, while Bezoar and Python do. To address this challenge, PopPy transforms all variable loads and stores to external calls and passes explicit “memory variables” M between them, ensuring that all variable accesses respect sequential execution semantics [68]. For example, in Fig. 4, store x "foo" (L1) is compiled to M1 := store(M0, x, "foo") (L1). The immutable variables M0 and M1 are dictionaries mapping (mutable) variable names to values, reflecting
Loops. Loops are functionalized using a similar transformation: for loops are compiled to the list function fold, which invokes a function once per element of a list, maintaining an accumulator that includes M and S and is passed between calls to the function. The loop body is compiled into the argument of the fold, updating the accumulator. After the loop completes, the final accumulator is used to set the new M and S for the rest of the program. Similarly, while loops are handled by transforming them into recursive functions. 7
6
core immutable datatypes:3 if all arguments are immutable, the call is unordered; otherwise, it is read-only.
External Calls and Concurrency Control
PopPy’s goal is to execute as many external calls in parallel as possible, while preserving the sequential program semantics. This poses two challenges. First, it needs to know which external functions can be reordered and run in parallel, and which are dependent. This is obvious when two calls have a data dependency—i.e., the return value of one is the argument of another—but this is not always the case— e.g., print calls need to be executed sequentially, but this is not visible from their arguments and return values. Second, Python’s dynamic dispatch makes it hard to determine which exact function will be invoked at each call site. This section describes how PopPy addresses these challenges with annotations (§6.1) and dynamic concurrency control (§6.2). 6.1
6.2
Dynamic Concurrency Control
Recall that 𝜆𝑂 assumes that there is a data-dependency between external calls that should be run sequentially. However, Python’s dynamic dispatch makes it impossible to know statically whether an external call is reorderable. For example, the += operator (L24) is dynamically dispatched based on the type of the left-hand side: for (immutable) tuples, it can be unordered, but for (mutable) lists, it must be sequential. As a result, the compiler ensures soundness by introducing sequencing variables S between all adjacent call sites (§5.2). However, the original 𝜆𝑂 interpreter always executes external calls with data-dependencies sequentially, so it would serialize all external calls.
Annotations and Library
Queued external calls. To address this issue, we introduce a new, queued state for external calls, between when the call has been discovered by the 𝜆𝑂 interpreter and when all of its dependencies have resolved. As soon as a call is queued, we spawn a concurrency controller for it that decides when to dispatch the call, possibly before preceding calls have finished. Because the controller operates at runtime, it knows which external function is actually being called, and thus its reordering annotation. To dispatch sequential and read-only calls, the controller must know when some or all preceding calls have resolved.
As mentioned in Section 4.2, PopPy allows users to decorate external calls with @sequential, @readonly, and @unordered to indicate when they can be run in parallel with other calls. If an annotation is missing for an external call, PopPy considers it to be @sequential, to guarantee soundness. Though users can annotate their own external functions, the goal is for external functions to be relegated to libraries and annotated once per library—e.g., by the library developer or crowdsourced—and then imported by users. Asynchronous external calls. Reordering annotations allow PopPy to execute parts of the program out of order when their arguments are ready, but external calls are run in a single Python interpreter, so if they take long to complete, they can block execution of other external calls. To address this issue, long-running external calls that should be executed in parallel should be marked as async and yield control. Most external components already offer asynchronous APIs which can be called directly, so this is not a heavy burden on the developer.
Controller communication. The inputs and outputs to each external call are available to the controller as futures; input futures can be awaited, and output futures can be fulfilled. Because the sequencing variables S are passed between adjacent call sites, we use them to communicate two key pieces of information between controllers: (1) a future 𝐹𝑅 (akin to a read lock), indicating whether all preceding “sequential” calls have resolved; and (2) a future 𝐹𝑊 (akin to a write lock), indicating whether all preceding “sequential” and “read-only” calls have resolved.
PopPy AI component library. To assist users with both annotations and asynchronous external calls, PopPy provides a library containing (1) async methods for popular AI components, and (2) annotations for these and other Python standard library calls. First, the library contains implementations of several AI components, including LLMs, text embedding models, and computer vision models, as well as a generic asynchrounous HTTP method that can be used to invoke arbitrary ML models or other stateless remote APIs. Second, it provides annotations for the above methods and the Python standard library. It annotates all 28 unary and binary operators (e.g. +, ==): if both arguments are immutable, the call is unordered; if one or both is mutable, the call is read-only (because prior mutations to the argument must be allowed to finish). It annotates all 13 in-place operators (e.g. +=): if both arguments are immutable, it is unordered; if the right-hand side is mutable, it is read-only, and if the left-hand side is mutable, it is sequential. It also annotates all 336 methods of
Implementation. Calls that are @sequential wait for both 𝐹𝑊 and 𝐹𝑅 to resolve before dispatching, guaranteeing that no other sequential or read-only call is executing while they do. After the call resolves, the controller fulfills ′ , notifying subsequent exterthe output futures 𝐹𝑅′ and 𝐹𝑊 nal calls that they can begin. Calls that are @readonly only wait for 𝐹𝑅 , allowing them to run without waiting for other read-only calls. Once 𝐹𝑅 resolves, 𝐹𝑅′ is resolved (forwarding to subsequent calls the fact that prior sequential calls have completed), and then the call is dispatched. After the call resolves, the controller waits for 𝐹𝑊 . Finally, it resolves ′ (indicating that this and all previous calls are complete). 𝐹𝑊 Call that are @unordered do not wait for either future, dispatching immediately and forwarding the input 𝐹𝑊 , 𝐹𝑅 as 3 bool, int, float, complex, str, bytes, tuple, frozenset, frozendict, date, time,
datetime, timedelta, NoneType, type, enums, Pydantic BaseModels (frozen) 8
′ , 𝐹 ′ . Implementing concurrency control this their output 𝐹𝑊 𝑅 way, by passing “locks” through the sequence variables, is extensible: finer-grained reorderability can be added in the future by passing finer-grained locks.
7
Table 1. Benchmark program characteristics. LoC is the number of lines, For and If are the number of each construct, Dyn is the number of dynamically dispatched call sites (operators or methods), Ext is the number of external function used, and Time is the ordinary Python execution time in seconds (median across 10 trials). For CaMeL, there are 30 programs, ranges are min–max across tasks.
Optimizing Variable Mutation
While reads of immutable state are always safe to execute concurrently, state mutation is not, and handling concurrent mutations is known to be challenging. By default, PopPy is conservative, matching sequential execution by ordering variable access with the memory variables from Section 6.2. While sound, serializing all variable operations in this way blocks almost all of the parallelism we want to extract. Though serialization is necessary in the worst case, we observe that in practice, most variables fall into one of two patterns that we can handle: (1) only assigned once, or (2) only accessed locally. We provide optimizations for each of these cases that avoids serialization and allows PopPy to unlock parallelism. Additionally, these optimizations allow variables to be omitted from the global memory states M, improving performance and lowering overhead.
LoC
For
If
Dyn
Ext
Time
BIRD DAE ToT SoT TRAQ
[24] [23] [74] [50] [41]
435 260 169 100 210
10 7 6 3 3
12 12 5 3 2
37 101 21 11 5
10 8 18 8 9
107 58 142 6 16
CaMeL (30)
[20]
2–114
0–7
0–17
0–53
0–8
0–4
execution (§8.2). Then, we assess PopPy’s runtime overhead and compilation time (§8.3). Finally, we evaluate whether PopPy can scale with increasing parallelism potential (§8.4).
Single-assignment variables. If a mutable variable is only assigned once, then PopPy turns it into an immutable variable, statically resolving its read operations without the need for the global memory object. To illustrate the importance of this optimization, note that Python allows library functions such as print to be reassigned. Naïvely, this means that all call sites require the function to be loaded from a variable, causing everything to be serialized. However, reassigning library functions is rare in practice, and this optimization avoids serialization in most cases.
Implementation. We have implemented a prototype of PopPy in 5427 lines of Python code. The implementation comprises 2988 LoC for the compiler and 2439 LoC for the concurrency controllers and annotations. Setup. All experiments were conducted on a machine with 24-core Intel(R) Xeon(R) Gold 6342 CPU @ 2.80GHz, with 1007GB RAM. The OS is Debian GNU/Linux 11 (bullseye) with kernel version 5.10.0-34-amd64, Python version 3.13.7, and OpenAI Python SDK version 2.16.0. For LLM calls, we used the model in the original benchmark, except where local models were used, which we replaced with OpenAI’s gpt-4omini. In all experiments, we execute applications 10 times and set temperature to 0 to make LLM calls more deterministic. Because the OpenAI API occasionally hangs for long periods of time, leading to outliers, we report medians across trials.
Local variable promotion. If a variable is only written and accessed in a local scope, PopPy uses a variable promotion SSA transformation [60] to unfold its loads and stores, avoiding the global memory object. For straight-line code (no control-flow constructs), this essentially amounts to, for a mutable variable x with 𝑛 store operations, splitting it into 𝑛 immutable variables x1 through xn, replacing the 𝑖-th store operation store x r with xi := r, and replacing each load operation load r x with r := xi, where 𝑖 is the index of the nearest preceding store operation. To handle controlflow, we mirror the way the memory (M) and sequence (S) variables are passed through the program. For each if statement and for loop, we statically determine which variables occur in load and store operations. These variables are included alongside the memory and sequence variables, being returned from conditional branches and loop bodies and reassigned by the ite and fold call sites.
8
Benchmark
8.1
Benchmarks
We collected a set of compound AI applications and a suite of LLM generated ones from the literature. We used the author’s implementation where available with minor adaptations. Tab. 1 shows an overview. Bayesian Inference from Abduction and Deduction (BIRD) [24]. A probabilistic inference framework that uses an LLM to generate and train a Bayesian network, which can then be used to compute accurate conditional probabilities. Diverse Agent Entropy (DAE) [23]. A multi-agent application for question-answering that has several agents debate among themselves to converge on an answer to the original query while also providing uncertainty quantification.
Evaluation
We evaluate PopPy on a variety of compound AI applications (§8.1) drawn from the literature. We first examine PopPy’s overall performance by comparing it to standard Python
Tree of Thoughts (ToT) [74]. An inference-time reasoning approach that performs search (e.g., beam search) using 9
Speedup
7.5 5.0 2.5 0.0
BIRD
DAE
SoT
ToT TRAQ
C-1
C-3
C-4 C-12 C-14 C-17 C-22 C-23 C-28 C-29 C-30 C-31 C-32 C-34 C-36
Figure 5. Median speedup of PopPy execution over Python across 10 trials. From CaMeL (C-𝑛) we only include applications that make at least one LLM call. Error bars show minimum to maximum speedup across trials. an LLM to both expand and score search nodes. The example in Fig. 1 is a simplified version of this implementation.
describe what they will be doing on June 13, and (2) create a new “packing list” file. CaMeL solves this by generating a program that: loops over each file in the drive and queries an LLM for whether it is a vacation plan file; asks an LLM, based on the file, what will be happening on June 13; asks an LLM, based on the file, to generate a packing list; and writes the packing list to a new file. PopPy is able to parallelize both the LLM calls that determine whether each file describes a vacation plan, as well as the two LLM calls that generate the June 13 description and the packing list. Some of the tasks are not parallelizable—e.g., CaMeL-28 makes a single LLM call to extract feedback scores from a document. For such programs, PopPy introduces overhead through its runtime, but since the execution time is dominated by the LLM call, the overhead is minimal (for CaMeL-28, indistinguishable from execution time variance).
Skeleton of Thought (SoT) [50]. An answer generation system that decomposes the process into an LLM generating an answer skeleton with multiple holes, followed by the filling of each hole by a separate LLM call. Trustworthy Retrieval Augmented Question Answering (TRAQ) [41]. An uncertainty-quantified retrieval augmented generation approach that uses a text embedding model to search for documents in a vector store, an LLM to generate multiple responses based on each document, and then a text clustering algorithm to combine related answers. Capabilities for Machine Learning (CaMeL) [20]. A collection of 39 programs for AI assistant tasks, generated by CaMeL, a prompt-injection prevention approach, for the AgentDojo [21] “workspace” benchmark: for each task, CaMeL uses an LLM to generate a Python program (which often itself contains LLM calls) based on user instructions, and then executes the generated program to solve the task. We exclude 9 programs that generate runtime errors during ordinary Python execution. 8.2
Detailed ToT Execution. To better understand the per-
Overall Performance
LLM Print
Figure 5 shows the speedups of PopPy over standard Python execution. Programs take from 0.06ms to 142s to run with standard Python. PopPy improves execution time for most programs that make LLM calls (geometric mean: 1.8×, min: 0.9×, max: 6.4×). PopPy introduces minor overhead for programs that make no LLM calls (mean overhead: −0.0 ms, max overhead: 49.1 ms)
0
Discussion. PopPy can successfully improve the end-toend execution time of all applications that involve multiple independent LLM calls. For ToT (the example shown in Section 2.2), PopPy manages to successfully uncover parallelization opportunities in both the search state expansion loop (Figure 1, L6) and the state valuation loop (L16). This is despite the complex inter-loop control-flow dependency (value_cache). As another interesting example, CaMeL-36 asks the assistant to search through a drive for a file containing vacation plans, and then based on that file, to (1)
2
4
Time (s)
6
8
Figure 6. A single execution trace of ToT (with 2 steps of search and beam size 3), showing selected external calls. Dashed lines indicate the time between queueing and dispatch; solid lines indicate the time between dispatch and resolution. (LLM calls dispatch immediately; print calls resolve immediately). Calls are sorted from top to bottom by the order in which they would be executed under sequential execution. 10
100 10 1 0
Speedup
Overhead (ms)
1000
0
1
10 Python execution time (s)
100
Figure 7. Absolute execution time overhead of PopPy vs the Python execution time, for each benchmark (median over 10 trials). Overhead is the time spent inside the 𝜆𝑂 interpreter, with all external calls annotated as sequential.
12 10 8 6 4 2 1 0 0.0
BIRD ToT
2.5
5.0
7.5
10.0 12.5 15.0 17.5 20.0
Hyperparameter Value
Figure 8. Speedup of PopPy over Python (median over 10 trials) as a function of a selected hyperparameter in each benchmark.
formance of PopPy, we zoom in on the precise timeline of external calls in a ToT execution with 2 steps of search and a beam size of 3 (Fig. 6). The execution goes through four distinct phases. The first LLM call corresponds to llm_get_ proposals for the initial search state. Execution blocks until it has completed. Then, many calls to llm_get_value execute in parallel. Once they have all completed, a print call executes, which was queued at the beginning, but had to wait for its argument (which is based on the LLM results) before it could execute. That concludes the first step of search. The process repeats, executing llm_get_proposals calls, but this time 3 in parallel (because of the beam size), and then many llm_get_value calls in parallel. A second print is then able to execute, concluding the second step of search. The whole program concludes with a final print call.
an LLM is called to assess a piece of evidence (originally set to 3), and for ToT, we vary BEAM_WIDTH (Fig. 1 L9; originally set to 5), from 1 to 20. Figure 8 shows the results. For BIRD the speedup over Python ranges from 1.51 to 10.82, and for ToT, it ranges from 2.39 to 9.80.
8.3
9
Discussion. These results show that PopPy is able to leverage increasing parallelization potential in applications. Note that the scaling is not linear because the parameters do not linearly lead to more parallelization, but just increase some LLM calls in the model—e.g., BIRD has separate, parallelizable LLM calls for generating additional information about the task. Furthermore, note that for ToT speedup is above 1 even for BEAM_WIDTH = 1 as the program has additional parallelism: llm_get_proposals (Fig. 1, L7) returns a list of states, which get_values can loop over in parallel.
Overheads
In this section, we evaluate PopPy’s compilation time and its execution overhead when there is no parallelization.
There are three main lines of related work, each of which has a limitation compared to PopPy: (1) There has been work prior work on parallelization of programs with external calls; however, none of them can support imperative code or Python in particular. (2) There has been prior work on specialized systems for optimizing compound AI applications; while some of them can exploit some degree of parallelization, they either have limited expressiveness or require manual parallelization. (3) There has been prior work on Python optimization; however, none of them can extract parallelism across external calls. Below, we expand on these and other lines of related work.
Compilation. PopPy compilation time for all applications ranges from 0.34ms to 51.15ms, making it fast enough to be used in the critical path when running such programs. Execution time. To evaluate the overhead of PopPy’s interpreter and runtime, we measure the execution time of all applications using PopPy with all external calls annotated as sequential. We instrument the system to track how much execution time is spent inside the 𝜆𝑂 interpreter. Figure 7 shows this interpreter overhead for each benchmark. For programs with no LLM calls (Python running time ≈ 0s), the absolute overhead is between 0.01ms and 208.35ms. For those with LLM calls, the absolute overhead is between 1.55ms and 3.77s, and the relative overhead between 0.15% and 11.18%. 8.4
Related Work
Automatic parallelization of general-purpose languages. There is an enormous literature on automatic parallelization [2, 3, 7, 9, 19, 22, 25, 29, 35, 36, 44, 45, 57, 69] of generalpurpose languages. While most of this existing work does not support extracting parallelism from programs bottlenecked at external calls, there has been recent interest in doing so [47, 54, 56, 67]. Most relatedly, PaSh [34, 66] focuses on shell scripts, extracting parallelism across blackbox external components; however, PaSh does not provide
Scaling
To evaluate whether PopPy can scale with more parallelization opportunities, we execute two programs (BIRD and ToT) that have a configurable hyperparameter affecting how many LLM calls are made. For BIRD, we vary the number of times 11
solutions for the challenges of Python code addressed by PopPy (e.g., function definitions, scoping, variable mutation, and dynamic dispatch). Other systems in this space have different goals from PopPy, though they also use external call annotations to specify key properties such as: (1) providing distribution and offloading hints (e.g., in POSH [56] and Ignis [67]), (2) describing the inputs and outputs of an external call (e.g., in PaSh [66] and DiSh [47] that focus on shell commands whose inputs and outputs cannot be directly identified), or (3) describing how to split the inputs of an external call to enable data parallelism (e.g., in Mozart [54] and PaSh [66]). Drawing inspiration from these systems, PopPy also uses annotations to specify important properties of the external code, though theirs describe the filesystem accesses and shardability of functions and commands, whereas ours describe how function reorderability varies based on call arguments. Finally, 𝜆𝑂 [46] is a core calculus for automatically extracting external-call parallelism; however, it does not operate on real-world programs, and does not handle issues like complex scoping, variable mutation, and dynamic dispatch. PopPy builds on this work by bridging the gap between 𝜆𝑂 and real-world Python code.
combining an ahead-of-time component with a runtime component to deal with Python’s dynamic features such as dynamic dispatch and mutation. At the same time, PopPy has a very different focus from these systems and therefore also addresses different challenges. Namely, all these systems try to optimize applications where the bottleneck is code written in Python. Because of this, they often make restrictive assumptions about what code can be supported by their systems, since the goal is to apply aggressive optimizations to Python internal code. In contrast, PopPy focuses on applications where the bottleneck is in external components, and the internal Python code is used to orchestrate the application. The key goal of PopPy is to extract parallelization opportunities by analyzing the orchestration code, addressing challenges related to discovering and preserving dependencies across external calls in the context of dynamic dispatch and making sure that the Python code does not force unnecessary sequentialization in the context of mutation. Parallelizable AI Agents. One line of work for reducing AI agent latency is to design AI agents that think and act in more parallelizable ways. For instance, Skeleton-ofThought [50] is an agent decoding approach that is intended to make decoding faster by decomposing generation into a skeleton generation step, followed by parallel generations to fill holes in the skeleton. However, their implementation does not actually execute in parallel (instead executing sequentially and estimating the speedup by adding the skeleton generation time to the longest hole generation time). We obtain the desired speedup on their implementation, demonstrating the value of our approach. APAR [43] and PASTA [32] are similar approaches, allowing models to generate special tokens which fork the generation process, leading to parallel generation. Our work is complimentary to these, as it helps exploit the parallelization opportunities that these designs provide.
Optimizations for compound AI applications. There is a significant body of work on frameworks for writing and optimizing compound AI applications [15, 16, 37, 48, 59, 77]; however, all of these systems assume that the compound AI application is written in a domain-specific language that is not as expressive as general-purpose Python. For example, LangChain [15], n8n [48], DataFlow [42], and Murakkab [16] all support restricted workflow descriptions without control flow, and are unable to support applications such as Tree-ofThoughts. SGLang [77] offers a DSL for expressing certain kinds of compound AI applications, but parallelism has to be handled manually and it has no support for other kinds of external calls, such as embedding models. Python optimization. Recent work improves the performance of Python programs by transforming and optimizing bottleneck fragments in them [4, 10, 13, 33, 38, 53, 61, 63, 78]. Their key focus is to identify small bottleneck fragments of the internal Python computation (e.g., UDFs that are used as part of a data analytics application [33, 63] or tensor computations [4, 13]), understand their semantics and transform them into a different representation (e.g., LLVM or XLA), and finally apply aggressive optimizations to them. Furthermore, Python has long been supported by a general purpose JIT compiler ecosystem, including PyPy [12] and more recently CPython’s JIT compiler [14]. All of this work identifies that Python is hard to precisely analyze ahead-of-time, so they combine static analysis passes with runtime components that leverage runtime execution information to make analysis more precise. PopPy follows the same hybrid approach,
10
Conclusion
We have proposed PopPy, a system focused on automatically parallelizing compound AI applications written in Python. Our key insight is that compound AI applications are bottlenecked by calls to external code such as ML models; as a consequence, effective parallelization relies on identifying external calls that can be run in parallel. PopPy solves a number of challenges to surfacing these opportunities in Python code, including the complexity of Python, dynamic dispatch, and variable mutation. Our experiments demonstrate that PopPy reduces execution time by up to 6.4× compared to standard Python execution while preserving the sequential program semantics. More broadly, we believe that PopPy provides an ideal balance between expressiveness and simplicity, making it easy to implement additional features for supporting compound AI applications. 12
References
IO-Awareness. In Advances in Neural Information Processing Systems, Vol. 35. 16344–16359. [19] Alan L. Davis and Robert M. Keller. 1982. Data Flow Program Graphs. Computer 15, 02 (2 1982), 26–41. [20] Edoardo Debenedetti, Ilia Shumailov, Tianqi Fan, Jamie Hayes, Nicholas Carlini, Daniel Fabian, Christoph Kern, Chongyang Shi, Andreas Terzis, and Florian Tramèr. 2026. Defeating Prompt Injections by Design. arXiv preprint arXiv:2503.18813. In IEEE Conference on Secure and Trustworthy Machine Learning (SaTML). https: //arxiv.org/abs/2503.18813 [21] Edoardo Debenedetti, Jie Zhang, Mislav Balunovic, Luca BeurerKellner, Marc Fischer, and Florian Tramèr. 2024. Agentdojo: A dynamic environment to evaluate prompt injection attacks and defenses for llm agents. Advances in Neural Information Processing Systems 37 (2024), 82895–82920. [22] Jack B. Dennis. 1974. First version of a data flow procedure language. In Programming Symposium, B. Robinet (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 362–376. [23] Yu Feng, Phu Mon Htut, Zheng Qi, Wei Xiao, Manuel Mager, Nikolaos Pappas, Kishaloy Halder, Yang Li, Yassine Benajiba, and Dan Roth. 2025. Rethinking LLM Uncertainty: A Multi-Agent Approach to Estimating Black-Box Model Uncertainty. In Findings of the Association for Computational Linguistics: EMNLP 2025, Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng (Eds.). Association for Computational Linguistics, Suzhou, China, 12349–12375. https://doi.org/10.18653/v1/2025.findings-emnlp.660 [24] Yu Feng, Ben Zhou, Weidong Lin, and Dan Roth. 2025. BIRD: A Trustworthy Bayesian Inference Framework for Large Language Models. In The Thirteenth International Conference on Learning Representations. https://openreview.net/forum?id=fAAaT826Vv [25] John T. Feo, David C. Cann, and Rodney R. Oldehoeft. 1990. A report on the sisal language project. J. Parallel and Distrib. Comput. 10, 4 (1990), 349–366. https://doi.org/10.1016/0743-7315(90)90035-N Data-flow Processing. [26] Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The essence of compiling with continuations. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation (Albuquerque, New Mexico, USA) (PLDI ’93). Association for Computing Machinery, New York, NY, USA, 237–247. https://doi.org/10.1145/155090.155113 [27] Gemini Team, Google. 2023. Gemini: A Family of Highly Capable Multimodal Models. arXiv preprint arXiv:2312.11805 (2023). [28] GitHub Staff. 2025. Octoverse: A new developer joins GitHub every second as AI leads TypeScript to #1. https://github.blog/news-insights/ octoverse/. Accessed: 2026-03-30. [29] Robert H. Halstead. 1985. MULTILISP: a language for concurrent symbolic computation. ACM Trans. Program. Lang. Syst. 7, 4 (Oct. 1985), 501–538. https://doi.org/10.1145/4472.4478 [30] Kang He and Kaushik Roy. 2025. LogicTree: Structured Proof Exploration for Coherent and Rigorous Logical Reasoning with Large Language Models. arXiv preprint arXiv:2504.14089 (2025). [31] Carlos E. Jimenez, John Yang, S. Friedman, et al. 2024. SWE-bench: Can Language Models Resolve Real-World GitHub Issues? arXiv preprint arXiv:2310.06770 (2024). [32] Tian Jin, Ellie Y Cheng, Zachary Ankner, Nikunj Saunshi, Blake M Elias, Amir Yazdanbakhsh, Jonathan Ragan-Kelley, Suvinay Subramanian, and Michael Carbin. 2025. Learning to Keep a Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding. In Forty-second International Conference on Machine Learning. https://openreview.net/forum?id=ZfX43ZZRZR [33] Michael Jungmair, Alexis Engelke, and Jana Giceva. 2024. HiPy: Extracting High-Level Semantics from Python Code for Data Processing. Proc. ACM Program. Lang. 8, OOPSLA2, Article 297 (Oct. 2024), 27 pages. https://doi.org/10.1145/3689737
[1] 2023. Official Repo of Tree of Thoughts. https://github.com/princetonnlp/tree-of-thought-llm [2] Duane A. Adams. 1968. A Computation Model with Data-Sequenced Control. Technical Report. Stanford University. Technical Report CGTM 45. [3] Duane A. Adams. 1969. A Computation Model with Data Flow Sequencing. Ph. D. Dissertation. [4] Jason Ansel, Edward Yang, Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesensky, Bin Bao, Peter Bell, David Berard, Evgeni Burovski, et al. 2024. Pytorch 2: Faster machine learning through dynamic python bytecode transformation and graph compilation. In Proceedings of the 29th ACM international conference on architectural support for programming languages and operating systems, volume 2. 929–947. [5] Anthropic. 2024. The Claude 3 Model Family: Opus, Sonnet, Haiku. https://www-cdn.anthropic.com/ de8ba9b01c9ab7cbabf5c33b80b7bbc618857627/Model_Card_ Claude_3.pdf. [6] Anthropic. 2025. How we built our multi-agent research system. https: //www.anthropic.com/engineering/multi-agent-research-system. Accessed: 2026-04-01. [7] Sotiris Apostolakis, Ziyang Xu, Greg Chan, Simone Campanoni, and David I August. 2020. Perspective: A sensible approach to speculative automatic parallelization. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. 351–367. [8] Andrew W. Appel. 1991. Compiling with Continuations. Cambridge University Press. [9] Rishiyur S Nikhil Arvind. 1992. Id: a language with implicit parallelism. In A Comparative Study of Parallel Programming Languages. Elsevier, 169–215. [10] Stefanos Baziotis, Daniel Kang, and Charith Mendis. 2024. Dias: Dynamic rewriting of Pandas code. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–27. [11] Luca Beurer-Kellner, Marc Fischer, and Martin T. Vechev. 2023. Prompting Is Programming: A Query Language for Large Language Models. In Proceedings of the 44th ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, 1946–1969. https://doi.org/10.1145/3591300 [12] Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, and Armin Rigo. 2009. Tracing the Meta-Level: PyPy’s Tracing JIT Compiler. In Proceedings of the 4th Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (ICOOOLPS). ACM, 18–25. https://doi.org/10.1145/1565824.1565827 [13] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, et al. 2021. Jax: Autograd and xla. Astrophysics Source Code Library (2021), ascl–2111. [14] Brandt Bucher and Savannah Ostrowski. 2024. PEP 744: JIT Compilation. https://peps.python.org/pep-0744/. Python Enhancement Proposal, Draft status. [15] Harrison Chase. 2023. LangChain. https://github.com/langchainai/langchain. [16] Gohar Irfan Chaudhry, Esha Choukse, Íñigo Goiri, Rodrigo Fonseca, Adam Belay, and Ricardo Bianchini. 2025. Towards Resource-Efficient Compound AI Systems. In Proceedings of the 2025 Workshop on Hot Topics in Operating Systems (Banff, AB, Canada) (HotOS ’25). Association for Computing Machinery, New York, NY, USA, 218–224. https://doi.org/10.1145/3713082.3730377 [17] Alonzo Church. 1941. The Calculi of Lambda-Conversion. Annals of Mathematics Studies, Vol. 6. Princeton University Press. [18] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022. FlashAttention: Fast and Memory-Efficient Exact Attention with 13
[50] Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang, and Yu Wang. 2024. Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation. In The Twelfth International Conference on Learning Representations. https://openreview.net/forum?id=mqVgBbNCm9 [51] OpenAI. 2023. GPT-4 Technical Report. Technical Report. OpenAI. arXiv preprint arXiv:2303.08774. [52] OpenAI. 2025. OpenAI Agents SDK. https://github.com/openai/openaiagents-python [53] Shoumik Palkar, James J Thomas, Anil Shanbhag, Deepak Narayanan, Holger Pirk, Malte Schwarzkopf, Saman Amarasinghe, and Matei Zaharia. 2017. Weld: A common runtime for high performance data analytics. (2017). [54] Shoumik Palkar and Matei Zaharia. 2019. Optimizing Data-Intensive Computations in Existing Libraries with Split Annotations. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (Huntsville, ON, Canada) (SOSP ’19). ACM, 291–305. https: //doi.org/10.1145/3341301.3359652 [55] Joe Gibbs Politz, Alejandro Martinez, Mae Milano, Sumner Warren, Daniel Patterson, Junsong Li, Anand Chitipothu, and Shriram Krishnamurthi. 2013. Python: the full monty. SIGPLAN Not. 48, 10 (Oct. 2013), 217–232. https://doi.org/10.1145/2544173.2509536 [56] Deepti Raghavan, Sadjad Fouladi, Philip Levis, and Matei Zaharia. 2020. POSH: A Data-Aware Shell. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). 617–631. [57] Jorge E. Rodriguez. 1969. A Graph Model for Parallel Computations. Ph. D. Dissertation. MIT-LCS-TR64. [58] Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. 2024. Mathematical discoveries from program search with large language models. Nature 625, 7995 (2024), 468–475. https://doi.org/10.1038/s41586-023-06924-6 [59] Keshav Santhanam, Deepti Raghavan, Muhammad Shahir Rahman, Thejas Venkatesh, Neha Kunjal, Pratiksha Thaker, Philip Levis, and Matei Zaharia. 2024. ALTO: An Efficient Network Orchestrator for Compound AI Systems. In Proceedings of the 4th Workshop on Machine Learning and Systems (Athens, Greece) (EuroMLSys ’24). Association for Computing Machinery, New York, NY, USA, 117–125. https: //doi.org/10.1145/3642970.3655844 [60] A.V.S. Sastry and Roy D.C. Ju. 1998. A New Algorithm for Scalar Register Promotion Based on SSA Form. PLDI ’98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation (1998). [61] Ariya Shajii, Gabriel Ramirez, Haris Smajlović, Jessica Ray, Bonnie Berger, Saman Amarasinghe, and Ibrahim Numanagić. 2023. Codon: A Compiler for High-Performance Pythonic Applications and DSLs. In Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction (Montréal, QC, Canada) (CC 2023). Association for Computing Machinery, New York, NY, USA, 191–202. https: //doi.org/10.1145/3578360.3580275 [62] Jonathan Silva, Qin Ma, Jordi Cabot, Pierre Kelsen, and Henderik A. Proper. 2024. Application of the Tree-of-Thoughts Framework to LLM-Enabled Domain Modeling. In Conceptual Modeling: 43rd International Conference, ER 2024, Pittsburgh, PA, USA, October 28–31, 2024, Proceedings (Pittsburg, PA, USA). Springer-Verlag, Berlin, Heidelberg, 94–111. https://doi.org/10.1007/978-3-031-75872-0_6 [63] Leonhard Spiegelberg, Rahul Yesantharao, Malte Schwarzkopf, and Tim Kraska. 2021. Tuplex: Data Science in Python at Native Code Speed. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 1718–1731. https: //doi.org/10.1145/3448016.3457244 [64] David Suris et al. 2023. ViperGPT: Visual Inference via Python Execution for Reasoning. arXiv preprint arXiv:2303.08128 (2023).
[34] Konstantinos Kallas, Tammam Mustafa, Jan Bielak, Dimitris Karnikis, Thurston HY Dang, Michael Greenberg, and Nikos Vasilakis. 2022. Practically correct,Just-in-Time shell script parallelization. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 769–785. [35] Richard M. Karp and Raymond Miller. 1966. Properties of a Model for Parallel Computation: Determinacy, Termination, Queueing. SlAM J. of Applied Mathematics 14, 6 (11 1966), 1390–1411. [36] Richard M. Karp and Raymond Miller. 1969. Parallel Program Schemata. J. Comput. System Sci. 3 (1969), 147–195. [37] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. 2024. DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines. The Twelfth International Conference on Learning Representations. [38] Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. 2015. Numba: A llvm-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC. 1–6. [39] LangChain Inc. 2024. LangGraph: Build Resilient Language Agents as Graphs. https://github.com/langchain-ai/langgraph [40] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in neural information processing systems 33 (2020), 9459–9474. [41] Shuo Li, Sangdon Park, Insup Lee, and Osbert Bastani. 2024. TRAQ: Trustworthy Retrieval Augmented Question Answering via Conformal Prediction. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), Kevin Duh, Helena Gomez, and Steven Bethard (Eds.). Association for Computational Linguistics, Mexico City, Mexico, 3799–3821. https://doi.org/10.18653/v1/2024. naacl-long.210 [42] Hao Liang, Xiaochen Ma, Zhou Liu, Zhen Hao Wong, Zhengyang Zhao, Zimo Meng, Runming He, Chengyu Shen, Qifeng Cai, Zhaoyang Han, et al. 2025. DataFlow: An LLM-Driven Framework for Unified Data Preparation and Workflow Automation in the Era of Data-Centric AI. arXiv preprint arXiv:2512.16676 (2025). [43] Mingdao Liu, Aohan Zeng, Bowen Wang, Peng Zhang, Jie Tang, and Yuxiao Dong. 2024. APAR: LLMs Can Do Auto-Parallel AutoRegressive Decoding. arXiv:2401.06761 [cs.CL] https://arxiv.org/abs/ 2401.06761 [44] Shail Aditya Arvind Jan-Willem Maessen, Lennart Augustsson, and Rishiyur S Nikhil. 1995. Semantics of pH: A parallel dialect of Haskell. In In Proceedings from the Haskell Workshop (at FPCA 95). 35–49. [45] James R McGraw. 1982. The VAL language: Description and analysis. ACM Transactions on Programming Languages and Systems (TOPLAS) 4, 1 (1982), 44–82. [46] Stephen Mell, Konstantinos Kallas, Steve Zdancewic, and Osbert Bastani. 2025. Opportunistically Parallel Lambda Calculus. Proc. ACM Program. Lang. 9, OOPSLA2, Article 365 (Oct. 2025), 27 pages. https://doi.org/10.1145/3763143 [47] Tammam Mustafa, Konstantinos Kallas, Pratyush Das, and Nikos Vasilakis. 2023. DiSh: Dynamic Shell-Script Distribution. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). 341–356. [48] n8n.io. 2026. n8n: Fair-code workflow automation platform with native AI capabilities. https://github.com/n8n-io/n8n [49] Ziyi Ni, Yifan Li, Ning Yang, Dou Shen, Pin Lyu, and Daxiang Dong. 2025. Tree-of-code: A self-growing tree framework for end-to-end code generation and execution in complex tasks. In Findings of the Association for Computational Linguistics: ACL 2025. 9804–9819.
14
[65] Trieu Trinh, Yuhuai Wu, Quoc V. Le, He He, and Minh-Thang Luong. 2024. Solving Olympiad Geometry without Human Demonstrations. Nature 625 (2024), 476–482. https://doi.org/10.1038/s41586-023-067475 [66] Nikos Vasilakis, Konstantinos Kallas, Konstantinos Mamouras, Achilles Benetopoulos, and Lazar Cvetković. 2021. PaSh: Light-Touch Data-Parallel Shell Processing. In Proceedings of the Sixteenth European Conference on Computer Systems (Online Event, United Kingdom) (EuroSys ’21). Association for Computing Machinery, New York, NY, USA, 49–66. https://doi.org/10.1145/3447786.3456228 [67] Nikos Vasilakis, Ben Karel, Yash Palkhiwala, John Sonchack, André DeHon, and Jonathan M. Smith. 2019. Ignis: Scaling DistributionOblivious Systems with Light-Touch Distribution. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). ACM, 1010–1026. https://doi.org/10.1145/3314221.3314586 [68] Philip Wadler. 1990. Comprehending monads. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming (Nice, France) (LFP ’90). Association for Computing Machinery, New York, NY, USA, 61–78. https://doi.org/10.1145/91556.91592 [69] Paul G. Whiting and Robert S. V. Pascoe. 1994. A history of data-flow languages. IEEE Annals of the History of Computing 16 (1994), 38–59. https://api.semanticscholar.org/CorpusID:7384421 [70] Brandon T. Willard et al. 2023. Guidance: A Guidance Language for Controlling Large Language Models. https://github.com/guidanceai/guidance [71] Mengdi Wu, Xinhao Cheng, Shengyu Liu, Chunan Shi, Jianan Ji, Kit Ao, Praveen Velliengiri, Xupeng Miao, Oded Padon, and Zhihao Jia. 2025. Mirage: A Multi-Level Superoptimizer for Tensor Programs. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25). USENIX Association, 1–18. [72] Wenjiang Xu, Cindy Wang, Rui Fang, Mingkang Zhang, Lusong Li, Jing Xu, Jiayuan Gu, Zecui Zeng, and Rui Chen. 2025. Embodied Tree of Thoughts: Deliberate Manipulation Planning with Embodied World Model. arXiv:2512.08188 [cs.RO] https://arxiv.org/abs/2512.08188 [73] John Yang, Carlos E Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. 2024. Swe-agent: Agentcomputer interfaces enable automated software engineering. Advances in Neural Information Processing Systems 37 (2024), 50528–50652. [74] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. Advances in neural information processing systems 36 (2023), 11809–11822. [75] Matei Zaharia, Omar Khattab, Lingjiao Chen, Jared Quincy Davis, Heather Miller, Chris Potts, James Zou, Michael Carbin, Jonathan Frankle, Naveen Rao, and Ali Ghodsi. 2024. The Shift from Models to Compound AI Systems. https://bair.berkeley.edu/blog/2024/02/18/ compound-ai-systems/. [76] Alex L Zhang, Tim Kraska, and Omar Khattab. 2025. Recursive language models. arXiv preprint arXiv:2512.24601 (2025). [77] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. 2024. SGLang: Efficient Execution of Structured Language Model Programs. In Advances in Neural Information Processing Systems, A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (Eds.), Vol. 37. Curran Associates, Inc., 62557–62583. https://doi.org/10.52202/0790172000 [78] Tong Zhou, Jun Shirako, and Vivek Sarkar. 2024. APPy: Annotated Parallelism for Python on GPUs. In Proceedings of the 33rd ACM SIGPLAN International Conference on Compiler Construction. 113–125.
15