Haskellの文字列リテラルはGHCでどのようにコンパイルされるか

# Haskellの文字列とは

まず、Haskell標準の文字型・文字列型が何であるかを確認しておきます。

Haskell 2010では `Char` 型はUnicode characterを表す、とされています。

* [Haskell 2010 Language Report -- 6.1.2 Characters and Strings](https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1190006.1.2)

「文字」というのが非自明な概念であることを知っている方であればUnicode **character**って具体的にはなんやねん！と言いたくなるかと思いますが、GHCにおいては `Char` 型は**Unicodeコードポイント**を表します。つまり、

* 0 以上 0x10FFFF 以下の整数

です。特に、サロゲートコードポイント（0xD800 以上 0xDFFF 以下）も有効な `Char` 型の値です。

* [GHC の Char 型の説明](https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html#t:Char)

`String` は `Char` のリストです。

これらの定義を擬似コードで書けば次のようになります。

```haskell
data Char = '\0' | '\1' | ... | '\x10FFFF'
type String = [Char]
```

ダブルクォートで囲まれた文字列リテラルは、文字のリストのシンタックスシュガーです。

```haskell
-- 文字列リテラルの脱糖
"hello" = ['h','e','l','l','o']
        = 'h':'e':'l':'l':'o':[]
```

# OverloadedStrings拡張とIsStringクラス

Haskellのリストは連結リストとして表現され、また、要素はボックス化されて格納されるため、決して効率の良いものではありません。具体的には、 `String` 型で表される文字列は1文字あたり5ワード（64ビット環境なら40バイト）消費します。

簡単なプログラムならそれでも良いかもしれませんが、本格的なアプリケーションを書く際にはこの効率の悪さは無視できない問題です。

そこで、本格的なHaskellプログラムでは `String` の代わりに `ByteString` や `Text` などの効率の良い文字列型が使用されます。

しかし、Haskellの文字列リテラルの型はあくまで `String` ですから、 `ByteString` や `Text` のリテラルが欲しかったら変換関数をかませる必要があります。

```haskell
import qualified Data.ByteString.Char8 as BS
import Data.Text as T
BS.pack "hello" -- ByteString型
T.pack "hello" -- Text型
```

`String` を経由するのはともかく、 `pack` のような関数呼び出しをいちいち書くのは面倒です。

この問題を解決するのが `OverloadedStrings` 拡張です。この拡張を有効にすると、文字列リテラルの方が `String` という具体的な型から `IsString` クラスの任意のインスタンスという風に一般化されます。（`IsString` クラスは [Data.String](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-String.html) モジュールで定義されていますが、自分で文字列型を定義するのでもない限り Data.String を import する必要はないでしょう。）

```haskell:Data.String
class IsString a where
  fromString :: String -> a
```

```haskell
-- OverloadeStrings 拡張の下での文字列リテラルの脱糖
"hello" = Data.String.fromString ['h','e','l','l','o']
```

## 注意：ByteStringとOverloadedStrings

`OverloadedStrings` 拡張の下で `ByteString` のリテラルを書く際は要注意です。

`ByteString` に対する `IsString` のインスタンスは `fromString = pack` という風に定義されています。

ASCII文字列ならば問題ないのですが、ASCII範囲外の文字に対しては `pack` は**Unicodeコードポイントの下位8ビットを取り出す**という挙動をします。**UTF-8でエンコードするような気の利いたことはしてくれない**ので注意してください。

```haskell:GHCi
λ> "猫" :: BS.ByteString
"+"
λ> "にゃーん" :: BS.ByteString
"k\131\252\147"
```

ちなみに `Data.ByteString.Builder` の `Builder` 型の `IsString` インスタンスはUTF-8でエンコードするように定義されているようです。統一感がない……。

関連Issue:

* [Surprising behavior of ByteString literals via IsString · Issue #140 · haskell/bytestring](https://github.com/haskell/bytestring/issues/140)

# より低レベルへ

ここまではHaskellをある程度やっている人なら誰でも知っている（べき）事柄です。ここからはGHC User's Guideにすらまともに書かれていない深みへ降りていきます。

このセクションの内容はGHC 8.8時点での話です。GHC 8.10でもそんなに変化はないと思います。将来のバージョンでは変わるかもしれません（GHC 9.0での変化は追記済みです）。

## primitive string literal または unboxed string literal または `Addr#` literal

`MagicHash` 拡張を使うと、識別子の末尾に `#` を使えるようになるほか、各種unboxed型のリテラルが使えるようになります。 `0#` は `Int#` 型、 `0##` は `Word#` 型、 `0.0##` は `Double#` 型、という感じです。

* [9.3.2. The magic hash](https://downloads.haskell.org/~ghc/8.10.1/docs/html/users_guide/glasgow_exts.html#the-magic-hash)

この中に、文字列リテラルの後ろに `#` をつけた `Addr#` 型のリテラルというものがあります。GHC 8.10.1時点のUser's Guideでは `"foo"#` という例しか載っていません。

これの呼び名は何種類かあるようで、GHC本体のソースをgrepしただけでも primitive string literal, unboxed string literal, `Addr#` literal という呼び名が確認されます。

（`Addr#` 型というのは `Ptr a` に対応するunboxed型です。）

この「生文字列リテラル」みたいなやつは、端的に言うと**バイト列のリテラル**です。

実際、1バイトに収まらない文字が含まれているとエラーとなります。UTF-8等でエンコードされるようなことはありません。0x80以上0xFF以下の値はそのまま埋め込まれます。

```haskell:GHCi
λ> :set -XMagicHash
λ> :t "hello"#
"hello"# :: ghc-prim-0.5.3:GHC.Prim.Addr#
λ> :t "\xA8"#
"\xA8"# :: ghc-prim-0.5.3:GHC.Prim.Addr#
λ> :t "にゃーん"#

<interactive>:1:1: error:
    primitive string literal must contain only characters <= '\xFF'
```

`Addr#` リテラルはCの文字列と同様にメモリ上の連続した領域に配置され、暗黙に NUL で終端されます（`ghc -S` でアセンブリを出力させると `.asciz` が使用されます）。

## 通常の文字列リテラルとprimitive string literalとの関係

最初の方に

```haskell
-- 文字列リテラルの脱糖
"hello" = ['h','e','l','l','o']
        = 'h':'e':'l':'l':'o':[]
```

と書きました。これは意味的には正しいのですが、GHCの実装上は異なります。つまり、文字列リテラルと `Char` を要素とするリストのリテラルでは、生成されるアセンブリコードが異なります。

試しにこういうコードをコンパイルしてみましょう。

```haskell:Foo.hs
module Foo where

hello :: String
hello = "hello"

hello2 :: String
hello2 = ['h','e','l','l','o']

world :: String
world = "世界"

foo :: String
foo = "f\0o"
```

`ghc -fforce-recomp -ddump-prep Foo.hs` みたいな感じでCoreを出力させると、

```haskell
-- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0}
Foo.hello :: GHC.Base.String
[GblId]
Foo.hello = GHC.CString.unpackCString# "hello"#

-- ...hello2用の補助的な定義は割愛...

-- RHS size: {terms: 3, types: 1, coercions: 0, joins: 0/0}
Foo.hello2 :: GHC.Base.String
[GblId, Caf=NoCafRefs, Unf=OtherCon []]
Foo.hello2 = GHC.Types.: @ GHC.Types.Char hello1_rXL hello10_rYm

-- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0}
Foo.world :: GHC.Base.String
[GblId]
Foo.world
  = GHC.CString.unpackCStringUtf8# "\\228\\184\\150\\231\\149\\140"#

-- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0}
Foo.foo :: GHC.Base.String
[GblId]
Foo.foo = GHC.CString.unpackCStringUtf8# "f\\192\\128o"#
```

となりました。 `Foo.hello` と `Foo.hello2` の定義がまるっきり違うのがわかります。文字列リテラルを使った方は `GHC.CString.unpackCString#` と `Addr#` リテラルの組み合わせとしてコンパイルされました（`Addr#` リテラル中のバックスラッシュがなんか多い気がします。Coreのpretty printerのバグかもしれません）。

`GHC.CString.unpackCString#` はNUL終端されたバイト列を `String` に変換する関数です。ghc-primパッケージの [GHC.CString](https://hackage.haskell.org/package/ghc-prim-0.5.3/docs/GHC-CString.html) で定義されています。

NULを含まないASCII文字列の場合はそれで良いのですが、 `Addr#` リテラルにはバイト列しか入らないので、Unicode文字列の場合（またはNULを含むASCII文字列の場合）は何らかの方法でエンコード・デコードする必要があります。

GHCではUnicode文字列をUTF-8エンコードすることによって `Addr#` リテラルにコンパイルし、実行時には `unpackCStringUtf8#` によってそれをデコードするようにしています。文字列リテラルに U+0080 以上のコードポイントが含まれる場合は、たとえ1バイト (Latin-1) に収まる場合でもUTF-8エンコードされます。

（この際のエンコード方法は厳密にはUTF-8と呼ぶべきではなくて、UTF-8としては不正なバイト列としてエンコードされる場合があります。NULは `\xC0\x80` に変換されます。また、サロゲートコードポイントもUTF-8と同じようにエンコードされます。まあ、デコードの際にUTF-8のエラーチェックを省けば期待通りのものが得られると言うことです。）

まとめると、先ほどの `Foo.hs` は次のように脱糖されるということです：

```haskell
{-# LANGUAGE MagicHash #-}
module Foo where
import GHC.CString

hello :: String
hello = unpackCString# "hello"#

-- hello2 : 省略

world :: String
world = unpackCStringUtf8# "\xE8\xB8\x96\xE7\x95\x8C"# -- "世界" (UTF-8 encoded)

foo :: String
foo = unpackCStringUtf8# "f\xC0\x80o"# -- "f\0o"
```

## オーバーロードされた文字列リテラルの効率

`OverloadedStrings` の先ほどの説明では、文字列は一旦 `String` を経由して目的の文字列型（`ByteString` や `Text`）に変換されるのでした。

しかし、直前に述べたような文字列リテラルの脱糖のことを知っていると、 `String` を経由せずに直接バイト列から目的の文字列型に変換することができます。

つまり、自作の文字列型 `SugoiString` について次のように `IsString` のインスタンスを用意したとすると、

```haskell
data SugoiString = ...

instance IsString SugoiString where
  fromString = pack
  -- 後からrewrite ruleを定義する関係上、クラスメソッドと実際の処理を行う関数は分けます

pack :: String -> SugoiString
pack s = ... -- String から SugoiString を構築する
```

次のようなrewrite rulesを書くことによって、効率の悪い`String` を避けて、メモリ上に連続したバイト列から直接目的の文字列を構築できます。

```haskell
{-# INLINE [0] pack #-} -- または NOINLINE

packAddr :: Addr# -> SugoiString
packAddr addr = ... -- NUL終端されたASCII文字列から SugoiString を構築する

packAddrUtf8 :: Addr# -> SugoiString
packAddrUtf8 addr = ... -- NUL終端されたUTF-8文字列から SugoiString を構築する

{-# RULES
"SugoiString pack/unpackCString" forall s.
  pack (GHC.CString.unpackCString# s) = packAddr s
"SugoiString pack/unpackCStringUtf8" forall s.
  pack (GHC.CString.unpackCStringUtf8# s) = packAddrUtf8 s
  #-}
```

`ByteString` や `Text` に関しては実際にこのようなrewrite ruleが定義されていて、 `String` を経由せずに文字列リテラルを構築できるようになっています。

ByteStringの場合は `Addr#` から直接 `ByteString` を構築する関数として

* [Data.ByteString.Unsafe.unsafePackAddress](https://hackage.haskell.org/package/bytestring-0.10.10.0/docs/Data-ByteString-Unsafe.html#v:unsafePackAddress) (bytestring-0.10.\*.\* まで)
* [Data.ByteString.Internal.unsafePackLiteral](https://hackage.haskell.org/package/bytestring-0.11.0.0/docs/Data-ByteString-Internal.html#v:unsafePackLiteral) (bytestring-0.11.0.0 以降)

が使用されるようです（この関数に関するrewrite ruleはNULを含む文字列や非ASCII文字列には発動しません）。

なお、GHC 9.0 では `GHC.CString.cStringLength#` という関数で `Addr#` リテラルの長さをコンパイル時に計算される定数として取得できるようになりました。bytestring-0.11.0.0 以降ではそれを使うようになっています。

ちなみに、GHC 9.0 と bytestring-0.11.0.0 の組み合わせでは文字列リテラルから `ByteString` を構築する際に内容をコピーしなくて済むようになっています。

# おことわり

この記事の内容（の後半）は将来のGHCバージョンでは変わる可能性があります。この辺の話に興味がある人は以下のGHC ProposalsとGHC Issuesをウォッチしておくと良いでしょう。

* GHC Proposals
    * [ByteArray Literals](https://github.com/ghc-proposals/ghc-proposals/pull/292)
* GHC Issues
    * [#17474 Behavior of Addr# literals is not documented in the user manual](https://gitlab.haskell.org/ghc/ghc/issues/17474)
    * [#5218 Add unpackCStringLen# to create Strings from string literals](https://gitlab.haskell.org/ghc/ghc/issues/5218)