A query language and ATtiny database written in uLisp


#1

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


#2

I’ve now also tested the application using the ESP32 version of uLisp running on the Adafruit HUZZAH32 ESP32 Feather, see ESP 32 boards. It should also work on the other ESP32 boards. As for the Arduino Due, 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 ESP32 section to:

#define SYMBOLTABLESIZE 1024

#3

I’ve now updated the database to include price information for the most hobbyist-friendly packages such as PDIP and SOIC.

For example, you can now ask a question such as:

  • Find the price 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

For the prices I took the lowest 1-off price, in pence, from https://uk.farnell.com/.

You can get the latest version of the uLisp query language program, and the ATtiny database, from GitHub at:

A query language and ATtiny database written in uLisp


#4

The Query Language program has been updated to take advantage of the new features in uLisp Version 2.6, and there’s an updated version of this description at:

Query language