Built-in symbols

In most implementations of Lisp, both the built-in symbols and the user-defined symbols are stored in the Lisp workspace, which resides in RAM. However, with uLisp this clearly wasn't going to be possible, as I was targeting microcontrollers with very limited RAM; for example, my minimum target system was the Arduino Uno, with 32K bytes of flash program memory but only 2K bytes of RAM. The first released version of uLisp had 108 symbols with a total length of 594 characters, which would require a significant proportion of the RAM for a RAM-based lookup table. Version 4.0 of AVR uLisp has about 180 symbols, and still fits on the Arduino Uno.

The solution was to store the built-in symbols in a lookup table in program memory. This document describes the structure of that table, and the routines used to access symbols in the table.

The built-in symbols are defined by three components: a list of symbol names, a lookup table, and an enum list.

Update

4th April 2023: This description has been updated to reflect the revised structure of uLisp 4.4 onwards.

The list of symbol names

The built-in symbol names are defined by a list of string definitions; for example, here is a section of the list:

const char string105[] PROGMEM = "abs";
const char string106[] PROGMEM = "random";
const char string107[] PROGMEM = "max";
const char string108[] PROGMEM = "min";

The strings are defined as PROGMEM which on AVR platforms ensures that they are stored in program memory.

The lookup table

The lookup table is a constant array defined in program memory called lookup_table[]:

const tbl_entry_t lookup_table[] PROGMEM = {

Each entry in the lookup table is specified by the tbl_entry_t structure:

typedef const struct {
  PGM_P string;
  fn_ptr_type fptr;
  uint8_t minmax;
} tbl_entry_t;

These fields are as follows:

  • string is the symbol name; for example "random".
  • fptr is a pointer to the function defining the symbol.
  • minmax specifies the type of function, and the minimum and maximum number of arguments the function can have.

The string field references the appropriate string in the list of symbol names.

The fptr field is a pointer to a function that takes two Lisp objects, and returns a Lisp object. Its type is fn_ptr_type defined by:

typedef object *(*fn_ptr_type)(object *, object *);

The minmax field consists of three octal digits. The first octal digit specifies the type of function, the second defines the minimum number of arguments, and the third defines the maximum number of arguments. If the third digit is 7 the number of arguments is unlimited.

Here's a section of the lookup table:

  { string105, fn_abs, 0211, doc105 },
  { string106, fn_random, 0211, doc106 },
  { string107, fn_maxfn, 0217, doc107 },
  { string108, fn_minfn, 0217, doc108 },

For example, the entry for the Lisp function random references the string "random", the function pointer to the C routine fn_random(), the function type is 2 (a normal function), and the minimum and maximum number of arguments is 1.

Here's the function definition:

object *fn_random (object *args, object *env) {
  (void) env;
  int arg = checkinteger(RANDOM, first(args));
  return number(pseudoRandom(arg));
}

The arguments of all functions are:

  • args - the list of arguments.
  • env - the environment of local variables in which the function is being evaluated.

In this case the function simply calls the function pseudoRandom() with the first argument, similar to the Arduino function random(), converts the result to a Lisp number object, and returns it.

Routines

The following routines are used to perform functions with the lookup table.

Most of these routines contain alternative versions of some statements, omitted from the following examples, to cater for the fact that on the older AVR processors, data in program memory has to be accessed through the special functions pgm_read_byte() and pgm_read_word().

Also, on platforms other than AVR-Nano, uLisp now supports extension functions provided in a separate file. The mechanism to implement this is omitted from the following examples.

lookupbuiltin

The function lookupbuiltin() looks up a string in the lookup table, and returns the index of its entry, or ENDFUNCTIONS if no match is found:

builtin_t lookupbuiltin (char* n) {
  int entry = 0;
  while (entry < ENDFUNCTIONS) {
    if (strcasecmp_P(n, (char*)pgm_read_word(&lookup_table[entry].string)) == 0)
      return (builtin_t)entry;
    entry++;
  }
  return ENDFUNCTIONS;
}

lookupfn

The function lookupfn() looks up an entry in the lookup table, and returns the function entry point:

intptr_t lookupfn (builtin_t name) {
  return pgm_read_word(&lookup_table[name].fptr);
}

getminmax

The function getminmax() looks up an entry in the lookup table, and returns the minmax byte:

uint8_t getminmax (builtin_t name) {
  uint8_t minmax = pgm_read_byte(&lookup_table[name].minmax);
  return minmax;
}

Previous: Symbols

Next: Strings