Improve the left-hand side flattener

[steinerkelvin]

HVM's runtime only handles direct, non nested matches. So, for example, this is a valid rule:

(Foo (Bar xs)) = (A xs)

But this is not:

(Foo (Bar (Cons x xs))) = (A (Cons x xs))

Because there is a nested match. In order for these cases to work, we must split the left-hand of nested patterns, into many non nested equations. Currently, the language has a flattener that is limited, and will fail in some cases. For example, the function below:

Fn (Bar (Cons ...)) = A
Fn (Bar Nil)        = B
Fn x                = C

Should be compiled to:

Fn (Bar _0)         = (Fn.0 _0)
  (Fn.0 (Cons x y)) = A
  (Fn.0 Nil)        = B
  (Fn.0 x)          = C
Fn x                = C

But the current flattener can't deal with that.

[rigille]

i need this so much. i'm trying to implement it right now

[bredelings]

The method for doing this is described in chapter five "Efficient compilation of Pattern-Matching" by Wadler in "The Implementation of Functional Programming Languages" (1987) by Simon L Peyton-Jones

https://www.microsoft.com/en-us/research/wp-content/uploads/1987/01/slpj-book-1987-small.pdf

[VictorTaelin]

Closing this issue since the flattener on master now covers all cases.