FWIW, I wrote a pattern-matching library for Lua, Tamale (http://github.com/silentbicycle/tamale/ http://github.com/silentbicycle/tamale/). It was an interesti

FWIW, I wrote a pattern-matching library for Lua, Tamale (http://github.com/silentbicycle/tamale/ http://github.com/silentbicycle/tamale/). It was an interesting project, because almost everything I could find about implementing pattern-matching assumed the patterns could be analyzed at compile time, rather than building some kind of dispatch tree at runtime. After trying some more elaborate methods (e.g. building a decision tree via CPS), I figured out that just indexing (on the first field, by default) and then doing linear search within the index's patterns got 90% of the benefit with very little runtime analysis.