Query language
26th March 2019
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.
It includes a sample database of information about Microchip ATtiny processors, to allow you to choose the best processor meeting the requirements of a particular project. 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" [1] and "ANSI Common Lisp" [2], and Peter Norvig's "Paradigms of Artificial Intelligence Programming" [3].
Update
12th February 2023: Updated the information about running the query language to make it clearer.
Running the query language
The query language will work on most boards with at least 2800 objects of workspace, including boards based on the AVRDA48 or AVRDB48, ATSAMD21 or ATSAMD51, ESP8266 or ESP32, or Raspberry Pi Pico.
- Download the appropriate version of uLisp for the board from Download uLisp.
- Use the Arduino IDE to upload it to the board; see Download uLisp - Installing uLisp.
- Open the Serial Monitor in the Arduino IDE to display the uLisp prompt.
- Display the source of the query language here: Query language program.
- Select the text of the program, copy it, paste it into the Arduino IDE Serial Monitor input field, and press Return.
Loading the demonstration database
To load the demonstration database, containing information about Microchip ATtiny processors:
- Display the source of the database here: ATtiny database.
- Select the text of the database, copy it, paste it into the Arduino IDE Serial Monitor input field, and press Return.
- Build the database by typing:
(read-data)
Submitting a query
To query the database you give a query of the form:
(answer '(query) '(output))
where query is a query you want to submit to the database, and output is a list to format the output.
The query can contain arbitrary variables beginning with a question mark, such as ?x, which will be set to matching values in the database. So, for example, the query:
(flash ?c ?x)
will match every rule in the database starting with flash, such as:
(flash attiny85 8192)
After this successful match the variable ?c will be set to attiny85 and ?x will be set to 8192. These values can be referred to later in the query, or in the output list.
You can combine queries with and, or, and not, and you can test values using test.
The output list can consist of a series of strings and variables to print the variables in each successful match. For example, after the above match the output list:
("Chip:" ?c "has flash:" ?x)
will print:
Chip: attiny85 has flash: 8192
Examples
Here are some examples you can try with the ATtiny database:
- Find the price (in pence) of each chip with 8 Kbytes of flash:
> (answer '(and (flash ?c ?x) (price ?c ?k ?p) (test (= ?x 8192)))
'("Chip:" ?c "Package:" ?k "Price:" ?p))
Chip: attiny828 Package: tqfp Price: 84
Chip: attiny88 Package: pdip Price: 143
Chip: attiny88 Package: tqfp Price: 76
Chip: attiny861 Package: pdip Price: 110
Chip: attiny861 Package: soic Price: 92
Chip: attiny841 Package: soic Price: 78
Chip: attiny84 Package: pdip Price: 87
Chip: attiny84 Package: soic Price: 60
Chip: attiny85 Package: pdip Price: 90
Chip: attiny85 Package: soic Price: 72
- 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.
The database includes 1-off prices (in pence) for the most hobbyist-friendly packages such as PDIP and SOIC from https://uk.farnell.com/ and https://uk.rs-online.com/.
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 &optional 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 &optional binds)
(case (car expr)
(and (query-and (reverse (cdr expr)) binds))
(or (query-or (cdr expr) binds))
(not (query-not (second expr) binds))
(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 &optional binds)
(mapcan
(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)
(mapcan (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) (mapcan (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 query language program: Query language program
And here's the data for the ATtiny database: ATtiny database
Or get them from GitHub at: https://github.com/technoblogy/query-language
- ^ Graham, Paul "On Lisp" Prentice-Hall, New Jersey, 1994, pp. 246-254, available as a PDF Download On Lisp.
- ^ Graham, Paul "ANSI Common Lisp" Prentice-Hall, New Jersey, 1996, pp. 247-256.
- ^ Norvig, Peter "Paradigms of Artificial Intelligence Programming" Morgan Kaufmann Publishers, Inc, San Francisco, 1992, pp 348-387, available as a PDF paip-lisp on GitHub.