19 May. 2025

§The Package Calculus

I’ve been updating the package management paper, which I include a snippet of below. I’m extending this core Package Calculus to support modelling real-world package managers, and showing a reduction to the core. I’m going to use this as the basis for bi-directional translations between package management ecosystems.

§Formalising Dependency Resolution

We present the Package Calculus, a formal system for analysing dependency resolution in package management systems. Based on the Package Calculus, we define a language Pac for expressing dependencies to be resolved. This calculus captures the essential complexity of version selection while remaining expressive enough to model real-world package managers.

§The Package Calculus

1. Package

   We define:

   • N is a set of possible package names,
   • V is the set of possible package versions,
   • P = N × V is the set of possible packages,
   • R ⊆ P is the set of packages which exist.

2. Dependency

   Dependencies D ⊆ P × (N × 2^V) are a relation from packages to a name and set of versions. We denote an element of D ∋ ((n, v), (m, vs)) with (n, v) → (m, vs) where a package (n, v) expresses a dependency on a package name m ∈ N and set of compatible versions vs ⊆ V which can satisfy the dependency. The set of versions vs is often expressed with /dependency formula/ which we abstract to a set. Every package referenced by D must be in R, (n, v) → (m, vs) ⟹ (n, v) ∈ R ∧ {(m, u) ∣ u ∈ vs} ⊆ R.

3. Resolution

   Given a set of dependencies D and a query set Q ⊆ P a resolution S ⊆ P is valid if the following conditions hold:

   1. Query Inclusion: Q ⊆ S

   2. Dependency Closure: ∀p ∈ S, p → (n, vs) ⟹ ∃(n, v) ∈ S : v ∈ vs

      If p is in S and p depends on (n, vs) then there exists a (n, v) in S where v is in the set vs.

   3. Version Uniqueness: ∀(n, v), (n, v′) ∈ S, v = v′

      Packages of the same name in S must have the same version,

   We write 𝒮(D, Q) for the set of all resolutions of Q in D.

§The Language Pac

Let n ∈ N and v ∈ V, then we define the expression language Pac by the following grammar:

p ::= n v vs :== v+ t ::= n ( v+ ) d ::= p ( t^* ) e ::= d^*

We extract D and R from an expression e with

d = p ( t^* ) e,m vs t^*, p (m, vs) p R

1. Example Mapping from a Pac expression to dependencies:

   A 1 ( B (1) C (1) ) B 1 ( D (1 2) ) C 1 ( D (2 3) ) D 1 () D 2 () D 3 ()	⟹	(A,1) → (B,{1}) (A,1) → (C,{1}) (B,1) → (D,{1,2}) (C,1) → (D,{2,3})
   Grammar expression e		Dependencies relation D

   We illustrate this example in figure 1 as a directed hypergraph, a graph where edges are hyperedges from a package (the domain) to a set of packages (the codomain). The hypergraph has vertices R and hyperedges E = {({(n, v)}, {(m, u) ∣ u ∈ vs}) ∣ (n, v) → (m, vs)}. Note that we restrict the domain to a size of one – we can only express a dependency from one package. The only resolution for the query Q = {(A, 1)} is S = {(A, 1), (B, 1), (C, 1), (D, 2)}.

   

§Matrix VoIP

I’ve tried and failed to add the new Matrix Element Call stack to Eilean. I think it’s probably a misconfigured LiveKit turn server.

§Bigraphs of the Real World

I was proof reading the last versions of Roy’s thesis, which was just submitted! I’ve excited to try incorporating some of his work into Eon as a step towards the Spatial Name System.