hvm-core 0.2.26

HVM-Core is a massively parallel Interaction Combinator evaluator.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

// This is, as far as I can tell, the most efficient solution to the atomic
// substitution problem: https://www.youtube.com/watch?v=PCAfVdmBYXQ
//
// It is an hybrid of the locking and lock-free approach that will try to
// perform the link with 2 atomic CAS. For each CAS that fails, we place a
// redirection node on the corresponding port. We then start a soft 'link(x)'
// procedure that will *try* to remove redirections. If 'x' is an aux port, we
// do not own it, so, some redirections may remain. If 'x' is a main port (not
// implemented here), we own it, so we will successfully remove all redirections
// after it, and either insert it in an aux port, or find a new active pair.
// This algorithm is superior because, in most cases, the 2 initial CAS will
// succeed, allowing us to avoid storing redirections and calling 'link()'. Both
// Oliver, Derenash and I independently concluded this is the best solution.

// Atomic Primitives
// -----------------

function* atomic_read(idx) {
  yield null;
  return D[idx];
}

function* atomic_swap(idx, val) {
  yield null;
  let got = D[idx];
  D[idx] = val;
  return got;
}

function* atomic_cas(idx, from, to) {
  yield null;
  let old = D[idx];
  if (old === from) {
    D[idx] = to;
  }
  return old;
}

// Atomic Substitution
// -------------------

const RED = 0x10; // redirection wire
const GOT = 0xFF; // "taken" placeholder

const is_red = (x) => x >= RED && x < RED*2;
const is_var = (x) => x >= 0 && x < RED;

function* atomic_rewrite(tid, a_dir, b_dir) {
  var a_ptr = yield* atomic_swap(a_dir, GOT);
  var b_ptr = yield* atomic_swap(b_dir, GOT);
  yield* atomic_subst(tid, a_ptr, a_dir, b_ptr);
  yield* atomic_subst(tid, b_ptr, b_dir, a_ptr);
}

function* atomic_subst(tid, a_ptr, a_dir, b_ptr) {
  var a_got = yield* atomic_cas(a_ptr, a_dir, b_ptr);
  yield* atomic_swap(a_dir, a_got == a_dir ? -1 : b_ptr+RED);
  yield* atomic_link(tid, a_ptr, b_ptr);
}

function* atomic_link(tid, dir, val) {
  var ptr = yield* atomic_read(dir);
  if (is_var(ptr)) {
    while (1) {
      var trg = yield* atomic_read(ptr);
      if (is_red(trg)) {
        var got = yield* atomic_cas(dir, ptr, trg-RED);
        if (got == ptr) {
          yield* atomic_swap(ptr, -1);
          ptr = trg - RED;
        }
      } else if (trg == GOT) {
        continue;
      } else {
        break;
      }
    }
  }
}

// Utils
// -----

function progress(ticks) {
  for (var i = 0; i < ticks; ++i) {
    var tid = Math.floor(Math.random() * 3);
    if (T[tid]) {
      let result = T[tid].next();
      if (result.done) {
        T[tid] = null;
      }
      if (!T[0] && !T[1] && !T[2]) {
        break;
      }
    }
  }
}

function show(x) {
  if (typeof x == "number") {
    return x == -1 ? "  " : x == 0xFF ? "::" : ("00"+x.toString(16)).slice(-2);
  } else {
    return x.map(show).join("|");
  }
}

// Tests
// -----

var I = [0,1,2,3,4,5,6,7];
var D = [1,0,3,2,5,4,7,6];
var T = [atomic_rewrite(0,1,2), atomic_rewrite(1,3,4), atomic_rewrite(2,5,6)];
progress(256);

console.log(show(I));
console.log(show(D));