Cプリプロセッサ(with Boost.PP)で簡単な言語処理系を実装しよう
この記事は、C++ (fork) Advent Calendar 2013の10日目の記事です。
はじめに
12月に入って10日目、もう中旬ですね。
連日C++に関するハイレベルな記事が目白押しで消化不良になってきている方々も居らっしゃると思いますので少し趣を変えて息抜きみたいな記事にしようと思います。
実行時処理やコンパイル時処理(TMP, constexpr)は並列処理の実装やコンパイル時言語処理系など他の方々が既に強烈なネタを披露してくれていますし、自分も前回主催した勉強会でそこそこTMPのネタを放出してしまったので、 今回はC++コードをコンパイル前に処理する段階、プリプロセス時の言語とその処理系であるCプリプロセッサに関するネタでいきたいと思います。
TMPに関するネタは前回の概ね前回自分主催の勉強会の資料
にまとまっているので興味のある方はこちらも読んでいただければ幸いです。
概要
※この記事はC++コード内において、Cプリプロセッサマクロの乱用を推奨するものではありません。
Cプリプロセッサは、namespaceやスコープの概念のない邪悪さ、癖のある展開の挙動などなかなか素晴らしいとは言い難い言語ですが、現状この存在なくしてC++での開発は厳しいでしょう。
Cプリプロセッサでのプログラミングは確かに初心者には少々取っ付きづらい面があるのですが、その敷居を下げてくれるものとして、数あるBoostのライブラリ群の中でも唯一Cプリプロセッサで記述されたCプリプロセッサの為のライブラリであるBoost.Preprocessor(以下Boost.PP)があります。
これを用いれば、比較的簡単に人類でもCプリプロセッサでちょっとしたなプログラミングが可能なので今回はそのポテンシャルを体感すべく、Cプリプロセッサ(with Boost.PP)でごくシンプルな言語処理系を実装してみることにしました。
本編
ということで作りました。
ppbf https://github.com/fimbul/ppbf
ppbfはbrainfuckの言語仕様を簡略化した、Cプリプロセッサ上で解釈可能な言語及びその処理系です。
Cプリプロセッサ自体がそれ自体をループ内で実行しない限りチューリング完全でないことからこの言語はbrainfuckと同等の計算能力は有さないのですが、簡単なループや文字の出力ぐらいは出来ます。この記事では実装に関して主に書くので、言語そのものの仕組みや文法等についてはgithubページで解説しているのでそちらを参照して頂けると幸いです。
実装に関して
記述されたソースコードをどうやって解釈しているか
ppbfでは実行されるソースコードはppbf_source.hpp内で定義されたPPBF_SOURCEマクロに半角スペースで命令を区切って
#define PPBF_SOURCE ip iv iv ...
といった風に記述されます。
ipやivという命令自体は単なるマクロで
#define ip (1) #define dp (2) #define iv (3) #define dv (4) #define sh (5) #define la (6) #define gt (7)
のように定義されています。
そこで
ip iv iv dp iv
といった文字列は
(1) (3) (3) (2) (3)
といった風にプリプロセス時に展開されます。
このような(数) (数) ... といった文字列の並びはBoost.PPではBOOST_PP_SEQ_~といった関数マクロでN番目の要素を取り出したり、順番を逆順にしたり、不要な要素を取り除いたり非常に使い勝手の良いコンテナ型として扱う事が出来ます。
状態をどうやって保持しているか
Boost.PPの機能の中でも最強といえるものにSLOTというものがあります。
以下はリファレンスからの引用です
#include <boost/preprocessor/slot/slot.hpp> #define X() 4 #define BOOST_PP_VALUE 1 + 2 + 3 + X() #include BOOST_PP_ASSIGN_SLOT(1) #undef X BOOST_PP_SLOT(1) // expands to 10
このようにBOOST_PP_VALUEに計算可能な式を定義した後、BOOST_PP_ASSIGN_SLOT(数)をincludeすることでBOOST_PP_SLOT(数)に値を割り当てる事が出来ます。1度この割り当てincludeを行うとBOOST_PP_VALUEはundefされます。しかしSLOTの値はBOOST_PP_VALUEがundefされた状態でも保持されるので事実上変数として機能します。勿論マクロなので扱える値には限界もあり万能ではありませんが、十分強力です。Boost.PPでは現在5つまでこのSLOTを利用することが出来ます。
しかもBOOST_PP_VALUEの定義には自分自身を使うことも可能です。
#define BOOST_PP_VALUE BOOST_PP_SLOT(1) + 1 #include BOOST_PP_ASSIGN_SLOT(1) // BOOST_PP_SLOT(1) += 1 のように振る舞う
限られた5つのSLOTを変数として使い、うまくやりくりして処理系の状態を更新していきます。
ppbf処理系では5つのSLOTをそれぞれ
- 何番目のポインタを現在指しているか
- 何番目の命令を現在実行しているか
- 値ポインタの値
- フラグポインタの値
- ラベルポインタの値
として利用しています。
状態をどうやって更新するか
プリプロセッサでは関数マクロの再帰的展開は通常行えないので以下のようなマクロは次のように展開されます
#define A() [B()] #define B() {A()} A()
プリプロセス結果
[{A()}] // 2度目に出現したA()は展開されない
そこで、再帰関数のように状態を変更しながら展開を続ける事は出来ません。
Boost.PPの一部のマクロはこういった事を回避する実装がなされて一見再帰的な展開が可能となっているものもありますが、基本的には出来ません。
またマクロ内でマクロを定義したり#include文を記述してもそれは単なる文字列になってしまいます。
これが文字列になるかどうかは未定義動作ではないかという話を小耳に挟みましたが、自分の知る限り更に展開可能なトークンとして定義したりincludeが実行される処理系を知りませんのでそのような挙動に期待するのはやめて全く別の方法を模索します。
#define a #define c #define b #include __FILE__ a b
プリプロセス結果
#define c #include "ppbf.hpp"
これでは処理の状態の更新が出来ません。
そこでどうするかというと自己includeを使った再帰を用いて状態を更新していきます。
#ifndef INIT #define INIT #include <boost/preprocessor.hpp> #define BOOST_PP_VALUE 2 #include BOOST_PP_ASSIGN_SLOT(1) #endif #if BOOST_PP_SLOT(1) < 100 // BOOST_PP_SLOT(1)が100未満ならば BOOST_PP_SLOT(1) // BOOST_PP_SLOT(1)の値を表示 #define BOOST_PP_VALUE BOOST_PP_SLOT(1) + 2 #include BOOST_PP_ASSIGN_SLOT(1) // BOOST_PP_SLOT(1) += 2 #include __FILE__ // 自己includeによって再帰する #endif
プリプロセス結果としては2~98までの2の倍数が表示されます。
これで状態を更新することが出来ます。
しかし再帰深度には限界があり、超えるとプリプロセスエラーになります。
現在の再帰深度は__INCLUDE_LEVEL__組み込みマクロで知る事が出来るので、例えば
#if 条件 && __INCLUDE_LEVEL__ < 128 // 処理系の再帰深度の限界を超えない適当な値
のようにしておけば再帰深度が深くなりすぎてエラーになることを防げます。
ppbfではppbf_eval.hppで再帰ごとにBOOST_PP_SLOT(2)の値を1進めて実行する命令をBOOST_PP_SEQ_ELEM(BOOST_PP_SLOT(2), PPBF_SOURCE)で取り出してその値で条件分岐して各種SLOTの値を更新するといった方法で処理しています。
そして、現在実行中の命令番号が与えられた命令数(すなわち最後まで)に達するか、再帰深度が128を超えないところで抜けます。
1つのppbf_eval.hppの再帰では最大で127回までしか命令を実行出来ないのでppbf.hppでは以下のように何度もincludeすることで実行可能な命令数の上限を増やしています…。
#// Evaluation capacity : 32 * 127 operators #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp" #include "ppbf_eval.hpp"
出力関数でどうやって値をASCIIコードの文字に変換するか
トークンは結合した後更に展開することが出来ます、例としては
#define CAT(x, y) x##y #define TEST test CAT(TE, ST)
プリプロセス結果
test // トークンの結合でTE##STがTESTになった後、さらに展開される
これを利用してあらかじめppbf_ascii.hppにASCIIコード表マクロを定義しておき
#define PPBF_ASCII_33 ! #define PPBF_ASCII_34 " #define PPBF_ASCII_35 # #define PPBF_ASCII_36 $ #define PPBF_ASCII_37 % #define PPBF_ASCII_38 & #define PPBF_ASCII_40 ( #define PPBF_ASCII_41 ) #define PPBF_ASCII_42 * #define PPBF_ASCII_43 + #define PPBF_ASCII_44 , #define PPBF_ASCII_45 - #define PPBF_ASCII_46 . #define PPBF_ASCII_47 / ...
これにSLOTの値とPPBF_ASCII_を結合したトークンの展開結果を表示しています。 実際のsh命令の定義です
BOOST_PP_CAT(PPBF_ASCII_, BOOST_PP_SLOT(BOOST_PP_SLOT(1)))
BOOST_PP_CATは2つの引数のトークンを結合します。 BOOST_PP_SLOTは入れ子にしても値が同じでなければ展開してくれるので、結果としてこのトークンはPPBF_ASCII_と現在指しているポインタの値を結合したトークンになり、それが更に展開されてアスキーコードの文字になります。
処理の終了
ppbf_eval.hppの最初に
#if PPBF_SOURCE_LENGTH != BOOST_PP_SLOT(2) && __INCLUDE_LEVEL__ < 128
が書かれており、これを32回includeしているので
PPBF_SOURCE_LENGTH != BOOST_PP_SLOT(2) // 実行中の命令が最後に達する
或いは32 * 127命令実行した時点で処理は終了します。
プログラムの実行
line行や余計な警告は表示しないようにしてプリプロセスのみを実行します。
clang -E -P -w ppbf.hpp | tr -d '\n' または gcc -E -P -w ppbf.hpp | tr -d '\n'
まずプリプロセスを行って、プリプロセス結果に含まれてしまう余計な改行をtr -d '\n'で除去してやります。
Hello,world!してみました。
Cプリプロセッサ自体がそれのみだとチューリング完全ではないので、この言語もチューリング完全ではありませんがその制約条件の中でループを行ったり、Hello,world!を表示する程度の事は出来る言語処理系を実装出来ました。
Cプリプロセッサのポテンシャルもなかなかですね。
おわりに
今回の言語処理系自体はネタなので、実用性は皆無だと思いますが、プリプロセッサメタプログラミングといった技法はあまり表に登場しないものの、実際Boost.MPLを始め各種ライブラリの中で結構本当に役に立つ形で多用されていたりします。後方互換性の問題の為や代用出来る新しい仕組みが登場していないことから今後も暫く使われるでしょうし、このような知識を持っておくとBoostのライブラリのソースコードを読む際に役立つかもしれません。
なんにせよ、現状ではプリプロセス時、コンパイル時、実行時のいずれにも熟達しておくに越したことは無いと思います。
明日からまたC++ (fork) Advent Calendar 2013ではC++に関するハイレベルな記事が続いていくと思いますが、今日の記事が趣の違う気分転換的ポジションの存在になれていれば幸いです。おしまい。
