Read, Evaluate, Print

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 (;;) {
    pserial('>'); pserial(' ');
    line = eval(line, env);
    pfl(pserial);
    printobject(line, pserial);
    pfl(pserial);
    pln(pserial);
  }
}

Update

4th April 2023: This description has been updated to reflect uLisp 4.4.

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 <= WORKSPACESIZE>>4) gc(form, env);

If less than 1/16 of the workspace is available a garbage collection is invoked.

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 (symbolp(form)) {
    symbol_t name = form->name;
    object *pair = value(name, env);
    if (pair != NULL) return cdr(pair);
    pair = value(name, GlobalEnv);
    if (pair != NULL) return cdr(pair);
    else if (builtinp(name)) return form;
    Context = NIL;
    error(PSTR("undefined"), form);
  }

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);

If the list starts with a built-in symbol we set name to its index in the list of built-in symbols:

  // List starts with a builtin symbol?
  if (symbolp(function) && builtinp(function->name)) {
    builtin_t name = builtin(function->name);

We then 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, identified by their function type number in minmax. The difference is explained in the following sections:

Special forms

The special forms have names beginning with sp; for example, sp_setq(). They have a function type of SPECIAL_FORMS. 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:

    if (fntype == SPECIAL_FORMS) {
      Context = name;
      return ((fn_ptr_type)lookupfn(name))(args, env);
    }

The global variable Context is set to name, so we can report the context in error messages.

Tail forms

The tail forms have names beginning with tf; for example, tf_if(). They have a function type of TAIL_FORMS. 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:

    if (fntype == TAIL_FORMS) {
      Context = name;
      form = ((fn_ptr_type)lookupfn(name))(args, env);
      TC = 1;
      goto EVAL;
    }

Invalid functions

If the built-in name is not a valid function, such as nil, it has a function type of OTHER_FORMS, and will give an error:

    if (fntype == OTHER_FORMS) error(PSTR("can't be used as a function"), function);

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(fname, 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 (symbolp(function)) {
    builtin_t bname = builtin(function->name);
    if (!builtinp(function->name)) error(PSTR("not valid here"), fname);
    Context = bname;
    checkminmax(bname, nargs);
    object *result = ((fn_ptr_type)lookupfn(bname))(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 (omitting the processing of tracing):

    if (isbuiltin(car(function), LAMBDA)) {
      form = closure(TCstart, name, 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. 
  • name, a pointer to the name of the function, used for error messages; in this case x2y.
  • 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 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:

void printobject (object *form, pfun_t pfun) {
  if (form == NULL) pfstring(PSTR("nil"), pfun);
  else if (listp(form) && isbuiltin(car(form), CLOSURE)) pfstring(PSTR("<closure>"), pfun);
  else if (listp(form)) plist(form, pfun);
  else if (integerp(form)) pint(form->integer, pfun);
  else if (symbolp(form)) { if (form->name != sym(NOTHING)) printsymbol(form, pfun); }
  else if (characterp(form)) pcharacter(form->chars, pfun);
  else if (stringp(form)) printstring(form, pfun);
  else if (streamp(form)) pstream(form, pfun);
  else error2(PSTR("error in print"));
}

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 is printed by plist().
  • If the argument is a number it is printed as an integer by pint().
  • If the argument is a symbol it is printed by printsymbol().
  • If the argument is a character it is printed by pcharacter().
  • If the argument is a string it is printed by printstring().
  • If the argument is a stream it is printed by pstream().
  • Otherwise it generates an error.

The function printobject() is also called by the Lisp functions print and printc


Previous: Arrays

Next: Garbage collection