Все ли в Haskell хранится в трюках, даже простых значениях?

Ответ 1

Официальный ответ

Это не твое дело. Строго детализация вашего компилятора.

Короткий ответ

Да.

Более длинный ответ

Для самой программы Haskell ответ всегда да, но компилятор может и будет делать что-то по-другому, если узнает, что он может уйти от него по соображениям производительности.

Например, для '' 'add x y = x + y' '' компилятор может генерировать код, который работает с thunks для x и y и создает в результате thunk. Но учтите следующее:

foo :: Int -> Int -> Int
foo x y = x * x + y * y

Здесь оптимизирующий компилятор будет генерировать код, который сначала принимает x и y из своих полей, затем выполняет всю арифметику, а затем сохраняет результат в поле.

Расширенный ответ

В этом документе описывается, как GHC переключился с одного из способов реализации thunks на другой, который был фактически проще и быстрее: http://research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/

Ответ 2

В общем, даже примитивные значения в Haskell (например, типа Int и Float) представлены thunks. Это действительно требуется нестрогой семантикой; рассмотрим следующий фрагмент:

bottom :: Int
bottom = div 1 0

Это определение генерирует исключение div-by-zero, только если проверяется значение дна, но не если значение никогда не используется.

Рассмотрим теперь функцию добавления:

add :: Int -> Int -> Int
add x y = x+y

Наивная реализация add должна вынуждать thunk для x, заставлять thunk для y, добавлять значения и создавать (оцениваемый) thunk для результата. Это огромные накладные расходы для арифметики по сравнению со строгими функциональными языками (не говоря уже о императивных).

Однако оптимизирующий компилятор, такой как GHC, может в основном избежать этих накладных расходов; это упрощенное представление о том, как GHC преобразует функцию добавления:

add :: Int -> Int -> Int
add (I# x) (I# y) = case# (x +# y) of z -> I# z 

Внутренне основные типы, такие как Int, рассматриваются как тип данных с одним конструктором. Тип Int # - это "необработанный" тип машины для целых чисел, а + # - примитивное дополнение к необработанным типам. Операции над сырыми типами реализуются непосредственно на битовых шаблонах (например, регистры) --- не thunks. Бокс и распаковка затем переводятся как приложение-конструктор и сопоставление шаблонов.

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

Ответ 3

Короткий ответ: Да.

Длинный ответ:

val = 5

Это должно быть сохранено в thunk, потому что представьте, если бы мы написали этот в любом месте в нашем коде (например, в импортированной библиотеке или что-то еще):

val = undefined

Если это нужно оценить, когда наша программа запустится, это сработает, верно? Если мы действительно используем это значение для чего-то, это то, что мы хотим, но если мы его не используем, оно не должно влиять на нашу программу настолько катастрофически.

Для вашего второго примера позвольте мне немного изменить его:

div x y = x / y

Это значение также должно быть сохранено в thunk, потому что представьте себе такой код:

average list =
  if null list
     then 0
     else div (sum list) (length list)

Если div был строгим здесь, он был бы оценен, даже если список null (aka. empty), что означает, что запись такой функции не будет работать, потому что у нее не было бы шанса return 0 при задании пустого списка, даже если это то, что мы хотели бы в этом случае.

Ваш последний пример - это просто вариант примера 1, и он должен лениться по тем же причинам.

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

Ответ 4

Было бы абсолютно правильно обернуть каждое значение в thunk. Но поскольку Haskell не является строгим, компиляторы могут выбирать, когда оценивать thunks/выражения. В частности, компиляторы могут выбрать выражение раньше, чем это необходимо, если это приведет к улучшению кода.

Оптимизация компиляторов Haskell (GHC) позволяет выполнить Анализ стриктуры, значения которых всегда будут вычисляться.

В начале компилятор должен предположить, что ни один из аргументов функции никогда не используется. Затем он просматривает тело функции и пытается найти приложения функций, которые 1), как известно, строгие в (по крайней мере, некоторых) их аргументах и ​​2) всегда должны быть оценены для вычисления результата функции.

В вашем примере у нас есть функция (+), которая является строгой в обоих аргументах. Таким образом, компилятор знает, что в этот момент всегда должны оцениваться как x, так и y. Теперь просто так, что выражение x+y всегда необходимо для вычисления результата функции, поэтому компилятор может хранить информацию о том, что функция add является строгой как в x, так и в y.

Сгенерированный код для add *, таким образом, ожидает целочисленные значения в качестве параметров, а не thunks. Алгоритм усложняется при рекурсии (проблема с фиксированной точкой), но основная идея остается прежней.

Другой пример:

mkList x y = 
    if x then y : []
         else []

Эта функция примет x в оценочной форме (в виде булева) и y как thunk. Выражение x должно оцениваться в каждом возможном пути выполнения через mkList, таким образом, мы можем его оценить. С другой стороны, выражение y никогда не используется в любом приложении-функции, которое является строгим в нем аргументами. Консфункция : никогда не смотрит на y, она просто сохраняет ее в списке. Таким образом, y необходимо передать как thunk, чтобы удовлетворить ленивую семантику Haskell.

mkList False undefined -- absolutely legal

*: add, конечно, является полиморфным, и точный тип x и y зависит от экземпляра.

Ответ 5

Я думаю, что остальные ответили на ваш вопрос красиво, но только для полноты позвольте мне добавить, что GHC предлагает вам возможность напрямую использовать unboxed values. Это то, что Haskell Wiki говорит об этом:

Когда вы действительно отчаянно нуждаетесь в скорости, и вы хотите перейти к "сырым битам". Для получения информации об использовании распакованных типов см. GHC Primitives.

Это должно быть последнее средство, однако, поскольку распакованные типы и примитивы не переносятся. К счастью, обычно нет необходимости прибегать к использованию явных unboxed типов и примитивов, потому что оптимизатор GHC может выполнить вашу работу, введя в действие операции, о которых он знает, и распаковывает строгие аргументы функции. Строгие и распакованные поля конструктора также могут помочь. Иногда GHC нуждается в небольшой помощи для создания правильного кода, поэтому вам, возможно, придется посмотреть на вывод Core, чтобы увидеть, действительно ли ваши настройки имеют желаемый эффект.

Одна вещь, которая может быть указана для использования unboxed типов и примитивов, заключается в том, что вы знаете, что пишете эффективный код, вместо того, чтобы полагаться на оптимизатора GHC, чтобы делать правильные вещи и быть во власти изменений в оптимизаторе GHC линия. Это может быть важно для вас, и в этом случае пойти на это.

Как уже упоминалось, он не переносится, поэтому вам нужно расширение языка GHC. См. здесь для своих документов.