babyLisp

index.js

const Token = {
  operator: "operator",
  parensOpen: "parensOpen",
  parensClose: "parensClose",
  number: "number"
};

const Operator = {
  add: "add",
  subtract: "subtract",
  multiply: "multiply",
  divide: "divide"
};

const tokenize = (input) =>
  input
    .replace(/(\(|\))/g, " $1 ")
    .toLowerCase()
    .split(/\s+/)
    .filter(Boolean)
    .map((token) => {
      if (token === "(") {
        return { type: Token.parensOpen };
      }
      if (token === ")") {
        return { type: Token.parensClose };
      }
      if (Object.keys(Operator).includes(token)) {
        return { type: Token.operator, value: Operator[token] };
      }
      const numberMaybe = Number(token);
      if (Number.isNaN(numberMaybe)) {
        throw new Error(`Incorrect token "${token}"`);
      }
      return { type: Token.number, value: numberMaybe };
    });

const NodeType = {
  expression: "expressionNode",
  number: "numberNode"
};

let parse = (tokens) => {
  const gatherExpressionTokens = (_tokens) => {
    if (_tokens[0].type === Token.number) {
      return [[_tokens[0]], 1];
    }
    let balance = null;
    let index = 0;
    let result = [];
    while (index < _tokens.length && balance !== 0) {
      if (balance === null) {
        balance = 0;
      }
      result.push(_tokens[index]);
      if (_tokens[index].type === Token.parensOpen) {
        balance -= 1;
      }
      if (_tokens[index].type === Token.parensClose) {
        balance += 1;
      }
      index += 1;
    }
    if (balance !== 0) {
      throw new Error("Unexpected unbalanced parens");
    }
    return [result, index];
  };

  const parseExpression = (expressionTokens) => {
    let firstToken = expressionTokens[0];
    if (firstToken.type === Token.number) {
      return { type: NodeType.number, value: firstToken.value };
    }

    const expression = { type: NodeType.expression };

    if (firstToken.type !== Token.parensOpen) {
      throw new Error(
        `Unexpected token "${JSON.stringify(firstToken)}", expected "("`
      );
    }
    let opToken = expressionTokens[1];
    if (opToken.type !== Token.operator) {
      throw new Error(
        `Unexpected token "${JSON.stringify(opToken)}", expected operator`
      );
    }
    expression.operator = opToken.value;
    let [leTokens, reIndex] = gatherExpressionTokens(expressionTokens.slice(2));
    let [reTokens] = gatherExpressionTokens(
      expressionTokens.slice(reIndex + 2)
    );

    expression.leftExpression = parseExpression(leTokens);
    expression.rightExpression = parseExpression(reTokens);

    return expression;
  };

  return parseExpression(tokens);
};

const evaluators = {
  [Operator.add]: (a, b) => a + b,
  [Operator.subtract]: (a, b) => a - b,
  [Operator.multiply]: (a, b) => a * b,
  [Operator.divide]: (a, b) => a / b
};

const eval = (expression) => {
  if (expression.type === NodeType.number) {
    return expression.value;
  }

  const evaluator = evaluators[expression.operator];
  const leftOperand = eval(expression.leftExpression);
  const rightOperand = eval(expression.rightExpression);
  return evaluator(leftOperand, rightOperand);
};

const babyLisp = (input) => {
  const tokens = tokenize(input);
  const ast = parse(tokens);
  const result = eval(ast);
  return result;
};

module.exports.babyLisp = babyLisp;
module.exports.tokenize = tokenize;
module.exports.parse = parse;
module.exports.eval = eval;
module.exports.NodeType = NodeType;

prettify.js

const { NodeType, parse, tokenize } = require("./");

const prettify = (code) => {
  const ast = parse(tokenize(code));

  const prettifyExpression = (expression) => {
    if (expression.type === NodeType.number) {
      return `${expression.value}`;
    }

    return `(${expression.operator} ${prettifyExpression(
      expression.leftExpression
    )} ${prettifyExpression(expression.rightExpression)})`;
  };

  return prettifyExpression(ast);
};

module.exports.prettify = prettify;

test.js

const babyLisp = require("./").babyLisp;
const prettify = require("./prettify").prettify;

console.log("Evaluation tests");
[
  ["(add 1 2)", 3],
  ["(multiply 4 (add 2 3))", 20],
  ["(subtract ( divide 4 2 ) 2.5)", -0.5],
  ["(multiply (add 4 2) (subtract 10 5))", 30],
  ["5", 5]
].forEach(([code, expected]) => {
  let result = babyLisp(code);
  if (result !== expected) {
    console.error(
      `FAIL: "${code}" is evaluated to equal "${result}", "${expected}" expected`
    );
    process.exitCode = 1;
  } else {
    console.log(`SUCCESS: "${code}" is evaluated to equal "${result}"`);
  }
});

console.log("\nEvaluation errors tests");
[
  [
    "(5 0 0)",
    'Unexpected token "{"type":"number","value":5}", expected operator'
  ]
].forEach(([code, expectedError]) => {
  try {
    babyLisp(code);
  } catch (error) {
    if (error.message !== expectedError) {
      console.error(
        `FAIL: "${code}" is evaluated to throw "${error.message}" expected error is "${expectedError}"`
      );
      process.exitCode = 1;
    } else {
      console.log(
        `SUCCESS: "${code}" is evaluated to throw "${error.message}"`
      );
    }
  }
});

console.log("\nPrettification tests");
[["( \tadd 1  (add 2 3\t)  )", "(add 1 (add 2 3))"]].forEach(
  ([code, expected]) => {
    let result = prettify(code);
    if (result !== expected) {
      console.error(
        `FAIL: "${code}" is prettified to equal "${result}", "${expected}" expected`
      );
      process.exitCode = 1;
    } else {
      console.log(`SUCCESS: "${code}" is prettified to equal "${result}"`);
    }
  }
);