エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

関数プログラミングと無限論理多項式(1)

この記事では、サーバーで無限に実行されるプログラムとブラウザーで実行されるプログラムを組み合わせたものを記述する方法について考えていきます。まずC#イテレーターで考えてみます。今後はHaskellなどのプログラミング言語とも比較していきたいと思います。

C# の例

例として3の平方根を1桁ずつ計算することを考えます。

 r_0 = 0 (コードでは number)、 q_0 = 3 (コードでは square_difference)とします。 e = 0, 1, \cdots (コードでは scale)に対して  r_e (コードでは number)、 q_e (コードでは square_difference)、 d_e \in D = \{0, 1, \cdots, 9\} (コードでは dd)を以下のように決めます。

 r_{e+1} = r_e + 10^{-e} d_e q_e = q_0 - r_e^2 q_{e+1} = q_0 - r_{e+1}^2 h_e = r_{e+1}^2 - r_e^2 = q_e - q_{e+1} = r_e \cdot 10^{-e} d \cdot 2 + 10^{-2e} d^2 としたとき  d_e = \max\{ d_e \in D \mid r_{e+1}^2 \le q_0 \} = \max\{ d_e \in D \mid h_e \le q_e \} とします。

以下のコードのクラス Numbers の関数 GetNextDecimalDigit() でこの1桁分の処理を行っています。LongDecimal は小数点以下の任意の桁数を計算することができるクラスとします。

    internal class Numbers
    {
        private LongDecimal number;
        private LongDecimal square_difference;
        private int scale;
        private int current_digit = 0;
        public Numbers(LongDecimal number, LongDecimal square_difference, int scale)
        {
            this.number = number;
            this.square_difference = square_difference;
            this.scale = scale;
        }
        public int CurrentDigit
        {
            get { return current_digit; }
        }
        public int GetNextDecimalDigit()
        {
            LongDecimal two = new LongDecimal(2);
            for (int dd = 9; dd >= 0; dd--)
            {
                LongDecimal zd = new LongDecimal(dd, scale);
                LongDecimal number_sq_diff = number * zd * two + zd * zd;
                if (number_sq_diff <= square_difference)
                {
                    number = number.Add(dd, scale);
                    square_difference -= number_sq_diff;
                    scale++;
                    current_digit = dd;
                    return dd;
                }
            }
            return 0;
        }
    }

サーバーで無限に計算するバージョン

サーバーで無限に計算していてブラウザーで1桁ずつ取り出す場合を考えます。サーバーは無限に状態が変化していくもので、それをクラスで表しています。ここでは以下のようにC#イテレーターを使ったクラスとしています。GenerateDecimal() がジェネレーターとなっています。

    internal class NumbersGenerator
    {
        public NumbersGenerator()
        {
            generator = GenerateDecimal().GetEnumerator();
        }
        private IEnumerator<int> generator;
        public int GetNextDecimalDigit()
        {
            generator.MoveNext();
            return generator.Current;
        }
        public IEnumerable<int> GenerateDecimal()
        {
            LongDecimal number = new LongDecimal();
            LongDecimal square_difference = new LongDecimal(3);
            Numbers nums = new Numbers(number, square_difference, 0);
            for(; ;)
            {
                yield return nums.GetNextDecimalDigit();
            }
        }
    }
サーバーから1回ずつ値を取り出す方法

以下の関数を呼び出すと、result_number に1桁ずつ結果が追加され、その結果の文字列を返します。

        private string NextDecimalByGenerator()
        {
            result_number.AddLast(generator.GetNextDecimalDigit());
            return result_number.Print();
        }

ここで generator はサーバーを表すクラスです。これらは以下のように定義されます。

        private NumbersGenerator generator;
        generator = new NumbersGenerator();

        private LongDecimal result_number;
        result_number = new LongDecimal();
イテレーターを直接使う方法

以下の関数の generator.GenerateDecimal() はジェネレーターで Take はその最初の部分を取り出すもの(C#の拡張メソッド)となります。この関数を呼び出すと、呼び出した回数分の結果の文字列を返します。

        private string NextDecimalByGeneratorTake()
        {
            string res = new LongDecimal(generator.GenerateDecimal().Take(scale + 1)).Print();
            scale++;
            return res;
        }

generator、scale は以下のように定義されます。

        private NumbersGenerator generator;
        generator = new NumbersGenerator();

        private int scale;
        scale = 0;

ブラウザーで計算するバージョン

サーバーにデータがあってそれをブラウザーで取り出して1桁ずつ計算する場合を考えます。ここでも(サーバーから1回ずつ値を取り出す場合は)クラスで表しています。以下のようにC#イテレーターを使ったクラスとしています。C#ではイテレーターの実行中に値を返す方法がないので、クラスのメンバーとして返すようになっています(Numbers プロパティ)。この Numbers プロパティを GenerateDecimalServer() のイテレーターのループ内で参照しています。

    internal class NumbersServer
    {
        public NumbersServer()
        {
            generator_server = GenerateDecimalServer().GetEnumerator();
        }
        private IEnumerator<Numbers> generator_server;
        private Numbers current_numbers;
        private Numbers GetNumbers()
        {
            generator_server.MoveNext();
            return generator_server.Current;
        }
        private void SetNumbers(Numbers numbers)
        {
            current_numbers = numbers;
        }
        public Numbers Numbers
        {
            get
            {
                return GetNumbers();
            }
            set
            {
                SetNumbers(value);
            }
        }
        public IEnumerable<Numbers> GenerateDecimalServer()
        {
            LongDecimal number = new LongDecimal();
            LongDecimal square_difference = new LongDecimal(3);
            current_numbers = new Numbers(number, square_difference, 0);
            for (; ; )
            {
                yield return current_numbers;
            }
        }
    }
サーバーから1回ずつ値を取り出す方法

以下の関数を呼び出すと、result_number に1桁ずつ結果が追加され、その結果の文字列を返します。

        private string NextDecimalByServer()
        {
            Numbers numbers = generator_server.Numbers;
            int dd = numbers.GetNextDecimalDigit();
            generator_server.Numbers = numbers;
            result_number.AddLast(dd);
            return result_number.Print();
        }

ここで generator_server はサーバーを表すクラスです。これらは以下のように定義されます。

        private NumbersServer generator_server;
        generator_server = new NumbersServer();

        private LongDecimal result_number;
        result_number = new LongDecimal();
Iterate 関数を使う方法

イテレーターを直接使うとイテレーターに値を返す方法がないので「サーバーで無限に計算するバージョン」のような「イテレーターを直接使う方法」はできません。ここではサーバーのクラスを使わずに、Haskell の iterate と同様の関数 Iterate を定義して使います。Iterate は指定された初期値から指定された関数を繰り返して適用した無限の列を返すもので、Iterate で生成されるものがジェネレーターで生成されるものと同様のものとなります。Select は Haskell の map に相当するもの(C#の拡張メソッド)となります。この関数を呼び出すと、呼び出した回数分の結果の文字列を返します。

        private string NextDecimalByServerTake()
        {
            LongDecimal number = new LongDecimal();
            LongDecimal square_difference = new LongDecimal(3);
            Numbers init_numbers = new Numbers(number, square_difference, 0);
            init_numbers.GetNextDecimalDigit();
            string res = new LongDecimal(Iterate(NextNumbers, init_numbers).Take(scale + 1).Select(numbers => numbers.CurrentDigit)).Print();
            scale++;
            return res;
        }

scale は以下のように定義されます。

        private int scale;
        scale = 0;

小数点以下20桁を計算した結果は以下のようになります。
1.73205080756887729352

今後はこれらを統一して記述する方法を考えていきます。