本エントリ投稿の 2, 3 ヶ月前に Haskell でスクラッチから x86-64 向けの C コンパイラを作った. 本エントリは, その記録である.

動機/背景

コンパイラの自作は, 社会人になる前に, 前々から一度はやっておきたいと思っていた事柄の一つであったこと, また関数プログラミングとの関係性について探求したかったこと, さらに, 一部には, 関数プログラミングはコンパイラ開発を容易にする¹という認識があるが, 数学的構造の実用化の一つとも言える関数プログラミングに関する考察においては, 圏論的な理由付けによりその有用性を言うことができるはずであろうという, 私の中での何となくの予想が本当であるのかどうか, 確認したかったことから, 実際に Haskell で C コンパイラを作るに至った. なお, 圏論の話題は再度別のエントリとしてまとめ, その後, さらに別のエントリにそれと関連付いた話題としてまとめようと考えているため, 本エントリでは特に立ち入らず, あくまでも, Haskell で C コンパイラを作ってみたという単なる取り組みへの記録程度に止める.

ブール代数は古典論理における命題論理と密接に関連している. 結論からいえば, 両者の違いは歴史的な背景ぐらいであり, 殆どの場合は同等の理論であるということができる¹. ブール代数はその応用として論理回路の構築に直接役立つことから, 計算機科学, とくにハードウェアの分野において重宝される代数系の 1 つである.

ブール代数の公理とその定理

次に示すのはブール代数の公理系である. 公理系に関する詳細は証明理論 (TODO) の冒頭を参照のこと.

また, この $1,0$ からのみ成る集合をブール領域, ブール代数の下に書かれた式をブール式, $n\in\mathbb{N}$ 個のブール領域の引数をとり, 1 個のブール領域の値となる関数 $f:B^n\to B$ をブール関数という. 例えば, 2 変数ブール関数 $f(x_1,x_2)$ では $x_1,x_2$ がそれぞれ $1,0$ のいずれかとなるので, $2^4=16$ 通りの 2 変数ブール式が存在することとなる. 以下, 演算の優先順序は左結合性で $',\land,\lor$ の順とする. ただし, 括弧内の演算はより優先される.

さてブール代数の公理における乗法 $\land$ と加法 $\lor$, および $1, 0$ をそれぞれ入れ替えると, 再びブール代数の公理である. これは双対の原理という公理である.

これらの公理から補元の一意性, べき等律, 有界律, 吸収律, 結合律, 対合律, ド・モルガンの法則, シャノンの展開定理が導出可能である. 以下 $x,y,z\in B$ とする.

関係 (集合論) について復習.

一般的な関係

いま, 二つの要素の順序体を $\left\lt a, b\right\gt$ と書くこととする. 他の異なる順序体 $\left\lt c, b\right\gt$ に対し, 以下の通り定義する.

$$\begin{aligned} \left\lt a,b\right\gt=\left\lt c,d\right\gt&:=&a=c, b=d\\ {\rm デカルト積} = {\rm 直積} = A\times B&:=&\left\{\left\lt a,b\right\gt\mid a\in A, b\in B\right\} \end{aligned}$$

このとき順序体の要素を $n$ 個に拡張したものを $n$-tuple といい, 以下の通り定義する.

放物運動に関する復習と再現.

等加速度運動をする物体の位置関数の導出

時刻 $t=0$ における物体の位置を ${\boldsymbol x_0}$, 速度を ${\boldsymbol v_0}$ とし, 加速度を考慮しない等速運動の三次元空間上の一点に対する位置関数 ${\boldsymbol x}(t)$ を $${\boldsymbol x}(t)={\boldsymbol x_0}+{\boldsymbol v_0}t$$ とおく. このとき, 時間 $t_1$ から $t_2$ への変化量 ${\boldsymbol x}(t_2)-{\boldsymbol x}(t_1)$ を $\Delta t=t_2-t_1$ で割れば, 時間経過に対する物体の位置の対比が得られる. これは正しく速度のことであるが, これは時間 $t_1$ に位置 ${\boldsymbol x}(t_1)$, 時間 $t_2$ に位置 ${\boldsymbol x}(t_2)$ にあった物体の平均速度である. いま時間 $t$ における物体の瞬間速度を知りたいとすると, $\Delta t$ が微小量となるように極限($t_2\to t_1\Leftrightarrow \Delta t\to 0$)を取れば良い.

要旨

本エントリー(WIP)はカーブフィッティング全般に関して記述したものであり, それぞれの原理, 性質について学んだ際のメモとして, より単純なものから広く浅く挙げています. 極力ないようにはしていますが, 本内容は独学で得た知見より書いておりますので, 一部正確さが欠けている可能性があることは否めません. 何かありましたら, コメント等で指摘していただけるとありがたいです. また, 本エントリ内における近似およびプロット等に関する実装は次のリポジトリ

にまとまっています.