Стратегия оценки

Question

Как следует рассуждать об оценке функции в примерах вроде следующего в Haskell:

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

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

Обновить

В следующем примере (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

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

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

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

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

Answer 3

Как вы могли сказать, это действительно зависит от оптимизации GHC.

Лучше всего изучить ядро GHC, которое вы получите после оптимизации программы. Я бы посмотрел на сгенерированное ядро ​​и проверил, f x был свой let заявление вне map или нет.

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

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

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