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

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

Шаблоны bang (BangPatterns) делают сопоставление с образцом и связи let более строгими.
Строгие типы данных (StrictData) по умолчанию делают поля конструкторов строгими для каждого модуля.
Строгий шаблон (Strict) делает все шаблоны и связи let строгими по умолчанию для каждого модуля.

Последние два расширения просто позволяют избежать заполнения высокопроизводительного кода шаблонами bang, что затрудняет его чтение.

Шаблоны bang и строгое соответствие никоим образом не влияют на систему типов.

6.14.1. Шаблоны bang

BangPatterns

Since:: 6.8.1
Status:: Включено в GHC2024, GHC2021

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

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

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

pat ::= !pat

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

6.14.1.1. Строгие связи

Расширение BangPatterns дополнительно включает синтаксис для строгих let или where связей с !pat = expr. Например,

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

В обоих случаях e оценивается до начала оценки body.

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

Строгая связь (с верхнеуровневым !) не следует рассматривать как обычную связь по образцу, которая случайно имеет шаблон bang (Шаблоны bang) в левой части. Скорее, верхнеуровневый ! следует рассматривать как часть связи let, а не как часть шаблона. Это имеет значение, когда мы переходим к правилам в Динамическая семантика шаблонов bang.
Только верхнеуровневый bang (возможно, в скобках) делает связь строгой; в противном случае она считается обычным шаблоном bang. Например,
```
let (!x,[y]) = e in b
```
эквивалентно этому:
```
let { t = case e of (x,[y]) -> x `seq` (x,y)
      x = fst t
      y = snd t }
in b
```
Связь ленивая, но при оценке x или y посредством b весь шаблон сопоставляется, включая принудительную оценку x.
Поскольку ! в строгой связи не является шаблоном bang, оно должно быть видно без прохождения через синонимы шаблонов
```
pattern Bang x <- !x
f1 = let Bang x = y in ...
f2 = let !x     = y in ...  -- not equivalent to f1
```
Строгие связи не допускаются на верхнем уровне модуля.
См. Семантика связей let с шаблонами bang для подробной семантики и описание функции в Haskell prime для более подробных обсуждений и примеров.

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

StrictData

Since:: 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 даёт стандартное ленивое поведение.

Преобразование шаблонов в безусловные требует ~(~p) при включенном Strict.
Связывания let/where

Когда пользователь пишет
```
let x = ...
let pat = ...
```
мы интерпретируем это так, как будто он написал
```
let !x = ...
let !pat = ...
```
Добавление ~ перед x даёт стандартное ленивое поведение. Общее правило состоит в том, что мы добавляем неявный знак ! к самому внешнему шаблону, если это не отключено с помощью ~.
Сопоставление шаблонов в выражениях case, лямбдах, do-нотации и т.д.

Наиболее внешний шаблон всех сопоставлений шаблонов получает неявный знак !, если это не отключено с помощью ~. Это относится к выражениям 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 добавленный знак ! делает её строгой.

Аналогично
```
\ x -> body
do { x <- rhs; blah }
[ e | x <- rhs; blah }
```
все получают неявные знаки ! на x шаблоне.
Вложенные шаблоны

Обратите внимание, что мы не добавляем знаки ! к вложенным шаблонам. Например,
```
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 могут оказаться привязанными к неопределённому значению. См. также Динамическая семантика шаблонов с ! ниже.
Связывания верхнего уровня

не затронуты 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 получает неявный знак !.

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

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

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

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

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

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

Сопоставление шаблона !pat со значением v происходит следующим образом:
- если v является неопределённым значением, сопоставление расходится
- в противном случае, 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:

SPLIT-LAZY

Дано ленивое связывание шаблона p = e, где p не является переменной, а x1...xn — переменные, связанные p, и все эти связывания имеют поднятый тип, замените связывание на следующее (где v — новая переменная):

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

Если n=1 (т.е. связана ровно одна переменная), десугаринг использует тип Solo для создания 1-кортежа.

SPLIT-STRICT

Дано жёсткое связывание шаблона !p = e, где x1...xn — переменные, связанные p, и все эти связывания имеют поднятый тип:

Замените связывание на следующее (где v — новая переменная):
```
v = case e of { !p -> (x1, ..., xn) }
(x1, ..., xn) = v
```
Замените body на v `seq` body.

Как и в SPLIT-LAZY, если n=1, десугаринг использует тип Solo для создания 1-кортежа.

Это преобразование запрещено на верхнем уровне модуля (поскольку нет body), поэтому жёсткие связывания запрещены на верхнем уровне.

Преобразование верно, когда p — переменная x, но может быть оптимизировано до:

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

CASE

Дано нерекурсивное жёсткое связывание шаблона !p = e, где x1...xn — переменные, связанные p, и у одного из связываний неподнятый тип: замените связывание пустым, а body на case e of p -> body.

Это преобразование запрещено на верхнем уровне модуля, поэтому такие связывания отклоняются.

Результат этого преобразования будет иметь ошибки области видимости, если любая из переменных x1...xn встречается в e; поэтому это ограничение для нерекурсивных связываний шаблонов.

Точно такое же преобразование применяется к нерекурсивному ленивому связыванию шаблона (т.е. без ! на верхнем уровне), которое связывает какие-либо переменные с неподнятым типом; но такое связывание выводит предупреждение -Wunbanged-strict-patterns. Предупреждение побуждает программиста сделать видимым тот факт, что это связывание обязательно жёсткое.

Результатом будет (возможно) рекурсивный набор связываний, связывающий только простые переменные слева. (Можно пойти ещё дальше, как в отчёте 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 1-кортежа.

Правило (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 в этом случае никак не влияет

© 2002–2007 The University Court of the University of Glasgow. All rights reserved.
Licensed under the Glasgow Haskell Compiler License.
https://downloads.haskell.org/~ghc/9.12.1/docs/users_guide/exts/strict.html