c - sanguineos - tipos de sangre raros

¿Puede un compilador detectar automáticamente funciones puras sin el tipo de información sobre pureza?

Question

Así que estoy discutiendo con mi amigo que afirma que un compilador como GCC puede detectar una función pura automáticamente sin ningún tipo de información. Dudo que.

Los lenguajes como D o Haskell tienen pureza en sus sistemas de tipos y un programador define explícitamente qué función es pura o no. Una función pura no tiene efectos secundarios y, por lo tanto, se puede paralelizar muy fácilmente.

Entonces la pregunta es: ¿esto es todo necesario o no? ¿Podría un compilador detectar la pureza, sin ninguna meta o tipo de información, simplemente suponiendo que todo lo que hace IO o accede a variables globales automáticamente no es puro?

Answer 1

Claro, puedes detectar funciones puras en algunos casos. Por ejemplo,

int f(int x)
{
    return x*2;
}

se puede detectar como puro con análisis estático simple. La dificultad está en hacer esto en general, y detectar interfaces que usan un estado "interno" pero que son externamente puros es básicamente imposible.

GCC tiene las opciones de advertencia -Wsuggest-attribute=pure y -Wsuggest-attribute=const , que sugieren funciones que podrían ser candidatas para los attributes pure y const . No estoy seguro si opta por ser conservador (es decir, perder muchas funciones puras, pero nunca sugerirlo para una función no pura) o deja que el usuario decida.

Tenga en cuenta que la definición de pure de GCC "depende únicamente de argumentos y variables globales":

Muchas funciones no tienen ningún efecto excepto el valor de retorno y su valor de retorno depende solo de los parámetros y / o variables globales. Dicha función puede estar sujeta a eliminación de subexpresiones comunes y optimización de bucles tal como lo haría un operador aritmético. Estas funciones deben declararse con el atributo pure .

- attributes

La pureza estricta, es decir, los mismos resultados para los mismos argumentos en todas las circunstancias, está representada por el atributo const , pero dicha función ni siquiera puede desreferenciar un puntero que se le haya pasado. Por lo tanto, las oportunidades de paralelismo para funciones pure son limitadas, pero se pueden comparar muchas menos funciones con las funciones puras que se pueden escribir en un lenguaje como Haskell.

Por cierto, el paralelismo automático de funciones puras no es tan fácil como se podría pensar; la parte difícil es decidir qué paralelizar. Paralelizar los cálculos que son demasiado baratos, y la sobrecarga lo hace inútil. No se paralelice lo suficiente y no obtenga los beneficios. No conozco ninguna implementación práctica de lenguaje funcional que tenga una paralelización automática por esta razón, aunque las bibliotecas como repa paralelan muchas operaciones detrás de escena sin un paralelismo explícito en el código de usuario.

Answer 2

Descubrí mientras escribía un artículo que compara el rendimiento de C # y C ++ que Visual C ++ puede detectar una función pura de complejidad moderada, al tiempo que llama a una función que calculó un polinomio .

Llamé a la función polinomial en un bucle para ganar tiempo en el reloj. El compilador optimizó la llamada para ejecutar una vez antes de que el ciclo se iniciara y reutilizara el resultado dentro del ciclo. Para hacer eso, debería saber que no hay efectos secundarios.

Debo decir sin embargo, es bueno poder garantizar que el compilador pueda hacer una optimización, marcando una función como pura, y también sirve como una forma de documentación.

Answer 3

Determinar si una función es pura (incluso en el sentido limitado utilizado por GCC) es equivalente al problema de detención, por lo que la respuesta es "no para funciones arbitrarias". Es posible detectar automáticamente que algunas funciones son puras, otras no son puras, y marcar el resto como "desconocido", lo que permite la paralelización automática en algunos casos.

En mi experiencia, incluso los programadores no son muy buenos para descifrar estas cosas, por lo que quiero que el sistema de tipos me ayude a hacer un seguimiento, no solo para el optimizador.

Answer 4

Hay otro problema Considerar

int isthispure(int i) {
   if (false) return getchar();
   return i + 42;
}

La función es efectivamente pura, aunque contiene código impuro, pero este código no puede ser alcanzado. Ahora supongamos que false es reemplazado por g(i) pero sabemos con bastante seguridad que g (i) es falso (por ejemplo, g podría verificar si su argumento es un número de Lychrel ). Para demostrar que esta pureza es de hecho pura, el compilador tendría que demostrar que no existen números de Lychrel.

(Admito que esta es una consideración bastante teórica. También se podría decidir que si una función contiene algún código impuro, es en sí misma impura. Pero esto no está justificado por el sistema de tipo C, en mi humilde opinión.)