6.14. Шаблоны с bang и строгий Haskell

6.14.1. Шаблоны с bang

BangPatterns

Начиная с версии:

6.8.1

Статус:

Включено в GHC2024, GHC2021

Разрешает синтаксис шаблонов с bang.

GHC поддерживает расширение сопоставления с образцом, называемое шаблонами с bang и записываемое как !pat. Шаблоны с bang доступны по умолчанию как часть GHC2021.

Основная идея состоит в добавлении одной новой продукции в синтаксис шаблонов:

pat ::= !pat

Сопоставление выражения e с шаблоном !p выполняется так: сначала вычисляется e (до WHNF), а затем результат сопоставляется с p. Пример:

f1 !x = True

Это определение делает f1 строгой относительно x, тогда как без bang оно было бы ленивым.

Обратите внимание на следующие моменты:

• Шаблоны с bang можно вкладывать друг в друга:

  f2 (!x, y) = [x,y]
  

  Здесь f2 строгая относительно x, но не относительно y.

• Шаблоны с bang можно использовать и в выражениях case:

  g1 x = let y = f x in body
  g2 x = case f x of { y -> body }
  g3 x = case f x of { !y -> body }
  

  Функции g1 и g2 означают одно и то же. Но g3 вычисляет (f x), связывает y с результатом, а затем вычисляет body.

• Шаблоны с bang не оказывают никакого эффекта при использовании с шаблонами-конструкторами:

  f3 !(x,y) = [x,y]
  f4 (x,y)  = [x,y]
  

  Здесь f3 и f4 идентичны: добавление bang перед шаблоном, который и так принудительно вычисляется, ничего не меняет. Однако см. оговорку ниже.

• Существует проблема синтаксической неоднозначности. Рассмотрим:

  f !x = 3
  

  Это определение инфиксной функции «(!)» или «f» с шаблоном с bang? GHC разрешает эту неоднозначность, учитывая окружающие пробелы:

  a ! b = ...   -- infix operator
  a !b = ...    -- bang pattern
  

  Точные правила см. в предложении GHC № 229.

let !x = e in body
let !(p,q) = e in body

6.14.2. Типы данных, строгие по умолчанию

StrictData

Начиная с версии:

8.0.1

По умолчанию делает строгими поля типов данных, определённых в текущем модуле.

В общих чертах языковое расширение StrictData делает объявления типов данных строгими по умолчанию, позволяя задавать ленивые поля, добавляя перед полем ~.

Когда пользователь пишет

data T = C a
data T' = C' ~a

мы интерпретируем это так, как если бы он написал

data T = C !a
data T' = C' a

Расширение влияет только на определения в этом модуле.

Аннотацию ~ необходимо записывать в префиксной форме:

data T = MkT ~Int   -- valid
data T = MkT ~ Int  -- invalid

Точные правила см. в предложении GHC № 229.

6.14.3. Связывания с образцом, строгие по умолчанию

Strict

Подразумевает:

StrictData

Начиная с версии:

8.0.1

По умолчанию делает строгими связывания в текущем модуле.

В общих чертах языковое расширение Strict делает функции, типы данных и связывания строгими по умолчанию, позволяя задавать необязательную ленивость, добавляя перед переменной ~. По сути, это меняет существующую ситуацию на противоположную: сейчас по умолчанию используется ленивость, а строгость можно включить, добавив перед переменной !.

Strict подразумевает StrictData.

• Определения функций

  Когда пользователь пишет

  f x = ...
  

  мы интерпретируем это так, как если бы он написал

  f !x = ...
  

  Добавление ~ перед x обеспечивает обычное ленивое поведение.

  Чтобы превратить шаблоны в неопровержимые, при включённом Strict требуется ~(~p).

• Связывания let/where

  Когда пользователь пишет

  let x = ...
  let pat = ...
  

  мы интерпретируем это так, как если бы он написал

  let !x = ...
  let !pat = ...
  

  Добавление ~ перед x обеспечивает обычное ленивое поведение. Общее правило состоит в том, что мы добавляем неявный bang к самому внешнему шаблону, если это не отключено с помощью ~.

• Сопоставление с образцом в выражениях case, лямбдах, do-нотации и т. д.

  Самый внешний шаблон всех сопоставлений с образцом получает неявный bang, если это не отключено с помощью ~. Это относится к выражениям case, шаблонам в лямбдах, do-нотации, списковым включениям и так далее. Например:

  case x of (a,b) -> rhs
  

  интерпретируется как

  case x of !(a,b) -> rhs
  

  Поскольку семантика сопоставления с образцом в выражениях case строгая, обычно это совершенно ничего не меняет. Однако разница есть в вырожденном случае переменных и newtype. Так что

  case x of y -> rhs
  

  в Haskell является ленивым, но с Strict интерпретируется как

  case x of !y -> rhs
  

  что вычисляет x. Аналогично, если newtype Age = MkAge Int, то

  case x of MkAge i -> rhs
  

  в Haskell является ленивым, но с Strict добавленный bang делает его строгим.

  Аналогично

  \ x -> body
  do { x <- rhs; blah }
  [ e | x <- rhs; blah }
  

  все получают неявные bang на шаблоне x.

• Вложенные шаблоны

  Обратите внимание, что мы не добавляем bang к вложенным шаблонам. Например:

  let (p,q) = if flob then (undefined, undefined) else (True, False)
  in ...
  

  будет вести себя как

  let !(p,q) = if flob then (undefined, undefined) else (True,False)
  in ...
  

  это строго вычислит правую часть и свяжет p и q с компонентами пары. Но сама пара остаётся ленивой (если только мы также не компилируем Prelude с Strict; см. ниже раздел Модульность). Поэтому p и q могут оказаться связаны с неопределённым значением. См. также раздел Динамическая семантика шаблонов с bang ниже.

• Связывания верхнего уровня

  не затрагиваются расширением Strict. Например:

  x = factorial 20
  (y,z) = if x > 10 then True else False
  

  Здесь x и связывание с образцом (y,z) остаются ленивыми. Причина в том, что подходящего момента для их принудительного вычисления нет до первого использования.

• Newtype

  На newtype это не влияет: они лишь переименовывают существующие типы. Например:

  newtype T = C a
  f (C x)  = rhs1
  g !(C x) = rhs2
  

  В обычном Haskell f является ленивым относительно своего аргумента, а значит, и относительно x; а g является строгим относительно своего аргумента, а значит, также строгим относительно x. С Strict оба становятся строгими, потому что аргумент f получает неявный bang.

6.14.4. Модульность

Strict и StrictData влияют только на определения в модуле, где они используются. Функции и типы данных, импортированные из других модулей, не затрагиваются. Например, мы не будем вычислять аргумент Just до применения конструктора. Аналогично, мы не будем вычислять первый аргумент Data.Map.findWithDefault до применения функции.

Это крайне важно для сохранения корректности. Сущности, определённые в других модулях, могут полагаться на ленивость для обеспечения корректности (функциональной или производительной).

Кортежи, списки, Maybe и все остальные типы из Prelude сохраняют существующую ленивую семантику.

6.14.5. Динамическая семантика шаблонов с bang

Семантика сопоставления с образцом в Haskell описана в разделе 3.17.2 отчёта Haskell. Добавьте к этому описанию ещё один пункт 9:

• Сопоставление шаблона !pat со значением v выполняется следующим образом:

  • если v равно bottom, сопоставление расходится
  • иначе pat сопоставляется с v

Аналогично, на рисунке 4 из раздела 3.17.3 добавьте новый случай (w):

case v of { !pat -> e; _ -> e' }
   = v `seq` case v of { pat -> e; _ -> e' }

Остаются выражения let, преобразование которых описано в разделе 3.12 отчёта Haskell. Замените приведённое там «Преобразование» следующим. Пусть дано let { bind1 ... bindn } in body:

v = case e of { p -> (x1, ..., xn) }
x1 = case v of { (x1, ..., xn) -> x1 }
...
xn = case v of { (x1, ..., xn) -> xn }``

let !x = e in body  ==>   let x = e in x `seq` body

В результате получится (возможно) рекурсивный набор связываний, где слева связываются только простые переменные. (Можно пойти ещё дальше, как в отчёте Haskell, и сделать рекурсивные связывания нерекурсивными с помощью fix, но мы не делаем этого в Core, поскольку это только затуманивает суть, и здесь поступать так тоже не будем.)

Преобразование тщательно продумано, чтобы шаблоны с bang имели смысл как для рекурсивных и полиморфных связываний, так и для простых нерекурсивных связываний.

Вот несколько примеров работы этого преобразования. Первое выражение в каждой последовательности — исходный код на Haskell, остальные — Core.

Простой нерекурсивный случай:

let x :: Int     -- Non-recursive
    !x = factorial y
in body

===> (SPLIT-STRICT)
     let x = factorial y in x `seq` body

===> (inline seq)
     let x = factorial y in case x of !x -> body

===> (inline x)
     case factorial y of !x -> body

То же самое, но со связыванием с образцом:

let !(Just x) = e in body

===> (SPLIT-STRICT)
     let v = case e of !(Just x) -> Solo x
         Solo x = v
     in v `seq` body

===> (SPLIT-LAZY, drop redundant bang)
     let v = case e of Just x -> Solo x
         x = case v of Solo x -> x
     in v `seq` body

===> (inline seq, float x,y bindings inwards)
     let v = case e of Just x -> Solo x
     in case v of !v -> let x = case v of Solo x -> x
                        in body

===> (fluff up v's pattern; this is a standard Core optimisation)
     let v = case e of Just x -> Solo x
     in case v of v@(Solo p) -> let x = case v of Solo x -> x
                                in body

===> (case of known constructor)
     let v = case e of Just x -> Solo x
     in case v of v@(Solo p) -> let x = p
                                in body

===> (inline x, v)
     case (case e of Just x -> Solo x) of
        Solo p -> body[p/x]

===> (case of case)
     case e of Just x -> body[p/x]

Итоговая форма — именно то, что нужно: простое выражение case. Важно отметить, что шаблон Just x принудительно сопоставляется сразу, но x само по себе не вычисляется, пока этого не сделает body. Также обратите внимание, что в этом примере используется шаблон, связывающий ровно одну переменную, и показано применение кортежа из одного элемента Solo.

Правило (SPLIT-STRICT) применяется, даже если шаблон не связывает ни одной переменной:

let !(True,False) = e in body

===> (SPLIT-STRICT)
     let v = case e of !(True,False) -> (); () = v in v `seq` body

===> (inline, simplify, drop redundant bang)
     case e of (True,False) -> body

То есть мы принудительно вычисляем e и проверяем, что оно имеет правильную форму, прежде чем продолжить вычисление body. Это происходит, даже если сам шаблон ничего не связывает:

let !_ = e in body

===> (SPLIT-STRICT)
     let v = case e of !_ -> (); () = v in v `seq` body

===> (inline, simplify)
     case e of !_ -> body

И снова e принудительно вычисляется до вычисления body. Именно поэтому (наряду с !x = e) правило (SPLIT-STRICT) использует шаблон с bang в case в десахаризованной правой части.

Обратите внимание: правило (CASE) применяется, только если какая-либо из связанных переменных имеет неподнятый тип; неважно, имеет ли неподнятый тип само связывание (см. предложение GHC № 35). Например (см. Типы без указателя и примитивные операции):

let (# a::Int, b::Bool #) = e in body
===> (SPLIT-LAZY)
    let v = case e of (# a,b #) -> (a,b)
        a = case v of (a,b) -> a
        b = case v of (a,b) -> b
    in body

Хотя шаблон кортежа не имеет указателя, сопоставление с ним выполняется только при вычислении a или b в body.

Пример с типом данных без указателя:

type T :: UnliftedType
data T = MkT Int
f1 x = let MkT y  = blah in body1
f2 x = let z :: T = blah in body2
f3 x = let _ :: T = blah in body3

В f1, хотя T имеет тип без указателя, шаблон MkT y связывает переменную y с типом с указателем, поэтому применяется (SPLIT-LAZY), и blah не вычисляется, пока body1 не вычислит y. Напротив, в f2 шаблон z :: T связывает переменную z с типом без указателя, поэтому применяется (CASE), и связывание let является строгим. В f3 шаблон не связывает переменных, поэтому связывание снова ленивое, как и f1.

Рекурсивный случай:

letrec xs :: [Int]  -- Recursive
        !xs = factorial y : xs
in body

===> (SPLIT-STRICT)
     letrec xs = factorial y : xs in xs `seq` body

===> (inline seq)
     letrec xs = factorial y : xs in case xs of xs -> body

===> (eliminate case of value)
     letrec xs = factorial y : xs in body

и полиморфный случай:

let f :: forall a. [a] -> [a]    -- Polymorphic
    !f = fst (reverse, True)
in body

===> (SPLIT-STRICT)
     let f = /\a. fst (reverse a, True) in f `seq` body

===> (inline seq, inline f)
     case (/\a. fst (reverse a, True)) of !f -> body

Обратите внимание, что seq добавляется только при преобразовании в Core. Если бы мы сделали это в исходном коде Haskell, то есть написали

let f = ... in f `seq` body

полиморфный тип f был бы конкретизирован, поэтому преобразование в Core выглядело бы так:

let f = ... in f Any `seq` body

При перегрузке результат может оказаться несколько неожиданным:

let f :: forall a. Eq a => a -> [a] -> Bool    -- Overloaded
    !f = fst (member, True)
in body

===> (SPLIT-STRICT)
     let f = /\a \(d::Eq a). fst (member, True) in f `seq` body

===> (inline seq, case of value)
     let f = /\a \(d::Eq a). fst (member, True) in body

Обратите внимание, что в этом случае bang вообще не оказывает никакого эффекта.