Alpha Beta Epsilon

Categories:

幽霊型で配列のコンパイル時境界検査を実装する

今回は論文 “Lightweight Static Capabilities” (Kiselyov and Shan) の第 3 章で紹介されている配列の境界検査の話を取り上げます。 ちょっとプログラムが複雑というか、色々な技術が組み合わさっているので、 慣れていない人にとってはやや読みにくいかな、と思います。 なので、少し丁寧に説明したいと思います。

Categories:

幽霊型を使って木に対する型安全な map2 を作る

以前に、幽霊型 を使って 型レベル自然数 を作り、リストの長さを型で表現することで、 空リストに対する hdtl 操作をコンパイル時に検出する、 というトリックを紹介しました。 当時は紹介していませんでしたが、リストの長さの等しさを型レベルで検査できるので、 map2 とかを型安全にすることもできます (map2 は 2 つリストを受け取るが、両者の長さは同じでなければいけない)。 その応用で、木の構造を型レベルで表現して、木に対する型安全な map2 を作ってみます。 割と簡単な応用なので、慣れている人にとってはあまり面白くないかもしれません。 まぁ、幽霊型って色々できるんだよ、というデモンストレーションです。

Categories:

条件付き確率場の勾配上昇法(勾配降下法)を理解する

機械学習で利用されるモデルの一つに、条件付き確率場というものがある。 このモデルの尤度関数の勾配を直感的に理解できる説明を思いついたので、 忘れないようにメモしておく(直感的な説明は最後の節なので、 知っている人はそれ以外の節を読み飛ばすと良いです)。

Categories:

幽霊型で「ファイルから読み込んだリストの長さ」をコンパイル時に取り扱う

幽霊型 (phantom type) は、関数型プログラミング言語、 特に強い静的型付きの言語のプログラミング・テクニックなどで、たびたび登場します。 幽霊型を使うと、ちょっと変わった条件や仕様をコンパイル時に検査することができ、 少しデバッグが楽になります。 なので、色々な仕様をコンパイル時に検査するべく、 古の時代から幽霊型が技術が磨き上げられてきました。 今回は、私が開発している静的サイズ検査付き線形代数演算ライブラリ SLAP (Sized Linear Algebra Package) にも応用されている手法のお話です。

Categories:

C++ テンプレートプログラミング:コンパイル時にリストをソートする

C++ のテンプレートを使うことで、コンパイル時に計算ができます。 コンパイル時の計算というのは、簡単に言えば、定数だけからなる式など、 実行時の情報に依存していないコードをコンパイルするときに計算してしまい、 実行時には計算結果の定数にアクセスするだけにする、ということです。 C++ では、テンプレートを使うことで、コンパイル時計算を行うことができ、 しかも、チューリング完全なので,どんな処理も書くことができます。 以前から、C++ のテンプレートを使って、リストをコンパイル時にソートするプログラムを作ろうと思っていて、 やっと完成したので、今日はその解説をしようと思います。