自由モノイドのイテレーター(11) - 非専門的シンギュラリティー研究所

自由モノイドプログラミング言語の作成(MonIter C#版バージョン1.0)

Python 版 MonIter バージョン 1 の C# 版です。

構文解析

C# のパーサコンビネータ Sprache (Sprache/README.md at develop · sprache/Sprache · GitHub)を使っています。まだ使い方はあまりわかっていません。構文解析の部分は以下のようになります。構文は Python 版と同じです。

    internal class MonParser
    {
        private static readonly Parser<Expression> ParseExpression =
            Parse.Ref(() => ParseExpression_);

        private static readonly Parser<Number> ParseNumber =
            from num in Parse.Decimal.Token()
            select DomainExpression.Number(num);

        private static readonly Parser<Identifier> ParseIdentifier =
            from name in Parse.Identifier(Parse.Letter, Parse.LetterOrDigit.Or(Parse.Char('_'))).Token()
            select DomainExpression.Identifier(name);

        private static readonly Parser<DomainTerm> ParseDomainTerm =
            ((Parser<DomainTerm>)ParseIdentifier).Or(ParseNumber);

        private static readonly Parser<DomainExpression> ParseDomainExpression =
            from first in ParseDomainTerm
            from rest in Parse.Char('+').Token().Then(_ => ParseDomainTerm).Many()
            select new DomainExpression(new[] { first }.Concat(rest));

        private static readonly Parser<IEnumerable<DomainExpression>> ParseDomainExpressionList =
            from first in ParseDomainExpression
            from rest in Parse.Char(',').Token().Then(_ => ParseDomainExpression).Many()
            select new DomainExpression[] { first }.Concat(rest);

        private static readonly Parser<DomainFunction> ParseDomainFunction =
            from name in ParseIdentifier
            from po in Parse.Char('(').Token()
            from list in ParseDomainExpressionList
            from pc in Parse.Char(')').Token()
            select Expression.DomainFunction(name, list);

        private static readonly Parser<IEnumerable<Expression>> ParseExpressionList =
            from first in ParseExpression
            from rest in Parse.Char(',').Token().Then(_ => ParseExpression).Many()
            select new Expression[] { first }.Concat(rest);

        private static readonly Parser<Function> ParseFunction =
            from pr in Parse.Char('$').Token()
            from name in ParseIdentifier
            from po in Parse.Char('(').Token()
            from list in ParseExpressionList
            from pc in Parse.Char(')').Token()
            select Expression.Function(name, list);

        private static readonly Parser<Term> ParseTerm =
            ((Parser<Term>)ParseFunction).Or(ParseDomainFunction).Or(ParseDomainExpression);

        private static readonly Parser<Expression> ParseExpression_ =
            from first in ParseTerm
            from rest in Parse.Char('&').Token().Then(_ => ParseTerm).Many()
            select new Expression(new[] { first }.Concat(rest));

        private static readonly Parser<Statement> ParseExpressionStatement =
            from exp in ParseExpression
            select Statement.ExpressionStatement(exp);

        private static readonly Parser<IEnumerable<Identifier>> ParseParameterList =
            from first in ParseIdentifier
            from rest in Parse.Char(',').Token().Then(_ => ParseIdentifier).Many()
            select new Identifier[] { first }.Concat(rest);

        private static readonly Parser<Definition> ParseDefinition =
            from pr in Parse.String("def").Token()
            from name in ParseIdentifier
            from po in Parse.Char('(').Token()
            from list in ParseParameterList
            from pc in Parse.Char(')').Token()
            from eq in Parse.Char('=').Token()
            from exp in ParseExpression
            select Statement.Definition(name, list, exp);

        private static readonly Parser<Statement> ParseStatement =
            ParseDefinition.Or(ParseExpressionStatement);

        public static readonly Parser<Prog> ParseProgram =
            from first in ParseStatement
            from rest in Parse.Char(';').Token().Then(_ => ParseStatement).Many()
            select new Prog(new[] { first }.Concat(rest));
    }

自由モノイドのクラス

Python 版と同様に、無限の場合も扱うことができる自由モノイドのクラスを作成します。Collect は、Python 版の chain.from_iterable に対応するものです。Python 版では Expression クラスで chain.from_iterable を使っていたのですが、これに対応するものが C# ではわからなかったので作成しました。

    internal class FreeMonoid<T> : IEnumerable<T>
    {
        private IEnumerable<T> elements;
        public FreeMonoid(IEnumerable<T> enumobj)
        {
            elements = enumobj;
        }
        public IEnumerator<T> GetEnumerator()
        {
            return elements.GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        public static FreeMonoid<T> Collect(IEnumerable<FreeMonoid<T>> ms)
        {
            IEnumerable<T> CollectEnum(IEnumerable<FreeMonoid<T>> ms)
            {
                foreach (FreeMonoid<T> m in ms)
                {
                    foreach (T e in m)
                    {
                        yield return e;
                    }
                }
            }
            return new FreeMonoid<T>(CollectEnum(ms));
        }
        public static FreeMonoid<T> operator &(FreeMonoid<T> mon1, FreeMonoid<T> mon2)
        {
            return new FreeMonoid<T>(mon1.Concat(mon2));
        }
        public static FreeMonoid<T> Unit(T element)
        {
            return new FreeMonoid<T>(new List<T> { element });
        }
        public static FreeMonoid<T> Zero
        {
            get
            {
                return new FreeMonoid<T>(new List<T> { });
            }
        }
        public FreeMonoid<T> ZipWith(FreeMonoid<T> mon2, Func<T, T, T> func)
        {
            return new FreeMonoid<T>(this.Zip(mon2, func));
        }
        public FreeMonoid<T> Tail()
        {
            return new FreeMonoid<T>(this.Skip(1));
        }
        public FreeMonoid<U> Map<U>(Func<T, U> func)
        {
            return new FreeMonoid<U>(this.Select(func));
        }
    }

構文に対応するクラス

構文に対応するクラスの説明は省略します。

フィボナッチ数列の例

引数で渡すバージョン

以下のようなコードを変換します。

    def fib(x, y) = x & fib(y, x + y);
    fib(0, 1)

以下のように使います。

        private FreeMonoid<int> InfiniteFibpnacciPrms()
        {
            string src = "def fib(x, y) = x & fib(y, x + y); fib(0, 1)";
            Prog prog = MonParser.ParseProgram.Parse(src);
            return prog.Eval();
        }

Zip を使うバージョン

以下のようなコードを変換します。

    def fib(x, y) = x & y & $zipsum(fib(x, y), $tail(fib(x, y)));
    fib(0, 1)

以下のように使います。

        private FreeMonoid<int> InfiniteFibpnacciZip()
        {
            string src = "def fib(x, y) = x & y & $zipsum(fib(x, y), $tail(fib(x, y))); fib(0, 1)";
            Prog prog = MonParser.ParseProgram.Parse(src);
            return prog.Eval();
        }

$tail と $zipsum はあらかじめ定義されているとします。先頭が「$」である関数は数値の列を扱う関数(引数が一つの数値ではなく数値の列)であるとします。