NCurses の Crystal binding を作った
この記事は、 Crystal Advent Calendar 2016 の８日目の記事です。 qiita.com
ncurses という CUI を作るためにスクリーンやキー入力を扱う有名なライブラリの Crystal binding を作りました。
ほとんど C の ncurses と同じ感じで使えるようになっていると思います． Ruby や Python の curses ライブラリを参考にしつつ，なるべく使用感がかわらないようにしています．
examples
require “ncurses” NCurses.open do NCurses.cbreak NCurses.noecho NCurses.move(x: 30, y: 20) NCurses.addstr(“Hello, world!”) NCurses.refresh NCurses.notimeout(true) NCurses.getch end
NCurses.addstr とか NCurses.move とかは ncurses で言う addstr や move に当たる関数で，stdscr に対して waddstr とか wmove するやつです．
w = NCurses::Window.new(height: height, width: width) とすることで subwindow が作れます．
w.addstr や w.move という形で w prefix な関数たちが呼べるようになっています．
pad や attron / attroff などなども使えます．
詳細な例は example/ 以下のにおいてあります
なぜ作ったのか
実は ncurses bindings for Crystal はすでにあります．(https://github.com/jreinert/ncurses-crystal)
curses が Crystal の標準ライブラリから外されることが決まったときの CHANGELOG を見ると，今後はそっちを使ってねと書いてあったりします．
じゃあなんでわざわざ別で作ったのかという話ですが，API が足りない & 提供する API の形を変えたいと思ったからです．
単純に bind されている API が少なくてやりたいことができなかったので，最初は追加して PR を出そうと思っていたのですが，すでに提供されている API が割と高級になっていて 1 : 1 で C API と対応していない感じでした． 個人的には C library の wrapper にはなるべく薄くなっていてもらって基本的な API は覚え直さないでも使えるようになっていてほしいというふうに思ったので，C API と 1 : 1 で対応した形の API を提供する wrapper を作ってみようという経緯で新しく作ることにしました．
おまけ
C bindings を書くときに，wrapper API として LibC::Int が登場しちゃうのがなんとなく嫌で，LibC::Int を C が要求してくる関数を呼ぶ wrapper 関数には型指定をあえてしないという選択をしたんですがどうなんでしょう．
lib LibNCurses fun wmove(w : Window, y : LibC::Int, x : LibC::Int) : Result end
class Window def move(y, x) LibNCurses.wmove(@win, y, x) end end
みたいな感じです．（多少簡略化しています）
これどうなんですかね．なるべく外に見せる API には型を明記するようにしたかったのですが，LibC:Int 系は環境によって異なるのでそういうわけにも行かず…
y : LibC::Int, x : LibC::Int とかは別に良いんですが，ncurses は文字と属性をくっつけた chtype なる型を持っていてこれが結構厄介というか混乱を招くのではと思っています．
chtype は char ではなく unsigned int で，文字と属性を bitor でくっつけたものになっています．addch のように char をとることを連想させる関数の引数が実は chtype = unsigned int でしかも Crystal の文字型 Char は 32bit なのでものすごく混乱します…
C は型変換を勝手にやってくれるので，unsigned int を返す関数から受け取った値を short を受け取る関数に渡すみたいなことをよくやっていて，Crystal のような型変換を暗黙にやらない言語から使おうとすると難しいんだなぁと思いました．
なにか良い方法があればぜひ知りたいです．
Rust で Box に包まれた構造体の所有権分解
ちょっとはまったのでメモ
struct A { foo: Vec<i32>, bar: Vec<bool>, }
こんな構造体があったとする。
普通、A の所有権を分解して foo と bar にしたいときは
fn xxx(x: A) -> (Vec<i32>, Vec<bool>) { let A { foo, bar } = x; (foo, bar) }
とやれば良い（この例だともっと簡単に書ける気もするけど）
一方、Box<A> から foo と bar に分解したい場合は話が変わってくる。
fn error1(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
(x.foo, x.bar)
}
fn error2(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
let A { foo, bar } = *x;
(foo, bar)
}
これらは両方共コンパイルできない。
人間から見ると，Box<A> は A の所有権を持っているのだから、A -> foo/bar に分解できるなら Box<A> も同様にできる気がする。
実際にはこのようにするとコンパイルが通る。
fn success(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
let x = *x;
let A { foo, bar } = x;
(foo, bar)
}
うーん、エラーになるケースだと Deref トレイトの機能を経由している感じになるのかな？
Deref 経由で foo の所有権をとるとその時点で Box<A> の所有権は奪われちゃうから bar の所有権が取れないということなのだと想像した。
success のようなコードが突然出てきたら混乱しそうだ。
日本語の改行を適当にいい感じにするツールを作りました
必要に迫られて、HTML ページ内の改行位置をいい感じにするツールを作ってみました。
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。
しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。
最も有名な問題として、今すぐダウンロー
ド問題が挙げられます。
japawrap を使うと、それっぽく日本語を解釈して <span> でくくるみたいなことができます。inline-block を適用すれば改行がそれっぽく入るようにできます。
Install
go get github.com/agatan/japawrap/...
で japawrap コマンドが使えるようになります。
Usage
CLI
ファイル名を指定するか標準入力から流し込みます。
$ echo "今日も元気です" | japawrap <span class="wordwrap">今日も</span><span class="wordwrap">元気です</span>
このように適宜いい感じに wrap してくれます。
オプションとして -open string と -close string をサポートしているので、
$ echo "今日も元気です" | japawrap -open '<span style="display: inline-block;">' -close "</span>" <span style="display: inline-block;">今日も</span><span style="display: inline-block;">元気です</span>
みたいなことができます。
Library
一応 japawrap はライブラリとしても使用できるようになっています。
w := japawrap.New(open, close) s := "今日も元気です" fmt.Println("%s => %s", s, w.Do(s))
これだけです。
Example
では実際に使った結果を下に記したいと思います。 文章は、上の方に自分で書いた文章をそのまま使います。
before
HTMLに長文を書くと、親DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
after
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
こんな感じになります。猛烈に効果がわかりにくくて驚いていますが、一応効果はちゃんと出ているのではないでしょうか？ HTMLを直接見ていただければどうなっているかはわかると思います。
次に青空文庫から夏目漱石「こころ」の序文を抜粋してみたのが下の画像たちです。
レスポンシブ！それなりになっている気がします。
あとがき
この問題へのアプローチとして、https://github.com/google/budou が有名だと思います。
budou は Cloud Natural Language API を内部で使っていて、しっかり日本語の文章を構文解析しているようです。
なので非常に精度は高いと思うのですが、今僕の GCP アカウントがごにょごにょしていてぱぱっと試せる状況ではなかったので自作しました。
budou と違ってしっかり構文解析などはしていなくて、形態素解析した後、それっぽく分割しているだけです。なので精度は落ちると思います。
一方、budou は GCP の credentails が必要だったりと準備が必要になるので、お手軽に試せるというのは悪くないかなと思っています。
Rust の Result と Iterator
Rust には失敗するかもしれない値を表す Result<T, E> という型があります。
std::result::Result
そして iterate できることを表す Iterator という trait があります。
std::iter::Iterator
また、Iterator trait は要素型を表す関連型を持ちます。例えば
ここ間違っていました。String は Iterator<Item=char> を impl しています。これは char 型を要素にもつ Iterator であることを意味します。String が直接 Iterator を impl しているのではありませんでした。
たまに Iterator<Item=Result<T, E>> のようになっている型を見かけます（T, E にはなにかしら具体的な型が入っていると思ってください）。
例えば、std::io::stdin().bytes() の返り値である std::io::Bytes は Iterator<Item=Result<u8>> を impl しています。
（ちょっとわかりにくいのですがここでの Result は std::result::Result ではなくて std::io::Result です。std::io::Result は std::result::Result<T, std::io::Error> のエイリアスです。）
さて、このような Iterator からすべての要素が Ok(_) であれば Ok<Vec_>> を、Err(_) があれば Err<_> を返すような処理を書きたいということは割りとよくあります。
で、これを一生懸命実装しようとしていたのですが、標準ライブラリの範囲内ですでに実装されていました。べんり。
let result = std::io::stdin().bytes().collect::<Result<Vec<_>, _>>();
これだけです。これで要件を満たす Result<Vec<_>, _> が返って来ます。すばらしい。
タネは簡単な話で Result が FromIterator trait を impl しているので collect で変換が可能であるというお話でした。
std::iter::FromIterator
値と参照について
「値」と「参照」という言葉があります。 このへんの言葉について、今の理解をまとめておこうと思います。 言葉の定義や理解が誤っている部分があればご指摘ください。
まず、前提として以下では、「値」ベースの言語として C, C++, Rust などを、「参照」ベースの言語として Java, C#, Ruby などを想定しています。 （もちろん言語によってはハイブリッドなものもあります: Crystal, Go, D, ...）
そもそも「値」「参照」とは
「値」は「実体」、「参照」は「実体へのポインタ」です。
int の配列みたいなものを考えてみます。
[1, 2, 3] をメモリ上にどう表現できるでしょうか。
配列ですから、単純にメモリ上のどこかに以下のような領域を作ればよさそうです。
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
これが「値」であり配列の実体です。 そして、実体の配置されたメモリ領域へのポインタが「参照」です。
スタック上の表現
さて、プログラム上ではこの配列のようなオブジェクトを、ローカル変数としてスタック上で表現したり、関数に引数として渡したりします。 では、スタック上での配列の表現はどうなっているのか考えてみます。
ここで、「値」と「参照」という言葉が重要になります。
「値」ベースな言語では、スタック上に
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
をそのままべたっと配置します。
一方で、「参照」ベースな言語では、ヒープ上に
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
を配置し、スタック上では実体へのポインタという表現になります。 （必ずしもヒープに置くとは限らない？処理系や最適化によってはスタックに置くこともありえる？とにかくローカル変数などの表現としては実体へのポインタという形をとるということ）
値渡し・参照渡し
値渡しとか参照渡しという言葉があります。
以下に擬似コードを一つ書いてみます。（C 風に書いていますが C ではないと思ってください）
void inc_age(Person p) { p.age++; } Person john = Person { "john", 20 }; inc_age(john); print(john.age); // => ??
このコード、処理系が「値」ベースか「参照」ベースかで結果が異なります。
「値」ベースの場合
値ベースの言語の場合、inc_age の引数に john を渡した時には、inc_age 内のローカル変数（引数） p のために、john のコピーが作られます。
inc_age 内で p.age++ としていますが、p は john のコピーであって john ではありませんから、inc_age から戻ってきて john.age を参照しても 20 のまま変化が無いはずです。
したがって結果として 20 が出力されます。
「参照」ベースの場合
参照ベースの言語の場合、john 変数のメモリ上での表現は、ヒープに置かれた Person { "john", 20 } というオブジェクトへのポインタになります。
inc_age にこれを引数として渡すと、ポインタの値がコピーされますから、p と john は同じオブジェクトを参照しているポインタになります。
p.age++ とすると p が参照するオブジェクトが変更されます。これは john が参照するオブジェクトと同一ですから、john.age も 21 に変化します。
したがって結果として 21 が出力されます。
C の場合
C の場合、ポインタが直接表現できますから、参照渡しの挙動を模倣することができます。
void inc_age(Person *p) { p->age++; } Person john = Person { "john", 20 }; inc_age(&john); print(john.age); // => 21
p が Person* 型であること、そして inc_age に john のアドレスを渡していることに注目してください。
この場合、p は john を参照するポインタですから、結果は 21 になります。
C++ の場合
C++ の場合、言語機能として「参照渡し」という機能があります。
void inc_age(Person& p) { p.age++; } Person john = Person { "john", 20 }; inc_age(john); print(john.age); // => 21
p が Person& 型であること、inc_age には john をそのまま渡しているように見えることに注目してください。
これは C++ の提供する機能で、コンパイルすると、Person& は実質 Person* と同じ表現になります。
p->age ではなく p.age と書けること、&john ではなく john のままで参照渡しが実現できるようになっています。
単純なポインタを使っても同じことが出来ますが、ポインタと違って nullptr になることがないという特徴があります。
参照のハマりやすい点
個人的に参照ベースの言語でハマりやすいなと感じるのは以下のようなコードです。
void some_function(Person p) { p.age++; p = new Person("bob", 30); } Person p = new Person("john", 20); some_function(p); println(p.name); // => john println(p.age); // => 21
p.age++ の部分は呼び出し元のオブジェクトに反映されるのに、p = new Person(...) の部分はなんで反映されないの！ってなります。（なりません？）
本質的にポインタの値渡しにすぎないんだということを理解していればまぁ納得なのですが...
（ちなみに C++ や D の参照渡しだと p = new Person(...) 的なコードも呼び出し元に反映されます。）
値のハマりやすい点
ハマりやすいというか、気がつかないままパフォーマンスが悪くなりやすいのが値ベースの言語の弱点でしょう。
void print_object(HugeObject obj) { printf("%s\n", obj.name); } HugeObject obj = ...; print_object(obj);
このようなコードを書くと、ただ名前を表示するだけの関数が激重になる可能性があります。 値ベースの言語では、引数として値を渡すとまるっとそのコピーをつくりますから、不要にもかかわらず巨大な値のコピーを作ってしまいます。
まとめ
「ムーブセマンティクス」とか「immutable と参照」とかについてまとめようと思ったのですが、前提として「値」「参照」についてまとめていないと書きにくいなと思ったのでまとめておきました。
内部表現を知ることでハマりやすい点の回避にもつながると思うので、この辺はきちんと理解しておきたいです。
再帰的 grep ツール crepe を作っています
再帰的にパスをたどりながらパターンにマッチする行を検索する grep 系のツールを作っています。
有名どころとしては、ack とか ggreer/the_silver_searcher(ag) とか monochromegane/the_platinum_searcher とか tkengo/highway なんかがあります。群雄割拠ですね。
これらの有名ツール達はそれぞれ特徴があって(速さとか出力形式とかエンコード対応とか)便利に使わせていただいております。
今回 crepe を作ろうと思った理由は、なんとなく C++ でちゃんとスレッド立てて並行処理みたいなコードを書いてみたくなったからです。
速度等も測っていないのでどこまで意味があるのか怪しいのですが、とりあえず現状 3 つの仕事を並列に動かしています。
一つ目は出力を担当するスレッドで、マッチ結果を受け取って出力するだけです。
二つ目はマッチを担当するスレッドで、ファイル名と FILE* を受け取ってマッチ結果を生成し出力担当スレッドに渡します。
三つ目はパスを walk するスレッドで、ディレクトリを掘りながらファイルを開いてマッチスレッドに送ります。
現状はまだ部分一致の matcher しか実装していないので正規表現や fuzzy マッチは未実装です。
標準入力かパスから部分一致する行を探してきて出力します。
出力形式は ag に近い形式で、ファイルごとにグループ分けして行番号とともに出力します（オプションでこの辺の挙動はいじれるようにはなっています）
バイナリファイルっぽいファイルはスキップするようになっています。
やりたいこと
最終目標として crepe は peco のような interactive な検索を実装してみたいなと思っています。
ag と peco の組み合わせで云々みたいなユースケースが割りとあるなぁと思ったので。
ただこれメモリ使用量とか速度上の制約からまともに働くのかはよくわかっていません。
単純に考えると、ユーザが一文字入力するたびにファイルの read からやり直す必要があるので...
入力ファイルが多すぎた場合にどこまでキャッシュするのかとかその辺を相当うまくやらないと死ぬのでは？という気がします。
短期的な目標としては
- .gitignore 対応 (意外とめっちゃ面倒で苦しんでいます)
- fuzzy マッチ
- 正規表現マッチ
あたりから順にやっていきたいなと思っています。とりあえずこっちからやろうかなと思います。
というわけで気合を入れる意味も込めて記事にしました。プルリクやフィードバック大歓迎なのでぜひよろしくお願いします。
C++ で result 型を作る
Haskell や Rust など多くの強力な型システムを持つプログラミング言語は、Either とか Result といった「失敗するかもしれない」計算の値を示す型を持っています。
現在の C++ の標準ライブラリにはこのような型はありませんので、それを自作してみようというわけです。
ちなみに現在策定中のC++17には std::optional が入ることが決定しているようです。これは、result と同様に失敗するかもしれな値を示しますが、失敗した原因がなんなのかを通知する仕組みを持っていません。
そもそもどういう型か
Rust の Result 型を例にみてみます。
enum Result<V, E> { Ok(V), Err(E), }
Rust における Result 型はだいたいこんな感じで定義されています。
Result は型引数を２つとります。V が成功時の値で、E が失敗時のエラー情報です。
例えば、fn parse_int(s: &str) -> Result<isize, String>; は、文字列を受け取り、それが整数としてパース出来れば isize に変換し、Ok(isize) として返します。
もし整数としてパース出来ないなどのエラーがあれば、それを String で表現し、Err(String) で返します。
本質的にはこれが全てです。ここに、Result から中身を取り出す(Err なら panic する)関数などを定義してあげれば便利にエラー状態を表現できます。
(Rust の try マクロはとても便利ですよね)
まずはベースとなる result を作る
まずはベースとなる result 型を作ってみます。
template <typename T, typename E> struct result { result(T const& ok) : t(tag::OK) { ok_ = ok; } result(E const& e) : t(tag::OK) { err_ = e; } ~result() { switch (t) { case tag::OK: ok_.~T(); break; case tag::ERROR: err_.~E(); break; } } result(result const& r): t(r.t) { switch (t) { case tag::OK: ok_ = r.ok_; break; case tag::ERROR: err_ = r.err_; break; } } T const& get() const { if (t != tag::OK) { throw "invalid get operation"; } return ok_; } E const& get_error() const { if (t != tag::ERROR) { throw "invalid get operation"; } return err_; } private: enum class tag { OK, ERROR, }; tag t; union { T ok_; E err_; }; };
かなり雑ですが、ざっくりこんな感じになるはずです。
C++11 から拡張されて自由度がかなり高くなった union がとても便利です。
これで result<int, std::string>(1).get() とやれば 1 が返るし result<int, std::string>(std::string("test")).get_error() で "test" が返るはずです。
C++ でやると何が難しいか
C++ で難しいのは、Rustより弱い型推論が引き起こす問題です。
Rust では、Ok(1isize) とか Err("error!".to_owned()) とすれば、その値がどういう型であることが期待されているのかまで含めて型推論や単一化が行われます。
すなわち、Ok(1isize) だけを見てもエラーの型がわからないため、Result<isize, E> の E を決定することが出来ないが、Rust は強力な型推論機構を持つため、これを決定することが出来ます。
一方、C++ では result<int, std::string> f() { return 1; } は int から result<int, std::string> の暗黙変換がきくので可能ですが、result<int, int> などとした瞬間、暗黙変換に頼ることはできなくなります。
そこで、出来れば ok(1) とか err("test") という感じにしたいのですが、これは一筋縄では行きません。
template <typename T, typename E> result<T, E> ok(T);
これだと T は推論されても E が推論されないので、ok<int, std::string>(1) などとしなければなりません。これは使いづらすぎます。
じゃあどうするか
先ほどとは違う形ですが、やっぱり暗黙の型変換を応用します。
要するに ok を表す型と error を表す型を区別しつつ、result<V, E> とはなるべくシームレスに変換をしたいというわけですから、それぞれ専用の型を作ってしまえば良いのです。
template <typename T> struct ok_value { explicit ok_value(T t): t(t) {} template <typename V, typename E> operator result<V, E> () const; private: T t; }; template <typename T> template <typename V, typename E> ok_value<T>::operator result<V, E> () const { return result<V, E>(t); } template <typename T> ok_value<T> ok(T t) { return ok_value<T>(t); }
ok 側だけ示しました。
ok 関数はテンプレートになっており、T 型の値をとって ok_value<T> を返します。（本当は値渡し以外にも対応すべきですが、簡単のために値渡しだけ実装しています）
ok_value<T> は型変換演算子 operator result<V, E>() const を持ちます。これによって ok_value から result への暗黙変換が可能になります。
ok_value<T> は result<T, E> に変換出来れば良さそうに見えるのですが、それでは不十分です。
ok("test") は ok_value<const char*> を返します。ok_value<T> -> result<T, E> の変換しか提供していない場合は、result<std::string, E> への変換ができなくなってしまいます。これは不便ですよね。
そこで新たにテンプレート引数を導入することでこれを解決しています。もっときちんとやるなら std::is_constructible などを使ってチェックをするべきだとは思いますが。
error 側もほぼ同様のコードを書いてやれば、
result<int, std::string> parse_digit(char c) { if (c < '0' || '9' < c) { return error("invalid character"); } return ok(c - '0'); }
というように書けます。
まとめ
T から result<T, E> への暗黙変換を許すという方針も全然ありだとは思いますが、個人的に Rust などで ok なら ok と明示するスタイルに慣れているので、こっちのほうが気に入っています。
明らかに正常に値を返していそうな感じがコードにあらわれて好きです。
暗黙の型変換って危険だしあまり良いイメージはないと思うのですが、やっぱりあれば便利ですね。 C++ を使っている時点で気を抜いたら死なので、「取り扱いを把握して全力で注意しながら使えば危険じゃない」という気持ちで便利に使いたいものです。
