¿Cuál es el papel del cálculo bicolor de las construcciones?

Entonces, estoy leyendo un poco sobre la elaboración, particularmente, algoritmos basados en el cálculo bicolor de la construcción, y estoy un poco confundido. No entiendo cuál es exactamente el propósito del . Parece ser idéntico a excepto que hay una distinción entre argumentos implícitos y explícitos para funciones. En particular, no veo cómo le permite escribir lugar de . Si asumimos un sistema para definiciones globales, entonces, $CC^{bi}$ $CC$ $(id\; 0)$ $(id\; \mathbb{N}\; 0)$

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

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

¿Las reglas realmente permiten ? Por supuesto, la sintaxis sí, pero no la veo en la relación de escritura. ¿Me estoy perdiendo de algo? ¿Entiendo incorrectamente el papel de ? $(id\; 0)$ $CC^{bi}$

Además, ¿no se pierde la propiedad de la confluencia? Supongo que mi problema es que estoy leyendo sobre elaboración sin haber leído mucho sobre antes de esto. ¿Qué es un buen artículo que lo presenta y solo? $CC^{bi}$

Editar: para ser más específicos, pregunto cómo se acepta en lugar de cuando las reglas para la aplicación explícita e implícita de son idénticas sintaxis de módulo . No veo diferencia entre y $(id\; 0)$ $(id\; \mathbb{N}\; 0)$ $\Pi$ $:$ $|$ Las reglas para ambos parecen las mismas.

Editar: No estoy hablando acerca del cálculo implícito de Construcciones, que es una teoría diferente y tiene diferentes reglas para explícita 's (generación o aplicación). $\Pi$

Editar: Bien, creo que estoy empezando a entender esto, pero no responderé esta pregunta hasta que esté seguro. Básicamente no escribe cheque y, de hecho, solo está elaborado para $(id\; 0)$ justo antes de la verificación de tipo o como una responsabilidad secundaria del algoritmo de verificación de tipo. Esencialmente, estos cálculos implícitos están destinados a ser lenguajes de interfaz (usuario final) que se elaboran en los cálculos habituales (explícitos) o al menos en el fragmento explícito de los cálculos implícitos antes de que se verifiquen los tipos. Si ese es el caso, entonces creo que veo el panorama general. ¿Puede alguien por favor confirmar esto? $(id\; \mathbb{N}\; 0)$

type-theory lambda-calculus type-inference dependent-type Antonio
fuente

Como dije a continuación, su intuición es correcta: el cálculo bicolor de las construcciones es un cálculo explícito, en el que los argumentos omitidos por el usuario pero elaborados por el "front end" están explícitamente marcados. Además, se pierde la confluencia para las reducciones beta + eta, pero es cierto si se restringe solo a beta.

cody

Respuestas:

En El cálculo implícito de construcciones que extienden sistemas de tipo puro con un aglutinante y subtipo de tipo de intersección , Alexandre Miquel presenta los conceptos básicos para el cálculo implícito de construcciones, que creo que es sinónimo del cálculo bicolor de construcciones.

El punto es (entre otras cosas) tener un cálculo sin el desorden de anotaciones de tipo explícito en todas partes. Sin embargo, la inferencia de tipos es (muy probable que sea) indecidible.

En este cálculo, si tomamos , entonces puedes derivar simplemente usando el producto explícito y las reglas del producto implícito en sucesión. A continuación, la regla de instancias para el producto implícita permite y así $id=\lambda x. x$

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

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

⊢ i d : N a t \to N a t

$\vdash id\colon Nat\rightarrow Nat$

⊢ i d 0 : N a t

$\vdash id\ 0 \colon Nat$ El sistema admite la reducción y la confluencia de sujetos, incluso en términos sin tipo (que de hecho falla para los cálculos con anotaciones de abstracción). Todo esto se puede encontrar en la tesis de Alexandre, que lamentablemente está en francés. No estoy seguro de tener una mejor referencia para estos resultados, aunque me temo.

cody
fuente

La primera parte de su respuesta la conocía, pero creo que debería haber sido más específica en mi pregunta original. Es decir, cómo se permite (id 0) exactamente si el id tiene el tipo (\ Pi X | Type. X -> X) porque parece que la regla APP es idéntica para el \ Pi implícito y explícito. En el cálculo implícito de las construcciones, que de hecho es una teoría diferente, este no es el caso porque está separado en APP y GEN. Para verificar que es diferente, marque el encabezado "Un cálculo con argumentos" realmente implícitos "en el documento al que hizo referencia.

Anthony

En cuanto a la capacidad de decisión. El artículo al que hace referencia conjetura que su teoría es indecidible. El documento al que hace referencia (supongo que el cálculo bicolor "original" de papel de construcciones) dice ser decidible pero no lo prueba explícitamente. Lo leí después de publicar esta pregunta y parece que definitivamente debería ser decidible y, dependiendo de las restricciones sintácticas, conserva la confluencia. Por otro lado, todavía estoy atrapado con mi confusión original: \

Anthony

Tal vez debería decirnos qué papel está mirando.

cody

Ok, eché un vistazo a Elaboración y borrado en la teoría de tipos de Marko Luther, que supongo que es su referencia. En ese caso, no existe una diferencia semántica entre los productos explícitos e implícitos, y de hecho el sistema bicolor es una extensión conservadora del cálculo de las construcciones. Lo que sucede es que utiliza la elaboración para tomar un término sin el argumento explícito para convertirlo en un término totalmente anotado: id !1 0elabora para id Nat 0. En este texto, la elaboración se cubre en la sección 4.

cody

C C^{b i}

$CC^{bi}$