Почему GHC рассматривает синтаксически LHS * при встраивании?

Ответ 1

Что делать, если в этом примере c сам по себе является типом функции? Я не понимаю, как ваше предложение будет работать в этом сценарии.

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

foo :: [Int] -> Int -> Int -> Int
foo list = let
  -- expensive precomputation here
  bar x y = ...
  in \ x y -> bar x y

Вы хотите, чтобы foo был частично применен, а затем для нескольких приложений получаемой функции, чтобы делиться дорогостоящей работой перед вычислением. Если вместо этого вы вытащили его вперед как foo list x y, вы не смогли бы поделиться этой дорогостоящей предварительной оценкой. (Я столкнулся с этим случаем в серьезных приложениях.)

Ответ 2

Это хороший вопрос. Я прочитал секреты Glasgow Haskell Compiler Inliner для некоторых подсказок, но не нашел много.

Вот ручное волновое объяснение. GHC на самом деле время от времени принимает comp1 до comp2 - который он называет "eta expansion". См. Эту тему для некоторых деталей: http://www.haskell.org/pipermail/glasgow-haskell-users/2011-October/020979.html

Также существует (или была) проблема, при которой это расширение может тонко изменить строгость. См. Это фиксацию в документах (которые, похоже, не находятся в текущих, поэтому либо они не были восстановлены, либо исправлены, но не уверены, что): http://permalink.gmane.org/gmane.comp.lang.haskell.cvs.ghc/57721

В любом случае приведенный выше поток имеет SPJ, объясняющий, почему мы, как всегда, хотим идти в этом направлении, когда это возможно. Поэтому сознательно идти в другом направлении, чтобы улучшить inlining, кажется немного глупым. Как обсуждается секретная статья, непродуманное вложение не является самой большой идеей - превращение прагмы в более грубый молот, так что функции были включены, независимо от того, имеет ли это смысл делать это, вероятно, повредит больше, чем поможет в целом, не говоря уже об увеличении кода, так как модули должны были бы поддерживать разные уровни функций eta-shifted вокруг всех одновременно.

В любом случае, поскольку кто-то очень не является основным разработчиком GHC, это то, что кажется мне наиболее вероятным.

Ответ 3

Хорошо, лучше поздно, чем никогда. Думаю.

comp1 и comp2 не только эквивалентны семантически, но даже синтаксически.

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

id1 x = x
id2 = \x -> x

Изменить: я понял, что не ответил на ваши вопросы, так что вот вы:

• Существует разница для GHC, когда они аннотируются с помощью INLINE pragmas, так как GHC хранит в своем представлении Core разворот функции и для которой можно развернуть ее (это часть Guidance=ALWAYS_IF(arity=1,...)), поэтому на практике это может фактически иметь дело.

• Я не думаю, что это происходит, поскольку comp1 и comp2 нельзя отличить после desugaring к Core, на котором работают все оптимизации. Поэтому, когда GHC хочет создать новое развертывание, он, вероятно, сделает это для манифестации (например, числа ведущих lambdas).

• Вкладывание в основном не выгодно для ненасыщенных связей, см. ниже. То же самое касается примера comp1: причина, по которой мы хотим, чтобы это произошло, заключается не в том, что мы заботимся об устранении вызова функции. Скорее мы хотим, чтобы comp1 был специализирован для параметров f и g, независимо от того, какой конкретный x применяем специализацию. Фактически есть пропуск оптимизации, который должен выполнять такую ​​работу, называемую специализацией конструктора (подробнее об этом ниже). INLINE является даже довольно неудачным для использования здесь: это все равно не будет специализироваться на вызове типа comp1 (const 5), где "очевидно", что это должно быть уменьшено до const 5.

• Следовательно, это не сильно изменится, если вы не побрызгаете каждую связанную вещь с помощью INLINE прагм. Даже тогда это сомнительно, если это приносит какую-либо пользу: дело в том, что просто не имеет смысла встраивать ненасыщенные вызовы без каких-либо дальнейших мотивов (например, специализация функции к конкретному аргументу) и, кроме того, она просто взорвет размер кода при в какой-то момент, поэтому, возможно, это даже может замедлить работу.

Конец редактирования

Одна из причин, почему я считаю, почему ненасыщенные вызовы привязок не включены, заключается в том, что в основном они не приносят никаких новых возможностей оптимизации.

f = \x y -> 1 + (x * y)
g = \x y -> (1 + x) * y

Вложение f 16 дает \y -> 1 + (16*y), что на самом деле не намного проще, чем f 16. Напротив, размер кода значительно увеличился (что является самым большим недостатком вложения).

Теперь, если бы появился вызов типа g 16, это дало бы \y -> (1 + 16) * y, который оптимизировался бы до \y -> 17 * y. Но такие возможности обнаруживаются другим проходом оптимизации, конструктором или специализацией call-pattern. Здесь понимается, что 1 + x можно упростить, если мы знаем значение x. Поскольку мы называем g литералом (например, значением), полезно специализировать g для этого конкретного сайта вызова, например. g16 = \y -> 17 *y. Нет необходимости встраивать g, а также другие сайты вызовов могут совместно использовать код, сгенерированный для g16.

Это всего лишь один пример того, как сделать инкрустацию не нужно, имея при этом эффективный код. Есть много других оптимизаций, которые во взаимодействии с Inliner достигают того, чего вы хотите. Например, расширение Eta гарантирует, что вызовы будут максимально насыщенными:

main = print (f 2)

f = g 1 
g x y = x + y

Так как f всегда вызывается с 1 аргументом, мы можем его расширять:

f eta = g 1 eta

Теперь вызов g насыщен и может быть встроен. Dito для f, поэтому в итоге это уменьшится до

main = print 3

f eta = 1 + eta
g x y = x + y

Удаление мертвого кода Modulo.