¿Qué tipo de teoría de la manija de la división por cero y tal?

Question

Decir que tengo un programa que necesita para no dividir por cero:

f(x):
    if nonzero(x):
        return sin(x)/x
    else:
        return 1

Si queremos dividir por cero, obtenemos un error. Podemos demostrar que la función anterior no de error al señalar que la primera si la rama no es tomado cuando x==0, por lo que el posible error de la división no puede suceder, y siempre nos dan una sensible resultado.

Así que la pregunta es ¿qué hace esta prueba en el aspecto como en el tipo de teoría?

Sé que debe involucrar a los tipos de dependientes y tal, y he leído un par de relevante páginas de Wikipedia, pero no sé cómo tipo distinto de cero() o la división o cómo mostrar en el tipo de teoría que el error no puede suceder.

(Esto no debería tener nada que ver con el cero en particular, me pregunto, en general, cómo el tipo de teoría que maneja probando cosas alrededor de estos predicados y dependiente-escribió funciones)

Answer 1

Esto depende enteramente de su tipo de teoría. Libros enteros se han escrito sobre el tipo de teoría, y eso es sólo la introducción antes de empezar a bucear en los trabajos de investigación, por lo que no puede cubrir todos los casos.

Atengámonos a la composición de las teorías, cuando una expresión está bien escrito sólo cuando sus subexpresiones que son, siguiendo el tratamiento habitual de expresiones con variables libres (poniéndolos en un contexto). En ese caso, debe ser:

• un tipo de sistema que tiene un tipo distinto de cero de los números como un subtipo de los números, o permite la introducción de una división con la hipótesis de que el denominador es distinto de cero;
• una instancia de una tipificación de la regla de la if constructo que permite la introducción de la subexpresión sin(x)/x en un contexto donde las $x \ne 0$.

Un simple tipo de sistema puede tener las siguientes normas pertinentes, donde $T \le T'$ significa que el tipo de $T$ es un subtipo de $T'$ $\mathbb{R}$ es el tipo de reales (o computable de reales, o lo que sea de dominio informático): $$ \mathbb{R}^* \le \mathbb{R} \qquad \frac{\Gamma, x:\mathbb{R}^* \vdash M:T \quad \Gamma \vdash N[x\leftarrow 0]:T} {\Gamma, x:\mathbb{R} \vdash \mathtt{ifnonzero}(x, M, N) : T} \qquad \frac{\Gamma \vdash M:\mathbb{R} \quad \Gamma \vdash N:\mathbb{R}^*} {\Gamma \vdash (M/N):\mathbb{R}} $$ Claro, esto es ad hoc, pero es suficiente para este tipo de programa en particular. No es necesario hacer el tipo de gramática compleja para manejar este caso.

Otro enfoque sintáctico de escritura permite a los tipos a integrar la fórmula. Por el Curry-Howard correspondencia, los tipos y las proposiciones lógicas son esencialmente la misma cosa. Un tipo popular de la teoría basada en este principio es que el cálculo de construcciones. Bajo este enfoque, el operador de división puede tomar dos formas:

• dos argumentos: una real, y real junto con una prueba de que esto es real es distinto de cero;
• tres argumentos: una real, otra real, y una prueba de que el segundo real es distinto de cero.

En ambos casos, el tipo de operador es un tipo dependiente, ya que el tipo de la prueba de que el denominador es distinto de cero implica que el denominador. Dispone de un plazo incrustado en un tipo es la definición de un tipo dependiente del sistema. He aquí cómo el tipo de operador de división se vería en un Coq-como la sintaxis, bajo los dos enfoques descritos anteriormente:

(/) : R -> {y:R | y <> 0} -> R
(/) : R -> forall y:R, y <> 0 -> R

Usted puede explorar Coq del axiomatization de los reales. Este es un axiomatization, no una implementación - no hay ninguna definición de la función inversa Rinv, es un parámetro de la teoría (junto a Rplus, Rmult, ...). Este axiomatization elige una forma diferente, menos intuitivo, pero más conveniente modelo: Rinv debe ser definido a lo largo de todos los reales, pero solo se usan en las pruebas con una hipótesis que implica que el denominador es distinto de cero. El axioma Rinv_l estados:

forall r:R, r <> 0 -> (Rinv r) * r = 1

ni en una notación matemática: $\forall r:\mathbb{R}, \neg (r = 0) \to \mathtt{Rinv}(r) * r = 1$. En esta teoría, if construcción tiene un tipo dependiente, donde el valor de la booleano prueba puede ser asumido al escribir las alternativas. $$ \frac{\Gamma \vdash C : \mathtt{boolean} \quad \Gamma, H:C=\mathtt{verdadero} \vdash M:T \quad \Gamma, H:C=\mathtt{false} \vdash N:T} {\Gamma \vdash \mathtt{si}(C,M,N) : T} $$ Esta no es la regla real, sino una presentación que está tan cerca como puedo conseguir sin un 10 páginas en el tratado sobre la dependiente tipo de coincidencia de patrón. Yo también estoy pasando por encima de la distinción entre igualdad sintáctica y semántica de la igualdad, y la igualdad entre las pruebas (boolean valores de la función) y los predicados de igualdad (una proposición), que rápidamente se hace evidente si en realidad se trata de jugar con esto en Coq.

Dada la expresión if nonzero(x)…, la condición de $C$$x \ne 0$, que puede ser usado para demostrar que la subexpresión $\mathtt{sin}(x)/x$ está bien formado, y por lo tanto que la expresión completa nunca se requiere de una división por cero.

Sin embargo, otro enfoque para escribir es tratar a tipos como conjunto. Este enfoque tiende a apelar a los matemáticos, pero no compilador de escritores, ya que los conjuntos de algoritmos y no de la malla. Bajo este enfoque, las alternativas de la condicional construcciones de asumir la condición o de su negación, además de los otros ambiente supuestos. $$ \frac{\Delta \wedge C \Vdash M \T \quad \Delta \wedge \neg C \Vdash N \T} {\Delta \Vdash \mathtt{si}(C,M,N) \T} $$