Lisp macros quotation implementation in JavaScript

Question

I have basic scheme like lisp in JavaScript and have problem with backquote and quote macros, they evaluate symbols if they are at first element of the array like

> `(foo 10)

give error foo not found

it work for code like this

> (define x '(1 2 3))
> (print `(1 2 ,@x 4 5))

my eval function look like this:

function evaluate(code, env) {
  env = env || global_env;
  var value;
  if (typeof code === 'undefined') {
    return;
  }
  var first = code.car;
  var rest = code.cdr;
  if (first instanceof Pair) {
    value = evaluate(first, env);
  }
  if (typeof first === 'function') {
    value = first;
  }
  if (first instanceof Symbol) {
    value = env.get(first);
    if (value instanceof Macro) {
      return evaluate(value.invoke(rest, env), env);
    } else if (typeof value !== 'function') {
      throw new Error('Unknown function `' + first.name + '\'');
    }
  }
  if (typeof value === 'function') {
    var args = [];
    var node = rest;
    while (true) {
      if (node instanceof Pair) {
        args.push(evaluate(node.car, env));
        node = node.cdr;
      } else {
        break;
      }
    }
    var promises = args.filter((arg) => arg instanceof Promise);
    if (promises.length) {
      return Promise.all(args).then((args) => {
        return value.apply(env, args);
      });
    }
    return value.apply(env, args);
  } else if (code instanceof Symbol) {
    value = env.get(code);
    if (value === 'undefined') {
      throw new Error('Unbound variable `' + code.name + '\'');
    }
    return value;
  } else {
    return code;
  }
}

my Macro i just a function that return instance of Pair which is the same as input and code argument to evaluate, env is a instance of Environment that have function get that return functions or variables.

The macro for quasiquote look like this:

  quasiquote: new Macro(function(arg) {
    var env = this;
    function recur(pair) {
      if (pair instanceof Pair) {
        var eval_pair;
        if (Symbol.is(pair.car.car, 'unquote-splicing')) {
          eval_pair = evaluate(pair.car.cdr.car, env);
          if (!eval_pair instanceof Pair) {
            throw new Error('Value of unquote-splicing need to be pair')
          }
          if (pair.cdr instanceof Pair) {
            if (eval_pair instanceof Pair) {
              eval_pair.cdr.append(recur(pair.cdr));
            } else {
              eval_pair = new Pair(eval_pair, recur(pair.cdr));
            }
          }
          return eval_pair;
        }
        if (Symbol.is(pair.car, 'unquote-splicing')) {
          eval_pair = evaluate(pair.cdr.car, env);
          if (!eval_pair instanceof Pair) {
            throw new Error('Value of unquote-splicing need to be pair')
          }
          return eval_pair;
        }
        if (Symbol.is(pair.car, 'unquote')) {
          return evaluate(pair.cdr.car, env);
        }
        var car = pair.car;
        if (car instanceof Pair) {
          car = recur(car);
        }
        var cdr = pair.cdr;
        if (cdr instanceof Pair) {
          cdr = recur(cdr);
        }
        return new Pair(car, cdr);
      }
      return pair;
    }
    return recur(arg.car);
  }),

Should quote be hardcoded into evaluate function, that should not process the arguments and return them as is? Then backquote would return (quote symbol) for each symbol?

Answer 1

With help from @WillNess in comment I was able to resolve the problem, I need to add special case into the parser.

  if (first instanceof Symbol) {
    value = env.get(first);
    if (value instanceof Macro) {
      value = value.invoke(rest, env);
      if (value instanceof Constant) {
        return value.value;
      }
      return evaluate(value, env);
    }
  ...

and quasiquote Macro wrap the output with Constant. which is just:

function Constant(value) {
   this.value = value;
}

Answer 2

The intent of the quasiquote is to return code that can be evaluated to return a new form. For example:

`(a b ,@list (,c ,d))

... might expand as:

(append (list 'a 'b) list (list (list c d)))

... so that, during evaluation, it produces the expected list. You could find some ways to avoid allocating lists that are actually constants, like '(a b) instead of (list 'a 'b), but this implies the value built from quasi-quotation cannot be guaranteed to be always modifiable.

However, you seem to be expanding macros at runtime, evaluating when necessary its nested forms, and so in your case, the returned list will be different each time. In that case, I believe the approach taken with Constant should work.