[MLton] Catching redundant pattern matches
Jesper Louis Andersen
Sun, 12 Dec 2004 19:27:16 +0100
I have a little lump of code, which is like this:
fun rewriteReg (spill_slots, regs, program, registermap) =
case (spill_slots, regs) of
(, regs) => raise AllocatorSpill (List.length regs)
| (s :: ss, r :: rs) =>
val (program, registermap) =
Isa.rewriteProgram (program, r, registermap, s)
rewriteReg (ss, rs, program, registermap)
| (ss, ) => (ss, program, registermap)
| (, ) => (, program, registermap)
Of course, the last pattern (, ) is redundant in the above and the
code is dead wrong since the pattern should be the first. My concern
is that MLton did not warn about this, while Moscow ML did:
File "RegisterAllocate-fun.sml", line 397-406, characters 4-354:
! ....(, regs) => raise AllocatorSpill (List.length regs)
! | (s :: ss, r :: rs) =>
! val (program, registermap) =
! rewriteReg (ss, rs, program, registermap)
! | (ss, ) => (ss, program, registermap)
! | (, ) => (, program, registermap)
! Warning: some cases are unused in this match.
A better error-message, though it doesn't point out the redundant
case. Moscow ML uses the following pattern-match compiler:
Which I thought about implementing in MLton for fun. It is a quite
simple algorithm and the paper is rather interesting (IMO). A resume
is that Sestoft uses a partial evaluator to drive his construction
of the pattern match compiler. At the beginning, there is no static
information at which the PE hooks, but when he instruments the compiler
to also track positive and negative information, he gets a speedup.
Next he then notices, that the partial evaluation is so simple it is
not needed at all! At that point he throws out the PE, writes the code
himself and ends up with a pattern match compiler, which Moscow ML uses.
The interesting part of the paper is section 7.4 in which he detects
such redundant cases.
While I know this is done inside the elaborator of MLton, I am wondering
if we can get the same case to find the redundant match (and print it,
just to do something additional). I am willing to do this myself, if
I can be directed at the places to look.