[Agda] unification and HITs

Dan Licata drl at cs.cmu.edu
Tue Jul 15 21:00:54 CEST 2014


Hi all,

I noticed an odd thing related to unification and the trick we use to implement higher inductive types with private data types.  It's a bit worrisome but I haven't been able to prove anything wrong from it (maybe someone else can?).  I was hoping someone would be able to explain what's going on here.  This happens in both 2.3.2.1 and the development version.  

A self-contained file with the code is here:
https://github.com/dlicata335/hott-agda/blob/master/misc/UnificationWeirdness.agda

Here's what I notice that seems wrong: Given

bad : S¹.S¹ → S¹.S¹
bad = S¹.S¹-rec S¹.base {!!}

The goal has type S1.base == S1.base (path from base to base).  If you do agda2-show-constraints, then there is a unification constraint
?0 := id
This seems wrong to me, because there is no reason that this path should be id.  


However, I wasn't able to exploit this to prove something incorrect:

It's clearly related to the trick for HITs, because it doesn't happen if we do the same thing with a postulate version of S1-rec, instead of with the version that reduces:
notbad1 : S¹.S¹ → S¹.S¹
notbad1 = S¹.S¹-rec-postulate S¹.base {!!}

If we write the loop in place of that goal (which unification said had to be id), then Agda accepts it:
fillbad : S¹.S¹ → S¹.S¹
fillbad = S¹.S¹-rec S¹.base S¹.loop

If there is some variable of type base=base, then the unification constraint is not generated:
notbad2 : (S¹.base == S¹.base) → S¹.S¹ → S¹.S¹
notbad2 t = S¹.S¹-rec S¹.base {!!} -- no constraint

We cannot equate S1-rec's with loop and id by unification:
notbad3 : (S¹.S¹-rec S¹.base S¹.loop) == (S¹.S¹-rec S¹.base id)
notbad3 = {!id!} -- id doesn't work

If there is something else in scope (locally) then the constraint is not generated:
l = S¹.loop
notbad4 : S¹.S¹ → S¹.S¹
notbad4 = S¹.S¹-rec S¹.base {!!} -- no constraint is generated


Any ideas about where this constraint comes from?

Thanks!
-Dan






More information about the Agda mailing list