C++ テンプレートメタプログラミングによるコンパイル時 Lazy K インタプリタ

※1. この記事は「KLab Engineer Advent Calendar 2020」の 16 日目にエントリしています
※2. 普段のこのブログの文体は常体ですが, 本記事においては Advent Calendar 用に敬体を使用します

Yellow duck Christmas ornament - m01229, Attribution 2.0 Generic (CC BY 2.0)

はじめに

この記事の公開日の 1 日前1に, プログラミング言語 C++ の新バージョン ISO/IEC 14882:2020, 通称 C++20 が国際標準として公開されました. これにより, いくつかの新しい言語機能や標準ライブラリが追加されます. その中でも, とくにコンセプトという言語機能は, テンプレートメタプログラミングが話題として盛んであった時代2から待望されていた言語機能のうちの 1 つなのではないでしょうか. この標準化によって, C++17 までで行う必要のあった多くの型制約のためのテンプレートメタプログラミングは, よりそれ専用の言語機能であるコンセプトを使う形に置き換えられるであろうと思われます. そのようなわけで, 今後徐々に出番を失っていくであろうテンプレートメタプログラミングを将来懐かしめるよう (?), テンプレートメタプログラミングによってコンパイル時に Lazy K ソースコードをパースして評価するインタプリタのようなものを書いてみました. 本記事では, これに関する実装と理論について紹介します. (型無し λ\lambda 計算について既知のものとします)

Read More...

個人ページ, ブログを移行した

旧個人ページ及び, 旧ブログを本ウェブサイト (roki.dev), 本ブログ (roki.dev/roki.log, roki.dev/roki.diary) に移行した. 以下では, 移行した経緯や技術的概要, 本サイトおよびブログの方針について (ゆるく) 紹介したい.

移行に至った経緯

移行前の旧ブログ1の構成では, static site generator である pelican を使っていた. 以下に, それを使ってそこそこの期間の運用をした上での実状, 感想を挙げる.

  • テンプレートプラグインが充実しており, 設定も非常に少ない記述から簡潔に行えるようになっていて, 主観的な感想として pelican は使い勝手の良いツールであった. 自分の場合は, nikhil-theme を元に拡張して利用しており, いくつかの機能の追加実装や bug fix, 依存関係の更新作業などを行っていた
  • 記事の執筆は Markdown で行い, D3.js や emscripten を導入していたので, 記事内で簡単なシミュレータや計算の視覚化などでヌルヌル動かしたり, 遊んだりできるようにしていた
  • 執筆時には MathJax が意図通り描画できているか等で瞬時にプレビューを見たかったため, 記事内の更新に合わせて記事のリビルド, ブラウザの自動リロードがされるスクリプトを作り, それを実用していたのでブログ記事執筆時のストレスもそこまではなかった
  • 全体のブログ記事管理の仕組みとして, draft から release ブランチに merge & push すると, Bitbucket Pipelines が走り2, ブログのビルドと GitHub pages へのデプロイが実行されるようにしていたので, 管理コストや記事公開のための作業も少なく, その点は快適であった
  • その他の細かい作業 (旧ブログ記事) を行うことで“色々とそれなりに”便利にしていた

…とこれまでを振り返ると, あまり不満はなかったのではないかというような気がしてくるが, 全く不満がなかったかというとやはりそうではない.

  • 元テンプレートの Bootstrap のバージョンが低い
  • MathJax が重い
  • テンプレートが膨大
  • 標準 (プラグイン) の検索機能が日本語に未対応
  • リンクのバリデーション機能がない
  • 無料 GitHub アカウントでもプライベートリポジトリが使えるようになり, Bitbucket と GitHub 間を横断させる必然性がなくなった (GitHub Actions も使えるようになったことで, ブログ管理のすべてを GitHub のみで一元管理できる)
  • 記事や記事内で使うスクリプトを校生するもの (textlint の linter 等) と, ブログそのもの (Jinja2 テンプレート, ビルド, デプロイ, ライブプレビュー, プラグイン管理…) は全くの別物なので, これらの管理を分離したい

無論, 元のブログでも修正, 更新, 機能追加でこれらをすべて満たそうとすることはできるが, もうそこまでするならいっそのことリニューアルしてしまったほうが…🤔となってしまった.

ブログの他にも, 個人 (プロフィール) サイトを公開しており, それにおいては Typescript + React を使って構築していた3. こちらは特に何か変わったこともしていないので, 特筆すべきトピックもないのだが, そこまで DOM 操作をするわけでもないプロフィールページにこれらの技術を用いたのはオーバースペックだったし, bundle.js の重さからしてもあまり理にかなっていなかったように思う.

Read More...

Haskell で C コンパイラを作ってみた

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

動機/背景

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

Read More...

ブール代数

  • 2019/05/29 09:00

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

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

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

ブール代数

半順序集合 (B,,,,0,1)(B,\lor,\land,',0,1) が可補分配ならば, (B,,,,0,1)(B,\lor,\land,',0,1) はブール代数である. すなわち, x,y,zBx,y,z\in B に対して, 次のすべての公理を満たした (B,,,,0,1)(B,\lor,\land,',0,1) はブール代数である.

  1. 可換律\htmlId{boolean_algebra1}{\rm 可換律}: xy=yx,xy=yxx\land y=y\land x,x\lor y=y\lor x
  2. 分配律\htmlId{boolean_algebra2}{\rm 分配律}: (xy)z=(xz)(yz),(xy)z=(xz)(yz)(x\lor y)\land z=(x\land z)\lor(y\land z),(x\land y)\lor z=(x\lor z)\land(y\lor z)
  3. 同一律\htmlId{boolean_algebra3}{\rm 同一律}: xL^\forall x\in L に対して x1=x,x0=xx\land 1=x,x\lor 0=x. ここで 11 は最大限, 単位元である. 00 は最小限, 零元である.
  4. 補元律\htmlId{boolean_algebra4}{\rm 補元律}: xL s.t. xL,xx=1,xx=0^\exists x'\in L\ {\rm s.t.}\ ^\forall x\in L, x\lor x'=1, x\land x'=0

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

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

双対の原理

ブール代数で成立する文/式は, そこに現れるすべての ,,0,1\lor ,\land,0,1 をそれぞれ ,,1,0\land,\lor ,1,0 で置き換えても成立する.

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

Read More...

関係 (集合論)

  • 2019/03/15 09:00

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

一般的な関係

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

<a,b>=<c,d>:=a=c,b=dデカルト積=直積=A×B:={<a,b>aA,bB} \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}

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

Read More...