数式微分器の作成 と D言語での木走査

モチベーション

無性に微分がしたくなった。

結論

出力が頭悪い。

D言語と振り分け式の外部訪問器は相性がいい。

特に数学的におもしろい話はありません。

はじめに

偏導関数値を求める方法には、数値微分 や (トップダウン/ボトムアップ)型自動微分などがありますが、今回は具体的な値を求めたいわけではないので数式微分を行います。

方法

式木で表される関数を、再帰的に微分することで偏微分関数を表す式木を作ります。

まず、ある程度簡単な関数であれば、三角関数のようなより単純な関数の組み合わせや四則演算で表すことが出来ます。

それらの 関数の組み合わせ に対する微分結果の式木を求めることで微分を行います。

例えば、{ y(x) = f(x) + g(x) } という関数の場合、

 y' = f' + g'

というふうに偏導関数を求めることが出来ます。以下に幾つかの関数の組み合わせに対応する微分結果を挙げます。

微分 微分結果
加算:  y = f + g    y' = f'+g'
乗算:  y = fg       y' = f'g + fg'
正弦:  y = sin(f)   y' = f'cos(f)
余弦:  y = cos(f)   y' = -f'sin(f)
冪乗:  y = f^{g}    y' = f^{g}(g'log(f)+\frac{f'}{f} g)
対数:  y = log(f)   y' = \frac{f'}{f}

このような規則に従い式木を走査し組み直すプログラムをD言語で作成しました。

https://github.com/Ryooooooga/DifferentialCulculator

では試しに  1/tan(x)微分してみます。

出力は以下の様になります。

((((-1)*sin(x))*sin(x)^{(-1)})+(cos(x)*(sin(x)^{(-1)}*((cos(x)*(-1))*sin(x)^{(-1)}))))

はい、出力の整形を面倒くさがったため括弧地獄になっています。

これを適当に手動で整形すると、

 -\frac{sin(x)}{sin(x)} - cos(x)\frac{\frac{cos(x)}{sin(x)}}{sin(x)}

の様になり、 1/tan(x)微分結果である

 -1 - \frac{cos^{2}(x)}{sin^{2}(x)}

と一致することがわかります。

まとめ

一応式木を走査して最低限無駄な項を切り落とすようにはしているのですが、出力結果が見れたものではないので、出力の式木に対してより高度な最適化を施す必要がありそうです。

木構造の走査と戦略

デザインパターンっぽい話です。

式木や構文木のような木構造の走査の戦略にはいくつかのパターンがあり、それぞれにメリット、デメリットが存在します。

下に、よく使われる3つのパターンを挙げます。

また、それぞれに例として簡単なC#ソースコードを載せます。

1. 走査メソッド(Interpreter パターン)

最も直感的なパターンです。

式木のノードを表すクラスが走査メソッドを持ち、再帰的に子ノードのメソッドを呼び出すことで木を走査します。

// ノード
interface INode {
    // 走査メソッド
    double Eval();
}

// 加算
class Add: INode {
    private INode left, right;
    
    public Add(INode left, INode right) {
        this.left  = left;
        this.right = right;
    }
    
    // 走査メソッドの実装
    public double Eval() => this.left.Eval() + this.right.Eval();
}

// 乗算
class Mul: INode {
    private INode left, right;
    
    public Mul(INode left, INode right) {
        this.left  = left;
        this.right = right;
    }
    
    // 走査メソッドの実装
    public double Eval() => this.left.Eval() * this.right.Eval();
}

// 数値
class Num: INode {
    private double value;
    
    public Num(double value) {
        this.value = value;
    }
    
    // 走査メソッドの実装
    public double Eval() => this.value;
}

class Prog {
    public static void Main() {
        // 1*2 + 3*4
        var tree = new Add(
            new Mul(new Num(1), new Num(2)),
            new Mul(new Num(3), new Num(4))
        );
        
        System.Console.WriteLine(tree.Eval());
    }
}

実行結果

14

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

上の例では、「加算」、「乗算」、「数値」というノードクラスがそれぞれ Eval メソッドを実装することで木の評価を行っています。

メリット

  1. わかりやすい

    仕組みが単純で動作がわかりやすいです。

  2. 引数をとれる、返り値を返せる

    基底クラス(インターフェース)の Eval メソッドの定義を変更することで自由な個数の引数をとる様にしたり、返り値の型を変更することが出来ます。

  3. クラスの内部構造を隠蔽できる

    メソッドにより走査するため、クラス内部の情報を外部に公開する必要がありません。

    上の例で言えば、Num クラスは内部にどのような値を保持しているのかを外部に公開していません。

  4. 木クラスの追加が容易

    上の例に平方根を表すノード Sqrt を追加する場合、SqrtEval メソッドを適切に実装するだけで平方根を含む式木の評価を行えます。

デメリット

  1. 処理が分散する

    上では比較的単純な例を示しましたが、非正規化非均質抽象構文木のような複雑になりやすい木構造の場合、クラスの数が数十以上になってしまうこともありえます。その場合、それぞれのクラスに処理が分散してしまうため、変更などが行いにくくなります。

    また、処理の追加(例: プリティプリント機能 や 型検査機能、最適化機能など)を行うごとに木クラスの定義が膨れあがっていきます。

単純な木構造の走査に向いたパターンと言えます。

2. 外部木訪問器(Visitorパターン)

非均質抽象構文木などの走査によく用いられるパターンです。

ダブルディスパッチにより、訪問した木クラスの型に応じた訪問器のメソッドに処理を振り分けます。

// 外部訪問器インターフェース
interface IVisitor<T> {
    T Visit(Add node);
    T Visit(Mul node);
    T Visit(Num node);
}

// ノード
interface INode {
    // 訪問器の受け入れ
    T Accept<T>(IVisitor<T> visitor);
}

// 加算
class Add: INode {
    public INode Left  { get; }
    public INode Right { get; }
    
    public Add(INode left, INode right) {
        this.Left  = left;
        this.Right = right;
    }
    
    // IVisitor.Visit(Add) を呼び出す
    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

// 乗算
class Mul: INode {
    public INode Left  { get; }
    public INode Right { get; }
    
    public Mul(INode left, INode right) {
        this.Left  = left;
        this.Right = right;
    }
    
    // IVisitor.Visit(Mul) を呼び出す
    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

// 数値
class Num: INode {
    public double Value { get; }
    
    public Num(double value) {
        this.Value = value;
    }
    
    // IVisitor.Visit(Num) を呼び出す
    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

// 評価訪問器
class Evaluator: IVisitor<double> {
    public double Visit(Add node) => node.Left.Accept(this) + node.Right.Accept(this);
    public double Visit(Mul node) => node.Left.Accept(this) * node.Right.Accept(this);
    public double Visit(Num node) => node.Value;
}

class Prog {
    public static void Main() {
        // 1*2 + 3*4
        var tree = new Add(
            new Mul(new Num(1), new Num(2)),
            new Mul(new Num(3), new Num(4))
        );
        
        // 評価器
        var evaluator = new Evaluator();
        
        System.Console.WriteLine(tree.Accept(evaluator));
    }
}

実行結果

14

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

注目して頂きたいのは 各木クラスに定義された Accept メソッドです。

全く同じ定義の関数がそれぞれのクラスで定義されています。これは一見無駄に見えますが、this の型によって呼び出すメソッドを解決するため必要になります。

また、式木の評価は訪問器が担当するため、評価に関する処理が木クラスから切り離されていることがわかります。

メリット

  1. 木構造と処理を分離できる

    処理を訪問器が行うため、木クラスは処理に関する詳細を知る必要がなくなりました。

  2. 訪問器が状態を持てる

    走査メソッドの場合、走査途中の状態は引数として伝播させる必要がありますが、Visitorパターンの場合は訪問器が処理途中の状態を持つことが出来ます。

  3. 機能の追加に強い

    機能を追加する際には、新しく処理を行う訪問器を作成すればよいため、既存のコードを変更する必要がありません。

    例として、式木を文字列に変換する訪問器 Printer の定義を示します。

class Printer: IVisitor<string> {
    public string Visit(Add node) => $"({node.Left.Accept(this)} + {node.Right.Accept(this)})";
    public string Visit(Mul node) => $"({node.Left.Accept(this)} * {node.Right.Accept(this)})";
    public string Visit(Num node) => $"{node.Value}";
}

tree.Accept(new Printer()); // ((1 * 2) + (3 * 4))

デメリット

  1. 木の内部情報を訪問器に公開する必要がある

    上の例であれば、Num クラスの保持している数値に関する情報などの、処理に必要な情報が外部に公開されていることがわかります。

  2. 引数の型や個数が固定

    訪問器によって引数の型や個数を変えることが難しくなります。

    更に、上の例の場合 ジェネリクスを用いて返り値の型を変えていますが、C++の場合は (templateと仮想関数の相性が良くないため) 処理の結果を呼び出し元へと伝播させるためには訪問器の内部状態を利用するなどの工夫が必要になります。

  3. 処理を行うメソッド名が固定

    Interpreterパターンの場合は処理によって適切なメソッド名を付けられますが、上の例の場合は Visit に固定されます。

構文木の解析などの比較的複雑な木構造の走査に向いているパターンと言えます。

3. 外部訪問器(型情報などによる振り分け)

メソッドの振り分けを訪問器の内部で行うパターンです。

// ノード
interface INode {
    // Acceptは必要ない
}

// 加算
class Add: INode {
    // ...
}

// 乗算
class Mul: INode {
    // ...
}

// 数値
class Num: INode {
    // ...
}

// 評価訪問器
class Evaluator {
    public double Dispatch(INode node) {
        // C# 6.0
        if (node is Add) return this.Eval((Add)node);
        if (node is Mul) return this.Eval((Mul)node);
        if (node is Num) return this.Eval((Num)node);
        
        // 処理できなかった
        throw new System.Exception();
    }
    
    private double Eval(Add node) => this.Dispatch(node.Left) + this.Dispatch(node.Right);
    private double Eval(Mul node) => this.Dispatch(node.Left) * this.Dispatch(node.Right);
    private double Eval(Num node) => node.Value;
}

class Prog {
    public static void Main() {
        // 1*2 + 3*4
        var tree = new Add(
            new Mul(new Num(1), new Num(2)),
            new Mul(new Num(3), new Num(4))
        );
        
        // 評価器
        var evaluator = new Evaluator();
        
        System.Console.WriteLine(evaluator.Dispatch(tree));
    }
}

実行結果

14

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

木クラスの Accept メソッドがなくなり、代わりに訪問器の Dispatch メソッドでクラスに応じたメソッドに処理が振り分けられていることがわかります。

mcsが C# 7 に対応していないため if 文を羅列していますが、C# 7 に対応した環境であれば switch 式を用いたパターンマッチングが使える様になるため、よりスマートに記述することが可能になります。

メリット

  1. 処理を行うメソッド名を自由に決められる

  2. 引数の数や個数が自由

  3. 各走査メソッドを private に出来る。

デメリット

  1. 各訪問器に Dispatch メソッドが必要

  2. メソッドの実装忘れがコンパイル時に確認できない

    Dispatch メソッド内のノード型に対応した振り分け機構に実装忘れがあっても、コンパイラはそれを検知できません。実行時に例外が発生してようやく実装忘れを確認出来ます。

このパターンの利点は一見少ないように見えますが、今回の数式微分を行うプログラムでは式木の走査にこれを採用しました。

なぜかと言うと、このパターンとD言語の言語機能である mixin / template mixin の相性が非常に良いためです。

それらの言語機能に関する詳細は省きますが、文法的にクリーンなC言語のマクロを想像すればだいたいそんな感じです。

では、D言語での 評価訪問器 の実装例を以下に示します。

// 訪問器ミックスイン
template Visitor() {
    // 振り分けメソッド
    auto dispatch(string func, Args...)(Node node, Args args) {
        import std.algorithm: castSwitch;
        
        return node.castSwitch!(
            (Add node) => mixin("this." ~ func ~ "(node, args)"),
            (Mul node) => mixin("this." ~ func ~ "(node, args)"),
            (Num node) => mixin("this." ~ func ~ "(node, args)"),
        )();
    }
}

// 評価訪問器
class Evaluator {
    mixin Visitor;
    
    private double eval(Add node) { return this.dispatch!"eval"(node.left) + this.dispatch!"eval"(node.right); }
    private double eval(Mul node) { return this.dispatch!"eval"(node.left) * this.dispatch!"eval"(node.right); }
    private double eval(Num node) { return node.value; }
}

この訪問器の振り分けメソッドは、visitor.dispatch!"eval"(node) のように呼び出します。

上の Visitor が template mixin と呼ばれる言語機能を使った部分で、mixin Visitor; と書かれた部分に Visitor 内部の 宣言 (この場合は dispatch メソッド)を展開します。

これによって複数の訪問器を書く場合にも、dispatch メソッドの定義は一度だけでよく、実装忘れの可能性を低減することができます。

更に、dispatch のテンプレート引数(上の場合は "eval") に適当な文字列を渡せば 振り分け先のメソッドを eval 以外にも変えられる他、node に続いて 引数を渡すことで 複数の引数を振り分け先のメソッドに渡すことができます。

最後に

D言語はそれなりに良い言語なのでみんなも書けばいいと思います。