[Agda] Sized types problem

Roly Perera roly.perera at dynamicaspects.org
Mon Aug 18 09:39:37 CEST 2014


Hi,

I'm modelling pi calculus in Agda and having difficulty using sized types
in order to have the function ⊖ below pass the termination-checker. I'm
also getting an error message which looks a bit odd, so perhaps there's a
clue to what I'm doing wrong in there.

{-# OPTIONS --sized-types #-}

module Temp 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. Leave undefined for now.
   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)

   -- "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 φ = {!!}

(I can try to boil the code down further if that would help, but I wanted
to maintain some of the structure of my setting.)

In the first goal above, 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. And indeed, toggling hidden arguments reveals that
the goal has type _—[_]→_ {↑ (↑ .ι)}, so I expect to be able to apply two
constructors (νᵇ and ν• in this case) in return for two I eliminated (ν•
and νᶜ).

I can also see that E has type _—[_]→_ {.ι}. Since I've postulated that ᵀ*
is size-preserving, the variable swap*E also has this type. Naively, I
expect νᵇ (ν• swap*E) to therefore 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,
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 appearance of meta-variable P in the error
message suggests that Agda is trying to match a size index against a
variable of type Proc, does it not?

Can anyone shed any light on what's going on here?

many thanks,
Roly


Roly Perera
LFCS, School of Informatics
University of Edinburgh
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20140818/7b8c2928/attachment.html


More information about the Agda mailing list