[Haskell] - あどけない話

自分で定義するデータの中には、足し算したくなるようなデータがある。たとえば、送信と受信のカウンターを定義したとしよう。

data Metrics = Metrics {
    rx :: Int
  , ts :: Int
  } deriving (Eq, Show)

これは以下のように足し算できると嬉しいだろう。

> Metrics 1 2 + Metrics 3 4
Metrics {rx = 4, ts = 6}

しかしこれは Num のインスタンスにすべきではない。このデータ型に掛け算は定義できないからだ。かといって、addMetrics みたいな関数を定義するのはかっこ悪い。

> Metrics 1 2 `addMetrics` Metrics 3 4
Metrics {rx = 4, ts = 6}

このように演算子が一個だけ欲しいと思ったら、それは多分 Monoid だ。

import Data.Monoid

instance Monoid Metrics where
    mempty = Metrics 0 0
    Metrics r1 t1 `mappend` Metrics r2 t2 = Metrics (r1 + r2) (t1 + t2)

GHC 7.10までは、(<>) が mappend の別名であるので、以下のようなコードが書ける。

> Metrics 1 2 <> Metrics 3 4
Metrics {rx = 4, ts = 6}

やったね！

GHC 8.4へようこそ

上記のコードを GHC 8.4 で読み込むと以下のようなエラーが出る。

Example.hs:8:10: error:
    ・ No instance for (Semigroup Metrics)
        arising from the superclasses of an instance declaration
    ・In the instance declaration for ‘Monoid Metrics’
  |
8 | instance Monoid Metrics where
  |          ^^^^^^^^^^^^^^

これはどういうことだろう？その疑問に答えるのがこの記事の主旨である。

mappendよりも(<>)の方がかっこいいのに、長い間 (<>) はMonoidのメソッドにはしてもらえなかった。あくまで別名であった。それは一部の人に、SemigroupをMonoidのスーパークラスにするという野望があったからだ。

数学での定義を思い出そう：

半群 (Semigroup)

結合則: (a <> b) <> c = a <> (b <> c)

モノイド (Monoid)

結合則: (a <> b) <> c = a <> (b <> c)
単位元：e <> a = a <> e = a

群 (Group)

結合則: (a <> b) <> c = a <> (b <> c)
単位元：e <> a = a <> e = a
逆元：a <> inv a = e

さっきの疑問に答えると、GHC 8.4ではSemigroupがMonoidのスーパークラスとなり、Metricsに対する(<>)の定義がないために、エラーが出たという訳だ。

状況把握

今後どのようなコードを書けばよいかという疑問に答えるためには、GHCの各バージョンでの状況を把握しなければならない。

GHC 7.10 (base 4.8)

GHC 7.10 では、みなさんご存知のように base パッケージに Data.Monoid モジュールがある：

-- base : Data.Monoid
class Monoid a where
    mempty :: a
    mappend :: a -> a -> a

(<>) :: a -> a -> a
(<>) = mappend

Monoid型自体はPreludeの仲間入りを果たしたが、(<>)は明示的にimportする必要がある。

Data.Semigroupは、semigroupsパッケージで定義されている：

-- semigroup : Data.Semigroup
class Semigroup a where
    (<>) :: a -> a -> a

default (<>) :: Monoid a => a -> a -> a
  (<>) = mappend

最後の default は、DefaultSignatures という拡張で、Monoidの制約を持てば Semigroupの方の (<>) は mappend で代用できると読む。親子関係がひっくり返っていて、なんだかなぁという感じである。

GHC 8.0 (base 4.9)

Data.Semigroupがsemigroupパッケージからbaseパッケージへ移った：

-- base : Data.Monoid
class Monoid a where
    mempty :: a
    mappend :: a -> a -> a

(<>) :: a -> a -> a
(<>) = mappend

--base : Data.Semigroup
class Semigroup a where
    (<>) :: a -> a -> a

親子関係はない。

フラグ -Wnoncanonical-monoid-instances が定義された。これは、MonoidのインスタンスなのにSemigroupのインスタンスになってないと警告を出すフラグである。デフォルトは off。上位互換性に関するフラグ -Wcompat を付けても、警告が出る。

まだ GHC 8.4 を使えない人は、-Wall の横に -Wcompat を書き足して遊んでみるとよい。

GHC 8.2 (base 4.10)

何も変更なし。嵐の前の静けさだ。

GHC 8.4 (base 4.11)

なんとなんと、MonoidとSemigroupがPreludeの仲間に入った。そして、SemigroupがMonoidのスーパークラスとなった。

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

class Semigroup a => Monoid a where
  mempty :: a

訂正：SemigroupがMonoidのスパークラスになったために、(<>) を定義してないとエラーが出るようになった。嵐がやってきたのだ。

対処方法

ここまで解説すれば、対処方法は明らかであろう。Semigroup (as superclass of) Monoid Proposalの最後に、semigroupsパッケージを使う方法と使わない方法が載っているので、よく眺めてほしい。

Permalink | コメント(2) | トラックバック(0) | 14:29

2018-02-14

TLS 1.3 開発日記その25 picotls

TLS, Haskell

kazuho さんが実装を進めている picotls を使う方法のまとめ。picotls は TLS 1.3 のみを実装している。またデフォルトで利用できる ECDHE は P256 のみである。

インストール

cmakeが必要なので、あらかじめインストールしておく。master ブランチが draft 23。

% git clone https://github.com/h2o/picotls
% cd picotls
% git submodule init
% git submodule update
% cmake .
% make

これで、トップディレクトリに "cli" というコマンドができる。"cli" は、サーバにもクライアントにもなる。

picotls サーバ

% ./cli -k $SOMEWHERE/key.pem -c $SOMEWHERE/certificate.pem 127.0.0.1 13443

picotls クライアント

Full:

% ./cli 127.0.0.1 443

HRR:

最初はkey_shareを空にして送るという裏技を使う

% ./cli -n 127.0.0.1 443

PSK:

最初の -s オプションでチケットを保存し、次の -s オプションでチケットを読み込む。

% rm ticket
% cli -s ticket 127.0.0.1 443
% cli -s ticket 127.0.0.1 443

0RTT:

% rm ticket
% cli -s ticket 127.0.0.1 443
% cat early-data.txt - | cli -s ticket -e 127.0.0.1 443

Permalink | コメント(0) | トラックバック(0) | 14:57

2018-01-16

TLS 1.3 開発日記その24 ID23

TLS, Haskell

ID23での変更点：

key_share拡張

Canonのプリンターが40を使っていることが判明したので、key_share拡張の値を40から51へ変更。

signature_algorithms_cert拡張

signature_algorithmsに加えてsignature_algorithms_cert拡張を新設した。CertificateVerify用がsignature_algorithms、証明書用がsignature_algorithms_cert。signature_algorithms_certがなければsignature_algorithmsで代用する。

PSSを分割した。たとえばrsa_pss_sha256は、rsaEncryption用のrsa_pss_rsae_sha256とRSASSA-PSS用のrsa_pss_pss_sha256に分かれた。

不変条件

不変条件が加筆された：

クライアントは提案したものは必ず実装してないといけない
サーバはわからないものは単に無視(異常終了してはいけない)
TLSを終端するミドルボックスはその両方を満たせ
単にリレーするミドルボックスは中身を触るな

CSS

状態を持たないサーバは、一番目と二番目のClientHelloの間に到着するCSSを無視すること。

静的なRSA

静的なRSAは、Bleichenbacher-type攻撃を防止するために使用不可にすべき。

Permalink | コメント(1) | トラックバック(0) | 12:57

2017-12-12

goな関数

Haskell

これは「Haskell (その2) Advent Calendar 2017」の1日目の記事です。遅くなってすいません。

読者として末尾再帰ぐらいは理解しているHaskellerを想定しています。

トップレベルとローカル関数

再帰を用いて関数を書いているとき、トップレベルで再帰するか、ローカル関数で再帰するか、ときどき迷う。この記事では、僕なりの判断基準を示したい。

Data.Listで定義されている再帰が必要な関数は、ほとんどがトップレベルで再帰している。代表例のmapの例を見てみよう。

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

mapをローカル関数を使う実装にしてみよう。この記事では、ローカル関数名としてgoを用いる。(loopを使う流儀もある。)

map' :: (a -> b) -> [a] -> [b]
map' f xxs = go [] xxs
  where
    go acc []     = acc
    go acc (x:xs) = go (acc ++ [f x]) xs

Haskellerなら、(++)を使いリストの末尾に要素を追加していることに違和感を覚えるだろう。

以前、NTT Dataで利用されたHaskellドリルが話題となった。全体的にはよいのだけれど、上記のmap'のように、必ずwhereの中にローカル関数を定義させていたことには賛同できなかった。

Haskellを習得する際は、リストプログラミングから入ることが多く、初心者はどうしてもトップレベルで再帰しがちである。Haskellドリルには、これを矯正する効果が多少はあるかもしれない。

一方、ローカル関数で再帰する例として、以下のコードを取り上げる。

udpLookup :: ByteString
          -> Socket
          -> Int
          -> (DNSMessage -> Bool)
          -> Int
          -> (Socket -> IO DNSMessage)
          -> IO DNSMessage
udpLookup query sock tm checkSeqno retry rcv = go 0 False
  where
    go cnt mismatch
      | cnt == retry = if mismatch then
                         E.throwIO SequenceNumberMismatch
                       else
                         E.throwIO RetryLimitExceeded
      | otherwise    = do
          mres <- timeout tm (send sock query >> rcv sock)
          case mres of
              Nothing  -> go (cnt + 1) False
              Just res
                | checkSeqno res -> if trunCation $ flags $ header res then
                                      E.throwIO TCPFallback
                                    else
                                      return res
                | otherwise      -> go (cnt + 1) True

このコードの意味は分からなくてもよいが、このコードをトップレベルでの再帰に書き直してみると、次のようなことが分かるだろう。

引数の数が多くなって、再帰の際に変化する引数がどれなのパッと見分からなくなる
蓄積変数など本来関数に閉じているべきパラメータを外に見せなければならなくなる

さてさて、トップレベルとローカル関数を使い分ける基準はあるのだろうか？

遅延評価とトップレベル

Data.Listの関数がトップレベルで定義されているのは、遅延評価と関係がある。私は遅延評価のファンではない。なぜなら、遅延評価が役立つ場面は、以下の3つしかないからである。

リスト処理
CASでの変数の更新
純粋性のテスト

Haskellのデフォルトの評価戦略が正格評価だったらよかったのにと思う。ただし、遅延評価がリスト処理に役立つのは間違いない。狭義の意味では、関数プログラミングはリストプログラミングであるから、関数プログラミングに遅延評価が必要であると勘違いしやすい。

Haskellで構造が遅延する一般的なデータ型はリストかData.Sequenceぐらいである。Data.Mapでさえ構造は遅延しない。私の定義では、関数プログラミングとは不変データプログラミングである。Haskellでは、構造が正格な不変データが多いので、デフォルトは正格評価であってほしい。

デフォルトを正格評価にするStrict/StrictDataプラグマは、GHC 8.0で実装された。GHC 8.4がリリースされれば、3つのメジャーバージョンを保守するポリシーでは GHC 7.x を捨てられるので、Strict/StrictDataプラグラマを活用できるようになるだろう。

前置きが長くなったが、遅延評価がリスト処理に役立つ例を見てみよう。以下は、map とhead を組み合わせた例である。

   head $ map (+1) [1,2,3,4,5]
-> head (2 : map (+1) [2,3,4,5])
-> 2

mapでは、トップレベルで再帰しているため、構造を再帰の外で作っている。そのため、遅延評価の下では無駄な計算が起こらない。一方、ローカル関数を使うmap'だと次のようになる。

   head $ map' (+1) [1,2,3,4,5]
-> head [2,3,4,5,6]
-> 2

という訳で、リストを生成する関数はトップレベルで再帰するべきである。

ローカル関数の利点

では、リストを生成しない関数はどうだろうか？上記のローカル関数を使う関数をトップレベルに書き換えたときの欠点が、ローカル関数を使う関数の利点であるから：

再帰の際に変化する引数がどれなのかパッと見て分かる
関数に閉じているべきパラメータを外に見せなくて済む

実は、もう一つ性能が良くなるという利点もある。Haskellの通常のデータはポインターで指されており、即値ではない。Intであろうと本当の値はポインターで指されている。トップレベルの再帰に、たとえば Int を使うと、関数を呼び出すごとにポインターをたどることになる。公開されている関数の引数は、即値に最適化できないからである。

ローカル関数を使うと、コンパイラは最適化に積極的になれる。

ローカル関数の引数は、可能であれば即値が使われる
ローカル関数から見たトップレベルの引数も可能であれば即値が使われる

こういう形式をWorker Wrapperと言って、プログラマーが少し手助けすることでコンパイラーに最適化を促す手法の一種である。たとえば、udpLookupなら、go が Worker、udpLookup が Wrapper である。

まとめ

結論はいたって簡単だ。

リストを生成する関数はトップレベルで再帰せよ
それ以外の関数ではローカル関数で再帰せよ

Permalink | コメント(8) | トラックバック(0) | 12:42

% git clone https://boringssl.googlesource.com/boringssl
% cd boringssl
% mkdir build && cd build && cmake -GNinja .. && ninja bssl

ビルドは感心するほど速い！

BoringSSLサーバ

% tool/bssl server -tls13-variant draft28 -accept 13443 -key $SOMEWHERE/key.pem -cert $SOMEWHERE/certificate.pem -loop -early-data

追記：-tls13-draft22-variantはなくなったようだ。

追記：-tls13-variant は引数を取るようになった。

BoringSSLクライアント

Full：

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443

HRR：

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443 -curves P-521:x25519

PSK：

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443 -test-resumption

0RTT：

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443 -test-resumption -early-data @$SOMEWHERE/early-data.txt

Permalink | コメント(0) | トラックバック(0) | 15:34

あどけない話

2018-03-06

あなたの知らないSemigroupの世界

GHC 8.4へようこそ

半群 (Semigroup)

モノイド (Monoid)

群 (Group)

状況把握

GHC 7.10 (base 4.8)

GHC 8.0 (base 4.9)

GHC 8.2 (base 4.10)

GHC 8.4 (base 4.11)

対処方法

2018-02-14

TLS 1.3 開発日記その25 picotls

インストール

picotls サーバ

picotls クライアント

2018-01-16

TLS 1.3 開発日記その24 ID23

key_share拡張

signature_algorithms_cert拡張

不変条件

CSS

静的なRSA

2017-12-12

goな関数

トップレベルとローカル関数

遅延評価とトップレベル

ローカル関数の利点

まとめ

2017-12-05

TLS 1.3 開発日記その23 BoringSSL

インストール

BoringSSLサーバ

BoringSSLクライアント