Переписывание как практическая техника оптимизации в GHC: действительно ли это необходимо?

Я читал статью, написанную Саймоном Пейтоном Джонсом и др. названный "Игра по правилам: переписывание как практическая техника оптимизации в GHC" . Во втором разделе, а именно "Основная идея", они пишут:

Рассмотрим знакомую функцию map, которая применяет функцию к каждому элементу списка. Написанная в Haskell, map выглядит следующим образом:

map f []     = []
map f (x:xs) = f x : map f xs

Теперь предположим, что компилятор встречает следующий вызов map:

map f (map g xs)

Мы знаем, что это выражение эквивалентно

map (f . g) xs

(где "." - состав функции), и мы знаем, что последнее выражение более эффективно, чем первое, потому что нет промежуточного списка. Но компилятор не имеет таких знаний.

Одно из возможных возражений заключается в том, что компилятор должен быть умнее, но программист всегда будет знать то, что компилятор не может понять. Еще одно предложение: позволить программисту передавать такие знания непосредственно компилятору. Это направление, которое мы исследуем здесь.

Мой вопрос: почему мы не можем сделать компилятор умнее? Авторы говорят, что "но программист всегда будет знать то, что компилятор не может понять". Однако это недействительный ответ, потому что компилятор действительно может понять, что map f (map g xs) эквивалентен map (f . g) xs, и вот как это сделать:

map f (map g xs)

map g xs объединяется с map f [] = [].

Следовательно, map g [] = [].
map f (map g []) = map f [].

map f [] объединяется с map f [] = [].

Следовательно, map f (map g []) = [].
map g xs объединяется с map f (x:xs) = f x : map f xs.

Следовательно, map g (x:xs) = g x : map g xs.
map f (map g (x:xs)) = map f (g x : map g xs).

map f (g x : map g xs) объединяется с map f (x:xs) = f x : map f xs.

Следовательно, map f (map g (x:xs)) = f (g x) : map f (map g xs).

Следовательно, теперь мы имеем правила:

map f (map g [])     = []
map f (map g (x:xs)) = f (g x) : map f (map g xs)

Как вы видите, f (g x) - это просто (f . g) и map f (map g xs) вызывается рекурсивно. Это точно определение map (f . g) xs. Алгоритм для этого автоматического преобразования кажется довольно простым. Так почему бы не реализовать это вместо правил перезаписи?

Ответ 1

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

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

Слияние потоков, например, изменяет представление типа данных. Это не может быть выражено путем вложения, поскольку это связано с изменением типа представления (мы пересматриваем проблему оптимизации в терминах Stream ADT). Легко заявить в правилах перезаписи, невозможно с помощью вставки только.

Ответ 2

Что-то в этом направлении было исследовано в тесте бакалавра Йоханнеса Бадера, моего ученика: Поиск уравнений в функциональных программах (PDF файл).

В некоторой степени это конечно возможно, но

Это довольно сложно. Найти такие уравнения в каком-то смысле так сложно, как найти доказательства в теореме proofer, и
он не часто очень полезен, потому что он стремится найти уравнения, которые программист редко записывал напрямую.

Однако полезно очищать после других преобразований, таких как inlining и различные формы слияния.

Ответ 3

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

В конкретном случае карт в структуре, которую вы даете, компьютер может найти оптимизацию. Однако, что относительно связанных структур? Что делать, если функция не является картой? Что делать, если есть дополнительный слой косвенности, например функция, возвращающая карту. В таких случаях компилятор не может легко оптимизировать. Это общая проблема.

Как если бы вы оптимизировали специальный случай, произошел один из двух результатов

Никто не полагается на это, потому что они не уверены, что он есть или нет. В этом случае статьи, подобные тем, которые вы цитируете, записываются
Люди действительно начинают полагаться на это, и теперь каждый разработчик вынужден помнить, что "карты, выполненные в этой конфигурации, автоматически преобразуются в быструю версию для меня, но если я это сделаю в этой конфигурации, я этого не делаю". Это начинает манипулировать тем, как люди используют этот язык, и может фактически уменьшить читаемость!

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

Теперь, если выяснится, что конкретный случай, который вам интересен, вызывает что-то массивное, например, 2% от мировой кодовой базы в Haskell, будет гораздо более сильный аргумент в пользу применения оптимизации вашего конкретного случая.