Symbolic derivative in C#

Question

I have translated the following F# code to C# and would appreciate constructive criticism. This code computes the symbolic derivative of the expression f(x)=x³-x-1:

type Expr =
  | Int of int
  | Var of string
  | Add of Expr * Expr
  | Mul of Expr * Expr

let rec d f x =
  match f with
  | Var y when x=y -> Int 1
  | Int _ | Var _ -> Int 0
  | Add(f, g) -> Add(d f x, d g x)
  | Mul(f, g) -> Add(Mul(f, d g x), Mul(g, d f x))

let f =
  let x = Var "x"
  Add(Add(Mul(x, Mul(x, x)), Mul(Int -1, x)), Int -1)

d f "x"

My translation from F# to C# fragments the d function into member functions in classes that implement an Expr interface and adds a hand-written structural pretty printers:

using System;

public interface Expr
{
    Expr d(string x);
}

public class Int : Expr
{
    int n;

    public Int(int m)
    {
        n = m;
    }

    public int Value
    {
        get { return n; }
    }

    public Expr d(string x)
    {
        return new Int(0);
    }

    public override string ToString()
    {
        return "Int " + n.ToString();
    }
}

public class Var : Expr
{
    string x;

    public Var(string y)
    {
        x = y;
    }

    public string Value
    {
        get { return x; }
    }

    public Expr d(string y)
    {
        return (x == y ? new Int(1) : new Int(0));
    }

    public override string ToString()
    {
        return "Var \"" + x + "\"";
    }
}

public class Add : Expr
{
    Expr f, g;

    public Add(Expr a, Expr b)
    {
        f = a;
        g = b;
    }

    public Tuple<Expr, Expr> Value
    {
        get { return Tuple.Create(f, g); }
    }

    public Expr d(string y)
    {
        return new Add(f.d(y), g.d(y));
    }

    public override string ToString()
    {
        return "Add(" + f.ToString() + ", " + g.ToString() + ")";
    }
}

class Mul : Expr
{
    Expr f, g;

    public Mul(Expr a, Expr b)
    {
        f = a;
        g = b;
    }

    public Tuple<Expr, Expr> Value
    {
        get { return Tuple.Create(f, g); }
    }

    public Expr d(string y)
    {
        return new Add(new Mul(f, g.d(y)), new Mul(g, f.d(y)));
    }

    public override string ToString()
    {
        return "Mul(" + f.ToString() + ", " + g.ToString() + ")";
    }
}

class SymbolicDerivative
{
    static void Main(string[] args)
    {
        var x = new Var("x");
        var f = new Add(new Add(new Mul(x, new Mul(x, x)),
                                new Mul(new Int(-1), x)),
                        new Int(-1));
        Console.WriteLine("{0}", f.d("x").ToString());
    }
}

I have also written the derivative function externally to the class hierarchy using the is operator to inspect the type of a given value but I chose this code because I believe it is more idiomatic OOP style.

Answer 1

First, there are some code naming and formatting standards in C# that you should follow:

• Interfaces begin with I
• Method names are Pascal-cased

And here are a small smattering of my personal standards:

• Specify access modifiers at all times (source code are for humans to read)
• Declare non-changing fields with readonly (primarily for intent, but there is supposed performance advantages)
• Declare non-inheritable classes with sealed (again, for intent, but there could be performance advantages)
• Use this. as a prefix for class members

Simple matters:

• Test for null where you would not want to have null objects (i.e. in the constructor)
• Instead of returning a new Int(0) each time in D(), have it be a pre-initialized static member.
• I'm thinking the same for new Int(1)? Your mileage may vary.

All in all, I really like your approach as loosely-coupled OOP using injection.

Given those, I would lightly refactor as such:

namespace SymbolicDerivative
{
    using System;

    public interface IExpr
    {
        IExpr D(string x);
    }

    public sealed class Int : IExpr
    {
        private static readonly IExpr intZero = new Int(0);

        private static readonly IExpr intOne = new Int(1);

        private readonly int n;

        public Int(int m)
        {
            this.n = m;
        }

        public static IExpr IntZero
        {
            get { return intZero; }
        }

        public static IExpr IntOne
        {
            get { return intOne; }
        }

        public int Value
        {
            get { return this.n; }
        }

        public IExpr D(string x)
        {
            return intZero;
        }

        public override string ToString()
        {
            return "Int " + this.n;
        }
    }

    public sealed class Var : IExpr
    {
        private readonly string x;

        public Var(string y)
        {
            if (y == null)
            {
                throw new ArgumentNullException("y");
            }

            this.x = y;
        }

        public string Value
        {
            get { return this.x; }
        }

        public IExpr D(string y)
        {
            return this.x == y ? Int.IntOne : Int.IntZero;
        }

        public override string ToString()
        {
            return "Var \"" + this.x + "\"";
        }
    }

    public sealed class Add : IExpr
    {
        private readonly IExpr f;

        private readonly IExpr g;

        public Add(IExpr a, IExpr b)
        {
            if (a == null)
            {
                throw new ArgumentNullException("a");
            }

            if (b == null)
            {
                throw new ArgumentNullException("b");
            }

            this.f = a;
            this.g = b;
        }

        public Tuple<IExpr, IExpr> Value
        {
            get { return Tuple.Create(this.f, this.g); }
        }

        public IExpr D(string y)
        {
            return new Add(this.f.D(y), this.g.D(y));
        }

        public override string ToString()
        {
            return "Add(" + this.f + ", " + this.g + ")";
        }
    }

    public sealed class Mul : IExpr
    {
        private readonly IExpr f;

        private readonly IExpr g;

        public Mul(IExpr a, IExpr b)
        {
            if (a == null)
            {
                throw new ArgumentNullException("a");
            }

            if (b == null)
            {
                throw new ArgumentNullException("b");
            }

            this.f = a;
            this.g = b;
        }

        public Tuple<IExpr, IExpr> Value
        {
            get { return Tuple.Create(this.f, this.g); }
        }

        public IExpr D(string y)
        {
            return new Add(new Mul(this.f, this.g.D(y)), new Mul(this.g, this.f.D(y)));
        }

        public override string ToString()
        {
            return "Mul(" + this.f + ", " + this.g + ")";
        }
    }

    internal static class SymbolicDerivative
    {
        private static void Main()
        {
            var x = new Var("x");
            var f = new Add(new Add(new Mul(x, new Mul(x, x)), new Mul(new Int(-1), x)), new Int(-1));

            Console.WriteLine("{0}", f.D("x"));
            Console.ReadLine();
        }
    }
}