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

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

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

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

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

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

Answer 3

В 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

Answer 4

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

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

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

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