この記事は rogy Advent Calenderの20日目の記事です また、この記事の単体のHTMLファイルがあります。
単体のHTMLファイルの方がスタイルが良い感じになっているので、出来ればそちらを読んでください。
プログラミング言語
この記事は rogy Advent Calenderの20日目の記事です また、この記事の単体のHTMLファイルがあります。
単体のHTMLファイルの方がスタイルが良い感じになっているので、出来ればそちらを読んでください。
これはrogy Advent Calendar 2015の16日目の記事です．
こんにちは．15のアーク(@_Ark_0 )と言います． rogyブログに記事を書くのは初めてです．
一応ゲーム作ったり，競プロに参加したりしています．最近はD言語がマイブームです． D言語くんかわいい
今回は，マウス操作によってカメラの移動を直感的に動かせるようにするためのクラスを作ってみました． (3Dグラフィックでの話です．実在のカメラではないです><)
具体的には次のマウス操作ができるように作りました．
(Three.jsのTrackballControlsみたいな挙動を目指しました)
他の環境でもだいたい同じような手段で実装できると思います．
点$P(x, y, z)$を点$Q(X, Y, Z)$に移動させるときにアフィン変換を用いると便利です． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \] このようにして4次正方行列によって点$P$から点$Q$への写像先を定めます．
例えば，$x$軸正方向に$5$だけ平行移動するような写像を定める行列を$A$，$z$軸周りに$\pi / 3$だけ回転する写像を定める行列を$B$としたとき，$x$軸正方向に$5$だけ平行移動してから$z$軸周りに$\pi / 3$だけ回転する写像を定める行列は$BA$という行列の積で表せます．行列で変換を表せることの良さはこの辺りに出てきます．
具体的な行列は次節以降に書きます．
Processingには，この変換行列の成分をそのまま引数にとって座標変換をしてくれる組み込み関数applyMatrix()があるので，それを使いました．プログラムの大筋の流れとしては次のようにしました．
正規化したベクトル$\vec{n} = \left ( \begin{array}{ccc} n_x \\ n_y \\ n_z \end{array} \right )$を回転軸として$\theta$回転をするようなアフィン変換は次のようになります． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} \cos \theta + n_x^2 (1-\cos \theta) & n_x n_y (1-\cos \theta) - n_z \sin \theta & n_x n_z (1-\cos \theta) + n_y \sin \theta & 0 \\ n_y n_x (1-\cos \theta) + n_z \sin \theta & \cos \theta + n_y^2 (1-\cos \theta) & n_y n_z (1-\cos \theta) - n_x \sin \theta & 0 \\ n_z n_x (1-\cos \theta) - n_y \sin \theta & n_z n_y (1-\cos \theta) + n_x \sin \theta & \cos \theta + n_z^2 (1-\cos \theta) & 0 \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \] これで，任意の回転を表せるようになりましたが，実際にマウスのドラッグと回転をどのようにして結びつけるかは結構悩みました．最終的に決めた方法は次のようにしました．
こんにちは．15のアーク(@_Ark_0 )と言います． rogyブログに記事を書くのは初めてです．
一応ゲーム作ったり，競プロに参加したりしています．最近はD言語がマイブームです． D言語くんかわいい
今回は，マウス操作によってカメラの移動を直感的に動かせるようにするためのクラスを作ってみました． (3Dグラフィックでの話です．実在のカメラではないです><)
概要
何らかの式を3D空間に視覚化させたり，実験的に何かを3D描画させたりすることがあると思います．そのときに困るのがカメラの視点．ある一方向からの視点からだと全体像がよくわからなかったり，カメラの位置を数値で設定するのが面倒だったりします．そこで，マウス操作によって簡単にカメラを動かせたらいいなと思い，実装してみました．具体的には次のマウス操作ができるように作りました．
- 左ボタンをドラッグ → 回転
- 中ボタンをドラッグ → 平行移動
- 右ボタンをクリック → 初期化
- マウスホイールを動かす → 拡大縮小
(Three.jsのTrackballControlsみたいな挙動を目指しました)
環境
Processingを用いました．(Processingはグラフィック系に特化した言語or統合開発環境です．ちょっとしたものの可視化などにおすすめです)他の環境でもだいたい同じような手段で実装できると思います．
アフィン変換
点$P(x, y, z)$を点$Q(X, Y, Z)$に移動させるときにアフィン変換を用いると便利です． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \] このようにして4次正方行列によって点$P$から点$Q$への写像先を定めます．
例えば，$x$軸正方向に$5$だけ平行移動するような写像を定める行列を$A$，$z$軸周りに$\pi / 3$だけ回転する写像を定める行列を$B$としたとき，$x$軸正方向に$5$だけ平行移動してから$z$軸周りに$\pi / 3$だけ回転する写像を定める行列は$BA$という行列の積で表せます．行列で変換を表せることの良さはこの辺りに出てきます．
具体的な行列は次節以降に書きます．
Processingには，この変換行列の成分をそのまま引数にとって座標変換をしてくれる組み込み関数applyMatrix()があるので，それを使いました．プログラムの大筋の流れとしては次のようにしました．
- 最初，変換行列は単位行列にしておく
- マウスの入力を受けるたびにそれに対応する行列を変換行列に左からかけていく
- 毎フレームで「カメラを初期位置に戻し，applyMatrix()で累積した変換行列を適用する」という処理をする
平行移動
$\vec{t} = \left ( \begin{array}{ccc} t_x \\ t_y \\ t_z \end{array} \right )$だけ平行移動させるようなアフィン変換は次のようになります． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \] よって中ボタンをドラッグしているときの平行移動を表す行列は，始点の$xy$座標を$(x_{pre}, y_{pre})$，終点の$xy$座標を$(x_{now}, y_{now})$(ただし，原点は画面の中心)として次のようにしました． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} 1 & 0 & 0 & x_{now} - x_{pre} \\ 0 & 1 & 0 & y_{now} - y_{pre} \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \]拡大縮小
原点との距離を$s$倍にするようなアフィン変換は次のようになります． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} s & 0 & 0 & 0 \\ 0 & s & 0 & 0 \\ 0 & 0 & s & 0 \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \] よってマウスホイールを動かしているときののときの拡大縮小を表す行列は，ホイールの回転量を$c$として次のようにしました． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} e^ｃ & 0 & 0 & 0 \\ 0 & e^ｃ & 0 & 0 \\ 0 & 0 & e^ｃ & 0 \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \] 冪乗を取ることによって倍率を正の数にすることを保証し，また回転量の正負で拡大と縮小が切り替わるようにしました．(もっといい方法があるのかもしれない)回転
回転の行列は$x$軸周りの回転とかなら楽だが任意の回転軸における回転をしたかったので，ロドリゲスの回転公式を用いました．(ロドリゲスの回転公式についてはこちらの説明と証明が分かりやすかったです)正規化したベクトル$\vec{n} = \left ( \begin{array}{ccc} n_x \\ n_y \\ n_z \end{array} \right )$を回転軸として$\theta$回転をするようなアフィン変換は次のようになります． \[ \left ( \begin{array}{ccc} X \\ Y \\ Z \\ 1 \end{array} \right ) = \left ( \begin{array}{ccc} \cos \theta + n_x^2 (1-\cos \theta) & n_x n_y (1-\cos \theta) - n_z \sin \theta & n_x n_z (1-\cos \theta) + n_y \sin \theta & 0 \\ n_y n_x (1-\cos \theta) + n_z \sin \theta & \cos \theta + n_y^2 (1-\cos \theta) & n_y n_z (1-\cos \theta) - n_x \sin \theta & 0 \\ n_z n_x (1-\cos \theta) - n_y \sin \theta & n_z n_y (1-\cos \theta) + n_x \sin \theta & \cos \theta + n_z^2 (1-\cos \theta) & 0 \\ 0 & 0 & 0 & 1 \end{array} \right ) \left ( \begin{array}{ccc} x \\ y \\ z \\ 1 \end{array} \right ) \] これで，任意の回転を表せるようになりましたが，実際にマウスのドラッグと回転をどのようにして結びつけるかは結構悩みました．最終的に決めた方法は次のようにしました．
- クラスの生成時に仮想的な球の半径$radius$を引数に指定する．
- 左ボタンのドラッグをしたときに，マウスのxy座標$(x, y)$ (ただし，原点は画面の中心)を取得し，$x' = x/radius$，$y' = y/radius$，$size = \sqrt{x'^2 + y'^2}$という数を定める．
- ベクトル$\vec{v} = \left ( \begin{array}{ccc} v_x \\ v_y \\ v_z \end{array} \right )$を次式で定義する． \[ \left ( \begin{array}{ccc} v_x \\ v_y \\ v_z \end{array} \right ) = \begin{cases} \left ( \begin{array}{ccc} \frac{x'}{size} \\ \frac{y'}{size} \\ 0 \end{array} \right ) & (size \ge 1) \\ \left ( \begin{array}{ccc} x' \\ y' \\ \sqrt{1- x'^2 - y'^2} \end{array} \right ) & (size < 1) \end{cases} \]
- マウスのドラッグにおいて，始点の$xy$座標$(x_{pre}, y_{pre})$，終点の$xy$座標$(x_{now}, y_{now})$に対応したベクトル$\vec{v}$をそれぞれ$\overrightarrow{v_{pre}}$，$\overrightarrow{v_{now}}$とする．
- $\overrightarrow{v_{pre}}$と$\overrightarrow{v_{now}}$のなす角を$\theta$とすると，$\cos \theta = \overrightarrow{v_{pre}} \cdot \overrightarrow{v_{now}}$，$\sin \theta = |\overrightarrow{v_{pre}} \times \overrightarrow{v_{now}}|$となる．($\overrightarrow{v_{pre}}$，$\overrightarrow{v_{now}}$がすでに正規化されていることに注意)
- ベクトル$\vec{n}$を$\vec{n} = \overrightarrow{v_{pre}} \times \overrightarrow{v_{now}}$で定義する．
- 以上で定めた$\vec{n}$の各成分と$\cos \theta$，$\sin \theta$を上に書いたロドリゲスの回転公式に代入して回転行列を定める．
初期化
右クリックしたときに，変換行列を単位行列にするようにしました．そうすることで変換行列が定める写像は恒等写像になり初期のカメラ位置に戻すことができます．ソースコード
実際に作成したプログラムのソースコードは次のとおりです． 実際の使用例があったほうが使い方がわかりやすいと思うので，このクラスを用いた，球とトーラスを描画するプログラムを貼っておきます．
12月13
こんにちは、12のjiko (@_j_i_k_o_) と申します。
この記事はrogy Advent Calendar 2015 の14日目の記事となります。
実際に作ってみる
ソースはこんな感じです。
最初の手順に対応するコードの一部は次のようになります。
CreateToolhelp32SnapshotというAPIで現在動いているプロセスの情報を集め、Process32FirstとProcess32NextというAPIでプロセスを1つずつ調べていき、ターゲットのプロセスを見つけたらそのプロセスIDを記録するという処理です。
得られたプロセスIDから、OpenProcessを用いることで対象プロセスのハンドルを手に入れることができます。
続いてDLLのパスを書き込むための領域を確保する必要があるのですが、これに関してはVirtualAllocExを用いれば可能です。確保した領域にはWriteProcessMemoryを使ってDLLのパスを書き込みます。
最後に、対象プロセスにLoadLibraryを実行させればよいのですが、LoadLibraryの関数ポインタを取得するためにGetProcAddressというAPIを用いる必要があります。LoadLibraryはuser32.dllなるモジュールで定義されているので、GetProcAddressにuser32.dllとLoadLibraryの文字列を指定してあげれば良いです。
(本当はLoadLibraryの正体はLoadLibraryWのマクロなので (Unicode環境の場合)、文字列としてLoadLibraryWを指定する必要があります。)
ようやく対象プロセスにLoadLibraryを実行させる段階まで来ましたが、その際に使うAPIがCreateRemoteThreadです。これを用いることで、指定したプロセス上で指定した関数を実行することが可能になります。この引数に先ほど書き込んだDLLのファイルパスを指定してあげれば、めでたくDLLが対象プロセスに注入され、DLLインジェクションが成功します。
https://github.com/j-i-k-o/rogyAdC/
本当はVisual Studioプロジェクトごと公開したほうが良いのですが、互換性とかで面倒くさそうなので後で考えます。
この記事はrogy Advent Calendar 2015 の14日目の記事となります。
はじめに
さて今回書く内容についてですが、最近ロ技研ではLinux が流行っているらしいので、あえて
Windows
に関するちょっとテクニカルなお話をしたいと思います。
Windowsといえばおそらく大多数の人が初めて触れたOSであると思いますが、技術的な視点から触れる機会は少ないのではないでしょうか。今回はそんなWindowsに普段とは違った一面を感じていただければと思います。
DLLインジェクションとAPIフック
今回紹介する内容は一言でいうと上の見出しのようになるのですが、「なんのこっちゃ」と感じる人がほとんどだと思うので1つずつ説明することにします。
DLLインジェクション
みなさんがこのブログを見る際に使っているブラウザやメールソフトなど、様々なアプリは「プロセス」という単位でPC上を動いています。こういったプロセスに、自分の書いたソースコードをDLL (ダイナミックリンクライブラリ) という形にして注入 (インジェクション) する技術のことをDLLインジェクションと呼びます。こうすることで対象のプロセス上で、自作した任意のコードが動かせることになり、事実上アプリを乗っ取ることができます。コンピューターウイルスなどがよく用いる手法だったりします。
APIフック
プログラム上でwindows特有の機能を使う場合には、必ずWindowsAPI と呼ばれる関数群を介することになりますが、このAPIの処理をこっそり独自の処理にすり替えてしまう技術がAPIフックと呼ばれるものです。これによって、例えばアプリがファイルを開くためにOpenFileといったWindows APIの関数を呼び出そうとしても、APIフックにより自前の処理に誘導してしまうことが可能になるわけです。
要するに、これらはいわゆる「ハッキング」に使われるような仕組みですね。次はこれらの詳細な仕組みや利用方法を実際のプログラムを通して見てみることにします。
実際に作ってみる
今回対象とするプログラムは、簡単のために次のように「進捗どうですか」をメッセージボックスで3回表示させるようなもの (TestEXE.exe)です。
このプログラムにDLLインジェクションとAPIフックを行い、「進捗どうですか」のメッセージを改変させてみようと思います。
必要なファイルは次の2つです。
- DLLを対象プロセスに注入するための「治具」の役割を果たすEXEファイル (InjectEXE.exe)
- DLL本体 (InjectDll.dll)
以下では2つのプログラムをソースコードを交えて解説していきます。
InjectEXE.exe
WindowsAPIにはLoadLibraryという、引数としてDLLのファイルパスを指定するとDLLを読み込んでくれる関数があります。対象プロセスがこの関数を実行してくれればDLLインジェクションが成功して万事解決というわけです。したがって、この実行ファイルの目的は
対象プロセスに注入したいDLLのファイルパスを書き込んでLoadLibraryを実行させる
ということになります。手順としては以下のような感じです。
- 実行されているプロセスから対象プロセスを探し出し、プロセスIDを取得する。
- 取得したIDを用いて対象プロセスを開き、DLLのパスを書き込むための領域を確保する。
- 確保した領域にDLLのパスを書き込む。
- DLLのパスを引数として対象プロセスにLoadLibraryを実行させる。
...以下淡々とコードの説明となるので、飛ばしたい方はこちらをクリックしてください
最初の手順に対応するコードの一部は次のようになります。
CreateToolhelp32SnapshotというAPIで現在動いているプロセスの情報を集め、Process32FirstとProcess32NextというAPIでプロセスを1つずつ調べていき、ターゲットのプロセスを見つけたらそのプロセスIDを記録するという処理です。
得られたプロセスIDから、OpenProcessを用いることで対象プロセスのハンドルを手に入れることができます。
続いてDLLのパスを書き込むための領域を確保する必要があるのですが、これに関してはVirtualAllocExを用いれば可能です。確保した領域にはWriteProcessMemoryを使ってDLLのパスを書き込みます。
最後に、対象プロセスにLoadLibraryを実行させればよいのですが、LoadLibraryの関数ポインタを取得するためにGetProcAddressというAPIを用いる必要があります。LoadLibraryはuser32.dllなるモジュールで定義されているので、GetProcAddressにuser32.dllとLoadLibraryの文字列を指定してあげれば良いです。
(本当はLoadLibraryの正体はLoadLibraryWのマクロなので (Unicode環境の場合)、文字列としてLoadLibraryWを指定する必要があります。)
ようやく対象プロセスにLoadLibraryを実行させる段階まで来ましたが、その際に使うAPIがCreateRemoteThreadです。これを用いることで、指定したプロセス上で指定した関数を実行することが可能になります。この引数に先ほど書き込んだDLLのファイルパスを指定してあげれば、めでたくDLLが対象プロセスに注入され、DLLインジェクションが成功します。
InjectDLL.dll
ようやくプロセス内にDLLが入り込めたので、続いての作業はDLL自身が担うこととなります。このDLLが行う仕事はAPIフックを行ってメッセージボックスを呼び出す関数 (MessageBoxW)の処理をすり替えることです。APIの関数のアドレスは、対象プログラムのexeファイルに存在するインポートセクションという領域で管理されているので、これを書き換えてしまえばAPIフックが実現できます。
ここでの手順は次のようになります。
- MessageBoxWを置き換える処理Hook_MessageBoxW関数を作成する。
- 対象プログラムのインポートセクションにアクセスし、MessageBoxWに対応する関数のアドレスを探す。
- アドレスをHook_MessageBoxWのアドレスに書き換える。
...この後延々とコードの説明が続くので、飛ばしたい方はこちらをクリックしてください。
まず、置き換え先の関数Hook_MessageBoxWの定義は、本来のMessageBoxWの定義に似せて、次のようにします。
ざっくりと説明すると、Hook_MessageBoxWでは、メッセージボックスの本文だけを「ぽぽぽぽぽぽぽぽ」に変えたMessageBoxWを実行しています。その際、return文の箇所を
のようにMessageBoxWをそのまま書いてしまうと、MessageBoxWをHook_MessageBoxWに置き換える処理のために無限ループが生じてしまうため、GetProcAddressを用いて、置き換える前のMessageBoxWを使用しています。
さて、DLLがプロセスに読み込まれた際、DLLにおけるmain関数に相当するDllmain関数が実行され、CreateThread関数によりapiHook関数が実行されるのですが、この関数の中でAPIフックに関する一連の処理が行われています。
apiHook関数では、まず対象プログラムのインポートセクションにアクセスすることから始めるのですが、その際にImageDirectoryEntryToDataというAPIを用いると便利です。ここではインポートされているモジュール名に、MessageBoxWを取り扱うモジュールであるuser32.dllが含まれているかを探しています。
モジュール名が見つかった後は、それぞれAPIの名前とアドレスを扱うインポートネームテーブルとインポートアドレステーブルを探し、MessageBoxWという文字列がインポートネームテーブルに存在するかを調べます。もし見つかれば対応するインポートアドレステーブルをHook_MessageBoxWのアドレスに書き換えてしまえばよいのですが、この領域は読み取り専用となっており、書き換えが不可能なので、VirtualProtectを用いて領域のアクセス権をいじってやればよいです。
これにて、MessageBoxWの処理がすべてHook_MessageBoxWに置き換わることとなったので、予想通り行けばすべてのメッセージボックスの本文が「ぽぽぽぽぽぽぽぽ」に書き換えられます。
ソースコードについて
全体のソースコードは以下に配置しています。https://github.com/j-i-k-o/rogyAdC/
本当はVisual Studioプロジェクトごと公開したほうが良いのですが、互換性とかで面倒くさそうなので後で考えます。
実演
1つ目のダイアログが「進捗どうですか」と表示されている間にInjectEXE.exeを実行すると、InjectDLL.dllが対象プロセスに注入され、APIフックによりMessageBoxWの処理がHook_MessageBoxWに置き換わります。その結果、2つ目以降のダイアログは次のようになります。
やったね。ちゃんとテキストが置き換わったね。
最後に
さて、長々とした説明となってしまいましたが、いかがでしたでしょうか。
今回はメッセージボックスの本文を変えるという単純なサンプルであったわけですが、注入するコード次第で様々なことができるのはとても面白いのではないでしょうか。例えば、いわゆる「ウイルス対策ソフト」がPCを監視するための方法にもこういった手法が使われていたりするそうです。
いずれにせよ、この記事を読んでくれた方が多少なりとも興味をもってもらえればと思います。
最後までお読みくださりありがとうございます！
参考サイトなど
12月12
こんにちは。15のphi16とかいいます。はじめてrogyブログをかかさせていただきます。
これはrogy Advent Calendar 2015の12日目の記事です。11日目は@cyan_rej55さんでした。
テーマは†万物の創造†ということですが、宗教色は多分ないのです。たぶん。
はじめに
私は一応rogyのほうでゲーム制作とかしてます。謎のゲームつくったのでそろそろ公開したいです。
さて、私はゲーム作るのが好きなのですが、プログラミングにおける「関数型言語」というものも好きです。
そこで(元祖)手続き型にはあんまりない、関数型言語でよく用いられる概念について、文字通り1から解説・創造していきます。
長々とした読み物になってしまいましたが、読んで面白さとかを感じた方がいたら関数型言語をやるなり手続き型にそれらをつっこむなりしたらいいなと思っています。
長々とした読み物になってしまいましたが、読んで面白さとかを感じた方がいたら関数型言語をやるなり手続き型にそれらをつっこむなりしたらいいなと思っています。
対象はプログラマっぽくて数学好きっぽい人です。
1
何よりも最初に必要なのは1です。ですがこの1はいわゆる自然数ではありません。言うなれば「自明」と呼ぶようなものです。
そこにただ存在しているということ、はなかなか認識されているものではありません。具体的には :
- int main(){}
という関数をC/C++で書くことがあるかと思われますが、これは0引数の関数ではなく、「1を受け取る」関数とみなすことができるのです。1引数ではなく、1です。
実際これはHaskellではユニット型『()』と呼ばれます。これが全てのベースになります。
ちなみに1って呼ぶのは後述の直積の単位元だから(とか)です。
ちなみに1って呼ぶのは後述の直積の単位元だから(とか)です。
直積 A × B
集合の方でも出てくる直積という概念ですが、これは2つの物があったときにその両方を保持する物が存在することを表します。
つまり、いわゆるPair,Tuple(,Struct)です。戻り値のためにわざわざ構造体を作らなくて良いなど便利なのです。
個人的に必要だとおもうのはPairを生で生成可能なこと、つまりJavaのようにわざわざ自分でnewとかを書かなくていいことかなと思っています。仕方ないですけど。
C++のstd::tieみたいになるのも残念ですし、直積はもっと言語側でサポートしほしいなとか思います。
直和 A + B
この直和ですが、全くと言っていいほど認知されていません。
何かというと、直積の反対で、2つのうち片方のみを保持していることを表す型です。Eitherとかいいます。
Eitherの制限としての「Maybe, Optional, Nullable」の方は最近ようやく流行ってきてる気がします。
これらは「あるかないか」ですが、Eitherは「AかBか」を表現します。一般的ですね。
例えば「本来なら」直和として表現すべきなのに大抵そうなっていないものがあります : Boolです。
Boolは、まさしく1と1の直和として表現できます(つまり1+1=2です。)。これで値が-1なんかになることはなくなるわけです。
Eitherそのものは例えばエラー処理に使うことができます。正常な値を「右」で返して発生したエラーを「左」で保持、みたいなことをしたり。
うまくやれば例外処理機構そのものを「創り上げる」ことができます : C++のExpectとかまさにそんな感じで使われますね(未来的に)。Expectについてはこれが詳しいです。
ちなみに演算子の優先順位として A × B + C = (A × B) + C として解釈してください。
冪 B → A
型に対して冪(二項演算)を定義するというのも変かもですが、集合においてA^BがBからAへの写像の集合であったように、型の冪とは関数のことです。
集合の冪集合といえば2^Aですが、これはAから2 = Boolへの写像、つまりAの指示関数と同じものですね。
指示関数に具体的な値を渡すことでBoolが得られます。即ちBとB → AがあるときAを得ることができます。これが関数適用です。
といってもまぁ細かいことは気にせず関数 B → A を使っていこうかと思います。私は最近冪と関数の対応に感動しました。
関数は様々な解釈を生みます : 「導出」「抽出」「変換」「埋め込み」「割り当て」「計算」などでしょうか。この多様性が便利な所以でもあるのかもしれません。
実際これだけでも殆どを構築できます。直積直和どちらも関数のみで作ることもできますし。だいたい。
ですが更に世界を広げる為にもうちょっと基本概念を創ります。
あと優先順位としては A + B → C → D = (A + B) → (C → D) となります。最弱で右結合。
多相 F A
ちょっと話は変わりますが「一定の構造」を「任意の型」に適用したいニーズはかなりあります : template,Genericsなど。
これは「型をとって型を返すモノ」Fとして考えることができます。Fは型じゃないです。
これによって関数型ではよく出てくるリストを作ることができます。要素の型をAとしたリストLは
- L A = 1 + A × L A
として表せます。直和の左は「空」、右は「要素とリスト」なので、「要素がない、または要素があってその後続も存在する」ものがリストと考えられるわけです。この構造はAの中身には依存していません。
例えば、リストという構造には一般的に「長さ」が定義され、これは要素の型に不変です。
つまりlength : L A → Intです。
多相型にしないとlengthを全ての型Aについて作ることになるわけです。これを防ぐためにC言語では暗黙の型キャストがあったのかなぁ、と思わなくもないですがダメです。
つまりlength : L A → Intです。
多相型にしないとlengthを全ての型Aについて作ることになるわけです。これを防ぐためにC言語では暗黙の型キャストがあったのかなぁ、と思わなくもないですがダメです。
ちなみに今までの例もみんな多相型です。例えば直積は左・右の型に依存せず定まるので。
型クラス
先ほどの例では「任意の型」の適用でしたが、実際は「乗算のできる型」に対して適用したい、みたいなことがあると思います。
これを実現するのが型クラスで、C++ではconcept(無い)、Javaでいうinterfaceみたいなものです。ゆるいことを言えばオーバーロードっぽい感じです。
例えば「A × A → A」ができる型を「乗算のできる型」みたいに扱います。すると「全ての乗算可能型」について同名で掛け算を適用できるわけです。
Haskellでは「数値」「除算」「実数」「比較」「順序」「最大最小」「自然数対応」「表示」「読み込み」「畳み込み」などたくさんの型クラスがあり、演算を一般化しています。
例えば比較に関しては compare : A × A → 3 が必要とされており(ここで3はLessとEqualとGreaterの直和になる)、これを満たす型は x < y や x >= y などの比較演算ができるようになります。
具体的な構成
これで†万物の創造†への準備は整いました。実際に例を書いていきます。
細かく解説しようと思ったんですけど長くなりすぎるので列挙していくのです。
1. よくあるもの
- Bool = 1 + 1 ―― 二値論理
- Nat = 1 + Nat ―― 自然数 (ペアノの公理)
- List A = 1 + A × List A ―― Consリスト
- Stream A = A × Stream A ―― 無限リスト
- Tree A = A + Tree A × Tree A ―― 葉に値を持つ二分木
2. 計算 Arrow
通常の計算A → Bの「→」を一般化すると(二項演算としてみると)、P A Bです。ここで計算Pに求める制限は、
- P A A (何もしないでそのまま出力する計算)
- P A B × P B C → P A C (順序結合可能)
- (A → B) → P A B (通常の計算を一般化する)
- P A B → P (A × C) (B × C) (一部だけを計算させる)
というもので、これを満たすとArrowという型クラスになります。
- P A B = A → B ―― 通常の計算(関数)
- P A B = Stream A → Stream B ―― ストリーム処理
- P A B = A × S → B × S ―― Sを状態としてもつ計算
- P A B = A → B + E ―― 例外処理
- P A B = A → B × P A B ―― オートマトン
3. 結果 Monad
これは完全に私の個人的思想なのですが、Arrowが入力についても考えるのに対しMonadというのは結果のみを保持するようなもの、と思っています。まぁ順序実行でいいんですけど。
そうすると入力がなくなって、値Aを表現するM Aとして表わせ、必要な法則(型クラス)は単純になって、
- A → M A (ただの値を計算結果にする)
- M A × (A → M B) → M B (前回の計算結果と、その値を使った計算をつなげる)
です。Arrowの特殊版なので実際にP A B = A → M Bと対応がとれます(KleisliArrow)。
- M A = A ―― ただの値
- M A = 1 + A ―― 失敗
- M A = S → A × S ―― 状態
- M A = List A ―― 非決定性計算
- M A = (A → R) → R ―― CallBack, 継続
4. 環境 Comonad
あんまり理解していないので細かいことは言えませんが、Monadの「逆」としてP A B = W A → Bを考えます。
そうすると法則が逆転して、
- W A → A (環境から抽出)
- W A × (W A → B) → W B (環境を移し替える)
これだと結果を返すのではなく環境を受け取ることになるわけです。
- W A = List A × Int ―― 現在地、近傍
- W A = Tree A ―― 部分木畳み込み
- W A = (S → A) × S ―― 環境更新
5. アクセス Lens
いわゆるオブジェクト指向でのGetter/Setterは、A → B(抽出), A → (B → A) (書き込んだ結果を返す)と書くことができます。
これを直積で合成するとA → B × (B → A)となり、軽量Lensと呼ばれます。これもこれでおもしろい。
そして、これをいじると(B → F B) → A → F Aが出てきます(ここでFはFunctorという型クラスに含まれる型)。 出てくるらしいです。
そして、これをいじると(B → F B) → A → F Aが出てきます(ここでFはFunctorという型クラスに含まれる型)。 出てくるらしいです。
このときGetterとSetterはそれぞれ
- (A → R) → B → R ―― Aでの読み出しをBでの読み出しに変換
- (A → A) → B → B ―― Aの変換をBに書き込み
と考えることができ、それぞれが
- Getter A = Const R A ―― 常にR。
- Setter A = Identity A ―― 常にA。
というFunctorに対応します。もっとやっちゃうと
- (A → F A') → B → F B' ―― Lens
となります。これは本当に様々な「アクセス」を一般化することができます。
- F A = A ―― Setter
- F A = R ―― Getter
- Contravariant F, Applicative F ―― Fold, 畳み込み
- Applicative F ―― Traversal, 走査
- Functor F ―― Lens
さらに「→」を一般化してP A (F A') → P B (F B')とすると
- Choice P, Applicative F ―― Prism, 部分的全単射
- Profunctor P, Functor F ―― Iso, 同型
- Forall P, Forall F ―― Equality, 等価
とまでなります。一般化された方は一般化する前のものとして使えます。つまり「同型」があるとそこから「Getter」「Setter」ができます。
説明的にはとりあえず様々な「アクセス」を一般化することができた、と考えればいいかなぐらいです。
これを使うと複素数で点P中心にθ回転する関数は subtracting P . _phase +~ θ で終わりです。すごい。
ちなみにsubtractingはIso、_phaseはLensです。
正直Lensを一番紹介したかった。
正直Lensを一番紹介したかった。
6. 世界 IO
せっかく万物の話をしているので世界をつくりたいとおもいます。
Haskellで用いられている「世界」は単純に、RealWorldという型を状態として持つMonadとして扱われます。これがIOモナドです。
IO A = RealWorld → RealWorld × A ―― 世界。実際には細かい違いがある。
このRealWorldはまさに世界そのもので、これを使うことで任意の操作(システムコールとか)ができる、という「仮想的な対象」です。
Monad内部の値を取り出すにはMonad以外の何らかの方法が必要、という制約によってRealWorldの整合性が保たれるのです。たぶん。
というわけで、「世界」とはMonadにより閉じ込められた状態、ということになります。
ちなみになんと「世界を過去に書き換える」みたいなことができるみたいです。過去の書き換えに永遠に時間がかかるみたいですけどね :(
終わりに
解説ほとんど無い上に省略・適当な部分が多く申し訳ないです。間違えてる部分などあれば教えて下さい。
とりあえずは「1」から「世界」まで、いろいろなものが型で表せることがちょっとでもわかっていただければとおもいます。
とりあえずは「1」から「世界」まで、いろいろなものが型で表せることがちょっとでもわかっていただければとおもいます。
C言語とかではハード的制限が強かった上に型は殆ど自明ですが、言語にきちんとした型をいれることでいろんなものができるようになるのです。
もっと関数と型を大事にしてあげてください、よろしくおねがいします。
あともっと面白い話を見たければ型理論とか圏論とかみるといいんだとおもいます。はい。
実際の実用っぽいです。おもしろい。 : dynamorphism
実際の実用っぽいです。おもしろい。 : dynamorphism
12月2
※効果には個人差があります。
はじめに
どうも。らりおです。
この記事は rogy Advent Calendar 2015 の2日目です。
さてこの度、 rogy Advent Calendar 2015
におきまして、「シェルスクリプトは救い」と題した記事を書くことを予定しておりました。
というのも、なかなか私の要求を満たす静的サイトジェネレータが見付からず、
ならば自力でシェルスクリプトで書こうか、などと考えていたためでございます。
しかしその目論みは崩れ、 nanoc に救われてしまったため、
急遽予定を変更し、
-
シェルスクリプトがあなたを救う、その理由
-
シェルスクリプト成果物 自慢大会 紹介
の二本立てでお送りいたします。
あと、この記事は†強い†人向けのものではありません、念の為。
Rubyに圧倒的感謝。
カテゴリー
