2次元調和振動子(古典力学)
概要
ベルトランの定理により、軌道が必ず閉軌道になるような中心力ポテンシャルというのは調和振動子とケプラー問題だけであることが知られている。ケプラー問題においては、エネルギーと角運動量だけでなく、離心率ベクトル(ルンゲ=レンツベクトルの定数倍)という幾何学的な意義のあるベクトルが保存量となるということが知られている。じゃあ2次元調和振動子のときには何が保存されるのか。気になったがググってもいい感じの資料がヒットしない(みんな量子の方の話ばかりしとる)ので、自分で考えてみることにした。
2次元調和振動子
初期位置 $\vec{X} = (X, Y)$, 初速度 $\vec{V} = (V_x, V_y)$ で質量 $m (>0) $ の粒子を調和振動子ポテンシャル $U(x,y) = \frac{1}{2}m\omega^2 (x^2+y^2)$(ただし $\omega \not= 0$) の中に投げ込んだとき、粒子は時刻 $t$ には位置 $\left(X\cos\omega t + \frac{V_{x}}{\omega}\sin\omega t,Y\cos\omega t+ \frac{V_{y}}{\omega}\sin\omega t\right)$ にある。時間に対する並進対称性があり、回転対称性もある系なので、総エネルギー $ \frac{1}{2}m(v_x^2+v_y^2) + \frac{1}{2}m\omega^2 (x^2+y^2)$ と角運動量 $mx v_y - my v_x$ は保存量となる。角運動量が非ゼロなら軌道は中心を原点とした円か楕円であり、いずれにしても閉軌道をなす。
以下長いので、まずはdesmosで書いた初期位置と初速度いじれるやつで遊んでみていただきたい。
ここで、楕円の2つの直交する軸を表す青い2直線は、$\left(x^{2}-y^{2}\right)\ \left(\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY\right)+\ xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right)=0$ として描画している。初期条件だけに基づいて、楕円の幾何学的特徴を表す存在を描画できているようだ。ということで、こいつについて調べてみよう。
証明パート
補題0
実数$A, B$ に対して、写像 $(x,y) \mapsto A\left(x^{2}-y^{2}\right)+2Bxy$ を考える。$A=B=0$ であればあらゆる $(x,y)$ に対しこの写像は $0$ を返す。それ以外の場合、2つの直交する軸が存在して、それら2軸上のベクトルに対してのみこの写像は $0$ を返す。
補題0の証明のsketch
$A=B=0$ については自明。そうでなければ、$A\left(x^{2}-y^{2}\right)+2Bxy=0$ を $\begin{pmatrix} x & y\end{pmatrix} \begin{pmatrix} A & B \\ B & -A \end{pmatrix} \begin{pmatrix} x \\ y\end{pmatrix} = 0 $ と書くと、$\begin{pmatrix} A & B \\ B & -A \end{pmatrix}$ の行列式は $-A^2-B^2 < 0$.
$\begin{pmatrix} A & B \\ B & -A \end{pmatrix}$ は実対称行列なので直交行列により対角化可能で、元のトレースが $0$ なのだから対角行列もトレースが $0$、元の行列式が非ゼロなのだから対角行列も行列式が非ゼロ。つまり直交行列 $P$ と実数 $C \not= 0$ が存在して、$A\left(x^{2}-y^{2}\right)+2Bxy=0$ を $\begin{pmatrix} x & y\end{pmatrix}P^T \begin{pmatrix} C & 0 \\ 0 & -C \end{pmatrix} P \begin{pmatrix} x \\ y\end{pmatrix} = 0 $ と書ける。直交する2ベクトル $P^{-1} \begin{pmatrix} 1 \\ 1\end{pmatrix} $ と $P^{-1} \begin{pmatrix} 1 \\ -1\end{pmatrix} $、およびこいつらのスカラー倍だけがこの式を成り立たせることは簡単に確認できる。
補題1
初期条件が円軌道(粒子が原点に居座る場合も半径$0$の円軌道と見なす)を与えることと、写像 $ (x,y) \mapsto \left(x^{2}-y^{2}\right)\left(\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY\right)+ xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right)$ が恒等的に$0$を与える写像となることとは同値である。
補題1の証明のsketch
初期条件が円軌道を与えるならば、中心が原点の円軌道であるので、角運動量保存により角速度は一定である。よって等速円運動である。周期の一意性より角速度$\omega$の等速円運動であるので、初期位置 $\vec{X} = (X, Y)$ と 初速度 $\vec{V} = (V_x, V_y)$ は直交し、 $|\vec{V}| = \omega|\vec{X}|$ である。 つまり $V_x + iV_y= \pm i \omega (X + iY)$ であるので、両辺を2乗すると $(V_x^2 - V_y^2) + 2iV_xV_y= - \omega^2 (X^2 - Y^2 + 2iXY)$ であり、実部どうしと虚部どうしを比較すると $V_x^2 - V_y^2 = - \omega^2 (X^2 - Y^2)$ と $2V_xV_y= - 2XY\omega^2$ が分かる。したがって $\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY = 0$ と $\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right) = 0$ が分かるので、写像 $ (x,y) \mapsto \left(x^{2}-y^{2}\right)\left(\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY\right)+ xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right)$ は恒等的に$0$を与える写像となる。
逆に、写像 $ (x,y) \mapsto \left(x^{2}-y^{2}\right)\left(\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY\right)+ xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right)$ が恒等的に$0$を与える写像であれば、補題0より $\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY = 0$ と $\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right) = 0$ が分かる。ここから$(V_x^2 - V_y^2) + 2iV_xV_y= - \omega^2 (X^2 - Y^2 + 2iXY)$ であり、$V_x + iV_y= \pm i \omega (X + iY)$ であり、原点中心の等速円運動である。
補題2
角運動量が $0$であり、粒子が原点に居座るのでないならば、写像 $ (x,y) \mapsto \left(x^{2}-y^{2}\right)\left(\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY\right)+ xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right)$ は、振動方向に平行または垂直なベクトルが入力されたときのみ $0$ を出力する写像となる。
補題2の証明のsketch
角運動量が $0$ であるなら $\vec{X}$ と $\vec{V}$ は平行(含ゼロベクトル)である。粒子は原点に居座っていないので、非0な複素数 $Z$ と少なくとも片方は非0な実数 $a$, $b$ が存在して $X + iY = aZ$, $\frac{V_x}{\omega} + i\frac{V_y}{\omega} = bZ$ と書ける。そうすると $\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY = \frac{1}{2}\mathrm{Im}(b^2Z^2) + \frac{1}{2}\mathrm{Im}(a^2Z^2) = \frac{a^2+b^2}{2} \mathrm{Im}(Z^2)$ と $\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right) = -\mathrm{Re}(b^2Z^2)-\mathrm{Re}(a^2Z^2) = -(a^2+b^2)\mathrm{Re}(Z^2)$ が成り立つので、$z = x + iy$ と置けば $\left(x^{2}-y^{2}\right)\left(\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY\right)+ xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right) =\mathrm{Re}(z^2)\frac{a^2+b^2}{2} \mathrm{Im}(Z^2)-(a^2+b^2)\mathrm{Re}(Z^2)\frac{1}{2}\mathrm{Im}(z^2)$ であり、こいつは $-\frac{a^2+b^2}{2}|Z^4|\mathrm{Im}\left(\frac{z^2}{Z^2}\right)$ と書ける(一般に $bc-ad = |c+di|^2 \frac{bc-ad}{c^2+d^2} = |c+di|^2 \mathrm{Im}(\frac{a+bi}{c+di})$ であることから従う)。 $-\frac{a^2+b^2}{2}|Z^4| \not= 0$ より、例の写像は $\frac{z^2}{Z^2}$ が実数であるときのみ $0$ を出力する写像であり、つまり $\frac{z}{Z}$ が実数または純虚数であるときのみ $0$ を出力する写像であり、$(x,y)$ が $\vec{X}$ と $\vec{V}$ の両方と平行、または両方と垂直、である場合のみに $0$ を出力する写像である。
主定理
楕円軌道であるならば、写像 $(x,y) \mapsto \left(x^{2}-y^{2}\right)\left(\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY\right)+ xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right)$ は、楕円の短軸か長軸と平行なベクトルが入力されたときのみ $0$ を出力する写像となる。
主定理の証明のsketch
楕円軌道にならない場合については補題1と補題2で考察した。ということで、角運動量は $0$ ではないし、$\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY$ と $\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)$ のどちらかは非ゼロである。
$\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+ Y^{2}-X^{2} = 0$のとき
$\frac{V_{x}}{\omega}\frac{V_{y}}{\omega}+XY$は非ゼロである。写像は $(x,y) \mapsto + xy\left(\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+\left(Y^{2}-X^{2}\right)\right)$ なので、この写像は $x$ 軸上の点と $y$ 軸上の点に対して、かつそのときのみ、 $0$ を出力する。
$\frac{V_{y}^{2}-V_{x}^{2}}{\omega^{2}}+ Y^{2}-X^{2} \not= 0$のとき
読者への演習課題とする。(まだ書き切れていないので後日書き上げて公開するかもしれません)
語学と私
以下、201920年9月19日に私が書いたメモに加筆したもの。
私はいま新幹線に乗っている。
/sæ̃/ で始まる単語を引きたいときに開く箇所:
— jekto.vatimeliju@hsjoihs@.sozysozbot. (@sosoBOTpi) 2019年9月7日
cein-
cin-
sain-
scin-
sein-
sim- ~ sin-
sym- ~ syn-
大学その2。日本語ができることが卒業要件「語学」を満たすので語学を取らなくていい。ということで、語学をほぼやらずに言語学だけやる生活を3年続けた。「現代ヘブライ語についての文法書を図書館から借り、全ページに目を通し、単語を1個も覚えずに返却する」みたいな。ときたまフランス語会話イベントなどが発生し、私のひどいフランス語を晒すはめになった。
ファミコン疑似三角波のフーリエ級数展開
概要
http://sketch.txt-nifty.com/blog/2008/12/post-cb2c.htmlによれば、ファミコン音源の「三角波」は実は16段階の階段状で、F E D C B A 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 A B C D E F の繰り返しを出力するそうだ。なるほどね。
ということでフーリエ級数展開してみよう。周期$t_0$の三角波の一周期分は$\left\{0<x<\frac{t_{0}}{2}:-1+\frac{4x}{t_{0}},\frac{t_{0}}{2}<x<t_{0}:3-\frac{4x}{t_{0}}\right\}$と書けて(これはdesmos記法の条件分岐。標準的な記法で書くなら$\begin{cases} -1+\frac{4x}{t_{0}} & (0<x<\frac{t_{0}}{2}) \\ 3-\frac{4x}{t_{0}} & (\frac{t_{0}}{2}<x<t_{0}) \end{cases}$ のこと。)、これを16段階に切ってやるには8倍して床関数を噛ませればよくて、それを線形変換して-1~1の範囲におさめると$f(x) = \frac{\operatorname{floor}\left(\left\{0<x<\frac{t_{0}}{2}:-1+\frac{4x}{t_{0}},\frac{t_{0}}{2}<x<t_{0}:3-\frac{4x}{t_{0}}\right\}\cdot8\right)\cdot2+1}{15}$ と書ける。この$f(x)$ をフーリエ級数展開してやればいい。
正の整数$n$について$h(n) = \frac{2}{t_{0}}\int_{0}^{t_{0}}f\left(x\right)\cos\left(\frac{2\pi n x}{t_{0}}\right)dx$ とする。区分定数関数なので簡単に計算できて$$h(n) = \frac{4}{2\pi n}\sum_{l=0}^{15}\left(-1+\frac{2l}{15}\right)\left(\sin\left(\frac{2\pi n\left(l+1\right)}{32}\right)-\sin\left(\frac{2\pi nl}{32}\right)\right)$$シグマを展開すると隣り合う項同士が部分的に打ち消し合うので$$h(n) = \frac{4}{2\pi n}\left(\sin\left(\pi n\right)-\frac{2}{15}\sum_{m=0}^{15}\sin\left(\frac{2\pi m n}{32}\right)\right) $$
整数$n$に対して$\sin\left(\pi n\right) = 0$ である。偶数$n$に対しては$\sum_{m=0}^{15}\sin\left(\frac{2\pi m n}{32}\right)$というのは($n$が$32$の倍数でないのなら単位円上に等間隔に置かれた点のy座標の総和、$n$が$32$の倍数なら全部ゼロなので)ゼロ。ということでフーリエ級数展開は(収束性とかの議論をすっ飛ばして=を書いてしまうと) $$f(x) = \sum_{k=1}^{\infty}h\left(k\right)\cos\left(\frac{2\pi kx}{t_{0}}\right) = \sum_{k=0}^{\infty}h\left(2k+1\right)\cos\left(\frac{2\pi\left(2k+1\right)x}{t_{0}}\right) $$ sinの和をうまく積和で処理してやることで $$f(x) = \sum_{k=0}^{\infty}-\frac{4}{\pi\left(2k+1\right)}\left(\frac{\sin\left(\frac{\pi\left(2k+1\right)}{2}\right)\sin\left(\frac{15\pi\left(2k+1\right)}{32}\right)}{15\sin\left(\frac{\pi\left(2k+1\right)}{32}\right)}\right)\cos\left(\frac{2\pi\left(2k+1\right)x}{t_{0}}\right)$$ を得る。
メモ用紙はこちら。
実際どんな感じになるのかを見てみよう。2乗して対数取って10倍すればデシベルが出る。
ということで、第3倍音や第5倍音などについてはほぼ差は無いが、疑似三角波の方は例えば第31倍音が-29.83dBあり、これは第5倍音(-28.67dB)に匹敵するというわけか。なるほど。
追記
このサイトにも "a triangle wave generator with a 32-step waveform (16 steps up, 16 steps down)" と書いてあるので、16段階なんでしょう(てきとう)
ATOKを買ったのでAZIKにする on Windows (2020年)
概要
私がかつて使用していて、2020年4月末頃からまた使い出した日本語入力方法として、AZIKというのがある。AZIKというのは、一般的なローマ字テーブル1を微改造したローマ字テーブルである。ローマ字テーブルとは、要するにkyuと入力されたらそれを「きゅ」と解釈せよ、というのを収録している一覧表のことである。
AZIKの特徴として、「-aん」「-iん」「-uん」「-eん」「-oん」と「-aい」「-uう」「-eい」「-oう」が2ストロークで打てるというのがある。具体的には、例えば「-aん」には(QWERTY配列でAの下の)「Z」が、「-oう」には(Oの右の)「P」が当たっているので、
環状構造 → KZJPKPZP
高等教育 → KPTPKYPIKU
などと打つことができる。具体的な仕様については AZIK総合解説書 とか AZIKとは (エイズィックとは) [単語記事] - ニコニコ大百科 とかをどうぞ。個人的には「ぬ」とかが「NF」で打てるのが地味に便利だと思っている。
さて、Google日本語入力でAZIKを使っていたが、諸般の事情でATOKに乗り換えてみることにしてみた。その際、現在のATOKに入れる方法を調べるのに意外と時間がかかったのでメモしておく。
やり方
- ATOK2013,2014用AZIK(拡張ローマ字入力)定義ファイル - とぴやまのブログ(アーカイブ) にある azik/ATOK2014 at master · topiyama/azik · GitHub からSTYファイルをダウンロードしたのち、Ctrl+F12で出る「ATOKプロパティ」から「キー・ローマ字・色」を選択。「スタイル操作(F) ▼」から「スタイルコンバート」を選び、「スタイル」横の「参照」から先ほどダウンロードしたSTYファイルを選択し、「実行」。
終わりに
ということで無事AZIKを入れることができた。ATOKはなんか同期機能とかが嬉しいらしいので、AZIKにしていなかったMacBook ProのほうもAZIKにしようかな。辞書も共有できるらしく、それは普通にかなりありがたい。
-
少なくともAZIK考案者とGoogle日本語入力は「ローマ字テーブル」と呼んでいる。初見で意味が伝わりそうなのでこれに統一する↩
2次のエルミート行列を対角化 with 具体的なパラメータ表示
メインコンテンツ
「任意のエルミート行列はユニタリ行列によって対角化可能で、得られた対角行列の成分がすべて実数となるようにすることができる」という話はよく知られている。とはいえ、せっかくなので具体的なパラメータ表示とかをいい感じに探してみると面白そうなので探す。
2次
$\begin{pmatrix}a & be^{i\theta}\\be^{-i\theta} & d\end{pmatrix}$ (ただし $a, \theta, d \in \mathbb{R}$, $b \in \mathbb{R}_{\ge 0}$ )を対角化する。特性方程式は $(a-\lambda)(d-\lambda) -b^2 = 0$ なのであって $\lambda^2 - (a+d)\lambda + (ad-b^2) = 0$
ここで $(a+d)^2 - 4(ad-b^2) = (a-d)^2 + 4b^2$ なのであって常に非負。$0$になるのは $a=d, b=0$ のときのみであり、このとき元の行列は単位行列のスカラー倍。以下この場合は無視する。
$b=0$ のときは行列は既に対角化されている。よってこの場合についても無視する。
固有値は $\lambda_{\pm} = \frac{a+d\pm \sqrt{(a-d)^2 + 4b^2}}{2}$ であり、特に $\lambda_{+} + \lambda_{-} = a+d$、$\lambda_{+}\lambda_{-} = ad-b^2$となる。
$\begin{pmatrix}a & be^{i\theta}\\be^{-i\theta} & d\end{pmatrix}\vec{v_{+}} = \lambda_{+}\vec{v_{+}} $ から $\begin{pmatrix}a - \lambda_{+} & be^{i\theta}\\be^{-i\theta} & d - \lambda_{+}\end{pmatrix}\vec{v_{+}} = 0$
$\begin{pmatrix}a - \lambda_{+} & be^{i\theta}\end{pmatrix}$ と $\begin{pmatrix}be^{-i\theta} & d - \lambda_{+}\end{pmatrix}$ は線形従属(by construction)であり、また$b\ne 0$ゆえにゼロベクトルではない。
したがって $ \vec{v_{+}} = \begin{pmatrix}be^{i\theta} \\ \lambda_{+} - a\end{pmatrix}$ としてよい。同様に $ \vec{v_{-}} = \begin{pmatrix}be^{i\theta} \\ \lambda_{-} - a\end{pmatrix}$ である。
$ \vec{v_{\pm}} = \begin{pmatrix}be^{i\theta} \\ \frac{a+d\pm \sqrt{(a-d)^2 + 4b^2}}{2} - a\end{pmatrix}= b\begin{pmatrix}e^{i\theta} \\ \frac{-a+d\pm \sqrt{(a-d)^2 + 4b^2}}{2b} \end{pmatrix}= b\begin{pmatrix}e^{i\theta} \\ \frac{-a+d}{2b} \pm \sqrt{\left(\frac{a-d}{2b}\right)^2 + 1} \end{pmatrix}$
ここで $\phi := \mathrm{sin h}^{-1}\left(\frac{a-d}{2b}\right)$ と置けば $ \vec{v_{\pm}} = b\begin{pmatrix}e^{i\theta} \\ -\mathrm{sin h}\phi \pm \mathrm{cos h}\phi \end{pmatrix}$, $\lambda_{\pm} = \frac{a+d}{2} \pm\mathrm{cos h}\phi$
$ \vec{v_{-}} = b\begin{pmatrix}e^{i\theta} \\ -e^{\phi} \end{pmatrix}$ であり $ \vec{v_{+}} = b\begin{pmatrix}e^{i\theta} \\ e^{-\phi} \end{pmatrix}$
スカラー倍して $ \frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{-\phi/2+i\theta/2} \\ -e^{\phi/2-i\theta/2} \end{pmatrix}$ と $\frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{\phi/2 + i\theta/2} \\ e^{-\phi/2-i\theta/2} \end{pmatrix}$ にすればユニタリ行列の基底
まとめると、$a, \theta, d \in \mathbb{R}$, $b \in \mathbb{R}_{> 0}$ のとき
$\begin{pmatrix}a & be^{i\theta}\\be^{-i\theta} & d\end{pmatrix} = b\begin{pmatrix}\frac{a+d}{2b} + \frac{a-d}{2b} & e^{i\theta}\\e^{-i\theta} & \frac{a+d}{2b} - \frac{a-d}{2b}\end{pmatrix} $
$u := \frac{a+d}{2b}$ や $\phi := \mathrm{sin h}^{-1}\left(\frac{a-d}{2b}\right)$ とすれば
$= b\begin{pmatrix}u + \mathrm{sin h}\phi & e^{i\theta}\\e^{-i\theta} & u- \mathrm{sin h}\phi\end{pmatrix} $
の固有値・固有ベクトルは
$(\lambda_1, \vec{v_1}) = \left( bu-b\mathrm{cos h}\phi , \frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{-\phi/2+i\theta/2} \\ -e^{\phi/2-i\theta/2} \end{pmatrix} \right)$
$(\lambda_2, \vec{v_2}) =\left( bu+b\mathrm{cos h}\phi , \frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{\phi/2+i\theta/2} \\ e^{-\phi/2-i\theta/2} \end{pmatrix}\right)$
と書くことができ、$\begin{pmatrix}\vec{v_1} & \vec{v_2} \end{pmatrix} = \frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{-\phi/2+i\theta/2} & e^{\phi/2+i\theta/2} \\ -e^{\phi/2-i\theta/2} & e^{-\phi/2-i\theta/2} \end{pmatrix}$ はユニタリ行列である。
ちなみに
今回の記事も私がdraft.hyuki.netに書いた下書きをほぼそのままHatena Blogに持ってきたものです。前回の記事↓の一般化です。
あ、あとtypoなどありましたらTwitter(@hsjoihs)辺りに投げていただけるとありがたいです
書いた経緯
はこつきさん(@re_hako_moon)と話していたら生えた
2次の実対称行列を対角化 with 具体的なパラメータ表示
メインコンテンツ
「任意の実対称行列は直交行列によって対角化可能である」という話はよく知られている。とはいえ、せっかくなので具体的なパラメータ表示とかをいい感じに探してみると面白そうなので探す。今回は2次で。
$\begin{pmatrix}a & b\\b & d\end{pmatrix}$ (ただし $a, b, d \in \mathbb{R}$ )を対角化する。特性方程式は $(a-\lambda)(d-\lambda) -b^2 = 0$ なのであって $\lambda^2 - (a+d)\lambda + (ad-b^2) = 0$
ここで $(a+d)^2 - 4(ad-b^2) = (a-d)^2 + 4b^2$ なのであって常に非負。$0$になるのは $a=d, b=0$ のときのみであり、このとき元の行列は単位行列のスカラー倍。以下この場合は無視する。
$b=0$ のときは行列は既に対角化されている。よってこの場合についても無視する。
固有値は $\lambda_{\pm} = \frac{a+d\pm \sqrt{(a-d)^2 + 4b^2}}{2}$ であり、特に $\lambda_{+} + \lambda_{-} = a+d$、$\lambda_{+}\lambda_{-} = ad-b^2$となる。
$\begin{pmatrix}a & b\\b & d\end{pmatrix}\vec{v_{+}} = \lambda_{+}\vec{v_{+}} $ から $\begin{pmatrix}a - \lambda_{+} & b\\b & d - \lambda_{+}\end{pmatrix}\vec{v_{+}} = 0$
$\begin{pmatrix}a - \lambda_{+} & b\end{pmatrix}$ と $\begin{pmatrix}b & d - \lambda_{+}\end{pmatrix}$ は線形従属(by construction)であり、また$b\ne 0$ゆえにゼロベクトルではない。
したがって $ \vec{v_{+}} = \begin{pmatrix}b \\ \lambda_{+} - a\end{pmatrix}$ としてよい。同様に $ \vec{v_{-}} = \begin{pmatrix}b \\ \lambda_{-} - a\end{pmatrix}$ である。
$ \vec{v_{+}} \cdot \vec{v_{-}} = b^2 + \lambda_{+}\lambda_{-} -a(\lambda_{+} + \lambda_{-}) + a^2 $ $= b^2 + (ad-b^2) -a(a+d)+a^2 = 0$
よってこれら2つは直交する。ということで、これらを座標軸としながら $\vec{v_1} \times \vec{v_2} > 0$ となるような選び方をしたい。
$\vec{v_{+}} \times \vec{v_{-}} = b(\lambda_{-}-a)-b(\lambda_{+}-a) = -b(\lambda_{+} - \lambda_{-})$
よって、$b>0$ のときには $\vec{v_1}$ として $\vec{v_{-}}$ を、$b<0$ のときには $\vec{v_1}$ として $\vec{v_{+}}$ を選べばよい。
ということで $ \vec{v_1} = \begin{pmatrix}b \\ \frac{a+d - \frac{b}{|b|} \sqrt{(a-d)^2 + 4b^2}}{2} - a\end{pmatrix}= \begin{pmatrix}b \\ \frac{-a+d}{2} - b \sqrt{\left(\frac{a-d}{2b}\right)^2 + 1} \end{pmatrix}$
同様に $ \vec{v_2} = \begin{pmatrix}b \\ \frac{-a+d}{2} + b \sqrt{\left(\frac{a-d}{2b}\right)^2 + 1} \end{pmatrix}$
ここで $\phi = \mathrm{sin h} ^ {-1} \left(\frac{a-d}{2b}\right) $ と置けば
$ \vec{v_1} = \begin{pmatrix}b \\ -b\mathrm{sin h}\phi - b \sqrt{\mathrm{sin h}^2 \phi + 1} \end{pmatrix} = b\begin{pmatrix}1 \\ -\mathrm{sin h}\phi - \mathrm{cos h} \phi \end{pmatrix} = b\begin{pmatrix}1 \\ -e^{\phi} \end{pmatrix}$
この第二成分に$a$を足したものが$\lambda_1$であるので
$\lambda_{1} = a - be^\phi = \frac{a+d}{2} + \frac{a-d}{2b}b - be^\phi = \frac{a+d}{2} + b\mathrm{sin h} \phi - be^\phi = \frac{a+d}{2} -b\mathrm{cos h} \phi $
$ \vec{v_2} = \begin{pmatrix}b \\ -b\mathrm{sin h}\phi + b \sqrt{\mathrm{sin h}^2 \phi + 1} \end{pmatrix} = b\begin{pmatrix}1 \\ -\mathrm{sin h}\phi + \mathrm{cos h} \phi \end{pmatrix} = b\begin{pmatrix}1 \\ e^{-\phi} \end{pmatrix}$
この第二成分に$a$を足したものが$\lambda_2$であるので
$\lambda_{2} = a + be^{-\phi} = \frac{a+d}{2} + \frac{a-d}{2b}b + be^{-\phi} = \frac{a+d}{2} +b\mathrm{sin h}\phi + be^{-\phi} = \frac{a+d}{2} + b\mathrm{cos h}\phi $
ということで、$ \vec{v_1} $ と $ \vec{v_2}$ の定数倍である $\begin{pmatrix}e^{-\phi/2} \\ -e^{\phi/2} \end{pmatrix}$ と $\begin{pmatrix}e^{\phi/2} \\ e^{-\phi/2} \end{pmatrix}$ で扱うとよさそう。
まとめると、$a, b, d \in \mathbb{R}$ で $b\ne 0$ のとき
$\begin{pmatrix}a & b\\b & d\end{pmatrix} = b\begin{pmatrix}\frac{a+d}{2b} + \frac{a-d}{2b} & 1\\1 & \frac{a+d}{2b} - \frac{a-d}{2b}\end{pmatrix} $
$u := \frac{a+d}{2b}$ や $\phi := \mathrm{sin h}^{-1}\left(\frac{a-d}{2b}\right)$ とすれば
$= b\begin{pmatrix}u + \mathrm{sin h}\phi & 1\\1 & u- \mathrm{sin h}\phi\end{pmatrix} $
の固有値・固有ベクトルは
$(\lambda_1, \vec{v_1}) = \left( bu-b\mathrm{cos h}\phi , \frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{-\phi/2} \\ -e^{\phi/2} \end{pmatrix} \right)$
$(\lambda_2, \vec{v_2}) =\left( bu+b\mathrm{cos h}\phi , \frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{\phi/2} \\ e^{-\phi/2} \end{pmatrix}\right)$
と書くことができ、$\begin{pmatrix}\vec{v_1} & \vec{v_2} \end{pmatrix} = \frac{1}{\sqrt{2\mathrm{cos h}\phi}}\begin{pmatrix}e^{-\phi/2} & e^{\phi/2} \\ -e^{\phi/2} & e^{-\phi/2} \end{pmatrix}$ は回転行列である。
ちなみに
今回の記事は私がdraft.hyuki.netに書いた下書きをほぼそのままHatena Blogに持ってきたものです。
を進めればSATySFiに持っていけるし、やってはみたい……けれど………
あ、あとtypoなどありましたらTwitter(@hsjoihs)辺りに投げていただけるとありがたいです
書いた経緯
ゆかたゆさん(@yukata_yu)と話していたら生えた
2014年ごろの私「読み書きしやすくするためにBrainf*ckに抽象化を入れよう」
この記事はBrainf*ck Advent Calendar 2019の20日目の記事です。
概要
- Brainf*ckにゼロコスト抽象化*1を入れた言語、CamphorScriptを2014年頃に作った話です
- 「Brainf*ck、コードの再利用さえできれば普通に楽しい言語なのになぁ」という思いを元に、演算子オーバーロードとインライン関数とかを大量導入したラッパー言語です
- Brainf*ckにコードの再利用を足そうというアイデアは https://aike.hatenablog.com/entries/2009/02/09 から得ました
- 「Brainf*ckに新しい要素を付け足した言語をやりたいんじゃなくて、あくまでBrainf*ckを書きたいんだよな」という人のためのコンパイラ・デコンパイラを提供します
- アセンブリを読む際に、理解した部分をCで書いてコンパイル、対象のアセンブリとだいたい一致することを以て理解を確認したりしますよね?それをBrainf*ckでやりたかった
- CやC++に意図的に見た目をかなり寄せているものの、意味論はかなり別物で、Brainf*ck側に寄り添っている
- リポジトリはこちら
自分語り(あんまり本題に関係ないので読み飛ばしてよい)
全ての始まりは、2013年の夏に参加した情報オリンピック夏季セミナーで『すごいHaskellたのしく学ぼう!』を読んだことから始まる。
歴史に残ることとなる
ヌエックの人「ヌエッ」
— きゅうり (@kyuridenamida) 2013年8月28日
などの名言が生み出されているとはつゆ知らず、私はHaskellにドハマリしていったのであった。型システムによって実行前にマズいコードを排除できるというのはなんとすごいことであるかと、当時JavaScriptぐらいしか書いたことがなくCannot read property '0' of undefined
でn時間を溶かした経験がいくらでもあった私は感動して3日ぐらいで本を読み切った覚えがある。ユーザーが自由に演算子を定義できるのも新鮮だったが、その抽象化力を以て言語仕様を小さくし*2、他の言語なら言語仕様としてアドホックに導入するものをライブラリとして提供しているのも面白いと思った。ということで、このHaskellの「高い抽象化により、コア言語の大きさをなるべく削減しつつライブラリに機能を委任」をBrainf*ckに適用し、ゼロコスト抽象だけでCっぽい見た目の言語を作ろう(もちろんHaskellで)として誕生したのがCamphorScriptである。
その後わりと放置していたが、2019年8月頭に人と会ったとき
ピザを食べに行こうと思ったら再帰的関数論とCamphorscriptを布教された(???) #ピザの集い
— 考察に紙とペンを使う (@yosswi414_0) 2019年8月4日
今日は @yosswi414_0 さんにCamphorScriptの説明をしたりした。作ったのが5年前であっても意外と覚えてて熱く語れるもんだなぁと思うなどした。https://t.co/BnPai7Y1MW
— hsjoihs (@hsjoihs) 2019年8月4日
と意外と内容を覚えていて熱く語れることに気づき、せっかくならアドカレに載せようと決めたので書いている。
以下CamphorScriptの紹介
関数と演算子
ということで、
Brainf**k、IOの状態を気にするとかそんな甘ったるいレベルじゃなく、メモリ上の全状態をコード書きが把握しているのを要求してくる。アレつらい。
— Deleting null solves all problems (@Kory__3) 2018年2月13日
を解決するためにメモリの抽象化としての変数を導入するのはもちろん、Brainf*ck中に出てくる頻出パターンを関数や演算子として抽象化できるようにし、しかもそれをライブラリとして提供できるように考えた。特に、Haskellでユーザーが自由に演算子を定義できることに影響され、ライブラリ側でどんどん演算子が追加できるようにした。
Brainf*ckではデータをコピーするにあたっても「Aを破壊し、それと同時にAの値をBとCに移す」という操作のほうが「Aを破壊せずAの値をBに移す」よりも軽い。そのような頻出処理にclear_the_first_and_add_to_the_second_and_to_the_third(a,b,c);
などという名前をつけるのはあまりにも仰々しいので、演算子にしてしまいたい。CamphorScriptでは、標準ライブラリeq_til
をインクルードすることにより、この処理を (b, c) += ~a;
と書くことができる。
【 ~
はC++のデストラクタの†イメージ†で、直後の変数の値がこの文によって破壊され、0になるということを意味する。その破壊される前のa
の値が、+=
の働きによりb
とc
へと足されていく】
…という現象があたかも起こっているかのように書けるようになっている。
とはいえもちろん、当然ながら舞台裏で起こっていることはそのようなことではない。標準ライブラリeq_til
の冒頭は次のようになっている。
#ifndef __STD_LIB_EQ_TIL_DEFINED__ #define __STD_LIB_EQ_TIL_DEFINED__ #include <fixdecl> void (+=~)(char& a;char& z){ while(z){a+=1;z-=1;} } /* a+= ~z */ void (+=~)(char& a,char& b;char& z){ while(z){a+=1;b+=1;z-=1;} } /* (a,b)+= ~z*/ void (+=~)(char& a;char& z * constant char N){ while(z){a+=N;z-=1;} } /* a+= ~z*N */
...
戻り値のところにvoid
と書いてあるが、これは見た目をC/C++に寄せるためのフェイクであり、実情としては関数であることを示すだけの予約語である。当時Rustを知っていたらfn
とかにしていたかも*3
(+=~)
という関数/演算子がオーバーロードされていることが分かるが、今回呼び出される関数はこのうち2番目のものである。void (+=~)(char& a, char& b; char& z)
とあり、なぜか引数区切りに記号にカンマとセミコロンの両方が登場している。これはどういうことかというと、(b, c) += ~a;
は (+=~)(b, c; a);
の糖衣構文であり、関数が演算子として定義されている場合は引数区切りでセミコロンが入るところに演算子を中置して用いることができる、という仕様になっているのだ。
同様に、三番目の (+=~)(char& a;char& z * constant char N)
というのも a += ~z * 8
として呼び出すことを目的として定義されている関数であり、Brainf*ckで頻繁に出てくる掛け算パターンを読みやすくすることができる。
さて、ここまで関数、関数と書いてきたが、もちろん生の関数がBrainf*ckにあるわけはなく、全てインライン展開される。当然ながら再帰(相互再帰含む)は禁止してある。
カスタム構文
制御構文が[]
、C風に言うならwhile
、しかないというのも、Brainf*ckの美しさでありBraif*ckプログラミングのつらさである。ということで構文すらライブラリで定義できるようにした。
syntax if(~ char& a){block;} { while(a) { while(a){a -= 1;} block; } }
と定義することで、if(~a){~~~}
と書いてあるところをwhile(a) { while(a){a -= 1;}~~~ }
と書き換えよ、と宣言することができる。なおblock
は予約語である。もっとマシな構文は思いつかなかったのだろうか*4。
型システム(笑)
関数/演算子の引数にchar&
とかconstant char
とかあるが、一応これに対しては型チェックが入り、 char&
は変数のみを、constant char
は定数のみを受け取る*5。const char
でchar&
とconstant char
の両方が受け取れるようになっている。
「暇があったら是非構造体やら列挙体やらを追加したい」ともう4年ぐらい前から言っているが、その「暇」とやらがあった試しはない。
この型システム(笑)の嬉しさを少しでも上げるべく、「ヌル関数」という言語仕様もある。どういうことかというと、void (+=~)(constant char N;char& z) = 0;
と書いておくことにより、8 += ~a;
といったコードをコンパイルエラーにできるという代物である*6。
プリプロセッサ(笑)
Cのプリプロセッサの劣化版が実装されているのだが、これは既存のCプリプロセッサを使うという発想が無かった(Cプリプロセッサが普通にHaskellに移植されていることを知ったのは開発が結構進んでからである)ために生まれた四角い車輪の再発明であるので、改善していきたいが、実はCプリプロセッサとは仕様が微妙に違い、かつ既存のコードがそれに依存しているため、単純に置き換えるわけにもいかない。
コア言語CompiledCamphorScript
ここでいう「コア言語」はC++における意味(C++の仕様から標準ライブラリを引き算した部分)ではなく、Haskellにおける意味(脱糖して得られるサブセット言語)である。プリプロセッサと関数のインライン展開を済ませ、残っている抽象化は変数ぐらいしか無いという状態である。
具体的なコード例を示すと次の通り。
char a; char b; char c; char dig1; char dig2; char dig3; char g; a+=4; while(a){ b+=4; { while(b){c+=3;b-=1;} } /* c+=12;*/ a-=1; } /* c += 48*/ delete a; delete b; read(dig1); read(dig2); read(dig3); while(c){ dig1-=1; dig2-=1; dig3-=1; c-=1; } { while(dig3){g+=1;dig3-=1;} } while(dig2){ dig3+=5; { while(dig3){g+=2;dig3-=1;} } /* g += 10;*/ dig2-=1; } /* g += ~dig2 * 10;*/ while(dig1){ dig2+=5; while(dig2){ dig3+=5; { while(dig3){g+=4;dig3-=1;} } /* g+=20;*/ dig2-=1; } /*g += 100;*/ dig1-=1; } /* g+= ~dig1 * 100*/ write(g);
こんな記事をここまで読むほどBrainf*ckに慣れ親しんでいる皆さんなら、このコードを手作業でBrainf*ckに直すことなど容易いだろう。もちろん私にとっても容易いのでちゃんとBrainf*ck化するコードは組んであり、それを通すと
++++[>++++[>+++<-]<-]>>>,>,>,<<<[>->->-<<<-]>>>[>+<-]<[>+++++[>++<-]<-]<[>+++++[>+++++[>++++<-]<-]<-]>>>.
という、我々のよく知るBrainf*ckが出てくるわけである。
変数
Brainf*ckではメモリというのはゼロ初期化されているので、使用し終わったメモリの値が0であることが明示できると、それをコンパイラ側で別の変数に使い回すことができるわけだ。ということで、使用済みメモリの値が0であるとプログラマーが保証する文delete
が用意されている。
なお、ブロック内で確保した変数は必ずdeleteしなければならない。RAIIってやつである。関数/演算子がインライン展開される際のブロックにもこの制約は適用されるので、メモリをゴリゴリ食いつぶして返却しない関数が定義できないようになっている。
例えば、変数を変数に非破壊的に+=する処理を書くなら次のようになる(もちろん標準ライブラリにある)(もちろんこれはCompiledCamphorScriptではなくCamphorScriptのコードである)。
void (+=)(char& to; char& from) { char c2 = 0; while(from){ to += 1; c2 += 1; from -= 1;} while(c2){ from += 1; c2 -= 1;} delete c2; }
確保されるメモリの量はコンパイル時に確定する。本当はメモリの配置を上手く工夫することでBrainf*ckに翻訳した際の>と<をなるべく減らせるようにしたかったが、それを実現するためのアルゴリズムもヒューリスティックも当時の私には実装できなかったため、実装されていない。
また、静的解析で全てメモリを握っている都合上、「実行時に長さが決まる0終端文字列を次々なめていく」というようなプログラムはCamphorScriptで書くことができず、そのようなプログラムをBrainf*ckからCamphorScriptへと逆コンパイルしようとするとエラーを吐く。つまり、実はBrainf*ckのサブセットしか現状のCamphorScriptでは表現できない。改善してはみたいが、本質的にCamphorScriptの表現力を爆上げしなければならないということでもあり、なかなか難しそうである。
(「Brainf*ckからCamphorScriptへと逆コンパイル」と書いたが、現状では実際はCompiledCamphorScriptへと逆コンパイルされる。「標準ライブラリと照らし合わせてパターンを検出し自動的に演算子化」とかができたらたのしいのになぁ)
せっかくなので
AtCoder Beginners Selection の PracticeA - Welcome to AtCoder の既存提出 Submission #2237782 をCamphorScript化してみよう。提出されたBrainf*ckソースをそのままデコンパイル…したものは533行あったので、改行とインデントを大胆に手動削除したものがこちら。
char v_0;char v_1;char v_2;char v_3;char v_4;char v_5;char v_6;char v_7; char v_8;char v_9;char v_10; read(v_5); v_5-=10; while(v_5) { v_5-=2; v_6+=6; while(v_6){ v_5-=6; v_6-=1; } while(v_2){ v_1+=1; v_2-=1; } while(v_3){ v_2+=1; v_3-=1; } while(v_4){ v_3+=1; v_4-=1; } while(v_5){ v_4+=1; v_5-=1; } read(v_5); v_5-=10; } read(v_9); v_10+=8; while(v_10){ v_9-=4; v_10-=1; } while(v_9) { v_10+=4; while(v_10){ v_9-=4; v_10-=1; } while(v_6){ v_5+=1; v_6-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_7+=1; v_8-=1; } while(v_9){ v_8+=1; v_9-=1; } read(v_9); v_10+=8; while(v_10){ v_9-=4; v_10-=1; } } while(v_8){ v_4+=1; v_8-=1; } while(v_7){ v_3+=1; v_7-=1; } while(v_6){ v_2+=1; v_6-=1; } while(v_5){ v_1+=1; v_5-=1; } while(v_4){ v_5+=1; v_6+=1; v_4-=1; } while(v_6){ v_4+=1; v_6-=1; } v_6+=10; while(v_5) { v_8+=1; while(v_6){ v_6-=1; v_5-=1; while(v_6){ v_7+=1; v_6-=1; } v_8-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_8-=1; while(v_5){ v_5-=1; } } } v_5+=1; while(v_6){ v_5-=1; while(v_6){ v_6-=1; } } while(v_5){ v_4-=10; v_3+=1; while(v_5) { v_5-=1; } } while(v_3){ v_5+=1; v_6+=1; v_3-=1; } while(v_6){ v_3+=1; v_6-=1; } v_6+=10; while(v_5) { v_8+=1; while(v_6){ v_6-=1; v_5-=1; while(v_6){ v_7+=1; v_6-=1; } v_8-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_8-=1; while(v_5){ v_5-=1; } } } v_5+=1; while(v_6){ v_5-=1; while(v_6){ v_6-=1; } } while(v_5){ v_3-=10; v_2+=1; while(v_5){ v_5-=1; } } while(v_2){ v_5+=1; v_6+=1; v_2-=1; } while(v_6){ v_2+=1; v_6-=1; } v_6+=10; while(v_5) { v_8+=1; while(v_6) { v_6-=1; v_5-=1; while(v_6){ v_7+=1; v_6-=1; } v_8-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_8-=1; while(v_5){ v_5-=1; } } } v_5+=1; while(v_6){ v_5-=1; while(v_6){ v_6-=1; } } while(v_5) { v_2-=10; v_1+=1; while(v_5) { v_5-=1; } } read(v_9); v_9-=10; while(v_9) { v_9-=2; v_10+=6; while(v_10){ v_9-=6; v_10-=1; } while(v_6){ v_5+=1; v_6-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_7+=1; v_8-=1; } while(v_9){ v_8+=1; v_9-=1; } read(v_9); v_9-=10; } while(v_8){ v_4+=1; v_8-=1; } while(v_7){ v_3+=1; v_7-=1; } while(v_6){ v_2+=1; v_6-=1; } while(v_5){ v_1+=1; v_5-=1; } while(v_4) { v_5+=1; v_6+=1; v_4-=1; } while(v_6){ v_4+=1; v_6-=1; } v_6+=10; while(v_5) { v_8+=1; while(v_6) { v_6-=1; v_5-=1; while(v_6){ v_7+=1; v_6-=1; } v_8-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_8-=1; while(v_5){ v_5-=1; } } } v_5+=1; while(v_6){ v_5-=1; while(v_6){ v_6-=1; } } while(v_5) { v_4-=10; v_3+=1; while(v_5) { v_5-=1; } } while(v_3) { v_5+=1; v_6+=1; v_3-=1; } while(v_6){ v_3+=1; v_6-=1; } v_6+=10; while(v_5) { v_8+=1; while(v_6) { v_6-=1; v_5-=1; while(v_6){ v_7+=1; v_6-=1; } v_8-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_8-=1; while(v_5){ v_5-=1; } } } v_5+=1; while(v_6){ v_5-=1; while(v_6){ v_6-=1; } } while(v_5) { v_3-=10; v_2+=1; while(v_5) { v_5-=1; } } while(v_2) { v_5+=1; v_6+=1; v_2-=1; } while(v_6){ v_2+=1; v_6-=1; } v_6+=10; while(v_5) { v_8+=1; while(v_6) { v_6-=1; v_5-=1; while(v_6){ v_7+=1; v_6-=1; } v_8-=1; } while(v_7){ v_6+=1; v_7-=1; } while(v_8){ v_8-=1; while(v_5){ v_5-=1; } } } v_5+=1; while(v_6){ v_5-=1; while(v_6){ v_6-=1; } } while(v_5) { v_2-=10; v_1+=1; while(v_5) { v_5-=1; } } v_5+=1; v_6+=1; while(v_1) { v_6-=1; v_0+=8; while(v_0){ v_1+=6; v_0-=1; } write(v_1); v_5-=1; while(v_1){ v_1-=1; } } while(v_5){ v_5-=1; } while(v_6) { v_7+=1; v_8+=1; v_6-=1; } while(v_8){ v_6+=1; v_8-=1; } v_8+=1; while(v_7) { v_5+=1; while(v_2) { v_6-=1; v_1+=8; while(v_1){ v_2+=6; v_1-=1; } write(v_2); v_5-=1; while(v_2){ v_2-=1; } } while(v_5){ v_5-=1; } while(v_8){ v_8-=1; } while(v_7){ v_7-=1; } } while(v_8) { v_1+=8; while(v_1){ v_2+=6; v_1-=1; } write(v_2); while(v_2){ v_2-=1; } while(v_8){ v_8-=1; } } while(v_6) { v_7+=1; v_8+=1; v_6-=1; } while(v_8){ v_6+=1; v_8-=1; } v_8+=1; while(v_7) { v_5+=1; while(v_3) { v_6-=1; v_2+=8; while(v_2){ v_3+=6; v_2-=1; } write(v_3); v_5-=1; while(v_3){ v_3-=1; } } while(v_5){ v_5-=1; } while(v_8){ v_8-=1; } while(v_7){ v_7-=1; } } while(v_8) { v_2+=8; while(v_2){ v_3+=6; v_2-=1; } write(v_3); while(v_3){ v_3-=1; } while(v_8){ v_8-=1; } } v_3+=8; while(v_3){ v_4+=6; v_3-=1; } write(v_4); v_2+=8; while(v_2){ v_1+=4; v_2-=1; } write(v_1); while(v_1) { read(v_1); write(v_1); v_1-=10; }
うわぁ。これならまだBrainf*ckの方が読みやすいんじゃないか。
と言ってても始まらないので、じっくりコードを読んで繰り返し登場する処理がないかを(3時間半ぐらい掛けて)探すと……
#include <eq_til> #include <stdcalc2> syntax if(~char& a){block} { while(a) { block; while(a){a-=1;} } } syntax if(! ~char& flag1){block} { char a; a += ! ~~flag1; if(~a) { block; } delete a; } infixr 5 (+=!~~); void (+=!~~)(char& a;char& z){ a+=1; if(~z){a-=1;} } infixl -5 (?@,); void (?@,)(char& b; char& a, char& d -= constant char N){ char c; while(b){ b -= N; a -= N; c +=~ b; d -= N; } b +=~ c; delete c; } infixl -5 (?~); /* if d, clear a */ void (?~)(char& d; char& a) { while(d){ d -= 1; clear(a); } } infixr 5 (-|=~~); void (-|=~~)(char& b;char& a){ /* if(a>=b){a=0;b=0;}else{b-=a;a=0;} */ while(a){ char dummy; char d = 1; delete dummy; b ? @, a, d -= 1; d ? ~a; delete d; } } void carry(char& to +<- char& from, constant char N) { char a; a += from; char b; b += N; /* if (from >= N) { b = 0; } else {b = N - from; } */ b -|=~~ a; /*# MEMORY using a #*/ if(! ~b) { from -= N; to += 1; } delete b; delete a; } void read_till_newline(char& buf_1000, char& buf_100, char& buf_10, char& buf_1) { char v_5; read(v_5); v_5 -= '\n'; while(v_5){ v_5 -= 2; v_5 -= 6 * 6; shift_left(buf_1000 +=, buf_100, buf_10, buf_1, ~v_5); read(v_5); v_5-=10; } delete v_5; } void read_till_space(char& buf_1000, char& buf_100, char& buf_10, char& buf_1) { char v_9; read(v_9); v_9 -= 8 * 4; while(v_9){ v_9 -= 4 * 4; shift_left(buf_1000 +=, buf_100, buf_10, buf_1, ~v_9); read(v_9); v_9 -= 8 * 4; } delete v_9; } infixl 0 (,~); infixl 0 (+=,); void shift_left(char& a +=, char& b, char& c, char& d,~ char& e) { a +=~ b; b +=~ c; c +=~ d; d +=~ e; } void baz(char& v_7 ?~ char& v_8, char& a, char& b, char& v_6) { char v_5; if (~v_7) { v_5+=1; if (~a) { v_6-=1; b += 8; a +=~ b * 6; write(a); v_5-=1; } clear(v_5); clear(v_8); } delete v_5; } void bar(char& v_6, char& a, char& b) { char dummy; char v_7; v_7 += v_6; char v_8 =1; delete dummy; baz(v_7 ?~ v_8, a, b, v_6); delete v_7; if(~v_8){ b += 8; a +=~ b * 6; write(a); clear(a); } delete v_8; } char v_0; char ans_1000; char ans_100; char ans_10; char ans_1; read_till_newline(ans_1000, ans_100, ans_10, ans_1); { char buf_1000; char buf_100; char buf_10; char buf_1; read_till_space(buf_1000, buf_100, buf_10, buf_1); ans_1 +=~ buf_1; ans_10 +=~ buf_10; ans_100 +=~ buf_100; ans_1000 +=~ buf_1000; delete buf_1000; delete buf_100; delete buf_10; delete buf_1; } carry(ans_10 +<- ans_1, 10); carry(ans_100 +<- ans_10, 10); carry(ans_1000 +<- ans_100, 10); { char buf_1000; char buf_100; char buf_10; char buf_1; read_till_newline(buf_1000, buf_100, buf_10, buf_1); ans_1 +=~ buf_1; ans_10 +=~ buf_10; ans_100 +=~ buf_100; ans_1000 +=~ buf_1000; delete buf_1000; delete buf_100; delete buf_10; delete buf_1; } carry(ans_10 +<- ans_1, 10); carry(ans_100 +<- ans_10, 10); carry(ans_1000 +<- ans_100, 10); char v_5 = 1; char v_6 = 1; while(ans_1000){ v_6-=1; v_0+=8; ans_1000 +=~ v_0 * 6; write(ans_1000); v_5-=1; clear(ans_1000); } clear(v_5); delete v_5; bar(v_6, ans_100, ans_1000); bar(v_6, ans_10, ans_100); delete ans_1000; delete ans_100; ans_10+=8; ans_1 +=~ ans_10 * 6; delete ans_10; write(ans_1); char v_1; v_1 += 8 * 4; write(v_1); while(v_1){ read(v_1); write(v_1); v_1-=10; }
と、まあちょっとは抽象化できる。
なんか途中に説明していない/*# MEMORY using a #*/
とかいうものがあるが、これはsyntax if(! ~char& flag1){block}
の呼び出し内で宣言されているローカル変数のための領域として、直前のb -|=~~ a;
により実は0クリアされているa
を使ってくれという指令である。こうしないと元の提出コードに一致するBrainf*ckへとコンパイルされない。
今後の課題
上述したこと以外の課題としては、そもそもBrainf*ckでは結局「アドレスを記録しそれを元にメモリにアクセスする」ということが(素朴には)できない(下スライドにあるポインタフラグ付き配列によりわりといい感じにはできるが)以上、抽象化だったりデータ構造を作っていったりというのにも限界がありそうだという、考えてみれば当然の壁がある。といっても、先人たちのBrainf*ckでのデータ構造の実装例についてまだあまり知らないため、調べてみると思いの外抽象化できるパターンなどが見つかるかもしれない。↓は読んだけれども、静的解析で処理できないデータ構造をいい感じにコア言語に組み込み、しかもそこまでアドホックでなくする方法はあるのだろうか。Brainf*ckプログラマの皆様のご意見など賜わることができれば幸いです
*1:当時はそんな単語知らなかった
*2:GHC拡張のマニュアルを日本語訳している私「たしかにHaskell自体の言語仕様は小さいけど、GHC拡張が膨大なんだよなぁ」
*3:当時JavaScriptは知っていたのだからfunctionにする選択肢はあって、それを採用しなかったのは多分無駄に長いからとかだろう。一応戻り値がvoidでない関数を将来実装することを考えていた可能性もあるが
*4:自分で作った言語の批判、一切忌憚なくできるからアドだということに気づいた。
*5:当時は「ロベールのC++」しか読んでいなかったのでconstexprという名前を知らなかった
*6:一見void (+=~)(constant char N;char& z)をただ定義しないだけで済む話にも見えるが、ヌル関数を予め定義しておくとユーザー側で新たにvoid (+=~)(constant char N;char& z)を定義することができなくなるという利点がある。