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

Question

Как выглядят thunks для следующего значения / выражения / функции в куче Haskell?

val = 5                -- is `val` a pointer to a box containing 5?
add x y = x + y        
result = add 2 val     
main = print $ result

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

Answer 1

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

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

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

Да.

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

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

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

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

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

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

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

Answer 2

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

bottom :: Int
bottom = div 1 0

Это определение будет генерировать исключение деления на ноль только , если проверяется значение bottom, но не, если значение никогда не используется.

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

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.Затем упаковка и распаковка переводятся как приложение-конструктор и сопоставление с образцом.

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

Answer 3

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

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

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

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

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

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

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

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

mkList False undefined -- absolutely legal

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

Answer 4

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

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

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 (он же пустой), что означает, что написание такой функции не будет работать, потому что у него не будет возможности вернуть 0, если дан пустой список,хотя это то, что мы хотели бы в этом случае.

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

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

Answer 5

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

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

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

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

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