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
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:
- Put the two objects side by side, aligning them on their first elements.
Start examining corresponding pairs of elements from the left
- If the elements of
the first pair are identical or if the first of this pair is ?, then move on to
examine the next pair, otherwise the match fails
- If you arrive successfully at
the end of both objects simultaneously, then the objects match
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:
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) :
- A check is made to see if some terminating condition is met - if it is, the
procedure halts in some way.
- Some action is taken.
- A recursive call is made
using inputs based on some variant(s) of the current input(s)
This translates straight into Logo, with the last line split for cosmetic reasons
- Have you arrived successfully a at the end of both objects simultaneously -
finding them both empty? If so, output "true (and halt).
- Check the the two
objects to see if either of the following is true
- their first elements are
- the first element of the first object is ?
- 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).
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]
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.
Department of Linguistic Science
The University of Reading