Может ли компилятор автоматически определять чистые функции без информации о типе чистоты?

Question

Поэтому я спорю с моим другом, который утверждает, что такой компилятор, как GCC, может автоматически определять чистую функцию без какой-либо информации о типе.Я сомневаюсь, что.

Такие языки, как D или Haskell, имеют чистоту в своих системах типов, и программист явно определяет, какая функция является чистой или нет.Чистая функция не имеет побочных эффектов и поэтому ее очень легко распараллелить.

Итак, вопрос в том: все это необходимо или нет?Может ли компилятор определить чистоту без какой-либо мета-информации или типа, просто предположив, что все, что делает IO или обращается к глобальным переменным автоматически, не является чистым?

Answer 1

Конечно, вы можете обнаружить чистые функции в некоторых случаях.Например,

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

можно определить как чистый с помощью простого статического анализа.Сложность заключается в том, чтобы сделать это в целом, и обнаружить интерфейсы, которые используют «внутреннее» состояние, но внешне чистые, в принципе невозможно.

GCC имеет опции предупреждений -Wsuggest-attribute=pure и -Wsuggest-attribute=const, которые предлагают функции, которые могут быть кандидатами для атрибутов pure и const .Я не уверен, предпочитает ли он быть консервативным (то есть пропускает много чистых функций, но никогда не предлагает его для не чистой функции) или позволяет пользователю решать.

Обратите внимание, что определение pure в GCC«зависит только от аргументов и глобальных переменных»:

Многие функции не имеют эффектов, кроме возвращаемого значения, и их возвращаемое значение зависит только от параметров и / или глобальных переменных.Такая функция может быть подвержена общему исключению подвыражения и оптимизации цикла, как если бы был арифметический оператор.Эти функции должны быть объявлены с атрибутом pure.

- GCC manual

Строгая чистота, то есть одинаковые результаты для одинаковых аргументов при любых обстоятельствах, представлен атрибутом const, но такая функция не может даже разыменовать переданный ему указатель.Таким образом, возможности распараллеливания для pure функций ограничены, но гораздо меньше функций может быть const по сравнению с чистыми функциями, которые вы можете написать на языке, подобном Haskell.

Кстати, автоматическое распараллеливание чистых функцийне так просто, как вы думаете;трудная часть принимает решение что распараллелить.Распараллеливать вычисления, которые слишком дешевы, а накладные расходы делают это бессмысленным.Не распараллеливайтесь достаточно, и вы не пожнете выгоды.Я не знаю ни одной практической реализации функционального языка, которая бы делала автоматическое распараллеливание по этой причине, хотя такие библиотеки, как repa , распараллеливают многие операции за кулисами без явного параллелизма в пользовательском коде.

Answer 2

Есть еще одна проблема. Рассмотрим

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

Функция фактически чистая, хотя она содержит нечистый код, но этот код недоступен. Теперь предположим, что false заменено на g(i), но мы точно знаем, что g (i) ложно (например, g может проверить, является ли его аргумент числом Лихрела ). Чтобы доказать, что это действительно чисто, компилятор должен доказать, что чисел Лихрела не существует.

(Я допускаю, что это довольно теоретическое соображение. Можно также решить, что если функция содержит какой-либо нечистый код, она сама по себе нечиста. Но это не оправдано системой типов C, ИМХО.)

Answer 3

Определение того, является ли функция чистой (даже в ограниченном смысле, используемом GCC), эквивалентно проблеме остановки, поэтому ответ «не для произвольных функций». Можно автоматически определить, что некоторые функции являются чистыми, а другие - не чистыми, и пометить остальные как «неизвестные», что в некоторых случаях допускает автоматическое распараллеливание.

По моему опыту, даже программисты не очень хорошо разбираются в таких вещах, поэтому я хочу, чтобы система типов помогала отслеживать это для меня , а не только для оптимизатора.

Answer 4

Я обнаружил, когда писал статью , сравнивая производительность C # и C ++ , что Visual C ++ действительно может обнаружить чистую функцию средней сложности, при вызове функции , которая вычисляла полином .

Я вызвал полиномиальную функцию в цикле, чтобы съесть время на часах. Компилятор оптимизировал вызов для запуска один раз перед началом цикла и повторно использовал результат в цикле. Для этого нужно знать, что побочных эффектов нет.

Должен сказать, что приятно иметь возможность гарантировать , что компилятор может выполнять оптимизацию, помечая функцию как чистую, и она также служит формой документации.