• Implementing Complex Case Analysis

    Published by on September 26th, 2011 12:26 am under Uncategorized

    No Comments

    The problem

    Every language has some way of implementing case analysis, such as the if-then-else construct, or some kind of switch or case statement. These work well for simple cases, but the code becomes unmanageable if the cases are too complex. If our cases are based on the type of an object, we can implement the code with a polymorphic method in that type hierarchy, or we can use a visitor. But what can we do when the cases aren’t based on the type of the object we are working with, but on an arbitrary set of rules?

    The solution

    We can view each case as a specialization of the main problem that works only for certain inputs. Each case can solve the problem, but only if the input of the problem falls within that case. So we’ll create a polymorphic hierarchy with the different cases we have. Each case/subclass will implement its condition as a static method, and any additional polymorphic methods required to solve the problem once we know which case to use. To solve the problem, we’ll iterate each subclass searching for the single one for which the method IsCaseFor: input returns true. Once we know which case to use, the polymorphic methods will handle the rest.

    Class Diagram implementing the solution by case analysis to a generic Problem

    image

    Implementing the logic to find the current case

    The logic performed to find the case for an input is the same for every problem. We can implement this logic once, and reuse it every time we need it. In the sample project there is a C# implementation of this component for an input of a single parameter called ClassForCaseFinder. The syntax to use it is:

    To create a new instance of the ClassForCaseFinder:

    problemCaseFinder = ClassForCaseFinder<IProblemClass, Input>.Builder.New()
        .SubclassesOf(typeof(Problem))
        .TestingWith((subclass, input) => subclass.IsCaseFor(input))
        .Build();
    

    Explanation:

    • The method .SubclassesOf(typeof(Problem)) tells the builder that the available cases are the subclasses of class Problem .
    • The method .TestingWith((subclass, input) => subclass.IsCaseFor(input)) tells the builder to find the case by calling the IsCaseFor method for each case/subclass.
    • The generic parameter IProblemClass is an interface containing the static methods we’ll use from the cases/subclasses (Generally the interface will contain the methods IsCaseFor(value) and PolymorphicMethod(value)). See the Implementation details in C#: Polymorphic Static-Methods section for the rational of why this is needed.
    • The generic argument Input is the class of the object we’ll use to decide which case to use.
    • We use a builder to simplify the creation of the ClassForCaseFinder because there are many advanced options we might want to use. Some of this options are discussed in the Handling non-exclusive conditions section.

     

    To find the case for an input, and then execute that case:

    result = problemCaseFinder.FindFor(input).PolymorphicMethod(input);
    

    Explanation:

    • .FindFor returns the case/subclass that should be used for input.
    • .PolymorphicMethod is a user defined method that solves the problem once we know which case to use.

    An example

    This is an example in C# of how we can use the ClassForCaseFinder to implement calculating the derivative of a function expressed as a LINQ Expression. e.g.: x => 3.0 * Math.Pow(x, 2.0) + 2.0 * x + 5.0 to x => 6.0 * x + 2.0 and x => Math.Sin(x) * x to x => x * Math.Cos(x) + Math.Sin(x).

    The implementation contains the following rules:

    • The Leibniz rule: (f(x) g(x))’ = f'(x) g(x) + f(x) g'(x).
    • The chain rule: (f(g(x)))’ = f'(g(x)) g'(x).
    • The linearity rule: (f(x) + g(x))’ = f'(x) + g'(x).
    • The constant rule: c’ = 0 for any number c.
    • The linear function rule: x’= 1.
    • Derivatives of trigonometric functions: (sin(x))’ = cos(x) and (cos(x))’ = -sin(x)
    • The Elementary power rule: (xn)’ = nxn-1 for n natural number

    The classes implementing the solution are:

    image

    The IDerivativeClass interface contains the static methods each case/subclass of Derivative has to implement:

    public interface IDerivativeClass
    {
        bool CanDerivate(Expression anExpression); // Used to test if this is the case for the input
    
        Derivative Of(Expression anExpression);    // Creates an instance of this case to calculate the
                                                   // derivative of the expression
    }
    

    The ClassForCaseFinder is stored as a static variable of class Derivative:

    private static readonly ClassForCaseFinder<IDerivativeClass, Expression> DerivateSubclassFinder =
        ClassForCaseFinder<IDerivativeClass, Expression>.Builder.New()
            .SubclassesOf(typeof(Derivative))
            .TestingWith((subclass, expression) => subclass.CanDerivate(expression))
            .Build();
    

    The ClassForCaseFinder will test each subclass by calling the .CanDerivate method.

    The ClassForCaseFinder is used from the Derivate method:

    public static Expression Derivate(Expression anExpression)
    {
        return DerivateSubclassFinder.FindFor(anExpression).Of(anExpression).Result();
    }
    

    This methods find the case to use for the expression, and then creates an instance of the case to find the derivative of the expression.

    Multiple satisfied conditions

    As defining conditions for complex case analysis can be an error-prone task, ClassForCaseFinder implementation evaluates the condition of every case/subclass for each input, and makes sure that just a single one is satisfied. This is an additional advantage over writing complex “if or case statements”, as this behavior helps to detect invalid or incomplete conditions in the cases.

    Non-exclusive and default conditions

    The problem of calculating the derivate of a LINQ expression is quite simple, but we often have complex problems where cases aren’t fully exclusive between each other, or we need to have a default case when no other case applies. Specifying exclusive conditions for the cases that cover every possible input can sometimes be difficult, and cumbersome.

    Handling non-exclusive conditions

    We don’t need to supply non-exclusive conditions for the cases, we just need a way to choose which case to use when more than one case applies. We can have an additional step to be performed if we found multiple cases for the input, or none at all. If we find multiple cases that are valid for a certain input, we need to supply some way of determining which case to use, such as a preference relationship between cases. If we find no suitable case for the input, we need to specify a default case to use. The following code shows how this can be specified with the sample implementation of the ClassForCaseFinder component.

    problemCaseFinder = ClassForCaseFinder<IProblemClass, Input>.Builder.New()
        .SubclassesOf(typeof(Problem))
        .TestingWith((subclass, input) => subclass.IsCaseFor(input))
        .TestingPreferenceWith((left, right) => left.HasPreferenceOver(right))
        .IfNoValidOptionReturn(typeof(DefaultCase))
        .Build();
    

    Explanation:

    • The method .TestingPreferenceWith((left, right) => left.HasPreferenceOver(right)) tells the builder that if multiple cases are found for the input, it has to search for one with preference over the others by calling the method left.HasPreferenceOver(right) on each pair of suitable cases for that input.
    • The method .IfNoValidOptionReturn(typeof(DefaultCase))tells the builder to use the case DefaultCase when no suitable case for an input is found.
    • If multiple cases apply, an none is found with preference over all the other cases that apply, a CouldntFindPreferred exception will be thrown.

    A more complex example

    This examples uses ClassForCaseFinder to implement simplifying and normalizing functions expressed as LINQ Expressions (simplifying and normalizing functions expressions is useful to ensure there is just a single possible representation for each expression, so we can compare them term by term). e.g.: x => 2.0 * 3.0 * Math.Pow(x, 1.0) + 2.0 * 1.0 to x => 6.0 * x + 2.0 and x => Math.Sin(x) * 1.0 + x * Math.Cos(x) + 0.0 to x => x * Math.Cos(x) + Math.Sin(x).

    The implementation contains the following rules:

    • Adding Zero rule: f(x) + 0 = f(x).
    • Constant Expression rule: e.g.: 8 + 20 *5 = 108.
    • Multiplying by One rule: f(x) * 1 = f(x).
    • Multiplying by Zero rule: f(x) * 0 = 0.
    • One exponent rule: f(x)1 = f(x).
    • Order commutative operations rule: e.g.: sin(x) + x * 20 = 20 * x + sin(x)

    For some expressions several cases apply e.g.: The expression 1.0 * 0.0 satisfies the condition of the cases Multiplying by One rule, Multiplying by Zero rule, Constant Expression rule and Order commutative operations rule. Other expressions such as Math.Pow(x, 2.0) have no cases at all (It can’t be simplified).

    The classes implementing the solution are:

    image

    The IExpressionSimplificationStepClass interface contains the static methods each case/subclass of ExpressionSimplificationStep has to implement:

    public interface IExpressionSimplificationStepClass : _Type
    {
        bool CanSimplify(Expression anExpression);
        ExpressionSimplificationStep Of(Expression anExpression);
        bool HasPreferenceOver(IExpressionSimplificationStepClass anExpressionSimplificationStepClass);
    }
    

    The ClassForCaseFinder is stored as a static variable of class ExpressionSimplificationStep:

    private static readonly ExpressionSimplificationCaseFinder ExpressionSimplificationSubclassFinder =
        ExpressionSimplificationCaseFinder.Builder.New()
            .SubclassesOf(typeof(ExpressionSimplificationStep))
            .TestingWith((subclass, expression) => subclass.CanSimplify(expression))
            .TestingPreferenceWith((left, right) => left.HasPreferenceOver(right))
            .IfNoValidOptionReturn(typeof(NoSimplification))
            .Build();
    

    The ClassForCaseFinder will test each subclass calling the .CanSimplify method. If no subclass can simplify the expression, then the NoSimplification subclass will be used. If more than one subclass can simplify the expression, then a subclass with preference over all the other possible subclasses for this input will be searched by calling .HasPreferenceOver on each pair. If a single subclass that can handle the input has preference over all the others, then that subclass will be used. If either none or many subclasses have preference over all the others then an exception will be thrown.

    The ClassForCaseFinder is called from the .Of method:

    public static ExpressionSimplificationStep Of(Expression anExpression)
    {
        return ExpressionSimplificationSubclassFinder.FindFor(anExpression).Of(anExpression);
    }
    

    This methods find the case to use for the expression, and then creates an instance of the case to find the normalized version of the expression.

    Implementation details in C#

    Polymorphic Static-Methods

    To select the correct case/subclass for an input, we need to have a collection of types, and call a static-side polymorphic method on each one of them. C# doesn’t have Metaclasses, so to implement this I use Castle.DynamicProxy to create a proxy for each subclass, that forwards the selected methods to their static methods. The generic argument IProblemClass of the ClassForCaseFinder is the interface that the proxy for each subclass will implement.

    Generic Types Cases

    Sometimes we need to create a case analysis with a generic type such as Problem<Parameter> with cases being Case1<Parameter>, Case2<Parameter>, etc…. As the cases are generic types, they aren’t included in any assembly, so they can’t be found by the ClassForCaseFinder using the traditional approach. The ClassForCaseFinder handles this case by searching for the generic types definitions that subclass Problem<> and share their parameters, and then instantiates the generic types definitions with the generic argument supplied to the Problem class.

    Sample Source Code

    The soure code can be downloaded from here

    You’ll need to download the Castle.Core component and put Castle.Core.dll in the solution directory, as the solution uses Castle.DynamicProxy.