Pattern matching for the Java programmer: part 1

A desirable property of code is to facilitate local reasoning, as programmers, we strive to write cohesive, loosely coupled code using mechanisms such as encapsulation for this purpose.

Functional programming promotes this property via its emphasis on avoiding side effects, expression-oriented programming, and referential transparency. Another mechanism that is employed is pattern matching. In this two-part series, I introduce this simple yet elegant mechanism that facilitates the writing of simple yet robust code.

The choice between specialization and generalization is prevalent in many aspects of life, and software development is not immune. In the following paragraph, I highlight the place for specialization in the control-flow space. Two of the control flow constructs in java are if/else and switch/case constructs

public String dayOftheWeek(int day){
    switch (day) {
        case 1:
            return ("Monday");
        case 2:
            return("Tuesday");
        case 3:
            return("Wednesday");
        case 4:
            return("Thursday");
        case 5:
            return("Friday");
        case 6:
            return("Saturday");
        case 7:
            return("Sunday");
        default:
              throw new IllegalArgumentException();
    }

}

Consider the code snippet shown above, its general-purpose, if-elseif-else code equivalent will be verbose, clumsy to read, has more duplication, brittle, and increases the chances of programmer errors.

Now consider the following code snippet. [while it is semantically correct doesn’t compile, because of the missing default block]. In an ideal world, the compiler would have complained if we had missed one of the cases.

enum Car {
    lamborghini,tata,audi,fiat,honda
}

public String toString(Car c){
    switch(c) {
        case lamborghini:
            return("You choose lamborghini!");
        case tata:
            return("You choose tata!");
        case audi:
            return("You choose audi!");
        case fiat:
            return("You choose fiat!");
        case honda:
            return("You choose honda!");
    };
}

while switch/case construct allows comparison of a value against a bunch of options, these checks are confined to equality. A natural extension of this idea is the match construct which can be summarised as below.

match VALUE { 
PATTERN => EXPRESSION,
PATTERN => EXPRESSION,
PATTERN => EXPRESSION
}

where a list of patterns is checked against the value and the expression corresponding to the first matching pattern is returned.

Consider the code snippet below, observe the terseness of this code compared to the switch statement.

public int fib(int n){
    Matcher1<Integer> matcher = Matcher.of(n);
    return matcher
            .when(eq(0), 1)
            .when(eq(1), 1)
            .orElse(m -> fib(m - 1) + fib(m - 2));
}

Find below the mathematical definition of the fibonacci numbers, observe how close its “code” version is. This kind of low representational gap allows programmers to faster understanding and better reasoning.

Let’s consider the code snippet people which provides string equivalent of Body Mass Indices. Here, the checks are for not equality but for less than or equal to. Observe the low representational gap here too. As an exercise write similar code using If/Else style, and compare the level of abstraction/reasoning.

public String message(Float bmi){
    Matcher1<Float> matcher = Matcher.of(bmi);
    return matcher.when(lte(18.5f), "underweight")
            .when(lte(25.0f), "normal")
            .when(lte(30.0f), "fat")
            .orElse("whale");

}

So far we have considered matching over one variable, this style can be employed across more variables. Here is a simple example of the same.

boolean longer(String string1, String string2) {
    Matcher2<String, String> matcher2 = Matcher.of(string1, string2);
    return matcher2
            .when((s1, __) -> s1.length() == 0, (__, s2) -> false)
            .when((__, s2) -> s2.length() == 0, (s1, __) -> true)
            .orElse((s1, s2) -> longer(s1.substring(1), s2.substring(1)));
}

The verbosity and representational gains are amplified when we employ this technique for harder problems such as the one below, where we check if a string matches a wildcard string.

static boolean matches(String wildCardExpression, String target) {

Matcher2<String, String> matcher2 = Matcher.of(wildCardExpression, target);
return matcher2
        .when((e, t) -> isEmpty(t) && isEmpty(e), true)
        .when((e, t) -> isEmpty(e), false)
        .when((e, t) -> isEmpty(t), true)
        .when((e, t) -> last(e) == last(t), (e, t) -> matches(removeLast(e), removeLast(t)))
        .when((e, t) -> last(e) == '?', (e, t) -> matches(removeLast(e), removeLast(t)))
        .when((e, t) -> last(e) == '*', (e, t) -> matches(removeLast(e), t) || matches(e, removeLast(t)))
        .orElse(false);

Note that the syntax of the constructs I have presented, especially the ones involving matching of two variables can be made even terse if they were to be implemented by Java Language itself.

Theory

Pattern matching facilitates thinking about the values, variables can have, reasoning, and mapping of these values. It provides the first-class status to what is traditionally considered edge cases.

More theory

Variables that programs access can be categorized into three buckets 1)free variables and 2)parameters and 3)local variables.

Pattern matching enables local reasoning as follows

within the match block, matched variables are parameters and predicates can be defined only on these parameters.

for e.g. string1 and string2 are the parameters of the match block, in the predicates such as (s1, __) -> s1.length() == 0 can be applied only to these. Note that expressions can span across all three buckets.

Source code for the constructs I have used can be found at the github repository.

NOTE: I had implemented my matcher constructs without the knowledge of a similar one from Vavr. Also, I have implemented a version in which pattern matches over pair of variables.