RUST でファイル入力処理

迷路のレイアウトをコードにベタ書きで埋め込むのは骨が折れるので、下のようなテキストで作成した迷路を読み込めるようにした。

だいぶ長くなってきたので、アルゴリズム以外を別ファイルに移した上で、ファイルから迷路を構築する処理を追加。
メインからはモジュールとして読み込んで利用する。
ファイル入力自体は比較的簡単だったが、エラー処理にだいぶ嵌められた。
エラー処理の仕様をきちんと理解しないままサンプルを見よう見まねでコピペしても全然コンパイルできなかった。
その分ちゃんと理解すれば柔軟なエラー処理ができるんだが、正直かなりとっかかりにくいと思う。

RUST 勉強中

環境構築

インストール

Ubuntu16.04 だと apt-get から入手できるようになった。

エディタ設定

Emacs 使いなので、melpa から lang-rust を導入

お勉強

何は無くとも RUST のドキュメントを熟読。

どうやらメモリ参照の透過性の高いプログラミング言語らしい。
なので、マルチスレッドとかに向いているそうだ。

一応オブジェクトっぽいこともできそうだが、オブジェクト指向言語ではないようだ。

実践

試しに単純な右手の法則で迷路を解くプログラムを書いてみた。

どうしても関数の引数が borrow ばっかりになってしまうが、これでいいんだろうか。

オブジェクト指向のようにポリモーフィズムばりばりで抽象化すると言うよりも、テンプレートで抽象化するが、テンプレートだとなんでもありになってしまうので、Trait で期待するテンプレートを指定するという感じか。
なんとなく、Cのマクロでこうできれば便利なんだけどなー、ってもどかしかったのができるようになっている感じで使っていて気持ちいい。

C++ で C# の delegate っぽいものも作ってみた

こないだ event 風のものを作ってみたけど、もう一ひねりしたら delegate っぽいものも作れた。

template<typename T>
class Delegate;

template<typename R, typename... A>
class Delegate<R(A...)> {
private:
    std::function<R(A...)> mFunc;
public:
    Delegate(std::function<R(A...)> func) : mFunc(func) {}
    template<typename C, typename T>
    Delegate(C* pObj, T func) {
        mFunc = [=](A... args) { std::mem_fn(func)(pObj, args...); };
    }
public:
    void operator()(A... args) {
        mFunc(std::forward<A>(args)...); // 修正
    }
};

ｅｖｅｎｔ と組み合わせるとこんな感じで使える。

class EventManager {
public:
    typedef Delegate<void(const std::string&)> TestEventHndlr;
    Event<TestEventHndlr> TestEvent;
    void InvokeTestEvent() {
        TestEvent("This is TestEvent. > ");
    }
};

class EventHandler {
public:
    void Hndlr(const std::string& msg) {
        std::cout << msg << "I'm a member function." << std::endl;
    }
};

void print_msg(const std::string& msg) {
    std::cout << msg << "I'm a static function." << std::endl;
}

int main()
{
    EventManager manager;
    EventHandler hndlr;
    manager.TestEvent += EventManager::TestEventHndlr([](const std::string& msg) {
        std::cout << msg << "I'm a lambda function." << std::endl;
    });
    manager.TestEvent += EventManager::TestEventHndlr(print_msg);
    manager.TestEvent += EventManager::TestEventHndlr(&hndlr, &EventHandler::Hndlr);
    manager.InvokeTestEvent();
    return 0;
}

※追記
unique_ptr を使おうとしたらハマったので Delegate を一部修正。
Event の方は複数のハンドラを登録できるようにしているのでもともと unique_ptr は適さない。
どうしても使いたければハンドラを一つしか登録できないイベントクラスを別途作る必要があるが、それよりはイベントハンドラ側にメモリ管理をさせないようにデータ構造を見直した方が健全かなぁ。。。

C++0x のラムダ式と可変長テンプレートで C# っぽいイベント処理

世の中便利になったものね～。
これでコールバックを多用した非同期処理がだいぶ書きやすくなりそう。

どうしてもメンバ関数は一旦ラムダ式で包んであげる必要があるので、デリゲートの仕組みも作れると完璧なんだが・・・

#include <iostream>
#include <list>
#include <functional>
#include <string>

template<typename T>
class Event {
private:
    std::list<T> mHndlrs;
public:
    void operator+=(T hndlr) {
        mHndlrs.push_back(hndlr);
    }
    template<typename... A>
    void operator()(A... args) {
        for (auto it = mHndlrs.begin(); it != mHndlrs.end(); it++) {
            (*it)(args...);
        }
    }
};

class EventManager {
public:
    Event<std::function<void(const std::string&)> > TestEvent;
    void InvokeTestEvent() {
        TestEvent("This is TestEvent. > ");
    }
};

class EventHandler {
public:
    void Hndlr(const std::string& msg) {
       std::cout << msg << "I'm a member function." << std::endl;
    }
};

void print_msg(const std::string& msg) {
    std::cout << msg << "I'm a static function." << std::endl;
}

int main()
{
    EventManager manager;
    EventHandler hndlr;
    manager.TestEvent += [](const std::string& msg) {
        std::cout << msg << "I'm a lambda function." << std::endl;
    };
    manager.TestEvent += print_msg;
    manager.TestEvent += [&](const std::string& msg) {
       hndlr.Hndlr(msg);
    };
    manager.InvokeTestEvent();
    return 0;
}

JavaScript で Sudoku を解いてみる (3)

前回までで、問題と条件が記述できたので、後は例によって解けば良い。

今回はモナドを利用したおかげで条件の記述がそのまま条件をチェックするコードになるので、ソルバは非常にシンプルに書ける。

        function solve(question, conditions, iter) {
            var result;
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) return;
            var answer = [];
            question[iter].selectEach(function() {
                result = conditions();
                if(result === undefined)
                    answer = answer.concat(solve(question, conditions, iter+1));
                else if(result === true) {
                    answer.push(question.map(function(tile) { return tile.get(); }));
                }
            });
            return answer;
        }

        var Question = Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }, []);

        var Answer = solve(Question, Condition);

ここまでシンプルに書けると、もはやソルバは要らないんじゃないかと思えてきて、問題に吸収させて、問題生成時に問題に対応するソルバを生成するようにもしてみた。

        function Question(items) {
            this.Solve = items.reduce(function(prev, item) {
                return function(condition) {
                    var answer = [];
                    item.selectEach(function() {
                        result = condition();
                        if(result === undefined)
                            answer = answer.concat(prev(condition));
                        else if(result === true) {
                            answer.push(items.map(function(tile) { return tile.get(); }));
                        }
                    });
                    return answer;
                }
            }, function() { return []; });
        }

        var Answer = (new Question(Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }))).Solve(Condition);

実際に解いてみると、簡単な問題なら一瞬で解けるが、難易度が上がると試行回数が跳ね上がってむちゃくちゃ時間がかかるようになる。
この辺はスクリプトの限界なのか、それとも工夫すればもっと速くなるのか。。。

JavaScript で Sudoku を解いてみる (2)

前回の続きで、塗り分けの時にモナド的に書きたいなと言っていたところを、無い知恵を絞ってモナドもどきを作ってみた。

        var Result = {
            False: {
                bind: function() {
                    return this;
                },
                get: function() {
                    return false;
                }
            },
            True: {
                bind: function(f) {
                    return f();
                },
                get: function() {
                    return true;
                }
            },
            Undefined: {
                bind: function(f) {
                    var result = f();
                    if(result.get() === false) {
                        return result;
                    }
                    return Result.Undefined;
                },
                get: function() {
                    return undefined;
                }
            }
        }

これを使うと、「与えられた要素が全て互いに異なる」という条件はこう書ける。
モナドを使いつつも、あまり関数型っぽくない書き方だが、実行効率を踏まえつつハイブリッドなやり方と言うことで

        function AllNotEqual() {
            return allNotEqual(arguments, arguments.length-2);
        }
        function allNotEqual(items, iter) {
            var result = (function(j) {
                var callee = arguments.callee;
                if(j <= iter + 1) return NotEqual(items[iter], items[j]);
                return NotEqual(items[iter], items[j]).bind(function() { return callee(j-1); });
            })(items.length - 1);
            if(iter <= 0) {
                return result;
            }
            return result.bind(function() { return allNotEqual(items, iter-1); });
        }
        function NotEqual(x, y) {
            var tmp_x = x.get(), tmp_y = y.get();
            if(tmp_x === undefined || tmp_y === undefined)
                return Result.Undefined;
            if(tmp_x != tmp_y)
                return Result.True;
            return Result.False;
        }

Sudoku の条件である、「各行、各列、各3x3のブロックで同じ数字を使わない」は、関数型言語の勉強の時に作った do 記法もどきを利用してこう書ける。
ちとながいが、よく見れば単にルールをべた書きしただけの記述。

        var MonaDo = function(fs) {
            var monado = function(funcs) {
                if(funcs.length > 1) {
                    var inner = monado(funcs.slice(1));
                    return function(a) {
                        return funcs[0](a).bind(inner);
                    }
                }
                return funcs[0];
            }
            return monado(fs)();
        }

        function RowNotEqual(cells, row) {
            return AllNotEqual.apply(this, cells[row]);
        }
        function ColNotEqual(cells, col) {
            return AllNotEqual.apply(this, cells.map(function(row) {
                return row[col];
            }));
        }
        function BlkNotEqual(cells, row, col) {
            return AllNotEqual(
                cells[row][col],  cells[row][col+1],  cells[row][col+2],
                cells[row+1][col],cells[row+1][col+1],cells[row+1][col+2],
                cells[row+2][col],cells[row+2][col+1],cells[row+2][col+2]);
        }
        var Condition = function() {
            return MonaDo([
                function() {return RowNotEqual(Cells, 0); },
                function() {return RowNotEqual(Cells, 1); },
                function() {return RowNotEqual(Cells, 2); },
                function() {return RowNotEqual(Cells, 3); },
                function() {return RowNotEqual(Cells, 4); },
                function() {return RowNotEqual(Cells, 5); },
                function() {return RowNotEqual(Cells, 6); },
                function() {return RowNotEqual(Cells, 7); },
                function() {return RowNotEqual(Cells, 8); },
                function() {return ColNotEqual(Cells, 0); },
                function() {return ColNotEqual(Cells, 1); },
                function() {return ColNotEqual(Cells, 2); },
                function() {return ColNotEqual(Cells, 3); },
                function() {return ColNotEqual(Cells, 4); },
                function() {return ColNotEqual(Cells, 5); },
                function() {return ColNotEqual(Cells, 6); },
                function() {return ColNotEqual(Cells, 7); },
                function() {return ColNotEqual(Cells, 8); },
                function() {return BlkNotEqual(Cells, 0, 0); },
                function() {return BlkNotEqual(Cells, 0, 3); },
                function() {return BlkNotEqual(Cells, 0, 6); },
                function() {return BlkNotEqual(Cells, 3, 0); },
                function() {return BlkNotEqual(Cells, 3, 3); },
                function() {return BlkNotEqual(Cells, 3, 6); },
                function() {return BlkNotEqual(Cells, 6, 0); },
                function() {return BlkNotEqual(Cells, 6, 3); },
                function() {return BlkNotEqual(Cells, 6, 6); }
            ]).get()
        };

JavaScript で Sudoku を解いてみる (1)

こないだ塗り分け問題を解く JavaScript を書いてみたが、同じ原理で Sudoku も解けるんじゃないかと思ってコードを改良しつつやってみた。

Sudoku の場合は初期状態で値が決まっているセルと決まっていないセルがあるので、これを表現するために、Obvious と Ambiguous という二つのクラスを作成した。

        function Ambiguous(candidates) {
            this.candidates = candidates;
            this.selected = undefined;
        }
        Ambiguous.prototype = {
            get: function() {
                return this.selected;
            },
            selectEach: function(callback) {
                this.candidates.forEach(function(item) {
                    this.selected = item;
                    callback();
                }.bind(this));
                this.selected = undefined;
            },
        }
        function Obvious(value) {
            this.value = value;
        }
        Obvious.prototype = {
            get: function() {
                return this.value;
            },
            selectEach: function(callback) {
                callback();
            }
        }

長くなるのでヘルパーを使いつつ、どっかから探してきた Sudoku の問題を表現するとこうなる。

        var Nine = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        function createRow(args) {
            return args.map(function(item) {
                if(Array.isArray(item)) return new Ambiguous(item);
                return new Obvious(item);
            });
        }
        var Cells = [
            createRow([Nine, Nine,    8, Nine,    9, Nine, Nine, Nine, Nine]),
            createRow([   9, Nine, Nine, Nine,    3, Nine, Nine, Nine,    1]),
            createRow([   6,    2, Nine, Nine,    4,    7, Nine,    8, Nine]),
            createRow([Nine, Nine,    7, Nine, Nine, Nine,    1,    9, Nine]),
            createRow([   1,    3, Nine,    4,    7, Nine,    2,    5,    8]),
            createRow([   5, Nine, Nine,    8,    2, Nine,    3,    6, Nine]),
            createRow([   3,    6,    1,    7, Nine,    4,    8,    2, Nine]),
            createRow([Nine,    5,    2,    9,    1, Nine,    4,    7,    6]),
            createRow([Nine,    9,    4,    6, Nine, Nine,    5, Nine,    3])
        ];

インデントは気にしない

Javascript で塗り分け問題を解いてみる (4)

前回で総当たり方式についてコードを一般化出来たところで、今度はこれに枝刈りを導入して動作の効率化を図る。

枝刈りというのは、要は全てのタイルの色を設定した後で全ての条件に合致するかを判断するのではなく、1枚ずつタイルの色を設定しながら、現時点で条件を満たさないことが判明したらその先の試行をやめて違う組み合わせを試すというものになる。

そのためには、それぞれの条件に対して判断に必要なタイルを明記する必要がある。

        var Colors = ['red', 'blue', 'green', 'yellow'];
        var tile1 = { candidates: Colors, selected: undefined };
        var tile2 = { candidates: Colors, selected: undefined };
        var tile3 = { candidates: Colors, selected: undefined };
        var tile4 = { candidates: Colors, selected: undefined };
        var tile5 = { candidates: Colors, selected: undefined };

        var Conditions = [
            { require: [tile1, tile2], func: function() { return tile1.selected != tile2.selected; } },
            { require: [tile1, tile3], func: function() { return tile1.selected != tile3.selected; } },
            { require: [tile1, tile4], func: function() { return tile1.selected != tile4.selected; } },
            { require: [tile1, tile5], func: function() { return tile1.selected != tile5.selected; } },
            { require: [tile2, tile3], func: function() { return tile2.selected != tile3.selected; } },
            { require: [tile3, tile5], func: function() { return tile3.selected != tile5.selected; } },
            { require: [tile4, tile5], func: function() { return tile4.selected != tile5.selected; } },
            { require: [tile4, tile2], func: function() { return tile4.selected != tile2.selected; } }
        ];

        var Question = [tile1, tile2, tile3, tile4, tile5];

各条件を判定するときには、require で示されたタイルの色が設定されているかをチェックして、設定されていない場合は undefined を返すようにする。

        function checkOne(question, cond) {
            var i;
            for(i = 0; i < cond.require.length; i++) {
                if(cond.require[i].selected === undefined) {
                    return undefined;
                }
            }
            return cond.func();
        }

あとは、
複数の条件のうち、一つでも条件を満たさない場合はその先の試行は行わない。
全ての条件を満たせばそれが回答の一つになる。
それ以外(undefinedが混じる場合)は次のタイルの色を設定してもう一度条件を確認する。
というのを行っていけばよい。

        function solve(question, conditions, iter) {
            var result;
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) return;
            var answer = [];
            question[iter].candidates.forEach(function(item) {
                question[iter].selected = item;
                result = check(question, conditions);
                if(result === undefined)
                    answer = answer.concat(solve(question, conditions, iter+1));
                else if(result === true) {
                    answer.push(question.map(function(tile) { return tile.selected; }));
                }
            });
            question[iter].selected = undefined;
            return answer;
        }

        function check(question, conditions) {
            var i,
                tmp,
                result = true;
            for(i = 0; i < conditions.length; i++) {
                tmp = checkOne(question, conditions[i]);
                if(tmp === false) return false;
                else if(tmp === undefined) result = undefined;
            }
            return result;
        }

こうすれば、メンテナンス性を維持しつつも、枝刈りにより高速に処理が出来る。

check や checkOne の戻り値をチェックして処理内容を変えるところなんかは、関数型言語で勉強したモナド的なやり方を導入するともう少しスマートに書けそうな気がするのだが、一からモナドを設計するのは自分の脳みそじゃ無理そうだ。

塗り分け問題を JavaScript で書いてみた結論としては、

　　prologで良いじゃん

の一言に尽きる。

というか、prolog 向きの問題だと言うことはハナからわかっていたが、JavaScript で書いたらもう少しオブジェクト指向的なアプローチが出来るかなと思って色々試行錯誤してみたのたが、結局は一般化しようとしたら prolog っぽい書き方をするのが一番良いよねということになってしまった。
強いて言えば、require と selected をもう少しスマートに表現できるようにしたかったなぁ。

まあ、こんなことは先人たちがさんざん試してるので今更なんだろうが、勉強には良いよね。

Javascript で塗り分け問題を解いてみる (3)

前回は効率性を重視するあまりメンテナンス性がおろそかになってしまった。
メンテナンス性を良くするために、解き方はもとの総当たりに戻すとして、一旦命題を整理してみる。

今回の命題を言葉で書くと
「タイル1～5までの5枚のタイルがある」
「それぞれのタイルには赤、青、緑、黄のどれかの色が塗られる」
「"条件"に合致するタイルの色の組み合わせは何か」
のということになる。

これをそのままコードで書くとこのように書ける。

        var Colors = ['red', 'blue', 'green', 'yellow'];

        var tile1 = { candidates: Colors, selected: undefined };
        var tile2 = { candidates: Colors, selected: undefined };
        var tile3 = { candidates: Colors, selected: undefined };
        var tile4 = { candidates: Colors, selected: undefined };
        var tile5 = { candidates: Colors, selected: undefined };

        var Conditions = [
            function() { return tile1.selected != tile2.selected; },
            function() { return tile1.selected != tile3.selected; },
            function() { return tile1.selected != tile4.selected; },
            function() { return tile1.selected != tile5.selected; },
            function() { return tile2.selected != tile3.selected; },
            function() { return tile3.selected != tile5.selected; },
            function() { return tile4.selected != tile5.selected; },
            function() { return tile4.selected != tile2.selected; }
        ];

        var Question = [tile1, tile2, tile3, tile4, tile5];

命題をコードで書けるのなら、それをそのまま解けば良い。

        function solve(question, conditions, iter) {
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) {
                if(conditions.every(function(condition) { return condition(); })) {
                    return [question.map(function(tile) { return tile.selected; })];
                }
                return [];
            }
            var answer = [];
            question[iter].candidates.forEach(function(item) {
                question[iter].selected = item;
                answer = answer.concat(solve(question, conditions, iter+1));
            });
            return answer;
        }

        var Answer = solve(Question, Conditions);

さらっと無茶なことをやっているようにも見えるが、実際は question で与えられた tile1 ～ tile5 に対して再起を使って candidate の全ての組み合わせを総当たりで試しているだけ。

こうしてしまえば、タイルの数が増えようが、条件が変わろうが容易に対応できる。

Javascript で塗り分け問題を解いてみる (2)

前回の続き。

さすがに総当たりだと単純すぎるので、いわゆる枝刈りして余計な試行を削っていく。

var colors = ['red', 'blue', 'green', 'yellow'];

colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        if(tile1 != tile2) {
            colors.forEach(function(tile3) {
                if(tile1 != tile3 && tile2 != tile3) {
                    colors.forEach(function(tile4) {
                        if(tile1 != tile4 && tile3 != tile4) {
                            colors.forEach(function(tile5) {
                                if(tile1 != tile5 && tile4 != tile5 && tile2 != tile5) {
                                    document.write(tile1+', '
                                        +tile2+', '
                                        +tile3+', '
                                        +tile4+', '
                                        +tile5+'<br>');
                                }
                            });
                        }
                    });
                }
            });
        }
    });
});

たしかにこれで速くはなるのだが、いかんせんメンテナンス性がすこぶる悪い。
タイルを一枚増やしたり、条件を変更しようとするとあっちゃこっちゃ変えなくちゃならない。

Javascript で塗り分け問題を解いてみる (1)

以前なんかで見かけて、暇があったら勉強がてら JavaScript で書いてみようと思っていたプログラム。
いわゆる塗り分け問題で、細かいところは覚えていないが、とりあえず適当に下のような5枚のタイルを同じ色が隣接しないように赤青黄緑の4色で塗り分ける問題を解いてみる。

まずは何も考えずに愚直に書くとこうなる

var colors = ['red', 'blue', 'green', 'yellow'];

var i, j, k, l, m;
var tile1, tile2, tile3, tile4, tile5;
for(i = 0; i < colors.length; i++) {
    tile1 = colors[i];
    for(j = 0; j < colors.length; j++) {
        tile2 = colors[j];
        for(k = 0; k < colors.length; k++) {
            tile3 = colors[k];
            for(l = 0; l < colors.length; l++) {
                tile4 = colors[l];
                for(m = 0; m < colors.length; m++) {
                    tile5 = colors[m];
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                }
            }
        }
    }
}

これでも解けることは解けるが、タイル数(N)が増えると試行回数が4(色数)のN乗で増えていくので、こんなんを大学の専攻のレポートで提出したら確実に赤点食らうだろう。

蛇足だが、forEachを使うと若干シンプルに書ける。

var colors = ['red', 'blue', 'green', 'yellow'];
var begin = Date.now();
colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        colors.forEach(function(tile3) {
            colors.forEach(function(tile4) {
                colors.forEach(function(tile5) {
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                });
            });
        });
    });
});

もっとも、シンプルに書けるだけで中身は変わらないので、まともにしようと思ったら工夫が必要になる。

Mongoose の autoreconnect が動かない

やったことのメモ

Mongoose には自動再接続の機能があるらしいのだが思ったように動かない。

とりあえず connection の connected, disconnected, reconnected イベントを拾ってログを出すようにしてみたら、１回目の再接続時はきちんと disconnected → connected のイベントが出ていたが、2回目以降は disconnected は発生せずに reconnected だけ発生していた。

さらにややこしいのが一度でもデータベースに save をするとどのイベントも発生しなくなる（厳密には拾い方が変わるのかもしれんが）。readyState も変わらないのでどうしようも無い。

こちらのイベント処理が悪いのかと思って、autoreconnect を信じて全てのイベント処理を外してみても駄目。

バグなのか仕様なのか自分の使い方が悪いのかはわからんが、色々試行錯誤した結果以下のように save のコールバックで失敗した書き込みをキューイングして再接続させるようにしたらうまく動いた。

mongoose.connect(dbURI);

// 送信失敗したデータを溜めるためのキュー
var instQueue = [];
var connecting = false;

function saveInst(inst) {
  inst.save( function(err) {
    if(err) {
      console.log('save failed');
      instQueue.push(inst);
      if(connecting) {
        connecting = true;
        mongoose.connect(dbURI, function(err) {
          connecting = false;
          // 接続に成功したら溜まっているキューを save
          if(!err && instQueue.length > 0) {
            saveInst(instQueue.shift());
          }
        });
      }
    } else {
      console.log('saved');
      // キューが溜まっていれば残りも save
      if(instQueue.length > 0) {
        saveInst(instQueue.shift());
      }
    }
}

connect 中にもう一回 connect するとエラーになるので connecting フラグを使って多重コネクトを行わないように管理していたが、自前でフラグを作らずに readyState を見ても良かったかもしれない。

今回は定期的に吐かれるログを保存するためのスクリプトだったので接続に失敗してもキューに突っ込んでおいて次回リトライできるが、そうでない場合は setTimeout 等を使って手動で connection を何度もリトライする必要が出てくる。

でもそれホントは autoreconnect の仕組みがやってくれるはずなんだよね・・・

struct 五段活用

久々に C 書くと毎度ごっちゃになるので整理しておく。

基礎知識

変数の宣言

型　変数名

typedef の宣言

typedef 型 別名

構造体の定義

struct 構造体名 定義

1. 標準型

struct mystruct {
  int foo;
};
struct mystruct bar;

おそらく一番オーソドックスな使い方。
構造体だからと言って盲目的に mystruct_t と _t を付ける人もいるが、"struct mystruct" 全体が型名なので、個人的にはいちいち _t を付けなくても構造体であることは明示されていると思う。

2. typedef 型

typedef struct {
  int foo;
} mystruct_t;
mystruct_t bar;

いちいちstructを付けるのが面倒くさいときによくやるやり方。
無名の構造体を定義して、それに対して typedef で新しい名前を与えている。
この場合は型名に struct が付かないので、_t を付けるべき。

3. 混合型

typedef struct mystruct {
  int foo;
} mystruct_t;
struct mystruct bar;
mystruct_t buz;

今度は struct mystruct という構造体の定義と、それに対して mystruct_t という別名を付けるのを同時に行っている。
最初に読んだ C の教科書にこう書かれていたためか、昔は盲目的にこう書いていたが、どっちかに統一すればいいだけの話なのであんまり意味ないのよね。

4. トリッキー型

struct {
  int foo;
} bar;

一見 2 と似ているが、typedef の有無で全く意味が異なる。
こちらでは、無名の構造体を定義すると同時に、その型の変数 bar を宣言している。
型名がないので関数の引数にも何にも出来ないが、グローバル変数を構造体に纏めておきたいときや、union や 構造体の中で入れ子にしたいときなど名前を付ける必要の無いときには便利。しかし、typedef の付け忘れと見分けが付きにくいので使いどころに気をつけた方が良い。

5. ものぐさ型

struct mystruct {
  int foo;
} bar;
struct mystruct buz;

3 と 4 に近いが、こちらは struct mystruct という構造体を定義すると同時に、その型の変数 bar を宣言している。
性質の異なる複数のことを同時に行うのは混乱のもとなので個人的にはおすすめしない。
4 と同じく typedef の付け忘れと混同されないように注意が必要というか、typedef を付け忘れたけどよくわからんがとりあえず "struct mystruct" の方が使えるから良いかということで放置されているケースの方が多い気がする。

モナドまとめ

これまで List,State,Maybe の3種類のモナドを見てきたが、結局のところモナドでは表向きは

m >>= f >>= g >>= h

 

と単純に左から右に値を流しているように見せかけて（ドットによる通常の結合と逆向きなのは何か深い意味があるんだろうか）実のところは bind によりリストの展開とか、状態の受け渡しとか、条件による処理の変更などを行っている。

こういった関数の間の繋ぎをするのがモナドで、やはり目的としては「どう繋がるか」ではなく「何と何が繋がっているのか」を明確にしたいというのがあるのだろうか。そのために、「どう繋がるか」の部分はモナドにより ">>=" 記号の中に埋め込まれるというのが「文脈に意味を持たせる」ということなのだろう。

本当に状況によっていろんなことが出来るので、一口にモナドはこんなもんだと簡単に説明できないのはよくわかった。

まだ遅延評価や型などもあるが、とりあえずこんなもんで関数型言語についてなんとなくは理解できたかな。
しばらくは Haskeller になるつもりはないが、最近C++やC#なんかでもラムダ式とかに対応し始めたので、うまく使えそうな機会があれば活用してみようと思う。

Maybe モナド

エラーを扱う

MaybeモナドはStateモナドに比べるとやりたいことはシンプルだ。

ある関数fに入力がある範囲なら処理結果を出力させそれを後続の関数gの入力とし、範囲外ならエラーとして処理を打ち切りたいとする。

普通に考えればせっかくタプルがあるのだから、片方に結果を入れて、もう片方に結果が有効かを示す情報を格納すればよい。さすがに関数型でも手続き型でも後続の関数gの中で入力エラーをチェックするのはナンセンスなので、fとgの接合部分でエラーチェックをしてgを呼び出すか処理を終了するか決めるのが自然だ。

そうするのが自然なのだが、Cでドライバのコード書いた経験があるならわかると思うが、この手のエラーを出力するかもしれない関数を並べると、エラーチェックのためのif文が大量に並んで非常にコードが見づらくなる。普通の神経の人ならぶち切れてマクロを定義して無理矢理1行に納めるが、それでも見栄えはよくない。

C++やJavaのように例外が扱えるとこの手のコードはきれいに書けるが、関数型言語では例外は扱わないようだ。本では例外が危険だからと書いてあったが、個人的には前述の「制御を分割して部品化する」といった都合上、例外が扱いにくい（下位にどんな関数が来るかわからないし、制御を分割しているのでどこで例外を待てばいいのか決めにくい）仕様になっているんじゃないかと思っている。

そこで、Maybeモナドの出番となる。

2つのbind関数

ListモナドとStateモナドはそれぞれ"List", "State"のキーワードによりバインド関数が生成されるが、Maybeモナドでは1つのモナドで"Just"と"Nothing"の2つのキーワードを持っている。（逆にMaybeのくせに"Maybe"ではバインド関数は生成されない）

下の図のように、Justの場合はバインドされた関数gを取り込んでfの戻り値を渡すbind関数を生成する。Nothingの場合はバインドされた関数は無視してそのままNothingを返すbind関数を生成する。

最終的な出力にはNothingを含むのでこれもMaybeモナドとなり、この後にさらに別の関数をバインドしていってもNothingの場合はひたすらNothingが伝搬していくことになる。

理屈がわかったところでこれまで同様JavaScriptで書いてみる。

var Maybe = {
  return: function(a) {
    return Maybe.Just(a)
  },
  Just: function(a) {
    return {
      bind: function(f) {
        return f(a);
      },
      inner: a
    }
  },
  Nothing: function() {
    return {
      bind: function() {
        return Maybe.Nothing();
      },
      inner: 'Nothing'
   }
  }
}

var f = function(a) {
  if(a < 0) return Maybe.Nothing();
  else return Maybe.Just(a * a);
}

var g = function(a) {
  return Maybe.Just(a * 2);
}

document.write(f(1).bind(g).inner+'<br>');
document.write(f(-1).bind(g).inner+'<br>');


fの引数が0以上ならJustにより生成されるbind関数でfの結果がgに渡される。0未満ならNothingにより何もせずにNothingを返すbind関数が生成され、Nothingが継承されていく。

Maybe.JustやMaybe.Nothingはなんか語呂が悪いので、Maybeの外に出すついでにinnerではなくvaluOfを利用するとすっきり書ける。
もちろん前回のdo記法もどきもちゃんと使える。


var Maybe = {
  return: function(a) {
    return Just(a)
  }
}
var Just = function(x) {
  return {
    bind: function(f) {
      return f(x);
    },
    valueOf: function() {
      return x;
    }
  }
}
var Nothing = function(x) {
  return {
    bind: function() {
      return Nothing();
    },
    valueOf: function() {
      return 'Nothing';
    }
  }
}

var f = function(a) {
  if(a < 0) return Nothing();
  else return Just(a * a);
}

var g = function(a) {
  return Just(a * 2);
}

document.write((function() {
  var a, b;
  return MonaDo(f(2),
  [
    function(x_) { a = x_; return g(2); },
    function(x_) { b = x_; return Maybe.return(a + b); }
  ]);
}())+'<br>');




State モナド

何が問題なのか

1. 状態だけを入出力する関数を作っても意味が無い
   なんとなく状態を入力としてそれに基づいて新しい状態を出力する関数を作って繋げていけば関数型プログラムでも状態の変化を表現できそうだが、関数型プログラムは副作用を及ぼさないため本当に状態だけぐるぐる回ることになりこれでは意味が無い
2. タプルは直接繋げられない
   じゃあ、タプルを使えば状態と入出力データをペアで扱えると思うが、f→[タプル]→gと直接繋げることは出来ずf→(a,s)→gと一旦変数に格納しないといけない
3. 変数の破壊的代入が出来ない
   別にタプルを変数に格納しても問題ないように思えるが、関数型プログラムでは変数の破壊的な代入が出来ないため、f→(a,s)→g→(b, s')→h→(c,s'')→と毎度状態を示す変数sをリネームしていかないといけなくなる

裏で状態の受け渡しを行う

そこで、Stateモナドでは表向きは入出力データの受け渡しのみを行い、その裏でStateモナドが状態の受け渡しを行う。
具体的な動作を理解するため、前回と同じく同様の動作をするコードをJavaScriptで書くと以下のようになった。

var State = {
  return: function(a) {
    return State.State(function(s) {
      return Touple(a, s);
    });
  },
  State: function(x) {
    return {
      bind: function(f) {
        return State.State(function(s) {
          var tmp = x(s);
          return runState(f(tmp.lhs), tmp.rhs);
        });
      },
      inner: x
    }
  }
}

var runState = function(state, a) {
  return state.inner(a);
}

var Touple = function(left, right) 
{
  return { lhs: left,rhs: right }
}

基本的には前回のListモナドと同じだが、Stateモナドの場合コンストラクタの引数(?)は関数で、これは値aと状態sを引数としてこれから新しい値a'と新しい状態s'のタプルを生成する関数f
f(a,s) -> (a',s')
があったとして、これを第一引数aでカリー化した関数f'
f'(s) -> (a',s')
を与えて生成する。
例えば、

var f = function(a) {
  return State.State(function(s) {
    return Touple(a+s, s+1);
  });
}

var g = function(a) {
  return State.State(function(s) {
    return Touple(a*s, s+a);
  });
}

var t = runState( f(1).bind(g), 2);

とすれば、
(a=1, s=2) →f()→(a'=a+s=3, s'=s+1=3)→g()→(a''=a'*s'=9,s''=s'+a'=6)
と期待通りの結果が得られる。

また、runStateはbindにより生成されたStateモナド内部の関数を実行して出力と状態を得る関数になる。

作りそのものはListモナドとあまり変わらないのだが、動きは非常に複雑なので頑張って図示すると以下のようになる。

まず関数ｆを入力aでカリー化してsを入力として(a',s')を出力する関数f'を内部関数として持つStateモナドを生成する。
これに関数gをバインドして新しいStateモナドを生成する。このモナドはbind関数の中で生成される関数(仮にinnerとする)を内部関数として持ち、innerはf'とgを内部に持っている。
このモナドに対して状態sを与えてrunStateすると、inner関数が呼び出される。inner関数では、状態sをf'に適用して、a'とs'を得、今度はa'をgに適用する。
gはfと同じくa'でカリー化したg'を持つStateモナドを生成する。
inner関数ではこの生成されたStateモナドに対して先ほどの状態s'を与えてrunStateすると最終的にg'にs'が適用されることになる。

このように、表向きはfとgの間では入出力だけをやりとりしているように見せつつ、StateモナドがrunStateを使って裏で状態の受け渡しを行っている。

今回もわかりやすいようにStateオブジェクトにbindをぶら下げたが、関数オブジェクトにbindをぶら下げればちょっとシンプルにかける。

var State = function(x) {
  x.bind = function(f) {
    return State(function(s) {
      var tmp = x(s);
      return runState(f(tmp.lhs), tmp.rhs);
    });
  }
  return x;
}
State.return = function(a) {
  return State(function(s) {
    return Touple(a, s);
  });
}

var runState = function(state, a) {
  return state(a);
}

もののついでなので、get/put/gets/modify/push/popも実装してみた。大体ルールがわかってきたので、Haskellのコードをそのまま置き換えれば動いた。

var get = function() {
  return State(function(s) {
    return Touple(s, s);
  });
}

var put = function(s) {
  return State(function() {
    return Touple(null, s);
  });
}

var gets = function(f)
{
  return get().bind(Combine(State.return, f));
}

var modify = function(f)
{
  return get().bind(Combine(put, f));
}

var Concat = function(val, arr) 
{
  var newArr = new Array(arr.length+1);
  newArr[0] = val;
  for(var i = 0; i < arr.length; i++) {
    newArr[i+1] = arr[i];
  }
  return newArr;
}

var Head = function(arr) {
  return arr[0];
}

var Tail = function(arr) {
  var newArr = new Array(arr.length-1);
  for(var i = 0; i < newArr.length; i++) {
    newArr[i] = arr[i+1];
  }
  return newArr;
}

var push = function(a)
{
  return modify(function(arr) 
  {
    return Concat(a, arr);
  });
}

var pop = function()
{
  var value;
  return MonaDo(gets(Head),
  [
    function(x_) { value = x_; return modify(Tail); },
    function(x_) { return State.return(value); }
  ]);
}

var t = runState( pop(), [1,4,5]);

popについては展開するのが面倒なのでさらについでにdo記方も作ってみたが、これもほぼほぼHakellの定義通りで出来る。（letはそのままは無理だがそれなりに書きようはある）

var MonaDo = function(m, fs) {
  if(fs.length > 2) {
    return m.bind(function(a) {
      return MonaDo(fs[0](a), fs.slice(1));
    });
  } else {
    return m.bind(function(a) {
      return fs[0](a).bind(fs[1]);
    });
  }
}

モナドとは

関数を繋ぐ

読んだ本にはモナドとは「文脈を持つ計算を扱う」ための仕組みとあるが、何を言っているのかさっぱりわからない。

ネットでもいろいろ勉強した結果、今のところの自分の理解だとモナドは関数を繋げるためのものだと解釈している。（間違っているかもしれないが）

単に関数を繋げるだけならHaskellにはすでに前回のCombineに相当する演算子が用意されている。これを使えば、単純に「 g . f x 」と書けば「 g(f(x)) 」と等価な処理に変換してくれる。

この場合は、単純に下図のように関数fの出力をそのまま関数gの入力として利用する。

 しかしながら、必ずしも毎回出力と入力が一対一対応するとは限らない。時には間に変換を挟んだりする必要が出てくる。そこでモナドが登場する。

 

イメージ的には下図のように先行の関数は出力の値を含んだモナドを出力して、モナドは必要により値を変換して後続の関数に渡す。

具体的な動きについて例としてListモナドを利用して見てみる。モナドの例としてはMaybeモナドがよく挙げられているが、Maybeモナドは動きがトリッキーなので個人的にはListモナドの方が入りやすいと思う。

 

Listモナド

Listモナドでは配列の要素を入力として配列を返す関数を想定している。例えば、値aを入力として、それを[a,a]という2要素の配列に変換する関数fがあったとして、これを前回のmapを利用して配列の各要素に適用すると、

 

f(1) → [1, 1]

map(f)([1,2,3])  → [[1,1],[2,2][3,3]]

 

このように、各要素にfを適用した戻り値の配列が配列として格納されるため、配列が入れ子になってしまう。
これの出力を別の関数gに同じくmapで適用するためには、入れ子を外して

[1,1,2,2,3,3]

 

という配列に変換する必要が出てくる。

Listモナドはこのmapと変換を一括してfとgの接続部分で行ってくれる。個人的にはこの変換に需要があるかはよくわからないが、Listモナドが用意されていると言うことは関数型言語の世界ではそれなりに需要があるのだろう。

Listモナドの挙動を理解するために、試しにJavaScriptで正確かどうかはわからないがそれっぽい挙動をするコードを書いてみた。

var List = function(array) {
  return {
    // (>>=) = concatMap に相当
    bind: function(f) {
      return List(concatMap(f)(array));
    },
    // 中身の配列を取得
    inner: array,
  }
}
// return = (:[]) に相当
List.return = function(a) {
  return List([a]);
}

var concatMap = function(f) {
  return function(array) {
    var newArray = [];
    for(var i = 0; i < array.length; i++) {
      var tmp = f(array[i]);
      newArray = newArray.concat(tmp.inner);
    }
    return newArray;
  }
}

これで、f,gを次のように定義して適用すると、期待通り入れ子を外した配列が出来上がる。

var f = function(a) {
  return List([a, a+1]);
}

var g = function(a) {
  return List([a, a*3]);
}

// f >>= g に相当
document.write( f(1).bind(g).inner + '<br>' );

自分の理解で作ったJavaScriptなのでHaskellと同じことになっているかはわからないが、これからListモナドの動作を見ていくと、まずListモナドでは前の関数の出力aを持ったbind関数を生成する。bind関数では右辺に来る関数を受け取ってこれと持っているaを組み合わせて出力（モナド）を生成する。
絵的に書くと下のようになるだろうか。

Listの場合はモナドを使わずにconcatMapだけで繋げることも出来るが、この場合は
concatMap(g)(concatMap(f)(1))

とconcatMapの方が目立ってしまうので、関数型言語ではモナドを使うことで間の変換処理を隠蔽してfとgの関係性を見えやすくしたということだと思う。

ちなみに、うえの説明ではわかりやすさのためにListオブジェクトにbind関数をぶら下げたが、Array.prototypeに追加することでよりシンプルに使えるようになる。

Array.prototype.bind = function(f) {
  return concatMap(f)(this);
}

var List = {
  return: function(a) {
    return [a];
  }
}

var f = function(a) {
  return [a, a+1];
}

var g = function(a) {
  return [a, a*3];
}

document.write( f(1).bind(g)+'<br>' );

モナドの大まかな挙動がわかったところで、今後はより複雑なMaybeモナドとStateモナドについても理解していく。

関数型言語をかじってみた

プラモのパーツが届かないこともあって、GW中の暇つぶしに「関数プログラミング実践入門」という本を買って関数型言語を勉強してみた。

関数型言語とは

いまさら書くまでもないが、関数型言語における関数は数学的な関数と同じで必ず入力により出力が一意に決まるものになっている。

CやJavaのような手続き型の言語における関数では関数内でstaticやglobal変数等アクセスすることが許されている。この結果として同じ入力を与えても出力が異なることが得る。このようにstaticやglobalな変数にアクセスすることを副作用と呼び関数型言語の関数ではこのような副作用を及ぼすことは許されていない。

このような考え方はオブジェクト指向目指す方向とは逆行しているように思える。オブジェクト指向におけるメソッド（関数）は基本的にはそのメソッドが属するオブジェクトのプロパティを参照もしくは変更するためのものなので、その関数から見て外部の状態を参照/変更するという副作用を及ぼすことを目的として作られているといっても過言ではない。

なぜオブジェクト指向がそうなっているかというと、端的に言えばデータの塊（オブジェクト）とそれに対する働きかけ（メソッド）をペアで取り扱うことで、複雑なデータ構造をよりシンプルな表現で操作できることを目指して作られているからと言える。

このため、手続き型言語で作った関数を単純に入出力を全て引数と戻り値で受け渡しするように変えれば関数型のプログラムになるかというと必ずしもそうではない。これだけでは単に引数と戻り値が大量にあって見づらいだけの手続き型プログラムの関数にしかならない。

制御を分割する

関数型言語では前述のような「副作用を及ぼさない」という性質が注目されがちだが、個人的には関数型言語で重要な点は制御の部品化にあると感じた。これについて、読んだ本の例をベースに自分なりの解釈も含めて例を書き直してみる。

お題となっている処理は、頂点座標の移動と回転を組み合わせる処理になる。これをJavascriptで従来通りの手続き型で書くとこのようになる。

for(var i = 0; i < points.length; i++) {
  var p = move(points[i]);
  newPoints[i] = rotate(p);
}

moveとrotateはそれぞれ頂点の移動と回転を行う処理だが、細かい説明をしなくても何の変哲も無いどこでも見かけるようなコードだと思う。

これに対して同じくJavascriptで関数型っぽく書くと以下のようになる。

newPoints = map(combine(rotate, move))(array);

ここで、mapとcombineは以下のように定義されている。

var map = function(f) {
  return function(array) {
    var newArray = new Array(array.length);
    for(var i = i; i < array.length; i++) {
      newArray[i] = f(array[i]);
    }
    return newArray;
  }
}

var combine = function(f, g) {
  return function(x) {
    var tmp = g(x);
    return f(tmp);
  }
}

関数を返す関数なので慣れないと直感的にわかりにくいかもしれないが、単にループと関数の結合を行う処理になっている。

手続き型のプログラムでは「処理Aの結果を処理Bに代入する」、「これを配列の全要素に行う」といった制御をコードとしてべた書きしていたものを、関数型のプログラムではそれぞれを関数（部品）として部品の組み合わせで目的とする制御を表現することが出来るようになっている。

そう言うと手続き型の関数だって部品じゃないのかと思うかもしれないが、手続き型の関数は言ってしまえば制御と処理をごちゃ混ぜにして一塊にしたもの、いわゆるカプセル化であって、関数型のように「ループ」、「処理Aの後に処理Bを行う」といった細かい制御の単位で部品化出来るわけではない。

実際問題上記の手続き型の例を手続き型プログラムの手法で部品化しようとしても、for文全体を一つの関数にするぐらいしかやりようがない。これでは中の処理を変えようとしたら関数の中身を変える必要があるし、for文の部分だけ再利用するなんてことは普通の手続き型プログラムでは出来ない。

部品化のメリット

このように制御を部品化する一つのメリットとしてはコードの再利用性が向上することがあげられる。おそらく手続き型言語のプログラマなら人生で数千回もfor文を書いていただろうが、これがmapという部品として再利用出来るようになる。

しかしながら、もっと大きなメリットとして検証の容易さがある。このように制御を小さくて単純な部品に分割していくことで、個々の部品に対する検証は容易になる。そして、品質が担保された部品を組み合わせていくことで全体として高品質なプログラムを組み上げることが出来る。

こう言うと勘のいい人なら「ちょっとまて」と思うかもしれない。検証や物作りの常識からいって高品質な部品を組み合わせたからといって高品質になるとは限らない。そこで重要になるのが最初に述べた「副作用を及ぼさない」という関数型プログラムの性質になる。

副作用を及ぼす部品を組み合わせるとお互いの副作用が干渉し合って単体では発生しなかった問題が発生する恐れがある。このため、副作用があることを前提とした世界では部品Aと部品Bを組み合わせて新しい部品Cを作ると、部品CはA,B含めた全体としてもう一度検証し直す必要がある。当然、どんどん部品を組み合わせていって大きな部品になってくるとその分検証の規模が増え中身も複雑になる。

一方で、関数型プログラムでは部品（関数）は副作用を及ぼさないため部品Aと部品Bを組み合わせても部品AとBの品質に変化は起きえない。このため、これらを組み合わせて部品Cを作っても、あくまでも部品Cとして新たに作った部分（たとえば部品の組み合わせ方は適切かとか、使う部品は合っているかとか）のみ検証すればよいことになる。

このように関数型プログラムでは、

• 大きなプログラムを小さな部品に分割する
• 小さくて単純な部品にすることで検証を容易にする
• 単純な部品を組み合わせて複雑な処理を実現する
  （副作用を及ぼさないため、組み合わせても品質は落ちない）

という作り方をして初めて本当の意味で関数型プログラムと言えるのだと理解した。

で、どうやって部品を繋げていくのかという話からモナドについて書こうと思ったが、長くなりそうなのでまた別の記事で