DNSSEC は RRset( RR(リソースレコード)のセット ) の内容を、利用者から検証可能にするための仕組みです.

DNSKEY RRには、そのゾーンで利用する公開鍵が登録され、RRSIG RR には RRset のタイプ(署名対象タイプ)とその署名値が登録されます.

RRset の利用者は、RRSIG RR が持つ署名値と DNSKEY RR が持つ公開鍵で署名検証を行なうことで、RRset がゾーンの管理者が署名した内容であることを確認することができます.

検証アルゴリズムでは、入力として RR の正規化ワイヤーフォーマット¹の列²を処理することで、表現のゆれや圧縮の有無による不一致が起きないようにしています.

DNSSEC - 委任情報の検証 - DS(Delegation Signer)

委任元ゾーンでは、 DS RR に委任先ゾーンの DNSKEY RRのダイジェスト値が登録されるとともに、 DSタイプを署名対象にした RRSIG RR が登録されます.

これは、委任元がDS RRを介して委任先を署名していることを意味します.

DS RRが保持しているのは秘密鍵が無くとも計算できる DNSKEY RRのダイジェスト値であるため、利用者が DS RRの内容を確認するには、RRSIG RRを使って検証する必要があります. DS RRとそれに対応するRRSIG RRは委任元のゾーンにあるため、検証は委任元の DNSKEY で行なうことになります.

DNSSEC - 不在証明 - NSEC3(NextSECure v.3)

NSEC3は、ドメインの不在を示すための仕組みです. ハッシュ化ドメイン名を使用することで、ゾーン全体の情報を簡単には取得できないようにしています.

NSEC3 RRは、ハッシュ化ドメイン名を所有者とし、そのゾーン内で存在する次のハッシュ化ドメイン名の先頭のラベルを保持します.

少し複雑ですが、このレコードは、以下を示しています.

所有者のハッシュ化ドメイン名のハッシュ化前のドメイン名が存在している.
次に存在するハッシュ化ドメイン名のハッシュ化前のドメイン名が存在している.
ハッシュ化ドメイン名が、所有者のハッシュ化ドメイン名と次のハッシュ化ドメイン名の間となった場合、ハッシュ化前のドメイン名が存在しない.

ここでハッシュ化ドメイン名とハッシュ化ラベルは次の操作で計算します.

元のドメイン名の正規化ワイヤーフォーマット(RR内のドメイン名の正規化と同じ)を入力としてハッシュ値を計算³
ハッシュ値を Base32Hex⁴ でエンコードし、アルファベットは小文字にする. これをハッシュ化ラベルとする
ハッシュ化ラベルを先頭のラベルとしてゾーンのドメイン名を補う. これをハッシュ化ドメイン名とする

ハッシュ化後の比較に利用する順序関係には、DNS名の正規順序⁵を使用します.

NSEC3 RR はタイプビットマップを持っています. このフィールドから、所有者名が持つ RRset のタイプの一覧がわかるので、ドメイン名は存在するけれども、タイプが無い NODATAの場合を示すこともできます.

このように、NSEC3 RR が有ることで、否定的な応答⁶を示すことができますが、利用者がその内容を確認するには、対応する RRSIG RR で署名検証する必要があります.

DNSSEC - 不在証明 - NSEC(NextSECure)

NSECも、ドメインの不在を示すための仕組みです. ルートゾーンのような、ゾーン全体が公開されている場合に利用されています.

NSEC RRは、そのゾーン内で所有者のドメイン名の次のドメイン名を保持します. このレコードは、所有者のドメイン名と次のドメイン名の間にはドメイン名が存在しないことを示しています.

比較に利用する順序関係には、やはりDNS名の正規順序を使用します.

ハッシュ化が無い分 NSEC3 よりも簡単です.

NSEC3 RRと同様に、NSEC RR もタイプビットマップを持っています.

確認のために RRSIG RR で署名検証が必要なのも、NSEC3 の場合と同様です.

DNSSEC 検証機能の実装

dnsextライブラリ群⁷の dnsext-dnssec に DNSSEC の各検証機能を実装しました⁸

DNSSEC では、暗号アルゴリズムに割り当てられた番号ごとに、アルゴリズムを切り替えて処理を行ないます. アルゴリズムの追加拡張を可能にするために、暗号ライブラリモジュールごとに異なっている公開鍵の型や署名の型を、抽象化して吸収する必要があります.

GHC の ExistensialQuantification の拡張機能で、この抽象化をうまく行なうことができました. たとえば、RRSIG を検証するインターフェースは次のような存在型を利用しています.

data RRSIGImpl =
  forall pubkey sig .
  RRSIGImpl
  { rrsigIGetKey :: PubKey -> Either String pubkey
  , rrsigIGetSig :: Opaque -> Either String sig
  , rrsigIVerify :: pubkey -> sig -> ByteString -> Either String Bool
  }

存在型 pubkey と sig のところに暗号ライブラリ依存の公開鍵の型や署名の型を当て嵌めることで、暗号ライブラリの型と切り離したインターフェースで、検証機能を実装することができました.

Canonical RR Form https://datatracker.ietf.org/doc/html/rfc4034#section-6.2 ↩
次の定義で整列させます: Canonical RR Ordering within an RRset https://datatracker.ietf.org/doc/html/rfc4034#section-6.3 ↩
Calculation of the Hash https://datatracker.ietf.org/doc/html/rfc5155#section-5 ↩
Base 32 Encoding with Extended Hex Alphabet https://www.rfc-editor.org/rfc/rfc4648#section-7 ↩
Canonical DNS Name Order https://datatracker.ietf.org/doc/html/rfc4034#section-6.1 ↩
否定応答については https://khibino.hatenadiary.jp/entry/2023/03/20/105555 を参照↩
https://github.com/kazu-yamamoto/dnsext ↩
インターフェース https://github.com/khibino/dnsext/blob/dnssec-verify-impl/dnsext-dnssec/DNS/SEC/Verify/Types.hs, 実装 https://github.com/khibino/dnsext/blob/dnssec-verify-impl/dnsext-dnssec/DNS/SEC/Verify/Verify.hs ↩

2023-03-28

DNS の反復的な名前解決の仕組みとフルリゾルバの実装

ドメイン名の階層

DNS ではドメイン名に対する情報を管理します.

ドメイン名には階層があり、ドットで区切られたラベルの列の接尾辞がより上位の名前です. 最上位のドメイン名は "." です.

通常利用されているホスト名では、最上位の "." が省略されています. たとえば、"example.com" の省略をやめると "example.com." です. "example.com." は "com." から見て下位のドメイン名です. また、"example.com." と "com." は "." から見て下位のドメイン名です.

DNS ゾーン、DNS 権威サーバ、委任

DNS ゾーンとは、ドメイン名を頂点とする名前情報の管理単位で、より下位のドメイン名を管理します. この頂点のドメイン名をゾーン頂点(zone apex)と言います. DNS 権威サーバはゾーンの名前情報を管理します. 最上位のゾーン頂点は "." で、このゾーンをルートゾーンといいます.

権威サーバはより下位のドメイン名のすべてを直接管理しているとは限らず、間接的な管理を行なっている場合があります. このとき、権威サーバは名前に対する情報を直接返す代わりに、下位のドメイン名を頂点とするゾーンの権威サーバの情報を返します. このような操作を委任と言い、その情報を委任情報と言います.

委任情報には、下位のドメイン名の権威サーバのドメイン名の情報を示すタイプNS のリソースレコード ¹と、権威サーバのアドレスの情報を示すタイプ A (IPv4アドレス) または AAAA (IPv6アドレス)のリソースレコードが含まれます. この、権威サーバのアドレスの情報を示すレコードを、グルーレコードと言います.

下位のドメイン名の権威サーバは、下位のドメイン名を持つ場合と、そうではないドメイン名を持つ場合があります. 下位のドメイン名を持つ場合には、グルーレコードが委任情報に含まれますが、そうではないドメイン名を持つ場合には、グルーレコードは利用できません.

DNS の反復的な名前解決とフルリゾルバ

DNS で名前を解決するには、目的の'ドメイン名'と'タイプ'を指定し、次のような問い合わせの繰り返しの操作が必要です.² この操作を反復的名前解決(iterative resolution)と言います.

'問い合わせ先'をルートゾーンの権威サーバ、'ドメイン名'を目的のドメイン名のトップレベル("com.", "net.", "jp." 等)に設定して開始する
'ドメイン名'が目的のドメイン名なら、目的のタイプを問い合わせて終了.
'ドメイン名'とタイプA の問い合わせを行なう
問い合わせの結果、
1. 委任情報が返らない場合、'ドメイン名'をより下位のドメイン名へと設定して、繰り返す. 2へ
2. 委任情報が返った場合、'問い合わせ先'を委任先の権威サーバ³、 'ドメイン名'をより下位のドメイン名へと設定して、繰り返す. 2へ

DNS のフルリゾルバはこの反復的名前解決を行なう機能に加えて、問い合わせの結果のキャッシュを保持しているため、直接は反復的な名前解決を行なうことができないクライアントのスタブリゾルバからの要求に対して、解決結果を提供することができます.

フルリゾルバの実装

Haskell で PoC として実装した反復的名前解決⁴とキャッシュ⁵ を組み合わせてフルリゾルバを実装しました. ⁶

次のプログラムは反復的名前解決うち、反復的に最終的な委任情報を得る部分を単純化したものです:

iterative :: Delegation  {- 初期値はルートゾーン -}
          -> [Name]      {- 上位から下位へのドメインリスト ex. ["com.", "example.com.", "www.example.com."] -}
          -> DNSQuery Delegation
iterative di0 []        = return di0
iterative di0 (name:ns) =
  step di0 >>=
  maybe
  (iterative di0 ns)  {- 委任情報が返らない無い場合は同じ委任情報を使う -}
  (\di -> iterative di ns)
  where
    step :: Delegation -> DNSQuery (Maybe Delegation)
    step di = do
      aa <- selectAuthAddr di
      msg <- queryAuth aa name A
      getDelegation name msg

{- 委任情報から権威サーバのアドレスを選ぶ.
   グルーレコードが利用できない場合は名前解決を再帰する -}
selectAuthAddr :: Delegation -> DNSQuery IP
{- 権威サーバから問い合わせ結果を得る -}
queryAuth :: IP -> Domain -> TYPE -> DNSQuery DNSMessage
{- 問い合わせ結果から委任情報を取り出す -}
getDelegation :: Domain -> DNSMessage -> QNSQuery (Maybe Delegation)

DNSメッセージのエンコード、デコード、およびスタブリゾルバには開発中のdnsextライブラリ群⁷ を利用しています.

キャッシュは優先度付きキューのライブラリであるpsqueues を利用して実現しています. キャッシュの実装の詳細な説明については https://khibino.hatenadiary.jp/entry/2023/03/20/105555#dns-full-resolver を参照してください.

フルリゾルバのサーバ機能は、次の 3種類のスレッドを連結することで実現しました.

問い合わせDNSメッセージの受信とデコード
キャッシュ付きの反復的名前解決のワーカー
返答DNSメッセージのエンコードと送信

Haskell の並行プログラミングの機能によって、フルリゾルバのサーバ機能を簡潔に実現することができました.

DNS のリソースレコードについては別記事 https://khibino.hatenadiary.jp/entry/2023/03/20/105555#dns-rr を参照↩
QNAME Minimisation Examples https://datatracker.ietf.org/doc/html/rfc9156#section-4 ↩
委任先の権威サーバが解決中の下位ドメイン名でない場合には、グルーレコードが利用できないため、同様の繰り返しで委任先の権威サーバのドメイン名の解決が必要↩
https://github.com/khibino/dns-resolver/blob/tag/cache-server/src/DNSC/Iterative.hs ↩
https://github.com/khibino/dns-resolver/blob/tag/cache-server/src/DNSC/Cache.hs ↩
https://github.com/khibino/dns-resolver/blob/tag/cache-server/src/DNSC/Server.hs ↩
フルリゾルバの PoC 実装当時はdnsライブラリを利用していましたが dnsext へと移行しました. またフルリゾルバのリポジトリを dnsext 下へ移動しました https://github.com/kazu-yamamoto/dnsext/tree/main/dnsext-full-resolver ↩

2023-03-20

DNS の否定応答とフルリゾルバへのネガティブキャッシュの組み込み

DNSのリソースレコードと名前解決

DNS ではドメイン名に関する情報としてリソースレコード(RR) を管理します. RR にはドメイン名、タイプ、クラス、生存期間を示す TTL、RDATA と呼ばれるタイプに応じた目的のデータが含まれています. 名前解決では問い合わせ内容となる (ドメイン名, タイプ, クラス) から RR を決定します.

例えば、ドメイン名 "example.com" の IPv4 アドレスを解決するなら、 ("example.com", A, IN) に対する RR を決定します. タイプ A は IPv4 アドレス用で、クラス IN はインターネットシステムをあらわします. 対応する RR の RDATA には IPv4 アドレスが入っています. 通常の運用ではクラスは IN を指定して利用され、他の値は一般的には使われていません. なので実際にはドメイン名とタイプが RR へ対応付けられることになります.

解決の結果となる RR は一つとはかぎらず、複数でもかまいません. 結果の RR が一つも無いこともあります.

DNSの否定応答とネガティブキャッシュ

DNS の否定応答には種類があり、SERVFAIL のような正常な結果が得られていないものと、 NODATA や NXDOMAIN といった正常な結果が得られているものがあります.

SERVFAIL は、なんらかの理由でシステムから、問い合わせに対する正常な結果を返せない状況です. NODATA は、そのドメイン名とタイプに対する RR は一つも無いけれども、同じドメイン名で別のタイプに対する RR が存在する場合です. NXDOMAIN は、どのようなタイプを指定したとしても、そのドメイン名に対する RR が一つも無い場合です.

DNS のネガティブキャッシュでは正常な結果が得られている NODATA と NXDOMAIN をキャッシュの対象とし、SERVFAIL は対象としません. ¹ 問い合わせに対する結果の RR が一つも無いという情報をキャッシュすることで、フルリゾルバの検索の回数を減らすことができます.

フルリゾルバのキャッシュとネガティブキャッシュの組み込み

開発中の Haskell によるフルリゾルバの実装では、優先度付きキューでキャッシュを実現していました. (Domain, TYPE, CLASS) をキー、[RData] を値、無効化時刻を優先度としています.

キャッシュ書き込み時には TTL と現在時刻から無効化時刻を計算して、優先度として書き込みます. キャッシュ読み出し時には無効化時刻と現在時刻から TTL を逆算することで、 [ResourceRecord] を復元できます.

ここに、ネガティブキャッシュを加えます.²

フルリゾルバの返答においても、ネガティブキャッシュの TTL をクライアント側へ知らせるために SOA とともに返すのが一般的です. キャッシュの情報から SOA を復元する必要があるため、優先度付きキューの値を [RData] から Either Domain [RData] へと変更しました.³ Right の場合が通常のキャッシュで、Left の場合がネガティブキャッシュです. Domain にはゾーンのドメイン名を入れておくことで、SOA を復元することができます.

キャッシュ書き込み時には、権威サーバからの SOA RR の TTL 値と MININUM フィールドのうちの小さい方を TTL として採用し、計算した無効化時刻を優先度として、 Left 付きのゾーンのドメイン名を書き込みます. キャッシュ読み出し時には、ゾーンのドメイン名から SOA を復元する他は、無効化時刻と現在時刻から TTL を逆算するのは通常のキャッシュと同様です.

NODATA の場合は、問い合わせの TYPE をそのままキーとして利用します. NXDOMAIN の場合は、問い合わせの TYPE 以外についても、RR が存在しないことを表現するため、Private Use の空間として定義されている⁴ TYPE の値を内部的に割り当てます. そうすることで、タイプに依らずにネガティブキャッシュを共有することができます.

https://datatracker.ietf.org/doc/html/rfc2308#section-7 ↩
ネガティブキャッシュ実装当時の変更内容 https://github.com/khibino/dns-resolver/compare/tag/empty-with-soa...tag/negative-cache ↩
実装当時の型は、キャッシュ用の型への変換の都合で異なっています. ここではより整理された同型の定義をもとに説明しています.↩
Private Use の空間は RFC6895 https://datatracker.ietf.org/doc/html/rfc6895#section-3.1 で定義される↩

2017-12-26

GHC Generic Programming と代数的データ型

Haskell Advent Calendar 2016 の 12日目のエントリーです。

代数的データ型と Functor

Generic Programming は代数的データ型の構造を Functor の直積と直和のネスト構造に対応付けることで、任意の代数的データ型に対する操作の記述を可能にする仕組みです。

まずは理解のために、より単純化した構造で考えてみましょう。

次のようなデータ型 ProdF f g a を考えると、 ProdF f g は Functor f および Functor g のもとで Functor になります。これは、 もとの Functor のそれぞれの像の直積も Functor になる ということです。

ほぼ自明な内容ですが、 functor則を満たしていることを下に簡単に示してあります。

data ProdF f g a = ProdF (f a) (g a)

instance (Functor f, Functor g) => Functor (ProdF f g) where
  fmap f (ProdF p q) = ProdF (fmap f p) (fmap f q)

{-    fmap id
      {- ProdF の fmap の定義を unfold -}
   =  \(ProdF p q) -> ProdF (fmap id p) (fmap id q)
      {- Functor f および Functor g において fmap id == id -}
   =  \(ProdF p q) -> ProdF p q
   =  id

      fmap (f . g)
      {- ProdF の fmap の定義を unfold -}
   =  \(ProdF p q) -> ProdF (fmap (f . g) p) (fmap (f . g) q)
      {- fmap (f . g) == fmap f . fmap g -}
   =  \(ProdF p q) -> ProdF ((fmap f . fmap g) p) ((fmap f . fmap g) q)
      {- 関数合成の分離 -}
   =  (\(ProdF p q) -> ProdF (fmap f p) (fmap f q)) . (\(ProdF p q) -> ProdF (fmap g p) (fmap g q))
      {- ProdF の fmap の定義を fold -}
   =  fmap f . fmap g
 -}

Control.Applicative モジュールにある Const functor を使って ProdF (Const a) (Const b) x を考えると、これは値の直積 (a, b) と同型( 互いに変換してもプログラムの持つ意味を保存する )になることがわかります。以下で、互いへの変換の関数の定義と、その関数の合成が向きがどちらでも恒等関数になることを示しています。

prodFrom :: (a, b) -> ProdF (Const a) (Const b) x
prodFrom (p, q) = ProdF (Const p) (Const q)

prodTo :: ProdF (Const a) (Const b) x -> (a, b)
prodTo (ProdF (Const p) (Const q)) = (p, q)

{-
      prodFrom . prodTo $ ProdF (Const p) (Const q)
   =  prodFrom  (p, q)
   =  prodF (Const p) (Const q)
 -}

{-
      prodTo . prodFrom $ (p, q)
   =  prodTo  (ProdF (Const p) (Const q))
   =  (p, q)
 -}

このように直積の構造を functor の中に保存することが可能です。

直和の場合も考えてみましょう。

次のようなデータ型 SumF f g x を考えると、 SumF f g は Functor f および Functor g のもとでやはり Functor になります。これは、 もとの Functor のそれぞれの像の直和も Functor になる ということです。

やはりほぼ自明な内容ですが、 functor則を満たしていることを下に簡単に示してあります。

data SumF f g x
  = SumL (f x)
  | SumR (g x)

instance (Functor f, Functor g) => Functor (SumF f g) where
  fmap f (SumL p) = SumL (fmap f p)
  fmap f (SumR q) = SumR (fmap f q)

{-    fmap id
      {- SumF の fmap の定義を unfold -}
   =  \x -> case x of { SumL p -> SumL (fmap id p) ; SumR q -> SumR (fmap id q) }
      {- Functor f および Functor g において fmap id == id -}
   =  \x -> case x of { SumL p -> SumL p ; SumR q -> SumR q }
   =  id

      fmap (f . g)
      {- SumF の fmap の定義を unfold -}
   =  \x -> case x of { SumL p -> SumL (fmap (f . g) p) ; SumR q -> SumR (fmap (f . g) q) }
      {- fmap (f . g) == fmap f . fmap g -}
   =  \x -> case x of { SumL p -> SumL ((fmap f . fmap g) p) ; SumR q -> SumR ((fmap f . fmap g) q) }
      {- 関数合成の分離 -}
   =  (\x -> case x of { SumL p -> SumL (fmap f p) ; SumR q -> SumR (fmap f q) }) .
      (\x -> case x of { SumL p -> SumL (fmap g p) ; SumR q -> SumR (fmap g q) })
      {- SumF の fmap の定義を fold -}
   =  fmap f . fmap g
 -}

こちらでも SumF (Const a) (Const b) x を考えると、これは値の直和 Either a b と同型になることがわかります。直積の場合と同様に、互いへの変換の関数の定義と、その関数の合成が向きがどちらでも恒等関数になることを示しています。

sumFrom :: Either a b -> SumF (Const a) (Const b) x
sumFrom (Left  p)  =  SumL (Const p)
sumFrom (Right q)  =  SumR (Const q)

sumTo :: SumF (Const a) (Const b) x -> Either a b
sumTo (SumL (Const p))  =  Left  p
sumTo (SumR (Const q))  =  Right q

{-
       sumFrom . sumTo $ SumL (Const p)
    =  sumFrom  (Left p)
    =  sumL p

       sumFrom . sumTo $ SumR (Const q)
    =  sumFrom  (Right q)
    =  sumL q
 -}

{-     sumTo . sumFrom $ Left p
    =  sumTo  (SumL (Const p))
    =  Left p

       sumTo . sumFrom $ Right q
    =  sumTo  (SumR (Const q))
    =  Right q
 -}

このように直和の構造も functor の中に保存することが可能です。

直積と直和の構造を情報を保存したままともに Functor にすることができたので、これをさらに入れ子にすることで、与えられた任意の代数的データ型と同型になる Functor に変換できることがわかります。

GHC Generic Programming における定義

ここからは GHC.Generics モジュールに定義されている実際の Generic Programming 用の定義を使って見ていきましょう。

上の例での ProdF に対応するのが :*:、 SumF に対応するのが :+:、 Const に対応するのが K1 です。

これに加えて、コンストラクタの情報を保存するための型 M1 (フィールド 1つ以上) U1 (フィールド無し) が用意されています。

data (:*:) f g p = (f p) :*: (g p)
data (:+:) f g p = L1 (f p) | R1 (g p)
newtype K1 i c p = K1 {unK1 :: c}

data U1 p = U1
newtype M1 i c f p = M1 {unM1 :: f p}

代数的データ型と Functor の構造を互いに変換するための関数も見てみましょう。

% ghci
Prelude> import GHC.Generics
Prelude GHC.Generics> :t from
from :: Generic a => a -> Rep a x
Prelude GHC.Generics> :t to
to :: Generic a => Rep a x -> a

a が代数的データ型であるとすると Rep a はそれに対応した構造を持つ Functor です。 from は代数的データ型を Functor のネスト構造に変換し、 to はFunctor のネスト構造を代数的データ型に変換します。 Generic クラスのインスタンスは、 GHC の DeriveGeneric 拡張を使うことで生成することができます。

では直積の構造がどのような Functor に変換されているか見てみましょう。

Prelude GHC.Generics> :t from ( ('a', 1) :: (Char, Int) )
from ( ('a', 1) :: (Char, Int) )
  :: D1
       ('MetaData "(,)" "GHC.Tuple" "ghc-prim" 'False)
       (C1
          ('MetaCons "(,)" 'PrefixI 'False)
          (S1
             ('MetaSel
                'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
             (Rec0 Char)
           :*: S1
                 ('MetaSel
                    'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
                 (Rec0 Int)))
       x

D1, C1, S1 は M1 の特殊化で、コンストラクタの情報です。 Rec0 は K1 の特殊化で、中にフィールド内の情報を保持しています。 :*: によってペア (Char, Int) の構造が保存されている様子が伝わるでしょうか。

直和の場合も見てみましょう。

Prelude GHC.Generics> :t from ( (Just 'x') :: Maybe Char )
from ( (Just 'x') :: Maybe Char )
  :: D1
       ('MetaData "Maybe" "GHC.Base" "base" 'False)
       (C1 ('MetaCons "Nothing" 'PrefixI 'False) U1
        :+: C1
              ('MetaCons "Just" 'PrefixI 'False)
              (S1
                 ('MetaSel
                    'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
                 (Rec0 Char)))
       x

Nothing はフィールドが無いコンストラクタなので U1 が使われています。 :+: によって Just と Nothing の直和の構造が保存されている様子が伝わるでしょうか。

このように、Generic Programming を利用すると、代数的データ型を直接操作する処理を書く代わりに、 Rep a x を操作する処理を書いておいて、適切に from および to で変換することで、任意の代数的データ型に対する汎用的な操作を書くことが可能となります。

GHC Generic Programming がどのように実現されているのかの理解の助けになればと思い、この記事を書いてみました。

ランキング参加中

Haskell

2017-12-18

OverloadedLabels と Haskell Relational Record

Haskell (その2) Advent Calendar 2017 の 18日目のエントリーです。

OverloadedLabels のレコードでの利用

GHC 8.0.1 以降では OverloadedLabels 拡張がサポートされたことにより、適切な定義を追加しておくことで、レコードのフィールド名の衝突を気にせずに利用できるようになりました。

以下 user's guide の example のコードです。

{-# LANGUAGE DataKinds, KindSignatures, MultiParamTypeClasses,
             FunctionalDependencies, FlexibleInstances,
             OverloadedLabels, ScopedTypeVariables #-}

import GHC.OverloadedLabels (IsLabel(..))
import GHC.TypeLits (Symbol)

data Label (l :: Symbol) = Get

class Has a l b | a l -> b where
  from :: a -> Label l -> b

data Point = Point Int Int deriving Show

instance Has Point "x" Int where from (Point x _) _ = x
instance Has Point "y" Int where from (Point _ y) _ = y

instance Has a l b => IsLabel l (a -> b) where
  fromLabel _ x = from x (Get :: Label l)

example = #x (Point 1 2)

IsLabel クラスのインスタンスを型レベルの文字列 "x" に対して実装することで、ここでは #x というフィールドを取り出す関数名を衝突を気にせずに利用することができます。

OverloadedLabels の Haskell Relational Record での利用

IsLabel のインスタンスは型レベル文字列 x と型 a に対して定義します。

class IsLabel (x :: Symbol) a where
  fromLabel :: Proxy# x -> a

この定義を良く見ると気がつきますが、型レベル文字列と任意の型に対するインスタンスを定義することができます。

レコードでの利用の場合は、型レベル文字列とレコードフィールドを取り出す関数に対して定義を行なっているということです。

Haskell Relational Record では型レベル文字列と Pi a b (レコードからの射影取り出しに利用するラベル) の型に対して定義することで、射影取り出しのラベルを衝突を気にせずに利用することができます。

Haskell Relational Record でのコード例は例えば以下のようになります。

windowRankByGroup :: Relation () ((Int64, Maybe Int32), (Maybe String, Maybe String))
windowRankByGroup =  relation $ do
  u <- query user
  m <- query membership
  on $ #id u .=. #userId m
  g <- query group
  on $ #id g .=. #groupId m

  let gwindow = do partitionBy $ (! #id) g -- g ! Group.id'
                   asc $ #name u

  return (rank `over` gwindow
          ><
          sum' (#id u) `over` gwindow
          ><
          (#name u
           ><
           #name g))

ラベル #id や #name が、衝突を気にせずに利用できていることがわかります。

ランキング参加中

Haskell

2015-12-14

Haskell Relational Record を PostgreSQL アンカンファレンスで宣伝してきました

Haskell Advent Calendar 2015 の15日目のエントリーです。

以前から、 Haskell Relational Record (HRR) [ http://khibino.github.io/haskell-relational-record/ ] を RDBMS のユーザーのコミュニティーにも紹介してみたいと考えていました。 ( HRR 自体についてはプロジェクトページやチュートリアルを見てください )

HRR を使うと SQL の部品化とその型付けを行なうことができるため、複雑な SQL を書く際の間違いを減らすことができるのが HRR を使うメリットです。そのような方向でよく利用されていると思われる、PostgreSQL 系のイベントで発表してみようと思い、 PostgreSQL アンカンファレンス ( https://atnd.org/events/70296 ) に発表しに行ってきました。

※ 発表資料

以下、togetter によるまとめからですが、

http://togetter.com/li/912198

集合の数式・・・う・・・頭が・・・ #pgunconf Haskeller って数学屋さん好きな言語なの？
— ぬこ＠横浜 9.5-beta2 (@nuko_yokohama) 2015, 12月 12

モナド怖くないけど、やっぱりHaskell怖いｗ #pgunconf
— ぬこ＠横浜 9.5-beta2 (@nuko_yokohama) 2015, 12月 12

「今日のモナドはこわくないです」 #pgunconf
— どこ住み？LINEやってる？ (@a_suenami) 2015, 12月 12

Haskellでは<-と∈(数式）は同じような意味！ #pgunconf
— show (@surumegohan) 2015, 12月 12

最初にリスト内包表記(とリストモナド)の見た目を紹介して、それとの対比で HRR の Query の表記と example を紹介していく流れで説明しました。

Composableバンザイ！ #pgunconf
— show (@surumegohan) 2015, 12月 12

型の話ってデータベース・データタイプと関係するの？ haskell コンパイル中にスキーマ情報もとってくる。それを元に型的には安全なSQLを生成できる（という理解で合ってるのかな？） #pgunconf
— ぬこ＠横浜 9.5-beta2 (@nuko_yokohama) 2015, 12月 12

inner JOINの例、Left Outer、Aggregate(group by)、order by, Window関数！これまでの例はHaskell式なので合成可能。 #pgunconf
— ぬこ＠横浜 9.5-beta2 (@nuko_yokohama) 2015, 12月 12

SQL を部品化して、composable に組み上げることができるという内容は伝わったのかなと考えています。

懇親会では、型付けをするモチベーションとして、必要な変更を正しく行ないやすいという話をして、ある程度納得してもらえたのかなと思っています。

簡単ですが以上です。

ランキング参加中

Haskell

2014-12-23

計算の合成

Haskell Advent Calendar 2014 の22日目のエントリーです。

導入

Haskell では計算を持った値であることを型で表わすことができる。とくに計算を持っていない型は Int や a のような形をしている。しかし例えば Maybe Int ならば、結果の型 Int の値は得られるかもしれないし得られないかもしれない。 Functor f => f a なら、結果の型 a を得るためには何らかの計算 f が必要だと考える。

プログラムを書くときには結果の値を計算するにあたって、様々な計算を利用する。複数の計算をうまく組み合わせる方法が重要だ。

計算の連続適用

型 a に計算 h を適用したものにさらに計算 g を適用し、さらに f を適用すれば f (g (h a)) である。

ここでは、どんな計算を適用するかだけを考えることにして、単に fgh の様に並べて書くことにしよう。

例えば fgh のような3種類の計算を欲しい順に欲しいだけ適用するには、 fghfghfgh ... というように並べ、さらに、f, g, h のそれぞれに、実は何もしない計算があればよいことになる。それぞれを Id_f, Id_g, Id_h と書くことにし、fghfgh の適用の中に Id が混ざっているものを考えれば、

f Id_g h Id_f g I_h == fhg

という様に結果的に欲しい計算を欲しい順に適用できる。

計算の直和

また、別のアプローチもある。仮に計算 f または g を適用することを表現するのに f+g と書くことにしよう。 f または g または h を適用するのは f+g+h である。

これを繰り返し適用すると、

(f+g+h)(f+g+h) = ff + fg + fh + gf + gg + gh + hf + hg + hh

となる。

これを繰り返し回数を増やしていけば、繰り返し回数だけやはり欲しい計算を欲しい順に適用できる。

Monad Transformer

前者のアプローチの実装例が Monad Transformer である。 Monad Transformer の場合は transformer の中のモナドを持ち上げる (lift する) と計算が内側に入ることになる ( StateT や ReaderT は違うと気がつくかもしれない。だが f (s -> (a, s)) -> s -> f (a, s) や f (r -> a) -> r -> f a は \mf s -> fmap ($ s) mf とやると簡単に作り出せることがわかるので、少なくとも Functor の計算が Monad Transformer の力を持っていることを認めて話を先に進める ) 。

Monad Transformer で作り出した、複数の計算の複合した Monad は、 (>>=) で繰り返し適用することができる。そして何もしない計算に相当するのは id や lift である。

Monad Transformer を利用することで、計算を欲しいだけ欲しい順に適用できる。

Data Types á la carte

後者のアプローチは Data Types á la carte や Extensible Effects (実装) である。

ここでは Data Types á la carte の方をとりあげる。 Data Types á la carte は

data (f :+: g) a = Inl (f a)
                 | Inr (g a)

と定義したときに、f, g が Functor であるときには f :+: g も Functor になることを利用する。残念なことに f, g が Monad であったとしても f :+: g は Monad になるとは限らない。 Monad であれば (>>=) で繰り返し適用することができたが、こちらではそうはいかない。

ではどうするのか。計算の繰り返しのデータ型を定義することで対応する。

data Expr f = In (f (Expr f))

foldExpr :: Functor f => (f a -> a) -> Expr f -> a
foldExpr f (In t) = f (fmap (foldExpr f) t)

Expr の定義は一見、いくらでも計算が出てくるので、本当に停止するのか心配になる。が、foldExpr は各計算から結果を導く関数 ( f a -> a ) が停止するなら全体が停止するとも読める。

Data Types á la carte の前半では結果が Int になるような evaluator の例が紹介されている。

class Functor f => Eval f where
  evalAlgebra :: f Int -> Int

eval :: Eval f => Expr f -> Int
eval expr = foldExpr evalAlgebra expr

このようにして、Functor の直和を利用することで、計算を欲しいだけ欲しい順に適用できる。

ここに至ると、この Functor を Free Monad に入れたらどうなるのかが気になるところだろう。しかし、今回は survey の時間が十分に取れなかったので、このあたりにしておきたい。

( Free Monad 編、Codensity, Yoneda, Lens 編に続く ... のか? )

ランキング参加中

Haskell

khibino blog

DNSSECの基本的な検証機能とその実装

DNSSEC - RRset の署名検証 - RRSIG(Resource Record Signature)

DNSSEC - 委任情報の検証 - DS(Delegation Signer)

DNSSEC - 不在証明 - NSEC3(NextSECure v.3)

DNSSEC - 不在証明 - NSEC(NextSECure)

DNSSEC 検証機能の実装

DNS の反復的な名前解決の仕組みとフルリゾルバの実装

ドメイン名の階層

DNS ゾーン、DNS 権威サーバ、委任

DNS の反復的な名前解決とフルリゾルバ

フルリゾルバの実装

DNS の否定応答とフルリゾルバへのネガティブキャッシュの組み込み

DNSのリソースレコードと名前解決

DNSの否定応答とネガティブキャッシュ

フルリゾルバのキャッシュとネガティブキャッシュの組み込み

GHC Generic Programming と代数的データ型

代数的データ型と Functor

GHC Generic Programming における定義

OverloadedLabels と Haskell Relational Record

OverloadedLabels のレコードでの利用

OverloadedLabels の Haskell Relational Record での利用

Haskell Relational Record を PostgreSQL アンカンファレンスで宣伝してきました

計算の合成

導入

計算の連続適用

計算の直和

Monad Transformer

Data Types á la carte