Kerflyn's Blog

Well… It's a blog!

Towards Pattern Matching in Java

with 8 comments

Pattern matching is such a cool feature that you always dream of in your language to represent alternative structures. It already exists in OCaml, in Haskell, or in Scala (here is an post in this blog showing the different usages of the pattern matching in Scala: Playing with Scala’s pattern matching). In Java, what is almost closed to pattern matching is named switch-case. But, you’re limited to scalar values (chars, integer types, booleans), enum types, and since Java 7 you can use strings. With the Java’s switch-case, you don’t have a way to check the type of arguments or to really mix the different kind of check, for example. These are features that pattern matching provides.

In this post, we’ll study a possibility to get an implementation in Java close to pattern matching. We’ll use lambda expressions of Java 8 in a view to get a more readable structure. Here, I don’t propose to make a real pattern matching, but to get a structure that can match different kinds of patterns and which is more flexible than the traditional switch-case.

Main implementation

First, we need a PatternMatching class. This class is a set of Pattern instances. Each Pattern can check if a value matches (a pattern) and is bound to a process/function that it can apply on.

The class PatternMatching provides just the method matchFor. This method tests the different Pattern instances that it contains to a value. If a Pattern matches, the method matchFor is applied to the value the function bound to the Pattern. If no pattern has been found, the method throws an exception.

To instantiate this class, you’ll need to provide a set of patterns.

public class PatternMatching {
    private Pattern[] patterns;

    public PatternMatching(Pattern... patterns) { this.patterns = patterns; }

    public Object matchFor(Object value) {
        for (Pattern pattern : patterns)
            if (pattern.matches(value))
                return pattern.apply(value);

        throw new IllegalArgumentException("cannot match " + value);
    }
}

Pattern

Pattern is an interface that provides two methods. matches should check if an object meets some requirements. apply should execute a process on a object. apply should be called once matches succeeded.

public interface Pattern {
    boolean matches(Object value);
    Object apply(Object value);
}

A first Pattern example: pattern for types

For example, ClassPattern is a Pattern implementation that checks the type of a value.

public class ClassPattern<T> implements Pattern {

    private Class<T> clazz;

    private Function<T, Object> function;

    public ClassPattern(Class<T> clazz, Function<T, Object> function) {
        this.clazz = clazz;
        this.function = function;
    }

    public boolean matches(Object value) {
        return clazz.isInstance(value);
    }

    public Object apply(Object value) {
        return function.apply((T) value);
    }

    public static <T> Pattern inCaseOf(Class<T> clazz, Function<T, Object> function) {
        return new ClassPattern<T>(clazz, function);
    }
}

Take a look at the example below:

PatternMatching pm = new PatternMatching(
    inCaseOf(Integer.class, x -> "Integer: " + x),
    inCaseOf(Double.class, x -> "Double: " + x)
);

System.out.println(pm.matchFor(42));
System.out.println(pm.matchFor(1.42));

This code displays:

Integer: 42
Double: 1.42

Usual patterns

Here are some “usual patterns”, in the sense that they imitate some functionality you already have with switch-case. First, we start with the pattern to match strings:

public class StringPattern implements Pattern {
    private final String pattern;
    private final Function<String, Object> function;

    public StringPattern(String pattern, Function<String, Object> function) {
        this.pattern = pattern;
        this.function = function;
    }

    @Override
    public boolean matches(Object value) { return pattern.equals(value); }

    @Override
    public Object apply(Object value) { return function.apply((String) value); }

    public static Pattern inCaseOf(String pattern, Function<String, Object> function) {
        return new StringPattern(pattern, function);
    }
}

Now, here is a pattern to match integers:

public class IntegerPattern implements Pattern {
    private final Integer pattern;
    private final Function<Integer, Object> function;

    public IntegerPattern(int pattern, Function<Integer, Object> function) {
        this.pattern = pattern;
        this.function = function;
    }

    @Override
    public boolean matches(Object value) { return pattern.equals(value); }

    @Override
    public Object apply(Object value) { return function.apply((Integer) value); }

    public static Pattern inCaseOf(int pattern, Function<Integer, Object> function) {
        return new IntegerPattern(pattern, function);
    }
}

And to finish, here is a pattern that matches everything. It is the equivalent of default in switch-case.

public class OtherwisePattern implements Pattern {
    private final Function<Object, Object> function;

    public OtherwisePattern(Function<Object, Object> function) {
        this.function = function;
    }

    @Override
    public boolean matches(Object value) { return true; }

    @Override
    public Object apply(Object value) { return function.apply(value); }

    public static Pattern otherwise(Function<Object, Object> function) {
        return new OtherwisePattern(function);
    }
}

Now, you can express something like this:

PatternMatching pm = new PatternMatching(
    inCaseOf(Integer.class, x -> "Integer: " + x),
    inCaseOf(      "world", x -> "Hello " + x),
    inCaseOf(           42, _ -> "forty-two"),
    otherwise(              x -> "got this object: " + x.toString())
);

Factorial based on PatternMatching

Our pattern matching API in Java 8 can define the body of recursive functions:

public static int fact(int n) {
    return ((Integer) new PatternMatching(
            inCaseOf(0, _ -> 1),
            otherwise(  _ -> n * fact(n - 1))
    ).matchFor(n));
}

Here, we use the lambda expressions to improve the readability. In this case, Java 8 is necessary. But it is easy to use the implementations of PatternMatching and Pattern above with former versions of Java. Nevertheless, you have to sacrify the readability.

For example, here is the implementation of the same factorial function for versions 6 and 7 of Java:

public static int fact_old(final int n) {
    return ((Integer) new PatternMatching(
            inCaseOf(0, new Function<Integer, Object>() {
                @Override
                public Object apply(Integer _) {
                    return 1;
                }
            }),
            otherwise(new Function<Object, Object>() {
                @Override
                public Object apply(Object _) {
                    return n * fact(n - 1);
                }
            })
    ).matchFor(n));
}

Conclusion

In this post, we’ve seen a way to define a structure close to pattern matching. This structure helps us to extend the semantic of switch-case in Java. Besides, it’s extendable with new implementations based on Pattern. The use of the Java 8’s lambda expressions make it more readable.

Nevertheless, if a PatternMatching is defined in a method, it’ll be completely reinstantiated at each call of this method. But if performance is needed, you can store the pattern matching in a constant.

So, we are able to represent pretty much the same functionnality than switch-case. The usual patterns I haven’t presented can be easily implemented. In addition, we can find a way to do pattern matching based on regular expressions. What is missing here is the ability to aggregate a set of patterns to the same process (ie. a kind of OR relation between some patterns for the same process), the addition of guard condition and above all the ability to represent algebraic types and use them in our structure.

About these ads

Written by fsarradin

2012/05/09 at 22:39

8 Responses

Subscribe to comments with RSS.

  1. I like your proposal, and Java 8 makes it easily readable!

    I would suggest a slight improvement though: we can add a type parameter to Pattern and PatternMatching (and to whole class hierachy down from here), that way it is now mandatory for every case to return the same type, and the factorial function can be rewritten like so:

    public static int fact(int n) {
    return new PatternMatching(
    inCaseOf(0, _ -> 1),
    otherwise( _ -> n * fact(n – 1))
    ).matchFor(n);
    }

    // Java 7
    public static int fact_old(final int n) {
    return new PatternMatching(
    inCaseOf(0, new Function() {
    @Override
    public Integer apply(Integer _) {
    return 1;
    }
    }),
    otherwise(new Function() {
    @Override
    public Integer apply(Object _) {
    return n * fact(n – 1);
    }
    })
    ).matchFor(n);
    }

    // for completeness
    public static interface Pattern {
    boolean matches(Object value);

    R apply(Object value);
    }

    public static class PatternMatching {
    private final Pattern[] patterns;

    public PatternMatching(final Pattern… patterns) {
    this.patterns = patterns;
    }

    public R matchFor(final Object value) {
    for (Pattern pattern : patterns) {
    if (pattern.matches(value)) {
    return pattern.apply(value);
    }
    }

    throw new IllegalArgumentException(“cannot match ” + value);
    }
    }

  2. Hmm, WordPress removed my types. Here is a new try with square brackets instead of angle ones:

    I like your proposal, and Java 8 makes it easily readable!

    I would suggest a slight improvement though: we can add a type parameter to Pattern and PatternMatching (and to whole class hierachy down from here), that way it is now mandatory for every case to return the same type, and the factorial function can be rewritten like so:

    public static int fact(int n) {
    return new PatternMatching(
    inCaseOf(0, _ -> 1),
    otherwise( _ -> n * fact(n – 1))
    ).matchFor(n);
    }

    // Java 7
    public static int fact_old(final int n) {
    return new PatternMatching(
    inCaseOf(0, new Function[Integer, Integer]() {
    @Override
    public Integer apply(Integer _) {
    return 1;
    }
    }),
    otherwise(new Function[Object, Integer]() {
    @Override
    public Integer apply(Object _) {
    return n * fact(n – 1);
    }
    })
    ).matchFor(n);
    }

    public static interface Pattern[R] {
    boolean matches(Object value);

    R apply(Object value);
    }

    public static class PatternMatching[R] {
    private final Pattern[R][] patterns;

    public PatternMatching(final Pattern[R]… patterns) {
    this.patterns = patterns;
    }

    public R matchFor(final Object value) {
    for (Pattern[R] pattern : patterns) {
    if (pattern.matches(value)) {
    return pattern.apply(value);
    }
    }

    throw new IllegalArgumentException(“cannot match ” + value);
    }
    }

  3. @NicolasDemengel: sorry for your code. I’ve tried to reformat internally… without success :( Next time, I suggest you provide a link to a gist!

    Otherwise, the suggestion in your comment is interesting.

    fsarradin

    2012/05/10 at 21:15

  4. You’re right, I should have created a gist. Here it is: https://gist.github.com/2658827

  5. For those who want another approach on pattern matching based on the Java language features only, there’s another article by Rúnar: http://apocalisp.wordpress.com/2009/08/21/structural-pattern-matching-in-java/

    fsarradin

    2012/05/13 at 17:58

  6. Have you ever stopped to wonder why OO languages do not have pattern matching? In general it is not needed, because dynamic dispatch (also known as message passing, virtual methods, etc) is used instead. Pattern matching tends to expose representations, making programs harder to maintain and evolved. I need to write an article titled “Instanceof considered harmful”…

    w7cook

    2012/05/13 at 18:51

    • @w7cook: thank for your comment. I’m totally agree with you.

      But, doesn’t the use of pure OO concepts imply that the overall architecture of your project respects those concepts? In most of the projects I’ve met in companies, this isn’t the case. Even the JDK is criticable in its non-application of OO concepts (java.util.Properties is one example). In those cases, it is hard to produce pure OO code. To gain in readability, to look at other concepts provided by the other paradigms is appealing. The solution I present is certainly far from perfect and not performant. But it delivers this readability. Nevertheless, I would be glad to read your post about the harmfulness of instanceof.

      fsarradin

      2012/05/15 at 22:52

      • You are absolutely right. Different solutions are appropriate for different problems. Not every problem is best solved with an OO style. However, if you are working in Java its important to understand its capabilities and limitations. In that light, having a lightweight approach to pattern matching is a great idea.

        w7cook

        2012/05/16 at 15:49


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 508 other followers

%d bloggers like this: