Go で Package を Build

• うまくいかなくなったビルドが元通りにうまくいくようになったので、とりあえずそのメモ

$ env | grep GO
GOROOT=/usr/local/Cellar/go/1.5.1/libexec
GOPATH=/Users/nishidy/.go

$ head -n1 *go
==> count.go <==
package ParseWikipediaXML

==> parse.go <==
package ParseWikipediaXML

==> redis_client.go <==
package ParseWikipediaXML

==> tfidf.go <==
package ParseWikipediaXML

$ cp *.go $GOROOT/src/ParseWikipediaXML/

$ ls $GOROOT/src/ParseWikipediaXML/
count.go  parse.go  redis_client.go  tfidf.go

$ go build -x ParseWikipediaXML
WORK=/var/folders/py/ckd84qtn5gz415br68fzzz6w0000gn/T/go-build372571907
mkdir -p $WORK/ParseWikipediaXML/_obj/
mkdir -p $WORK/
cd /usr/local/Cellar/go/1.5.1/libexec/src/ParseWikipediaXML
/usr/local/Cellar/go/1.5.1/libexec/pkg/tool/darwin_amd64/compile -o $WORK/ParseWikipediaXML.a -trimpath $WORK -p ParseWikipediaXML -complete -buildid fbfb2249b3c733faf3613e823f1ae8ca07ba6fb3 -D _/usr/local/Cellar/go/1.5.1/libexec/src/ParseWikipediaXML -I $WORK -I /Users/nishidy/.go/pkg/darwin_amd64 -pack ./count.go ./parse.go ./redis_client.go ./tfidf.go

$ go install -x ParseWikipediaXML
WORK=/var/folders/py/ckd84qtn5gz415br68fzzz6w0000gn/T/go-build655772754
mkdir -p $WORK/ParseWikipediaXML/_obj/
mkdir -p $WORK/
cd /usr/local/Cellar/go/1.5.1/libexec/src/ParseWikipediaXML
/usr/local/Cellar/go/1.5.1/libexec/pkg/tool/darwin_amd64/compile -o $WORK/ParseWikipediaXML.a -trimpath $WORK -p ParseWikipediaXML -complete -buildid fbfb2249b3c733faf3613e823f1ae8ca07ba6fb3 -D _/usr/local/Cellar/go/1.5.1/libexec/src/ParseWikipediaXML -I $WORK -I /Users/nishidy/.go/pkg/darwin_amd64 -pack ./count.go ./parse.go ./redis_client.go ./tfidf.go
mkdir -p /usr/local/Cellar/go/1.5.1/libexec/pkg/darwin_amd64/
mv $WORK/ParseWikipediaXML.a /usr/local/Cellar/go/1.5.1/libexec/pkg/darwin_amd64/ParseWikipediaXML.a

# すると以下にスタティックライブラリが作成される

$ ls $GOROOT/pkg/darwin_amd64/ | grep ParseWikipediaXML
ParseWikipediaXML.a

# あとはこれをimportすれば良い

$ cat main.go
package main

import (
   pxml "ParseWikipediaXML"
...
)
...

$ go build -x main.go
WORK=/var/folders/py/ckd84qtn5gz415br68fzzz6w0000gn/T/go-build988424706
mkdir -p $WORK/command-line-arguments/_obj/
mkdir -p $WORK/command-line-arguments/_obj/exe/
cd /Users/nishidy/Documents/git/ParseWikipediaXML/go/main
/usr/local/Cellar/go/1.5.1/libexec/pkg/tool/darwin_amd64/compile -o $WORK/command-line-arguments.a -trimpath $WORK -p main -complete -buildid 6d5db34fe7bb1b4b80c5e874d09cbbd020df25ab -D _/Users/nishidy/Documents/git/ParseWikipediaXML/go/main -I $WORK -pack ./main.go
cd .
/usr/local/Cellar/go/1.5.1/libexec/pkg/tool/darwin_amd64/link -o $WORK/command-line-arguments/_obj/exe/a.out -L $WORK -L /Users/nishidy/.go/pkg/darwin_amd64 -extld=clang -buildmode=exe -buildid=6d5db34fe7bb1b4b80c5e874d09cbbd020df25ab $WORK/command-line-arguments.a
mv $WORK/command-line-arguments/_obj/exe/a.out main

# ファイルを更新した場合は、作成したライブラリを消して再ビルド

$ rm GOROOT/pkg/darwin_amd64/ParseWikipediaXML.a
$ cp *.go $GOROOT/src/ParseWikipediaXML/
$ go build ParseWikipediaXML
$ go install ParseWikipediaXML
$ go build main.go

# ライブラリを消すのにgo cleanは使えない

$ go clean -x ParseWikipediaXML
cd /usr/local/Cellar/go/1.5.1/libexec/src/ParseWikipediaXML
rm -f ParseWikipediaXML.test ParseWikipediaXML.test.exe
$

# go get したものは$GOPATH以下にインストールされる

$ ls $GOPATH
bin  pkg  src

$ cat main.go
package main

import (
   pxml "github.com/nishidy/ParseWikipediaXML"
...
)
...

# すると$GOPATHがsearch pathに追加される

$ go build -x main.go 
WORK=/var/folders/py/ckd84qtn5gz415br68fzzz6w0000gn/T/go-build264272204
mkdir -p $WORK/command-line-arguments/_obj/
mkdir -p $WORK/command-line-arguments/_obj/exe/
cd /Users/nishidy/Documents/git/ParseWikipediaXML/go/main
/usr/local/Cellar/go/1.5.1/libexec/pkg/tool/darwin_amd64/compile -o $WORK/command-line-arguments.a -trimpath $WORK -p main -complete -buildid b461d8c26a7bd15d8303385abe3e39199b894a08 -D _/Users/nishidy/Documents/git/ParseWikipediaXML/go/main -I $WORK -I /Users/nishidy/.go/pkg/darwin_amd64 -pack ./main.go
cd .
/usr/local/Cellar/go/1.5.1/libexec/pkg/tool/darwin_amd64/link -o $WORK/command-line-arguments/_obj/exe/a.out -L $WORK -L /Users/nishidy/.go/pkg/darwin_amd64 -extld=clang -buildmode=exe -buildid=b461d8c26a7bd15d8303385abe3e39199b894a08 $WORK/command-line-arguments.a
mv $WORK/command-line-arguments/_obj/exe/a.out main

$ /usr/local/Cellar/go/1.5.1/libexec/pkg/tool/darwin_amd64/compile --help
...
  -I directory
        add directory to import search path
...

Erlang で Process の Join

• Erlang(BEAM)のProcessは、他言語でThread.Joinのようなスレッド・プロセスの終了を待つ機能が無さそうなので、Receiveを用いたメッセージパッシングで実装した
• 今回は、Preforkモデルのように予めProcessをワーカースレッド的に起動しておく実装ではなく、軽量なグリーンスレッドを活用して必要なパラメータが用意できた時点で次々にProcessをSpawnしていく実装を用いている
• 計算すべきパラメータが尽きた時点でプログラムが終了してしまう可能性があるため、起動したProcessが完了したうえでプログラムが終了することを保証するためにJoinが必要になる

process_wait(Num,LastPid) ->
    receive
        {add, _} -> process_wait(Num+1,LastPid);
        {done,_} when Num == 1 ->
            case LastPid of
                {true,Pid} -> Pid ! {complete,self()};
                {false,_} -> process_wait(Num-1,LastPid)
            end;
        {done,_} -> process_wait(Num-1,LastPid);
        {join,Pid} when Num == 0 -> Pid ! {complete,self()};
        {join,Pid} -> process_wait(Num,{true,Pid})
    end.

• プロセスの状態を管理するprocess_waitに対して、Processの起動直前にaddを送信、Processの終了時点でdoneを送信、プログラムの終了時点でjoinを送信してreceiveで返信を待機、という三種類のメソッドをアトムで実現するように、送信されるメッセージに対してガードを定義する
• LastPidタプルに格納されるPidはtrueの場合のみ取り出して使用することにし、その用途はcompleteを返信することでreceiveによるJoinを完了させる（これによって動き出す）
• joinを送信したときに初めてLastPidにPidを登録してそのフラグをtrueに設定することによって、最後にProcessが終了した際に、joinを送信したプロセスに対してメッセージを送ることができる
• completeの返信は、Num==0になるタイミング、かつ、一度でもjoinを受けた後、という条件でなければ発動しない
• registerを使えばSpawnしたProcessのPidを関数呼び出しの度に引き回す必要もなく、グローバルにアクセスできるアトムを紐付けておくことができるので使い勝手が良い

ISUCON5から学ぶいろいろ

ISUCON5のエントリを見てるとたくさん得られることがある。コンテストといっても、実際に課題になった技術は単に知っているだけのものとは違って、手を動かして実際に実装してみないといけないな、と思わせるには十分なインパクトがある。単に知っているだけのことと、自分ではなくても誰かが実装して失敗して諦めて成功して、という過程を見ていると、自分が知っていたことがとても浅いことに気付いたりして、思わぬ収穫というより大きな収穫がある。

並列化

• お題は、クライアントからのリクエストが、複数の外部APIサーバへのリクエストになるマイクロサービス。Goであれば、goroutineを使って書けるので並列化は難しくない。
• Goでセマフォ（ロックカウント＞1）を実現する場合は、sync.WaitGroupを使う必要があるのだと思っていたけど、sync.Mutexでもいけるようだ？

ISUCON5本戦にてスコアトップの18万点でfailしました - Qiita

HTTP/2

• HTTPSを使っている外部APIサーバがあって、同じトークンでリクエストを並列化するとToo Many Requestsが返ってしまうという罠で、HTTPSで待ち受けているのは理由があって、これは実はHTTP/2を話せるサーバなので、HTTP/2を使えば並列化が可能というトリック。
• HTTP/1.1では、リクエストとレスポンスの対応がその順序でしか取れない（ためにHTTPパイライン上におけるHoL問題が発生する）が、HTTP/2ではストリーム単位でIDが振られるので（TCP上におけるHoL問題は残るものの）並列化がうまくいく。
• HTTP/2はクライアント側のフィックスされた実装がまだまだ言語毎に出揃っていないことが露呈した様子。node.jsはnghttp2がある。

Last-Modified / If-Modified-Since

• レスポンスにLast-Modifiedヘッダが付加されていたコンテンツ（あるいは付加されていない場合もあり得る？）は、クライアント側からリクエストを投げる際にIf-Modified-Sinceによって、コンテンツ自体に変化があったかどうかを問い合わせる。変化していない場合に、クライアントはサーバから304 Not Modifiedを受け取ることで、クライアントはキャッシュしているコンテンツを利用することができる。つまり、外部APIサーバには500msecの遅延が挿入されていた、ということだから、これによって1msecから数msec程度にまでRTTが短縮されることになる。
• HTTPヘッダのCache-Controlは効果としてはこれに良く似ており、max-ageでキャッシュとして有効な期間をあらかじめ指定でき、この期間を過ぎるまではサーバに問い合わせを行わなず即座にキャッシュされたコンテンツを利用できる。またno-cacheは、キャッシュしたコンテンツに対するETAGをサーバに送って検証することで、Last-Modifiedと同様の効果を得ることができ、no-storeは、クライアント側にキャッシュさせないよう指示する。

Sinatra ENV = production

• sinatra/sinatra · GitHubにIn the "production" and "test" environments, templates are cached by default.という記載があった。配信するtemplateとしてwww.yahoo.co.jpのHTMLを使い、ローカルでSinatraのウェブサーバをRACK_ENV=production指定有り・無しで起動して、abテストをパラメータは適当に決めて実行してみた結果、3倍くらい速くなっていることが分かる。

$ RACK_ENV=production ruby WebView.rb

$ sudo ab -n 1000 -c 2 http://127.0.0.1:4567/bench
Time per request:       5.543 [ms] (mean)
Time per request:       2.772 [ms] (mean, across all concurrent requests)
Transfer rate:          6767.21 [Kbytes/sec] received

$ ruby WebView.rb

$ sudo ab -n 1000 -c 2 http://127.0.0.1:4567/bench
Time per request:       15.486 [ms] (mean)
Time per request:       7.743 [ms] (mean, across all concurrent requests)
Transfer rate:          2422.46 [Kbytes/sec] received

キャッシュ戦略

• 静的コンテンツと思いきや、数秒毎に更新されるAPIがあるので、キャッシュに有効期限を付ける必要がある。memcachedにはTTL（Expiration）を指定できるので、それで対応したチームがほとんどという印象。
• キャッシュが切れた直後に、並列化された外部APIアクセスが一斉にバックエンドに対して発生する現象を、CacheのThundering Herdと呼ぶ。キャッシュの期限が短い場合、そのタイミングでバックエンド側へのアクセスが増えるために性能が上がらないという結果になる。バックエンド側の同一エンドポイントへのアクセスを束ねるか、常にキャッシュを最新に保つスレッドをバックグラウンドで動かしておくか、という対策が必要になる。
• キャッシュの更新というと、最近ホット*1なVarnishのPURGEを思い付くが、PURGEは予めTTLを設定していなくとも任意のタイミングでキャッシュをクリアするためのAPI。

ISUCON 5 決勝の天気APIの解説 - Qiita

MySQL Engine = BLACKHOLE

• id:songmuさんの過去のエントリ（ISUCON1）で神の一手として登場。Engine=BLACKHOLEはWriteもReadも常に成功するが、実際にはテーブルに対する変化はメモリ上でもディスク上でも、何も起こらない。ただ、ステートメントベースのバイナリログにはクエリが残るので、レプリケーション先のスレーブでReadに対するウォームアップ（メモリにロード）が出来る。

おそらくはそれさえも平凡な日々: #isucon で優勝させてもらってきました

Gzip化

• サイズの大きなコンテンツを圧縮することによって、トラヒック流量の削減に貢献できる。これによってCPU使用率は上がるので、トレードオフを考えてサイズの大きいコンテンツに対して適用することで効果がある。

静的コンテンツ配信

• ユーザに依存しない静的なコンテンツの配信を、アプリサーバからリバースプロキシに委ねることによって、アプリサーバの負荷を低減する。

*1:CDNスタートアップのFastlyが使っていることでも更に株が上がった感がある Fastly社に行ってきた ー 動的コンテンツの定義を変えるCDN？ | API guy

アンアラインメントデータアクセスについて

• メモリにデータを格納する際、通常はアラインメントに沿って展開される。ワード単位以上のデータを格納する場合、その開始アドレスがワード単位の整数倍になっていないと、メモリフェッチが余分に発生してスループットが落ちるか、アラインメント違反によってエラーが発生するか、アクセスしたデータが異常となり期待していない挙動を引き起こす。
• x86では、アラインメントに沿っていないアドレスにアクセスする場合、メモリフェッチが余分に発生するが、アラインメント違反は起こらない。ARM/Linuxでは、アラインメント違反が発生するが、/proc/cpu/alignmentに設定されている値に従って結果として発生する挙動が変わる。

0	例外を無視
1	例外をdmesgに出力
2	例外を捕捉して正常にアクセスする
3	1+2
4	例外を受理してバスエラーを起こす
5	1+4

c.f. Linux Kernel Documentation :: arm : mem_alignment

• 構造体structは各フィールドの中で最大のアラインメントに併せてパディングを入れてメモリを確保する。ただし、__attribute__((packed)) を指定した場合はパディングを入れない。なお、共用体unionは各フィールドでメモリを共有する。
• gcc/clangでは__attribute__((aligned(byte)))によってアラインメントをマニュアルで調整することができる。C++11(C++0x)では言語の機能として、alignas(byte)が導入されている。

c.f. ホイール欲しい ハンドル欲しい » C++11 alignas/alignof メモリアライメント

$ cat align.c 
#include <stdio.h>

int main(int argc, char* argv[])
{

    char a[16] = {"abcd"};
    unsigned int *b,*c,*d;
    b = (unsigned int *)(a);
    c = (unsigned int *)(a+2);
    d = (unsigned int *)(a+3);

    printf("char a %s\n",a);
    printf("int b %u\n",*b);
    printf("int c %u\n",*c);
    printf("int d %u\n",*d);

    printf("char a addr %p\n",a);
    printf("int b addr %p\n",b);
    printf("int c addr %p\n",c);
    printf("int d addr %p\n",d);

    struct s1 {
        char i;
    } s1;

    struct s2 {
        int j;
    } s2;

    struct s3 {
        char i;
        int j;
    } s3;

    struct s4 {
        char i;
        int j;
    } __attribute__((packed)) s4;

    union u4 {
        char i;
        int j;
    } u4;

    struct s5 {
    char i;
    __attribute__((aligned(8))) int j;
    }  s5;

    printf("s1 size %zu\n",sizeof(s1));
    printf("s2 size %zu\n",sizeof(s2));
    printf("s3 size %zu\n",sizeof(s3));
    printf("s4 size %zu\n",sizeof(s4));
    printf("u4 size %zu\n",sizeof(u4));
    printf("s5 size %zu\n",sizeof(s5));

    printf("s3 addr %p\n",&s3);
    printf("s3.i addr %p\n",&s3.i);
    printf("s3.j addr %p\n",&s3.j);

    printf("s4 addr %p\n",&s4);
    printf("s4.i addr %p\n",&s4.i);
    printf("s4.j addr %p\n",&s4.j);

    printf("u4 addr %p\n",&u4);
    printf("u4.i addr %p\n",&u4.i);
    printf("u4.j addr %p\n",&u4.j);

    printf("s5 addr %p\n",&s5);
    printf("s5.i addr %p\n",&s5.i);
    printf("s5.j addr %p\n",&s5.j);

    s3.i = 'a';
    s3.j = 65535;

    printf("s3.i %c\n",s3.i);
    printf("s3.j %d\n",s3.j);

    s4.i = 'a';
    s4.j = 65535;

    printf("s4.i %c\n",s4.i);
    printf("s4.j %d\n",s4.j);

    return 0;
}

$ ./a.out 
char a abcd
int b 1684234849
int c 25699
int d 100
char a addr 0x7fff504e5130
int b addr 0x7fff504e5130
int c addr 0x7fff504e5132
int d addr 0x7fff504e5133
s1 size 1
s2 size 4
s3 size 8
s4 size 5
u4 size 4
s5 size 16
s3 addr 0x7fff504e50f0
s3.i addr 0x7fff504e50f0
s3.j addr 0x7fff504e50f4
s4 addr 0x7fff504e50e8
s4.i addr 0x7fff504e50e8
s4.j addr 0x7fff504e50e9
u4 addr 0x7fff504e50e0
u4.i addr 0x7fff504e50e0
u4.j addr 0x7fff504e50e0
s5 addr 0x7fff519cb0b0
s5.i addr 0x7fff519cb0b0
s5.j addr 0x7fff519cb0b8
s3.i a
s3.j 65535
s4.i a
s4.j 65535

$ uname -a
Darwin MBA.local 14.5.0 Darwin Kernel Version 14.5.0: Wed Jul 29 02:26:53 PDT 2015; root:xnu-2782.40.9~1/RELEASE_X86_64 x86_64

Thanks to

ARM gcc バッドノウハウ集: アラインメント

データ型のアラインメントとは何か，なぜ必要なのか？

Note : []演算子について

• 配列arrayと[]演算子に与える添字iにおいて、arrayとiは交換可能である。つまり、array[i]とi[array]は等価である。これは[]演算子をコンパイラが*(array+i)に変換しているためである。

    int i[4] = {1,2,3,4};
    int j=1;

    printf("i[j] %d\n",i[j]);
    printf("j[i] %d\n",j[i]);
    printf("1[i] %d\n",1[i]);
    printf("*(i+j) %d\n",*(i+j));

~~~

i[j] 2
j[i] 2
1[i] 2
*(i+j) 2

32ビットコンピュータをやさしく語る　はじめて読む486 (アスキー書籍)

30日でできる! OS自作入門

MySQLのグループコミットとそれに連想するもの

グループコミット

• MySQLでは、バイナリログへの書き込みのタイミングを、sync_binlogによってユーザが指定することができる。具体的にはsync_binlogの値によって、何回コミットを行ったらバイナリログをディスクにフラッシュするか、を指示するため、sync_binlog=1を設定することでコミット毎にバイナリログをディスクにフラッシュすることができ、耐障害性を上げることができる。ただし、その結果として書き込み性能は下がることになる。sync_binlog=0を設定することで、バイナリログのフラッシュのタイミングをOSに委ねることにより書き込み性能は上がるが、マスタの障害時には、マスタ側では最新の内容をディスクに保存できているにも関わらず、スレーブ側に最新の状態でレプリケーションすることが出来ず、マスタとスレーブで一貫性が保てなくなる。

• MySQL5.6では、複数コミットをまとめた上で、バイナリログのフラッシュを実施するための機能である、グループコミットのsync_binlog=1の場合の性能が向上されている。これにより、sync_binlog=1を設定していても、書き込み性能をそれほど落とすことなく運用することが可能になった。グループコミットにおける複数コミットのまとめ方は、あるトランザクションAにおいてディスクへのフラッシュが行われている間に、別のトランザクションBがそのフラッシュを待っている間、また別のトランザクションCがフラッシュを行おうとした際に、Aによるフラッシュが完了した際に、BとCをまとめてフラッシュすることによって、書き込み性能を上げるものである。

アグリゲーション

• 複数コミットをまとめることで性能を上げるのは、アグリゲーションによる最適化手法と言える。例えば、無線LANにおいて802.11nでは、フレームを複数まとめて一つのフレームとして送信するA-MSDU/A-MPDUというアグリゲーション手法（ヘッダ圧縮）が取り入れられており、これによってスループットが向上している。この場合、どのようにMACフレームをまとめているのか、という点を考えてみると、アクセスポイントからフレームを送信する際、CSMA/CAにおけるキャリアセンスによってチャネルが占有されていることを検知して送信タイミングをインターバル＋バックオフの分だけ遅延する場合、その間にアクセスポイントに到達した宛先が同じフレームをまとめ上げて一つのフレームを形成し、次にチャネルが空いているタイミングで送信している、と考えられる。あるいはもっと単純に、送信レートが低い場合などは、一つのフレームを送信している間に別のフレームが到達するケースも考えられる。

• しかし、チャネルが一つのアクセスポイントによって占有できる場合、あるいは受信感度が良く最大送信レートを持続できる場合、あるフレームの送信中に別のフレームが到達する頻度が少なくなるため、アグリゲーションが起きづらい、ということが考えられる。そうなると、チャネルの状態が悪い場合（より混雑している、距離が遠いことなどによって、より受信感度が悪い）の方が、アグリゲーションによる恩恵によってスループットが上がるケースもあり得る、と考えることができる。ただし、最大スループットを測定するようなベンチマークの場合は、アグリゲーションが起きやすくなっているため、このような逆転は起こらない、とも考えられる。

• アグリゲーションなど、リソースを蓄積するための期間を設ける必要がある手法を用いる場合に、その期間がある定まった値になると、必ずその期間だけ遅延が挿入されていることになる。下のリンクで紹介されているPostgreSQLに実装されていたcommit_delayが、それに当たるのではないかなと推測している。スループットとRTTは別々のベンチマークが必要になることには注意が必要である。

Nagle Algorithm

• もう一つ「まとめる」と聞いて連想するのが、TCPのNagle Algorithm。小さいデータをまとめて一つのパケットとして送ることによって、パケット数を減らす効果がある。ACK待ちの場合に、次のMSS以下のサイズのデータはすぐには送らずに、ACKが来るまで待って、一つのパケットに詰め込んで送る。ただしこれも諸刃の剣であり、利点としてパケット中のヘッダに対するペイロードの割合が上がるので帯域使用率は上昇するものの、欠点としてはリアルタイム性が下がるので、アプリケーションによっては問題になる。Nagle Algorithmによる遅延を回避するためには、ソケットオプションにTCP_NODELAYを指定する。

Thanks to

Yoshinori Matsunobu's blog: Making slave pre-fetching work better with SSD

Haskellのパース処理（文字コードについて）

文字コードについて

• Unicodeは文字集合である。Unicodeで規定される文字を、UTF-8やUTF-16などの符号化方式で扱うことができる(e.g. Shift-JISやEUC-JPは別の文字集合を扱う)。Unicodeでは文字集合を、コードポイントという各文字に対する通し番号のようなもので管理する。コードポイントは符号化方式を意識しておらず、すなわち符号化されたバイト列ではない（バイト列は符号化方式によって決まる）。

• UTF-16は、文字を16bit単位で表すための符号化方式で、ASCII非互換である。最小単位が2byteであるため、ビッグエンディアンか、リトルエンディアンか、で符号化されたバイト列の解釈が変わってしまうため、エンディアンを示すBOM(バイトオーダーマーク)をテキストデータの先頭に付加する。ただしUTF-16BE・UTF-16LEという符号化方式では、符号化方式自体でそれを示しており、BOMは付加されない。HaskellではChar型の値を内部的にUTF-16として扱うUnicodeのコードポイントとして保持する*1。UTF-16では、1符号（2byte）で文字を表す場合、Unicodeのコードポイントをそのまま使う。2符号（4byte）で文字を表す場合、サロゲートコードポイント（コードポイントとして割り当てられていないU+D800 から U+DFFFの範囲）をペアで使うため、サロゲートペアと呼ばれる。

• Haskellのprintの出力はUnicodeのコードポイントを10進数で出力する。ただし、putStr|putStrLnは、端末のロケールに関する環境変数を参照して、文字コードをUnicodeのコードポイントから変換して表示するので、その環境の文字コードがUnicodeを扱う符号化方式であれば、端末上で正しく表示できる。

• UTF-8は、文字を8bit単位で表すための可変長の符号化方式で、ASCII互換である*2。先頭ビットが0の場合は8bitx1、110の場合は8bitx2、1110の場合は8bitx3、11110の場合は8bitx4、という長さで1文字を表す。

Prelude> print "あいうえお"
"\12354\12356\12358\12360\12362"
Prelude> putStrLn "あいうえお"
あいうえお
Prelude> 
Leaving GHCi.
$ echo $LANG
ja_JP.UTF-8

• Thanks to

Unicode のサロゲートペアとは何か - ひだまりソケットは壊れない

Yapafi/charset.mkdn at master · Songmu/Yapafi · GitHub

文字コード表(Unicode UTF-8 UTF-16) [7000/21420] - [技術資料 + 技術資料] ぺんたん info

Unicode 〜UTF-8、UTF-16との違い〜（文字コード関連） | 読み物 | ウナのIT資格一問一答

• 下段のリンクにあるように、Windowsアプリで文字コードとして"Unicode"が選択肢にあるのが混乱の一端。

Text.Regex.Posixについて

• 正規表現を扱うためのモジュール。=~が定義されており、自由に型を指定することで、マッチング有無（Bool）やマッチした文字列（String）、マッチした回数（Int）を取り出すことができる。
• ただし、UTF-8の全角スペース（0xE8,0x80,0x80）が含まれる場合、マッチングがうまくいかなくなる*3。

Prelude> import Text.Regex.Posix
Prelude Text.Regex.Posix> "a1b2c3" =~ "[a-z]" :: Int
Loading package array-0.4.0.1 ... linking ... done.
Loading package deepseq-1.3.0.1 ... linking ... done.
Loading package containers-0.5.0.0 ... linking ... done.
Loading package bytestring-0.10.0.2 ... linking ... done.
Loading package transformers-0.4.3.0 ... linking ... done.
Loading package mtl-2.2.1 ... linking ... done.
Loading package regex-base-0.93.2 ... linking ... done.
Loading package regex-posix-0.95.2 ... linking ... done.
3
Prelude Text.Regex.Posix> "<tag>aaa bbb</tag>" =~ "</tag>" :: Bool
True
Prelude Text.Regex.Posix> "<tag>aaa　bbb</tag>" =~ "</tag>" :: Bool
False
Prelude Text.Regex.Posix> "<tag>aaaあbbb</tag>" =~ "</tag>" :: Bool
True

• 他にもいろいろ制限がありそう

$ cat re_test.hs
import Text.Regex.Posix
type S = String
main = do
    case "aaa   bbb ccc" =~ "([a-z]*) *([a-z]*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

    case "aaa   bbb ccc" =~ "([^ ]*)[ ]*([^ ]*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

    case "aaa   bbb ccc" =~ "([a-z]*) *([a-z ]*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

    case "aaa   bbb ccc" =~ "([^ ]*)[ ]*([^ ]* ?[^ ]*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

    case "aaa   bbb ccc" =~ "([a-z]*)\\s*([a-z]*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

    case "aaa   bbb ccc" =~ "([\\S]*) *(\\S*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

    case "aaa   bbb ccc" =~ "([\\S]*)\\s*(\\S*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

    case "aaa   bbb ccc" =~ "([\\S]*?)\\s*(\\S*)" :: (S,S,S,[S]) of
        (a,b,c,d) -> putStrLn $ a++":"++b++":"++c++":"++(show d)

$ runghc re_test.hs
:aaa   bbb: ccc:["aaa","bbb"]
:aaa   bbb: ccc:["aaa","bbb"]
:aaa   bbb ccc::["aaa","bbb ccc"]
:aaa   bbb ccc::["aaa","bbb ccc"]
:aaa:   bbb ccc:["aaa",""]
::aaa   bbb ccc:["",""]
::aaa   bbb ccc:["",""]
re_test.hs: user error (Text.Regex.Posix.String died: (ReturnCode 13,"repetition-operator operand invalid"))

Text.Parsecについて

• 文字列のパース処理についてはText.Parsecが使いやすい。使い方についてはUnbui.ltが分かり易い。モナドのdo記法をDesugarした考察が載っていて親切。

Text.ParserCombinators.Parsec.Prim.many: combinator 'many' is applied to a parser that accepts an empty string

• Parsecを使い始めた当初、単語を取り出すパーサを書いてみたが、実行時に上記のエラーとなった。これは、セパレータの定義において、Parsec.many ""を受理してしまっていたからだと思われる。Parsec.manyは0以上のパターンにマッチするので、パターンとして空文字列を渡してしまうと、パターンマッチが永久に終わらない。*4

Look ahead

• Parsecを使って、例えばXMLのtextタグ<text property='hoge'>blah blah ... </text>からpropertyを意識せずにコンテンツを取り出したい場合、以下のex1.hsのbadparserのように書けそう*5だが、これはうまくいかない。これは、Parsecのマッチングでは性能的な理由から先読み（Look ahead）をせず、一つずつマッチング対象の文字を調べていく。これをconsumeと呼び、マッチングに成功した文字を二度と使わない、という点がうまく表現されている。つまり、textタグが現れるよりも前に他のタグ<page>などが存在した場合、<は<textの先頭にマッチするものの、その次のpはtextの先頭にはマッチしないのでエラーとなり、そこでマッチングが終了してしまう。
• そこで、Parsec.tryを使うと、consumeスタイルのマッチングにエラーが発生した場合でも、改めてマッチングをやり直してくれるため、ex1.hsのgoodparserのようにうまくいく*6。

--ex1.hs 
import Text.Parsec as P

badparser = do
    P.manyTill P.anyChar (P.string "<text")
    P.manyTill P.anyChar (P.char '>')
    P.manyTill P.anyChar (P.string "</text>")

goodparser = do
    P.manyTill P.anyChar (P.try $ P.string "<text")
    P.manyTill P.anyChar (P.char '>')
    P.manyTill P.anyChar (P.try $ P.string "</text>")

main = do
    let text = "<page>Page content.<text property='hoge'>Text <b>conntent.</b></text></page>"

    case P.parse badparser "" text of
        Right text -> putStrLn text
        Left err -> putStrLn $ show err

    case P.parse goodparser "" text of
        Right text -> putStrLn text
        Left err -> putStrLn $ show err

$ runghc ex1.hs 
(line 1, column 1):
unexpected "p"
expecting "<text"
Text <b>conntent.</b>

ByteStringとData.Textについて

• String型は、Char型のリストであるためメモリ効率が悪く、文字列操作の性能は高くない*7。そのため、Unicodeを扱う場合、IOからメモリ効率の良いByteString型として読み込み*8、それを使いやすいData.Text型に変換して使用するのが良いようだ*9。
• ByteStringを使ってバイト単位から文字コードを生成することもできる。ByteStringとして読み込んだUnicodeのバイト列をString型に変換（してメモリ上に配置）するにはutf8-stringパッケージを利用する。

-- ex2.hs 
import qualified Data.ByteString as B
import Codec.Binary.UTF8.String as C

main = do
    putStrLn $ C.decode [0xE3,0x81,0x82]
    putStrLn $ C.decode $ B.unpack $ B.pack [0xE3,0x81,0x82]

$ runghc ex3.hs 
あ
あ

• c.f.

Haskell Tips (文字列編) - りんごがでている

Haskell Character Data · GitHub

Languageプラグマについて

• プラグマはGHCの拡張機能で、Languageプラグマは言語に関する機能を拡張する。デフォルトではコード中の文字リテラルはString型として扱われるが、{-# LANGUAGE OverloadedStrings #-}を付けることによって文字リテラルをString型以外の型として扱うことができる。以下のコードは、Languageプラグマを付けないとコンパイルエラーとなる。ByteString型は1文字を1バイトで格納するため、UTF-8で符号化された*101文字3バイトの文字コードを格納しきれず、1バイトに切り詰められていることが分かる。

-- ex3.hs
{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString as B
import qualified Data.Text as T

a :: T.Text
b :: B.ByteString
c :: String

a = "あいうえお"
b = "あいうえお"
c = "あいうえお"

main = do

    print a
    print b
    print c

    print $ T.length a
    print $ B.length b
    print $ length c

$ runghc ex3.hs 
"\12354\12356\12358\12360\12362"
"BDFHJ"
"\12354\12356\12358\12360\12362"
5
5
5

• c.f.

10. プラグマ - とりあえず雑記帳

補足： Python2とPython3の文字型の扱いについて

• Python2系とPython3系では文字型の扱いが異なっている。
  • Python2 : 文字型は、エンコーディングされたバイト列を保持する。ただし、uフラグ*11をつけたリテラルは、ユニコード文字型として、Unicodeのコードポイントを保持する。
  • Python3 : 文字型は、Unicodeのコードポイントを保持する、ただし、bフラグをつけたリテラルは、バイト型*12として0<=x<256の間の整数値のシーケンスを保持する。256以上のコードポイントが割り当てられている文字（ASCIIで扱える文字以外）は、バイト型として扱えないことに注意。

• つまりPython3では文字列は全て内部的にUnicodeのコードポイントとして保持される。そのため、Unicodeの文字集合を扱わない符号化方式で符号化されたファイルを読み込む場合は、encodingを指定してUnicodeのコードポイントに変換する必要がある。（ASCIIのみの場合はバイト列として保持しておくことも可能）

• Thanks to

Python2 と Python3 の数値、文字列データの取り扱い：ある nakagami の日記：So-netブログ

*1:Unicodeに対応しているため、Char型では1文字に対して4バイトが割り当てられるらしい お気楽 Haskell プログラミング入門

*2:UTF-8が扱える範囲は8bitx6までだが、実際に使われているのは8bitx4まで。

*3:全角スペースの問題はこちらに報告済みText.Regex.Lazy / Bugs / #4 Strange behaviour with some non-ASCII symbols。問題はそれだけではなさそうだが。

*4:しかし、当時のコードはどこかへいってしまい再現する方法がない。それにしても、うまく「文字数字シングルクオーテーションハイフン以外」をセパレータのパターンとして指定する方法が分からない...

*5:do式では、最後の式の結果がdo式の値となるので、それ以外の式の結果は単に捨てられている。

*6:Parsecの場合はコンテンツ部分に全角スペースが存在していてもマッチングに問題は無かった。単にText.Regex.PosixがUnicodeに非対応なだけ？

*7:大きなサイズのファイルの内容を読み込む際、String型はhGetLineを使って手軽に行ごとに読み込める利点はある。

*8:ByteStringはWord8と呼ばれる1バイトの単位で管理される。

*9:なお、lengthの計算時間は、StringではO(N)、ByteStringはO(1)らしい。 Haskellライブラリ入門 (2011年版) - あどけない話

*10:エディタ（Vim）の設定は : set enc? encoding=utf-8 である

*11:フラグ？

*12:イミュータブルなbyte型か、ミュータブルなbytearray型、の区別がある

純粋関数型言語 Haskell 基礎まとめ

すごいHaskellたのしく学ぼう！

Haskellを学ぶ上で難しいのは、その概念が高度に抽象化されている点にある*1。そのため、矛盾の無い説明が難しい。自分なりに解釈した上で説明すると、どこかに矛盾が入り込み、説明しづらい。それが読み手にとって理解を難しくしていると思う。それと、何が嬉しいのか、が分からない。これは、様々な型インスタンスを使った事例を読む必要がある。現時点の自分なりの主観と選択が入った説明であれば、以下のようになる。

遅延評価

Haskellでは値が具体的に必要になるまで評価しない。標準関数を使ったxs = repeat xは、全ての要素がxの無限リストを作成して、それをxsに束縛するが、これはエラーにならない。head xsはこの無限リストの先頭の要素を返す。length xsは無限リストの要素数を評価する必要があるので、これは計算が終わらない。このようにHaskellでは、本当に必要となるまで、出来る限りその場では評価せずに遅延させる。*2

カリー化

ある多引数関数の一部の引数のみを部分適用することで、その関数を元にした新たな関数を作ることができる。 仮に、多引数関数が禁止されている世界*3で、多引数関数を実現しようとすると、その世界では引数を一つずつ適用していくしかない。 そうやって、部分的に実引数が渡された新たな関数を作りながら、最終的に全ての引数を適用した結果を取得することができる。 カリー化というのは、多引数関数の引数を先頭のものから一つずつ適用していくことで、部分適用された関数を取得していきながら、最終的に結果を取得することができるような手法を概念として表したようなものと考えることができる。 Haskellの関数の型表記において、'->'が引数と戻り値で区別なく使われている点を見てもそのことが分かる。どのような関数であっても引数の先頭から一つずつ適用するしかないからだ。

Prelude> :t (*)
(*) :: Num a => a -> a -> a
Prelude> :t (* 10)
(* 10) :: Num a => a -> a

Prelude> :{
Prelude| let myfunc :: Int -> Int -> Int -> Int
Prelude|     myfunc x y z = x + y + z
Prelude| :}
Prelude> :t (myfunc)
(myfunc) :: Int -> Int -> Int -> Int
Prelude> :t (myfunc 1)
(myfunc 1) :: Int -> Int -> Int
Prelude> :t ((myfunc 1) 2)
((myfunc 1) 2) :: Int -> Int
Prelude> :t (((myfunc 1) 2) 3)
(((myfunc 1) 2) 3) :: Int

文脈

Maybe型は、計算が失敗するかもしれない、という「文脈」のついた値を示す型である。計算が成功した場合はJustにくるんで、例えばJust 10を返し、計算が失敗した場合はNothingを返せばよい。もしMaybe型を扱うことができる関数があれば、計算が失敗したかどうかを、C言語で返り値がNULLであるかを分岐でチェックするような、手続き的な処理を書く必要がなく、統一的に扱うことができる。

IO型は、外の世界（副作用の存在する世界）という「文脈」のついた値を示す型である。 リスト[]は、非決定性という「文脈」がついた値を示す型、と考えることもできる。複数の値を持っており、そのどれが値なのかが決定的でない、という意味である。

このように、Haskellには様々な「文脈」を表す型が存在し、同時にそれらを統一的に扱う手法も提供されている。

参照透過性

Haskellは純粋関数型言語なので、副作用のある関数は許さない。ある関数にある実引数を適用した場合、その結果は常に同じである、という「参照透過性」があることを前提とする。

しかし、それだとIOが処理できない。実行するたびに関数が返す結果が変わる可能性があるからである。

そのために文脈（型）IOを使う。IO型は、「副作用がある」という文脈を値に与える。とにかくIOを含む処理は、IO型にまかせる必要があり、その値は文脈を考慮したまま計算に使用する必要がある。

ファンクター

ある文脈の付いた値に対して、文脈の付かない値を引数にとる通常の関数が適用できる方がよい。例えばMaybe型の値Just 10に対して(*10)を適用することで、Just 100が手に入る方が、Maybe用の非常に良く似た*maybeみたいな、内部で文脈を解釈する関数を用意する必要がなく、使い勝手が良い。そのためには、Maybe型にfmap関数を定義して、fmap (*10) Just 10とすることで望み通りJust 100が手に入るようにすれば良い。また、これはMaybe型に限った話ではなく、他の文脈を表す型でも同じである。そのために抽象化した上位の型として、ファンクタ型Functorがある。MaybeやIO、リストはFunctorのインスタンスであるためfmapが定義されており、このfmapを使うことによって、文脈の付いた値を文脈を考慮しない関数に適用することができる。

アプリカティブファンクター

今度は(*10)ではなく[(*10)]を適用したいとする。リストが関数を要素として持っており、それをなんらかの文脈の付いた値に適用したい場合である。文脈から関数を取り出して、それをファンクタのように、ある文脈の付いた値に適用し、そして文脈を付けて返す。

そのためにアプリカティブファンクタ型Applicativeは、<*>を定義*4している。この演算子は、例えばリストではfs <*> xs = [ f x | f <- fs, x <- xs ]とリスト内包表記を用いて定義されており、これはリストから関数を取り出して、それぞれの関数をリストの値に適用する。

Prelude> :m Control.Applicative
Prelude Control.Applicative> (myfunc) <$> [1,2,3] <*> [10,20,30] <*> [1,-1,0]
[12,10,11,22,20,21,32,30,31,13,11,12,23,21,22,33,31,32,14,12,13,24,22,23,34,32,33]

なお、(myfunc) <$>はfmap myfuncと等価である。良く使う表現であるため、演算子<$>が定義されている。

Prelude Control.Applicative> :t (<$>)
(<$>) :: Functor f => (a -> b) -> f a -> f b
Prelude Control.Applicative> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

モノイド

モノイドはファンクタやアプリカティブファンクタと異なり、具体型をインスタンスとする型クラスである。

memptyは単位元を示す定数*5である。単位元とは、*であれば1、+であれば0、である。 mappendは同じモノイド同士を'二項演算'して新たなモノイドを返す関数を定義する。かなり抽象的な表現だが、appendとあるにもかかわらず型によっては'結合'とは言えない演算もあるので、このように表現している。 mconcatはデフォルト実装が与えられており、foldr mappend m aである。複数のモノイドから、単一のモノイドを作る。

モナド

モナドは、ある値をある文脈に入れて返す関数f :: a -> m bを相手にする。これが、ファンクタやアプリカティブファンクタと異なる点である。ある文脈の付いた値m aを、その関数に適用することを考える。そのためにモナド型Monadは、バインドと呼ばれる>>=を定義している。

Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m 

また、Monadはreturnを定義している。これは、他言語におけるreturnとは全く違い、Haskellのreturnは値をモナドに包んで返す関数、である。

Prelude> :t (return)
(return) :: Monad m => a -> m a

Maybeやリスト、IOなどは全てモナド型の型インスタンスである。

モナドが嬉しいのは、ある文脈の付いた値が複数あるときに、それらに対して次々に関数を適用していけるところである。

Prelude> Just 10 >>= \x -> return (x*10) >>= \y -> return (y+10)
Just 110

do記法

モナドを扱うための、より表現力のある記法を構文糖衣として提供する。doブロックでは、演算子<-を使ってモナドから値を取り出して変数に束縛できるので、命令型（手続き型）のスタイルでコーディングができる。doブロックの最後の式の結果が、doブロック全体の結果となる。

do
    x <- Just 10
    y <- return (x*10)
    z <- return (y+10)
    return z

Prelude> do { x <- Just 10; y <- return (x*10); z <- return (y+10); return z }
Just 110

その他の演算子

<*>や<$>、>>=、<-、->の他に頻出の演算子として$と.がある。$は単なる関数適用である。ただし、最低の優先度で、右結合になるので、つまり右辺を先に評価しろ、という指令となり、優先順位を変える()を右側に付けるのを省略することができる。.は関数合成であり、( f . g . h ) a = f ( g ( h a ) )である。map(fmap)などの高階関数に渡す際に便利である。

c.f.

このサイトの絵を見て、それ以上でも以下でもないところに、なるほど、と思えるようになったら、それがモナドを理解した一つの指標になるのではないかな、と思う。

モナド - ウォークスルー Haskell

*1:どのくらい抽象度が高いかというと、ハトとイワシは、二つの目と一つの口を持つ点が共通している、と言ってしまうくらい。魚類と鳥類だから全然違う生き物じゃないか、と思ってしまいそうなものだが。

*2:なおlengthはリストの要素数だけに興味があるので、実際には各要素そのものの評価は行われない。これは、例えばx=1/0であったとしてもエラーにならないことを意味する

*3:レジスタの特別な制限などにより！

*4:言葉の意味が重複しないように説明すると、これは抽象メソッドのようなものであると言える。つまり、インターフェースを与えているのだ。ただ、具体的な実装が与えられる場合もあるし、型インスタンスの方で実装しなければいけない場合もある。なお<*>は、具体的な実装は与えられていない

*5:引数の無い関数は定数と同じように扱える