Skip to content

Commit fe2c6f7

Browse files
codedotcodedot
committed
Replace 'abstract' with an impure solution
1 parent c5e70c2 commit fe2c6f7

3 files changed

Lines changed: 35 additions & 77 deletions

File tree

‎README.md‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -16,8 +16,7 @@ by Ian Mackie, this is the default algorithm;
1616
* `optimal`, an implementation of
1717
[_Lambdascope_][5] by Vincent van Oostrom et al;
1818

19-
* `abstract`, an experimental algorithm described in
20-
[arXiv:1701.04691v2][6].
19+
* `abstract`, an undocumented experimental algorithm.
2120

2221
The embedded read-back mechanism is described
2322
in Section 7 of [10.4204/EPTCS.225.7][4].
@@ -26,15 +25,14 @@ in Section 7 of [10.4204/EPTCS.225.7][4].
2625
[3]: http://dx.doi.org/10.1007/978-3-642-24452-0_3
2726
[4]: http://dx.doi.org/10.4204/EPTCS.225.7
2827
[5]: http://www.phil.uu.nl/~oostrom/publication/pdf/lambdascope.pdf
29-
[6]: https://arxiv.org/abs/1701.04691v2
3028

3129
# Benchmarks
3230

3331
The following is output of the `test.sh` script provided in the package:
3432

3533
```
3634
SAMPLE CLOSED OPTIMAL ABSTRACT
37-
counter 58/6 143/4 N/A
35+
counter 58/6 143/4 27/4
3836
w2eta 137/16 205/7 37/7
3937
22210ii 1740/182 7886/70 731/70
4038
3222ii 5896/545 164197/43 1182/43

‎encoding/abstract/index.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ function psi(shared, list)
1313
const twins = shared[atom];
1414
const wleft = twins.left;
1515
const wright = twins.right;
16-
const agent = `\\fan_{this.uniq()}`;
16+
const agent = `\\fanin_{this.uniq()}`;
1717
const tree = `${agent}(${wright}, ${wleft})`;
1818

1919
list.push(`${atom} = ${tree}`);

‎encoding/abstract/template.txt‎

Lines changed: 32 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -4,48 +4,36 @@
44
++this.total;
55
} \lambda[a, b];
66

7-
\apply[
8-
\fan_{[i[0], i[1] + 1]}(a, b),
9-
\fan_{[i[0], i[1] + 1]}(c, d)
10-
] {
7+
\apply[\fanin_{i}(a, b), \fanout_{i}(c, d)] {
118
/* Duplicate application. */
129
++this.total;
13-
} \fan_{i}[\apply(a, c), \apply(b, d)];
10+
} \fanout_{i}[\apply(a, c), \apply(b, d)];
1411

15-
\fan_{i}[\lambda(a, b), \lambda(c, d)] {
12+
\fanin_{i}[\lambda(a, b), \lambda(c, d)] {
1613
/* Duplicate abstraction. */
1714
++this.total;
18-
} \lambda[
19-
\fan_{[i[0], i[1] + 1]}(a, c),
20-
\fan_{[i[0], i[1] + 1]}(b, d)
21-
];
22-
23-
\fan_{i}[
24-
\fan_{[j[0], j[1] + 1]}(a, b),
25-
\fan_{[j[0], j[1] + 1]}(c, d)
26-
] {
15+
} \lambda[\fanout_{i}(a, c), \fanin_{i}(b, d)];
16+
17+
\fanin_{i}[\fanout_{this.int1(j, i)}(a, b), \fanout_{this.int2(j, i)}(c, d)] {
2718
/* Duplicate different fans. */
28-
if ((i[0] != j[0]) && (i[1] < j[1]))
19+
if (!this.match(i, j))
2920
++this.total;
3021
else
3122
return false;
32-
} \fan_{j}[
33-
\fan_{[this.plus(i[0], j[0]), i[1]]}(a, c),
34-
\fan_{[this.minus(i[0], j[0]), i[1]]}(b, d)
35-
];
23+
} \fanout_{j}[\fanin_{this.int1(i, j)}(a, c), \fanin_{this.int2(i, j)}(b, d)];
3624

37-
\fan_{i}[a, b] {
25+
\fanin_{i}[a, b] {
3826
/* Annihilate matching fans. */
39-
if ((i[0] == j[0]) || (i[1] == j[1]))
27+
if (this.match(i, j))
4028
++this.total;
4129
else
4230
return false;
43-
} \fan_{j}[a, b];
31+
} \fanout_{j}[a, b];
4432

45-
\read_{C}[\fan_{i}(a, b)] {
33+
\read_{C}[\fanout_{i}(a, b)] {
4634
/* Duplicate context. */
4735
++this.total;
48-
} \fan_{i}[\read_{C}(a), \read_{this.clone(C)}(b)];
36+
} \fanout_{i}[\read_{C}(a), \read_{this.clone(C)}(b)];
4937

5038
\print {
5139
/* Output results of read-back. */
@@ -68,7 +56,7 @@
6856
++this.total;
6957
} \atom_{M};
7058

71-
\fan_{i}[\atom_{M}, \atom_{M}] {
59+
\fanin_{i}[\atom_{M}, \atom_{M}] {
7260
/* Duplicate an atom. */
7361
++this.total;
7462
} \atom_{M};
@@ -81,57 +69,29 @@ $$
8169

8270
READBACK
8371

84-
const table = [];
85-
let last = 0;
72+
const db = {};
73+
let nonce = 0;
8674

87-
function uniq()
75+
function decide(i, j)
8876
{
89-
let fresh = ++last;
90-
91-
fresh = fresh.toString();
92-
fresh = hash(fresh);
93-
return [fresh, 1];
94-
}
95-
96-
function cons(s, a, b)
97-
{
98-
return hash(a + s + b);
99-
}
100-
101-
function mktable()
102-
{
103-
for (let n = 0; n < 256; n++) {
104-
let c = n;
105-
106-
for (let k = 0; k < 8; k++) {
107-
if (c & 1)
108-
c = 0xEDB88320 ^ (c >>> 1);
109-
else
110-
c = c >>> 1;
111-
}
112-
113-
table[n] = c;
114-
}
115-
}
116-
117-
function hash(str)
118-
{
119-
const n = str.length;
120-
let crc = 0 ^ (-1);
121-
122-
for (let i = 0; i < n; i++) {
123-
const b = str.charCodeAt(i);
124-
125-
crc = (crc >>> 8) ^ table[(crc ^ b) & 0xFF];
126-
}
77+
if (db[`${i}-${j}`])
78+
return;
12779

128-
return (crc ^ (-1)) >>> 0;
80+
db[`${i}-${j}`] = ++nonce;
81+
db[`${i}+${j}`] = ++nonce;
82+
db[`${j}-${i}`] = j;
83+
db[`${j}+${i}`] = j;
12984
}
13085

131-
mktable();
86+
this.uniq = () => ++nonce;
87+
this.int1 = (i, j) => db[`${i}-${j}`];
88+
this.int2 = (i, j) => db[`${i}+${j}`];
89+
this.match = (i, j) => {
90+
if (i == j)
91+
return true;
13292

133-
this.plus = cons.bind(this, "+");
134-
this.minus = cons.bind(this, "-");
135-
this.uniq = uniq;
93+
decide(i, j);
94+
return false;
95+
};
13696
this.beta = 0;
13797
this.total = 0;

0 commit comments

Comments
 (0)