Оценка стратегии

Question

Как следует одна причина, о вычислении функции в примерах, как следующее в Haskell:

let f x = ... 
    x = ... 
in map (g (f x)) xs 

В GHC, иногда (f x) вычисляется только один раз, а иногда и один раз для каждого элемента в xs, в зависимости от того, что именно f и g есть. Это может быть важно, когда f x - дорогое вычисление. Он только что сработал новичком Haskell, которым я помогал, и я не знал, что сказать ему, кроме того, что это зависит от компилятора. Есть ли лучшая история?

Update

В следующем примере (f x) будет оцениваться в 4 раза:

let f x = trace "!" $ zip x x 
    x = "abc" 
in map (\i -> lookup i (f x)) "abcd" 

Answer 1

С расширений языка, мы можем создавать ситуации, в которых f xнеобходимо быть оценены несколько раз:

{-# LANGUAGE GADTs, Rank2Types #-} 
module MultiEvG where 

data BI where 
    B :: (Bounded b, Integral b) => b -> BI 

foo :: [BI] -> [Integer] 
foo xs = let f :: (Integral c, Bounded c) => c -> c 
      f x = maxBound - x 
      g :: (forall a. (Integral a, Bounded a) => a) -> BI -> Integer 
      g m (B y) = toInteger (m + y) 
      x :: (Integral i) => i 
      x = 3 
     in map (g (f x)) xs 

Гвоздь должен иметь f x полиморфный даже в качестве аргумента g, и мы должны создать ситуацию, в которой тип (ы), в котором это необходимо, не может быть предсказано (мой первый удар использовал Either a b вместо BI, но при оптимизации это, разумеется, привело только к двум оценкам f x).

Полиморфное выражение должно оцениваться по крайней мере один раз для каждого типа, в котором он используется. Это одна из причин ограничения мономорфизма. Однако, когда диапазон типов, в котором он может понадобиться, ограничен, возможно запоминать значения для каждого типа, и в некоторых случаях GHC делает это (требуется оптимизация, и я ожидаю, что количество типов не должно быть слишком большой). Здесь мы сталкиваемся с тем, что является в основном неоднородным списком, поэтому при каждом вызове g (f x) он может понадобиться произвольному типу, удовлетворяющему ограничениям, поэтому вычисление невозможно снять за пределами map (технически компилятор все еще может создавать кеш значений для каждого используемого типа, поэтому он будет оцениваться только один раз для каждого типа, но GHC не имеет, по всей вероятности, это не стоило бы проблем).

• Мономорфные выражения нужно оценивать только один раз, их можно обменивать. Независимо от того, выполняются ли они до реализации; по чистоте, это не изменяет семантику программы. Если выражение привязано к имени, на практике вы можете полагаться на его совместное использование, поскольку это легко и очевидно, что хочет программист. Если это не связано с именем, это вопрос оптимизации. С генератором байткода или без оптимизаций выражение часто будет оцениваться повторно, но при повторной оценке оптимизации будет указываться ошибка компилятора.
• Полиморфные выражения должны оцениваться по крайней мере один раз для каждого типа, в котором они используются, но с оптимизацией, когда GHC может видеть, что он может использоваться несколько раз в одном типе, он будет (обычно) по-прежнему использоваться для этого типа при более широком вычислении.

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

Answer 2

Это действительно зависит от оптимизаций GHC, поскольку вы были в состоянии сказать.

Что нужно сделать, это изучить GHC core, который вы получите после оптимизации программы. Я бы посмотрел на сгенерированный Core и проверил, имел ли f x свой собственный оператор let за пределами map или нет.

Если вы хотите быть уверены, ,, то вы должны учитывать f x в отдельное присвоенной переменной в let, но есть на самом деле не гарантированный способ, чтобы понять это, кроме чтения через Core.

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

Answer 3

Ваши примеры действительно совсем другие.

В первом примере аргумент карты равен g (f x) и передается один раз map, скорее всего, как частично примененная функция. Должен g (f x), когда применяется к аргументу в пределах map, оцените его первый аргумент, тогда это будет сделано только один раз, а затем thunk (f x) будет обновлен с результатом.

Следовательно, в вашем первом примере f x будет оценен не более 1 раз.

Ваш второй пример требует более глубокого анализа, прежде чем компилятор сможет прийти к выводу, что (f x) всегда является константой в выражении лямбда. Возможно, он никогда не будет оптимизировать его вообще, потому что он может знать, что след не совсем kosher. Таким образом, это может оцениваться 4 раза при трассировке и 4 раза или 1 раз, когда не отслеживается.

Answer 4

В GHC без оптимизации тело функции оценивается каждый раз, когда вызывается функция. («Вызов» означает, что функция применяется к аргументам и результат оценивается.) В следующем примере f x находится внутри функции, поэтому он будет выполняться каждый раз, когда вызывается функция. (GHC может оптимизировать это выражение, как описано в FAQ [1].)

let f x = trace "!" $ zip x x 
    x = "abc" 
in map (\i -> lookup i (f x)) "abcd" 

Однако, если мы будем двигаться f x из функции он будет выполнять только один раз.

let f x = trace "!" $ zip x x 
    x = "abc" 
in map ((\f_x i -> lookup i f_x) (f x)) "abcd" 

Это может быть переписан более читаем, как

let f x = trace "!" $ zip x x 
    x = "abc" 
    g f_x i = lookup i f_x 
in map (g (f x)) "abcd" 

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

[1] http://www.haskell.org/haskellwiki/GHC/FAQ#Subexpression_Elimination