Как сделать CAF не CAF в Haskell?

Ответ 1

Обобщение. Если у вас есть постоянное значение, можете ли вы обобщить это на функцию некоторой переменной? Именование моей функции в вопросе 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 быть в виде бесконечного списка.

Ответ 2

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

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

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))

Не встроить и больше функций

Сделайте все в функцию, включая 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-free! Даже с -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. Однако это не работает.

Ответ 3

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

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

twoTrues u = map (++ (True : repeat False)) . trueBlock <$> [(u `seq` 1)..]

Ответ 4

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

Ответ 5

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

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

{-# NOINLINE false #-}
false :: () -> Bool
false _ = False

Ответ 6

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

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

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

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

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

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

Ответ 7

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

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

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

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

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

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

Теперь вы можете использовать twoTrues следующим образом:

map concat $ twoTrues()

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

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

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

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

ИЗМЕНИТЬ

Теперь можно задаться вопросом, есть ли только один способ реализовать 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.