Contactez-nous au 01 83 62 88 34

Extended RAM

The original objective in designing uLisp was to make it possible to run Lisp on a microcontroller with a limited amount of RAM, from the 2 Kbytes on the Arduino Uno upwards.

However, several ESP32 microcontrollers now include an additional PSRAM (pseudo-static RAM) extension, and release 4.7 of uLisp has been updated to take advantage of all the RAM on these platforms. This page describes the changes that were needed to do this.

It supports ESP32 variants with 2 Mbytes or 8 Mbytes of PSRAM.

In the following description the boards with PSRAM are referred to as large-RAM, and the boards without PSRAM as small-RAM, since the technique applies to any type of RAM extension.

Interning symbols

The small-RAM version of uLisp interns symbols when they are read in, either by the REPL or by functions such as read or read-from-string, to ensure that there is only a unique occurrence of each symbol in the workspace. This results in a more efficient usage of the workspace by programs.

Here are some examples showing the workspace (in objects) taken by three benchmarks on each of the versions of uLisp (see Benchmarks for the programs):

Program	Small-RAM	Large-RAM
tak	54	72
q2	64	81
sieve	107	127

Interning symbols reduces the amount of workspace needed for a program by up to 25%.

The small-RAM version of uLisp achieves this by scanning through the workspace to check for the existing occurrence of a symbol with the same name, and if found, returns it rather than creating a new symbol:

object *intern (symbol_t name) {
  for (int i=0; i<WORKSPACESIZE; i++) {
    object *obj = &Workspace[i];
    if (obj->type == SYMBOL && obj->name == name) return obj;
  }
  return symbol(name);
}

Interning symbols in this way only gives an overhead once, when the symbol is read in. However, on a large-RAM platform with more than about 50000 objects of workspace, scanning through the entire workspace for each symbol would give an objectionable delay when reading in a program.

The solution is that in the large-RAM version of uLisp intern() simply creates a new symbol, even if one already exists in the workspace:

object *intern (symbol_t name) {
  return symbol(name);
}

The slightly less efficient use of the workspace is not a problem when there is plenty of RAM available.

The similar routine internlong() interns a long symbol from a C string in a buffer. The function eqsymbols() compares a symbol in the workspace with the string in the buffer:

object *internlong (char *buffer) {
  for (int i=0; i<WORKSPACESIZE; i++) {
    object *obj = &Workspace[i];
    if (obj->type == SYMBOL && longsymbolp(obj) && eqsymbols(obj, buffer)) return obj;
  }
  object *obj = lispstring(buffer);
  obj->type = SYMBOL;
  return obj;
}

Here's the large-RAM version:

object *internlong (char *buffer) {
  object *obj = lispstring(buffer);
  obj->type = SYMBOL;
  return obj;
}

On small-RAM versions of uLisp it would also be possible to intern other objects, such as numbers and characters, but the savings made by doing this would typically be minimal.

Testing whether symbols are equal 

The advantage of the small-RAM approach is that, because there is a unique copy of each symbol in the workspace, to test whether two symbols are equal it's only necessary to test whether their addresses are equal. In the large-RAM version of uLisp we need an additional function eqsymbol() to compare symbols:

bool eqsymbol (symbol_t sym1, symbol_t sym2) {
  if (!longnamep(sym1) && !longnamep(sym2)) return (sym1 == sym2);  // Same short symbol
  if (longnamep(sym1) && longnamep(sym2)) return eqlongsymbol(sym1, sym2);//Same long symbol
  return false;
}

where eqlongsymbol() compares two long symbols word by word:

bool eqlongsymbol (symbol_t sym1, symbol_t sym2) {
  object *arg1 = (object *)sym1; object *arg2 = (object *)sym2;
  while ((arg1 != NULL) || (arg2 != NULL)) {
    if (arg1 == NULL || arg2 == NULL) return false;
    if (arg1->chars != arg2->chars) return false;
    arg1 = car(arg1); arg2 = car(arg2);
  }
  return true;
}

Looking up a variable in the environment

One function affected by this is value(), which looks up the value of a variable in the environment. In the small-RAM version of uLisp this can simply comparing symbol addresses:

object *value (symbol_t n, object *env) {
  while (env != NULL) {
    object *pair = car(env);
    if (pair != NULL && car(pair)->name == n) return pair;
    env = cdr(env);
  }
  return nil;
}

In the large-RAM version of uLisp it's necessary to compare symbol names by calling eqsymbol():

object *value (symbol_t n, object *env) {
  while (env != NULL) {
    object *pair = car(env);
    if (pair != NULL && eqsymbol(car(pair)->name, n)) return pair;
    env = cdr(env);
  }
  return nil;
}

Testing equality

Another function affected by this is eq(), which implements the Lisp eq function. In the small-RAM version it's only necessary to test whether the addresses of two symbols are equal:

bool eq (object *arg1, object *arg2) {
  if (arg1 == arg2) return true;  // Same object
  if ((arg1 == nil) || (arg2 == nil)) return false;  // Not both values
  if (arg1->cdr != arg2->cdr) return false;  // Different values
  if (symbolp(arg1) && symbolp(arg2)) return true;  // Same symbol
  if (integerp(arg1) && integerp(arg2)) return true;  // Same integer
  if (floatp(arg1) && floatp(arg2)) return true; // Same float
  if (characterp(arg1) && characterp(arg2)) return true;  // Same character
  return false;
}

In the large-RAM version of uLisp it's necessary to test whether their names are equal by calling eqsymbol():

bool eq (object *arg1, object *arg2) {
  if (arg1 == arg2) return true;  // Same object
  if ((arg1 == nil) || (arg2 == nil)) return false;  // Not both values
  if (symbolp(arg1) && symbolp(arg2)) return eqsymbol(arg1->name, arg2->name);//Same symbol?
  if (arg1->cdr != arg2->cdr) return false;  // Different values
  if (integerp(arg1) && integerp(arg2)) return true;  // Same integer
  if (floatp(arg1) && floatp(arg2)) return true; // Same float
  if (characterp(arg1) && characterp(arg2)) return true;  // Same character
  return false;
}

Implementation

These changes are merged into a single uLisp source file using conditional directives:

#if defined(BOARD_HAS_PSRAM)

The only other change is the way in which the extra RAM is allocated. On the ESP32 platforms it is achieved by the statements:

if (!psramInit()) { Serial.print("the PSRAM couldn't be initialized"); for(;;); }
Workspace = (object*) ps_malloc(WORKSPACESIZE);

Afterthought

The previous function eqsymbol() assumes that there couldn't be a long and a short symbol with the same name. For example, cat is a valid name for a short symbol, packed into a single word. Could a long symbol exist with the name cat?

Although this is technically possible, uLisp ensures that it can't happen, because the only way to create a symbol is via the REPL, or the functions read or read-from-string, which automatically create a short symbol if the name is a valid short symbol.