関手、Applicative、Monadの法則

Monadとは、Applicativeであるデータ構造で、(>>=)演算子を提供し、それがMonad法則を満たすものである。

正確に表現するとこうなんですが、「はぁ？」っ感じですよね。「満たすべき法則」とか言われると、まったく理解できません。でも、オススメの形に持っていくための変換規則と捉えると分かりやすいのではないかというのが、この記事の主旨です。

関手

関手法則は以下の2つです：

• 単位元： id <$> x = x
• 合成　： f <$> (g <$> x) = (f . g) <$> x

左辺が冗長な形、右辺がオススメの形です。これはいいですよね？

Applicative

Applicative法則は以下の4つです（<*>は左結合）。

• 単位元： pure id <*> x = x
• 準同型： pure g <*> pure x = pure (g x)
• 交換　： x <*> pure y = pure (\g -> g y) <*> x
• 結合　： x <*> (y <*> z) = pure (.) <*> x <*> y <*> z

アプリカティブスタイルは、

pure g <*> x1 <*> x2 <*> ... <*> xn

でした（pure g <*> の部分は g <$> と書くことが多い）。Applicative法則は、アプリカティブならすべてこの形に直せることを保証する規則なのです。例として、t <*> pure s <*> (u <*> v) を変換してみましょう。

  t <*> pure s <*> (u <*> v)
(結合)
= pure (.) <*> (t <*> pure s) <*> u <*> v
(交換)
= pure (.) <*> (pure (\g -> g s) <*> t) <*> u <*> v
(結合)
= pure (.) <*> pure (.) <*> pure (\g -> g s) <*> t <*> u <*> v
(準同型)
= pure ((.)(.)) <*> pure (\g -> g s) <*> t <*> u <*> v
(準同型)
= pure ((.)(.)(\g -> g s)) <*> t <*> u <*> v

ほらね、言った通りでしょ。

Monad

Monad法則は以下の3つです（return は pure の別名）：

• 左単位元： return x >>= f = f x
• 右単位元： mx >>= return = mx
• 結合　　： mx >>= (\x -> (f x) >>= g) = mx >>= f >>= g

二つの単位元ですが、右辺がオススメなのは分かりますよね？ 右単位元は特に有用です。do の中をいろいろ書き換えていると、知らない間に、

do ...
   y <- f x
   return y

みたいな形になっていることがあります。これは冗長なので、以下のように書けということです。

do ...
   f x

結合の法則ですが、左辺は、

do y <- do x <- mx
           f x
   g y

ですから冗長ですね。一方右辺は、

do x <- mx
   do y <- f x
      g y

という意味ですが、これは平坦化できて、

do x <- mx
   y <- f x
   g y

と書けます。

すなわち、do は入れ子で書かずに、平坦な形でスッキリ書いてねという意味です。

まとめ

法則は、オススメの形式が右に書かれてないことも多いので気づきにくいのですが、「オススメの形式に書き換えてよいことが保証されているよ」と理解すれば親しみ易くなりませんか？

追記

4つのApplicative法則が満たされると、 pure f <*> x = f <$> x が自動的に満たされます。

関手の単位元を示すために、f = id を代入：

  pure f <*> x
(単位元)
= pure id <*> x
= x

関手の合成を示す：

  pure f <*> (pure g <*> x)
(結合)
= pure (.) <*> pure f <*> pure g <*> x
(準同型)
= pure ((.) f) <*> pure g <*> x
(準同型)
= pure ((.) f g) <*> x
(中置表記)
= pure (f . g) <*> x

よって、2つの関手法則は満たされるので、 pure f <*> x = f <$> x です。

さようなら遅延評価

Haskellがとっつきにくい原因の一つに遅延評価がある。入門書では、無限リストと遅延評価がことさら強調される。しかし、Haskellを業務で使ってみると、遅延評価が煩わしくなってくる。遅延評価なしでもほとんどのことは実現できるし、メモリーの使用量は推測できないし、あまりいいことはない。

Haskellの評価戦略が、他の言語と同じように正格評価だったらよかったのに。

今まで、このようなセリフを何度聞いたか分からない。 そもそも遅延評価が役立つことはあるのだろうか？

ある。お世辞抜きに、少なくとも以下の3つでは本当に役立つ。

1. リスト(あるいは類似のデータ構造)処理
2. 純粋性に対する暗黙のテスト
3. 効率的なCAS

1.はよいだろう。2.は純粋さを守るために必要だが、コンパイラを開発する人にとって重要なのであり、ユーザには関係ない。3.は、並行プログラミングの奥義である。atomicModifyIORef'を用いれば、実際の仕事を待機させた状態で compare-and-swap を成功させ、後からその仕事を片付けられる。

しかしながら私は、これ以外で遅延評価が役に立った事例を寡聞にして知らない。

実はHaskellでも、正格評価を利用できる。それには !(バンと読む)を使う。

{-# LANGUAGE BangPatterns #-}

data T = C !Int

f !x = y
  where
    !y = x + 1

この問題点は、コードのいたるところがバンバンして、読みにくくなることである。実際、コードを書いてみると嫌になってくる。この問題を解決するために、GHC 8.0 では、言語拡張 Strict と StrictData が提供された。この二つを使えば、デフォルトの評価戦略が正格評価となる。

つまり、以下のコードの評価戦略は遅延評価だが、Strict と StrictData を用いると正格評価となる。

data T = C Int

f x = y
  where
    y = x + 1

ちなみに、この言語拡張が有効な範囲は指定されたモジュール内のみである。

デフォルトの評価戦略を正格評価にすると、今度は遅延評価を明示的に書けるようにする必要がある。それには ~ を使う。

data T = C ~Int

f ~x = y
  where
    ~y = x + 1

Strict と StrictData をもう少しく知りたい人はStrict Haskellを読んでほしい。

純粋関数型データ構造を読んだ諸君、Haskellではデフォルトが遅延評価だからイマイチ例題をうまく実装できないと思ったことだろう。でも、今なら簡単にできるのだ！

GHC 8.0.1がリリースされたのは、2016年5月。あれから2年強。現在は、GHC 8.6の時代だ。GHCのメジャーバージョンは3つサポートする掟に鑑みてもお釣りがくる。

Haskellerよ、時は来た。新しいプロジェクトを始めるときは、迷わずに以下を cabalファイルに入れるのだ！

  default-extensions:  Strict StrictData

Haskell network library version 3.0

Brief history

The first commit of the network library in Haskell was created by Simon Marlow in 2001. It says:

Package 'net' moved over. URI & CGI still missing because they have dependencies on other bits that haven't made it over yet.

So, I guess that the code existed before the day and actually I heard that network was one of the oldest packages in Haskell. When Johan Tibell became the previous maintainer, network was messy already. Before he started refactoring, he added many test cases. Thank you, Johan!

In 2015, he passed the baton to Evan Borden and me without drastic refactoring. After that, we concentrated on bug fixes only for a while. I don't know about Evan but this is because I didn't have any ideas to improve this package.

In December 2017, I decided to resolve issues as much as possible. During this work, I realized what is important for network:

• The code was messy like other long-life code. We should clean up the code for maintainability.
• The build system was terrible. We cannot understand which depends on which. We should also clean up it.
• Believing or not, Socket cannot be GCed. This is a shame. Socket should be GCed.
• SockAddr was not extensible. If users want to add a new one, they must send a PR. Once merged, the maintainers must maintain it even they don't know it well. Other packages should be able to extend SockAddr without modifying network.

I divided the jumbo Network.Socket module into small sub-modules. Also, I cleaned up the build system. This work was painful because I don't know Windows well. Luckily, we welcomed Tamar Christina as a new maintainer for Windows.

I will explain the last two items in the next section in detail. But briefly, we had to change the signatures of two APIs.

In network v2.6:

fdSocket :: Socket -> CInt
mkSocket :: CInt -> Family -> SocketType -> ProtocolNumber -> SocketStatus -> IO Socket

But in network v3.0:

fdSocket :: Socket -> IO CInt
mkSocket :: CInt -> IO Socket

To provide migration path, we did:

v2.6

• Making SockAddrCan deprecated

v2.7

• Making Network deprecated
• Making Network.BSD deprecated
• Making MkSocket deprecated
• Making many APIs deprecated

v2.8

• Stop exporting the PortNum constructor in PortNumber

v3.0

• Removing Network
• Removing Network.BSD
• Removing SockAddrCan
• Changing the internal structure of Socket.
• Make address extensible.
• Remove EOF errors

Like Network.URI in the network-uri package, Herbert Valerio Riedel kindly released the network-bsd package for Network.BSD.

Main jobs for v3.0 were done in Dec 2017 and v3.0 was released in Jan 2019. I'm very sorry for breaking backward compatibility but we waited for at least one year.

GC and extensibility

Recall the signature of the old API:

mkSocket :: CInt -> Family -> SocketType -> ProtocolNumber -> SocketStatus -> IO Socket

To make a Socket, we needed to supply Family, SocketType and ProtocolNumber. Since they are sum types, they cannot be extended without modifying the definitions. But CInt, a socket descriptor, is created by the socket() system call with its protocol family, its socket type and its protocol number. Why should we specify them again?

See the old definition of Socket:

data Socket = MkSocket CInt Family SocketType ProtocolNumber (MVar SocketStatus)

I don't know why they were included in. Let's remove them for extensibility. So, what about MVar SocketStatus? A good question! The reason why Socket cannot be GCed is MVar. We tried two approaches: mkWeakMVar and addFinalizer but it appeared that they did not solve the problem.

So, let's remove MVar, too:

data Socket = Socket CInt

But without status control, unexpected things would happen. Consider this scenario:

• Haskell thread (A) creates Socket with a socket descriptor and close it.
• The socket descriptor is re-used in another Haskell thread (B).
• Haskell thread (C) can close the Socket again.
• At this point, Haskell thread (B) suffers from unexpected behavior.

The key idea to solve this problem was provided by Viktor Dukhovni. He suggested to use IORef:

data Socket = Socket (IORef CInt)

When Socket is closed, we modify the value of IORef to -1 for safety. Unfortunately, to extract the file descriptor in Socket, IO is necessary:

fdSocket :: Socket -> IO CInt

This is the reason why the signature changed. With this definition, we need unsafePerformIO to make Socket an instance of Show. So, the final definition of Socket is:

data Socket = Socket (IORef CInt) CInt -- for Show

Final note

If you want to extend socket addresses, see the new Network.Socket.Address module.

I hope that the reasons for the breaking changes are now more clear.

I thank Lars Petersen for showcasing design for extensibility in his socket package.

QUIC開発日記 その1 参戦

QUICや ああQUICや QUICや

詠み人知らず。QUICの実装の難しさに絶望した心境が詠まれたと伝う。

序章

2017年の7月ごろ、QUICの実装を始めました。Haskellの有名なシリアライザ/デシリアライザである binary や cereal では、バッファ操作ができないので、パケットヘッダを複雑に処理する必要がある QUIC には不向きです。そこで、Haskell HTTP/2 ライブラリから、バッファ操作の部分を切り出して、network-byte-orderというライブラリを作るところから始めました。

その矢先、上司とのミーティングでのこと：

上司「来年度開発室を立ち上げる前に、下期の半年間、現場に行って開発の現場を見てこい」
kazu「いいですけど、他のQUIC実装に遅れをとることになりますが、いいんですか？」
上司「いい。」

という訳で、QUICの開発は中断されました。

2018年4月に開発室が立ち上がりました。帰ってきてから、まずTLS 1.3を片付ける必要があり、根気強く上流にマージました。そして、ようやく2019年の年明けからQUICの実装を再開しました。1月末にIETF QUIC分科会の相互接続試験イベントと中間ミーティングが東京で開催されるので、それに間に合わせるためです。

これは一ヶ月間のQUIC実装奮闘記です。

再開

まずQUICの仕様を読むところから再開しました。transport/tls草稿の番号は17になっていました。巨大な仕様なので、まったく頭に入ってきません。気分が滅入っているところに、次の18ではテストベクタが追加されることが分かり、俄然やる気が出てきました。

最初の目標は、テストベクタに載っているネットワーク上のバイナリをデコードすることです。鍵を生成するには Haskell TLS ライブラリから非公開の関数を公開する必要がありました。興味がある人は、quicブランチを見てください。また、QUICパケットを扱うには network-byte-order ライブラリを育てていく必要もありました。

QUICパケットのデコード

QUICパケットをデコードするには以下の手順を踏みます。

1. 保護されたヘッダをパースする
2. 暗号化されたペイロードを用いてヘッダの保護を外し、パケット番号を取り出す
3. ヘッダとパケット番号などを用いてペイロードを復号化する

ヘッダのパースには、整数デコーダが2つ必要になります。

1. 可変長の整数デコーダ
2. パケット番号に用いられる差分変数のデコーダ

これらはQUICに特有なので、自分で実装する必要があります。実装は簡単です。テストベクタは、TLS 1.3の鍵交換をする前のInitialパケットの例であり、自明な鍵でペイロードを復号化できます。

この辺りまでは、面倒でしたが特に問題なく実装できました。

QUIC パケットのエンコード

QUIC パケットのエンコードは、この逆をやります。

1. ヘッダを組み立てる
2. ヘッダとパケット番号を用いてペイロードを暗号化する
3. 暗号化されたペイロードを用いてヘッダを保護する

分かりやすい図があるので、ペイロードの暗号化についてもう少し詳しく見てみましょう。Martin Thomson氏のQUIC Secruityより抜粋：

QUIC ペイロードの暗号化

AEADの入力は、平文(Packet Payload)、付加データ(Packet Header)、鍵(Key)、Nonce(IV xor Packet Number)です。AEADを安全に使うには、付加データか Nonce が一意である必要があります。パケット番号を使うことで、Nonce が一意になるように設計されていることが分かります。

ヘッダの保護の方も図で見てみましょう。再びMartin Thomson氏のQUIC Secruityより抜粋：

QUIC ヘッダの保護

サンプルを暗号ペイロードの先頭付近からとってきます。「付近」なのは、パケットの差分が最大4バイトで表されるからです。最大の4バイトに重ならない部分からサンプリングします。

ちなみに、パケットの差分が何バイトになるかは、ヘッダの保護されるビットに指定します。さらっと書きましたが、すべてきちんと順に実装していかないと、パケットを組み立てたり解析したりはできないのです。

TLS 1.3

次の目標はハンドシェクです。QUICの元々の設計では、TLS 1.3を従来の方法で使うことになっていました。つまり、入出力を伴うソケット層として使うのです。TLS 1.3のハンドシェイクメッセージが入ったTLSレコードは、QUICパケットに格納して運ぶ必要があります。

何を言っているか分からないかもしれませんが、実はこれは簡単に実装できます。というのは、通常のTLSライブラリにはIOバックエンドを指定する方法があるからです。QUICが、TLSライブラリのハンドシェイクAPIを呼ぶときに、QUICをバックエンドに指定しておけばいいのです。交換した鍵は、Exporter Master Secretとして提供されます。

しかし、ちゃぶ台は見事にひっくり返されました。QUICは、TLS 1.3をソケット層ではなく、IOを伴わないエンコーダ/デコーダとして使うように再設計されたのです。QUICとTLSの間では、TLSハンドシェイクメッセージは平文で交換され、ネットワークに送信する前に暗号化/復号化するのはQUIC側になります。詳しくはTLS Handshake Messages on QUIC, and Address Validationを読んでください。

TLSは Transport Layer Security の略語ですが、QUICでは T も L も使わずに、S しか使いません。QUICは、新しい Transport Layer ですからね！

さぁ、TLS 1.3 ライブラリの大幅改造が必要です。APIからIOを分離する必要があります。僕はしばらくTLS沼でもがいていましたが、どれくらい大変だったかは、このプルリクを見ていただくと感じ取れるかもしれません。

相互接続試験イベント

QUIC transport草稿の図5より：

Initial[0]: CRYPTO[CH]
0-RTT[0]: STREAM[0, "..."] ->
                                 Initial[0]: CRYPTO[SH] ACK[0]
                        Handshake[0] CRYPTO[EE, CERT, CV, FIN]
                          <- 1-RTT[0]: STREAM[1, "..."] ACK[0]

Initial[1]: ACK[0]
Handshake[0]: CRYPTO[FIN], ACK[0]
1-RTT[2]: STREAM[0, "..."] ACK[0] ->

                         1-RTT[1]: STREAM[55, "..."], ACK[1,2]
                                       <- Handshake[1]: ACK[0]

UDPの部分を付け足して、なんとかQUICパケットをネットワークに送信できるようになりました。辻川さんが隣にいたので、最初の相手としてngtcp2サーバに話しかけます。いわゆる Client Hello を送信し、Server Hello を受信しすると、なんと Encrypted Extensions (EE) 以降が復号化できません。

kazu「ひょっとしてHandshakeパケットって分割されてますか？」
辻川さん「証明書が大きいので分割されます」
kazu「がーん」
辻川さん「TLSライブラリが鍵をくれるまで、ペイロードを突っ込めばいいです」

いや、Haskell TLSライブラリでもできなくはないんです。でも、TLSのAPIから「TLSパケットをパースしている途中の状態」を返すのは避けたいのです。一晩悩みましたが、TLSハンドシェイクメッセージは平文であり、TLVの形が見える、そう、型と長さが分かることに気づきました。そこで、TLSのAPIを呼ぶ前に、TLSハンドシェイクメッセージを組み立てて完全な形にすことができるようになりました。

ここで、試合終了。Client Finishedは、まだ送れていません。

To be continued

2月は報告書の作業が忙しいので、再び中断です。

I will be back in March!

TLS 1.3 開発日記 その30 NewSessionTicket 再考

NewSessionTicketをいつ送るかの議論です。

まず、TLS 1.3 開発日記 その9 NewSessionTicketをお読み下さい。

Haskell TLS の実装では、Client Finished の値を予測して NewSessionTicket を作成し、handshake() API が送信していました。このときは、クライアント認証は実装していませんでした。

クライアント認証を実装するにあたり、Haskell TLS ライブラリのメンテナの間で、この方法は適切なのか議論になりました。サーバはクライアント認証を要求している場合でも、クライアントを認証する前に NewSessionTicket を送るからです。サーバがクライアント認証に失敗し、クライアントの接続を拒否したとします。しかし、クライアントはチケットを手に入れているので、再び接続すればクライアント認証を省略してハンドシェイクを完了できます。

いくつかの意見が出されたのですが、結局 Client Finished の到着後、つまり必要であればクラアント認証を完了してから、recvAppData() API が NewSessionTicket を送ることになりました。

SemigroupがMonoidに恋するとき

復習

Semigroup

• 結合則 (a・b)・c = a・(b・c)

class Semigroup a where
  (<>) :: a -> a -> a

Monoid

• 結合則 (a・b)・c = a・(b・c)
• 単位元 e・a = a・e = a

class Semigroup a => Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mappend = (<>)

本題

Haskellerの中には、「設定はMonoidであるべき」宗派が存在する。そのような信念を持つHaskellerが作ったライブラリを使おうとすると、Monoid のインスタンスを (<>) でつないで設定データを構築することになる。

この記事では、SemigroupをMonoidに昇格させるのはいつかという話題を扱うので、まずSemigroupである設定データから始めよう。僕が最近秀逸だと思っているフラグを例として挙げる。

フラグには以下のような操作ができる：

• フラグをセットする (FlagSet)
• フラグをクリア(アンセット)する (FlagClear)
• フラグをデフォルトに戻す (FlagReset)

これを実装するのは簡単だろう。(<>) の右が勝つことに決めれば、以下のようになる。

data FlagOp = FlagSet | FlagClear | FlagReset deriving (Eq,Show)

instance Semigroup FlagOp where
    _ <> op = op

使ってみよう：

> FlagSet <> FlagReset <> FlagClear
FlagClear

あとは、これを受け取って、

• FlagSet ならフラグをセットする
• FlagClear ならフラグをクリアする
• FlagReset ならデフォルトの値を使用する

という関数を書くことになるだろう。そこは割愛する。

これで話が終われば、設定データは Semigroup で十分で Monoid にする必要はない。どうして、設定と言えば Monoid と言われるのだろう？

答えは「設定したい項目は複数あることが多い」からだ。FlagOpを複数格納しているデータをConfigとしよう。

data Config = Config { aflag :: FlagOp, bflag :: FlagOp } deriving (Eq,Show)

instance Semigroup Config where
    Config a1 b1 <> Config a2 b2 = Config (a1 <> a2) (b1 <> b2)

aflag をセットする setAFlag を作るとする。bflag は明らかに FlagSet や FlagClear ではないので、FlagReset としてみる。

setAFlag :: Config
setAFlag = Config { aflag = FlagSet, bflag = FlagReset }

同様に、setBFlag も作る。

setBFlag :: Config
setBFlag = Config { aflag = FlagReset, bflag = FlagSet }

setAFlag と setBFlag を結合するとどうなるだろう？

> setAFlag <> setBFlag 
Config {aflag = FlagReset, bflag = FlagSet}

あれれれれ？ aflag も bflag も FlagSet であるべきなのに、aflag は FlagReset になってしまった。

どうやって直すべきだろうか？ 元の値を保存する FlagKeep が必要そうだ。

元の値を保存する？ それって、単位元では？ ということは、Monoid に昇格するべきでは？

その通りだ。

data FlagOp = FlagSet | FlagClear | FlagReset | FlagKeep deriving (Eq,Show)

instance Semigroup FlagOp where
    op <> FlagKeep = op
    _ <> op = op

instance Monoid FlagOp where
    mempty = FlagKeep

data Config = Config { aflag :: FlagOp, bflag :: FlagOp } deriving (Eq,Show)

instance Semigroup Config where
    Config a1 b1 <> Config a2 b2 = Config (a1 <> a2) (b1 <> b2)

instance Monoid Config where
    mempty = Config mempty mempty

setAFlag :: Config
setAFlag = Config { aflag = FlagSet, bflag = mempty }

setBFlag :: Config
setBFlag = Config { aflag = mempty, bflag = FlagSet }

使ってみよう。

> setAFlag <> setBFlag 
Config {aflag = FlagSet, bflag = FlagSet}

めでたし、めでたし。

なお、僕は「設定はMonoidであるべき」宗派ではなく、「デフォルトの設定に対して変更関数を用意すべき」宗派なので、あしからず。

TLS 1.3 開発日記 その29 Key update

TLS 1.2で暗号路の鍵を更新する場合は、ハンドシェイクをやり直す(再ネゴシエーションする)必要があった。実装の視点からいうと、鍵更新はハンドシェイクに対して同期的だった訳だ。

TLS 1.3では、サーバやクライアントがハンドシェイクをし直すことなく、いつでも鍵を更新できる。(TLS 1.3 には再ネゴシエーションはない。)つまり、鍵更新はハンドシェイクに対して非同期的になった。プログラマーにとっては、腕が試されることになる。

TLS 1.3の鍵更新メッセージの書式は、以下のように定義されている。

enum {
    update_not_requested(0), update_requested(1), (255)
} KeyUpdateRequest;

struct {
    KeyUpdateRequest request_update;
} KeyUpdate;

典型的な使い方はこうだ：

1. AがKeyUpdate(update_requested)を送り、送信側の鍵を更新
2. BはKeyUpdate(update_requested)を受け取ったら受信側の鍵を更新し、KeyUpdate(update_not_requested)を送り、送信側の鍵を更新
3. AがKeyUpdate(update_not_requested)を受け取ったら、受信側の鍵を更新

AとBが同時にKeyUpdate(update_requested)を送ってもよく、その場合、単に2回鍵が更新された状態に落ち着く。

さて、問題はここからだ。

私は update_not_requested を update_requested への応答だと解釈していた。そこで、update_requested を送信してない状態で、update_not_requested を受け取ると、エラーにしていた。しかし、レビュアーの Olivier さんから、一方向の更新も許されるのではないかと指摘を受けた。そう思った理由は、OpenSSL の s_client が、

• k コマンドの場合、一方向の鍵を更新しようとし (update_not_requested を送信)
• K コマンドの場合、双方向の鍵を更新しようとする (update_requested を送信)

からだった。

slack のTLS 1.3の実装者が集まるチャンネルに話題を振ったところ

• 許されていない：無視すべき
• 許されていない：エラーにすべき
• 許されている

の3つの解釈が出てきて、やはり仕様が曖昧だと分かった。

結局、編集者の Eric さんが降臨し、「許されている」と言って決着した。

結論：TLS 1.3 では、一方向の鍵更新もOK！