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.

1. 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.

2. 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 Pak 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.