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.
I have read a great deal of discussion on the pattern matching PEPs and
less formal discussions. It is possible I have overlooked some post in all
of that, of course.
... OK, just saw Guido's "wait for new SC" comment, which I suppose applies
to this too :-).
One idea that I cannot recall seeing, but that seems to make sense to me
and fit with Python's feel is using a WORD to distinguish between a
variable value and a binding target. That is, instead of a special symbol
prefixing or suffixing a name, either to indicate it is or is not a binding
target. Of course, whether the extra word would be used for binding or for
NOT binding is a question still.
NOT_FOUND = 404
match http_code:
case 200:
print("OK document")
case value NOT_FOUND: # use the variable value
print("Document not found")
case OTHER_CODE: # bind this name
print("Other HTTP code", OTHER_CODE)
Of course, this would require a soft keyword, which is a disadvantage.
Going the other direction:
NOT_FOUND = 404
match http_code:
case 200:
print("OK document")
case NOT_FOUND: # use the variable value
print("Document not found")
case bind OTHER_CODE: # bind this name
print("Other HTTP code")
To me these read better than the punctuation characters. But I guess some
folks have suggested enlisting 'as', which is a word, of course.
--
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons. Intellectual property is
to the 21st century what the slave trade was to the 16th.
Hi everyone,
There has been much discussion on the syntax of pattern matching for
Python (in case you hadn't noticed ;)
Unfortunately the semantics seem to have been somewhat overlooked.
What pattern matching actually does seems at least as important as the
syntax.
I believe that a pattern matching implementation must have the following
properties:
* The semantics must be precisely defined.
* It must be implemented efficiently.
* Failed matches must not pollute the enclosing namespace.
* Objects should be able determine which patterns they match.
* It should be able to handle erroneous patterns, beyond just syntax errors.
PEP 634 and PEP 642 don't have *any* of these properties.
I've written up a document to specify a possible semantics of pattern
matching for Python that has the above properties, and includes reasons
why they are necessary.
https://github.com/markshannon/pattern-matching/blob/master/precise_semanti…
It's in the format of a PEP, but it isn't a complete PEP as it lacks
surface syntax.
Please, let me know what you think.
Cheers,
Mark.
Hi Tobias,
A couple of questions about the DLS 2020 paper.
1. Why do you use the term "validate" rather than "test" for the process
of selecting a match?
It seems to me, that this is a test, not a validation, as no exception
is raised if a case doesn't match.
2. Is the error in the ast matching example, an intentional
"simplification" or just an oversight?
The example:
```
def simplify(node):
match node:
case BinOp(Num(left), '+', Num(right)):
return Num(left + right)
case BinOp(left, '+' | '-', Num(0)):
return simplify(left)
case UnaryOp('-', UnaryOp('-', item)):
return simplify(item)
case _:
return node
```
is wrong.
The correct version is
```
def simplify(node):
match node:
case BinOp(Num(left), Add(), Num(right)):
return Num(left + right)
case BinOp(left, Add() | Sub(), Num(0)):
return simplify(left)
case UnaryOp(USub(), UnaryOp(USub(), item)):
return simplify(item)
case _:
return node
```
Cheers,
Mark.
Hi all,
Some days back Mark Shannon posted his view/proposal pattern matching on github.
While reading it I realised an intermediate step between matching and variable assignment might do away with part of the discussion.
I wrote it in an issue with the view/proposal (https://github.com/markshannon/pattern-matching/issues/1)
Thinking about it a bit longer, it really might be worth exploring the idea more, so let me repeat it here:
1. In a pattern the values to match are marked with a special symbol (‘$’, ‘!’ or ‘?’ seem candidates).
2. A matching case produces a tuple of matched values. The tuple may be nested to reflect the matched structure.
3. The tuple may be deconstructed according to the usual rules.
As an example:
example_value = Example("bar", Embedded(None, "foo"), 42, "baz")
match example_value:
case Example($, Embedded($, "foo"), 42, $) as t:
# t = ("bar”, (None, ), "baz”)
pass
case Example($, Embedded($, "foo"), 42, $) as pre, *rest:
# pre = "bar", rest = ((None, ), "baz”)
pass
alternatively:
match example_value:
case pre, *rest = t = Example($, Embedded($, "foo"), 42, $):
# pre = "bar", rest = ((None, ), "baz”)
# t = ("bar”, (None, ), "baz”)
pass
Just my $0.02
—eric
Hi,
I'd like to request that any pattern matching PEP and its implementation
meet certain standards before acceptance.
As one of the maintainers of the AST-to-bytecode part of the compiler
and the bytecode interpreter, I don't want to be in the situation where
we are forced to accept a sub-standard implementation because a PEP has
been accepted and the PEP authors are unable, or unwilling, to produce
an implementation that is of a sufficiently high standard.
Therefore, I would ask the steering committee to require the following
as a minimum before formal acceptance of any pattern matching PEP.
1. The semantics must be well defined.
2. There should be no global side-effects in the bytecode.
3. Each bytecode should perform a single, reasonably limited, operation.
4. There should be a clear path, using known compiler optimization
techniques to making it efficient, if it is not initially so.
1.
We want to be able to change the implementation.
The current (3.9+) compiler produces quite clean bytecode for
"try-finally" and "with" statements.
Earlier implementations of the compiler were simplistic and required
quite convoluted bytecodes in the interpreter.
We were able to make these improvements because the "try-finally" and
"with" statements are well specified, so we could reason about changes
to the implementation.
Should the old and new implementations have differed, it was possible to
refer to the language documentation to determine which was correct.
Without well defined semantics, the first implementation of pattern
matching becomes the de-facto semantics, with all of its corner cases.
Reasoning about changes becomes almost impossible.
2.
The implementation of PEP 634 can import "abc.collections" mid bytecode.
I don't look forward to the bug reports when the module can't be
imported for some unrelated reason and pattern matching fails.
We recently added the `LOAD_ASSERTION_ERROR` bytecode to ensure that
asserts work even after `del builtins.AssertionError`. We should
maintain this level of robustness.
3.
This comes down to reasoning about whether the compiler is correct, and
interpreter performance.
Admittedly, the current bytecodes don't always adhere to the above rule,
but they mostly do and I don't want the situation to deteriorate.
The implementation of PEP 634 includes a number of bytecodes that
implement their own mini-interpreters within. It is the job of the
compiler, not the interpreter, to handle such control flow.
4.
If pattern matching is added to the language, and it becomes popular, we
don't want it to be slow. Knowing that there exists an efficient
implementation, and how to achieve it, is important. Ideally the initial
implementation should be efficient, but knowing that it could be is
sufficient for acceptance.
Cheers,
Mark.
Hi folks,
I know this is a high-volume list so sorry for being yet another voice
screaming into your mailbox, but I do not know how else to handle this.
A few months ago, I opened a pull request fixing packed bitfields in
ctypes struct/union, which right now are being incorrectly created. The
offsets and size are all wrong in some cases, fields which should be
packed end up with padding between them.
bpo: https://bugs.python.org/issue29753
PR: https://github.com/python/cpython/pull/19850
Since ctypes has no maintainer it has been very hard tracking down
someone who is up to review this. So, if this issue sparks some
interest to you, or you just want to help me out, please have a look :)
Cheers,
Filipe Laíns
Hi folks,
This is a mailing list repost of the Discourse thread at
https://discuss.python.org/t/pep-642-constraint-pattern-syntax-for-structur…
The rendered version of the PEP can be found here:
https://www.python.org/dev/peps/pep-0642/
The full text is also quoted in the Discourse thread.
The remainder of this email is the same introduction that I posted on Discourse.
I’m largely a fan of the Structural Pattern Matching proposal in PEP
634, but there’s one specific piece of the syntax proposal that I
strongly dislike: the idea of basing the distinction between capture
patterns and value patterns purely on whether they use a simple name
or a dotted name.
Thus PEP 642, which retains most of PEP 634 unchanged, but adjusts
value checks to use an explicit prefix syntax (either `?EXPR` for
equality constraints, or `?is EXPR` for identity constraints), rather
than relying on users learning that literals and attribute lookups in
a capture pattern mean a value lookup check, while simple names mean a
capture pattern (unlike both normal expressions, where all three mean
a value lookup, and assignment targets, where both simple and dotted
names bind a new reference).
The PEP itself has a lot of words explaining why I’ve made the design
decisions I have, as well as the immediate and potential future
benefits offered by using an explicit prefix syntax for value
constraints, but the super short form goes like this:
* if you don’t like match statements at all, or wish we were working
on designing a C-style switch statement instead, then PEP 642 isn’t
going to appeal to you any more than PEP 634 does
* if, like me, you don’t like the idea of breaking the existing
property of Python that caching the result of a value lookup
subexpression in a local variable and then using that variable in
place of the original subexpression should “just work”, then PEP 642’s
explicit constraint prefix syntax may be more to your liking
* however, if the idea of the `?` symbol becoming part of Python’s
syntax doesn’t appeal to you, then you may consider any improved
clarity of intent that PEP 642 might offer to not be worth that cost
Cheers,
Nick.
--
Nick Coghlan | ncoghlan(a)gmail.com | Brisbane, Australia
Hello,
I'm not a Python contributor but I have a question which (I believe) can be
answered here, so I've subscribed.
The question is at stackoverflow:
https://stackoverflow.com/questions/64912716/are-pre-commit-hooks-clonable
After some research the only thing similtar to a git pre-commit hook I
could find on the cpython repo was the patchcheck.py script on
github.com/python/cpython/tree/master/Tools/scripts (patchcheck.py), which
runs in Travis.
Is this the pre-commit hook PEP8 talks about ?
Thanks for your help and attention.
--
*Nilo César Teixeira*
nilo.teixeira(a)gmail.com
(55) (11) 98571-5314
