We are supposing that match? will be called with two lists as its inputs. One list represents the user's query (the original input to query) which may contain occurrences of the ? wild card and the other list represents a single database fact. Match?, being a predicate, will only output "true or "false. It will output "true if the two lists match and "false otherwise.

Since, however, we are planning to develop a matching tool with more general application, it will probably be sensible to design match? to accept words (including wild cards) just as easily as lists - in other words, to accept any Logo object. To reflect this open door policy, we might call the two inputs simply "this and "that.

The basic algorithm

As for the matching algorithm, here, paraphrased in English, is one possibility: If you prefer a more visual version, use words as examples of the objects to be matched and imagine examining them through a letter-wide window which you can slide over the words. Here are some examples of what happens in different cases:

If you have been looking at the characteristics of recursive procedures, you will recall that the structure for the body of a recursive definition is typically:

  1. A check is made to see if some terminating condition is met - if it is, the procedure halts in some way.
  2. Some action is taken.
  3. A recursive call is made using inputs based on some variant(s) of the current input(s)
With a simple reordering of the terminating condition, our English version of the algorithm for the predicate match? will map directly onto this pattern. (The business of aligning the two objects is handled automatically if we process both together starting with their first elements) :
  1. Have you arrived successfully a at the end of both objects simultaneously - finding them both empty? If so, output "true (and halt).
  2. Check the the two objects to see if either of the following is true
  3. Make a recursive call using the remainders of the objects as inputs (in order to check the next pair), if the test result was positive - if not, output "false (and halt).
This translates straight into Logo, with the last line split for cosmetic reasons only:

to match? :this :that 
if and empty? :this empty? :that [op "true]
if or  (first :this ) = ( first :that) 
           ( first :this ) = "? 
                      [op match? bf :this bf :that] 
                                 [op "false] 

Back up to query

If you have been following the story bottom up, you can now jump back to continue with the development of query. Just click here. Otherwise, try the next page.

Ron Brasington
Department of Linguistic Science
The University of Reading