Mailman 3 Advantages of pattern matching - a simple comparative analysis - Python-Dev

23 Nov 2020

      Take as an example a function designed to process a tree of nodes similar to that which might be output by a JSON parser. There are 4 types of node:

- A node representing JSON strings
- A node representing JSON numbers
- A node representing JSON arrays
- A node representing JSON dictionaries

The function transforms a tree of nodes, beginning at the root node, and proceeding recursively through each child node in turn. The result is a Python object, with the following transformation applied to each node type:

- A JSON string `->` Python `str`
- A JSON number `->` Python `float`
- A JSON array `->` Python `list`
- A JSON dictionary `->` Python `dict`

I have implemented this function using 3 different approaches:

- The visitor pattern
- `isinstance` checks against the node type
- Pattern matching

Here is the implementation using the visitor pattern:

```
from typing import List, Tuple

class NodeVisitor:
    def visit_string_node(self, node: StringNode):
        pass

    def visit_number_node(self, node: NumberNode):
        pass

    def visit_list_node(self, node: ListNode):
        pass

    def visit_dict_node(self, node: DictNode):
        pass

class Node:
    def visit(visitor: NodeVisitor):
        raise NotImplementedError()

class StringNode(Node):
    value: str

    def visit(self, visitor: NodeVisitor):
        visitor.visit_string_node(self)

class NumberNode(Node):
    value: str

    def visit(self, visitor: NodeVisitor):
        visitor.visit_number_node(self)

class ListNode(Node):
    children: List[Node]

    def visit(self, visitor: NodeVisitor):
        visitor.visit_list_node(self)

class DictNode(Node):
    children: List[Tuple[str, Node]]

    def visit(self, visitor: NodeVisitor):
        visitor.visit_dict_node(self)

class Processor(NodeVisitor):
    def process(root_node: Node):
        return root_node.visit(self)

    def visit_string_node(self, node: StringNode):
        return node.value

    def visit_number_node(self, node: NumberNode):
        return float(node.value)

    def visit_list_node(self, node: ListNode):
        return [child_node.visit(self) for child_node in node.children]

    def visit_dict_node(self, node: DictNode):
        return {key: child_node.visit(self) for key, child_node in node.children}

def process(root_node: Node):
    processor = Processor()
    return processor.process(root_node)
```

Here is the implementation using `isinstance` checks against the node type:

```
from typing import List, Tuple

class Node:
    pass

class StringNode(Node):
    value: str

class NumberNode(Node):
    value: str

class ListNode(Node):
    children: List[Node]

class DictNode(Node):
    children: List[Tuple[str, Node]]

def process(root_node: Node):
    def process_node(node: Node):
        if isinstance(node, StringNode):
            return node.value
        elif isinstance(node, NumberNode):
            return float(node.value)
        elif isinstance(node, ListNode):
            return [process_node(child_node) for child_node in node.children]
        elif isinstance(node, DictNode):
            return {key: process_node(child_node) for key, child_node in node.children}
        else:
            raise Exception('Unexpected node')

    return process_node(root_node)
```

Finally here is the implementation using pattern matching:

```
from typing import List, Tuple

class Node:
    pass

class StringNode(Node):
    value: str

class NumberNode(Node):
    value: str

class ListNode(Node):
    children: List[Node]

class DictNode(Node):
    children: List[Tuple[str, Node]]

def process(root_node: Node):
    def process_node(node: Node):
        match node:
            case StringNode(value=str_value):
                return str_value
            case NumberNode(value=number_value):
                return float(number_value)
            case ListNode(children=child_nodes):
                return [process_node(child_node) for child_node in child_nodes]
            case DictNode(children=child_nodes):
                return {key: process_node(child_node) for key, child_node in child_nodes}
            case _:
                raise Exception('Unexpected node')

    return process_node(root_node)
```

Here are the lengths of the different implementations:

- Pattern matching `->` 37 lines
- `isinstance` checks `->` 36 lines
- The visitor pattern `->` 69 lines

The visitor pattern implementation is by far the most verbose solution, weighing in at almost twice the length of the alternative implementations due to the large amount of boilerplate that is necessary to achieve double dispatch. The pattern matching and `isinstance` check implementations are very similar in length for this trivial example.

In each implementation, there are 2 operations performed on each node.

- Determine the type of the node
- Destructure the node to extract the desired data

The visitor pattern and `isinstance` check implementations separate these 2 operations, whereas the pattern matching approach combines the operations together. I believe that it is the declarative nature of pattern matching, where the operations of determining the type of the node and destructuring the node are combined into a single clause, which allows pattern matching to express a concise solution to the problem. In this trivial example, the advantage of pattern matching over the alternative of using a sequence of `if`-`elif`-`else` statements is not as obvious as it would be when compared to a more complex example, where a sub-tree of nodes might be matched based on their type and be destructured in a single clause.

I have seen elsewhere an argument that pattern matching should not be accepted into Python as it introduces a pseudo-DSL that is separate from the rest of the language. I agree that pattern matching might be viewed as a pseudo-DSL, but I believe that it is a good thing, if it allows the solution to certain classes of problems to be expressed in a concise manner. People often raise similar objections to operator overloading in other languages, whereas the presence of operator overloading in Python allows mathematical expressions involving custom numeric types such as vectors to be expressed in a natural way. Furthermore, Python has a regular expression module which implements it's own DSL for the purpose of matching string patterns. Regular expressions, in a similar way to pattern matching, allow string patterns to be expressed in a concise and declarative manner.

I really hope that the Steering Council accepts pattern matching into Python. I think that it allows for processing of heterogeneous graphs of objects using recursion in a concise, declarative manner. I would like to thank the authors of the Structural Pattern Matching PEP for their hard work in designing this feature and developing an implementation of it. I believe that it will be a wonderful addition to the language that I am very much looking forward to using.

Advantages of pattern matching - a simple comparative analysis

Brian Coleman

Larry Hastings

Ethan Furman

David Mertz

Chris Angelico

Ethan Furman

Brian Coleman

David Mertz

Brian Coleman

David Mertz

Brian Coleman

Brian Coleman

Eric V. Smith

David Mertz

Ethan Furman

Eric V. Smith

David Mertz

Eric V. Smith

Mark Shannon

Steven D'Aprano

Greg Ewing

Antoine Pitrou

Brian Coleman

Greg Ewing

Chris Barker

Antoine Pitrou

tags

participants (12)