Phantom arguments in functions [Re: [Agda] another possible
without-K problem]
Dan Licata
drl at cs.cmu.edu
Wed Jul 10 21:09:28 CEST 2013
Hi Andreas, Guillaume,
Andreas, thanks for the suggestion!
Guillaume, unless I'm mistaken, or things have changed since 2.3.2.1, I think there
is a simpler way to avoid the annoyance of the phantom argument:
- To make an unused argument used, you need to match on a "phantom"
argument indexed by that argument. (I.e. it's important that
the unit in Andreas's code is a data, not a record)
- But it's OK if the function is always called on the canonical
inhabitant of the type you're matching on---you don't need to quantify
over variable phantoms like Andreas is doing in his example.
This is important for getting the right definitional behavior, as
otherwise the match on the phantom would block reduction.
So the trick can be hidden in the implementation of the HIT, without
changing the external interface.
For example, the following implementation of a higher inductive type
works for me in 2.3.2.1. (Guillaume, does it still work in the
development version?)
Andreas, perhaps you could confirm that this is reasonable, given the
meaning of the unused argument check?
Also: does anyone know if there is a nice way to install and switch between multiple versions of Agda?
How would I have 2.3.2.1 from cabal and the devel version installed
simultaneously?
-Dan
----------------------------------------------------------------------
{-# OPTIONS --type-in-type --without-K #-}
open import lib.Prelude -- ≃ and id are the identity type and refl; Type is Set
module misc.Phantom where
data Unit⁺ : Type where
<>⁺ : Unit⁺
record Phantom {A : Type}(a : A) : Type where
constructor phantom
field
match : Unit⁺
module S where
private
data S¹' : Type where
Base : S¹'
S¹ : Type
S¹ = S¹'
base : S¹
base = Base
postulate {- HoTT Axiom -}
loop : Path base base
S¹-rec' : {C : Type}
-> (c : C)
-> (p : c ≃ C) (_ : Phantom p)
-> S¹ -> C
S¹-rec' c p (Phantom.phantom <>⁺) Base = c
S¹-rec : {C : Type}
-> (c : C)
-> (p : c ≃ c)
-> S¹ -> C
S¹-rec c p = S¹-rec' c p (Phantom.phantom <>⁺)
{- correctly fails:
p != q of type Id c c
when checking that the expression id has type
Id (S.rec c p) (S.rec c q)
test : {C : Type}
-> (c : C)
-> (p q : c ≃ c)
→ S.S¹-rec c p ≃ S.S¹-rec c q
test c p q = id
-}
-- still get definitional computation on points
test' : {C : Type}
-> (c : C)
-> (p : c ≃ c)
→ S.S¹-rec c p S.base ≃ c
test' c p = id
On Jul10, Guillaume Brunerie wrote:
> Thanks for the workaround!
> It’s not optimal though, you have to give the silly [z] argument
> everytime you use [fool] which is a bit annoying.
> But this is easy to fix by making the argument [z] of [fool] an
> instance argument instead of an implicit argument and by putting
> somewhere in the context the following definition:
>
> inhab-Phantom : {A : Set} {a : A} -> Phantom a Unit
> inhab-Phantom = phantom unit
>
> Then you can use [fool] just as you use [bla]:
>
> same? : {x : Unit} → fool u1 x ≡ fool u2 x
> same? = refl
>
> gives the expected error.
>
> Guillaume
>
> 2013/7/10 Andreas Abel <andreas.abel at ifi.lmu.de>:
> > On 10.07.2013 16:54, Dan Licata wrote:
> >>
> >> Also, related to implementing higher inductives, but not to without-K:
> >> is there a way to turn off/defeat the unused arguments analysis that is
> >> new in 2.3.2.1? It breaks some of the things I'm doing: I want a
> >> function with a "phantom" parameter, where different values of the
> >> phantom parameter do not automatically get equated.
> >
> >
> > Data and record types still have phantom arguments, which can be exploited.
> >
> > Would this workaround help you?
> >
> > import Common.Level
> > open import Common.Equality
> >
> > record Phantom {A : Set}(a : A)(B : Set) : Set where
> > constructor phantom
> > field
> > thePhantom : B
> > open Phantom
> >
> > postulate
> > A : Set
> > a : A
> > Unused : Set
> > u1 u2 : Unused
> >
> > data Unit : Set where
> > unit : Unit
> >
> > bla : (u : Unused) → Unit → A
> > bla u unit = a
> >
> > same : {x : Unit} → bla u1 x ≡ bla u2 x
> > same = refl
> >
> > fool : (u : Unused){z : Phantom u Unit} → Unit → A
> > fool u {phantom unit} unit = a
> >
> > same? : ∀ {x : Unit}{y z} → fool u1 {y} x ≡ fool u2 {z} x
> > same? = refl
> >
> > -- ERROR:
> > -- u1 != u2 of type Unused
> > -- when checking that the expression refl has type
> > -- fool u1 .x ≡ fool u2 .x
> >
> >
> >
> >
> >
> > Theoretical Computer Science, University of Munich
> > Oettingenstr. 67, D-80538 Munich, GERMANY
> >
> > andreas.abel at ifi.lmu.de
> > http://www2.tcs.ifi.lmu.de/~abel/
> > _______________________________________________
> > Agda mailing list
> > Agda at lists.chalmers.se
> > https://lists.chalmers.se/mailman/listinfo/agda
More information about the Agda
mailing list