Consecuencias de la incapacidad para agregar números naturales en C

Question

En el Sistema F I puede definir la auténtica total, además de la función con la Iglesia números.

En Haskell no puedo definir esa función, porque de la parte inferior valor.Por ejemplo, en haskell si x + y = x, entonces no puedo decir que y es cero si x es inferior, x + y = x para cualquier y.Por eso, la suma no es la verdadera adición, sino de una aproximación a ella.

En C no puedo definir que la función debido a la C la especificación requiere que todo tiene un tamaño finito.Así que en C es posible aproximaciones son incluso peores que en Haskell.

Por lo tanto tenemos:

En el Sistema de F es posible definir la adición, pero no es posible disponer de una completa aplicación (porque no hay ningún infinita de hardware).

En Haskell no es posible definir la adición (porque de la parte inferior), y no es posible tener una implementación completa.

En C no es posible definir la suma total de la función (porque semántica de todo lo que es limitado) pero compatible con las implementaciones son posibles.

Para todos 3 los sistemas formales (Haskell, Sistema de F y C), parecen tener diferentes concesiones de diseño.

Entonces, ¿cuáles son las consecuencias de la elección de uno sobre otro?

Answer 1

Haskell

Este es un problema extraño porque estás trabajando con una vaga noción de =. _|_ = _|_ sólo "tiene" (e incluso entonces usted realmente debería usar ⊑) en el dominio en el nivel semántico.Si distinguimos entre la información disponible en el dominio en el nivel semántico y la igualdad en el lenguaje mismo, entonces es perfectamente correcto decir que True ⊑ x + y == x --> True ⊑ y == 0.

No, además de que es el problema, y no es de números naturales que son el problema, el asunto es simplemente distinguir entre la igualdad en el lenguaje y las declaraciones acerca de la igualdad o de la información en la semántica de la lengua.Ausente el tema de los fondos, normalmente podemos razonar sobre Haskell uso ingenuo de la lógica ecuacional.Con fondos, todavía podemos utilizar el razonamiento ecuacional -- sólo tenemos que ser más sofisticado, con nuestras ecuaciones.

Una mayor y más clara exposición de la relación entre el total de los idiomas y el parcial de idiomas definidos por el levantamiento de ellos es dado en el excelente papel "Rápido y Suelto el Razonamiento es Moralmente Correcto".

C

Reclama que el C requiere todo (incluyendo espacio direccionable) tener un tamaño finito, y por lo tanto que C semántica de "imponer un límite en el tamaño de representable naturales.De verdad que no.El Estándar C99 dice lo siguiente:"Cualquier tipo de puntero puede ser convertido a un tipo entero.Excepto como se especificó anteriormente, el resultado de la implementación definido.Si el resultado no puede ser representado en el tipo integer, el comportamiento es indefinido.El resultado no tiene que estar en el rango de valores de cualquier número entero tipo". El fundamento documento destaca, además, que "C ya se ha implementado en una amplia variedad de arquitecturas.Mientras que algunos de estos arquitecturas característica uniforme de los punteros, que son el tamaño de algunos de tipo entero, máximo el código portable no puede asumir ninguna correspondencia necesaria entre los diferentes tipos de puntero y los tipos enteros.En algunas implementaciones, los punteros pueden ser incluso más amplia que la de cualquier tipo entero."

Como usted puede ver, hay explícitamente ninguna suposición de que los punteros deben ser de un tamaño finito.

Answer 2

Tiene un conjunto de teorías como marcos para hacer su razonamiento; La realidad finita, la semántica de Haskell, el sistema F son solo de ellos.

Puede elegir la teoría apropiada para su trabajo, construir una nueva teoría desde cero o desde grandes teorías existentes reunidas. Por ejemplo, puede considerar el conjunto de programas de Haskell siempre terminados y emplear semánticas sin fondo de manera segura. En este caso, su adición será correcta.

Para un lenguaje de bajo nivel, puede haber consideraciones para enchufar la finura, pero para un lenguaje de alto nivel vale la pena omitir tales cosas porque las teorías más abstractas permiten una aplicación más amplia.

Mientras se programa, no utiliza la teoría de la "especificación del lenguaje" sino la teoría de "especificación del lenguaje + limitaciones de implementación", por lo que no hay diferencia entre los casos en que los límites de memoria presentes en la especificación del lenguaje o en la implementación del lenguaje. La ausencia de límites se vuelve importante cuando comienzas a construir construcciones teóricas puras en marco de semántica del lenguaje. Por ejemplo, es posible que desee probar algunas equivalencias de programa o traducciones de idiomas y descubrir que cada detalle innecesario en la especificación del lenguaje trae mucho dolor en la prueba.

Answer 3

Estoy seguro de que has escuchado el aforismo de que "en teoría no hay diferencia entre la teoría y la práctica, pero en la práctica lo existe".

En este caso, en teoría hay diferencias, pero todos estos sistemas tratan con la misma cantidad finita de memoria direccionable, por lo que en la práctica no hay diferencia.

EDITAR:

Suponiendo que puede representar un número natural en cualquiera de estos sistemas, puede representar la adición en cualquiera de ellos. Si las restricciones que le preocupan por evitar que represente un número natural, entonces no puede representar la adición de Nat*Nat.

Representa un número natural como un par de (límite inferior heurístico en el tamaño máximo de bits y una lista de bits de bits perezosamente evaluada).

En el cálculo de Lambda, puede representar la lista como una función que devuelve una función que llamó a True Devuelve el bit de 1, y llamado con False Devuelve una función que hace lo mismo para el bit de los 2, etc.

La adición es entonces una operación aplicada a la zip de esas dos listas perezosas que propaga un bit de transporte.

Por supuesto, debe representar la heurística de tamaño máximo de bit como un número natural, pero si solo instancia los números con un bit cuentan que es estrictamente más pequeño que el número que representa, y sus operadores no rompen ese heurístico, entonces el bit el bit El tamaño es inductivamente un problema menor que los números que desea manipular, por lo que las operaciones terminan.

Sobre la facilidad de contabilidad de los casos de borde, C le brindará muy poca ayuda. Puede devolver valores especiales para representar el desbordamiento/subflujo, e incluso tratar de hacerlos infecciosos (como IEEE-754 NAN), pero no recibirá quejas en el momento de la compilación si no lo verifica. Puede intentar sobrecargar una señal SIGFPE o algo similar a los problemas de trampa.

No puedo decir que y sea cero: si x es inferior, x + y = x para cualquier y.

Si está buscando hacer una manipulación simbólica, Matlab y Mathematica se implementan en idiomas C y C. Dicho esto, Python tiene una implementación Bigint bien optimizada que se utiliza para todos los tipos de enteros. Sin embargo, probablemente no sea adecuado para representar números realmente grandes.