Boost.勉強会#3
Boost.勉強会#3でBoost.Buildについて発表しました。
発表資料
http://www12.ocn.ne.jp/~dante98/BoostBuild-pre.pptx
サンプルコード
http://www12.ocn.ne.jp/~dante98/zip/bbv2.zip
名前を言ってはいけないあのプログラミング言語のインタプリタ
http://www12.ocn.ne.jp/~dante98/zip/bf.zip
初PowerPoint/プレゼンテーション/大阪で緊張しました。
蛇足(蛇足大好きなもので、、、)ばかり話して時間配分も失敗してしまい、Tipsの部分は喋れませんでした。
次やるならラウンドテーブルとかの方がいいかなぁ。
Dante98 for Windowsクラッシュ回避パッチ
ワイド液晶になってからDante98 for Windowsが動いてなかったのですが、ようやく重い腰を上げて調査しました。
640x480x256色のDirectDrawサーフェイスのピッチが640以外の環境で動いていませんでした。
Ver. 2.0.1.10用のパッチです。
0x00016AC3: D4 -> D0
0x00016AC6: D0 -> D4
普通にビルドしたら実行ファイルのサイズが大きくなったので、そのままリリースは怖くてとりあえずパッチだけです。
(12:50 追記)
http://www12.ocn.ne.jp/~dante98/#20100925
に修正プログラムを置きました。
The AATT Programming Language
先日、kinabaさんと朗読劇を観に行ったときに話していたネタ言語を実装してみました。
元ネタ：「kinaba さんが Cryolite を洗脳してパターンマッチ厨に仕立て上げるリスト」
http://togetter.com/li/6990
確かにパターンマッチがあれば木の操作を簡潔に書けるのですが、
コメントにAAで木を書いておかないと何をやっているのかよく分からないので、
AAがそのままプログラムになればいいんではないかという発想です。
とりあえず、「ASCII Art Tree Transform」を略してAATTと呼ぶことにします。
「Tree」と言っても今のところ「赤黒木」専用です。
AATTのソースコードは次のようになります。
G P / \ / \ p U -> n g / \ / \ n 3 3 U ^
大文字が黒ノード、小文字が赤ノード、数字は任意のノード(空ノード含む)で、それぞれのノードは「/」か「\」で繋ぎます。
変形前と変形後の木は「->」のある列で区切られます。
「赤黒木」の挿入操作では追加したノードから探索する必要があるため、「^」で探索開始ノードを指定できるようにしています。
「^」がない場合は(部分木の)ルートから探索します。
このソースコードをコンパイルすると、以下のようなC++コードが出力されます。
inline tree_node* balance(tree_node* root, tree_node* node) { // G P // / \ / \ // U p -> g n // / \ / \ // 3 n U 3 // ^ { tree_node* pN = node; if ((pN != 0) && (pN->color == RED)) { tree_node* pP = pN->parent; if ((pP != 0) && (pP->right == pN) && (pP->color == RED)) { tree_node* p3 = pP->left; tree_node* pG = pP->parent; if ((pG != 0) && (pG->right == pP) && (pG->color == BLACK)) { tree_node* pU = pG->left; if ((pU != 0) && (pU->color == BLACK)) { tree_node* parent = pG->parent; pP->parent = parent; pP->color = BLACK; pP->left = pG; pG->color = RED; pG->parent = pP; pG->right = p3; if (p3 != 0) { p3->parent = pG; } if (parent != 0) { if (parent->left == pG) parent->left = pP; else parent->right = pP; } else root = pP; return root; } } } } } return root; }
関数名はソースファイル名から自動生成されます。
元のAAはコメントとして残ります。
引数rootは木のルート、nodeは探索開始ノードで、戻り値は変形後のルートになります。空行区切りでパターンを書いておけば、上から順にマッチングを行うコードが出力されます。
「tree_node」とか「BLACK」とか決め打ちなのは手抜きです。
再帰も書けます。
G g / \ /^\ p u -> P U / / n n ^
変形後の木のノードに「^」でマークすると、その位置をnodeとして再び変換を行います。
また、ルートかどうかの判定機能もあります。
* n -> N ^
ノードの上に「*」を付けると、そのノードが(部分木でなく全体の)ルートの場合のみマッチするようになります。
ちなみに、
とソースが読みやすくなります。
一応、ソースコードを置いておきます。
http://www12.ocn.ne.jp/~dante98/zip/aattc.zip (CR/LF改行)
http://www12.ocn.ne.jp/~dante98/zip/aattc.tar.bz2 (LF改行)
(23:30 追記)
#以降行末まではコメントです
バックスラッシュが出ないのでシンタックスハイライトしたものをこちらに貼りました
http://www12.ocn.ne.jp/~dante98/balance.aatt.html
xor_listの実装
http://d.hatena.ne.jp/y-hamigaki/20100118
の解説です。
やたら長くなったので続きを読む記法。
xor_list
暇つぶしにSTL風にXOR連結リストを書いてみました。
<hamigaki/xor_list.hpp>
ドキュメント
wikipedia:XOR連結リスト
要するに、某巨大掲示板で昔話題になった「マジックリスト」のことです。
そのときアップされていた某氏のコードを参考にしました。
自分も途中まで書いていたので、それも参考にしつつ、「XOR連結リスト」の方が一般的みたいなので、xor_listと改名しています。
実用性はあまりないと思うのですが、割とまじめに書いています。
以下、特徴。
- Boostなしで1ファイルだけで利用可能(一部Boostの劣化コピー品含む)
- 等価でないアロケータ対応
- sort()も実装(マージソート)
- VC++9.0(32/64bit)、g++4.4.0で動作確認済み
- 一応ドキュメントも書いた
コンテナ実装の参考になればと。
気が向いたら解説書きます。
wave.state
まだBoost.Waveで引っ張ります。
Boost.Waveのインタラクティブモードには状態の保存/復帰機能があります。
この機能はcpp.cppのBOOST_WAVE_SERIALIZATIONの値を1に変えてビルドすることで利用できるようになります。
ただし、コンパイルエラーとロード処理のバグがあったので少し手を加えました。
Index: cpplexer/cpp_lex_token.hpp =================================================================== --- cpplexer/cpp_lex_token.hpp (リビジョン 58616) +++ cpplexer/cpp_lex_token.hpp (作業コピー) @@ -280,6 +280,8 @@ template<typename Archive> void serialize(Archive &ar, const unsigned int version) { + if (!data) + data = new data_type(0); data->serialize(ar, version); } #endif Index: util/cpp_include_paths.hpp =================================================================== --- util/cpp_include_paths.hpp (リビジョン 58616) +++ util/cpp_include_paths.hpp (作業コピー) @@ -482,7 +482,7 @@ >::type map_type; boost::serialization::stl::load_collection< Archive, map_type, - boost::serialization::stl::archive_input_unique<Archive, map_type>, + boost::serialization::stl::archive_input_map<Archive, map_type>, boost::serialization::stl::no_reserve_imp<map_type> >(ar, t); }
状態を保存しておくファイルは「-s」オプションで指定します。
ファイル名が「-」なら、「wave.state」になります。
C:\Boost>wave.exe -s -
Wave: A Standard conformant C++ preprocessor based on the Boost.Wave library
Version: 2.0.3.2941 [Win32/Microsoft Visual C++ version 9.0] (20090602)
>>> #define HOGE 123
>>> ^ZC:\Boost>wave.exe -s -
Wave: A Standard conformant C++ preprocessor based on the Boost.Wave library
Version: 2.0.3.2941 [Win32/Microsoft Visual C++ version 9.0] (20090602)
>>> HOGE
123
>>> ^ZC:\Boost>
マクロの名前で分かるとおり、状態の保存にはBoost.Serializationが利用されています。
元ソースではアーカイブにXMLを利用していて遅いので、
BOOST_WAVE_BINARY_SERIALIZATIONを1に、BOOST_WAVE_XML_SERIALIZATIONを0に変えて、
バイナリフォーマットを使うようにした方がよいです。
また、Boost.Waveで使っている文字列がstringではないため、バイナリフォーマットの方が中を覗きやすかったりもします。
よく使うヘッダをインクルードしたwave.stateを用意しておくと便利かもしれません。
wave.cfg
今日もwaveをいじってました。
waveをそのまま起動すると、インクルードディレクトリや事前定義マクロが設定されていないので、
コマンドライン引数で指定する必要があります。
ただ毎回設定すると面倒なので、設定ファイルを使った方がよいです。
既定では、入力ファイルのあるディレクトリから上へ辿って最初に見つかったwave.cfgが使われます。
書式はコマンドライン引数を１行に１つずつ並べて書くだけです。いわゆるレスポンスファイルですね。
VC++9.0風ならこんな感じです。
-D_CPPUNWIND=1 -D_M_IX86=600 -D_WIN32=1 -D_CPPRTTI=1 -D_MSC_EXTENSIONS=1 -D_MSC_VER=1500 -D_MSC_FULL_VER=150030729 -D_MT=1 -D_NATIVE_WCHAR_T_DEFINED=1 -D__BOOL_DEFINED=1 -D_INTEGRAL_MAX_BITS=64 -SC:\Boost\src\svn -Sc:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\ATLMFC\INCLUDE -Sc:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\INCLUDE -SC:\Program Files\\Microsoft SDKs\Windows\v6.0A\include -S.
ただし、インタラクティブモードの場合には二つ制限があります。
- 入力ファイルがないので設定ファイルを明示的に指定する必要がある
- マクロ定義がクリアされる
二つ目は次のパッチで改善できます。
Index: cpp.cpp =================================================================== --- cpp.cpp (リビジョン 57536) +++ cpp.cpp (作業コピー) @@ -996,7 +996,7 @@ if (is_interactive) { // if interactive we don't warn for missing endif's etc. ctx.set_language( - boost::wave::enable_single_line(ctx.get_language())); + boost::wave::enable_single_line(ctx.get_language()), false); } // analyze the input file
ちゃんと調べてないので、何か挙動が怪しくなるかもしれません。
