Implementing the query command

Responding to a wild-card (wh) question

We are assuming that query, like the other main system primitives, takes one input - a list. As far as the user is concerned, this input list corresponds to the question to be put to the database and it may include wild cards if it represents a wh-question. Now, since wh-questions are open to more than one answer, it is clear that, if query is to provide a full response to such questions, it must retrieve all of the facts in the database whose pattern is found to match its input. Let us suppose, then, that query's response to a wild card question will be to output a list containing, as sub-lists, all of the matching facts. More often than not, this list will, of course, contain only one answer (one sub-list) and it may even be empty (like a shrug of the shoulders) if no matching fact is found.

And responding to a yes/no question

When it comes to yes/no questions, you might want to argue that query's response should be either the word Yes! or the word No! After all, that is why the questions are called yes/no questions. But, given that a list is the natural output format for wh-questions, it would more convenient, from a programming point of view, if we were able to standardise the format - and the retrieval technique - for all question types and supply responses to yes/no questions which were also lists. In fact, it is not too far fetched for query to output, instead of Yes! or No!, either a list containing the matching fact (with the exact repetition of the question acting as confirmation) or a list containing nothing at all (with the empty list this time being taken as a shake of the head, a denial rather than a don't know). This is, at any rate, the line we are going to take in order to avoid complications. You can, for your part, experiment with generating 'simple' Yes! or No! replies instead, if you wish.

Working bottom up

Having elsewhere argued for top-down system building, we are now going to suggest using the opposite tactic to prove that with Logo you can have your cake and eat it.

We know that, somehow or other, query is going to need to step systematically through the database list retrieving one fact (one sub-list) at a time so that it can be established whether or not this particular fact matches the list which represents the question. Now it is a normal tactic for a Logo procedure to delegate responsibility to a subordinate whenever possible, and query, if it has any sense, is certainly going to call on a helper to do the real work of deciding whether the input 'question' is matched or not by each individual fact. Since this helper is just going to need to answer "true or "false (meaning the lists 'match' or not), it is going to be a predicate. In view of its function, we may as well call it match?, with the question mark identifying the operation type.

Having got this far with our ideas, there is nothing to prevent us from ignoring for the moment the precise mechanics of query and turning our attention first to experimenting with the definition match?. The advantage of this bottom-up tactic is not only that in isolating the development of match? from the specifics of query we are more likely to create a universal pattern-matching tool which can be plugged into a number of other applications, but also we make it easier to update query itself should we later come across (or invent) a more useful general purpose pattern matcher.

So, if you want to look first at match?, click here.

Of course, if you prefer to read on, feel free.

Continuing with query

On the assumption that match? is set up to do the hard work of determining whether the current question is matched or not by a particular fact, all that remains for query itself to do is to submit each database fact in turn to match? and build up a list containing all those facts which which match? approves. In other words, thanks to match?, query reduces to a basic list-filtering procedure.

You should not be surprised as a result to see that it conforms in its general structure to one of the very common patterns for a recursive procedure:
  1. If no items left in the list, stop
  2. If the first item passes the given test, hang onto it
    (In other words, stick it on the front of whatever else turns up)
  3. Go back to 1 with the rest of the list

Translating this structure into a Logo procedure which would do the job required of query is straightforward enough. Here is a version:

to query :question :data
if empty? :data [op []]
if match? :question first :data 
          [op fput first :data query :question bf :data]
 op query :question bf :data
But you will notice that for this version of query to be able to work it has been necessary to provide it with two inputs. The first is the question to be checked and the second (called "data) is a list against whose members the question is to be checked turn by turn as the procedure winds its way through. This does not exactly coincide with the plan to standardise the format of user commands so that they all take just one input.

You might say: OK. So why stick to the format if it makes life difficult? Well, in fact, not sticking to the format would make life unnecessarily difficult for the user. After all, there is really little point in having to write:

query [john likes mary] :facts

if :facts is only and always the list against which questions are checked. From the user's point of view, specifying the name of the database is quite redundant.

Luckily, the problem is simply solved by using a technique which you will find useful on many other occasions. All we need to do is to provide a front-end or an interface to the real procedure which simplifies the user's task. Let's change the name of the version of query above and call it check instead:

to check :question :data
if empty? :data [op []]
if match? :question first :data 
          [op fput first :data check :question bf :data]
 op check :question bf :data
We can now define a short procedure query which accepts one input (corresponding to the question to be asked). The only role of this procedure is to call check - passing on the question as the first input and throwing in the database list called :facts as the second input - and then print what it receives. Just like this:

to query :question
pr check :question :facts

The user now need know nothing at all about check. Query is there to protect him or her from all the dirty work.

Still need to find out about match?

If you have been working top down and still need to find out about implementing match?, click here. Otherwise, try the next page to see a summary and the complete set of procedures.

Ron Brasington
Department of Linguistic Science
The University of Reading