koka-lang / koka

Koka language compiler and interpreter
http://koka-lang.org
Other
3.16k stars 151 forks source link

match merging optimization #363

Open TimWhiting opened 9 months ago

TimWhiting commented 9 months ago

Takes a match that has common superstructure, and reworks it to match on that first.

Note that the transform expects there only to be a single pattern in the match statement, which I believe is a fine assumption to begin with, since tuple types are used for multiple pattern matches, and it rewrites the core from the bottom up. However, it probably should be improved to handle this as well. Branches can get tricky fast.

So

match e
    Cons(a, Cons(1, Cons(c, Nil))) -> (a + c).show.println
    Cons(_, Cons(b, _)) -> b.show.println
    Nil -> "Nothing".println
    _ -> implicit error

Turns into

match e
  Cons(a, Cons(b, d)) -> 
    match (b, d)
       (1, Cons(c, Nil) -> a + c.show.println
       (b, _) -> b.show.println
        _ -> implicit error
  Nil -> "Nothing".println
  _ -> implicit error

In the generated C code, the original results in duplicated Cons checks for the first two Conses. In the new, those checks are eliminated.

It is smart enough to push the implicit error incomplete match error branches down into subpatterns, but doesn't do any exhaustiveness checking to see if the changes have resulted in any new exhaustive cases.

TimWhiting commented 8 months ago

This is not ready to merge, I'll add some tests since it does end up moving things around quite a bit.