Deriving Miss Daisy

As I've mentioned previously, I'm slowly reading through SICP - it's an amazing book and reading it has been a humbling experience.

'Geeking' Out

I completely geeked out reading one example on functional derivatives.  (Take a math expression as a parameter and return the derivative as an expression)

It's in the first chapter, and they use this to implement Newton's Method -> to then implement a Sqrt function!

Approximate Derivative

After I picked my brain off the floor, I decided to have a crack at implementing derivatives in C# using lambda expressions:



Using the formula of a derivative (above), we can simply code an approximate derivative (below):

Func<double, double> Approximate(Func<double, double> f)
{
    var h = 0.0001;
    return a => ((f(a + h) - f(a)) / h);
}

Symbolic Derivation

Easy huh!  So for fun I decided to use linq expression trees to derive algebraically.

It's easy to get an expression tree in C# - simply use the Expression<> type.

Func<double, double> Derive(Expression<Func<double, double>> e)
{
    var lambda = new Derivative().Eval(e) as LambdaExpression;
    return (Func<double, double>) lambda.Compile();
}

I parse the expression tree using Matt Warren's ExpressionVisitor class - and using the basic rules of Derivation (Constant, Product and Quotient rules) we get:

class Derivative : ExpressionVisitor
{
    public Expression Eval(Expression exp)
    {
        return this.Visit(Evaluator.PartialEval(exp));
    }
    
    protected override Expression VisitBinary(BinaryExpression b)
    {
        // Product Rule: (fg)' = f'g + fg' 
        if (b.NodeType == ExpressionType.Multiply)
        {
            return Expression.Add(
                Expression.Multiply(Eval(b.Left), b.Right),
                Expression.Multiply(b.Left, Eval(b.Right)));
        }
    
        // Quotient Rule: (f/g)' = (f'g - fg') / (g*g)
        if (b.NodeType == ExpressionType.Divide)
        {
            return Expression.Divide(
                Expression.Subtract(
                    Expression.Multiply(Eval(b.Left), b.Right),
                    Expression.Multiply(b.Left, Eval(b.Right))),
                Expression.Multiply(b.Right, b.Right));
        }
    
        return base.VisitBinary(b);
    }
    
    // Parameter Derivation: f(x)' = 1
    protected override Expression VisitParameter(ParameterExpression p)
    {
        return Expression.Constant(1.0);
    }
    
    // Constant Rule f(a)' = 0
    protected override Expression VisitConstant(ConstantExpression c)
    {
        return Expression.Constant(0.0);
    }
}

Wrapping it up

To quickly finish this long blog post, here's the usage code:

// f(x * x * x)' = 3 * x * x
var approx = Approximate(x => x * x * x);
var derive = Derive(x => x * x * x);
 
var y1 = approx(1); // 3.0000300001109532
var y2 = derive(1); // 3.0

And there it is!  Useful? maybe not.  Fun? Definitely!