33
16

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-03-25

Haskellの文字列とは

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

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

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

  • 0 以上 0x10FFFF 以下の整数

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

StringChar のリストです。

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

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

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

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

OverloadedStrings拡張とIsStringクラス

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

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

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

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

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 モジュールで定義されていますが、自分で文字列型を定義するのでもない限り Data.String を import する必要はないでしょう。)

Data.String
class IsString a where
  fromString :: String -> a
-- OverloadeStrings 拡張の下での文字列リテラルの脱糖
"hello" = Data.String.fromString ['h','e','l','l','o']

注意:ByteStringとOverloadedStrings

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

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

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

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

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

関連Issue:

より低レベルへ

ここまでは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# 型、という感じです。

この中に、文字列リテラルの後ろに # をつけた 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以下の値はそのまま埋め込まれます。

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との関係

最初の方に

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

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

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

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を出力させると、

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

GHC.CString.unpackCString# はNUL終端されたバイト列を String に変換する関数です。ghc-primパッケージの GHC.CString で定義されています。

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 は次のように脱糖されるということです:

{-# 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 を経由して目的の文字列型(ByteStringText)に変換されるのでした。

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

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

data SugoiString = ...

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

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

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

{-# 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
  #-}

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

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

が使用されるようです(この関数に関する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をウォッチしておくと良いでしょう。

33
16
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
33
16

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?