lisp.js

const isWhitespace = (char) =>
  char === ' ' || char === '\n' || char === '\t' || char === '\r';

const isParen = (char) => char === '(' || char === ')';

const getLiteralType = (literal) => {
  if (literal[0] === '"' && literal[literal.length - 1] === '"') {
    return 'string';
  }

  if (!isNaN(+literal)) {
    return 'number';
  }

  return 'identifier';
};

// Transforms code into tokens
const tokenizer = (code) => {
  const tokens = [];

  for (let i = 0, n = code.length; i < n; i++) {
    let curr = code[i];

    // Eat whitespace
    if (isWhitespace(curr)) {
      continue;
    }

    // Parens
    if (isParen(curr)) {
      tokens.push({ type: 'paren', value: curr });
      continue;
    }

    // Literals
    let literal = '';
    while (i < n && !isWhitespace(curr) && !isParen(curr)) {
      literal += curr;
      i++;
      curr = code[i];
    }

    // Restore whitespace or paren
    i--;

    if (literal) {
      tokens.push({ type: getLiteralType(literal), value: literal });
      continue;
    }

    throw new Error(`Unhandled character: ${curr}`);
  }

  return tokens;
};

const parser = (tokens) => {
  let i = 0;

  const parseExpression = () => {
    let token = tokens[i];

    // NumericLiteral
    if (token.type === 'number') {
      i++;

      return {
        type: 'NumericLiteral',
        value: parseFloat(token.value, 10),
      };
    }

    if (token.type === 'string') {
      i++;

      return {
        type: 'StringLiteral',
        value: token.value.substring(1, token.value.length - 1),
      };
    }

    if (token.type === 'identifier') {
      i++;

      return {
        type: 'Identifier',
        value: token.value,
      };
    }

    // CallExpression
    if (token.type === 'paren' && token.value === '(') {
      // Eat paren
      token = tokens[++i];

      const node = {
        type: 'Expression',
        params: [],
      };

      while (
        token &&
        (token.type !== 'paren' ||
          (token.type === 'paren' && token.value !== ')'))
      ) {
        node.params.push(parseExpression());
        token = tokens[i];
      }

      if (!token) {
        throw new Error(`Unexpected end of parsing`);
      }

      // Eat closing paren
      i++;

      return node;
    }

    if (token.type === 'paren' && token.value === ')') {
      throw new Error(`Mismatched paren`);
    }

    // Unknown
    throw new Error(`Unknown token type: ${token.type}`);
  };

  const n = tokens.length;
  const program = { type: 'Program', body: [] };

  while (i < n) {
    program.body.push(parseExpression());
  }

  return program;
};

class Context {
  constructor(vars = {}, parent = null) {
    this.vars = vars;
    this.parent = parent;
  }

  get(key) {
    if (key in this.vars) {
      return this.vars[key];
    }

    if (this.parent) {
      return this.parent.get(key);
    }
  }

  set(key, value) {
    this.vars[key] = value;
  }
}

// Transforms ast into result
const interpreter = (ast) => {
  const evalExpression = (expr, context) => {
    if (Array.isArray(expr)) {
      return expr.map((e) => evalExpression(e, context));
    }

    if (expr.type === 'NumericLiteral' || expr.type === 'StringLiteral') {
      return expr.value;
    }

    if (expr.type === 'Identifier') {
      const value = context.get(expr.value);

      if (typeof value !== 'undefined') {
        return value;
      }
    }

    if (expr.type === 'Expression') {
      const name = expr.params[0];
      const fn = name && vtable[name.value];

      // Call expression
      const params = expr.params.slice(1);
      return fn(params, context, (e) => evalExpression(e, context));
    }

    throw new Error(`Unexpected ${expr.type}: ${expr.value}`);
  };

  const vtable = {
    // Math
    '+': (args, ctx, eval) => eval(args).reduce((m, e) => m + e, 0),
    '*': (args, ctx, eval) => eval(args).reduce((m, e) => m * e, 1),
    // Utilities
    print: (args, ctx, eval) => process.stdout.write(eval(args).join(' ')),
    println: (args, ctx, eval) => console.log(...eval(args)),
    // Lists
    list: (args, ctx, eval) => Array.from(eval(args)),
    first: (args, ctx, eval) => eval(args[0]),
    // Vars
    let: (args, ctx, eval) => ctx.set(args[0].value, eval(args[1])),
    // Logic
    if: (args, ctx, eval) => (eval(args[0]) ? eval(args[1]) : eval(args[2])),
    not: (args, ctx, eval) => !eval(args[0]),
    and: (args, ctx, eval) => args.every(arg => eval(arg)),
    or: (args, ctx, eval) => args.some(arg => eval(arg)),
  };

  return evalExpression(ast.body, new Context());
};

const execute = (code, options = {}) => {
  const debug = (...args) => options.debug && console.log(...args);
  debug('execute', code, '\n---');

  const tokens = tokenizer(code);
  debug('tokens', tokens);

  const ast = parser(tokens);
  debug('ast', ast);

  const result = interpreter(ast);
  debug('result', result, '\n');

  return result;
};

//execute('(+ 2 3)', { debug: true });
//execute('(println (list 1)) (+ 2 3) (println 23) (list 1 2 3)', { debug: true });
//execute('(let x 2) (println x)', { debug: true });
//execute('(let x 2) (println x)', { debug: true });
execute('(let x 10) (println x)', { debug: true });
//execute('(and (not 0) 1) (or 1 1)', { debug: true });