Simple Evaluator vs Compile to Closure Evaluator benchmark

ccAndEval.js

// calculates factorials of numbers from 1 to 20
const code = 
  ["do",
    ["var", "N", 20],
    ["var", "i", 1],
    ["while", ["<=", "i", "N"],
      ["do",
        ["var", "n", "i"],
        ["var", "f", 1],
        ["while", [">", "n", 0],
          ["do",
            ["set!", "f", ["*", "f", "n"]],
            ["set!", "n", ["-", "n", 1]]]],
        ["println", "f"],
        ["set!", "i", ["+", "i", 1]]]]];
// =====


// env utils
function newEnv(parent = null) {
  return { __PARENT__: parent };
}

function envLookup(env, name) {
  if (name in env)
    return env[name];
  else if (env.__PARENT__)
    return envLookup(env.__PARENT__, name);
  else
    throw new Error("Not defined: " + name);
}

function envBind(env, name, val) {
  env[name] = val;
}

function envSet(env, name, newval) {
  if (name in env)
    env[name] = newval;
  else if (env.__PARENT__)
    envSet(env.__PARENT__, name, newval);
  else
    throw new Error("Not defined: " + name);
}

function envExtend(env) {
  return newEnv(env);
}
// =====


// simple evaluator
function walk(expr, env) {
  const t = typeof expr;
  if (t === "number")
    return expr;
  else if (t === "string")
    return envLookup(env, expr);
  else if (Array.isArray(expr)) {
    const [op, ...args] = expr;
    if (op === "do") {
      const newEnv = envExtend(env);
      let res = null;
      for (const subexpr of args)
        res = walk(subexpr, newEnv);
      return res;
    } else if (op === "var") {
      const [name, valExpr] = args;
      const val = walk(valExpr, env);
      return envBind(env, name, val);
    } else if (op === "set!") {
      const [name, valExpr] = args;
      const val = walk(valExpr, env);
      return envSet(env, name, val);
    } else if (op === "while") {
      const [condExpr, bodyExpr] = args;
      while (walk(condExpr, env))
        walk(bodyExpr, env);
      return;
    } else if (op === "println") {
      const argExpr = args[0];
      const arg = walk(argExpr, env);
      return console.log(arg);
    } else if (op === "<=") {
      const [left, right] = args.map(arg => walk(arg, env));
      return left <= right;
    } else if (op === ">") {
      const [left, right] = args.map(arg => walk(arg, env));
      return left > right;
    } else if (op === "+") {
      const [left, right] = args.map(arg => walk(arg, env));
      return left + right;
    } else if (op === "-") {
      const [left, right] = args.map(arg => walk(arg, env));
      return left - right;
    } else if (op === "*") {
      const [left, right] = args.map(arg => walk(arg, env));
      return left * right;
    } else
      throw new Error("Invalid operator: " + op);
  } else
    throw new Error("Invalid expression: " + expr);
}
// =====


// compile to closure evaluator
function cc(expr) {
  const t = typeof expr;
  if (t === "number")
    return _ => expr;
  else if (t === "string")
    return env => envLookup(env, expr);
  else if (Array.isArray(expr)) {
    const [op, ...args] = expr;
    if (op === "do") {
      const subclosures = args.map(cc);
      return env => {
        const newEnv = envExtend(env);
        let res = null;
        for (const subclosure of subclosures)
          res = subclosure(newEnv);
        return res;
      }
    } else if (op === "var") {
      const [name, valExpr] = args;
      const valClosure = cc(valExpr);
      return env => envBind(env, name, valClosure(env));
    } else if (op === "set!") {
      const [name, valExpr] = args;
      const valClosure = cc(valExpr);
      return env => envSet(env, name, valClosure(env));
    } else if (op === "while") {
      const [condClosure, bodyClosure] = args.map(cc);
      return env => {
        while (condClosure(env))
          bodyClosure(env);
        return;
      };
    } else if (op === "println") {
      const argExpr = args[0];
      const argClosure = cc(argExpr);
      return env => console.log(argClosure(env));
    } else if (op === "<=") {
      const [leftClosure, rightClosure] = args.map(cc);
      return env => leftClosure(env) <= rightClosure(env);
    } else if (op === ">") {
      const [leftClosure, rightClosure] = args.map(cc);
      return env => leftClosure(env) > rightClosure(env);
    } else if (op === "+") {
      const [leftClosure, rightClosure] = args.map(cc);
      return env => leftClosure(env) + rightClosure(env);
    } else if (op === "-") {
      const [leftClosure, rightClosure] = args.map(cc);
      return env => leftClosure(env) - rightClosure(env);
    } else if (op === "*") {
      const [leftClosure, rightClosure] = args.map(cc);
      return env => leftClosure(env) * rightClosure(env);
    } else
      throw new Error("Invalid operator: " + op);
  } else
    throw new Error("Invalid expression: " + expr);
}

function ccAndEval(expr, env) {
  const closure = cc(expr);
  return closure(env);
}
// =====


// benchmark
function time(tag, f) {
  console.time(tag);
  const res = f();
  console.timeEnd(tag);
  return res;
}

time("walk", () => walk(code, newEnv()));
time("ccAndEval", () => ccAndEval(code, newEnv()));