Всегда ли функция в Haskell оценивает свое возвращаемое значение?
Я пытаюсь лучше понять лень Хаскелла, например, когда он оценивает аргумент функции.
Из этого источника:
Но когда звонок
constоценивается (это ситуация, которая нас интересует, здесь, в конце концов), ее возвращаемое значение также оценивается... Это хороший общий принцип: функция, очевидно, является строгой в своем возвращаемом значении, потому что когда приложение функции должно быть оцененным, он должен оценить, в теле функции, что возвращается. Исходя из этого, вы можете узнать, что должно быть оценено, посмотрев на то, от чего неизменно зависит возвращаемое значение. Ваша функция будет строгой в этих аргументах и ленивой в других.
Таким образом, функция в Haskell всегда оценивает свое собственное возвращаемое значение? Если у меня есть:
foo :: Num a => [a] -> [a]
foo [] = []
foo (_:xs) = map (* 2) xs
head (foo [1..]) -- = 4
Согласно приведенному выше абзацу, map (* 2) xs, должны быть оценены. Интуитивно я думаю, что это означает применение map ко всему списку, что приводит к бесконечному циклу. Но я могу успешно взять на себя ответственность за результат. я знаю это : в Haskell ленив, значит ли это, что map (* 2) xs просто означает создание чего-то еще, что еще не полностью оценено?
Что значит оценивать функцию, примененную к бесконечному списку? Если возвращаемое значение функции всегда вычисляется, когда функция оценивается, может ли функция когда-либо действительно возвращать thunk?
Редактировать:
bar x y = x
var = bar (product [1..]) 1
Этот код не зависает. Когда я создаю varразве он не оценивает свое тело? Или это установить bar в product [1..] а не оценить что? Если последний, bar не возвращает свое тело в WHNF, верно, так ли это на самом деле "оценить" х? Как мог bar будь строг в x если он не зависает на компьютерах product [1..]?
5 ответов
Прежде всего, Haskell не указывает, когда происходит оценка, поэтому на вопрос можно дать только определенный ответ для конкретных реализаций.
Следующее верно для всех непараллельных реализаций, о которых я знаю, таких как ghc, hbc, nhc, hugs и т. Д. (Все на основе G-машины, кстати).
Кстати, следует помнить, что когда вы слышите "оценивать" для Haskell, это обычно означает "оценивать по WHNF".
В отличие от строгих языков, вы должны различать двух "вызывающих" функций, первая - это когда вызов происходит лексически, а вторая - где запрашивается значение. Для строгого языка эти два всегда совпадают, но не для ленивого языка. Давайте возьмем ваш пример и немного усложним его:
foo [] = []
foo (_:xs) = map (* 2) xs
bar x = (foo [1..], x)
main = print (head (fst (bar 42)))
foo функция происходит в bar, Оценка bar вернет пару, и первый компонент пары - это thunk, соответствующий foo [1..], Так bar это то, что будет звонить на строгом языке, но в случае ленивого языка это не вызывает foo вообще, вместо этого это только строит закрытие.
Теперь в main функция нам на самом деле нужно значение head (fst (bar 42)) так как мы должны напечатать это. Итак head функция на самом деле будет вызвана. head Функция определяется сопоставлением с шаблоном, поэтому ей необходимо значение аргумента. Так fst называется. Это также определяется сопоставлением с образцом и нуждается в аргументе, так bar называется, и bar вернет пару, и fst оценит и вернет свой первый компонент. И вот наконец то foo называется"; и под названием я имею в виду, что блок оценивается (вводится так, как его иногда называют в терминологии TIM), потому что это значение необходимо. Единственная причина фактического кода для foo называется то, что мы хотим значение. Так foo лучше вернуть значение (т. е. WHNF). foo Функция оценит свой аргумент и попадет во вторую ветвь. Здесь он будет вызывать код для map, map Функция определяется путем сопоставления с шаблоном, и она будет оценивать свой аргумент, который является минусом. Таким образом, карта вернет следующее {(*2) y} : {map (*2) ys}где я использовал {} чтобы указать закрытие строится. Итак, как вы можете видеть map просто возвращает против клетки с головой, являющейся закрытием, и хвостом, являющимся закрытием.
Чтобы лучше понять операционную семантику Haskell, я предлагаю вам взглянуть на статью, описывающую, как перевести Haskell на некоторую абстрактную машину, такую как G-машина.
Я всегда обнаруживал, что термин "оценивать", который я выучил в других контекстах (например, программирование на Scheme), всегда приводил меня в замешательство, когда я пытался применить его к Haskell, и что я совершил прорыв, когда начал думать о Haskell с точки зрения форсирования выражений вместо их "оценки". Некоторые ключевые отличия:
- "Оценка", как я узнал ранее, сильно связывает отображение выражений со значениями, которые сами не являются выражениями. (Один общий технический термин здесь - "обозначения".)
- В Хаскеле процесс форсирования ИМХО наиболее легко понять как переписывание выражений. Вы начинаете с выражения и неоднократно переписываете его в соответствии с определенными правилами, пока не получите эквивалентное выражение, удовлетворяющее определенному свойству.
В Haskell "определенное свойство" имеет недружелюбное имя " нормальная форма слабой головы" ("WHNF"), что на самом деле означает, что выражение является либо нулевым конструктором данных, либо приложением конструктора данных.
Давайте переведем это на очень грубый набор неформальных правил. Форсировать выражение expr:
- Если
exprявляется нулевым конструктором или конструктором приложения, результатом его форсирования являетсяexprсам. (Это уже в WHNF.) - Если
exprэто приложение-функцияf argТогда результат принуждения получается так:- Найти определение
f, - Можете ли вы сопоставить это определение с выражением
arg? Если нет, то силаargи попробуйте еще раз с результатом этого. - Подставьте переменные соответствия шаблона в теле
fс частями (возможно, переписаны)argкоторые соответствуют им, и форсируют полученное выражение.
- Найти определение
Один из способов думать об этом заключается в том, что при форсировании выражения вы пытаетесь переписать его минимально, чтобы уменьшить его до эквивалентного выражения в WHNF.
Давайте применим это к вашему примеру:
foo :: Num a => [a] -> [a]
foo [] = []
foo (_:xs) = map (* 2) xs
-- We want to force this expression:
head (foo [1..])
Нам понадобятся определения для head и `карта:
head [] = undefined
head (x:_) = x
map _ [] = []
map f (x:xs) = f x : map f x
-- Not real code, but a rule we'll be using for forcing infinite ranges.
[n..] ==> n : [(n+1)..]
А сейчас:
head (foo [1..]) ==> head (map (*2) [1..]) -- using the definition of foo
==> head (map (*2) (1 : [2..])) -- using the forcing rule for [n..]
==> head (1*2 : map (*2) [2..]) -- using the definition of map
==> 1*2 -- using the definition of head
==> 2 -- using the definition of *
Я считаю, что идея должна заключаться в том, что если вы оцениваете приложение-функцию на ленивом языке, это должно быть потому, что вам нужен результат приложения для чего-то. Таким образом, независимо от причины, по которой приложение функции было сокращено, во-первых, будет необходимо уменьшать возвращаемый результат. Если бы нам не понадобился результат функции, мы бы не оценивали вызов в первую очередь, все приложение было бы оставлено в виде кода.
Ключевым моментом является то, что стандартный порядок "отложенной оценки" определяется спросом. Вы оцениваете только то, что вам нужно. Оценка большего количества рисков, нарушающих определение языковой спецификации "нестрогая семантика", а также зацикливание или сбой для некоторых программ, которые должны быть в состоянии завершиться; Ленивая оценка обладает интересным свойством, что если какой-либо порядок оценки может привести к завершению конкретной программы, то может быть и ленивая оценка.1
Но если мы оцениваем только то, что нам нужно, что означает "необходимость"? Как правило, это означает либо
- сопоставление с образцом должно знать, каким конструктором является конкретное значение (например, я не могу знать, какую ветвь использовать в вашем определении
fooне зная, является ли аргумент[]или же_:xs) - примитивная операция должна знать все значение (например, арифметические схемы в ЦП не могут добавлять или сравнивать значения; мне нужно полностью оценить два
Intзначения для вызова таких операций) - внешний драйвер, который выполняет
mainДействие ввода-вывода должно знать, что будет дальше
Скажем, у нас есть эта программа:
foo :: Num a => [a] -> [a]
foo [] = []
foo (_:xs) = map (* 2) xs
main :: IO ()
main = print (head (foo [1..]))
Выполнить mainдрайвер IO должен оценить thunk print (head (foo [1..])) выяснить, что это print применяется к Thunk head (foo [1..]), print Нужно оценить его аргумент для того, чтобы напечатать его, так что теперь нам нужно оценить этот блок.
head начинается с шаблона, соответствующего его аргументу, так что теперь нам нужно оценить foo [1..], но только для WHNF - достаточно, чтобы определить, является ли самый внешний конструктор списка [] или же :,
foo начинается с сопоставления с шаблоном по аргументу. Итак, нам нужно оценить [1..]Также только для WHNF. Это в основном 1 : [2..], что достаточно, чтобы увидеть, какую ветку принять в foo,2
: в случае если foo (с xs привязанный к толпе [2..]) оцениваю как гром map (*2) [2..],
Так foo оценивается, и не оценил его тело. Тем не менее, мы сделали это только потому, что head было сопоставление с образцом, чтобы увидеть, если бы мы имели [] или же x : _, Мы до сих пор этого не знаем, поэтому мы должны немедленно продолжить оценку результатов foo,
Это то, что означает статья, когда в ней говорится, что функции строги в своем результате. Учитывая, что призыв к foo оценивается вообще, его результат также будет оцениваться (и поэтому все, что необходимо для оценки результата, также будет оцениваться).
Но насколько это нужно оценить, зависит от вызывающего контекста. head только сопоставление с образцом по результату fooтак что для WHNF нужен только результат. Мы можем получить бесконечный список для WHNF (мы уже сделали это, с 1 : [2..]), поэтому мы не обязательно попадем в бесконечный цикл при оценке вызова foo, Но если head если бы какая-то примитивная операция, реализованная за пределами Haskell, должна была быть передана полностью оцененным списком, тогда мы будем оценивать foo [1..] полностью, и поэтому никогда не закончил бы, чтобы вернуться к head,
Итак, просто чтобы завершить мой пример, мы оцениваем map (2 *) [2..],
map шаблон соответствует своему второму аргументу, поэтому нам нужно оценить [2..] так далеко как 2 : [3..], Этого достаточно для map вернуть гром (2 *) 2 : map (2 *) [3..], который находится в WHNF. И так все готово, мы можем наконец вернуться к head,
head ((2 *) 2 : map (2 *) [3..]) не нужно проверять любую сторону :, ему просто нужно знать, что он есть, чтобы он мог вернуть левую сторону. Так что это просто возвращает неоцененный Thunk (2 *) 2,
Опять же, мы оценили только вызов head это далеко, потому что print необходимо знать, каков его результат, поэтому, хотя head не оценивает его результат, его результат всегда оценивается всякий раз, когда вызов head является.
(2 *) 2 оценивает 4, print преобразует это в строку "4" (с помощью show), и строка выводится на выход. Это был весь main IO действие, так что программа выполнена.
1 Реализации Haskell, такие как GHC, не всегда используют "стандартную ленивую оценку", и спецификация языка не требует этого. Если компилятор может доказать, что что-то всегда будет необходимо, или не может выполнить цикл / ошибку, то это безопасно оценить, даже если ленивая оценка (пока) этого не сделает. Это часто может быть быстрее, так что оптимизация GHC действительно делает это.
2 Я пропускаю несколько деталей здесь, вот так print имеет некоторую не примитивную реализацию, которую мы могли бы зайти внутрь и лениво оценить, и это [1..] может быть далее расширен до функций, которые фактически реализуют этот синтаксис.
Не обязательно. Haskell ленив, это означает, что он оценивает только тогда, когда это необходимо. Это имеет некоторые интересные эффекты. Если мы возьмем код ниже, например:
-- File: lazinessTest.hs
(>?) :: a -> b -> b
a >? b = b
main = (putStrLn "Something") >? (putStrLn "Something else")
Это вывод программы:
$ ./lazinessTest
Something else
Это указывает на то, что putStrLn "Something" никогда не оценивается. Но это все еще передается в функцию, в виде "thunk". Эти "thunks" являются неоцененными значениями, которые, вместо того, чтобы быть конкретными значениями, похожи на крошечный след того, как вычислять значение. Вот как работает лень Хаскелла.
В нашем случае два "грома" передаются >?, но только один выдается, что означает, что только один оценивается в конце. Это также относится к constгде второй аргумент может быть безопасно проигнорирован, и, следовательно, никогда не вычисляется. Что касается mapGHC достаточно умен, чтобы понять, что нас не волнует конец массива, и он беспокоится только о том, что ему нужно, в вашем случае - о втором элементе исходного списка.
Тем не менее, лучше оставить мысли о лени компилятору и продолжать кодирование, если только вы не имеете дело с IO, и в этом случае вы действительно должны думать о лени, потому что вы можете легко пойти не так, как я только что продемонстрировал,
В вики Haskell есть много и много онлайн-статей, на которые стоит посмотреть, если вы хотите получить больше подробностей.
Функция может оценить любой тип возвращаемого значения:
head (x:_) = x
или исключение / ошибка:
head _ = error "Head: List is empty!"
или снизу (⊥)
a = a
b = last [1 ..]