Skip to content

pattern-matching refactoring: simplify Default_env.specialize_matrix by avoiding the OrPat exception#9464

Merged
gasche merged 4 commits intoocaml:trunkfrom
gasche:rematch-exceptionless-matcher
Apr 23, 2020
Merged

pattern-matching refactoring: simplify Default_env.specialize_matrix by avoiding the OrPat exception#9464
gasche merged 4 commits intoocaml:trunkfrom
gasche:rematch-exceptionless-matcher

Conversation

@gasche
Copy link
Copy Markdown
Member

@gasche gasche commented Apr 18, 2020

This is the next bit of the big pattern-matching refactoring change (#9321) after #9447 has been merged.

(cc @trefis @Octachron)

This patchset contains a bugfix, and a (tricky) refactoring that clarifies and simplifies the specialize_matrix logic by getting rid of the OrPat exception used in a higher-order way. Instead it uses an arity-based criterion to implement the same logic, which lets us do it once in the specializer, instead of having to implement it in each matcher. As a result, the compiler improves a bit as it will push or-patterns down during specialization in valid situations that were not implemented before. For example, lazy p | lazy q is turned into lazy (p | q) -- same non-constant polymorphic variants, etc..

@gasche gasche force-pushed the rematch-exceptionless-matcher branch from da4b7cb to dc068bd Compare April 18, 2020 09:32
Several functions in the pattern-matching compiler do recursive
"specialization" through a filter_rec helper written in tail-call
style with a 'rem' parameter containing the matrix rows yet to be
processed as input. Typical returns of the function are

  foo :: filter_rec rem

to add a new output, and

  filter_rec (foo :: rem)

to add a new input to be processed (usually by partial decomposition
of the current input row).

Some places would contain the declaration (let rem = filter_rec rem)
to factorize outputs of the first kind, but this gives a programming
style that is very confusing as `rem` may now represent either an
input or an output of the filter.

Using better types (as will be done farther away in the
pattern-matching refactoring) avoids this problem completely:
specialization then has different input and output types (typically,
from general to half-simple patterns), so incorrectly mixing inputs
and outputs is impossible. Yay typing.
@gasche gasche force-pushed the rematch-exceptionless-matcher branch from dc068bd to 8426fcb Compare April 22, 2020 09:06
…r side

(This commit is more tricky than the previous ones in the patchset
and requires a careful review.)

This refactoring clarifies and simplifies the specialize_matrix logic
by getting rid of the OrPat exception used in a higher-order
way (or sometimes not used in certain matchers, when it is possible to
"push" the or-pattern down in the pattern). Instead it uses an
arity-based criterion to implement the or-pattern-related logic once
in the specializer, instead of having to implement it in each
matcher. As a result, the compiler improves a bit as it will push
or-patterns down during specialization in valid situations that were
not implemented before -- probably because they are not terribly
important in practice: all constant and arity-1 constructs benefit
from optimized or-pattern handling, in particular the following are
new:
- lazy patterns
- non-constant polymorphic variants
- size-one records and arrays
@gasche gasche force-pushed the rematch-exceptionless-matcher branch from 8426fcb to 6e153b1 Compare April 22, 2020 19:32
Copy link
Copy Markdown
Member

@Octachron Octachron left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks good to me.
Overall, removing an exception from the control flow by generalizing an optimization is really nice.

@gasche gasche merged commit 4943a37 into ocaml:trunk Apr 23, 2020
@gasche
Copy link
Copy Markdown
Member Author

gasche commented Apr 23, 2020

Thanks! I will now work on the next PR.

@gasche gasche changed the title pattern-matching refactoring: simplify Default_env.specialize_matrix by avoiding exceptions pattern-matching refactoring: simplify Default_env.specialize_matrix by avoiding the OrPat exception Apr 23, 2020
gasche added a commit to gasche/ocaml that referenced this pull request Aug 11, 2020
gasche added a commit that referenced this pull request Aug 11, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants