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

自由モノイドプログラミング言語の作成

前回のフィボナッチ数列を生成するプログラムを書くことができる簡単なプログラミング言語を作ります。C# のパーサコンビネータ Sprache (Sprache/README.md at develop · sprache/Sprache · GitHub)を使ってやってみます。言語の構文の各要素をそれに対応するクラスのオブジェクトに変換します。構文に対応するクラスの説明は省略します。

まだ使い方がよくわからない段階でやっていますが以下のようになります。複雑すぎる気がするので今後もう少し簡単にしていきたいと思います。もう少しわかってきたら説明を書きたいと思います。

    internal class MonParser
    {
        public static readonly Parser<DomExp> ParseDomExp =
            Parse.Ref(() => ParseDomSum);

        public static readonly Parser<MonExp> ParseExp =
            Parse.Ref(() => ParseProd);

        public static readonly Parser<MonBlock> ParseProg =
            Parse.Ref(() => ParseBlock);

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

        static readonly Parser<string> ParseName =
            Parse.Identifier(Parse.Letter, Parse.LetterOrDigit.Or(Parse.Char('_'))).Token();

        static readonly Parser<DomExp> ParseIdentifier =
            from name in ParseName
            select DomExp.Name(name);

        static readonly Parser<string> ParseSeqName =
            Parse.Identifier(Parse.Char('_'), Parse.LetterOrDigit.Or(Parse.Char('_'))).Token();

        static readonly Parser<DomExp> ParseSeqIdentifier =
            from name in ParseSeqName
            select DomExp.Name(name);

        static readonly Parser<MonNameList> ParseNameList =
            from first in ParseName
            from rest in Parse.Char(',').Token().Then(_ => ParseName).Many()
            select new MonNameList(new[] { first }.Concat(rest));

        static readonly Parser<MonNameList> ParsePNameList =
            from p1 in Parse.Char('(').Token()
            from list in ParseNameList.XOr(Parse.Return(new MonNameList()))
            from p2 in Parse.Char(')').Token()
            select list;

        static readonly Parser<MonExpList> ParseExpList =
            from first in ParseExp
            from rest in Parse.Char(',').Token().Then(_ => ParseExp).Many()
            select new MonExpList(new[] { first }.Concat(rest));

        static readonly Parser<MonExpList> ParsePExpList =
            from p1 in Parse.Char('(').Token()
            from list in ParseExpList.XOr(Parse.Return(new MonExpList()))
            from p2 in Parse.Char(')').Token()
            select list;

        static readonly Parser<MonExp> ParsePExp =
            from p1 in Parse.Char('(').Token()
            from exp in ParseExp
            from p2 in Parse.Char(')').Token()
            select exp;

        static readonly Parser<DomExp> ParsePDomExp =
            from p1 in Parse.Char('(').Token()
            from exp in ParseDomExp
            from p2 in Parse.Char(')').Token()
            select exp;

        static readonly Parser<DomExpList> ParseDomExpList =
            from first in ParseDomExp
            from rest in Parse.Char(',').Token().Then(_ => ParseDomExp).Many()
            select new DomExpList(new[] { first }.Concat(rest));

        static readonly Parser<DomExpList> ParsePDomExpList =
            from p1 in Parse.Char('(').Token()
            from list in ParseDomExpList.XOr(Parse.Return(new DomExpList()))
            from p2 in Parse.Char(')').Token()
            select list;

        static readonly Parser<DomExp> ParseDomPrim =
            ParsePDomExp
            .Or(ParseNumber)
            .Or(ParseIdentifier);

        static readonly Parser<DomExp> ParseDomSum =
            Parse.ChainOperator(Parse.String("+").Token().Text(), ParseDomPrim, (op, x, y) => DomExp.Bin(op, x, y));

        static readonly Parser<MonExp> ParseDomFunc =
            from name in ParseName
            from args in ParsePDomExpList
            select MonExp.Func(name, args);

        static readonly Parser<MonExp> ParseFunc =
            from name in ParseSeqName
            from args in ParsePExpList
            select MonExp.Func(name, args);

        static readonly Parser<MonExp> ParseUnit =
            from exp in ParseDomExp
            select MonExp.Unit(exp);

        static readonly Parser<MonExp> ParsePrim =
            ParsePExp
            .Or(ParseDomFunc)
            .Or(ParseFunc)
            .Or(ParseUnit);

        static readonly Parser<MonExp> ParseProd =
            Parse.ChainOperator(Parse.String("*").Token().Text(), ParsePrim, (op, x, y) => MonExp.Bin(op, x, y));

        static readonly Parser<MonStat> ParseDef =
            from name in ParseName
            from prms in ParsePNameList
            from t2 in Parse.String("=").Token()
            from e in ParseExp
            select MonStat.Define(name, prms, e);

        static readonly Parser<MonStat> ParseStatementExp =
            from e in ParseExp
            select MonStat.StatExp(e);

        static readonly Parser<MonStat> ParseStatement =
            ParseDef
            .Or(ParseStatementExp);

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

引数で渡すバージョン

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

            fib(x, y) = x * fib(y, x + y);
            fib(0, 1)

以下のように使います。

        private void GenerateCodeFibpnacciPrms()
        {
            string src = "fib(x, y) = x * fib(y, x + y); fib(0, 1)";
            MonBlock prog = MonParser.ParseProg.Parse(src);
            textBoxResult.Text = prog.Print();
        }

以下のような C# のコードを出力します。これを直接実行する方法がないので、いったんコードとして出力して、それをコンパイルして実行することにします。Sprache の例で「式木」に変換するものがあったのですが、このようなコードは「式木」に変換することはできないようです。

        private IEnumerable<int> GenerateCodeFibpnacciPrmsResult()
        {
            IEnumerable<int> fib(int x, int y)
            {
                yield return x;
                foreach (var e in fib(y, x + y))
                {
                    yield return e;
                }
            }
            return fib(0, 1);
        }

Zip を使うバージョン

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

            fib(x, y) = x * y * _zipsum(fib(x, y), _tail(fib(x, y)));
            fib(0, 1)

以下のように使います。

        private void GenerateCodeFibpnacciZip()
        {
            string src = "fib(x, y) = x * y * _zipsum(fib(x, y), _tail(fib(x, y))); fib(0, 1)";
            MonBlock prog = MonParser.ParseProg.Parse(src);
            textBoxResult.Text = prog.Print();
        }

_tail と _zipsum はあらかじめ定義されているとします。先頭が「_」である関数は数値の列を扱う関数であるとします。

        private IEnumerable<int> _tail(IEnumerable<int> x)
        {
            return x.Skip(1);
        }
        private IEnumerable<int> _zipsum(IEnumerable<int> x, IEnumerable<int> y)
        {
            return x.Zip(y, (a, b) => a + b);
        }

以下のような C# のコードを出力します。

        private IEnumerable<int> GenerateCodeFibpnacciZipResult()
        {
            IEnumerable<int> fib(int x, int y)
            {
                yield return x;
                yield return y;
                foreach (var e in _zipsum(fib(x, y), _tail(fib(x, y))))
                {
                    yield return e;
                }
            }
            return fib(0, 1);
        }