💻 computer science

Package Managers Ã la Carte: A Formal Model of Dependency Resolution

This paper introduces the Package Calculus, a formal model that unifies the diverse semantics of package managers across programming ecosystems to enable precise cross-language dependency expression and improve supply-chain analysis.

Original authors: Ryan Gibb, Patrick Ferris, David Allsopp, Thomas Gazagnaire, Anil Madhavapeddy

Published 2026-07-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ryan Gibb, Patrick Ferris, David Allsopp, Thomas Gazagnaire, Anil Madhavapeddy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Software Tower of Babel

Imagine you are building a massive, intricate castle. In the real world, you might need bricks from one quarry, mortar from another, and stained glass from a third. If these suppliers don't speak the same language or use different measuring tapes, your castle might crumble before it's finished. This is exactly the problem facing the digital world of software.

In the realm of computer science, specifically in a field called programming languages and software engineering, developers build applications using code written in many different "languages" (like Python, Rust, or OCaml). To make these programs work, they rely on pre-built pieces of code called packages. Think of a package as a pre-fabricated room for your castle: a library of tools, a database, or a graphics engine.

However, every programming language has its own "package manager," a digital foreman that finds and installs these rooms. The problem is that these foremen speak different dialects. The Python foreman (called pip) doesn't understand the Rust foreman (Cargo), and neither can talk to the Linux system foreman (APT). They all have different rules for how rooms fit together. If you try to build a project that uses Python, Rust, and C code all at once, you end up with a chaotic mess where the Python rooms don't fit the Rust walls, and the whole structure becomes a security risk because no one can see the full blueprint of how everything connects.

The Universal Translator for Software Rooms

This paper, titled "Package Managers à la Carte," by researchers from the University of Cambridge and industry partners, proposes a solution to this chaos. They aren't trying to force every package manager to speak the exact same language immediately. Instead, they have invented a universal grammar called the Package Calculus.

Think of the Package Calculus as a "lingua franca" or a universal translator for software dependencies. The authors realized that despite the wild differences between package managers, they all share a tiny, common core. At their heart, they all do three simple things:

Root Inclusion: You must include the main project you are building.
Dependency Closure: If you install a room, you must also install all the smaller rooms it needs to stand up.
Version Uniqueness: You can't have two different versions of the same room type installed in the same spot at the same time (usually).

The paper proves that this small core is powerful enough to describe the behavior of over thirty different package managers, from the ancient Perl archives to modern Rust tools. The researchers didn't just guess this; they built a rigorous mathematical model and even wrote a computer program (using a tool called Lean 4) to prove their logic is sound.

The "À La Carte" Menu of Features

The real magic of the paper is how it handles the differences. The authors realized that the complex features that make package managers unique—like allowing multiple versions of a library to coexist, or letting a package say "I need either library A or library B"—are just special "add-ons" to that simple core.

They call this approach "à la carte," like ordering from a menu. You can order the basic core, and then add specific extensions for things like:

Conflicts: "I absolutely cannot install this package with that one."
Concurrent Versions: "I need two different versions of this library to run side-by-side."
Peer Dependencies: "I need my neighbor to have a specific version of a library, even though I don't use it directly."
Features: "If you turn on the 'graphics' option, I need these extra tools."

The paper shows that every one of these complex features can be mathematically "reduced" back to the simple core. It's like showing that a complex recipe for a soufflé can be broken down into basic steps of mixing, heating, and folding. By translating every ecosystem's rules into this common core, the researchers demonstrate that we can finally solve the dependency puzzle for a project that spans multiple languages all at once.

Why This Matters: The Polyglot Resolver

The ultimate goal described in the paper is a polyglot resolver. Currently, if you want to build a project using Python, Rust, and C, you have to run three separate package managers, hoping they don't break each other. The authors suggest that in the future, we could have a single "super-resolver."

Here is how it would work:

The Python part of your project translates its needs into the Package Calculus.
The Rust part does the same.
The C part does the same.
The super-resolver combines them all into one giant, unified puzzle and solves it, ensuring that the Python library, the Rust library, and the C driver all agree on which versions to use.

The paper argues that this is not just a nice idea, but a necessary step for security and stability. When dependencies are hidden or unversioned across different ecosystems, it becomes impossible to track security vulnerabilities. By unifying the semantics, we can see the full "dependency graph"—the complete map of every piece of code your software relies on.

The authors are careful to note that this doesn't mean every package manager will disappear tomorrow. Instead, this formal model provides the theoretical foundation for building tools that can translate between ecosystems. They show that while the problem of finding the perfect set of versions is mathematically difficult (specifically, it is "NP-complete," meaning it gets exponentially harder as the project grows), we can navigate this complexity by understanding the underlying rules.

In short, the paper doesn't just point out that the current system is broken; it provides the blueprints for a new kind of construction site where software from different worlds can finally build together without falling apart. It turns a chaotic jumble of isolated tools into a coherent, unified system, paving the way for safer, more reliable, and truly cross-language software projects.

Technical Summary: Package Managers à la Carte

Problem Statement

Package managers are ubiquitous across operating systems and programming languages, yet they remain fundamentally non-interoperable. Despite solving the same core problem—selecting a consistent set of package versions to satisfy a project's dependencies—each ecosystem employs ad hoc, fragmented semantics. This fragmentation prevents multilingual projects from expressing precise cross-ecosystem dependencies, leaves external system dependencies implicit and unversioned, and obscures the full dependency graph required for supply-chain security analysis. Current interoperability efforts focus on sharing solving mechanisms between ecosystems with identical semantics, failing to address the underlying diversity in how dependencies are expressed.

Methodology

The authors propose the Package Calculus, a minimal formal system designed to serve as a lingua franca for dependency expression. The methodology follows a "core-and-extension" approach:

Core Formalization: The authors define a minimal kernel capturing the universal conditions of dependency resolution: Root Inclusion (the requested package is installed), Dependency Closure (all dependencies are satisfied), and Version Uniqueness (at most one version of a package name is installed). They prove that solving this core problem is NP-complete via reduction from 3-SAT.
Extension and Reduction: The paper identifies specific axes of divergence in real-world package managers (e.g., conflicts, concurrent versions, peer dependencies, features, Boolean formulae, virtual packages). For each axis, the authors define an extended calculus and, crucially, provide a sound and complete reduction back to the core calculus. These reductions act as compilation passes, translating complex, ecosystem-specific dependency expressions into the core formalism.
Composition: The authors demonstrate how these extensions can be composed to model real-world package managers that combine multiple features (e.g., Cargo's combination of concurrent versions and features). They outline the considerations required to compose reductions, such as handling invariant violations between extensions.
Mechanization: All theorems presented in the paper are mechanized in Lean 4.

Key Contributions

A Unified Survey: A survey of over thirty package managers identifying a shared core and the specific axes along which they diverge, including version constraints, conflicts, concurrent versions, peer dependencies, features, package formulae, variable formulae, virtual packages, and optional dependencies.
The Package Calculus: A minimal formal system capturing the essence of dependency resolution. The authors show that while the core problem is NP-complete, this complexity is inherent to capturing real-world expressiveness; restricted approaches (like Go's Minimal Version Selection) avoid NP-completeness by sacrificing expressiveness.
Reductions for Divergence: A formal model for each axis of divergence as an extension to the core, accompanied by a reduction back to the core. These reductions preserve satisfiability (valid resolutions remain valid) but do not necessarily preserve optimality.
Composability: A demonstration that extensions can be composed to model complex, real-world package managers. The paper provides a framework for constructing calculi that combine multiple extensions (e.g., Concurrent Feature Package Calculus).
Polyglot Resolution Pathway: A theoretical foundation for a "polyglot resolver." By reducing dependencies from multiple ecosystems to the core calculus, a single resolver could theoretically solve a project spanning multiple languages and operating systems as a unified instance.

Results

The paper establishes that the core Package Calculus is expressive enough to model the diversity of real-world dependency expression languages through a series of formal reductions.

Complexity: The authors confirm that dependency resolution is NP-complete in the general case. They analyze how different ecosystems navigate this spectrum: Go's MVS achieves linear-time resolution by restricting constraints to lower bounds and removing version uniqueness for major versions; Nix sidesteps the problem by requiring exact versions (singular dependencies); while systems like opam and Cargo accept NP-completeness to maintain expressiveness.
Reduction Validity: For every extension (Conflicts, Concurrent Versions, Peer Dependencies, Features, Package Formulae, Variable Formulae, Virtual Packages), the paper provides a reduction to the core. Theorems of Soundness and Completeness are proven for each, ensuring that a resolution exists in the extended calculus if and only if a resolution exists in the reduced core calculus.
Composition: The paper successfully models the composition of extensions, specifically demonstrating how to combine Concurrent Versions and Features, which are common in modern ecosystems like Rust (Cargo).

Significance and Claims

The paper claims to provide the theoretical foundation for principled cross-ecosystem tooling that has been lacking to date. By unifying the semantics of dependency expression, the Package Calculus enables:

Cross-Ecosystem Comparison: Superficially different mechanisms can be identified as the same construct or distinguished where they differ.
Polyglot Resolution: A project spanning several ecosystems can be resolved as a single unit by compiling each ecosystem's dependencies into the core and solving the combined instance.
Translation as an Intermediate Representation: The core calculus could serve as an intermediate representation for translating dependencies from one ecosystem's language to another, reducing the complexity of cross-ecosystem translation from $O(n^2)$ direct translators to $2n$ frontend/backend translators.

The authors remain modest regarding the immediate realization of these goals. They note that while single-extension reductions can be inverted (lifted) to recover the original instance, inverting composed reductions (where synthetic structures interleave) is an open problem requiring explicit definition for each composition. Consequently, while the calculus reduces cross-ecosystem translation to a well-defined problem (inverting composed reductions), the actual implementation of translators and polyglot resolvers is left as future work. The paper does not claim to solve the problem of build system integration or the specific challenges of sandboxed builds, but rather provides the formal semantics necessary to address dependency resolution across these boundaries.