Re: A reference of the match compiler?

["Mura Li" <mail@xxxxxxx>]

That helps a lot. Thanks!

-mura
On Thu, May 9, 2019, at 4:25 AM, Ori Bernstein wrote:
> On Wed, 08 May 2019 04:49:49 -0400, "Mura Li" <mail@xxxxxxx> wrote:
> 
> > What is the algorithm on which the current match compiler (mi/match.c) is based?
> 
> A thing that came out of my head. It's kind of janky -- the idea is that it's
> based on incrementally building up a DFA. So, for example:
> 
> match x
> | `Some (123, a): do1
> | `Some (234, 789): do2
> | `Some (234, b): do3
> | `Some _: do4
> | `None do5
> ;;
> 
> Gets compiled incrementally to an automaton like so:
> 
> 
> First match added: no multiple tails to attach to, just go through
> and create a linear set of states.
> 
>  (tag(x) == `Some) ---> (some.val == 123) ---> wildcard --> do1
> 
> Second one matches branches after the tag:
> 
>  (tag(x) == `Some) -----> (some.val == 123) ---> wildcard --> do1
>  \
>  +-> (some.val == 234) ---> 789 --> do2
> 
> Third one adds in a wildcard, so we tack that on:
> 
>  (tag(x) == `Some) -----> (some.val == 123) ---> wildcard --> do1
>  \
>  +-> (some.val == 234) -----> 789 --> do2
>  \
>  +-> wildcard --> do3
> 
> the fourth one adds wildcards for all tuple, so we need to walk down
> all branches and tack it in:
> 
>  +-----------> wildcard -> do4
>  /
>  (tag(x) == `Some) -----> (some.val == 123) ---> wildcard --> do1
>  \ 
>  \
>  +-> (some.val == 234) -----> 789 --> do2
>  | \
>  | +-> wildcard --> do3
>  \
>  \---> wildcard -----------> wildcard --> do4
> 
> And finally, we add the none in.
> 
> > Any reference paper or book about it?
> 
> 
> Not that I'm aware of.
> 
> > I have looked into a few from the internet, but they do not look like a one-to-one translation.
> 
> Yeah, it's a confusing stateful mess. I'd be happy to tear it out
> and looking at put in a new one, possibly based on Augustsson's
> paper on how to compile pattern matching.
> 
> -- 
>  Ori Bernstein
>