abstract-algorithm - npm Package Compare versions

Comparing version 0.1.19 to 0.1.22

package.json

 {
   "name": "abstract-algorithm",
-  "version": "0.1.19",
+  "version": "0.1.22",
   "description": "Abstract-algorithm for optional reduction of stratifiable lambda terms",
@@ -5,0 +5,0 @@ "main": "src/lambda-calculus.js",

src/abstract-combinators.js

@@ -5,7 +5,7 @@ function port(node, slot) {
 
-function getPortNode(port) {
+function node(port) {
   return port >>> 2;
 }
 
-function getPortSlot(port) {
+function slot(port) {
   return port & 3;
@@ -18,3 +18,3 @@ }
     reuse: [],
-    stats: {}
+    stats: {loops:0, rules:0, betas:0, dupls:0, annis:0}
   };
@@ -24,7 +24,7 @@ }
 function newNode(net, kind) {
-  var node = net.reuse.pop() || (net.nodes.length / 4);
+  var node = net.reuse.pop() || (net.nodes.length >> 2);
   net.nodes[node * 4 + 0] = node * 4 + 0;
   net.nodes[node * 4 + 1] = node * 4 + 1;
   net.nodes[node * 4 + 2] = node * 4 + 2;
-  net.nodes[node * 4 + 3] = kind << 2;
+  net.nodes[node * 4 + 3] = kind * 4;
   return node;
@@ -37,11 +37,11 @@ }
 
-function getNodeKind(net, node) {
+function kind(net, node) {
   return net.nodes[node * 4 + 3] >>> 2;
 }
 
-function getNodeMeta(net, node) {
+function meta(net, node) {
   return (net.nodes[node * 4 + 3] >>> 0) & 3;
 }
 
-function setNodeMeta(net, node, meta) {
+function setMeta(net, node, meta) {
   return net.nodes[node * 4 + 3] = net.nodes[node * 4 + 3] & 0xFFFFFFFC | meta;
@@ -56,22 +56,27 @@ }
 function reduce(net) {
-  net.stats = {loops:0, rules:0, betas:0, dupls:0, annis:0};
-  net.reuse = [];
   var next = net.nodes[0];
-  var prev, back;
+  var prev, back, nextMeta, nextSlot;
+  var i = 0;
   while (next > 0) {
     prev = enterPort(net, next);
     next = enterPort(net, prev);
-    if (getPortSlot(next) === 0) {
-      if (getPortSlot(prev) === 0 && getPortNode(prev) !== 0) {
-        back = enterPort(net, port(getPortNode(prev), getNodeMeta(net, getPortNode(prev))));
-        rewrite(net, getPortNode(prev), getPortNode(next), net.stats);
-        next = enterPort(net, back);
-      } else {
-        setNodeMeta(net, getPortNode(next), 1);
-        next = enterPort(net, port(getPortNode(next), 1));
+    ++i;
+    if (slot(next) === 0 && slot(prev) === 0 && node(prev) !== 0) {
+      back = enterPort(net, port(node(prev), meta(net, node(prev))));
+      rewrite(net, node(prev), node(next), net.stats);
+      next = enterPort(net, back);
+    } else {
+      switch (slot(next) * 3 + meta(net, node(next))) {
+        case 0 * 3 + 0: nextSlot = 1; nextMeta = 1; break;
+        case 0 * 3 + 1: nextSlot = 2; nextMeta = 2; break;
+        case 0 * 3 + 2: nextSlot = 1; nextMeta = 1; break;
+        case 1 * 3 + 0: nextSlot = 0; nextMeta = 1; break;
+        case 1 * 3 + 1: nextSlot = 2; nextMeta = 2; break;
+        case 1 * 3 + 2: nextSlot = 0; nextMeta = 3; break;
+        case 2 * 3 + 0: nextSlot = 0; nextMeta = 2; break;
+        case 2 * 3 + 1: nextSlot = 2; nextMeta = 2; break;
+        case 2 * 3 + 2: nextSlot = 0; nextMeta = 3; break;
       }
-    } else {
-      var meta = getNodeMeta(net, getPortNode(next));
-      setNodeMeta(net, getPortNode(next), meta === 0 ? getPortSlot(next) : meta + 1);
-      next = enterPort(net, port(getPortNode(next), meta === 1 ? 2 : 0));
+      setMeta(net, node(next), nextMeta);
+      next = enterPort(net, port(node(next), nextSlot));
     }
@@ -83,32 +88,36 @@ ++net.stats.loops;
 
-function rewrite(net, x, y) {
-  if (getNodeKind(net,x) === getNodeKind(net,y)) {
-    //  a          b            a   b
+function rewrite(net, A, B) {
+  if (kind(net,A) === kind(net,B)) {
+    //  1          2            1   2
     //   \        /              \ / 
-    //     A -- B       -->       X  
+    //     A == B       -->       X  
     //   /        \              / \ 
-    //  c          d            c   d
-    link(net, enterPort(net, port(x, 1)),  enterPort(net, port(y, 1)));
-    link(net, enterPort(net, port(x, 2)),  enterPort(net, port(y, 2)));
-    net.stats.betas += getNodeKind(net, x) === 1 ? 1 : 0;
+    //  2          1            2   1
+    link(net, enterPort(net, port(A, 1)),  enterPort(net, port(B, 1)));
+    link(net, enterPort(net, port(A, 2)),  enterPort(net, port(B, 2)));
+    net.stats.betas += kind(net, A) === 1 ? 1 : 0;
     net.stats.annis += 1;
+    net.reuse.push(A, B);
   } else {
-    //  a          d       a - B --- A - d
+    //  1          2       1 = B --- A = 2
     //   \        /              \ /   
-    //     A -- B     -->         X    
+    //     A == B     -->         X    
     //   /        \              / \  
-    //  b          c       b - B --- A - c 
-    var x1 = newNode(net, getNodeKind(net, x)), x2 = newNode(net, getNodeKind(net, x));
-    var y1 = newNode(net, getNodeKind(net, y)), y2 = newNode(net, getNodeKind(net, y));
-    link(net, enterPort(net, port(y1, 0)), enterPort(net, port(x, 1)));
-    link(net, enterPort(net, port(y2, 0)), enterPort(net, port(x, 2)));
-    link(net, enterPort(net, port(x1, 0)), enterPort(net, port(y, 1)));
-    link(net, enterPort(net, port(x2, 0)), enterPort(net, port(y, 2)));
-    link(net, enterPort(net, port(x1, 1)), enterPort(net, port(y1, 1)));
-    link(net, enterPort(net, port(x1, 2)), enterPort(net, port(y2, 1)));
-    link(net, enterPort(net, port(x2, 1)), enterPort(net, port(y1, 2)));
-    link(net, enterPort(net, port(x2, 2)), enterPort(net, port(y2, 2)));
+    //  2          1       2 = B --- A = 1 
+    var a = newNode(net, kind(net, A));
+    var b = newNode(net, kind(net, B));
+    
+    link(net, port(b, 0), enterPort(net, port(A, 1)));
+    link(net, port(B, 0), enterPort(net, port(A, 2)));
+    link(net, port(a, 0), enterPort(net, port(B, 1)));
+    link(net, port(A, 0), enterPort(net, port(B, 2)));
+    link(net, port(a, 1), port(b, 1));
+    link(net, port(a, 2), port(B, 1));
+    link(net, port(A, 1), port(b, 2));
+    link(net, port(A, 2), port(B, 2));
+
+    setMeta(net, A, 0);
+    setMeta(net, B, 0);
     net.stats.dupls += 1;
   }
-  net.reuse.push(x, y);
   net.stats.rules += 1;
@@ -119,10 +128,10 @@ }
   port,
-  getPortNode,
-  getPortSlot,
+  node,
+  slot,
   newNet,
   newNode,
   enterPort,
-  getNodeKind,
-  getNodeMeta,
-  setNodeMeta,
+  kind,
+  meta,
+  setMeta,
   link,
@@ -129,0 +138,0 @@ reduce,

src/lambda-calculus.js

@@ -82,5 +82,20 @@ const I = require("./abstract-combinators.js");
   var kind = 1;
-  var net = I.newNet([0, 1, 2, 0]);
+  var net = I.newNet([0, 2, 1, 4]);
   var ptr = (function encode(term, scope){
     switch (term.tag){
+      // Arg
+      //    \
+      //     App = Fun
+      //    /
+      // Ret
+      case "App":
+        var app = I.newNode(net,1);
+        var fun = encode(term.fun, scope);
+        I.link(net, I.port(app,0), fun);
+        var arg = encode(term.arg, scope);
+        I.link(net, I.port(app,1), arg);
+        return I.port(app,2);
+      // Era =- Fun = Ret  
+      //         |     
+      //        Bod  
       case "Lam": 
@@ -94,17 +109,16 @@ var fun = I.newNode(net,1);
         return I.port(fun,0);
-      case "App":
-        var app = I.newNode(net,1);
-        var fun = encode(term.fun, scope);
-        I.link(net, I.port(app,0), fun);
-        var arg = encode(term.arg, scope);
-        I.link(net, I.port(app,1), arg);
-        return I.port(app,2);
+      // Arg
+      //    \
+      //     Dup =- Fun      Ret - Era
+      //    /
+      // Ret
       case "Var":
         var lam = scope[term.idx];
-        if (I.getNodeKind(net,I.getPortNode(I.enterPort(net,I.port(lam,1)))) === 0) {
-          return I.port(lam,1);
+        var arg = I.enterPort(net, I.port(lam,1));
+        if (I.kind(net, I.node(arg)) === 0) {
+          net.reuse.push(I.node(arg));
+          return I.port(lam, 1);
         } else {
           var dup = I.newNode(net, ++kind);
-          var arg = I.enterPort(net, I.port(lam,1));
-          I.link(net, I.port(dup,1), I.enterPort(net,I.port(lam,1)));
+          I.link(net, I.port(dup,1), arg);
           I.link(net, I.port(dup,0), I.port(lam,1));
@@ -123,5 +137,5 @@ return I.port(dup,2);
     var prev = I.enterPort(net, next);
-    var prevPort = I.getPortSlot(prev);
-    var prevNode = I.getPortNode(prev);
-    if (I.getNodeKind(net, prevNode) === 1) {
+    var prevPort = I.slot(prev);
+    var prevNode = I.node(prev);
+    if (I.kind(net, prevNode) === 1) {
       switch (prevPort) {
@@ -128,0 +142,0 @@ case 0:

src/main.js

@@ -11,2 +11,4 @@ #!/usr/bin/env node --stack_size=5000000
   var bruijn = args.indexOf("-b") !== -1 || args.indexOf("--bruijn") !== -1;
+  var nobase = args.indexOf("-n") !== -1 || args.indexOf("--nobase") !== -1;
+  var dump = args.indexOf("-d") !== -1 || args.indexOf("--dump") !== -1;
   var file = args[args.length - 1];
@@ -17,12 +19,12 @@ var base = fs.readFileSync(path.join(__dirname, "..", "lib", "base.lam"), "utf8");
   console.log("Absal evaluates λ-terms optimally (no oracle).");
-  console.log("Usage:");
-  console.log("  absal [--stats] [--bruijn] fileName[.lam]");
-  console.log("Syntax:");
+  console.log("\nUsage:");
+  console.log("  absal [--stats] [--bruijn] [--nobase] fileName[.lam]");
+  console.log("\nSyntax:");
   console.log("  #arg body      : lambda expression");
   console.log("  /fn arg        : applies fn to arg");
   console.log("  @name val expr : let name be val in expr");
-  console.log("Example:");
+  console.log("\nExample:");
   console.log("  @four #f #x /f /f /f /f x");
   console.log("  /four four");
-  console.log("Stats:");
+  console.log("\nStats:");
   console.log("  - loops    : how many times the main loop was executed");
@@ -36,4 +38,20 @@ console.log("  - rules    : total graph rewrites (dupls + annis)");
 
+function print(net) {
+  for (var i=0; i < net.nodes.length; i+=4) {
+    if (net.reuse.some(x => x === i >> 2)) {
+      console.log(i>>2);
+      continue;
+    }
+    [a,b,c,d] = net.nodes.slice(i, i+4);
+    console.log(i>>2, `${a>>2}:${a&3} ${b>>2}:${b&3} ${c>>2}:${c&3} ${d>>2}:${d&3}`);
+  }
+}
+
 var start = Date.now();
-var result = L.reduce(`${base} ${code}`, 1, bruijn);
+var net = L.toNet(L.fromString(nobase ? code : base + " " + code));
+if (dump) { print(net); }
+var net = L.net.reduce(net);
+if (dump) { print(net); }
+var result = {term: L.toString(L.fromNet(net), bruijn), stats: net.stats};
+var time = Date.now() - start;
 
@@ -40,0 +58,0 @@ console.log(result.term);

No alert changes

Improved metrics

Total package byte prevSize

5563644

increased by2.26%

Number of package files

61

increased by8.93%

Lines of code

2936

increased by11.13%

No dependency changes