Old version of tutorial on pattern matching. New version at http://youtu.be/RvpK7RgWmoE
Channel: aaronsloman
Date: 04/12/2011

This has been replaced by http://youtu.be/RvpK7RgWmoE



This is one of a collection of tutorials demonstrating Pop11, a language with some of the features of Lisp, Scheme, and Prolog, developed for teaching and research in AI and Cognitive Science. This unscripted tutorial turned out longer than intended. It is based on this file, showing the program text demonstrated in the tutorial http://www.cs.bham.ac.uk/research/projects/poplog/teach/match_sorted

Most people think of pattern matching as an operation performed on strings (e.g. 'grep' in unix/linux). The matching here is on structures, including lists of items, lists of lists, etc. So the functions of matching in this context can be thought of as searching in and extracting information from a database of knowledge rather than finding and manipulating bits of text.

Because the tutorial was unscripted there are some bloopers -- e.g. where I temporarily switched my brain into the wrong context -- e.g. attempting to trace "matches" in an example that used "doesmatch", not "matches".

The tutorial presents a fairly standard recursive algorithm for checking whether a list of numbers is sorted, then shows how that can be replaced by a non-recursive definition using the pop11 pattern matcher, which allows you to specify a sort of abstract picture of what is not allowed in a sorted list. The pop11 matcher compares that picture with an input list, and if it matches, the list is not sorted.

This naive use of the matcher is shown to work, but with considerable inefficiency. So a Pop11 library is compiled which allows, instead of the format

      DATUM matches PATTERN

the format

      DATUM doesmatch PATTERN where CONDITION

Using the second format, the pictorial specification of what a non-sorted list is like is somewhat clearer and its use is also much more efficient, since the search for an unsorted fragment of the list is more controlled. 

The tutorial then shows how the procedure can be generalised to test a variety of types of list, including lists with mixed types of components (e.g. words and numbers) by  allowing the test for unordered elements instead of being frozen in the code to be passed as a second parameter to the procedure. Then by using the same procedure with different 'unordered' tests we can produce a variety of tests for different kinds of ordering, all using the same generic procedure.

Finally the tutorial shows how the generic procedure can be partially applied to different specific tests (forming Pop11 closures) to create different procedures, testing for different things.

In retrospect I think the example may be confusing for some viewers because the task of checking whether a list satisfies a condition (e.g. containing numbers in ascending order) requires using a test that indicates a failure to satisfy that condition, e.g. a test for an adjacent pair of numbers being in descending order. That implies that a true result for the test implies a false result for the main procedure. This complexity is a consequence of the example shown being for something being true of ALL parts of a list, which is equivalent to non-existence of ANY part of the list for which it is not true. Some human brains find this hard to grasp. 

The process of generalisation or abstraction from a few examples of testing a list, then creating a new "generic" version of the test, by abstraction, which can then be instantiated to produce new examples,
illustrates the ability of humans to learn different competences, then discover that those competences share some structure, and then use the shared structure with additional parameters to cope with novel situations.

That is a common process in mathematical discovery and in becoming more competent at programming. It is often confused with metaphorical thinking (which requires continued reference to the original examples, whereas abstraction does not).

I think it is an example of the notion of "Representational Redescription" presented by Annette Karmiloff-Smith in her 1992 book "Beyond modularity". Implementing representational redescription in a program is an ambitious task for Artificial Intelligence. This tutorial does not go into that.