This application is a simple query language to allow you to create a database of information about a particular domain, and then write queries to find answers to questions about that domain. I wrote it to make a database of information about Microchip ATtiny processors, to allow me to choose the best processor meeting the requirements of a particular project.
I give the full ATtiny database here so you can try it out, or extend it with other information such as the price of each chip. Note that it doesnāt include information about the new ATtiny 0-Series or 1-Series families.
Alternatively you could use the query language to build an information system for your own application.
Itās a simplified version of a popular type of example given in several Lisp books, including: Paul Grahamās āOn Lispā (pp. 246-254), available as a PDF on his site: Download On Lisp, his āANSI Common Lispā (pp. 247-256), and Peter Norvigās āParadigms of Artificial Intelligence Programmingā (pp 348-387), available as a PDF on GitHub: paip-lisp.
Running the query language
Iāve tested the query language with the ATtiny database using the ARM version of uLisp running on an Adafruit ItsyBitsy M4. After installing the program and database you can save everything into the non-volatile DataFlash provided on this board using (save-image), and then load everything back in with (load-image). The Adafruit Metro M4 and Adafruit Feather M4 should give identical performance; see Adafruit M4 boards.
It also works nicely using the ARM version of uLisp running on the Arduino Due, see Arduino Due, but in versions of uLisp up to and including 2.5c you need to double the symbol table size to 1024 bytes by editing the #define in the ARDUINO_SAM_DUE section to:
#define SYMBOLTABLESIZE 1024
Examples
For example, the database allows you to ask questions such as:
- Find all chips with at least 10 Kbytes of flash:
> (answer '(and (flash ?c ?x) (test (> ?x 10240))) '("Flash > 10K:" ?c))
Flash > 10K: attiny1634
Flash > 10K: attiny167
- Find all chips that have I2C slave support in hardware:
> (answer '(and (family ?c ?f) (i2c ?f slave)) '("I2C Slave support:" ?c))
I2C Slave support: attiny828
I2C Slave support: attiny1634
I2C Slave support: attiny48
I2C Slave support: attiny88
I2C Slave support: attiny441
I2C Slave support: attiny841
- Find all chips that have at least three timers (8-bit or 16-bit):
> (answer '(and (family ?c ?f) (timer8 ?f ?x) (timer16 ?f ?y) (test (>= (+ ?x ?y) 3)))
'("3 Timers:" ?c))
3 Timers: attiny441
3 Timers: attiny841
The database
The information is represented in the database as a series of facts, each of which is represented as a list, with the facts indexed under the first element, the predicate.
The database is stored as an association list in the global variable rules:
(defvar *rules* nil)
The function add is used to add a rule to the database. If the predicate doesnāt already exist in the database it is first added. Then the rule is added under the predicate:
(defun add (rule)
(unless (assoc (car rule) *rules*) (push (list (car rule)) *rules*))
(push (cdr rule) (cdr (assoc (car rule) *rules*)))
t)
For example, after executing:
> (add '(flash attiny85 8192))
t
> (add '(flash attiny45 4096))
t
> (add '(ram attiny85 512))
t
> (add '(ram attiny45 256))
t
the value of the database in *rules* will be:
((ram (attiny45 256) (attiny85 512)) (flash (attiny45 4096) (attiny85 8192)))
You can use add to add extra information to the database; for example, to add a rule giving the price of an ATtiny85:
(add '(price attiny85 0.89))
Structuring the ATtiny database
The ATtiny processors are arranged into families. The members of each family share the same package size and peripherals, but differ in the amount of flash, RAM, and EEPROM. For example, the ATtiny25, ATtiny45, and ATtiny85 are all 8-pin processors with the same I/O ports, timers, ADC features, and other peripherals. However the ATtiny85 has 8192 bytes of flash, the ATtiny45 has 4096 bytes of flash, and the ATtiny25 has 2048 bytes of flash, and the other memory sizes scale accordingly.
I have therefore represented the families in the database using predicates containing an āxā, such as attinyx5, and chips using predicates such as attiny25, attiny45, and attiny85, etc. The family determines values such as pins, io, and adc, whereas the individual chips determine the flash, ram, and eeprom values. Each chip also has a family attribute that links it to its family.
Pattern match
Patterns can include variables, which are symbols prefixed by a ā?ā. When a match succeeds the matching values are assigned to the corresponding variables.
The function var? tests whether a symbol is a variable:
(defun var? (x)
(and (symbolp x) (eq (char (string x) 0) #\?)))
The queries are matched against the database using the routine match:
(defun match (x y binds)
(cond
((eq x y) (if binds binds '((t))))
((assoc x binds) (match (binding x binds) y binds))
((assoc y binds) (match x (binding y binds) binds))
((var? x) (cons (cons x y) binds))
((var? y) (cons (cons y x) binds))
(t
(when (and (consp x) (consp y))
(let ((m (match (car x) (car y) binds)))
(when m (match (cdr x) (cdr y) m)))))))
This takes two patterns, x and y, and a list of variable bindings, and returns a new list of bindings corresponding to the variables that matched. For example:
> (match '(pins 20) '(pins ?x) nil)
((?x . 20) (t))
This means that the match has succeeded, with the variable ?x having the value 20.
If the match succeeds, but doesnāt create any bindings, it returns the special value ((t)):
> (match '(a b) '(a b) nil)
((t))
This is to distinguish from the case where the match fails, in which case it returns nil:
> (match '(a b) '(a c) nil)
nil
The function binding gets the value of a variable from the list of bindings:
(defun binding (x binds)
(let ((b (assoc x binds)))
(when b
(or (binding (cdr b) binds)
(cdr b)))))
For example:
> (binding '?x '((?x . 20)))
20
It calls itself recursively to resolve the case where the variableās value is referenced via another variable:
> (binding '?x '((?x . ?y) (?y . 20)))
20
Resolving queries
The function query submits a query to the database and returns a list of bindings:
(defun query (expr binds)
(let ((key (car expr)))
(cond
((eq key 'and) (query-and (reverse (cdr expr)) binds))
((eq key 'or) (query-or (cdr expr) binds))
((eq key 'not) (query-not (second expr) binds))
((eq key 'test) (query-test (second expr) binds))
(t (lookup (car expr) (cdr expr) binds)))))
A simple query calls lookup to look up the predicate in the database, and then match the arguments against the list of bindings. For example, to find all the chips in the database with 16384 bytes of flash:
> (query '(flash ?x 16384) nil)
(((?x . attiny1634)) ((?x . attiny167)))
This is handled by lookup:
(defun lookup (pred args binds)
(apply 'append
(mapcar
(lambda (x)
(let ((m (match args x binds)))
(when m (list m))))
(cdr (assoc pred *rules*)))))
It looks up the predicate in the database to get the list of rules for that predicate, matches each rule against the arguments of the query, and then appends together the results. Note that variables cannot appear in the predicate position.
The equivalent call to lookup for the above query is:
> (lookup 'flash '(?x 16384) nil)
(((?x . attiny1634)) ((?x . attiny167)))
The query function also supports queries starting with one of the keywords and, or, not, or test. These are explained in the following sections.
And
The and keyword combines conditions all of which must be true. For example, to find the chips with 16384 bytes of flash and 1024 bytes of RAM:
> (query '(and (ram ?c 1024) (flash ?c 16384)) nil)
(((?c . attiny1634)))
It is implemented by the function query-and:
(defun query-and (clauses binds)
(if (null clauses)
(list binds)
(apply 'append
(mapcar
(lambda (b) (query (car clauses) b))
(query-and (cdr clauses) binds)))))
Or
The or keyword combines conditions any of which can be true. For example, to find the families with either 1 or 2 UARTs:
> (query '(or (uart ?f 1) (uart ?f 2)) nil)
(((?f . attinyx28)) ((?f . attinyx7)) ((?f . attinyx313)) ((?f . attinyx34)) ((?f . attinyx41)))
It is implemented by the function query-or:
(defun query-or (clauses binds)
(apply 'append (mapcar (lambda (c) (query c binds)) clauses)))
Not
The not keyword allows you to filter previous matches from the results. For example, to find the families that donāt support an external crystal:
> (query '(and (family ?c ?f) (not (crystal ?f))) nil)
(((?f . attiny4/5) (?c . attiny4)) ((?f . attiny4/5) (?c . attiny5)) ((?f . attiny9/10)
(?c . attiny9)) ((?f . attiny9/10) (?c . attiny10)) ((?f . attinyX3) (?c . attiny43))
((?f . attinyX28) (?c . attiny828)) ((?f . attinyX8) (?c . attiny48)) ((?f . attinyX8)
(?c . attiny88)) ((?f . attinyx5) (?c . attiny25)) ((?f . attinyx5) (?c . attiny45))
((?f . attinyx5) (?c . attiny85)))
It is implemented by the function query-not:
(defun query-not (clause binds)
(unless (query clause binds)
(list binds)))
Test
The test query allows you to evaluate a Lisp test using the variables returned by earlier parts of a query. For example, to find all the families that have more than 28 pins:
> (query '(and (pins ?f ?p) (test (> ?p 28))) nil)
(((?p . 32) (?f . attinyX28)))
This is implemented by the function query-test:
(defun query-test (tst binds)
(when (eval (subs tst binds))
(list binds)))
It uses the function subs that substitutes the values of variables from the list of bindings in binds into the test expression:
(defun subs (lst binds)
(cond
((null lst) nil)
((atom lst) (if (assoc lst binds) (cdr (assoc lst binds)) lst))
(t (cons (subs (car lst) binds) (subs (cdr lst) binds)))))
Formatting the results
The final function, answer, provides a more elegant way of presenting the results of a query. It allows you to specify a query and an output list which will be printed on a separate line for each result. The output list can contain strings, and variables which will be replaced by the actual values of the variables:
(defun answer (expr output)
(dolist (binds (query expr nil))
(mapc (lambda (p) (princ p) (princ #\space)) (subs output binds))
(terpri)))
It uses subs, defined earlier, to substitute values into the variables.
Hereās an example that uses answer to print the flash, RAM, and EEPROM values for all processors with 16 Kb of flash:
> (answer '(and (flash ?c 16384) (ram ?c ?r) (eeprom ?c ?e))
'("16K chip:" ?c "RAM:" ?r "EEPROM:" ?e))
16K chip: attiny1634 RAM: 1024 EEPROM: 256
16K chip: attiny167 RAM: 512 EEPROM: 512
Reading in the database
Although you could define the database using a series of add commands, itās easier to define the ATtiny database structured by the devices and families, and then convert this to the appropriate calls to add. This is handled by the following read-data routine:
(defun read-data ()
(dolist (rules *data*)
(let ((pred (first rules))
(data (cdr rules)))
(mapc (lambda (rule) (add (cons (first rule) (cons pred (cdr rule))))) data)))
t)
Hereās an exerpt from the database; it gives the data for a family, and then the devices in that family:
(defvar *data*
'((attinyX5 (pins 8) (io 5) (adc 4) (pwm 3) (usi 1) (timer8 2) (crystal) (pll))
(attiny85 (family attinyx5) (flash 8192) (ram 512) (eeprom 512))
(attiny45 (family attinyx5) (flash 4096) (ram 256) (eeprom 256))
(attiny25 (family attinyx5) (flash 2048) (ram 128) (eeprom 128))))
The data for the full ATtiny database is given in the listing below.
Hereās the whole query language program, together with the data for the ATtiny database: Query language program