{"id":"422fb970-eff5-4c7d-93e5-81614f574510","arxiv_id":"2602.18602","paper_version":5,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A core calculus for dependency resolution is proposed with reductions from package-manager extensions, aiming to enable cross-ecosystem dependency translation.","lead":"Gibb et al. introduce the Package Calculus, a formal model of dependency resolution intended to unify package-manager semantics across ecosystems. The paper defines a minimal core calculus and claims, via reductions stated without proofs, that common package-manager features can all be expressed in it.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Composition of reductions is unproven: the 2n-translator claim fails for ecosystems combining conflicts with concurrent versions (e.g., Portage).","rationale":"The reader identified missing proofs for the §4.1–§4.7 soundness/completeness theorems as the weakest assumption. I agree that is a serious gap, but the more specific and arguably more damaging issue is that the general translation pipeline requires compositions of extensions that are not established. The paper's own §5.2.2 documents an invariant violation between the conflict encoding and concurrent versions—not merely a missing proof but a stated obstruction. The 2n-translator claim is the headline practical contribution, and it depends on lowering any combination of extensions into the core. Since only one pair is proved to compose (features + concurrent versions), the claim is an overstatement as written. My proposed check would empirically and then formally test the composition for a concrete problematic combination; if it fails, the paper requires a new composition technique, not just proofs of the existing individual theorems. Thus I partially agree with the reader: missing proofs are part of the problem, but the composition gap is the load-bearing element.","tokens_in":30642,"tokens_out":17201,"duration_ms":150294,"concrete_test":"Enumerate all small instances of a combined Concurrent+Conflict calculus (e.g., ≤3 package names, ≤2 versions, one granularity function and one conflict relation). Implement the suggested 'concurrent-first then conflict' lowering as an explicit algorithm and compare the original resolutions (satisfying both Def. 4.2.2 and Def. 4.1.2) with the core resolutions projected back via the lifting constructions. Any spurious or missing resolution falsifies the composition. If no counterexample appears, formalize and prove the combined reduction; this would settle whether Portage-style managers fall within the 2n-translator pipeline.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5 claims the Package Calculus reduces cross-ecosystem translation from n^2 to 2n translators by using the §4 reductions as lowering/lifting passes. This presupposes that any real ecosystem's combination of extensions can be lowered by composing those reductions. The paper proves only one composition (features + concurrent versions, Theorem 5.2.2–5.2.3) and admits in §5.2.2 that conflict reduction (Def. 4.1.3) and package-formula negation (Def. 4.5.4) rely on synthetic packages with two versions and core version uniqueness, which the concurrent-versions relaxation to granularity breaks. It suggests reducing concurrent versions first, but provides no combined reduction or correctness theorem. Portage combines slots (concurrent versions) with blockers (conflicts), so the pipeline cannot currently handle such a manager. Without a general composition theorem, the 2n claim is unsupported even if each individual reduction is sound and complete.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the Package Calculus, a minimal three-rule formal system for dependency resolution (root inclusion, dependency closure, version uniqueness). It surveys over thirty package managers, identifies seven axes of semantic diversity (conflicts, concurrent versions, peer dependencies, features, package formulae, variable formulae, virtual packages), and defines an extension of the core calculus for each. The central claim is that every extension can be reduced to the core via sound and complete reductions, so that the core can serve as an intermediate representation reducing cross-ecosystem translation from n² to 2n translators. The paper proves NP-completeness of the core (Appendix B) and gives a SAT encoding (Appendix C), but the soundness/completeness theorems for the reductions are stated without proof. The composition of reductions is only proved informally for features plus concurrent versions, and §5.2.2 explicitly notes a conflict between the conflict/negation encodings and the concurrent-versions relaxation.","tokens_in":30964,"tokens_out":5548,"duration_ms":52327,"significance":"If the reductions and composition claims were fully proved, the Package Calculus would be a valuable unifying framework for package-manager semantics, with practical potential for cross-ecosystem dependency resolution and supply-chain analysis. The survey and taxonomy (§2, Table 1) are useful as a systematization of package-manager features, and the core calculus is clearly and precisely defined. The NP-completeness proof and the SAT encoding are solid contributions. However, the paper's central formal claims—the sound and complete reductions of all seven extensions and the 2n-translator pipeline—are currently unproved, and the paper itself identifies a load-bearing composition limitation. The framework is promising, but in its present form the formal results do not support the advertised conclusions.","major_comments":[{"comment":"All soundness and completeness theorems for the reductions are stated without proof. For example, Theorem 4.1.4 and Theorem 4.1.5 are essential to the claim that conflicts are faithfully modelled, yet no derivation is provided. The same applies to every other reduction in §4. The paper's central contribution is a set of formal equivalences; without proofs, these remain conjectures. The authors should supply full proofs for each theorem, or at least rigorous proof sketches that demonstrate the key invariants (e.g., why synthetic conflict packages cannot be bypassed, why intermediate packages preserve parent-relation uniqueness, and why feature unification is maintained).","section":"§4 (Theorems 4.1.4–4.1.5, 4.2.4–4.2.5, 4.3.4–4.3.5, 4.4.5–4.4.6, 4.5.5–4.5.6, 4.6.4–4.6.5, 4.7.4–4.7.5; also Theorem 3.2"},{"comment":"The paper claims that using the core as an IR reduces translation from n² to 2n translators, but this presupposes that combinations of extensions can be lowered by composing the reductions. The paper itself admits in §5.2.2 that the conflict reduction (Definition 4.1.3) and the package-formula negation encoding (Definition 4.5.4) rely on version uniqueness, which the concurrent-versions extension (Definition 4.2.2) relaxes. The suggested remedy—'reducing concurrent versions first'—is not accompanied by a combined reduction or a correctness theorem. Consequently, the 2n claim is unsupported for ecosystems that combine concurrent versions with conflicts, such as Portage (slots and blockers) or any future manager mixing these features. A general composition theorem, or an explicit and proved characterization of which extension combinations are composable, is needed before the pipeline claim","section":"§5.2.2 (Limits of Composition) and §5 (2n translator claim)"},{"comment":"Even the one positive composition result—features with concurrent versions—is only supported by an informal argument ('the feature reduction is version-preserving') and the two theorems are stated without proof. This is the only fully worked composition in the paper, and it is central to the claim that the framework can handle real-world managers like Cargo. Please provide actual proofs for Theorems 5.2.2 and 5.2.3, or downgrade the presentation to a conjecture and clearly mark it as unproved.","section":"§5.2.1 (Theorems 5.2.2 and 5.2.3)"}],"minor_comments":[{"comment":"The conflict-avoidance condition contains a corrupted symbol ('šv∈vs') that should be the non-existence quantifier (e.g., ∄). Please fix the typo for readability.","section":"Definition 4.1.2(b)"},{"comment":"The sentence 'Where the target ecosystem does not support an extension, the core encoding is emitted directly' is unclear. If the target DSL cannot express the extension natively, how can the core encoding with structured names like ⟨n,g(v)⟩ be emitted into that DSL? This needs a concrete explanation or an example.","section":"§5.1 (Transpiling Pipeline)"},{"comment":"The footnote numbering is confusing: footnote 3 ('Limited support with ‘Slotting’') appears to annotate the 'Concurrent Versions' column for Portage, but the footnote marker is attached to the Toolchain column. Please align the markers with the intended cells.","section":"Table 1"},{"comment":"The De Morgan rule E(p ΔΨ ¬(ψL∧ψR)) = E(p ΔΨ ¬ψL∨¬ψR) introduces a disjunction that is not a syntactic subformula of the original; this is fine because the encoding is recursive, but the rule should be stated more carefully to avoid the impression that ΔΨ is closed under such rewriting.","section":"Definition 4.5.4(b)(iv)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a good high-level idea and a useful taxonomy, but the formal core is currently unproved. I would be willing to reconsider after the authors supply proofs for the reduction theorems and either prove a composition theorem or substantially qualify the 2n-translator claim. The self-admitted composition failure in §5.2.2 is not, by itself, disqualifying if the paper is reframed as a framework rather than a complete pipeline, but as written the contribution section overstates what is established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The Package Calculus is a credible attempt at a lingua franca for dependency resolution, and the paper earns attention for its systematic survey and its clean separation between a minimal core and a catalogue of extensions. The three-rule core (root inclusion, dependency closure, version uniqueness) is elegantly simple, and the reductions are concrete enough to be checked by hand — the conflicts-as-synthetic-packages encoding and the granularity-renaming for concurrent versions are particularly nice. The paper also deserves credit for citing prior work fairly, including noting that pubgrub-rs contains encodings very similar to its own reductions, and for being upfront in §5.2.2 about the limits of composing reductions.\n\nThe main problem is exactly what the reader flagged: every extension section states soundness and completeness theorems but supplies no proofs, not even sketches. Only the NP-completeness of the core is proved (Appendix B). That is a load-bearing gap because the 2n-translator promise in §5 assumes all the reductions are correct. If any reduction is subtly wrong, the entire cross-ecosystem pipeline falls down. The theorems look plausible and the definitions are precise, but this is claim-without-derivation for the central technical results.\n\nThe stress-test concern about composition also holds up on reading. The paper proves one clean composition (features + concurrent versions), but for conflicts combined with concurrent versions it explicitly admits that the conflict reduction breaks because version uniqueness is relaxed. The suggested fix — reduce concurrent versions first — is not proved, and the Portage example (slots plus blockers) is exactly a case the pipeline cannot currently handle. So the 2n claim is overstated: it is conditional on an unproven composition theorem, or on a more modest statement about ecosystems whose extension combinations happen to compose.\n\nThat said, this is not a fatal flaw in the paper's core idea. The framework is genuinely useful, the reductions are a solid foundation, and the composition limits are acknowledged rather than hidden. The paper just needs full proofs, a clearer statement of when the translation pipeline is guaranteed sound, and possibly a more conservative claim about the 2n reduction. I would send it to peer review, but with a request for substantial revision: full derivations for Theorems 4.1.4–4.7.5, and a proper treatment of the composition cases that currently fail.\n\nWho is this for? Anyone working on cross-ecosystem tooling, SBOM generation, or formal models of package semantics. It is worth a serious referee, and if the proofs get written, it could become a reference point for the area.","headline":"A promising unifying formalization of dependency resolution that needs full proofs for its reduction theorems and a more honest composition story before the 2n-translator claim is credible.","tokens_in":31433,"tokens_out":2378,"would_cite":false,"duration_ms":26417,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A three-rule calculus — root inclusion, dependency closure, version uniqueness — is claimed to capture the common core of all package managers, with each ecosystem-specific feature reduced to that core by sound and complete encodings.","keywords":["Package Calculus","dependency resolution","package managers","formal semantics","reductions","conflicts","concurrent versions","cross-ecosystem translation"],"falsifier":"Concrete test: take a small instance of any extension, for example a package A that conflicts with versions 1 and 2 of B while also depending on C, and compare the set of valid resolutions under the extension with the set produced by the reduction to the core. If any reduction maps a satisfiable extended instance to an unsatisfiable core instance, or yields a core resolution that decodes to an invalid extended resolution, the central claim fails. A systematic version: enumerate all small repositories, encode both the extension and its reduction as SAT instances, and check satisfiability equiva","tokens_in":30547,"feed_emoji":"📦","tokens_out":5853,"duration_ms":51305,"temperature":0.7,"pith_summary":"The paper tries to establish that every package manager, however idiosyncratic, runs on a common three-rule core: the resolved set must include the root, must be closed under dependencies, and can contain only one version of any package name. It defines this core as the Package Calculus and then shows, extension by extension, that conflicts, concurrent versions, peer dependencies, features, package formulae, variable formulae, and virtual packages can all be encoded back into the core by adding synthetic packages with structured names. Each encoding is claimed to preserve valid resolutions exactly, so the reductions double as compilation passes: a dependency expression in any ecosystem can be lowered to the core, solved there, and lifted into another ecosystem. The payoff is that translating among n package managers needs 2n translators through the core rather than n² direct translators, which would let a multilingual project resolve OCaml, Rust, Python, and system dependencies in one pass and see the full dependency graph.","feed_headline":"Three rules capture what every package manager does","feed_subtitle":"A three-rule core could translate dependency languages across programming-language and OS ecosystems in one pass.","key_machinery":"The carrying object is the Package Calculus itself: a dependency relation from packages (name, version) to name-and-version-set, with validity defined by root inclusion, dependency closure, and version uniqueness. The mechanism that makes the extensions work is the synthetic package: each extension is encoded by injecting new packages with structured names, often two versions 0 and 1, and rewiring dependencies so that the core's version-uniqueness condition enforces the extension's constraint. Supporting sub-mechanisms include a granularity function that maps versions to coarse labels for concurrent versions, linear auxiliary packages that encode formula disjunction without exponential blowu","core_discovery":"On the paper's own terms, the discovery is a unification result: dependency resolution in more than thirty surveyed package managers is not thirty different problems but one problem with optional vocabulary. The Package Calculus fixes a minimal semantics — root inclusion, dependency closure, version uniqueness — and the paper's reductions show this semantics is expressive enough to absorb the axes along which package managers diverge. Conflicts become synthetic packages with versions 0 and 1; concurrent versions push a granularity label into the package name; features become feature-labelled packages; disjunction and negation become auxiliary one-of-two packages; variables become packages ra","pith_inferences":["Editorial inference: the practical value of the 2n pipeline depends on the unproven soundness and completeness theorems; formalizing them in a proof assistant or finding a counterexample would be the natural next step.","Editorial inference: the encodings suggest a testable extension — generate random small dependency instances in two ecosystems, lower both to the core, and check that satisfiability and selected versions agree; disagreements would pinpoint where ecosystem semantics diverge.","Editorial inference: the calculus models resolution only, not deployment order or build semantics; a full cross-ecosystem tool would need to couple these with the build-graph treatment of optional dependencies.","Editorial inference: the NP-completeness of the core implies that cross-ecosystem resolution inherits exponential worst-case behavior; practical tools would need SAT-style engines, so this formalism is a semantic backbone rather than a performance recipe."],"forward_implications":["Cross-ecosystem translation reduces to writing one lowerer and one lifter per ecosystem; a resolver built on the core can serve all of them.","A dependency graph spanning OCaml, Rust, Python, and system packages could be resolved as a single instance, making security-vulnerability analysis and SBOM generation see the full transitive closure.","New dependency constructs can be incorporated into the translation network as soon as they admit a sound and complete reduction to the core, without rewriting other ecosystems' translators.","The complexity spectrum is formalized: minimum-version-only constraints give linear-time resolution, removing version uniqueness gives greedy resolution, and full expressiveness is NP-complete.","Where reductions compose, they do so because encodings are version-preserving; where they do not compose, the paper specifies the ordering constraints or mutual awareness required."],"fun_headline_variants":["Every package manager boils down to three rules","Why dependency resolution is one problem, not many","A three-rule core in one calculus unifies package managers","The Package Calculus: one semantics for many managers","A single formal model for all dependency resolution"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that every reduction in Sections 4.1 through 4.7 is sound and complete — that is, it neither creates nor destroys valid resolutions — but the paper states these theorems without supplying proofs; the only formal claim with a proof is the NP-completeness argument in Appendix B.","fun_headline_variants_meta":{"raw":{"variants":["Every package manager boils down to three rules","Why dependency resolution is one problem, not many","A three-rule core in one calculus unifies package managers","The Package Calculus: one semantics for many managers","A single formal model for all dependency resolution"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00091,"raw_usage":{"total_tokens":3679,"prompt_tokens":609,"completion_tokens":3070,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":353,"completion_tokens_details":{"reasoning_tokens":2998}},"tokens_in":353,"tokens_out":3070,"duration_ms":68112,"temperature":1.0,"reasoning_tokens":2998,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T21:54:00.900383+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Concrete test: take a small instance of any extension, for example a package A that conflicts with versions 1 and 2 of B while also depending on C, and compare the set of valid resolutions under the extension with the set produced by the reduction to the core. If any reduction maps a satisfiable extended instance to an unsatisfiable core instance, or yields a core resolution that decodes to an invalid extended resolution, the central claim fails. A systematic version: enumerate all small repositories, encode both the extension and its reduction as SAT instances, and check satisfiability equiva","supporting_citations":[],"review_version":1}