Re: A reference of the match compiler?

[Ori Bernstein <ori@xxxxxxxxxxxxxx>]

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