Que partes da teoria do tipo de homotopia não são possíveis na Agda ou na Coq?

16

Quando olhamos para o livro, Homotopy Type Theory - vemos os seguintes tópicos:

Homotopy type theory 
2.1 Types are higher groupoids
2.2 Functions are functors
2.3 Type families are fibrations
2.4 Homotopies and equivalences
2.5 The higher groupoid structure of type formers
2.6 Cartesian product types
2.7 S-types
2.8 The unit type
2.9 P-types and the function extensionality axiom
2.10 Universes and the univalence axiom
2.11 Identity type
2.12 Coproducts
2.13 Natural numbers
2.14 Example: equality of structures
2.15 Universal properties

Agora sabemos que nem toda teoria de tipos de homotopia é possível é Agda e Coq .

Minha pergunta é: Quais partes da teoria dos tipos de homotopia não são possíveis na Agda ou na Coq?

type-systems Hawkeye
fonte
4
Não é uma pergunta particularmente bem formulada. Qual é a relação entre a lista de tópicos e a pergunta?
Dave Clarke
@ Dave Clarke, A lista de tópicos se parece com o contexto da mente do questionador, para que o respondente saiba qual é o ponto de partida do questionador e possa adequá-la adequadamente. Outros alunos também podem apreciar a resposta no mesmo contexto e entender que a resposta provavelmente será útil para eles se o respondente for atencioso e sagaz em relação à natureza humana. Espero que também ajude em outras conversas futuras.
codeshot

Respostas:

21

Se você olhar para Notas sobre o Capítulo 8 você vai ver o que tem já sido formalizado, e eu acho que é muito. Há a biblioteca Coq HoTT e a biblioteca Agda HoTT-Agda que formalizam grandes partes da teoria do tipo de homotopia.

Para fazer as coisas no Coq, precisávamos de uma versão especial do Coq que fosse corrigida apenas para os propósitos do HoTT. No entanto, a Coq está se movendo na direção de apoiar a teoria do tipo de homotopia, portanto, em breve, poderemos fazê-lo com a Coq padrão.

No Agda, é preciso ativar a --without-Kopção, caso contrário, o Agda pensa que todos os tipos são do tipo 0. Há algumas dúvidas remanescentes sobre se --without-Krealmente se livra da suposição de que tudo está definido como 0, ou talvez alguém possa reintroduzi-lo no Agda com usos complicados de correspondências de padrões.

Os seguintes aspectos das formalizações Coq e Agda não são satisfatórios:

  1. O axioma da univalência é afirmado como uma hipótese. Seria melhor se fosse incorporado ao sistema. Em particular, gostaríamos que Coq e Agda entendessem as regras de computação sobre o axioma da Univalência.

  2. Da mesma forma, temos que usar hacks para obter tipos indutivos mais elevados. Novamente, seria melhor ter apoio direto.

O problema com as deficiências acima é que ninguém sabe como corrigi-las, mesmo em teoria. Esta é uma área ativa de pesquisa.

Fora isso, acho justo dizer que o HoTT pode ser feito principalmente na Coq e na Agda, mas não da maneira ideal.

Andrej Bauer
fonte
11
Obrigado, há uma boa descrição de por que a univalência e os tipos indutivos mais elevados não se encaixam bem com teorias de tipos como Agda e Coq?
Martin Berger
11
@ MartinBerger, essa provavelmente poderia ser uma pergunta separada (com algumas definições para leitores mais informais, etc.).
Artem Kaznatcheev
4
O problema da univalência e das HITs não é que elas "não se encaixam bem com teorias de tipos como Agda e Coq", mas que "não sabemos como fazê-las adequadamente em nenhuma teoria de tipos".
Andrej Bauer
11
A univalência do @AndrejBauer e os tipos indutivos mais altos são formalizados no artigo do HoTT, que é uma teoria do tipo (semi-formal). Qual é o ingrediente que falta que impede uma formalização adequada na Agda / Coq? Relacionado, se você está disposto a desistir de Curry-Howard, há alguma dificuldade em formular univalência e tipos indutivos mais altos em um provador no estilo LCF, como Isabelle, usando, por exemplo, LF como uma meta-linguagem para formalizar regras de prova?
Martin Berger
4
Para que servem as regras de computação ua, a constante que testemunha o axioma da Univalência? Quais são as regras de computação para HITs? Temos algumas idéias, mas nada impermeável.
Andrej Bauer
12

Até onde eu entendi, no Agda é possível representar tudo isso (ou seja, todo o Capítulo 2 - há uma biblioteca no github que sim; AFAIK, o mesmo acontece com Coq). Somente nos capítulos posteriores é que as coisas ficam arriscadas. Existem dois itens óbvios:

  1. O circulo. Isso é representado (no Agda) usando um postulado e, portanto, não é tão bom quanto outras coisas.
  2. ∞

Também existem outros itens, mas ainda não cheguei a ler essa parte da formalização da Agda ... Mas, em geral, a maior parte do HoTT pode ser bem formalizada tanto na Agda quanto na Coq.

Mais importante, ambas as equipes de desenvolvedores estão trabalhando ativamente na adaptação de seus sistemas para que mais HoTT possa ser gerenciado, pelo menos sempre que houver uma teoria clara de como implementar os recursos necessários. Isso acabou sendo um desafio em partes.

Jacques Carette
fonte