Qual é o papel do Cálculo Bicolor das Construções?

Então, estou lendo um pouco sobre elaboração, particularmente sobre algoritmos baseados no Cálculo de Construção Bicolor, e estou um pouco confuso. Não entendo qual é exatamente o propósito da $CC^{bi}$ . Parece ser idêntico a $CC$ exceto que há uma distinção entre argumentos implícitos e explícitos para funções. Em particular, não vejo como isso permite que você escreva $(id\; 0)$ vez de $(id\; \mathbb{N}\; 0)$ . Se assumirmos um sistema para definições globais, então,

$id : (\Pi A\; |\; \mathsf{Type}\; . (\Pi x : A\; . A))$

$id = (\lambda A\; |\; \mathsf{Type}\; . (\lambda x : A . x))$ .

As regras realmente permitem $(id\; 0)$ ? Claro que a sintaxe sim, mas não a vejo na relação de digitação. Estou esquecendo de algo? Estou entendendo o papel de $CC^{bi}$ incorretamente?

Além disso, a propriedade da confluência não é perdida? Acho que meu problema é que estou lendo sobre elaboração sem ter lido muito sobre antes disso. O que é um bom artigo que o apresenta e sozinho? $CC^{bi}$

Edit: Para ser mais específico, estou perguntando como é aceito no lugar de $(id\; 0)$ quando as regras para tanto explícita e implícita aplicação são sytnax modulo idênticos. Não vejo diferença entre eas regras para ambos parecem as mesmas. $(id\; \mathbb{N}\; 0)$ $\Pi$ $:$ $|$

Edit: Eu não estou falando sobre o cálculo implícito de Construções, que é uma teoria diferente e tem regras diferentes para explícita 's (geração vs. aplicação.) $\Pi$

Edit: Ok, acho que estou começando a entender isso, mas não vou responder a essa pergunta até ter certeza. Basicamente não digita cheque e, de fato, é apenas elaborado para $(id\; 0)$ imediatamente antes da verificação do tipo ou realizada como uma responsabilidade secundária do algoritmo de verificação do tipo. Essencialmente, esses cálculos implícitos devem ser linguagens de interface (final do usuário), elaboradas nos cálculos usuais (explícitos) ou pelo menos no fragmento explícito dos cálculos implícitos antes que os termos sejam verificados. Se for esse o caso, acho que vejo o quadro geral. alguém pode por favor confirmar isso? $(id\; \mathbb{N}\; 0)$

type-theory lambda-calculus type-inference dependent-type Anthony
fonte

Como eu disse abaixo, sua intuição está correta: o cálculo bicolor de construções é um cálculo explícito, no qual os argumentos omitidos pelo usuário, mas elaborados pelo "front end" são marcados explicitamente. Além disso, a confluência é perdida para reduções beta + eta, mas verdadeira se restrita a apenas beta.

Cody

Respostas:

No cálculo implícito de construções que estende os sistemas de tipo puro com um aglutinante e subtipo de tipo de interseção , Alexandre Miquel apresenta os conceitos básicos para o cálculo implícito de construções, que acredito ser sinônimo de cálculo de construções bicolor.

O ponto é (entre outras coisas) ter um cálculo sem a confusão de anotações explícitas de tipo em todos os lugares. A inferência de tipo é (muito provavelmente) indecidível.

Neste cálculo, se tomarmos , em seguida, você pode derivar simplesmente usando o produto explícito e as regras implícitas do produto em sucessão. Em seguida, a regra para a instanciação do produto implícito permite e assim $id=\lambda x. x$

⊢ Eu d : \forall X : T y p e . X \to X

$\vdash id\colon \forall X\colon Type. X\rightarrow X$

⊢ Eu d : N uma t \to N uma t

$\vdash id\colon Nat\rightarrow Nat$

⊢ Eu d 0 0 : N uma t

$\vdash id\ 0 \colon Nat$ O sistema admite redução e confluência de assuntos, mesmo em termos não digitados (que de fato falham nos cálculos com anotações de abstração). Tudo isso pode ser encontrado na tese de Alexandre, que infelizmente está em francês. Não tenho certeza se tenho uma referência melhor para esses resultados, embora tenha medo.

cody
fonte

A primeira parte da sua resposta eu sabia, mas acho que deveria ter sido mais específica na minha pergunta original. Ou seja, como exatamente (id 0) é permitido se id tiver o tipo (\ Pi X | Type. X -> X) porque parece que a regra APP é idêntica para o \ Pi implícito e explícito. No cálculo implícito de construções, que é de fato uma teoria diferente, esse não é o caso, porque é separado em APP e GEN. Para verificar se é diferente, verifique o cabeçalho "Um cálculo com argumentos 'realmente implícitos'" no documento que você referenciou.

Anthony

Em relação à decidibilidade. O artigo a que você se refere conjectura que é teoria é indecidível. O artigo que ele faz referência (acho que o cálculo de cálculo bicolor "original" do papel de construção) afirma ser decidível, mas não o prova explicitamente. Eu li depois de postar esta pergunta e parece que ela definitivamente deve ser decidida e, dependendo das restrições sintáticas, mantém a confluência. Por outro lado, ainda estou preso à minha confusão original: \

Anthony

Talvez você deva nos dizer qual papel está vendo.

Cody

Ok, dei uma olhada em Elaboration and Erasure in Type Theory, de Marko Luther, que acho que é sua referência. Nesse caso, não há diferença semântica entre os produtos explícitos e implícitos e, de fato, o sistema bicolor é uma extensão conservadora do cálculo das construções. O que acontece é que você usa a elaboração para obter um termo sem o argumento explícito para transformá-lo em um termo totalmente anotado: id !1 0elaborado para id Nat 0. Neste texto, a elaboração é abordada na seção 4.

cody 29/07

C C^{b i}

$CC^{bi}$