Discussion of Homotopy Type Theory and Univalent Foundations
 help / Atom feed
From: Jasper Hugunin <jasperh@cs.washington.edu>
To: "Licata, Dan" <dlicata@wesleyan.edu>
Cc: "HomotopyTypeTheory@googlegroups.com"
	<HomotopyTypeTheory@googlegroups.com>
Subject: Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory
Date: Mon, 16 Sep 2019 13:09:30 -0400
Message-ID: <CAGTS-a_qUJdhOcQUznrY3JetHjQpCasCYHb1PR2hBPL0+Mj1xg@mail.gmail.com> (raw)
In-Reply-To: <10B7D7E9-3155-4FA0-90E0-BB6BE2C37B1B@wesleyan.edu>

[-- Attachment #1: Type: text/plain, Size: 10342 bytes --]

Hi Dan,

Of course. I'm thinking primarily of composition for Glue given in the CCHM
paper you linked, reproduced below.
As you know, the single potential issue is that we need pres of a
degenerate filling problem and function to be reflexivity. I claim that
this holds by regularity of composition in T and A, partly as a consequence
of the fact that regularity of composition implies regularity of filling
(that fill of a degenerate system is refl), which certainly holds for fill
defined by connections (and I believe also holds for fill as defined in
ABCFHL).

(a)
Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 :
B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 :
B(i1)[ psi |-> b(i1) ].
We set a := unglue b and a0 := unglue b0.
Set delta := forall i. phi.
Then we take:
a1' := comp^i A [ psi |-> a ] a0
delta |- t1' := comp^i T [ psi |-> b ] b0
delta |- omega := pres^i f [ psi |-> b ] b0
phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |->
(b(i1), refl a1') ] a1'
a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that
in the regular setting the psi face is redundant)
b1 := glue [ phi(i1) |-> t1 ] a1

With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |->
b(i0) ], we define
pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i
T [ psi |-> b ] b0) ] (f(i0) b0).

(b)
Now consider the regular case, where phi, T, f, and A are independent of i.
We want that b1 = b0.
We have that a is independent of i, and delta = phi.

First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the
explanation of your first dash)
Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b
This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0)
] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0.
Thus pres of a degenerate filling problem and function is reflexivity.

Going back to composition of Glue,
a1' = a0
phi |- t1' = b0
phi |- omega = refl (f b0)
phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the
delta face of equiv)
a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega =
refl, so this filling problem is degenerate)
b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ]
(unglue b0) = b0 (by eta, see Figure 4 in CCHM)

Thus this algorithm for composition of Glue is regular.
Other algorithms, such as the one in ABCFHL, may not be, but I am prone to
believe that there exist regular algorithms in other settings including
Orton-Pitts and Cartesian cubes.

Best regards,
- Jasper Hugunin

On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <dlicata@wesleyan.edu> wrote:

> Hi Jasper,
>
> It would help me follow the discussion if you could say a little more
> about (a) which version of composition for Glue exactly you mean (because
> there is at least the one in the CCHM paper and the “aligned” one from
> Orton-Pitts, which are intensionally different, as well as other possible
> variations), and (b) include some of your reasoning for why you think
> things are regular, to make it easier for me and others to reconstruct.
>
> My current understanding is that
>
> - For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential
> issue is with the ‘pres’ path omega, which via the equiv operation ends up
> in alpha, so the system in a1 may not be degenerate even if the input is.
> Do you think this does work out to be degenerate?
>
> - For the current version of ABCFHL
> https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf which
> uses aligning “all the way at the outside”, an issue is with the adjust_com
> operation on page 20, which is later used for aligning (in that case beta
> is (forall i phi)).  The potential issue is that adjust_com uses a
> *filler*, not just a composition from 0 to 1, so even if t doesn’t depend
> on z, the filling does, and the outer com won’t cancel.  In CCHM, filling
> is defined using connections, so it’s a little different, but I think there
> still has to be a dependence on z for it to even type check — it should
> come up because of the connection term that is substituted into the type of
> the composition problem.  So I’d guess there is still a problem in the
> aligned algorithm for CCHM.
>
> However, it would be great if this is wrong and something does work!
>
> -Dan
>
> > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <jasperh@cs.washington.edu>
> wrote:
> >
> > This doesn't seem right; as far as I can tell, composition for Glue
> types in CCHM preserves regularity and reduces to composition in A on phi.
> >
> > - Jasper Hugunin
> >
> > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <
> anders.mortberg@math.su.se> wrote:
> > Hi Jasper,
> >
> > Indeed, the problem is to construct an algorithm for comp (or even
> > coe/transp) for Glue that reduces to the one of A when phi is true
> > while still preserving regularity. It was pointed out independently by
> > Sattler and Orton around 2016 that one can factor out this step in our
> > algorithm in a separate lemma that is now called "alignment". This is
> > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of
> > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly
> > where regularity for comp for Glue types break down. In this step we
> > do an additional comp/hcomp that inserts an additional forall i. phi
> > face making the comp/coe irregular.
> >
> > One could imagine there being a way to modify the algorithm to avoid
> > this, maybe by inlining the alignment step... But despite considerable
> > efforts no one has been able to figure this out and I think Swan's
> > recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is
> > not even possible!
> >
> > Another approach would be to have weak Glue types that don't strictly
> > reduce to A when phi is true, but this causes problems for the
> > composition in the universe and would be weird for cubical type
> > theory...
> >
> > In light of Swan's negative results I think we need a completely new
> > approach if we ever hope to solve this problem. Luckily for you Andrew
> > Swan is starting as a postdoc over in Baker Hall in October, so he can
> > explain his counterexamples to you in person.
> >
> > Best,
> > Anders
> >
> > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin
> > <jasperh@cs.washington.edu> wrote:
> > >
> > > Offline, Carlo Angiuli showed me that the difficulty was in part 1,
> because of a subtlety I had been forgetting.
> > >
> > > Since types are *Kan* cubical sets, we need that the Kan operations
> agree as well as the sets.
> > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A,
> compGlue) = (A, compA), and getting that the Kan operations to agree was/is
> difficult.
> > > (Now that I know what the answer is, it is clear that this was already
> explained in the initial discussion.)
> > >
> > > Humbly,
> > > - Jasper Hugunin
> > >
> > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <
> jasperh@cs.washington.edu> wrote:
> > >>
> > >> Hello all,
> > >>
> > >> I've been trying to understand better why composition for the
> universe does not satisfy regularity.
> > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |->
> equiv^i E ] A, I would expect regularity to follow from two parts:
> > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of
> regularity condition for the Glue type constructor itself)
> > >> 2. That equiv^i (refl A) reduces to equivRefl A
> > >> I'm curious as to which (or both) of these parts was the issue, or if
> regularity for the universe was supposed to follow from a different
> argument.
> > >>
> > >> Context:
> > >> I've been studying and using CCHM cubical type theory recently, and
> often finding myself wishing that J computed strictly.
> > >> If I understand correctly, early implementations of ctt did have
> strict J for Path types, and this was justified by a "regularity" condition
> on the composition operation, but as discussed in this thread on the HoTT
> mailing list, the definition of composition for the universe was found to
> not satisfy regularity.
> > >> I don't remember seeing the regularity condition defined anywhere,
> but my understanding is that it requires that composition in a degenerate
> line of types, with the system of constraints giving the sides of the box
> also degenerate in that direction, reduces to just the bottom of the box.
> This seems to be closed under the usual type formers, plus Glue, but not
> the universe with computation defined as in the CCHM paper (for trivial
> reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi
> |-> equiv^i refl ] A not reducing to anything).
> > >>
> > >> Best regards,
> > >> - Jasper Hugunin
> > >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups "Homotopy Type Theory" group.
> > > To unsubscribe from this group and stop receiving emails from it, send
> an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
> > > To view this discussion on the web visit
> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com
> .
> >
> > --
> > You received this message because you are subscribed to the Google
> Groups "Homotopy Type Theory" group.
> > To unsubscribe from this group and stop receiving emails from it, send
> an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
> > To view this discussion on the web visit
> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com
> .
>
>

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a_qUJdhOcQUznrY3JetHjQpCasCYHb1PR2hBPL0%2BMj1xg%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 13041 bytes --]

  reply index

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-09-13  6:10 Jasper Hugunin
2019-09-15  5:57 ` [HoTT] " Jasper Hugunin
     [not found]   ` <CAMWCppk4PWzfZ1HKNLMdAZ=RBC-ARxtJXR8okvwO3raea5gC8Q@mail.gmail.com>
     [not found]     ` <CAGTS-a-SvWWF+br6sKxGj6ufVY=4m830FH9BDg06QJR1vbNFsw@mail.gmail.com>
2019-09-16  2:18       ` Fwd: " Jasper Hugunin
2019-09-16 16:18         ` [HoTT] " Licata, Dan
2019-09-16 17:09           ` Jasper Hugunin [this message]
2019-09-16 19:01             ` Licata, Dan
2019-09-16 20:17               ` Jasper Hugunin
2019-09-18 12:16                 ` Anders Mortberg
2019-09-18 12:52                   ` Thierry Coquand
2019-09-15 11:55 ` [HoTT] " Andrew Swan
2019-09-15 22:38   ` Jasper Hugunin
2019-09-16  1:04   ` Jon Sterling
     [not found]     ` <A605E6EE-0101-4390-B50D-A6AEB36FDCC2@icloud.com>
2019-09-16  1:44       ` Jon Sterling

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAGTS-a_qUJdhOcQUznrY3JetHjQpCasCYHb1PR2hBPL0+Mj1xg@mail.gmail.com \
    --to=jasperh@cs.washington.edu \
    --cc=HomotopyTypeTheory@googlegroups.com \
    --cc=dlicata@wesleyan.edu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Discussion of Homotopy Type Theory and Univalent Foundations

Archives are clonable: git clone --mirror http://inbox.vuxu.org/hott

Newsgroup available over NNTP:
	nntp://inbox.vuxu.org/vuxu.archive.hott


AGPL code for this site: git clone https://public-inbox.org/ public-inbox