The query function you’ll write, select, is loosely modeled on the SELECT statement from Structured Query Language (SQL). It’ll take five keyword parameters: :from, :columns, :where, :distinct, and :order-by. The :from argument is the table object you want to query. The :columns argument specifies which columns should be included in the result. The value should be a list of column names, a single column name, or a **T**, the default, meaning return all columns. The :where argument, if provided, should be a function that accepts a row and returns true if it should be included in the results. In a moment, you’ll write two functions, matching and in, that return functions appropriate for use as arguments. The :order-by argument, if supplied, should be a list of column names; the results will be sorted by the named columns. As with the :columns argument, you can specify a single column using just the name, which is equivalent to a one-item list containing the same name. Finally, the :distinct argument is a boolean that says whether to eliminate duplicate rows from the results. The default value for :distinct is **NIL**.

Here are some examples of using select:

Of course, the really interesting part of select is how you implement the functions extractor, row-equality-tester, and row-comparator.

As you can tell by how they’re used, each of these functions must return a function. For instance, project-columns uses the value returned by extractor as the function argument to **MAP**. Since the purpose of is to return a set of rows with only certain column values, you can infer that extractor returns a function that takes a row as an argument and returns a new row containing only the columns specified in the schema it’s passed. Here’s how you can implement it:

The functions row-equality-tester and row-comparator are implemented in a similar way. To decide whether two rows are equivalent, you need to apply the appropriate equality predicate for each column to the appropriate column values. Recall from Chapter 22 that the **LOOP** clause always will return **NIL** as soon as a pair of values fails their test or will cause the **LOOP** to return **T**.

Ordering two rows is a bit more complex. In Lisp, comparator functions return true if their first argument should be sorted ahead of the second and **NIL** otherwise. Thus, a **NIL** can mean that the second argument should be sorted ahead of the first or that they’re equivalent. You want your row comparators to behave the same way: return **T** if the first row should be sorted ahead of the second and **NIL** otherwise.

But if the column comparator returns **NIL**, then you need to determine whether that’s because the second value should sort ahead of the first value or because they’re equivalent. So you should call the comparator again with the arguments reversed. If the comparator returns true this time, it means the second column value sorts ahead of the first and thus the second row ahead of the first row, so you can return immediately. Otherwise, the column values are equivalent, and you need to move onto the next column. If you get through all the columns without one row’s value ever winning the comparison, then the rows are equivalent, and you return **NIL**. A function that implements this algorithm looks like this: