My research and investigations

Martin Elsman directs me to these doco relating to the Pattern Matching algorithm in ML:

  1. Peter Sestoft: ML Pattern Match Compilation and Partial Evaluation
  2. 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.

Unification is pattern matching on structured data: for example matching a list by its head and tail. The best known algorithm for unification of first-order logic is due to John Robinson in 1965.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: