💻 computer science

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

Dieses Paper führt die Package Calculus ein, ein formales Modell, das die vielfältigen Semantiken von Paketmanagern über verschiedene Programmier-Ökosysteme hinweg vereinheitlicht, um eine präzise sprachenübergreifende Ausdruck von Abhängigkeiten zu ermöglichen und die Analyse der Lieferkette zu verbessern.

Ursprüngliche Autoren: Ryan Gibb, Patrick Ferris, David Allsopp, Thomas Gazagnaire, Anil Madhavapeddy

Veröffentlicht 2026-07-20

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ryan Gibb, Patrick Ferris, David Allsopp, Thomas Gazagnaire, Anil Madhavapeddy

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Der große Software-Turmbau zu Babel

Stellen Sie sich vor, Sie bauen eine massive, komplexe Burg. In der realen Welt benötigen Sie vielleicht Ziegel aus einem Steinbruch, Mörtel aus einem anderen und Buntglas aus einem dritten. Wenn diese Lieferanten nicht dieselbe Sprache sprechen oder unterschiedliche Maßeinheiten verwenden, könnte Ihre Burg zusammenbrechen, noch bevor sie fertiggestellt ist. Genau das ist das Problem, vor dem die digitale Welt der Software steht.

Im Bereich der Informatik, speziell in einem Feld namens Programmiersprachen und Softwaretechnik, bauen Entwickler Anwendungen mithilfe von Code, der in vielen verschiedenen „Sprachen“ geschrieben ist (wie Python, Rust oder OCaml). Um diese Programme funktionsfähig zu machen, verlassen sie sich auf vorgefertigte Code-Teile, die sogenannten Pakete. Betrachten Sie ein Paket als ein vorgefertigtes Zimmer für Ihre Burg: eine Bibliothek von Werkzeugen, eine Datenbank oder eine Grafik-Engine.

Jede Programmiersprache hat jedoch ihren eigenen „Paketmanager“, einen digitalen Vorarbeiter, der diese Zimmer findet und installiert. Das Problem ist, dass diese Vorarbeiter verschiedene Dialekte sprechen. Der Python-Vorarbeiter (genannt pip) versteht den Rust-Vorarbeiter (Cargo) nicht, und keiner von beiden kann mit dem Linux-System-Vorarbeiter (APT) kommunizieren. Sie alle haben unterschiedliche Regeln dafür, wie die Zimmer zusammenpassen. Wenn Sie versuchen, ein Projekt zu bauen, das gleichzeitig Python, Rust und C verwendet, entsteht ein chaotisches Durcheinander, bei dem die Python-Zimmer nicht an die Rust-Wände passen, und die gesamte Struktur wird zu einem Sicherheitsrisiko, weil niemand den vollständigen Bauplan sehen kann, wie alles miteinander verbunden ist.

Der universelle Übersetzer für Software-Räume

Dieses Papier mit dem Titel „Package Managers à la Carte“, verfasst von Forschern der University of Cambridge und Industriepartnern, schlägt eine Lösung für dieses Chaos vor. Sie versuchen nicht, jeden Paketmanager sofort dazu zu bringen, exakt dieselbe Sprache zu sprechen. Stattdessen haben sie eine universelle Grammatik erfunden, die Package Calculus (Paket-Kalkül) genannt wird.

Betrachten Sie die Package Calculus als eine „Lingua Franca“ oder einen universellen Übersetzer für Software-Abhängigkeiten. Die Autoren erkannten, dass trotz der wilden Unterschiede zwischen den Paketmanagern alle einen winzigen, gemeinsamen Kern teilen. Im Kern tun sie alle drei einfache Dinge:

Root Inclusion (Stamm-Einschluss): Man muss das Hauptprojekt einschließen, das man gerade baut.
Dependency Closure (Abhängigkeits-Abschluss): Wenn man ein Zimmer installiert, muss man auch alle kleineren Räume installieren, die es benötigt, um stabil zu stehen.
Version Uniqueness (Versions-Einzigartigkeit): Man kann normalerweise nicht zwei verschiedene Versionen desselben Zimmertyps am selben Ort zur gleichen Zeit installiert haben.

Das Papier beweist, dass dieser kleine Kern leistungsstark genug ist, um das Verhalten von über dreißig verschiedenen Paketmanagern zu beschreiben, von den alten Perl-Archiven bis hin zu modernen Rust-Tools. Die Forscher haben dies nicht nur vermutet; sie haben ein strenges mathematisches Modell erstellt und sogar ein Computerprogramm (unter Verwendung eines Tools namens Lean 4) geschrieben, um zu beweisen, dass ihre Logik fundiert ist.

Das „À La Carte“-Menü der Funktionen

Die wahre Magie des Papiers liegt darin, wie es mit den Unterschieden umgeht. Die Autoren erkannten, dass die komplexen Funktionen, die Paketmanager einzigartig machen – wie das Zulassen von mehreren Versionen einer Bibliothek nebeneinander oder das Erlauben, dass ein Paket sagt: „Ich brauche entweder Bibliothek A oder Bibliothek B“ – lediglich spezielle „Erweiterungen“ zu diesem einfachen Kern sind.

Sie nennen diesen Ansatz „à la carte“, wie das Bestellen von einer Speisekarte. Man kann den Basiskern bestellen und dann spezifische Erweiterungen hinzufügen für Dinge wie:

Konflikte: „Ich kann dieses Paket absolut nicht zusammen mit jenem installieren.“
Nebenläufige Versionen: „Ich benötige zwei verschiedene Versionen dieser Bibliothek, die nebeneinander laufen.“
Peer-Abhängigkeiten: „Mein Nachbar muss eine bestimmte Version einer Bibliothek haben, auch wenn ich sie nicht direkt verwende.“
Features (Funktionen): „Wenn du die Option ‚Grafik‘ einschaltest, benötige ich diese zusätzlichen Werkzeuge.“

Das Papier zeigt, dass jede dieser komplexen Funktionen mathematisch auf den einfachen Kern „reduziert“ werden kann. Es ist, als würde man zeigen, dass ein komplexes Rezept für ein Soufflé in die Basisschritte Mischen, Erhitzen und Falten zerlegt werden kann. Indem sie die Regeln jedes Ökosystems in diesen gemeinsamen Kern übersetzen, demonstrieren die Forscher, dass wir das Abhängigkeitsrätsel für ein Projekt, das über mehrere Sprachen hinweg gleichzeitig existiert, endlich lösen können.

Warum das wichtig ist: Der Polyglot Resolver

Das ultimative Ziel, das in dem Papier beschrieben wird, ist ein Polyglot Resolver (ein mehrsprachiger Problemlöser). Wenn Sie heute ein Projekt bauen wollen, das Python, Rust und C verwendet, müssen Sie drei separate Paketmanager ausführen und hoffen, dass sie sich nicht gegenseitig stören. Die Autoren schlagen vor, dass wir in Zukunft einen einzigen „Super-Resolver“ haben könnten.

So würde es funktionieren:

Der Python-Teil Ihres Projekts übersetzt seine Anforderungen in die Package Calculus.
Der Rust-Teil macht dasselbe.
Der C-Teil macht dasselbe.
Der Super-Resolver kombiniert sie alle zu einem einzigen, riesigen, einheitlichen Puzzle und löst es, wobei er sicherstellt, dass die Python-Bibliothek, die Rust-Bibliothek und der C-Treiber sich alle auf die zu verwendenden Versionen einigen.

Das Papier argumenttiert, dass dies nicht nur eine nette Idee ist, sondern ein notwendiger Schritt für Sicherheit und Stabilität. Wenn Abhängigkeiten über verschiedene Ökosysteme hinweg verborgen oder unverversioniert sind, wird es unmöglich, Sicherheitslücken nachzuverfolgen. Durch die Vereinheitlichung der Semantik können wir den vollständigen „Abhängigkeitsgraphen“ sehen – die komplette Karte jedes Code-Stücks, auf das Ihre Software angewiesen ist.

Die Autoren weisen vorsichtig darauf hin, dass dies nicht bedeutet, dass jeder Paketmanager morgen verschwinden wird. Stattdessen bietet dieses formale Modell die theoretische Grundlage für den Bau von Werkzeugen, die zwischen Ökosystemen übersetzen können. Sie zeigen, dass wir – obwohl das Finden der perfekten Menge an Versionen mathematisch schwierig ist (speziell ist es „NP-vollständig“, was bedeutet, dass es exponentiell schwieriger wird, je größer das Projekt wächst) – diese Komplexität bewältigen können, indem wir die zugrunde liegenden Regeln verstehen.

Kurz gesagt: Das Papier weist nicht nur darauf hin, dass das aktuelle System defekt ist; es liefert die Blaupausen für eine neue Art von Baustelle, auf der Software aus verschiedenen Welten endlich zusammenarbeiten kann, ohne in sich zusammenzufallen. Es verwandelt ein chaotisches Durcheinander isolierter Werkzeuge in ein kohärentes, einheitliches System und ebnet den Weg für sicherere, zuverlässigere und wahrhaft sprachübergreifende Softwareprojekte.

Technisches Resümee: Package Manager à la Carte

Problemstellung

Paketmanager sind in Betriebssystemen und Programmiersprachen allgegenwärtig, bleiben jedoch fundamental nicht interoperabel. Obwohl sie dasselbe Kernproblem lösen – die Auswahl eines konsistenten Satzes von Paketversionen zur Erfüllung der Abhängigkeiten eines Projekts –, verwendet jedes Ökosystem ad hoc entwickelte, fragmentierte Semantiken. Diese Fragmentierung verhindert, dass mehrsprachige Projekte präzise über das Ökosystem hinausgehende Abhängigkeiten ausdrücken können, lässt externe Systemabhängigkeiten implizit und unversioniert zurück und verschleiert den vollständigen Abhängigkeitsgraphen, der für die Sicherheitsanalyse der Lieferkette erforderlich ist. Aktuelle Interoperabilitätsbemühungen konzentrieren sich auf die Weitergabe von Lösungsmechanismen zwischen Ökosystemen mit identischen Semantiken, versäumen es jedoch, die zugrunde liegende Diversität in der Art und Weise zu adressieren, wie Abhängigkeiten ausgedrückt werden.

Methodik

Die Autoren schlagen den Package Calculus vor, ein minimales formales System, das als Lingua Franca für den Ausdruck von Abhängigkeiten dienen soll. Die Methodik folgt einem „Kern-und-Erweiterung“-Ansatz:

Kern-Formalisierung: Die Autoren definieren einen minimalen Kernel, der die universellen Bedingungen der Abhängigkeitsauflösung erfasst: Root Inclusion (das angeforderte Paket ist installiert), Dependency Closure (alle Abhängigkeiten sind erfüllt) und Version Uniqueness (höchstens eine Version eines Paketnamens ist installiert). Sie beweisen, dass das Lösen dieses Kernproblems NP-vollständig ist, mittels einer Reduktion von 3-SAT.
Erweiterung und Reduktion: Das Paper identifiziert spezifische Divergenzachsen realer Paketmanager (z. B. Konflikte, konkurrierende Versionen, Peer-Abhängigkeiten, Features, Boole’sche Formeln, virtuelle Pakete). Für jede Achse definieren die Autoren einen erweiterten Kalkül und liefern entscheidend eine korrekte und vollständige Reduktion zurück zum Kernkalkül. Diese Reduktionen fungieren als Kompilierungsschritte, die komplexe, ökosystemspezifische Abhängigkeitsausdrücke in das Kernformalismus übersetzen.
Komposition: Die Autoren demonstrieren, wie diese Erweiterungen kombiniert werden können, um reale Paketmanager abzubilden, die mehrere Features kombinieren (z. B. die Kombination von konkurrierenden Versionen und Features in Cargo). Sie skizzieren die notwendigen Überlegungen für die Komposition von Reduktionen, wie etwa den Umgang mit Verletzungen von Invarianten zwischen Erweiterungen.
Mechanisierung: Alle im Paper präsentierten Theoreme wurden in Lean 4 mechanisiert.

Zentrale Beiträge

Eine vereinheitlichte Übersicht: Eine Untersuchung von über dreißig Paketmanagern, die einen gemeinsamen Kern sowie die spezifischen Achsen identifiziert, entlang derer sie divergieren, einschließlich Versionsbeschränkungen, Konflikten, konkurrierenden Versionen, Peer-Abhängigkeiten, Features, Paketformeln, Variablenformeln, virtuellen Paketen und optionalen Abhängigkeiten.
Der Package Calculus: Ein minimales formales System, das das Wesen der Abhängigkeitsauflösung erfasst. Die Autoren zeigen, dass das Kernproblem zwar NP-vollständig ist, diese Komplexität jedoch inhärent für die Abbildung realer Ausdruckskraft ist; eingeschränkte Ansätze (wie Go's Minimal Version Selection) vermeiden NP-Vollständigkeit, indem sie die Ausdruckskraft zugunsten der linearen Zeitkomplexität opfern.
Reduktionen für Divergenz: Ein formales Modell für jede Divergenzachse als Erweiterung des Kerns, begleitet von einer Reduktion zurück zum Kern. Diese Reduktionen bewahren die Erfüllbarkeit (gültige Auflösungen bleiben gültig), garantieren aber nicht zwangsläufig die Optimalität.
Komposition: Eine Demonstration, dass Erweiterungen kombiniert werden können, um komplexe, reale Paketmanager abzubilden. Das Paper bietet einen Rahmen für die Konstruktion von Kalkülen, die mehrere Erweiterungen kombinieren (z. B. Concurrent Feature Package Calculus).
Polyglot Resolution Pathway: Eine theoretische Grundlage für einen „polyglotten Resolver“. Durch die Reduktion von Abhängigkeiten aus mehreren Ökosystemen auf den Kernkalkül könnte ein einziger Resolver theoretisch ein Projekt, das mehrere Sprachen und Betriebssysteme umfasst, als eine einheitliche Instanz lösen.

Ergebnisse

Das Paper stellt fest, dass der Kern-Package-Calculus durch eine Serie formaler Reduktionen in der Lage ist, die Vielfalt realer Abhängigkeitsausdruckssprachen abzubilden.

Komplexität: Die Autoren bestätigen, dass die Abhängigkeitsauflösung im allgemeinen Fall NP-vollständig ist. Sie analysieren, wie verschiedene Ökosysteme dieses Spektrum navigieren: Go's MVS erreicht eine lineare Zeitkomplexität durch die Beschränkung von Constraints auf untere Schranken und die Entfernung der Versionsunika für Major-Versionen; Nix umgeht das Problem durch die Forderung nach exakten Versionen (singuläre Abhängigkeiten); während Systeme wie opam und Cargo die NP-Vollständigkeit akzeptieren, um die Ausdruckskraft zu erhalten.
Reduktions-Validität: Für jede Erweiterung (Conflicts, Concurrent Versions, Peer Dependencies, Features, Package Formulae, Variable Formulae, Virtual Packages) liefert das Paper eine Reduktion zum Kern. Die Beweise für Korrektheit (Soundness) und Vollständigkeit (Completeness) werden für jede Erweiterung erbracht und stellen sicher, dass eine Lösung im erweiterten Kalkül existiert, wenn und nur wenn eine Lösung im reduzierten Kernkalkül existiert.
Komposition: Das Paper modelliert erfolgreich die Komposition von Erweiterungen, insbesondere durch die Demonstration, wie Concurrent Versions und Features kombiniert werden können, was in modernen Ökosystemen wie Rust (Cargo) üblich ist.

Bedeutung und Ansprüche

Das Paper beansprucht, die theoretische Grundlage für prinzipiengetreue, ökosystemübergreifende Werkzeuge zu liefern, die bisher gefehlt hat. Durch die Vereinheitlichung der Semantik der Abhängigkeitsausdrücke ermöglicht der Package Calculus:

Ökosystemübergreifender Vergleich: Oberflächlich unterschiedliche Mechanismen können als dieselbe Konstruktion identifiziert oder dort unterschieden werden, wo sie divergieren.
Polyglotte Auflösung: Ein Projekt, das mehrere Ökosysteme umfasst, kann als eine einzige Einheit aufgelöst werden, indem die Abhängigkeiten jedes Ökosystems in den Kernkalkül kompiliert und die kombinierte Instanz gelöst wird.
Translation als Zwischenrepräsentation: Der Kernkalkül könnte als Zwischenrepräsentation dienen, um Abhängigkeiten von der Sprache eines Ökosystems in die eines anderen zu übersetzen, wodurch die Komplexität der ökosystemübergreifenden Translation von $O(n^2)$ direkten Translatoren auf $2n$ Frontend/Backend-Translatoren reduziert wird.

Die Autoren bleiben bescheiden hinsichtlich der unmittelbaren Realisierung dieser Ziele. Sie merken an, dass zwar die Reduktion einzelner Erweiterungen invertiert (gehoben/lifted) werden kann, um die ursprüngliche Instanz wiederherzustellen, die Invertierung komponierter Reduktionen (bei denen synthetische Strukturen ineinandergreifen) jedoch ein offenes Problem darstellt, das eine explizite Definition für jede Komposition erfordert. Folglich reduziert der Kalkül die ökosystemübergreifende Translation zwar auf ein wohldefiniertes Problem (die Invertierung komponierter Reduktionen), die tatsächliche Implementierung von Translatoren und polyglotten Resolvern bleibt jedoch als zukünftige Arbeit offen. Das Paper beansprucht nicht, das Problem der Build-System-Integration oder die spezifischen Herausforderungen von Sandboxed Builds zu lösen, sondern liefert die formalen Semantiken, die notwendig sind, um diese Grenzen bei der Abhängigkeitsauflösung zu adressieren.