Read, Evaluate, Print

16th April 2017: This description has been updated to match uLisp 1.8.

The input you type at the ">" prompt is read, evaluated, and printed in a loop; hence its alternative name: the REPL.

This is implemented by the C function repl(). A simplified version of this is as follows:

void repl(object *env) {
  for (;;) {
    pfstring(F("> "));
    object *line = read();
    printobject(eval(line, env));
} }

Read

When you enter an item at the ">" prompt it is read in by the C function read(), which returns an object corresponding to what you entered. The C function read() is also used by the Lisp function read.

The read() function calls nextitem() to read the next token in the input line. There are then these possibilities:

  • If the token is an opening bracket, read() calls readrest(), which continues reading tokens, consing them into a list, until it finds a matching closing bracket.
  • If the token is a single quote, it returns a list consisting of QUOTE followed by the next item read.
  • Otherwise the token is an atom, and it is returned as the value of read().

The function nextitem() handles the tokens '(', ')', '\', and '.', integers, and symbols.

Evaluate

The main function in uLisp is eval(), which evaluates an item and returns the result. It is called to evaluate the item you type at the ">" prompt, and is also called by the Lisp function eval.

First eval() invokes the garbage collector, to ensure that there is as much space as possible for the evaluation:

object *eval (object *form, object *env) {
  int TC=0;
  EVAL:
  // Enough space?
  if (Freespace < 20) gc(form, env);

If the form being evaluated is nil, eval() simply returns nil:

if (form == NULL) return nil;

If the form is a number or string eval() just returns it:

  if ((form->type == NUMBER) || (form->type == STRING)) return form;

If the form is a symbol it is first looked up in the local environment, env. If it's found, the value is returned; otherwise it is looked up in the global environment GlobalEnv, and again its value is returned. Otherwise, if the name is the number of one of the built-in functions the symbol is simply returned. Otherwise an "undefined" error is given:

  if (form->type == SYMBOL) {
    symbol_t name = form->name;
    if (name == NIL) return nil;
    object *pair = value(name, env);
    if (pair != NULL) return cdr(pair);
    pair = value(name, GlobalEnv);
    if (pair != NULL) return cdr(pair);
    else if (name <= ENDFUNCTIONS) return form;
    error2(form, F("undefined"));
  }

By this time we know that the form must be a list. We set function to the first item in the list, and args to the rest of the list:

  // It's a list
  object *function = car(form);
  object *args = cdr(form);

  // List starts with a symbol?
  if (function->type == SYMBOL) {
    unsigned int name = function->name;

If function is a symbol we set name to its index number, and check for the special cases let, let*, and lambda. These can modify the environment, and so it's simpler to code them in-line.

Otherwise we check for one of the built-in functions. There are three types of built-in function, and the difference is explained in the following sections:

Special forms

The special forms have names beginning with sp; for example, sp_setq(). We look up the index number of the function in the table of built-in functions, pass it a list of their arguments unevaluated, and return a result that becomes the value of the function:

Their number lies between SPECIAL_FORMS and TAIL_FORMS:

 if ((name > SPECIAL_FORMS) && (name < TAIL_FORMS)) {
      return ((fn_ptr_type)lookupfn(name))(args, env);
    }

Tail forms

The tail forms have names beginning with tf; for example, tf_if(). Like the special forms, we look up the index number of the function in the table of built-in functions, and pass it a list of their arguments unevaluated. However, these return a result that needs to be evaluated to become the value of the function, so after calling them eval() is reentered with form set to the result to be evaluated:

Their number lies between TAIL_FORMS and FUNCTIONS:

    if ((name > TAIL_FORMS) && (name < FUNCTIONS)) {
      form = ((fn_ptr_type)lookupfn(name))(args, env);
      TC = 1;
      goto EVAL;
    } 

Functions

Otherwise the function is a normal function, with a name beginning with fn; for example, fn_cons(). Its arguments are first evaluated before being passed to the function.

  // Evaluate the parameters - result in head
  object *fname = car(form);
  int TCstart = TC;
  object *head = cons(eval(car(form), env), NULL);
  push(head, GCStack); // Don't GC the result list
  object *tail = head;
  form = cdr(form);
  int nargs = 0;

  while (form != NULL){
    object *obj = cons(eval(car(form),env),NULL);
    cdr(tail) = obj;
    tail = obj;
    form = cdr(form);
    nargs++;
  }
    
  function = car(head);
  args = cdr(head);

If the value of the function name is a symbol, its index is looked up in the table of built-in functions, and the result is returned:

  if (function->type == SYMBOL) {
    symbol_t name = function->name;
    if (name >= ENDFUNCTIONS) error2(fname, F("is not valid here"));
    if (nargs<lookupmin(name)) error2(fname, F("has too few arguments"));
    if (nargs>lookupmax(name)) error2(fname, F("has too many arguments"));
    object *result = ((fn_ptr_type)lookupfn(name))(args, env);
    pop(GCStack);
    return result;
  }

The only remaining case is when the value of the name of the function is a list, as in a user-defined function. For example, if we define a function:

(defun x2y (x y) (* x x y))

then in the call:

(x2y 3 2)

the value of x2y is:

(lambda (x y) (* x x y))

This case is handled by the following code:

  if (listp(function) && issymbol(car(function), LAMBDA)) {
    form = closure(TCstart, fname, NULL, cdr(function), args, &env);
    pop(GCStack);
    TC = 1;
    goto EVAL;
  }

The work is done by the function closure() which evaluates the closure and returns the result. It takes the following six parameters:

  • tail, a flag indicating whether the function is a tail call. 
  • fname, a pointer to the name of the function, used for error messages; in this case x2y.
  • state, a pointer to the state stored for closures.
  • function, a pointer to the function body; in this case ((x y) (* x x y)).
  • args, a pointer to the arguments; in this case (3 2).
  • env, a pointer to the environment stack of local and global variables and values.

The C function closure() is also used by the function apply(). This is called by the functions fn_apply(), fn_funcall(), fn_mapc(), and fn_mapcar() which implement the uLisp functions apply, funcall, mapc, and mapcar respectively.

Print

The last part of the REPL loop is a call to printobject() to print the result of evaluating the input line. This is also called by the Lisp functions print and printc. This works as follows:

  • If the argument form is nil it simply prints "nil".
  • If the argument is a list starting with the symbol closure it prints "<closure>".
  • If the argument is a list it prints "(", followed by printobject(car(form)), followed by printobject(cdr(form)), followed by ")".
  • If the argument is a number it is printed as an integer.
  • If the argument is a symbol it is printed as a string.
  • If the argument is a stream it prints either <spi-stream>, <i2c-stream>, or <serial-stream> as appropriate.
  • Otherwise it generates an error.