8
\$\begingroup\$

I've written a small library, that provides a way to store mathematical expressions in a tree-like structure, and provides a method, that finds the first derivative of a function. I know, that there are various libraries, that do the same, but I'd like to create an application, which calculates the derivative, for fun, and learning, and this library is a portion of that application.

I'd like to know, whether my design is good, and what can I do to improve the quality of my code.

Code

In Derivative.cs, there is a static class, that contains the method, which computes the derivative. This function takes in an expression, and a string, which is the name of the variable, we will differentiate respect to, and produces an expression, which is the derivative of the input expression. It doesn't always produce the most reduced expression.

using System;
using System.Collections.Generic;
using CalculateDerivative.Operations;

namespace CalculateDerivative
{
    public static class Derivative
    {
        public static Expression CalculateDerivative(Expression exp, string variableName)
        {
            var root = exp.Root;
            Expression[] arguments;
            if (root.Children != null)
            {
                arguments = new Expression[root.Children.Length];
                for (var i = 0; i < root.Children.Length; i++)
                {
                    arguments[i] = new Expression(root.Children[i]);
                }
            }
            else
            {
                arguments = null;
            }
            switch (root)
            {
                case Add _:
                    return AddDerivative(arguments, variableName);
                case Subtract _:
                    return SubtractDerivative(arguments, variableName);
                case Multiply _:
                    return MultiplyDerivative(arguments, variableName);
                case Divide _:
                    return DivideDerivative(arguments, variableName);
                case Power _:
                    return PowerDerivative(arguments, variableName);
                case Constant _:
                    return new Expression(new Constant(0));
                case Variable v:
                    return new Expression(new Constant(v.Name == variableName ? 1 : 0));
                case Log l:
                    return LogDerivative(arguments, variableName, l.Base);
                default:
                    throw new Exception("This function is not supported yet");
            }
        }

        private static Expression AddDerivative(IReadOnlyList<Expression> arguments, string varName)
        {
            return new Expression(new Add(new[]
                {CalculateDerivative(arguments[0],varName).Root, CalculateDerivative(arguments[1],varName).Root}));
        }

        private static Expression SubtractDerivative(IReadOnlyList<Expression> arguments, string varName)
        {
            return new Expression(new Subtract(new[]
                {CalculateDerivative(arguments[0],varName).Root, CalculateDerivative(arguments[1],varName).Root}));
        }

        private static Expression MultiplyDerivative(IReadOnlyList<Expression> arguments, string varName)
        {
            return new Expression(new Add(new Node[]
            {
                new Multiply(new[]{arguments[0].Root,CalculateDerivative(arguments[1],varName).Root}),
                new Multiply(new[]{arguments[1].Root,CalculateDerivative(arguments[0],varName).Root})
            }));
        }

        private static Expression DivideDerivative(IReadOnlyList<Expression> arguments, string varName)
        {
            return new Expression(new Divide(new Node[]
            {
                new Subtract(new Node[]
                {
                    new Multiply(
                        new[] {arguments[1].Root, CalculateDerivative(arguments[0], varName).Root}),
                    new Multiply(
                        new[] {arguments[0].Root, CalculateDerivative(arguments[1], varName).Root})
                }),
                new Power(new[]{arguments[1].Root,new Constant(2)})
            }));
        }

        private static Expression PowerDerivative(IReadOnlyList<Expression> arguments, string varName)
        {
            return new Expression(new Multiply(new Node[]
            {
                new Power(new[] {arguments[0].Root, arguments[1].Root}),
                new Add(new Node[]
                {
                    new Divide(new[]
                    {
                        new Multiply(new[]
                            {arguments[1].Root, CalculateDerivative(arguments[0], varName).Root}),
                        arguments[0].Root
                    }),
                    new Multiply(new[]
                    {
                        new Log(new[] {arguments[0].Root}, Math.E),
                        CalculateDerivative(arguments[1], varName).Root
                    })
                })
            }));
        }

        private static Expression LogDerivative(IReadOnlyList<Expression> arguments, string varName, double _base)
        {
            return new Expression(new Multiply(new Node[]
            {
                new Divide(new Node[]
                {
                    new Constant(1),
                    new Multiply(new Node[]
                    {
                        arguments[0].Root,
                        new Log(new[] {new Constant(_base)}, Math.E)
                    })
                }),
                CalculateDerivative(arguments[0], varName).Root
            }));
        }
    }
}

The class, in which the expressions are stored, is in Expression.cs:

namespace CalculateDerivative
{
    public class Expression
    {
        public Node Root{ get; set; }

        public Expression(Node root)
        {
            Root = root;
        }
        public override bool Equals(object obj)
        {

            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }

            return Root.Equals(((Expression)obj).Root);
        }
        public override int GetHashCode()
        {
            var hash = 17;
            hash = hash * 23 + Root.GetHashCode();
            return hash;
        }
    }
}

The base class for the nodes in the tree structure is in Node.cs:

namespace CalculateDerivative
{
    public abstract class Node
    {
        protected abstract int ArgumentNumber { get; }
        public Node[] Children { get; set; }

        protected Node(Node[] children)
        {
            if (children==null)
            {
                if (ArgumentNumber!=0)
                {
                    throw new Exception("Wrong number of arguments");
                }
                Children = children;
                return;
            }
            if (children.Length != ArgumentNumber)
            {
                throw new Exception("Wrong number of arguments");
            }
            Children = children;
        }
        public override bool Equals(object obj)
        {

            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }
            var equals = true;
            for (int i = 0; i < Children.Length; i++)
            {
                if (!Children[i].Equals(((Node)obj).Children[i]))
                {
                    equals = false;
                }
            }
            return equals;
        }
        public override int GetHashCode()
        {
            var hash = 17;
            hash = hash * 23 + ArgumentNumber.GetHashCode();
            hash = hash * 23 + Children.GetHashCode();
            return hash;
        }
    }
}

There are various classes inherited from this class, for all the mathematical operations, that are supported. In Constant.cs there are the numbers, and in Variable.cs there are the variables (x,y,z,..)

Add.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Add : Node
    {
        protected override int ArgumentNumber => 2;
        public Add(Node[] children):base(children)
        {
        }
    }
}

Constant.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Constant : Node
    {
        protected override int ArgumentNumber => 0;
        public double Value { get; set; }
        public Constant(double value) : base(null)
        {
            Value = value;
        }
        public override bool Equals(object obj)
        {

            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }

            return Value.Equals(((Constant)obj).Value);
        }
        public override int GetHashCode()
        {
            var hash = 17;
            hash = hash * 23 + ArgumentNumber.GetHashCode();
            hash = hash * 23 + Children.GetHashCode();
            hash = hash * 23 + Value.GetHashCode();
            return hash;
        }
    }
}

Divide.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Divide : Node
    {
        protected override int ArgumentNumber => 2;
        public Divide(Node[] children):base(children)
        {
        }
    }
}

Log.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Log : Node
    {
        protected override int ArgumentNumber => 1;

        public double Base { get; set; }
        public Log(Node[] children,double _base):base(children)
        {
            Base = _base;
        }
    }
}

Multiply.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Multiply : Node
    {
        protected override int ArgumentNumber => 2;
        public Multiply(Node[] children):base(children)
        {
        }
    }
}

Power.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Power : Node
    {
        protected override int ArgumentNumber => 2;
        public Power(Node[] children):base(children)
        {
        }
    }
}

Subtract.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Subtract : Node
    {
        protected override int ArgumentNumber => 2;
        public Subtract(Node[] children):base(children)
        {
        }
    }
}

Variable.cs:

namespace CalculateDerivative.Operations
{
    public sealed class Variable : Node
    {
        protected override int ArgumentNumber => 0;
        public string Name { get; }
        public Variable(string name):base(null)
        {
            Name = name;
        }
        public override bool Equals(object obj)
        {

            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }

            return Name.Equals(((Variable)obj).Name);
        }
        public override int GetHashCode()
        {
            var hash = 17;
            hash = hash * 23 + ArgumentNumber.GetHashCode();
            hash = hash * 23 + Children.GetHashCode();
            hash = hash * 23 + Name.GetHashCode();
            return hash;
        }
    }
}

Usage

If you'd like to calculate the derivative of \$x^2\$, first you need to create an Expression, and call the function CalculateDerivative:

using CalculateDerivative;
using CalculateDerivative.Operations;
var expression=new Expression(new Power(new Node[] {new Variable("x"),new Constant(2)}));
var derivative=Derivative.CalculateDerivative(expression,"x")

It produces the following tree structure:

tree-structure

Which is equivalent to:

\$x^2(\frac{(2 \cdot 1)}{x + log_e(x) \cdot 0}) = 2x\$

\$\endgroup\$
  • 3
    \$\begingroup\$ Can you include example usage? :) \$\endgroup\$ – Denis Jun 22 '17 at 18:45
  • \$\begingroup\$ @Denis Of course, sorry for being late, but took a while to figure out, how to draw a tree structure. \$\endgroup\$ – Horváth Dávid Jun 22 '17 at 19:29
  • \$\begingroup\$ A google search showed that the derivative of x^2 is equal to 2x am I missing something here? \$\endgroup\$ – Denis Jun 22 '17 at 20:25
  • \$\begingroup\$ @Denis It's equal to 2x, but the output of my method is a bit complicated. Additionally, on the last line, I show, that it's equal to 2x. \$\endgroup\$ – Horváth Dávid Jun 22 '17 at 20:29
  • \$\begingroup\$ This is a great project, would like to see a GitHub repo, very nice! \$\endgroup\$ – Rusty Nail Jan 24 '18 at 21:51
8
\$\begingroup\$

It might be just me but it took me a minute, until I realized you're not using expression trees but your own class with the same name (Expression).. That's confusing, don't use names that are already in the .NET framework.

Here is a summary of some of the problems I noticed in your code:

  • Using mutable objects in GetHashCode().
  • Virtual calls in the constructor.
  • Throwing generic Exception rather than more concrete one.
  • You've violated the Open/closed principle.
  • You might want to use more LINQ to make the code more readable.

Here is what you can do to fix those problems:

Using mutable objects in GetHashCode()

Guideline: the integer returned by GetHashCode should never change.

Rule: the integer returned by GetHashCode must never change while the object is contained in a data structure that depends on the hash code remaining stable

Quoted from Eric Lippert's blog.

The way to fix it is to simply make your properties readonly or in C#6 + get only.

Virtual calls in the constructor

In your case that wont cause any problems as far as I can tell, but in general it's tricky and it can cause some weird behavior.

This is because if you were to give value to ArgumentNumber in your derived class constructor and you're also operating on that property in your base class constructor (as you're), you would always get a value of 0 because your base constructor will be invoked before your derived one.

Of course if you know what you're doing and you're sure it wont cause any trouble, you can just leave it there.

Throwing generic Exception

You should never throw Exception, you should use that type to implement your own exception for example. If you need to throw an exception, use a more concrete type e.g:

if (ArgumentNumber != 0)
{
    throw new Exception("Wrong number of arguments");
}
if (ArgumentNumber != 0)
{
    throw new ArgumentOutOfRangeException("Wrong number of arguments");
}

Open/closed principle

Quote from Wikipedia :

In object-oriented programming, the open/closed principle states "software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification".

You're violating this principle with your switch case, if you add new type, you must go there and everywhere else where you're checking all the types manually, and update it if needed.

A simple solution would be to introduce a common interface, which would have a method that all the derived class would have to implement, for example the Add class would have the AddDerivative method inside of it, once you've done this for all of the classes, you can easily return the method that the Root is holding.

Now if you decide to add new type, you would implement the method in the class and it will still work, where your switch case would've required some modification.

LINQ

There are only few loops in your code, which luckily you can replace with more readable LINQ expression:

You can convert this whole chunk of code to a single line:

Expression[] arguments;
if (root.Children != null)
{
    arguments = new Expression[root.Children.Length];
    for (var i = 0; i < root.Children.Length; i++)
    {
        arguments[i] = new Expression(root.Children[i]);
    }
}
else
{
    arguments = null;
}

Like this:

var arguments = root.Children?.Select(t => new NodeExpression(t)).ToArray();

Also your Equals method:

var equals = true;
for (int i = 0; i < Children.Length; i++)
{
    if (!Children[i].Equals(((Node)obj).Children[i]))
    {
        equals = false;
    }
}
return equals;

Can become:

return !Children.Where((t, i) => !t.Equals(((Node) obj).Children[i])).Any();

I think the main problem in your code is that it has a God class - Derivative. If you separate all the methods into they're respective classes and add a common interface to replace the switch case, it should look a lot better.

\$\endgroup\$
  • \$\begingroup\$ Would it be sufficient, if I added an abstract method(Derivative) to the Node class, so all of its child classes will have to implement a method, that calculates the derivative? \$\endgroup\$ – Horváth Dávid Jun 22 '17 at 21:41
  • \$\begingroup\$ @HorváthDávid Yes it should be good enough, as you already have some stuff that cant be put in an interface. You can have both too and implement only some stuff in the abstract class and rest you leave up to the derived classes. \$\endgroup\$ – Denis Jun 22 '17 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.