Untyped lambda calculus with floating point arithmetic primitives and JIT compilation to/from JS

untyped_float_jit.js

module.exports = (function(){

  // Constructors
  var VAR = 1, LAM = 2, APP = 3, NUM = 4, OPC = 5;
  function Lam(bod){ return {type:LAM, bod:bod}; };
  function App(fun,arg){ return {type:APP, fun:fun, arg:arg}; };
  function Var(index){ return {type:VAR, index:index}; };
  function Num(num){ return {type:NUM, value:num}; };
  function Opc(op,a,b){ return {type:OPC, op:op, a:a, b:b}; };

  // Primitive operations
  var ops = (function(){
    var ops = {};
    function trueCase(a){return function(b){return a}};
    function falseCase(a){return function(b){return b}};
    function op(name,fn){
      return function(a,b){
        return typeof a === "number" && typeof b === "number"
          ? fn(a, b)
          : Opc(name,a,b);
      };
    };
    ops.add = op("add", function(a,b){return a+b});
    ops.sub = op("sub", function(a,b){return a-b});
    ops.mul = op("mul", function(a,b){return a*b});
    ops.div = op("div", function(a,b){return a/b});
    ops.pow = op("pow", function(a,b){return Math.pow(a, b);});
    ops.mod = op("mod", function(a,b){return ((a%b)+b)%b;});
    ops.log = op("log", function(a,b){return Math.log(a) / Math.log(b);});
    ops.sin = op("sin", function(a,b){return a*Math.sin(b);});
    ops.asi = op("asi", function(a,b){return a*Math.asin(b);});
    ops.cos = op("cos", function(a,b){return a*Math.cos(b);});
    ops.aco = op("aco", function(a,b){return a*Math.aco(b);});
    ops.tan = op("tan", function(a,b){return a*Math.tan(b); });
    ops.ata = op("ata", function(a,b){return a*Math.atan(b); });
    ops.atg = op("atg", function(a,b){return Math.atan2(a,b); });
    ops.min = op("min", function(a,b){return Math.min(a,b); });
    ops.max = op("max", function(a,b){return Math.max(a,b); });
    ops.ltn = op("ltn", function(a,b){return a<b ? trueCase : falseCase; });
    ops.leq = op("leq", function(a,b){return a<=b ? trueCase : falseCase; });
    ops.gtn = op("gtn", function(a,b){return a>b ? trueCase : falseCase; });
    ops.geq = op("geq", function(a,b){return a>=b ? trueCase : falseCase; });
    ops.eql = op("eql", function(a,b){return a===b ? trueCase : falseCase; });
    return ops;
  })();

  // Replaces constructors by functions
  function fold(foldVar,foldLam,foldApp,foldNum,foldOpc){
    return function go(term){
      switch (term.type){
        case VAR: return foldVar(term.index);
        case LAM: return foldLam(go(term.bod));
        case APP: return foldApp(go(term.fun),go(term.arg));
        case NUM: return foldNum(term.value);
        case OPC: return foldOpc(term.op, go(term.a), go(term.b));
      };
    };
  };

  // Translates to target language with named variables
  function translate(lam,app,num,opc){
    return function(term){
      var alphabet = "abcdefghijklmnopqrstuvwxyz";
      function toName(nat){
        var name = "";
        do {
          name += alphabet[nat % alphabet.length];
          nat = Math.floor(nat / alphabet.length);
        } while (nat > 0);
        return name;
      };
      return fold(
        function(idx){return function(d){return toName(d-1-idx); }},
        function(bod){return function(d){return lam(toName(d),bod(d+1)); }},
        function(fun, arg){return function(d){return app(fun(d),arg(d)); }},
        function(n){return function(d){return num(n); }},
        function(op,a,b){return function(d){return opc(op,a(d),b(d)); }})
        (term)(0);
    };
  };

  // Reduces to normal form
  function norm(term){
    function compile(term){
      return eval("(function($,$ops){return "+translate(
        function(varName, bod){ return "(function("+varName+"){return "+bod+"})"; },
        function(fun, arg){ return "$("+fun+","+arg+")"; },
        function(num){ return num; },
        function(op,a,b){ return "$ops."+op+"("+a+","+b+")"; })
        (term)+"})");
    };
    var c = 0;
    function nat(n,f){
      return function(x){
        for (var i=0; i<n; ++i)
          x = f(x);
        return x;
      };
    };
    function app(a,b){
      return typeof a === "number" ? nat(a,b) : a(b);
    }
    function readback(value){
      var nextVarId = 0;
      return (function nf(value, depth){
        function app(fun){
          function getArg(arg){
            return arg === null ? fun : app(function(d){
              return App(fun(d), nf(arg, d));
            });
          };
          getArg.isApp = true;
          return getArg;
        };
        if (value.isApp) {
          return value(null)(depth);
        } else if (typeof value === "number") {
          return Num(value);
        } else if (typeof value === "function") {
          return Lam(nf(value(app(function(d){
            return Var(d-1-depth);
          })), depth+1));
        } else if (value.type === OPC) {
          return Opc(value.op, nf(value.a, depth), nf(value.b, depth));
        } else return value;
      })(value(app, ops), 0);
    };
    return readback(compile(term));
  };

  // String -> {term: Term, deps: [String]}
  function parse(source){
    var index = 0;
    var deps = [];
    var term = (function parse(depth, binders){
      while (/[^a-zA-Z\(\)_{0-9]/.test(source[index]))
        ++index;
      if (source[index] === "("){
        ++index;
        var app = parse(depth, binders);
        while (source[index] !== ")")
          app = App(app, parse(depth, binders));
        ++index;
        return app; 
      } else if (source[index] === "{"){
        ++index;
        return Opc(
          source.slice(index, index+=3),
          parse(depth,binders),
          parse(depth,binders));
      } else if (/[0-9]/.test(source[index])) {
        for (var num = ""; /[0-9]/.test(source[index]); ++index)
          num += source[index];
        return Num(Number(num));
      } else {
        var binder = "";
        while (/[a-zA-Z0-9_]/.test(source[index]) && index !== source.length)
          binder += source[index++];
        var binderIndex = binders.indexOf(binder);
        if (source[index] === "."){
          return Lam(parse(depth+1, binders.concat(binder)));
        } else if (binderIndex === -1) {
          deps.push(binder);
          return Var(depth + deps.length - 1);
        } else {
          return Var(depth - binderIndex - 1);
        };
      }
    })(0, []);
    for (var i=0, l=deps.length; i<l; ++i)
      term = Lam(term);
    return {term: term, deps: deps};
  };

  // String -> Term
  function read(source){
    return parse(source).term;
  };

  // Term -> String
  var show = translate(
    function(arg,bod){return arg+"."+bod},
    function(fun,arg){return "("+fun+" "+arg+")"},
    function(num){return num},
    function(op,a,b){return "{"+op+" "+a+" "+b+"}"});

  return {
    Lam: Lam,
    App: App,
    Var: Var,
    Num: Num,
    Opc: Opc,
    LAM: LAM,
    APP: APP,
    VAR: VAR,
    NUM: NUM,
    OPC: OPC,
    parse: parse,
    read: read,
    show: show,
    norm: norm};
})();

Example:

var term = lam.read("t.(t f.x.(f (f x)) (50 a.{add a 1} 0))");
console.log(lam.show(lam.norm(term)));