making the match compiler smarter

The match compiler developed a little problem.  It's amazing that it didn't show up earlier.  As described in chapter 5 of Peyton-Jones' book, "The Implementation of Functional Programming Languages", certain 'obvious' or 'optimized' pattern matches actually compile to worse code.

The following function is from the book (pg 88), and is similar to an implementation of map2.

(define demo
  () ys -> (:A ys)
  xs () -> (:B xs)
  (x . xs) (y . ys) -> (:C x xs y ys)
  )

The second match clause will actually compile more efficiently if you use (x . xs) rather than a variable, because the match compiler knows in this case you're matching a cons cell. (it avoids the 'mixture rule' and uses only the 'constructor rule').

Regardless of this optimization, I ran into a more significant issue.  If I use xs, I get an 'incomplete match' error, because the code generated for this match has to examine the first list twice - in the first test it covers only the nil case.  In the second test, it covers the cons case, but has an 'else' clause that generates a match error.

Here's what the node tree looks like:

290 L    primapp [33] ('%%fatbar', None) ? 
262 L      nvcase [5] ('list', ['nil']) ? 
258 L        varref [1] m0_7_i0 ? 
260 L        primapp [2] ('%vcon/A/1', None) ? 
259 L          varref [1] m1_8_i1 ? 
261 L        primapp [1] ('%%fail', None) ? 
289 L      primapp [27] ('%%fatbar', None) ? 
267 L        nvcase [5] ('list', ['nil']) ? 
263 L          varref [1] m1_8_i1 ? 
265 L          primapp [2] ('%vcon/B/1', None) ? 
264 L            varref [1] m0_7_i0 ? 
266 L          primapp [1] ('%%fail', None) ? 
288 L        nvcase [21] ('list', ['cons']) ? 
268 L          varref [1] m0_7_i0 ? 
286 L          let_splat [18] [{m2_9_i0}, {m3_10_i0}] ? 
270 L            primapp [2] ('%nvget/list/cons/0', None) ? 
269 L              varref [1] m0_7_i0 ? 
272 L            primapp [2] ('%nvget/list/cons/1', None) ? 
271 L              varref [1] m0_7_i0 ? 
285 L            nvcase [13] ('list', ['cons']) ? 
273 L              varref [1] m1_8_i1 ? 
283 L              let_splat [10] [{m4_11_i0}, {m5_12_i0}] ? 
275 L                primapp [2] ('%nvget/list/cons/0', None) ? 
274 L                  varref [1] m1_8_i1 ? 
277 L                primapp [2] ('%nvget/list/cons/1', None) ? 
276 L                  varref [1] m1_8_i1 ? 
282 L                primapp [5] ('%vcon/C/4', None) ? 
278 L                  varref [1] m2_9_i0 ? 
279 L                  varref [1] m3_10_i0 ? 
280 L                  varref [1] m4_11_i0 ? 
281 L                  varref [1] m5_12_i0 ? 
284 L              primapp [1] ('%%match-error', None) ? 
287 L          primapp [1] ('%%match-error', None) ? 

...and in a pseudo-python:

if nil(m0):
  A()
elif nil(m1):
  B()
else:
  if cons(m0):
    if cons(m1):
      C()
    else:
      raise Error
  else:
    raise Error

The problem is that the match is actually exhaustive, because the nil case was examined already.  %%match-error in Irken is actually a kind of sentinel, the back end doesn't know how to compile it, so you can't actually compile code that's not exhaustive.

To fix this, I added an extra pass to the analysis phase that builds environments of 'already tested alternatives' for each nvcase variable. This actually killed two birds with one stone. In many cases, the innermost nvcase test is completely unnecessary - for this example, we've already tested for nil, and actually testing for a cons is redundant. In this case we simply remove the nvcase test (and the erroneous match-error), and return the body.

The code then generated for map is closer to what a human might write:

pseudo-python:

if nil(m0):
  A()
elif nil(m1):
  B()
else:
  C()

RTL:

0 = constructed [] 1
   1 = constructed [] 0
   2 = fatbar 'fatbar_0' []
       2 = move [0, None] 'm0_7_i0'
       2 = nvcase 'list' [2]
           2 = move [1, None] 'm1_8_i1'
           2 = primop [2] ('%make-tuple', 'A', 0)
               return [2] None
               fail [] ('fatbar_0', 0)
           return [2] None
       2 = fatbar 'fatbar_1' []
           2 = move [1, None] 'm1_8_i1'
           2 = nvcase 'list' [2]
               2 = move [0, None] 'm0_7_i0'
               2 = primop [2] ('%make-tuple', 'B', 1)
                   return [2] None
                   fail [] ('fatbar_1', 0)
               return [2] None
           2 = move [0, None] 'm0_7_i0'
           2 = primop [2] ('%vget', '0')
           3 = move [0, None] 'm0_7_i0'
           3 = primop [3] ('%vget', '1')
           4 = move [1, None] 'm1_8_i1'
           4 = primop [4] ('%vget', '0')
           5 = move [1, None] 'm1_8_i1'
           5 = primop [5] ('%vget', '1')
           6 = move [2, None] 'm2_9_i0'
           7 = move [3, None] 'm3_10_i0'
           8 = move [4, None] 'm4_11_i0'
           9 = move [5, None] 'm5_12_i0'
           6 = primop [6, 7, 8, 9] ('%make-tuple', 'C', 2)
               return [6] None
           return [2] None
       return [2] None