19A Query CompilerSome of the macros defined in the preceding chapter were large ones. To generateits expansion, if-match needed all the code in Figures 18.7 and 18.8, plusdestruc from Figure 18.1. Macros of this size lead naturally to our last topic,embedded languages. If small macros are extensions to Lisp, large macros definesub-languages within it—possibly with their own syntax or control structure. Wesaw the beginning of this in if-match, which had its own distinct representationfor variables.A language implemented within Lisp is called an embedded language. Like“utility,” the term is not a precisely defined one; if-match probably still countsas a utility, but it is getting close to the borderline.An embedded language is not a like a language implemented by a traditionalcompiler or interpreter. It is implemented within some existing language, usuallyby transformation. There need be no barrier between the base language and theextension: itshouldbepossibleto intermingle thetwo freely. For theimplementor,this can mean a huge saving of effort. You can embed just what you need, and forthe rest, use the base language.Transformation, in Lisp, suggests macros. To some extent, you could imple-ment embedded languages with preprocessors. But preprocessors usually operateonly on text, while macros take advantage of a unique property of Lisp: betweenthe reader and the compiler, your Lisp program is represented as lists of Lispobjects. Transformations done at this stage can be much smarter.The best-knownexampleof an embedded languageisCLOS, the Common LispObjectSystem. If youwanted to makean object-orientedversionofa conventionallanguage, you would have to write a new compiler. Not so in Lisp. Tuning the24619.1 THE DATABASE 247compiler will makeCLOS run faster, but in principle the compiler doesn’t have tobe changed at all. The whole thing can be written in Lisp.The remaining chapters give examples of embedded languages. This chapterdescribes how to embed in Lisp a program to answer queries on a database. (Youwill notice in this program a certain family resemblance to if-match.) The firstsections describe how to write a system which interprets queries. This program isthen reimplemented as a query compiler—in essence, as one big macro—makingit both more efficient and better integrated with Lisp.19.1 The DatabaseFor our present purposes, the format of the database doesn’t matter very much.Here, for the sake of convenience, we will store information in lists. For example,we will represent the fact that Joshua Reynolds was an English painter who livedfrom 1723 to 1792 by:(painter reynolds joshua english)(dates reynolds 1723 1792)There is no canonical way of reducing information to lists. We could just as wellhave used one big list:(painter reynolds joshua 1723 1792 english)It is up to the user to decide how to organize database entries. The only restrictionis that the entries ( facts) will be indexed under their first element (the predicate).Within those bounds, any consistent form will do, although some forms mightmake for faster queries than others.Any database system needs at least two operations: one for modifying thedatabase, and one for examining it. The code shown in Figure 19.1 provides theseoperations in a basic form. A database is represented as a hash-table filled withlists of facts, hashed according to their predicate.Although the database functions defined in Figure 19.1 support multipledatabases, they all default to operations on *default-db*. As with packagesin Common Lisp, programs which don’t need multiple databases need not evenmention them. In this chapter all the examples will just use the *default-db*.We initialize the system by calling clear-db, which empties the currentdatabase. We can look up facts with a given predicate with db-query, and insertnew facts into a database entry with db-push. As explained in Section 12.1, amacro which expands into an invertible reference will itself be invertible. Sincedb-query is defined this way, we can simply push new facts onto the db-queryof their predicates. In Common Lisp, hash-table entries are initialized to nil248 A QUERY COMPILER(defun make-db (&optional (size 100))(make-hash-table :size size))(defvar *default-db* (make-db))(defun clear-db (&optional (db *default-db*))(clrhash db))(defmacro db-query (key &optional (db ’*default-db*))‘(gethash ,key ,db))(defun db-push (key val &optional (db *default-db*))(push val (db-query key db)))(defmacro fact (pred &rest args)‘(progn (db-push ’,pred ’,args)’,args))Figure 19.1: Basic database functions.unless specified otherwise, so any key initially has an empty list associated withit. Finally, the macro fact adds a new fact to the database.> (fact painter reynolds joshua english)(REYNOLDS JOSHUA ENGLISH)> (fact painter canale antonio venetian)(CANALE ANTONIO VENETIAN)> (db-query ’painter)((CANALE ANTONIO VENETIAN)(REYNOLDS JOSHUA ENGLISH))TThe t returned as the second value by db-query appears because db-queryexpands into a gethash, which returns as its second value a flag to distinguishbetween finding no entry and finding an entry whose value is nil.19.2 Pattern-Matching QueriesCalling db-query is not a very flexible way of looking at the contents of thedatabase. Usually the user wants to ask questions which depend on more thanjust the first element of a fact. A query language is a language for expressing19.2 PATTERN-MATCHING QUERIES 249query : (symbol argument *): (not query ): (and query *): (or query *)argument : ?symbol : symbol : number Figure 19.2: Syntax of queries.more complicated questions. In a typical query language, the user can ask for allthe values which satisfy some combination of restrictions—for example, the lastnames of all the painters born in 1697.Our program will provide a declarative query language. In a declarative querylanguage, the user specifies the constraints which answers must satisfy, and leavesit to the system to figure out howto generate them. This way of expressing queriesis close to the form people use in everyday conversation. With our program, wewill be able to express the sample query by asking for all the x such that thereis a fact of the form (painter x ...), and a fact of the form (dates x 1697...). We will be able to refer to all the painters born in 1697 by writing:(and (painter ?x ?y ?z)(dates ?x 1697 ?w))As well as accepting simple queries consisting of a predicate and some