Lambda-Calculus Evaluator

"use strict";

function Lexer(lexemes, end_lexeme) {
  this.lexemes = lexemes;
  this.lex = function (str) {
    str = str.replace(/\(|\)|=>/g, " $& "); // Parentheses
    str = str.replace(/\/\/[^\n]*/g, ""); // Comments
    this.array = str.trim().split(/\s+/);
    this.array = this.array.map(
      el => new (this.lexemes.find(lex => lex.is(el))) (el));
    this.array.push(new end_lexeme());
    this.index = 0;
  }
  this.advance = function () { lexer.index++; };
  this.peek = function () {
    if (lexer.index === lexer.array.length) return null;
    else                                    return lexer.array[lexer.index];
  };
}

function FnLexeme (fn) { this.name = "fn"; }
FnLexeme.is = str => str === "fn";

function ArrowLexeme (arrow) { this.name = "=>"; }
ArrowLexeme.is = str => str === "=>";

function LParenLexeme (lpar) { this.name = "("; }
LParenLexeme.is = str => str === "(";

function RParenLexeme (rpar) { this.name = ")"; }
RParenLexeme.is = str => str === ")";

function EndLexeme (end) { this.name = "$"; }
EndLexeme.is = str => false;

function VarLexeme (variable) { this.name = variable; }
VarLexeme.is = str => true;

var lexer = new Lexer([FnLexeme, ArrowLexeme, LParenLexeme,
                       RParenLexeme, VarLexeme], EndLexeme);

function Parser(lexer) {
  this.lexer = lexer;

  this.parse = function (str) {
    this.states = [0];
    this.values = [];
    this.lexer.lex(str);
    let accepted = false;
    while (!accepted &&
           this.lexer.peek() !== null) {
      let lexeme = this.lexer.peek();
      let action = lexeme.action[this.states.top()];
      accepted = action(this.states, this.values, this.lexer);
    };

    return accepted && this.values.top();
  };
}

var parser = new Parser(lexer);

Array.prototype.top = function () { return this[this.length - 1]; };
Array.prototype.empty = function () { return this.length === 0; };

FnLexeme.prototype.action =
  [Shift(2),   ParseError, ParseError, ParseError, Shift(2),
   ParseError, ParseError, ParseError, ParseError, ParseError,
   Shift(2),   ParseError, ParseError, ParseError, ParseError];

ArrowLexeme.prototype.action =
  [ParseError, ParseError, ParseError, Shift(4),  ParseError,
   ParseError, ParseError, ParseError, ParseError, ParseError,
   ParseError, ParseError, ParseError, Reduce9,    Reduce8];

LParenLexeme.prototype.action =
  [Shift(10),  ParseError, ParseError, ParseError, Shift(10),
   ParseError, Shift(10),  Reduce4  ,  Reduce5,    Reduce6,
   Shift(10),  ParseError, Reduce7,    ParseError, ParseError];

RParenLexeme.prototype.action =
  [ParseError, ParseError, ParseError, ParseError, ParseError,
   Reduce2,    Reduce3,    Reduce4,    Reduce5,    Reduce6,
   ParseError, Shift(12),  Reduce7,    ParseError, ParseError];

EndLexeme.prototype.action =
  [ParseError, Accept,     ParseError, ParseError, ParseError,
   Reduce2,    Reduce3,    Reduce4,    Reduce5,    Reduce6,
   ParseError, ParseError, Reduce7,    ParseError, ParseError];

VarLexeme.prototype.action =
  [Shift(9),   ParseError, Shift(13),  ParseError, Shift(9),
   ParseError, Shift(9),   Reduce4,    Reduce5,    Reduce6,
   Shift(9),   ParseError, Reduce7,    Shift(13),  ParseError];

function ParseError(s, v, lexer) {
  throw [s, v, lexer.peek(), lexer];
}

function Accept(s, v, terminals) {
  return true;
}

function Shift(state) {
  return function (s, v, lexer) {
    v.push(lexer.peek());
    s.push(state);
    lexer.advance();
    return false;
  };
}

let E_r_goto = [1, ,,, 5, ,,,,, 11, ,,,,];
let E_l_goto = [6, ,,, 6, ,,,,,  6, ,,,,];
let E_goto = [8, ,,, 8, , 7, ,,, 8, ,,,,];
let Vars_goto = [,, 3, ,,,,, ,,,,, 14, ,];

function Reduce1(s, v, lexer) { throw "Should accept instead of reducing S"; }
function Reduce2(s, v, lexer) {
  let E_r = v.pop(), arrow = v.pop(), vars = v.pop(), fn = v.pop();
  vars.reverse()
  s.pop(); s.pop(); s.pop(); s.pop();
  v.push(new Fn(vars, E_r));
  s.push(E_r_goto[s.top()]);
  return false;
}
function Reduce3(s, v, lexer) {
  s.pop();
  s.push(E_r_goto[s.top()]);
  return false;
}
function Reduce4(s, v, lexer) {
  let operand = v.pop(), operator = v.pop();
  s.pop(); s.pop();
  v.push(new App(operator, operand));
  s.push(E_l_goto[s.top()]);
  return false;
}
function Reduce5(s, v, lexer) {
  s.pop();
  s.push(E_l_goto[s.top()]);
  return false;
}
function Reduce6(s, v, lexer) {
  let variable = v.pop();
  s.pop();
  v.push(new Var(variable.name));
  s.push(E_goto[s.top()]);
  return false;
}
function Reduce7(s, v, lexer) {
  let rpar = v.pop(), E_r = v.pop(), lpar = v.pop();
  s.pop(); s.pop(); s.pop();
  v.push(E_r);
  s.push(E_goto[s.top()]);
  return false;
}
function Reduce8(s, v, lexer) {
  let vars = v.pop(), variable = v.pop();
  s.pop(); s.pop();
  vars.push(new Var(variable.name));
  v.push(vars);
  s.push(Vars_goto[s.top()]);
  return false;
}
function Reduce9(s, v, lexer) {
  let variable = v.pop();
  s.pop();
  v.push([new Var(variable.name)]);
  s.push(Vars_goto[s.top()]);
  return false;
}

function Var(name) {
  this.name = name;
}

function Fn(vars, body) {
  this.vars = vars;
  this.body = body;
}

function App(operator, operand) {
  this.operator = operator;
  this.operand = operand;
}

Var.prototype.setup = function () { /* No equivalent rule */ }

Fn.prototype.setup = function () {
  this.body.continuation = (value) => this.continuation(new Fn(this.vars, value));
  this.body.setup();
}

App.prototype.setup = function () {
  this.operator.continuation =
    (value) => this.continuation(new App(value, this.operand));
  this.operator.setup();
  this.operand.continuation =
    (value) => this.continuation(new App(this.operator, value));
  this.operand.setup();
}

var max_steps = 10;
var eager_strategy = false;
App.prototype.perform = function () {
  let next_operator = this.operator;
  let next_operand = this.operand;
  for (let steps = 0; steps < max_steps; ++steps) {
    if (next_operator.is_steppable()) {
      next_operator = next_operator.step();
    } else if (next_operator.requires_eager() &&
               next_operand.is_steppable()) {
      next_operand = next_operand.step();
    } else {
      return this.continuation(next_operator.apply(next_operand));
    }
  }
  return this.continuation(new App(next_operator, next_operand));
}

Var.prototype.is_steppable = function () { return false; }
Fn.prototype.is_steppable  = function () { return false; }
App.prototype.is_steppable = function () { return true; }

Var.prototype.apply = function (actual) {
  return new App(this.clone(), actual.clone());
}

Fn.prototype.apply = function (actual) {
  let renamed = this.avoidCapture(actual.free_var_names(), this.used_names());
  let formal = renamed.vars[0];
  if (this.vars.length > 1) {
    let slice = renamed.vars.slice(1);
    return new Fn(slice, renamed.body).subst(formal, actual);
  } else {
    return renamed.body.subst(formal, actual);
  }
}

Var.prototype.avoidCapture = function (avoid_names, used_names) {
  return this.clone();
}

Fn.prototype.avoidCapture = function (avoid_names, used_names) {
  let new_body = this.body.avoidCapture(avoid_names, used_names)
  let new_names = [];
  for (const v of this.vars) {
    if (avoid_names.has(v.name)) {
      let fresh_var = fresh_variable(v.name, avoid_names, used_names);
      new_names.push(fresh_var);
      new_body = new_body.subst(v, fresh_var);
    } else {
      new_names.push(v);
    }
  }
  return new Fn(new_names, new_body);
}

App.prototype.avoidCapture = function (avoid_names, used_names) {
  return new App(this.operator.avoidCapture(avoid_names, used_names),
                 this.operand.avoidCapture(avoid_names, used_names));
}

function fresh_variable(name, avoid, used) {
  let n;
  for (n = 0; avoid.has(name + n) || used.has(name + n); ++n) { }
  return new Var(name + n);
}

Var.prototype.free_var_names = function () { return new Set([this.name]); }

Fn.prototype.free_var_names = function () {
  let recur = this.body.free_var_names();
  for (const n of this.vars)
    recur.delete(n.name);
  return recur;
}

App.prototype.free_var_names = function () {
  let operator_names = this.operator.free_var_names();
  for (const n of this.operand.free_var_names())
    operator_names.add(n);
  return operator_names;
}

Var.prototype.used_names = function () { return new Set([this.name]); }

Fn.prototype.used_names = function () {
  let recur = this.body.used_names();
  for (const n of this.vars)
    recur.add(n.name);
  return recur;
}

App.prototype.used_names = function () {
  let operator_names = this.operator.used_names();
  for (const n of this.operand.used_names())
    operator_names.add(n);
  return operator_names;
}

Var.prototype.equals = function (arg) { return this.name === arg.name; }
Var.prototype.subst = function (formal, actual) {
  return this.equals(formal) ? actual : this.clone();
}

Fn.prototype.subst = function (formal, actual) {
  if (this.vars.some(x => x.equals(formal))) {
    return this.clone();
  } else {
    return new Fn(this.vars, this.body.subst(formal, actual));
  }
}

App.prototype.subst = function (formal, actual) {
  return new App(this.operator.subst(formal, actual),
                 this.operand.subst(formal, actual));
}

Var.prototype.step = function () { return this.clone(); }

Fn.prototype.step = function () {
  return new Fn(this.vars, this.body.step());
}

App.prototype.step = function () {
  if (this.operator.is_steppable()) {
    return new App(this.operator.step(), this.operand);
  } else {
    if ((eager_strategy || this.operator.requires_eager())
        && this.operand.is_steppable())
      return new App(this.operator, this.operand.step());
    else
      return this.operator.apply(this.operand);
  }
}

Var.prototype.requires_eager = function () { return false; }
Fn.prototype.requires_eager = function () { return false; }
App.prototype.requires_eager = function () { return false; }

Var.prototype.clone = function () { return new Var(this.name); }
Fn.prototype.clone = function () {
  return new Fn(this.vars, this.body.clone());
}
App.prototype.clone = function () {
  return new App(this.operator.clone(), this.operand.clone());
}
Var.prototype.bind = function (vars) { this.free = !vars.has(this.name); }
Fn.prototype.bind = function (vars) {
  let new_vars = new Set(vars);
  for (const v of this.vars) new_vars.add(v);
  this.body.bind(new_vars);
}
App.prototype.bind = function (vars) {
  this.operator.bind(vars); this.operand.bind(vars);
}

Var.prototype.pretty_print = function () {
  let VarElement = document.createElement("var");
  VarElement.term = this;
  this.element = VarElement;
  VarElement.innerText = this.name;
  return VarElement;
}

Fn.prototype.pretty_print = function () {
  let FnElement = document.createElement("span");
  FnElement.term = this;
  this.element = FnElement;

  let FnText = document.createElement("span");
  FnText.innerHTML = this.fnText;
  FnText.classList.add("fn");
  FnElement.appendChild(FnText);

  FnElement.append(" ");
  for (const v of this.vars) {
    FnElement.appendChild(v.pretty_print());
    FnElement.append(" ");
  }

  let FnArrow = document.createElement("span");
  FnArrow.innerHTML = this.arrowText;
  FnArrow.classList.add("arrow");
  FnElement.appendChild(FnArrow);
  FnElement.append(" ");

  FnElement.appendChild(this.body.pretty_print());
  return FnElement;
}

function setDisplay(fn, arrow) {
  Fn.prototype.fnText = fn; Fn.prototype.arrowText = arrow;
  for (const tag of document.getElementsByClassName("fn"))
    tag.innerHTML = fn;
  for (const tag of document.getElementsByClassName("arrow"))
    tag.innerHTML = arrow;
}
setDisplay("fn", "=>");

App.prototype.pretty_print = function () {
  let AppElement = document.createElement("span");
  AppElement.term = this;
  this.element = AppElement;
  AppElement.classList.add("application");

  let OperatorElement = this.operator.pretty_print();
  if (this.operator.grammar_level < 1) {
    OperatorElement.prepend("(");
    OperatorElement.append(")");
  }
  AppElement.appendChild(OperatorElement);

  AppElement.append(" ");

  let OperandElement = this.operand.pretty_print();
  if (this.operand.grammar_level < 2) {
    OperandElement.prepend("(");
    OperandElement.append(")");
  }
  AppElement.appendChild(OperandElement);

  return AppElement;
}

Var.prototype.grammar_level = 2;
App.prototype.grammar_level = 1;
Fn.prototype.grammar_level  = 0;

function tie(inputID, outputID) {
  tie_value(document.getElementById(inputID).value,
            document.getElementById(outputID));
}
function tie_value(input, output) {
  while (output.hasChildNodes())
    output.removeChild(output.lastChild);

  let root = parse(input);
  let root_element = root.pretty_print();
  root.setup();
  root.bind(new Set());
  root.continuation = x => x;

  output.appendChild(root_element);
  addInteraction(output);
}

function appOn(event, span, container) {
  event.stopPropagation();
  span.children[0].style.background = "lightblue";
  span.children[1].style.background = "lightgreen";
}

function appOut(event, span, container) {
  span.children[0].style.background = "";
  span.children[1].style.background = "";
}

function appClick(event, span, container) {
  if (event.button === 0) {
    event.stopPropagation();
    let new_term = span.term.perform();
    let new_element = new_term.pretty_print();
    new_term.setup();
    new_term.bind(new Set());
    new_term.continuation = x => x;
    container.insertBefore(document.createElement("br"), container.firstChild);
    container.insertBefore(new_element, container.firstChild);
    addInteraction(container);
  }
}

function addInteraction(container) {
  for (const el of container.getElementsByClassName("application")) {
    el.onmouseover = ev => appOn(ev, el, container);
    el.onmouseout = ev => appOut(ev, el, container);
    el.onclick =  ev => appClick(ev, el, container);
  }
}