2010-03-14

先日、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

かそくそうち

The AATT Programming Language