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)=x3-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.

• Daniel: I think that's as good as it gets in C# (sigh).

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();
 }
 }
}

• svick: I don't think always specifying access modifiers is an accepted standard. (Though personally I agree it's usually a good idea to specify them even when it's not necessary.)
• Jesse C. Slicer: I thought I had a document from MS where they said this, but I can't find my reference for the life of me. Editing to de-emphasize.
• Leonid: @svick, I see nothing wrong with such mandate (unless it does not compile, such as when declaring an interface). What is a good reason to omit those? Personally, I do not remember all of the defaults off the top of my head. That is a damn good reason to force those. That plus there is a StyleCop rule for that, and I personally would gladly exchange freedom for convenience in that case.
• svick: @Leonid, I wasn't arguing against it (although, personally, I think intenal modifiers for types are useless), just that I don't think it's an accepted standard.
• Jonathan Allen: I find private readonly to be redundant with just readonly.