Skip to content

Commit 690a338

Browse files
codedotcodedot
committed
Revert "Replace 'optimal' with 'standard'"
This reverts commit 7325c31.
1 parent 7325c31 commit 690a338

8 files changed

Lines changed: 439 additions & 213 deletions

File tree

‎README.md‎

Lines changed: 28 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -14,47 +14,51 @@ in [Lamping's abstract algorithm][7],
1414
described in [arXiv:1710.07516][6],
1515
this is the default algorithm;
1616

17-
* `closed`, the approach of [arXiv:1304.2290][2] applied to
17+
* `closed`, the approach of [arXiv:1304.2290v8][2] applied to
1818
[_An Interaction Net Implementation of Closed Reduction_][3]
1919
by Ian Mackie;
2020

21-
* `optimal`, an implementation of optimal reduction as in
22-
[_The Optimal Implementation of Functional Programming Languages_][5],
23-
pp. 40-41.
21+
* `optimal`, an implementation of
22+
[_Lambdascope_][5] by Vincent van Oostrom et al;
23+
24+
* `standard`, an implementation of optimal reduction as in
25+
[_The Optimal Implementation of Functional Programming Languages_][8],
26+
pages 40-41.
2427

2528
The embedded read-back mechanism is described
2629
in Section 7 of [10.4204/EPTCS.225.7][4].
2730

28-
[2]: https://arxiv.org/abs/1304.2290
31+
[2]: https://arxiv.org/abs/1304.2290v8
2932
[3]: http://dx.doi.org/10.1007/978-3-642-24452-0_3
3033
[4]: http://dx.doi.org/10.4204/EPTCS.225.7
31-
[5]: https://books.google.com/books?id=Bod5HbPh-WwC
34+
[5]: http://www.phil.uu.nl/~oostrom/publication/pdf/lambdascope.pdf
3235
[6]: https://arxiv.org/abs/1710.07516
3336
[7]: https://doi.org/10.1145/96709.96711
37+
[8]: https://books.google.com/books?id=Bod5HbPh-WwC
3438

3539
# Benchmarks
3640

3741
The following is output of the `test.sh` script provided in the package:
3842

3943
```
40-
SAMPLE ABSTRACT CLOSED OPTIMAL
41-
counter 27/4 58/6 121/4
42-
w2eta 37/7 137/16 374/7
43-
1021 199/55 11871/1088 4307803/55
44-
22210i 494/68 2539/254 N/A
45-
3222i 1206/50 8638/819 N/A
46-
1022i 4317/69 33369/3139 N/A
47-
4222i 262425/72 2097926/196692 N/A
48-
222210i 1311135/139 8652059/852063 N/A
49-
2222101 2621862/327818 N/A N/A
50-
facty6nt 1112/210 80562/2436 3013433/210
51-
facty9i 1629/287 3746232/130949 N/A
52-
33-fact4 3770/704 16114/912 234075/704
53-
fibo16nt 24931/3042 134135/5673 8959455/3042
54-
fact100i 28502/3752 121854/10565 N/A
55-
35-fact5 72944/13480 805218/16206 N/A
56-
fibo20i 93534/6863 536843/24626 4023117/6863
57-
fact1knt 6215039/1353692 N/A N/A
44+
SAMPLE ABSTRACT CLOSED OPTIMAL STANDARD
45+
counter 27/4 58/6 143/4 121/4
46+
w2eta 37/7 137/16 205/7 374/7
47+
1021 199/55 11871/1088 1599875/55 4307803/55
48+
22210i 494/68 2539/254 58602/68 N/A
49+
3222i 1206/50 8638/819 804529/50 N/A
50+
1022i 4317/69 33369/3139 N/A N/A
51+
4222i 262425/72 2097926/196692 N/A N/A
52+
222210i 1311135/139 8652059/852063 N/A N/A
53+
2222101 2621862/327818 N/A N/A N/A
54+
facty6nt 1112/210 80562/2436 2790150/210 3013433/210
55+
facty9i 1629/287 3746232/130949 N/A N/A
56+
33-fact4 3770/704 16114/912 80706/704 234075/704
57+
fibo16nt 24931/3042 134135/5673 5462373/3042 8959455/3042
58+
fact100i 28502/3752 121854/10565 N/A N/A
59+
35-fact5 72944/13480 805218/16206 4702709/13480 N/A
60+
fibo20i 93534/6863 536843/24626 1961507/6863 4023117/6863
61+
fact1knt 6215039/1353692 N/A N/A N/A
5862
```
5963

6064
`T/B` should be read as total of `T` interactions,

‎encoding/index.js‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@ const generic = require("./generic");
44
const abstract = require("./abstract");
55
const closed = require("./closed");
66
const optimal = require("./optimal");
7+
const standard = require("./standard");
78

89
const expand = generic.expand;
910
const readback = generic.readback;
@@ -30,3 +31,4 @@ function addalgo(name, algo)
3031
addalgo("abstract", abstract);
3132
addalgo("closed", closed);
3233
addalgo("optimal", optimal);
34+
addalgo("standard", standard);

‎encoding/optimal/index.js‎

Lines changed: 21 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -5,32 +5,30 @@ const path = require("path");
55

66
const template = fs.readFileSync(path.join(__dirname, "template.txt"), "utf8");
77

8-
let mkwire, mktwins, getfv, subst;
8+
let mkwire, mktwins, getfv;
99

10-
function box(fv, list, lvl)
11-
{
12-
for (const atom in fv) {
13-
const ref = fv[atom].ref;
14-
const agent = `\\bra_{${lvl}}(${ref})`;
15-
16-
list.push(`${atom} = ${agent}`);
17-
}
18-
}
19-
20-
function psi(shared, list, lvl)
10+
function psi(shared, list)
2111
{
2212
for (const atom in shared) {
2313
const twins = shared[atom];
2414
const wleft = twins.left;
2515
const wright = twins.right;
26-
const agent = `\\fan_{${lvl}}`;
16+
const agent = `\\fan_{0}`;
2717
const tree = `${agent}(${wright}, ${wleft})`;
2818

2919
list.push(`${atom} = ${tree}`);
3020
}
3121
}
3222

33-
function gamma(obj, root, list, lvl)
23+
function mkscope(n, s)
24+
{
25+
for (let i = 0; i < n; i++)
26+
s = `\\scope_{0}(${s})`;
27+
28+
return s;
29+
}
30+
31+
function gamma(obj, root, list)
3432
{
3533
const node = obj.node;
3634

@@ -41,7 +39,7 @@ function gamma(obj, root, list, lvl)
4139

4240
list.push(`${root} = ${agent}`);
4341
} else {
44-
const agent = `\\cro_{${lvl}}(${root})`;
42+
const agent = mkscope(obj.index, root);
4543

4644
list.push(`${obj.name} = ${agent}`);
4745
}
@@ -51,38 +49,25 @@ function gamma(obj, root, list, lvl)
5149
const fv = getfv(body);
5250
const wire = mkwire();
5351
const agent = (id in fv) ? id : "\\erase";
54-
const tree = `\\lam_{${lvl}}(${agent}, ${wire})`;
52+
const tree = `\\lambda(${agent}, ${wire})`;
5553

5654
list.push(`${root} = ${tree}`);
5755

58-
gamma(body, wire, list, lvl);
56+
gamma(body, wire, list);
5957
} else if ("appl" == node) {
6058
const wleft = mkwire();
6159
const wright = mkwire();
6260
const left = obj.left;
6361
const right = obj.right;
6462
const shared = mktwins(left, right);
65-
const agent = `\\app_{${lvl}}`;
66-
const tree = `${agent}(${wright}, ${root})`;
67-
const fv = getfv(right);
68-
69-
for (const atom in fv) {
70-
const wref = mkwire();
71-
72-
fv[atom] = {
73-
ref: wref
74-
};
75-
}
76-
77-
subst(right, fv, "ref");
63+
const agent = `\\apply(${wright}, ${root})`;
7864

79-
list.push(`${wleft} = ${tree}`);
65+
list.push(`${wleft} = ${agent}`);
8066

81-
gamma(left, wleft, list, lvl);
82-
gamma(right, wright, list, lvl + 1);
67+
gamma(left, wleft, list);
68+
gamma(right, wright, list);
8369

84-
box(fv, list, lvl);
85-
psi(shared, list, lvl);
70+
psi(shared, list);
8671
}
8772
}
8873

@@ -95,9 +80,8 @@ function encode(generic, term)
9580
mkwire = generic.mkwire;
9681
mktwins = generic.mktwins;
9782
getfv = generic.getfv;
98-
subst = generic.subst;
9983

100-
gamma(term, "root", inconfig, 0);
84+
gamma(term, "root", inconfig);
10185

10286
inconfig.inet = template;
10387
return inconfig;

0 commit comments

Comments
 (0)