to_publish.cs

// Copyright © 2015 Aleksey Cherepanov <lyosha@openwall.com>
// License is the same as Symbolism (Apache license)
// TODO: Replace above with the license

using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Text.RegularExpressions;
using System.Linq;

using Microsoft.CSharp;
using System.CodeDom.Compiler;
using System.Linq.Expressions;

using Symbolism;
using Symbolism.Substitute;
using Symbolism.AlgebraicExpand;

using M = Symbolism.MathObject;

// ** We use my.My in ParseFormula
namespace my
{

    public class My
    {

        // ////////////////////////////////////////////////////////////
        // MakeFunction
        class FunctionFactory
        {
            public string name;
            public FunctionFactory(string name_str) {
                name = name_str;
            }
            public Function CreateFunction(params MathObject[] ls) {
                var f = new Function();
                f.name = name;
                f.args = new List<MathObject>(ls);
                return f;
            }
        }
        // TODO: rename MyCallable
        public delegate MathObject MyCallable(params MathObject[] ls);
        public static MyCallable MakeFunction(string name_str) {
            var ff = new FunctionFactory(name_str);
            return new MyCallable(ff.CreateFunction);
        }

        // ////////////////////////////////////////////////////////////
        // Universal copying of object
        // TODO: It is not really needed!
        static MathObject MyClone(MathObject f) {
            // http://stackoverflow.com/questions/2023210/cannot-access-protected-member-object-memberwiseclone
            MethodInfo inst = f.GetType().GetMethod("MemberwiseClone",
                System.Reflection.BindingFlags.Instance
                | System.Reflection.BindingFlags.NonPublic);
            if (inst != null)
                return (MathObject)inst.Invoke(f, null);
            else
                return null;
        }

        // ////////////////////////////////////////////////////////////
        // Universal formula tree traversing with copying and replacement by callback
        static List<MathObject> WalkList(List<MathObject> lst, Func<MathObject, MathObject> callback) {
            return lst.ConvertAll((e) => WalkTree(e, callback));
        }
        static MathObject WalkTree(MathObject f, Func<MathObject, MathObject> callback) {
            MathObject r;
            if (f is Integer
                || f is Symbol
                || f is Bool
                || f is Number
                || f is DoubleFloat
                || f is Fraction
                || f is Undefined
                ) {
                r = MyClone(f);
                return callback(r) ?? r;
            } else if (f is Equation) {
                Equation t = (Equation)MyClone(f);
                t.a = WalkTree(t.a, callback);
                t.b = WalkTree(t.b, callback);
                // TODO: copy Equation's Operator field and MyClone may be avoided.
                r = t.Simplify();
                return callback(r) ?? r;
            } else if (f is Function) {
                Function t = (Function)MyClone(f);
                t.args = WalkList(t.args, callback);
                r = t.Simplify();
                return callback(r) ?? r;
            } else if (f is Product || f is Sum) {
                if (f is Product) {
                    r = MyClone(f);
                    Product t = (Product)r;;
                    t.elts = WalkList(t.elts, callback);
                    r = t.Simplify();
                } else {
                    r = MyClone(f);
                    Sum t = (Sum)r;
                    t.elts = WalkList(t.elts, callback);
                    r = t.Simplify();
                }
                return callback(r) ?? r;
            } else if (f is Power) {
                Power t = (Power)MyClone(f);
                t.bas = WalkTree(t.bas, callback);
                t.exp = WalkTree(t.exp, callback);
                r = t.Simplify();
                return callback(r) ?? r;
            } else {
                throw new Exception("not implemented");
            }
        }

        // ////////////////////////////////////////////////////////////
        // Function substitution (imperative expansion)
        static MathObject SubsFunctionStatic(MathObject f, MyCallable what, MyCallable fun) {
            // We replace 'what' with results of 'fun' called with expressions from formula as parameters.
            string what_name = ((FunctionFactory)what.Target).name;
            Func<MathObject, MathObject> replacer = (o) => {
                // Console.WriteLine("{0} {1}", o, o.GetType());
                if (o is Function) {
                    Function cf = (Function)o;
                    if (cf.name == what_name) {
                        return fun(cf.args.ToArray());
                    }
                }
                return o;
            };
            MathObject t = WalkTree(f, replacer);
            return t;
        }

        // ////////////////////////////////////////////////////////////
        // Subs() is the interface for the function substitution.

        // Variant to substitute plain subtrees/symbols, not functions
        static MathObject Subs(MathObject f, MathObject what, MathObject rep) {
            // return f.Substitute(what, rep);
            return WalkTree(f, (e) => what == e ? rep : e);
        }

        // Helper function
        static void CheckLength(int size, MathObject[] args) {
            if (size != args.Length)
                throw new Exception(string.Format("Unexpected number of arguments, should be {0}, but got {1}", size, args.Length));
        }

        // The wrappers below provide type information to let compiler inference types of lambda expressions, it makes lambda expressions handy to be passed to Subs().

        // Generated with
        // perl -e 'printf qq{static MathObject Subs(MathObject f, MyCallable what, Func<M%s> fun) { return SubsFunctionStatic(f, what, (args) => { CheckLength(%d, args); return fun(%s); }); }\n}, (", M" x $_), $_, (join ", ", map { "args[$_]" } 0 .. $_ - 1) for 0 .. 4;'
        static MathObject Subs(MathObject f, MyCallable what, Func<M> fun) { return SubsFunctionStatic(f, what, (args) => { CheckLength(0, args); return fun(); }); }
        static MathObject Subs(MathObject f, MyCallable what, Func<M, M> fun) { return SubsFunctionStatic(f, what, (args) => { CheckLength(1, args); return fun(args[0]); }); }
        static MathObject Subs(MathObject f, MyCallable what, Func<M, M, M> fun) { return SubsFunctionStatic(f, what, (args) => { CheckLength(2, args); return fun(args[0], args[1]); }); }
        static MathObject Subs(MathObject f, MyCallable what, Func<M, M, M, M> fun) { return SubsFunctionStatic(f, what, (args) => { CheckLength(3, args); return fun(args[0], args[1], args[2]); }); }
        static MathObject Subs(MathObject f, MyCallable what, Func<M, M, M, M, M> fun) { return SubsFunctionStatic(f, what, (args) => { CheckLength(4, args); return fun(args[0], args[1], args[2], args[3]); }); }

        // ////////////////////////////////////////////////////////////
        // Function to throw exception from expression
        static MathObject Fail(string msg) {
            throw new Exception(msg);
        }

        // ////////////////////////////////////////////////////////////
        // Output to TeX / LaTeX

        class CustomFunctionWithPrint : Function
        {
            string custom_format;
            public CustomFunctionWithPrint(Function f, IDictionary<string, string> custom) {
                name = f.name;
                args = f.args;
                if (custom.ContainsKey(name))
                    custom_format = custom[name];
            }
            public override string ToString()
            {
                if (custom_format == null)
                    return base.ToString();
                else
                    return string.Format(custom_format, args.ToArray());
            }
        }
        class CustomPowerWithPrint : Power
        {
            public CustomPowerWithPrint(Power f) : base(f.bas, f.exp) {
            }
            public override string ToString()
            {
                string fmt;
                if (bas is Symbol) {
                    fmt = "{{{0}}}^{{{1}}}";
                } else {
                    // TODO: not all our () are needed even so.
                    fmt = "({{{0}}})^{{{1}}}";
                }
                return string.Format(fmt, bas, exp);
            }
        }
        // custom: function name -> format string
        static string ToTex(MathObject f, IDictionary<string, string> custom)
        {
            // We use regular ToString() but we tweak some objects to have overridden ToString().
            MathObject r = WalkTree(f, (o) => {
                    if (o is Function) {
                        return new CustomFunctionWithPrint((Function)o, custom);
                    }
                    if (o is Power) {
                        return new CustomPowerWithPrint((Power)o);
                    }
                    return o;
                });
            string s = r.ToString();
            s = s.Replace("*", "\\cdot");
            s = s.Replace("==", "=");
            s = s.Replace("(", "\\left(");
            s = s.Replace(")", "\\right)");
            // Digits in the end of name automatically become indexes.
            // TODO: underscores in names are not handled.
            s = Regex.Replace(s, "([a-zA-Z]+)(\\d+)", "$1_{$2}");
            return s;
        }

        // ////////////////////////////////////////////////////////////
        // Class to accumulate text
        // TODO: it is not a great API, it is just a partial example how it could be implemented.
        public class MyOutput
        {
            string title;
            string body = "";
            IDictionary<string, string> custom;
            // Online variant
            string mathjax_source = "https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML";
            // // Local copy
            // string mathjax_source = "mathjax/MathJax.js?config=TeX-AMS-MML_HTMLorMML";
            public MyOutput() {
            }
            public void SetTitle(string str)
            {
                title = str;
            }
            public void SetCustom(IDictionary<string, string> d)
            {
                custom = d;
            }
            public void Add(string str, MathObject o)
            {
                body += str;
                body += " $$" + ToTex(o, custom) + "$$ ";
            }
            public void AddMaybe(string str, MathObject o)
            {
                if (str != null)
                    Add(str, o);
            }
            string html_template =
                "<!DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.01 Transitional//EN\">\n"
                + "<html><head>"
                + "<meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\">"
                + "<title>{0}</title>"
                + "<script src=\"{1}\"></script>"
                + "</head><body>"
                + "<h1>{0}</h1>"
                + "{2}"
                + "</body></html>";
            public string ToHtml()
            {
                return string.Format(html_template, title, mathjax_source, body);
            }
            string tex_template =
                "\\documentclass[a4paper,12pt]{{article}}\n"
                + "\\usepackage[utf8]{{inputenc}}\n"
                + "\\usepackage{{amsmath}}\n"
                + "\\usepackage{{amssymb}}\n"
                + "\\usepackage{{geometry}}\n"
                + "\\usepackage{{latexsym}}\n"
                + "\\usepackage[russian]{{babel}}\n"
                + "\\pagestyle{{empty}}\n"
                + "\\begin{{document}}\n"
                + "\\textbf{{{0}}}\n\n"
                + "{{{1}}}"
                + "\\end{{document}}\n";
            public string ToLatex()
            {
                return string.Format(tex_template, title, body);
            }
        }

        // ////////////////////////////////////////////////////////////
        // Typical building blocks for math

        // Check dependency against symbol or expression
        static bool DependsOnto(MathObject f, MathObject v)
        {
            bool k = false;
            WalkTree(f, (e) => {
                    if (e == v)
                        k = true;
                    return e;
                });
            return k;
        }

        // My simple expansion
        // TODO: AlgebraicExpand() should do the work but hangs on some expressions with powers...
        static MathObject MyExpand(MathObject f)
        {
            return WalkTree(f, (o) => {
                    if (o is Product) {
                        Product t = (Product)o;
                        MathObject r = 1;
                        foreach (MathObject e in t.elts) {
                            if (e is Sum) {
                                Sum t2 = (Sum)e;
                                MathObject nr = 0;
                                if (r is Sum) {
                                    foreach (MathObject e2 in t2.elts) {
                                        foreach (MathObject e3 in ((Sum)r).elts) {
                                            nr += e3 * e2;
                                        }
                                    }
                                } else {
                                    foreach (MathObject e2 in t2.elts) {
                                        nr += r * e2;
                                    }
                                }
                                r = nr;
                            } else {
                                r *= e;
                            }
                        }
                        return r;
                    }
                    return o;
                });
        }

        // ////////////////////////////////////////////////////////////
        // Parser for formulas (through compilation)
        // TODO: it is not a safe approach and was written just for fun.
        static MathObject ParseFormula(string str)
        {
            // Instead of real parsing, we check that given formula does not seem to have anything malicious, compile it as code and execute it to get expression as object.
            // TODO: It is very very probable that it is not safe. Replace it with real parser.
            var s = str;
            s = Regex.Replace(s, "[;\"{}\\[\\]?:\\\\]", "");
            if (s != str)
                throw new Exception("Illegal input");
            // We replace all identifier with calls to create symbols and functions.
            s = Regex.Replace(s, @"([a-zA-Z]\w*)(\(?)",
                (m) => string.Format(m.Groups[2].ToString() == ""
                                     ? "(new Symbol(\"{0}\"))"
                                     : "(my.My.MakeFunction(\"{0}\"))(",
                                     m.Groups[1]));
            // Console.WriteLine("{0}", s);
            // Compilation of code
            var csc = new CSharpCodeProvider();
            var p = new CompilerParameters(new[] { "System.Core.dll", "Symbolism.dll" }, null, true);
            // Add our code into assemblies
            // http://stackoverflow.com/questions/20312341/c-using-class-from-current-appdomain-when-compiling-with-csharpcodeprovider
            foreach (Assembly assembly in AppDomain.CurrentDomain.GetAssemblies()) {
                try {
                    string location = assembly.Location;
                    if (!String.IsNullOrEmpty(location)) {
                        p.ReferencedAssemblies.Add(location);
                    }
                } catch (NotSupportedException) {
                    // this happens for dynamic assemblies, so just ignore it.
                }
            }
            p.GenerateInMemory = true;
            p.GenerateExecutable = false;
            s = "using Symbolism;"
                + "using System;"
                + "public static class p { "
                + "public static MathObject c() { return ("
                + s + ");} }";
            CompilerResults r = csc.CompileAssemblyFromSource(p, s);
            if (r.Errors.Count > 0) {
                foreach (var error in r.Errors) {
                    Console.WriteLine("> {0}", ((CompilerError)error).ErrorText);
                }
                throw new Exception("compilation failure");
            }
            var mi = r.CompiledAssembly.GetType("p").GetMethod("c");
            var expr = (MathObject)mi.Invoke(null, null);
            return expr;
        }

        // ////////////////////////////////////////////////////////////
        // The main code: some artificial examples

        static void Main(string[] args)
        {

            Symbol
                C = new Symbol("C"),
                k = new Symbol("k"),
                m = new Symbol("m"),
                x0 = new Symbol("x0"),
                x = new Symbol("x");

            // We use functions to represent all complex constructions of math language, including sum of sequence, product of sequence, difference.

            // Let's express product of sequence by function P:
            //   P(v, sub, sup, expr(v))
            // where
            // v - dummy variable,
            // sub - subscript,
            // sup - superscript,
            // expr(v) - expression:
            //
            //    sup
            //     ∏ expr(v)
            //  v = sub
            //
            // (∏ - n-ary product, Unicode char U+220F)
            var P = MakeFunction("P");

            // Let's express sum of sequence by function S:
            //   S(v, sub, sup, expr(v))
            // like product of sequence above:
            //
            //    sup
            //     ∑ expr(v)
            //  v = sub
            //
            // (∑ - n-ary summation, Unicode char U+2211)
            var S = MakeFunction("S");

            var p = MakeFunction("p");
            var f = MakeFunction("f");

            var delta = MakeFunction("delta");
            var u = MakeFunction("u");

            var output = new MyOutput();
            output.SetTitle("Examples");

            // We define our custom TeX format strings to represent our custom functions.
            var custom_tex = new Dictionary<string, string>();
            custom_tex["P"] = "\\prod_{{{0} = {1}}}^{{{2}}} ({3})";
            custom_tex["S"] = "\\sum_{{{0} = {1}}}^{{{2}}} ({3})";
            custom_tex["delta"] = "\\Delta {0}";
            output.SetCustom(custom_tex);

            // Equation task = u(x + 1) == (2^x) * u(x);
            Equation task = (Equation)ParseFormula("u(x + 1) == (2^x) * u(x)");
            Console.WriteLine("task = {0}", task);
            output.Add("Formula parsed from string:", task);

            // delta(u(x)) --> u(x + 1) - u(x)
            var t2 = delta(x ^ 2);
            var o2 = Subs(t2, delta, (ux) => Subs(ux, x, x + 1) - ux);
            output.Add("Example function substitution:", t2 == o2);

            var f_solution = P(k, x0, x - 1, p(k)) * (C + S(k, x0, x - 1, f(k) * (P(m, x0, k, p(m))^(-1)) ));
            output.Add("Formula for solution of linear nonhomogeneous difference equation (with step 1):", u(x) == f_solution);
            // Ok, we expressed sum and product in formula, but all simplifications should be done manually, Subs() simplifies some manipulation, but not all.

            System.IO.File.WriteAllText("t.html", output.ToHtml());
            // System.IO.File.WriteAllText("t.tex", output.ToLatex());

        }
    }
}