I want to define a size-preserving function on derivations of a transition relation for pi calculus. I'm not able to convince Agda that it is indeed size-preserving. I'm also getting an error message which appears non-sensical, so perhaps there's a clue in there.
I've boiled the code down as much as possible whilst still retaining the flavour of the setting. Here's the preamble.
{-# OPTIONS --sized-types #-}
module SizedTypes where
open import Data.Product public hiding (swap)
open import Relation.Binary.PropositionalEquality
open import Size
-- Processes.
data Proc : Set where
ν_ : Proc → Proc
-- Actions.
data ⟿ᵇ : Set where
input : ⟿ᵇ
boundOut : ⟿ᵇ
data ⟿ᶜ : Set where
out : ⟿ᶜ
data ⟿ : Set where
_ᵇ : ⟿ᵇ → ⟿
_ᶜ : ⟿ᶜ → ⟿
-- Renamings.
data Ren : Set where
postulate
push : Ren
swap : Ren
_ᴬ*_ : Ren → ⟿ᶜ → ⟿ᶜ
-- Transitions.
data _—[_]→_ : {ι : Size} → Proc → (a : ⟿) → Proc → Set where
ν•_ : ∀ {ι P R} → _—[_]→_ {ι = ι} P (out ᶜ) R →
_—[_]→_ {ι = ↑ ι} (ν P) (boundOut ᵇ) R
νᵇ_ : ∀ {ι P R} {a : ⟿ᵇ} → _—[_]→_ {ι = ι} P (boundOut ᵇ) R →
_—[_]→_ {ι = ↑ ι} (ν P) (a ᵇ) (ν R)
νᶜ_ : ∀ {ι P R} → _—[_]→_ {ι = ι} P ((push ᴬ* out) ᶜ) R →
_—[_]→_ {ι = ↑ ι} (ν P) (out ᶜ) (ν R)
infixl 0 _—[_]→_
postulate
_ᴾ*_ : Ren → Proc → Proc
_ᵀ*_ : ∀ {ι} (ρ : Ren) {P R} {a : ⟿ᶜ} → _—[_]→_ {ι = ι} P (a ᶜ) R →
_—[_]→_ {ι = ι} (ρ ᴾ* P) ((ρ ᴬ* a) ᶜ) (ρ ᴾ* R)
swap-involutive : ∀ (P : Proc) → swap ᴾ* swap ᴾ* P ≡ P
swap∘push : swap ᴬ* push ᴬ* out ≡ out
infixr 8 _ᵀ*_ _ᴾ*_ _ᴬ*_
-- Structural congruence.
infix 4 _≅_
data _≅_ : Proc → Proc → Set where
νν-swap : ∀ P → ν (ν (swap ᴾ* P)) ≅ ν (ν P)
Now here's what I can't make work.
-- "Residual" of a transition E after a structural congruence φ.
⊖ : ∀ {ι P P′} {a : ⟿} {R} (E : _—[_]→_ {ι = ι} P a R) (φ : P ≅ P′) →
Σ[ R ∈ Proc ] _—[_]→_ {ι = ι} P′ a R
⊖ (ν•_ (νᶜ E)) (νν-swap P) with swap ᵀ* E
... | swap*E rewrite swap-involutive P | swap∘push =
_ , {!!} -- νᵇ (ν• swap*E)
⊖ E φ = {!!}
Roughly, I'm matching on the situation where there are adjacent ν binders, and showing that if I transpose the binders (by applying the 'swap' renaming under the binders) then the associated steps in the derivation also tranpose. Intuitively this preserves the size of the transition derivation.
Toggling hidden arguments (in Emacs) reveals that the goal in the problematic clause has type _—[_]→_ {↑ (↑ .ι)}, so I expect to be able to apply two constructors (in this case νᵇ and ν•). I can also see that E has type _—[_]→_ {.ι}, as does swap*E, and so I (naively) expect νᵇ (ν• swap*E) to be size-consistent with the goal. However Agda complains that the constraints are inconsistent.
Weirdly, if I use a with clause to introduce ν• swap*E into the context, then I get the following error:
.ι !=< P of type Size
when checking that the expression E has type
swap ᴾ* P —[ (push ᴬ* out) ᶜ ]→ .R
This is baffling because the choice of meta-variable P suggests that Agda is trying to match a size index against a variable of type Proc.
What am I doing wrong here?
