[WIP] pattern-matching: Cannot_flatten, maybe we can? #9650
Conversation
|
We had a meeting today about this PR with @trefis and @maranget. @maranget is willing to get rid of exceptional control-flow, if the code really is simpler. @trefis or @Octachron proposed to review the PR (eventually) to get a third-party opinion (or two) on whether the change actually simplifies the code. |
|
I did the changes suggested by @trefis. To make the |
gasche
force-pushed
the
matching-can-flatten
branch
3 times, most recently
from
f2e274a
to
08d3b4b
Compare
lambda/matching.ml
Outdated
| compile a tuple pattern [match e1, .. en with ...] | ||
| without allocating the tuple [(e1, .., en)]. | ||
| *) | ||
| let env = List.map (fun id -> id, Ident.rename id) vars in |
There was a problem hiding this comment.
Not all of the fresh new ids are being used, so you could delay the call to Ident.rename until you know that you're going to be using the id.
Also, I think the code would be easier to read without one more env variable with a different meaning from other envs in this file. (I know the name was there before your PR, but let's take the opportunity to change it!)
There was a problem hiding this comment.
I'm trying to apply your on-demand-rename suggestion:
- bad news: the resulting code is even more complex than the current one
- good news: this forced me to write a comment to explain what the function does in the first place, and I realized that we can probably simplify its interface a bit (it does not need to take the
patlas part of the input as it ignores them, and in particular does not freshen any variables they would bind in the action, which is fine as the function is only called with omega-patterns there!).
There was a problem hiding this comment.
I pushed commits corresponding to those changes, let me know what you think.
|
PS: What about the changes entry? |
gasche
force-pushed
the
matching-can-flatten
branch
3 times, most recently
from
7814416
to
045d106
Compare
|
@trefis I believe that I have addressed your comments (although for fresh-id generation you might think that the cure is worse than the disease, with the resulting code more complex; let me know and I can always revert), and now the CI is green. Hint hint. |
|
(recently I wondered about which of the pattern-matching PR are still in-flight; this one is) |
Note: we now use -dlambda rather than -drawlambda, because otherwise the output is much more verbose and difficult to read. (-drawlambda is closed to the inner workings of the pattern-matching compiler, but the simplification in -dlambda make the output much more readable. They are also fairly predictable/non-surprising, so I think that we can still easily understand what the compiler did from that output.)
gasche
force-pushed
the
matching-can-flatten
branch
from
045d106
to
10ab7c1
Compare
…bles Before we ignored as-patterns in the flatten_* functions because as-patterns would either be half-simplified or raise Cannot_flatten (in any case, never reach the flattening functions). Now the reasoning is a bit more subtle: the only non-simple matrices we flatten are used as "ghost" information (default environments, provenance) where variables do not matter, only the shape of matched values.
…iers This change was suggested by Thomas Refis during code review.
(suggested by Thomas Refis' review)
gasche
force-pushed
the
matching-can-flatten
branch
from
10ab7c1
to
dacaddc
Compare
(A nice catch of Florian Angeletti's review)
This PR implements a new approach to "flattening" pattern-matching compilation (
do_for_multiple_match) for source programs of the formmatch foo, bar, baz with .... (The pattern-matching compiler is trying to avoid allocating a tuple if possible, that is if the patterns do not use the name of the tuple. The point of this PR is to change the details of how this is implemented.)The goal of getting rid of the
Cannot_flattenexception is to simplify reasoning on the codebase. It looks like we actually produce better code, but this was not the intent -- the examples where we see a different are relatively artificial and may not exist in real codebases.This PR is only a Work-in-Progress, because the "simplify the reasoning" part is only half-achieved. We do not have
Cannot_flattenanymore, so the control flow is simpler, but the correctness reasoning for theflatten_*functions has become more subtle: whereas we knew before that they would never encounter (and throw away) as-patterns, they can now reach as-patterns, but only in usage modes (default environments, provenance) where (I believe that) variables do not matter anyway, so ignoring them is fine.(cc @maranget, @trefis, @Octachron)