Martin Elsman directs me to these doco relating to the Pattern Matching algorithm in ML:
- Peter Sestoft: ML Pattern Match Compilation and Partial Evaluation
- Martin Elsman: Polymorphism and Unification of Cyclic Terms
Peter’s paper is quite thorough: starting with codes of a naive ML pattern matcher, he improves it to the instrumented ML pattern matcher. He proceeds to show ML match compilation, also with codes — all within 20 pages!
Martin’ paper confirms my hunch that ML pattern matching is closely related to the unification algorithm of Prolog. Again the algorithm is presented with actual codes, making this enjoyable reading.