Haskells Weak Head Нормальная форма - PullRequest
Новая
       36

Haskells Weak Head Нормальная форма

9 голосов
/ 04 февраля 2020

Я наткнулся на некоторые раздражающие вещи. Я знаю, что haskell работает со слабой головой нормальной формы (WHNF), и я знаю, что это такое. Вводим следующий код в ghci (я использую команду: sprint, которая, насколько мне известно, сокращает выражение до WHNF.): 

let intlist = [[1,2],[2,3]]
:sprint intlist

дает intlist = _, это абсолютно логично для меня. 

let stringlist = ["hi","there"]
:sprint stringlist

дает stringlist = [_,_] Это меня уже смущает. Но тогда: 

let charlist = [['h','i'], ['t','h','e','r','e']]
:sprint charlist

неожиданно дает charlist = ["hi","there"]

Насколько я понял Haskell, строки - это не что иное, как списки символов, что, кажется, подтверждается проверкой типов "hi" :: [Char] и ['h','i'] :: [Char].

Я в замешательстве, потому что в моем понимании все три приведенных выше примера более или менее одинаковы (список списков) и поэтому должны сводиться к одной и той же WHNF, а именно _. Что мне не хватает?

Спасибо

1 Ответ

5 голосов
/ 04 февраля 2020

Обратите внимание, что :sprint делает не сокращением выражения до WHNF. Если это так, то следующее даст 4 вместо _: 

Prelude> let four = 2 + 2 :: Int
Prelude> :sprint four
four = _

Скорее, :sprint берет имя привязки, обходит внутреннее представление значения привязки и показывает уже «вычисленные части» (то есть части, которые являются конструкторами) при использовании _ в качестве заполнителя для неоцененных блоков (т. е. приостановленных вызовов ленивых функций). Если значение полностью не оценено, оценка не будет выполнена, даже для WHNF. (И если значение будет полностью оценено, вы получите это, а не только WHNF.)

То, что вы наблюдаете в своих экспериментах, является комбинацией полиморфизма c против мономорфи c цифра c типы, различные внутренние представления строковых литералов и явные списки символов и т. д. c. По сути, вы наблюдаете технические различия в том, как различные литеральные выражения компилируются в байт-код. Таким образом, интерпретация этих деталей реализации как имеющих отношение к WHNF может безнадежно запутать вас. Как правило, вы должны использовать :sprint только как инструмент отладки, а не как способ узнать о WHNF и семантике Haskell оценки.

Если вы действительно хотите понять, что делает :sprint, Вы можете включить несколько флагов в GHCi, чтобы увидеть, как на самом деле обрабатываются выражения и, таким образом, в конечном итоге скомпилированы в байт-код: 

> :set -ddump-simpl -dsuppress-all -dsuppress-uniques

После этого мы можем увидеть причину, по которой ваш intlist дает _: 

> let intlist = [[1,2],[2,3]]
==================== Simplified expression ====================
returnIO
  (: ((\ @ a $dNum ->
         : (: (fromInteger $dNum 1) (: (fromInteger $dNum 2) []))
           (: (: (fromInteger $dNum 2) (: (fromInteger $dNum 3) [])) []))
      `cast` <Co:10>)
     [])

Вы можете игнорировать returnIO и внешний вызов : и сосредоточиться на части, которая начинается с ((\ @ a $dNum -> ...

Здесь $dNum - словарь для ограничения Num. Это означает, что сгенерированный код еще не разрешил фактический тип a в типе Num a => [[a]], поэтому все выражение все еще представляется как вызов функции, принимающей (словарь для) соответствующий тип Num. Другими словами, это неоцененный thunk, и мы получаем: 

> :sprint intlist
_

С другой стороны, укажите тип как Int, и код будет совершенно другим: 

> let intlist = [[1::Int,2],[2,3]]
==================== Simplified expression ====================
returnIO
  (: ((: (: (I# 1#) (: (I# 2#) []))
         (: (: (I# 2#) (: (I# 3#) [])) []))
      `cast` <Co:6>)
     [])

и вывод :sprint: 

> :sprint intlist
intlist = [[1,2],[2,3]]

Аналогично, буквенные строки и явные списки символов имеют совершенно разные представления: 

> let stringlist = ["hi", "there"]
==================== Simplified expression ====================
returnIO
  (: ((: (unpackCString# "hi"#) (: (unpackCString# "there"#) []))
      `cast` <Co:6>)
     [])

> let charlist = [['h','i'], ['t','h','e','r','e']]
==================== Simplified expression ====================
returnIO
  (: ((: (: (C# 'h'#) (: (C# 'i'#) []))
         (: (: (C# 't'#)
               (: (C# 'h'#) (: (C# 'e'#) (: (C# 'r'#) (: (C# 'e'#) [])))))
            []))
      `cast` <Co:6>)
     [])

и различия в :sprint output представляет артефакты, которые часть выражения GHCi считает оцененными (явные : конструкторы) по сравнению с неоцененными (unpackCString# thunks).

...