reproduce the nots/maps experiment

nots_and_maps.js

var absal = require("abstract-algorithm");

// Produces a λ-encoded representation of a number with high sharing
// This is what allows us to perform repeated applications
// Example:
// 731 = λ1. λ0.
//     let 2   = λx.   1   (1 x) in
//     let 4   = λx.   2   (2 x) in
//     let 8   = λx.   4   (4 x) in
//     let 16  = λx.   8   (8 x) in
//     let 32  = λx.  16  (16 x) in
//     let 64  = λx.  32  (32 x) in
//     let 128 = λx.  64  (64 x) in
//     let 256 = λx. 128 (128 x) in
//     let 512 = λx. 256 (256 x) in
//     :1 :2 :8 :16 :64 :128 :512 0
var num = num => {
  var bits = num.toString(2).split("").reverse();
  var numb = "#1 #0 ";
  for (var i = 0; i < bits.length - 1; ++i) {
    numb += "=" + Math.pow(2,i+1) + " #x :" + Math.pow(2,i) + " :" + Math.pow(2,i) + " x ";
  }
  for (var i = 0; i < bits.length; ++i) {
    numb += bits[i] === "1" ? ":" + Math.pow(2,i) + " " : "";
  }
  numb += "0";
  return numb;
};

// λ-calculus term that applies two versions of not/map N times
var test = (N, func, version) => `
  @True  #t #f t
  @False #t #f f
  @not_a #b ::b False True
  @not_b #b #t #f ::b f t
  @nots  ::${num(N)} not_${version} True

  @Nil   #c #n n
  @Cons  #h #t #c #n ::c h ::t c n
  @list  ::Cons True ::Cons False ::Cons True ::Cons False Nil
  @map_a #f #l ::l #h #t ::Cons :f h t Nil
  @map_b #f #l #c #n ::l #h #t ::c :f h t n
  @maps  ::${num(N)} :map_${version} not_b list

  ${func}s
`;

var make_csv = (func) => {
  console.log(`N,${func}_a,${func}_b`);
  for (var i = 0; i <= 256; i += 1) {
    var a_result = absal.reduce(test(i,func,"a"),1);
    var b_result = absal.reduce(test(i,func,"b"),1);
    if (a_result.term !== b_result.term) throw `${func}_a and ${func}_b not equal!`;
    console.log(i+","+a_result.stats.rules+","+b_result.stats.rules);
  }
};

console.log("## nots");
make_csv("not");

console.log("## maps");
make_csv("map");