"Structural pattern matching" for Python, part 2 [LWN.net]

"Structural pattern matching" for Python, part 2

Posted Sep 4, 2020 11:31 UTC (Fri) by gray_-_wolf (subscriber, #131074)
Parent article: "Structural pattern matching" for Python, part 2

Given that the same variable in the match multiple times is illegal, how is one supposed to match things like Point with x == y?

I would have assume that

match p:
case (x, x):

would match points where p.x == p.y. However that does not seem to be the case. How can I express such a match?

Second question, if constants must be namespaced, is there no way to express something like:

x = 1
match p:
case (x, y):

For points that are `(1, .*)`? Is there something like `local` namespaces for local variables in python?

I'm not a python programmer, so I might be lacking some parts of the proper mindset, but it seems... limiting.

to post comments

"Structural pattern matching" for Python, part 2

Posted Sep 4, 2020 15:54 UTC (Fri) by ecree (guest, #95790) [Link] (18 responses)

Apparently the PEP authors decided to punt on what they call "algebraic matching" of repeated names.

IMNSHO, if this PEP isn't doing algebraic matching then it's really far from clear what it's for, and I'm tempted to side with those who say this creature is being feeped purely for the sake of feeping.

"Structural pattern matching" for Python, part 2

Posted Sep 6, 2020 11:35 UTC (Sun) by kleptog (subscriber, #1183) [Link] (17 responses)

An alternative to algebraic pattern matching is allowing extra conditional, like in elixir (which also offers algebraic matching). Then it could look like:

match size:
    case (x,y) if x == y:
        circle()
    case (x,y):
        ellipse()

The whole power of such a match statement is that you can match entire nested structures, which this PEP does offer. An optional extra if clause for the more fancy cases can help here.

"Structural pattern matching" for Python, part 2

Posted Sep 7, 2020 16:45 UTC (Mon) by ecree (guest, #95790) [Link] (8 responses)

On thinking more about this, I have a fairly fundamental question, which I didn't see raised anywhere:

Why can't this be done as a library? Why is a language feature needed?

Something like

    import matching

    # ...

    if m := matching.match(p, (matching.capture('x'), matching.capture('x')):
        print("Diagonal at %d" % (m.x,))
    elif m := matching.match(p, (0, matching.capture('y')):
        print("X-axis as %d" % (m.y,))
    elif m := matching.match(p, (matching.capture('x'), matching.capture('y')):
        print("Point at (%d,%d)" % (m.x, m.y))
    else:
        raise ValueError("Not a 2-tuple")
    return Point(*p)

Yes, it's more verbose than the 'match' statement, but mainly because of the length of names, and still much more concise and declarative than doing everything with isinstance() and len(). And it makes the difference between constants and capture variables totally explicit!

"Structural pattern matching" for Python, part 2

Posted Sep 8, 2020 7:21 UTC (Tue) by johill (subscriber, #25196) [Link] (7 responses)

You can probably use some more "magic" to make that shorter, something like

  from matching import match, capture

  with match(p) as matches:
    if m := matches((capture.x, capture.y)):
      print("Diagonal at %d" % (m.x, ))
    elif m := matches((0, capture.y)):
      print("X-axis at %d" % (m.y, ))
    elif m := matches((capture.x, capture.y)):
      print("Point at (%d, %d)" % (m.x, m.y))
    else:
      raise ValueError("Not a 2-tuple")
  return Point(*p)

You need something like

class CapturedVar:
  def __init__(self, name):
    self.name = name

class capture:
  def __getattr__(self, name):
    return CapturedVar(name)

and "match(...)" returns an object that is callable; the called method knows about CapturedVar instances and bumps those into the returned MatchedVars object ("m").

"Structural pattern matching" for Python, part 2

Posted Sep 8, 2020 7:29 UTC (Tue) by johill (subscriber, #25196) [Link] (6 responses)

And maybe CapturedVar() can be callable again, returning another CapturedVar() instance with a type attached, so you can write

  from matching import match, capture

  with match(p) as matches:
    if m := matches((capture.x(int), capture.y(int))):
      print("Diagonal at %d" % (m.x, ))
    elif m := matches((0, capture.y(int))):
      print("X-axis at %d" % (m.y, ))
    elif m := matches((capture.x(int), capture.y(int))):
      print("Point at (%d, %d)" % (m.x, m.y))
    elif m := matches((capture.x, capture.y)):
      raise ValueError("It's a tuple, but not with integers")
    else:
      raise ValueError("Not a 2-tuple")
  return Point(*p)

"Structural pattern matching" for Python, part 2

Posted Sep 8, 2020 7:34 UTC (Tue) by johill (subscriber, #25196) [Link] (5 responses)

Sorry, obviously in both cases the first if was meant to be

    if m := matches((capture.x(int), capture.x(int))):
      print("Diagonal at %d" % (m.x, ))

And that of course shows that the matches() call needs to be fairly smart about disentangling instances of CapturedVar() etc. But I believe it can be done.

"Structural pattern matching" for Python, part 2

Posted Sep 8, 2020 16:15 UTC (Tue) by ecree (guest, #95790) [Link] (4 responses)

> But I believe it can be done.

I agree. And that's a clever idea of yours to use a context manager to get the 'only mention p once' semantics.

"Structural pattern matching" for Python, part 2

Posted Sep 8, 2020 17:39 UTC (Tue) by johill (subscriber, #25196) [Link] (3 responses)

I also just realized that I sort of sketched the basics of "algebraic matching", where the original PEP completely bypassed that issue and (x, x) doesn't even do what seems obvious? Or am I reading that wrong?

Of course some more complex expressions would be ... hard. Probably not impossible, but hard. You'd have to make the CapturedVar() be able to track all kinds of things, if you wanted to be able to write

...
    if m := matches((capture.x(int), capture.x(int)**2)):
        print("Integer point on the parabola at %d" % m.x)
...

It still seems possible, but ... tricky to say the least. Effectively, "CapturedVar" would have to be able to be operated on in a symbolic fashion, always returning a new CapturedVar object that encapsulates the expression, and can later evaluate it. So given an instance

  x_square := CapturedVar('x') ** 2

you'd have to be able to calculate

x_square(7)

so you can compare to

capture.x(7)

But you can see the ambiguity here! I previously allowed

capture.x(int)

to indicate you wanted a specific type ...

This would be better if the types were to rely on type annotations, but I don't think you can do that in this fashion.

I suppose you could detect if the argument was a type or an instance or something? But tricky to differentiate ...

Oh, I have an idea. The

x_square(7)

calculation is purely internal, so we can do it as

x_square(value=y)

(say the signature is "__call__(self, type=None, value=None)" so you can differentiate more easily. The value passing syntax is only needed internally to evaluate when you have a given thing in hand.

Well, basically ... it get complex, but I haven't hit anything I couldn't do.

Now I'm tempted to actually implement it :-)

"Structural pattern matching" for Python, part 2

Posted Sep 8, 2020 18:33 UTC (Tue) by johill (subscriber, #25196) [Link] (2 responses)

But actually...

while all of that works nicely with tuples because you can build some knowledge of them into the code, it really doesn't work at all with what the PEP calls "Class Patterns".

You can't write "m := matches(Point(capture.x, capture.y))" because you quite probably cannot instantiate a Point() object with two CapturedVar instances.

so you'd have to rewrite that as something like "m := matches_instance(Point, capture.x, capture.y)" at which point (pun intended) new syntax seems to make sense...

"Structural pattern matching" for Python, part 2

Posted Sep 8, 2020 23:39 UTC (Tue) by ecree (guest, #95790) [Link] (1 responses)

because you quite probably cannot instantiate a Point() object with two CapturedVar instances.

But can't you, though?

As long as CapturedVar suitably 'ducks' its type (e.g. for ints, implementing + and **, like you suggested), Point.__init__ should be entirely happy with it unless it's trying to do things that depend on the actual values.

Sure, it's not something that will work for every class, but nor is the rest of the "Match Protocol" in PEP 622. And if the class has a __match_args__, then you could potentially have a matching.Duck that uses that to "play the rôle of" the class in a match expression:

from matching import match, capture, Duck

with match(p) as matches:
    if m := matches(Duck(Point)(capture.x(int), capture.x(int))):
        print("Diagonal at %d" % (m.x, ))
    elif m := matches(capture.p(Point)(capture.x(int), capture.y(int))):
        # the second call on capture.p implies a Duck
        # if the match succeeds, it is replaced with the concrete Point
        print("Other point at %s % (m.p, ))

So you'd use plain Point() for dataclasses and anything else that's not too fussy, Duck(Point)() otherwise.

Still not quite as pretty as the PEP 622 syntax, but it still seems like a good way to get experience with "how this feature would be used in practice" before baking it into the language. Which to my mind is reason enough to do it.

"Structural pattern matching" for Python, part 2

Posted Sep 9, 2020 6:22 UTC (Wed) by johill (subscriber, #25196) [Link]

> As long as CapturedVar suitably 'ducks' its type (e.g. for ints, implementing + and **, like you suggested), Point.__init__ should be entirely happy with it unless it's trying to do things that depend on the actual values.

I don't think that'll work. It has to implement the algebraic operations to build a parse tree to be able to do algebraic matching, but you still can't really call Point.__init__ with it I'd think, it might check the type, or other random things in there. Hence the match protocol though!

> Sure, it's not something that will work for every class, but nor is the rest of the "Match Protocol" in PEP 622. And if the class has a __match_args__, then you could potentially have a matching.Duck that uses that to "play the rôle of" the class in a match expression: [...]

But yeah, you're right, the PEP also cannot do magic wrt. class matching, it has __match_args__ for that, and indeed with something like the "Duck()" you propose - or what I wrote as "m := matches_instance(Point, capture.x, capture.y)" - you can indeed do the same thing.

I neglected to think enough about it I suppose, but (fairly obviously) the only magic in the PEP can be the syntax, making "Point(x, y)" not be an instantiation call but some other kind of expression. Without new syntax we have to open that up manually by doing "Duck(Point)(capture.x, capture.y)" or my "m := matches_instance(Point, capture.x, capture.y)".

The rest ... yeah can probably be done, now that I think about it. In mostly the same ways.

And that shows to some extent where and how the algebraic matching breaks down and probably why they punted on it, though I'm not convinced it's that bad. Obviously, you don't want to get into the territory of writing "Point(x**2, x**3)" and suddenly needing an arbitrary solver to do the match, but I think you could do it if you restrict to having to mention each variable "naked" at least once. I.e. "Point(x, x**3)" would be OK and "Point3d(x, y, x+y)" would also be OK - all of this because once you have values for x/y it's easy to check the remaining expressions. But something like "Point(x+y, x-y)" would not be allowed.

"Structural pattern matching" for Python, part 2

Posted Sep 9, 2020 13:37 UTC (Wed) by milesrout (guest, #126894) [Link] (7 responses)

At that point, how is this better than


(x, y) = size
if x == y:
    circle()
else:
    ellipse()

I would contend that it is not. It is an extra level of indentation and a whole new complicated language construct.

"Structural pattern matching" for Python, part 2

Posted Sep 9, 2020 22:16 UTC (Wed) by johill (subscriber, #25196) [Link] (6 responses)

Your version crashes if you pass it a 3-tuple or something else.

The match/case version can handle such things without you having to put another "is a 2-tuple" if outside of it.

"Structural pattern matching" for Python, part 2

Posted Sep 10, 2020 2:12 UTC (Thu) by milesrout (guest, #126894) [Link] (5 responses)

That's quite intentional. If you are passing the wrong type of value to a function then your code should crash. The code will also crash if I pass a string to a function that expects an integer. Code should not be full of defensive checks for programmer error: they're code paths that are hard if not impossible to test and by design are intended to never be run (nobody makes programmer errors on purpose). Type checks are for dispatching based on type in Python, and most of the time 'isinstance' checks are the wrong way of doing things. "if isinstance elif isinstance elif isinstance"-style code is considered unPythonic, and I don't think that papering over that code with a language construct makes it a good idea.

Now there are possibly some cases where you want to be able to pass different sizes of tuples to a single function. However I think in most of those cases you probably shouldn't be using tuples, you should be using something like a named tuple, a dictionary, a custom class, a dataclass with an optional field, or just separate arguments to a single function, some of which are optional.

Or possibly you should actually be making a decision 'am I working with 2-tuples or 3-tuples?' at a higher level and switch. If you had some code that is meant to work with 2D or 3D or 4D vectors for example, it would be better to have separate functions for the length of 2D, 3D and 4D vectors than a single function that does


    def veclen(v):
      match v:
        case (x,y): return sqrt(x*x + y*y)
        case (x,y,z): return sqrt(x*x + y*y + z*z)
        case (x,y,z,w): return sqrt(x*x + y*y + z*z + w*w)

Then you should make the determination as to whether you are working with 2D, 3D or 4D vectors at a high level and write all the functions dealing with 2D, 3D or 4D vectors separately.

For example if you really want to write 'length-agnostic' code with tuples up to some maximum length, then you should encapsulate that variation in size in Vector2D, Vector3D and Vector4D etc. classes with a common Vector superclass such that Vector's methods can be those that are parametric in the dimension.

And if it's really truly length-agnostic tuple code then you should be writing loops over lists, not matching on tuples.

"Structural pattern matching" for Python, part 2

Posted Sep 11, 2020 6:29 UTC (Fri) by johill (subscriber, #25196) [Link] (4 responses)

Well, that's a question of your architecture/design, but a large part of the whole point of the match statement was to be able to match different types in the same place.

"Structural pattern matching" for Python, part 2

Posted Sep 11, 2020 12:53 UTC (Fri) by milesrout (guest, #126894) [Link] (3 responses)

And what I am saying, quite clearly I think, is that I do not think that that is the right thing to be doing in Python code. It's not supported by the language *for good reason*.

"Structural pattern matching" for Python, part 2

Posted Sep 11, 2020 13:27 UTC (Fri) by mathstuf (subscriber, #69389) [Link] (2 responses)

> It's not supported by the language *for good reason*.

This feels like one of those "cannot derive ought from is" statements. Is there any indication that something better than `isinstance` if-trees was explicitly rejected earlier in the language's design process? I'd expect the previous approach was "just treat it like a duck and if it quacks well enough, what do you care?", but with types now becoming more and more of a thing in general (even in Python), this seems like a natural thing to be considering around this time (to me at least).

"Structural pattern matching" for Python, part 2

Posted Sep 12, 2020 4:30 UTC (Sat) by milesrout (guest, #126894) [Link] (1 responses)

>Is there any indication that something better than `isinstance` if-trees was explicitly rejected earlier in the language's design process?

Yes. Switch statement suggestions have been rejected over and over again. Pattern matching proposals have been rejected before. 'if isinstance' isn't considered bad Python because it's *ugly* but because it's *bad design*. Dispatching on types is just not a good way to write code in a dynamically typed language. There is no - and can be no - exhaustiveness checking for example, to give just one example of why it's a problem.

>but with types now becoming more and more of a thing in general (even in Python), this seems like a natural thing to be considering around this time (to me at least).

Adding type annotations to Python is yet another example of the continual application of bad ideas to clutter up Python, done by people trying to roleplay as Haskell programmers. Pattern matching is the same thing. It's blatant cargo culting.

"Structural pattern matching" for Python, part 2

Posted Sep 16, 2020 16:02 UTC (Wed) by HelloWorld (guest, #56129) [Link]

> Dispatching on types is just not a good way to write code in a dynamically typed language. There is no - and can be no - exhaustiveness checking for example, to give just one example of why it's a problem.

That problem has nothing to do with pattern matching and everything to do with dynamic typing, which is quite simply an inherently bad idea.