DLR で名前付き引数を使う

C# で、メソッドに引数として「キーと値のペア」を渡す方法を考えてみます。
例えば HTTP で GET でアクセスするときに URL でクエリ文字列を指定する場合が挙げられます。

よく使われているのは、メソッドの引数に Dictionary や匿名型オブジェクトを渡す方法かと思います。
以下の HttpHelper クラスのように実装します。
なお、WebClient クラスではクエリ文字列 (QueryString プロパティ) は NameValueCollection 型であるため、
受け取った情報を NameValueCollection 型に変換しています。

なお、ここでは題材として CGI’s 郵便番号検索 API を利用しています。

さて、動的言語ランタイム (DLR)名前付き引数を利用して、引数の情報を実行時に解決できないかと考えると、
次のような方法を思いつきます。

dynamic http = new DynamicHttpProxy();
var result = http.Get(Uri_Cgis_Xml, zn: "402", ver: 1);

実際、DynamicObject クラスを継承した DynamicHttpProxy クラスを次のように作れば可能です。

TryInvokeMember メソッドの中で、引数の名前は binder.CallInfo.ArgumentNames で取得できます。
ただし、引数の名前を指定せずに渡された分はここに含まれない (コレクションの長さが変わる) ため注意が必要です。

 

また、C# 7.0 で追加された ValueTuple を利用して、

var result = HttpHelper.Get(Uri_Cgis_Xml, (zn: "6050073"));

とする案もありましたが、

  • 要素が 1 つ以下の場合、タプル リテラルを記述できない
  • コンパイル後はフィールド名が残らないため、実行時に動的に取得できない

という制約により実現できませんでした。

次回:インターフェイスに対する透過プロキシ

作成したサンプル
DynamicHttpConsole (GitHub)

バージョン情報
C# 7.0
.NET Framework 4.5

参照
動的言語ランタイムの概要
名前付き引数と省略可能な引数
タプル – C# によるプログラミング入門

広告

命題論理を実装する (C#)

// この投稿は 数学 Advent Calendar 2016 の 16 日目の記事です。

命題といえば高校数学で「かつ」「または」「ならば」などを学習すると思いますが、
この投稿では、これらを一般化、形式化した命題論理をプログラミングで表現することを目指します。
プログラミングをしない方も、適宜飛ばせばなんとか読めると思います。

用語や定義については、主に Raymond Smullyan「記号論理学: 一般化と記号化」の第 7 章「命題論理入門」に記載されているものを使い、
解説と実装をしていきます。
プログラミング言語としては C# (.NET) を利用します。

Raymond Smullyan「記号論理学: 一般化と記号化」
「記号論理学: 一般化と記号化」
高橋 昌一郎, Raymond Smullyan, 川辺 治之

 

論理結合子

任意の命題 p は、真偽値 (truth value) を持ちます。真偽値とは、真 (T) または偽 (F) です。
そして、「かつ」「または」「ならば」などを一般化した概念を論理結合子 (logical connective) と呼び、次のものがあります。

  1. 否定 (~p)
    真偽値を反転させます。
  2. 論理積 (p ∧ q)
    p および q がともに真のときに限り真です。
  3. 論理和 (p ∨ q)
    p または q のうち、少なくとも一方が真のときに真です。
  4. 含意 (p ⇒ q)
    ~p ∨ q と同義です。
  5. 同値 (p ≡ q)
    (p ⇒ q) ∧ (q ⇒ p) と同義です。計算機においては、XOR 演算の否定と同義です。

論理式

さらに、論理式を次のように定義します。

  • 命題変数 (propositional variable): 命題を表す変数。値は、真または偽となりうる。
  • 命題定数 (propositional constant): 真を表す t および偽を表す f
  • 論理式 (formula): 命題変数、命題定数、論理結合子により構成される式。

ここまでの内容をもとに、論理式を実装します。 論理結合子は、否定のみが単項で、他はすべて二項です。

式を簡単に記述できるようにするため、静的メソッドを用意します。

 

恒真式および矛盾

論理式のうち、含まれる命題変数がどのような真偽値の組合せになっても真であるものを恒真式 (tautology) と呼びます。
逆に、含まれる命題変数がどのような真偽値の組合せになっても偽であるものを矛盾論理式または矛盾 (contradiction) と呼びます。
簡単な例を挙げると、p ∨ ~p は恒真式で、p ∧ ~p は矛盾です。

論理式が恒真式あるいは矛盾であるかどうかを判定するためのメソッドは、次のように実装できます。

以上のコードをまとめて、Blaze (GitHub) というライブラリとして公開しています。 NuGet でインストールできます。

 

ライブラリを使ってみる

さて、このライブラリを利用すると、命題論理に関する定理を証明できるようになります。
実際にいくつかやってみましょう。
Visual Studio で新規のコンソール アプリケーション プロジェクトを作成して、NuGet で Blaze をインストールします。
そして次のようなコードを記述します。

恒真式であるということは、その論理式がつねに成り立つということです。
このコードを実行することで、三段論法、背理法、対偶などを証明できます。

PropositionsConsole

 

次回は、このライブラリを利用してもう少し高度な問題を解いてみます。

次回: 命題論理の複雑な問題を解く (C#)

作成したライブラリ
Blaze (GitHub)
Blaze (NuGet Gallery)

作成したサンプル
PropositionsConsole (GitHub)

バージョン情報
.NET Framework 4.5

参照
Raymond Smullyan「記号論理学: 一般化と記号化」

Azure Table の検索条件を LINQ で指定する

Azure Storage の SDK (Windows Azure Storage) を利用して .NET のクライアントから Table のデータを取得する際に、
検索条件を指定しようとすると、通常の実装では次のようなコードになり少し複雑です。
この例では、フィルター条件を 2 つ指定しています。


var query = new TableQuery<Person>()
    .Where(TableQuery.CombineFilters(
        TableQuery.GenerateFilterCondition("PartitionKey", QueryComparisons.Equal, "2015"),
        TableOperators.And,
        TableQuery.GenerateFilterConditionForInt("Age", QueryComparisons.LessThan, 20)));

var result = PeopleTable.ExecuteQuery(query).ToArray();


ここで、Person  は TableEntity を継承したクラスで、PeopleTable は CloudTable 型のオブジェクトです。

結局、上記の Where メソッドに渡されるのは、

(PartitionKey eq ‘2015’) and (Age lt 20)

という文字列になります。
これなら string.Format メソッドでもよいのではないのかという気もしますが、
プログラミングのミスを防ぐためには、フィルターや射影などの検索条件は LINQ で指定したいところです。

検索条件を LINQ で指定する方法として TableServiceContext クラスを使う方法もあるようですが、
現在は Obsolete 属性が指定されており、非推奨となっています。

とはいえ、自力で IQueryable<T> を実装するのも骨が折れるので、
ここでは簡易的に、TableQuery<T> の拡張メソッドとして Select および Where メソッドを実装していきます。
ラムダ式で指定された検索条件を式ツリーとして受け取って解析し、動的にクエリを生成します。

このような TableHelper クラスを実装することで、Azure Table の検索条件を LINQ で指定できるようになります。
ただし、文字列の不等式については、String クラスの演算子として不等号が定義されていないため、

p.LastName >= "W"

と書くことができず、

p.LastName.CompareTo("W") >= 0

のようにせざるを得ませんでした。

 

作成したサンプル
ExpressionsConsole (GitHub)

バージョン情報
Windows Azure Storage 6.0.0

参照
Windows Azure Storage
Expression<TDelegate> クラス
TableQuery<TElement> Class

Windows Azure Storage Extensions
テーブル サービスに対する LINQ クエリの作成 (古い形式)
TableServiceContext Class (古い形式)

エンティティを匿名型で手軽に実装する (2)

前回のエンティティを匿名型で手軽に実装する (1) で作成した EntityType<TEntity> では、
インスタンスを初期化するために毎回 ConstructorInfo を経由していましたが、
少し重い処理のため、回数が多いと処理時間に影響します。

そこで、あらかじめコンストラクターをラムダ式の式ツリーからコンパイルしておくという方法があります。
先にコードを示します。

取得した ConstructorInfo をもとに、

p => new TEntity((int)p[0], (string)p[1])

のような処理に相当する式ツリーを構築してコンパイルすることで、object[] から TEntity を初期化する関数が得られます。

CreateEntity メソッドの呼び出しを 100 万回実行して計測してみると、手元の環境だと前回のコードでは

  • EntityType の初期化: 0.0006 秒
  • CreateEntity メソッド 100 万回: 0.6 秒

だったのが、今回のコードでは

  • EntityType の初期化: 0.006 秒
  • CreateEntity メソッド 100 万回: 0.06 秒

になりました。

 

前回: エンティティを匿名型で手軽に実装する (1)

作成したサンプル
ExpressionsConsole (GitHub)

参照
Expression<TDelegate> クラス

エンティティを匿名型で手軽に実装する (1)

ここでは、次のようなものをエンティティ型と呼ぶことにします。

  • プロパティが定義されている
  • 各プロパティの値を指定してインスタンスを初期化する方法 (コンストラクターなど) が用意されている

通常、これを C# で実装すると次の図のようになり、少し手間がかかると思うことがあります。
Class1 はコンストラクターの実装が必要であり、Class2 はインスタンス生成時にプロパティ名を指定する必要があります。

エンティティ型の宣言

 

そこで今回は、匿名型を活用してこのようなエンティティ型を定義する方法を考えてみたいと思います。

実は匿名型は、プロパティは読取り専用で定義され、プロパティの数だけ引数を持つコンストラクターが 1 つだけ定義されます。
つまり、ちょうど上記の Class1 のような構造をしています。

このコンストラクターにアクセスできれば、任意のタイミングで匿名型のインスタンスを生成できるというわけです。
そこで、次のように EntityType クラスを実装してみました。

匿名型によりプロパティを宣言し、CreateEntity メソッドによりインスタンスを初期化できます。
CreateEntity メソッドの引数は params object[] のため IntelliSense は利きませんが、簡単に書けている気がします。
ただし匿名型のため、ローカル スコープを抜けられないという制限があります。

 

次に、これを CSV ファイルの読み込みに応用します。
CsvFile クラスで、読み込んだデータを指定された型に変換します。

(なお、ConvertHelper.cs は省略されています。完全なソースコードは ExpressionsConsole – GitHub にあります。)

このようにすると、CsvFile クラスを呼び出す側では IntelliSense が利き、LINQ to Objects でアクセスできます。

CsvFile (IntelliSense)

 

さて、インスタンスを生成するときに毎回 ConstructorInfo にアクセスするのは少しコストがかかるので、
次回は式ツリーを利用してパフォーマンスを改善したいと思います。

次回: エンティティを匿名型で手軽に実装する (2)

作成したサンプル
ExpressionsConsole (GitHub)

参照
匿名型 (C# プログラミング ガイド)

C# で方程式を解く

// この投稿は C# Advent Calendar 2014 の 7 日目の記事です。

ゲーム アプリケーションやセンサーを用いたアプリケーションでは、
力学系の方程式の計算や座標系の変換など、何らかの数値計算が必要になることがあります。

中でも一次方程式は頻度が高いと思いますが、開発者の多くは毎回、
あらかじめ手計算により解の形式 (x = ~) を求めてから実装しているのではないでしょうか?
例えば、ax + b = cx + d の形式のものを x = (d – b) / (a – c) に変形してからプログラムするとか。

処理速度に重点を置く場合はこれでよいのですが、
最初に脳内で導出された式とソースコード上の式とでは形式に乖離が生じることがあり、
確認のために再計算しなければならなくなるなど、保守性が高いとはいえないでしょう。

パターン化できるのであれば、面倒な作業は自動化したいところです。
そこで以下では、なるべく元の方程式のままの形から解を得る仕組みを考えます。

 

まず、数式を C# の標準的な算術演算子を用いて表現できるようにするため、
一変数の多項式を表す Polynomial 構造体を以下のように定義します。
それぞれの次数に対する係数を Dictionary で管理し、必要な演算子を用意します。
(全体のソースコードは GitHub の EquationConsole にあります。)


public struct Polynomial
{
    public static readonly Polynomial X = new Polynomial(new Dictionary<int, double> { { 1, 1 } });

    static readonly IDictionary<int, double> _coefficients_empty = new Dictionary<int, double>();

    IDictionary<int, double> _coefficients;

    IDictionary<int, double> Coefficients
    {
        get { return _coefficients == null ? _coefficients_empty : _coefficients; }
    } 

    // The dictionary represents index/coefficient pairs.
    // The dictionary does not contain entries whose coefficient is 0.
    public Polynomial(IDictionary<int, double> coefficients)
    {
        _coefficients = coefficients;
    }

    public static implicit operator Polynomial(double value)
    {
        return value == 0 ? default(Polynomial) : new Polynomial(new Dictionary<int, double> { { 0, value } });
    }

    public static Polynomial operator +(Polynomial p1, Polynomial p2)
    {
        var coefficients = new Dictionary<int, double>(p1.Coefficients);

        foreach (var item2 in p2.Coefficients)
        {
            AddMonomial(coefficients, item2.Key, item2.Value);
        }
        return new Polynomial(coefficients);
    }

    public static Polynomial operator (Polynomial p1, Polynomial p2)
    {
        var coefficients = new Dictionary<int, double>(p1.Coefficients);

        foreach (var item2 in p2.Coefficients)
        {
            AddMonomial(coefficients, item2.Key, item2.Value);
        }
        return new Polynomial(coefficients);
    }

    public static Polynomial operator *(Polynomial p1, Polynomial p2)
    {
        var coefficients = new Dictionary<int, double>();

        foreach (var item1 in p1.Coefficients)
        {
            foreach (var item2 in p2.Coefficients)
            {
                AddMonomial(coefficients, item1.Key + item2.Key, item1.Value * item2.Value);
            }
        }
        return new Polynomial(coefficients);
    }

    public static Polynomial operator /(Polynomial p, double value)
    {
        var coefficients = new Dictionary<int, double>();

        foreach (var item in p.Coefficients)
        {
            AddMonomial(coefficients, item.Key, item.Value / value);
        }
        return new Polynomial(coefficients);
    }

    // Power
    public static Polynomial operator ^(Polynomial p, int power)
    {
        if (power < 0) throw new ArgumentOutOfRangeException("power", "The value must be non-negative.");

        Polynomial result = 1;

        for (var i = 0; i < power; i++)
        {
            result *= p;
        }
        return result;
    }

    public static Polynomial operator +(Polynomial p)
    {
        return p;
    }

    public static Polynomial operator (Polynomial p)
    {
        return 1 * p;
    }

    static void AddMonomial(Dictionary<int, double> coefficients, int index, double coefficient)
    {
        if (coefficients.ContainsKey(index))
        {
            coefficient += coefficients[index];
        }

        if (coefficient != 0)
        {
            coefficients[index] = coefficient;
        }
        else
        {
            coefficients.Remove(index);
        }
    }
}


今回は等値演算子 (==) などは省きました。
暗黙的型変換演算子 (implicit operator Polynomial) を定義したため、
多項式 -x + 2 や 2x – 1 を次のように表すことができます。

var x = Polynomial.X;
var p1 = x + 2;
var p2 = 2 * x  1;

 

次に、この Polynomial 構造体に、方程式を解くためのメソッドを追加します。
方程式の左辺はこの多項式自身で、右辺は 0 であるとします。
一次方程式のほか、二次方程式についても実装しています。


public int Degree
{
    get { return Coefficients.Count == 0 ? 0 : Coefficients.Max(c => c.Key); }
}

// Substitution
public double this[double value]
{
    get { return Coefficients.Sum(c => c.Value * Math.Pow(value, c.Key)); }
}

// Solve the equation whose right operand is 0.
public double SolveLinearEquation()
{
    if (Degree != 1) throw new InvalidOperationException("The degree must be 1.");

    // ax + b = 0
    var a = GetCoefficient(1);
    var b = GetCoefficient(0);

    return b / a;
}

// Solve the equation whose right operand is 0.
public double[] SolveQuadraticEquation()
{
    if (Degree != 2) throw new InvalidOperationException("The degree must be 2.");

    // ax^2 + bx + c = 0
    var a = GetCoefficient(2);
    var b = GetCoefficient(1);
    var c = GetCoefficient(0);
    var d = b * b  4 * a * c;

    return d > 0 ? new[] { (b  Math.Sqrt(d)) / (2 * a), (b + Math.Sqrt(d)) / (2 * a) }
        : d == 0 ? new[] { b / (2 * a) }
        : new double[0];
}

double GetCoefficient(int index)
{
    return Coefficients.ContainsKey(index) ? Coefficients[index] : 0;
}


インデクサーには代入の機能を割り当てました。
以上で Polynomial 構造体の最低限の実装はできたと思います。

これを使うと、例えば直線 y = x – 1 と直線 y = -2x + 5 の交点 P は次のように求められます。
ほぼ数式のままの形で記述できていると思います。


static class Program
{
    static readonly Polynomial x = Polynomial.X;

    static void Main(string[] args)
    {
        var l1 = x  1;
        var l2 = 2 * x + 5;
        var p_x = (l1 l2).SolveLinearEquation();
        var p_y = l1[p_x];
        Console.WriteLine("P({0}, {1})", p_x, p_y); // P(2, 1)
    }
}


 

次の例では、特定の 2 点を通る直線上で、y 座標から x 座標を求めます。


static class Program
{
    static readonly Polynomial x = Polynomial.X;

    static void Main(string[] args)
    {
        var p1 = new Point2D(0, 300);
        var p2 = new Point2D(1800, 300);
        var y_to_x = GetFunc_y_to_x(p1, p2);
        Console.WriteLine(y_to_x(0)); // 900
        Console.WriteLine(y_to_x(100)); // 600
    }

    // P1, P2 を通る直線上で、指定された y 座標に対応する x 座標を求めるための関数。
    static Func<double, double> GetFunc_y_to_x(Point2D p1, Point2D p2)
    {
        // P1(x1, y1) および P2(x2, y2) を通る直線の方程式 (の公式):
        // (x – x1) (y2 – y1) – (x2 – x1) (y – y1) = 0
        return y => ((x p1.X) * (p2.Y p1.Y) (p2.X p1.X) * (y p1.Y)).SolveLinearEquation();
    }
}

struct Point2D
{
    public double X { get; private set; }
    public double Y { get; private set; }

    public Point2D(double x, double y)
        : this()
    {
        X = x;
        Y = y;
    }
}


座標系のマッピングも、簡単なものであればこれとほぼ同様にできます (一般的には行列を使いますが)。

ちなみに、二次方程式 x2 + x -1 = 0 の解もこの通り。

二次方程式

 

なお、今回は引数が (Polynomial, Polynomial) のみの +, -, * 演算子を定義しましたが、
(Polynomial, double) などの引数を受け付けるオーバーロードを用意すれば、演算量を若干削減できると思います。

作成したサンプル
EquationConsole (GitHub)

参照
オーバーロードされた演算子 (C# プログラミング ガイド)

LINQ のクエリ パターン

Visual Studio で C# のプロジェクト (ここではコンソール アプリケーションにしています) を作成して、
次のようなクエリ式を書いてみます。

Program.cs


class Program
{
    static void Main(string[] args)
    {
        var result =
            from x in new Monad<int>()
            select x;
    }
}

public class Monad<T>
{
}


Monad<T> はとりあえず空のジェネリック クラスです。
この状態でビルドすると、

「ソース型 ○○ のクエリ パターンの実装が見つかりませんでした。’Select’ が見つかりません。」

というコンパイラ エラーになります。

コンパイラ エラー CS1936

 

このクエリ パターンとは LINQ 標準クエリ演算子のことで、具体的には Select, Where, OrderBy メソッドなどがあります。
標準クエリ演算子のクエリ式構文に対応が記載されており、
例えば C# で select 句が有効になるようにするには、
IEnumerable<T> でいうところの Enumerable.Select メソッドに相当するメソッドが実装されている必要があります。

 

というわけで、例として Maybe モナドとそのクエリ パターンを実装してみます。

Maybe.cs


public struct Maybe<T>
{
    public static readonly Maybe<T> None = new Maybe<T>();

    T _value;

    public T Value
    {
        get
        {
            if (!HasValue) throw new InvalidOperationException();
            return _value;
        }
    }

    public bool HasValue { get; private set; }

    public Maybe(T value)
        : this()
    {
        _value = value;
        HasValue = true;
    }

    public static explicit operator T(Maybe<T> value)
    {
        return value.Value;
    }

    public static implicit operator Maybe<T>(T value)
    {
        return new Maybe<T>(value);
    }

    public Maybe<TResult> Bind<TResult>(Func<T, Maybe<TResult>> func)
    {
        return HasValue
            ? func(_value)
            : Maybe<TResult>.None;
    }

    public override string ToString()
    {
        return HasValue
            ? _value.ToString()
            : "";
    }
}

public static class Maybe
{
    public static Maybe<T> ToMaybe<T>(this T value)
    {
        return value;
    }

    public static Maybe<TResult> Select<T, TResult>(this Maybe<T> maybe, Func<T, TResult> selector)
    {
        return maybe.HasValue
            ? selector((T)maybe)
            : Maybe<TResult>.None;
    }

    public static Maybe<TResult> SelectMany<T, U, TResult>(this Maybe<T> maybe, Func<T, Maybe<U>> selector, Func<T, U, TResult> resultSelector)
    {
        var selected = maybe.Bind(selector);
        return selected.HasValue
            ? resultSelector((T)maybe, (U)selected)
            : Maybe<TResult>.None;
    }

    public static Maybe<T> Where<T>(this Maybe<T> maybe, Func<T, bool> predicate)
    {
        return maybe.HasValue && predicate((T)maybe)
            ? maybe
            : Maybe<T>.None;
    }
}


Select メソッドのほか、

  • 複数の from 句に相当する SelectMany メソッド
  • where 句に相当する Where メソッド

を実装しています。
このようにクエリ パターンを実装しておくと、次のようにクエリ式を書くことができます。

Program.cs


class Program
{
    static void Main(string[] args)
    {
        var result1 = Add(1, 2); // 3
        var result2 = Add(2, 1); // None
        var result3 = Add(1, Maybe<int>.None); // None
    }

    static Maybe<int> Add(Maybe<int> x, Maybe<int> y)
    {
        return
            from _x in x
            from _y in y
            where _x < _y
            select _x + _y;
    }
}


 

このようにして、IEnumerable<T> インターフェイス以外でもクエリ式を利用することができます。
ちなみに、IObservable<T> インターフェイスのクエリ式については、
Reactive Extensionsの概要と利用方法にコード例が載っています。

 

作成したサンプル
MonadConsole (GitHub)

参照
コンパイラ エラー CS1936
標準クエリ演算子の概要
select 句 (C# リファレンス)
Query Expression Pattern で Maybe monad を書く
モナドの驚異