Как сделать CAF не CAF в Haskell? - PullRequest
27 голосов
/ 23 мая 2011

Как превратить постоянную аппликационную форму, а не в постоянную аппликационную форму, чтобы предотвратить ее сохранение в течение всего срока действия программы?

Я пробовал этот подход:

-- | Dummy parameter to avoid creating a CAF
twoTrues :: () -> [[[Bool]]]
twoTrues _ = map (++ (True : repeat False)) . trueBlock <$> [1..]

но это не похоже на работу - профиль показывает, что он все еще сохраняется , а все еще помечает его как CAF.

Я нашел один релевантный результат Google по этому вопросу, ответ Саймона Пейтона-Джонса Нилу Митчеллу, который задал именно этот вопрос - но этот ответ, к сожалению, относится к неработающей ссылке.

Ответы [ 7 ]

15 голосов
/ 23 мая 2011

Полный пример

Вот небольшой пример, который показывает ситуацию:

module A where

big :: () -> [Int]
big _ = [1..10^7]

Похоже на функцию, верно? Но что делает GHC? Перечисляет перечисление на верхний уровень!

A.big1 :: [Int]
[ Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 7 0}]
A.big1 =
  case A.$wf1 10 A.big2 of ww_sDD { __DEFAULT ->
  eftInt 1 ww_sDD
  }

A.big :: () -> [Int]
[Arity=1,    
 Unf=Unf{Src=InlineStable, TopLvl=True, Arity=1, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=True)
         Tmpl= \ _ -> A.big1}]
A.big = \ _ -> A.big1

по электронной почте Ой!


Так что мы можем сделать?

Отключить оптимизацию

Это работает, -Onot, но не желательно:

A.big :: () -> [Int]
[GblId, Arity=1]
A.big =
  \ _ ->
    enumFromTo
      @ Int
      $fEnumInt
      (I# 1)
      (^
         @ Int
         @ Type.Integer
         $fNumInt
         $fIntegralInteger
         (I# 10)
         (smallInteger 7))

Не inline, и больше функций

Превратите все в функцию, включая enumFromTo, передавая параметр рабочим:

big :: () -> [Int]
big u = myEnumFromTo u 1 (10^7)
{-# NOINLINE big #-}

myEnumFromTo :: () -> Int -> Int -> [Int]
myEnumFromTo _ n m = enumFromTo n m
{-# NOINLINE myEnumFromTo #-}

Теперь мы, наконец, свободны от CAF! Даже с -O2

A.myEnumFromTo [InlPrag=NOINLINE]
  :: () -> Int -> Int -> [Int]
A.myEnumFromTo =
  \ _ (n_afx :: Int) (m_afy :: Int) ->
    $fEnumInt_$cenumFromTo n_afx m_afy

A.big [InlPrag=NOINLINE] :: () -> [Int]
A.big = \ (u_abx :: ()) -> A.myEnumFromTo u_abx A.$s^2 lvl3_rEe

Yay.


Что не работает?

Отключить - полная лень

Полное преобразование лени выводит определения наружу. Он включен по умолчанию с -O1 или выше. Давайте попробуем выключить его с помощью -fno-full-laziness. Тем не менее, это не работает.

8 голосов
/ 23 мая 2011

Обобщение. Если у вас есть постоянное значение, можете ли вы обобщить это для функции некоторой переменной? Наименование моей функции в вопросе twoTrues сразу предполагает, что эта константа является третьей в последовательности zeroTrues, oneTrue, twoTrues, threeTrues и т. Д. - и это действительно так. Таким образом, обобщение twoTrues в функцию nTrues , которая принимает параметр n и удаление twoTrues, исключит один CAF из программы.

Так получилось, что в этом случае я рассмотрел только случаи zeroTrues, oneTrue и twoTrues для моей программы, потому что это было все, что мне было нужно, но моя программа, естественно, могла быть расширена для работы с nTrues для n> 2 - обобщение до nTrues будет означать, что имеет смысл "обобщать все" до пользователей zeroTrues, oneTrue и т. д. Это не всегда так.

Примечание: могут быть и другие CAF, с которыми нужно иметь дело, либо в коде, либо в результате "оптимизаций" GHC (которые на самом деле не являются оптимизациями в этих патологических случаях).

Этот ответ может потребовать от программиста больше работы, чем это строго необходимо. На самом деле нет необходимости обобщать, как показывает ответ Дона.

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

Примечание об этом конкретном случае (которое можно игнорировать): В этом конкретном случае я бы не хотел превращать nTrues сам в бесконечный список (который снова будет CAF, снова вводя оригинальная проблема!) а не функция. Одна из причин заключается в том, что хотя twoTrues может быть полезно в форме бесконечного списка, я не понимаю, как было бы полезно (в любом случае, в моем приложении), чтобы nTrues был в форме бесконечного списка.

5 голосов
/ 23 мая 2011

Кажется, это давняя проблема http://hackage.haskell.org/trac/ghc/ticket/917. И на мой взгляд, критический.

5 голосов
/ 23 мая 2011

С введением фиктивного параметра вы также должны заставить его выглядеть так, как будто результат зависит от параметра.В противном случае ум GHC может снова превратить его в CAF.

Я предлагаю следующее:

twoTrues u = map (++ (True : repeat False)) . trueBlock <$> [(u `seq` 1)..]
3 голосов
/ 23 мая 2011

Вам нужно скрыть тот факт, что rhs является CAF от оптимизатора. Нечто подобное должно сделать это.

twoTrues :: () -> [[[Bool]]]
twoTrues u = map (++ (True : repeat (false u))) . trueBlock <$> [1..]

{-# NOINLINE false #-}
false :: () -> Bool
false _ = False
0 голосов
/ 13 января 2014

Всякий раз, когда вы используете () в качестве параметра, на самом деле вы говорите

Хотя я объявил параметр здесь, мне не интересно, что это такое, и я не собираюсь ничего делать с его значением.

Вам это не интересно, потому что () вообще ничего интересного не имеет; вы не собираетесь ничего с этим делать, потому что вы ничего не можете сделать с ().

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

К счастью, есть еще один способ сделать это. Посмотрите на следующую модификацию twoTrues:

twoTrues :: a -> [[[Bool]]]
twoTrues _ = map (++ (True : repeat False)) . trueBlock <$> [1..]

Теперь вы можете использовать twoTrues так:

map concat $ twoTrues()

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

Конечно, теперь вы можете передать любую функцию (включая undefined) этой функции. Но это не имеет значения, и на самом деле именно эта возможность делает этот трюк работоспособным, поскольку компилятор больше не может предсказать, как эта функция используется. Когда пользователь видит эту функцию, он должен знать, что вы собираетесь здесь сказать, и заключить, что передача () является самой простой, но даже если он этого не делает и передает что-то еще, это ничего не сломает, и поскольку Haskell ленив дополнительный параметр никогда не может быть оценен вообще.

Так что, если () будет использоваться в результате? Это еще хуже. Поскольку возвращение () означает, что ваша функция вообще ничего не делает (в Haskell все эффекты функции должны быть представлены в ее возвращаемом значении), компилятор имеет право сделать вывод, что ваша функция не нужна.

Вывод таков: () как тип не должен появляться в сигнатурах типа, если только не используется с другим типом (то есть в IO ()).

EDIT

Теперь можно задаться вопросом: если есть только один способ реализовать a -> String из String, почему компилятор не может сделать вывод, что они одинаковы. Ответ, как оказалось, заключается в том, что у вас есть два способа реализовать это.

usual :: a -> String
usual _ = "Hello World!"

unusual :: a -> String
unusual a = seq a "Hello World!"

Почти для всех входных данных usual value = unusual value, но usual undefined равно "Hello World!", а unusual undefined равно undefined.

С человеческой точки зрения, unusual довольно необычно, поскольку заставляет оценивать значение, не связанное с конечным результатом. Если в любом случае вам нужна такая вещь, просто позвоните seq. Кроме того, поскольку Haskell по умолчанию является ленивым, если вы хотите определить строгую функцию, вам лучше задокументировать это поведение. Поэтому, если вы видите такую ​​подпись без дополнительной документации, вы имеете право предполагать, что она реализована usual.

0 голосов
/ 23 мая 2011

Самым простым решением может быть указание компилятору встроить его. (Примечание: этот ответ не проверен. Если он не работает, прокомментируйте ниже.)

Даже если (гипотетически) компилятор по какой-то причине отказывается встроить его, вы можете вместо этого использовать cpp, #defining:

#define twoTrues (map (++ (True : repeat False)) . trueBlock <$> [1..])

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

Опция -cpp указывает GHC предварительно обработать входной файл с помощью cpp.

Подстановка означает дублирование кода n раз, если вы ссылаетесь на twoTrues в n> 1 местах. Однако, хотя это теоретически нежелательно, на практике это, вероятно, не будет значительной проблемой.

...