Hand-written tests for porting boolean operators from the Lambda Calculus and/or Smullyan Forest to Concatenative Combinators. Yet another reminder to...
“Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.”—Dr. Alan J. Perlis, 1982
![// [B] [A] And == [B && A]
test("boolean and", () => {
expect(display(rewrite([ [False], [False], And ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [False], [True], And ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [True], [False], And ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [True], [True], And ]))).toEqual(display(rewrite([ [True] ])));
});
// [B] [A] Or == [B || A]
test("boolean or", () => {
expect(display(rewrite([ [False], [False], Or ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [False], [True], Or ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [False], Or ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [True], Or ]))).toEqual(display(rewrite([ [True] ])));
});
// [A] Not == [¬A]
test("boolean not", () => {
expect(display(rewrite([ [False], Not ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], Not ]))).toEqual(display(rewrite([ [False] ])));
});
// [B] [A] Xor == [(B || A) && ¬(B && A)]
test("boolean or", () => {
expect(display(rewrite([ [False], [False], Xor ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [False], [True], Xor ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [False], Xor ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [True], Xor ]))).toEqual(display(rewrite([ [False] ])));
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreicxis6ini7ovwo4nhaw3swqtvevxrdo7ppumyuwhbjivdqaxoy64e)
![export const times = b;
export const plus = construction([ [cons, b], cons, s ]);
export const exponent = i;
export const succ = construction([ [z1], plus ]);
export const pred = construction([
// initialization
[[z0], [z0]],
// [[__], [Zn]] => [Zn], [++Zn]
[i, nip, dup, [succ], cons],
// dig the quoted parameter up: [C] [B] [A] => [B] [A] [C]
dig,
// apply it, counting up: [z0], [z0] => [z0], [z1] => [z1], [z2] => [z2], [z3], ...
i,
// discard the rightmost quoted number, revealing the quoted predecessor
zap,
// apply it
i
]);
test("pred", () => {
expect((rewrite([[[]], [unit], [z0], pred]))).toEqual(rewrite([[[]], [unit], z0]));
expect((rewrite([[[]], [unit], [z1], pred]))).toEqual(rewrite([[[]], [unit], z0]));
expect((rewrite([[[]], [unit], [z2], pred]))).toEqual(rewrite([[[]], [unit], z1]));
expect((rewrite([[[]], [unit], [z3], pred]))).toEqual(rewrite([[[]], [unit], z2]));
expect((rewrite([[[]], [unit], [z4], pred]))).toEqual(rewrite([[[]], [unit], z3]));
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreigam5tt37az5nilpbazhck52dw442x3tm37wf53cyl6drktdqxnxe)
![test("product", () => {
expect(rewrite([ [], [unit], [z0], [z3], product ])).toEqual(rewrite([ [], [unit], z0 ]));
expect(rewrite([ [], [unit], [z3], [z0], product ])).toEqual(rewrite([ [], [unit], z0 ]));
expect(rewrite([ [], [unit], [z1], [z5], product ])).toEqual(rewrite([ [], [unit], z5 ]));
expect(rewrite([ [], [unit], [z5], [z1], product ])).toEqual(rewrite([ [], [unit], z5 ]));
expect(rewrite([ [], [unit], [z2], [z3], product ])).toEqual(rewrite([ [], [unit], z6 ]));
expect(rewrite([ [], [unit], [z3], [z2], product ])).toEqual(rewrite([ [], [unit], z6 ]));
});
test("sum", () => {
expect(rewrite([ [], [unit], [z0], [z3], sum ])).toEqual(rewrite([ [], [unit], z3 ]));
expect(rewrite([ [], [unit], [z3], [z0], sum ])).toEqual(rewrite([ [], [unit], z3 ]));
expect(rewrite([ [], [unit], [z1], [z5], sum ])).toEqual(rewrite([ [], [unit], z6 ]));
expect(rewrite([ [], [unit], [z5], [z1], sum ])).toEqual(rewrite([ [], [unit], z6 ]));
expect(rewrite([ [], [unit], [z2], [z3], sum ])).toEqual(rewrite([ [], [unit], z5 ]));
expect(rewrite([ [], [unit], [z3], [z2], sum ])).toEqual(rewrite([ [], [unit], z5 ]));
});
test("exponent", () => {
expect(rewrite([ [], [unit], [z2], [z0], exponent ])).toEqual(rewrite([ [], [unit], z1 ]));
expect(rewrite([ [], [unit], [z2], [z1], exponent ])).toEqual(rewrite([ [], [unit], z2 ]));
expect(rewrite([ [], [unit], [z2], [z2], exponent ])).toEqual(rewrite([ [], [unit], z4 ]));
expect(rewrite([ [], [unit], [z2], [z3], exponent ])).toEqual(rewrite([ [], [unit], z8 ]));
expect(rewrite([ [], [unit], [z3], [z2], exponent ])).toEqual(rewrite([ [], [unit], z9 ]));
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiec2jhfcepaw6xkueuiuitxaw6cgqyhkozgtqvsslneu3yh5xliiu)
![// [C] [B] [A] s == [[C] B] [C] A
export const s = combinator((C: Quotation, B: Quotation, A: Quotation) => [ [C, ...B], C, ...A ]);
export const starling = s;
// [B] [A] k == A
export const k = combinator((B: Quotation, A: Quotation) => [ ...A ]);
export const kestrel = k;](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiewblb5opxs26itxj3mpszjaqyic6qmei2u7xic7zofmw7ujli27a)
![test("zn", () => {
expect(z0([ [z0], [z1] ])).toEqual([ z0 ]);
expect(z1([ [z0], [z1] ])).toEqual([ [ z0 ], z1 ]);
expect(z2([ [z0], [z1] ])).toEqual([ [ [ z0 ], z1 ], z1 ]);
expect(z3([ [z0], [z1] ])).toEqual([ [ [ [ z0 ], z1 ], z1 ], z1 ]);
expect(z4([ [z0], [z1] ])).toEqual([ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ]);
expect(z5([ [z0], [z1] ])).toEqual([ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z6([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z7([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z8([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z9([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiapiw4qcccf7ewmttazpi2to3256jdzxj7zdcoe7fodxrwtqy2a7y)
![// [B] [A] cons == [[B] A]
export const cons = combinator((B: Parameter, A: Parameter) => {
if (!isProgram(A)) return Fail;
if (!isProgram(B)) return Fail;
if (A.length === 0) return Fail;
if (B.length === 0) return Fail;
return [ [B, ...A] ];
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreicgxmuu5kwdyqocdlvbzzrpniq3cw4abij4wgin4bice4fxudygga)
![### the list interpretation of balanced parentheses
Chaining cons cells together by the `cdr` pointer creates a list. For example, this is a list of five holes —`()()()()()`—diagrammed to show the links:
```mermaid
graph LR
EmptyPair@{ shape: dbl-circ, label: "()" }
Five(["()()()()()"]) --> Four(["()()()()"])
Four --> Three(["()()()"])
Three --> Two(["()()"])
Two --> EmptyPair
```
We don't call it a list of empty pairs. The pairs we write in text notation are containers, and if the pairs contain empty, than we say this is a list of five holes.
A list of five empty pairs looks like this:
```mermaid
graph TD
EmptyPair@{ shape: dbl-circ, label: "()" }
Five(["(())(())(())(())(())"]) --o EmptyPair
Five --> Four(["(())(())(())(())"])
Four --o EmptyPair
Four --> Three(["(())(())(())"])
Three --o EmptyPair
Three --> Two(["(())(())"])
Two --o EmptyPair
Two --> One(["(())"])
One --o EmptyPair
```](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiep2bm4ce7kdxdz2k7bg6k4t7rkjzcuuksbjqmd4xo5lkls3kruhe)
![### the cons cell interpretation of balanced parentheses
An empty pair of parentheses is a cons cell with both its `car` and `cdr` pointing to the empty string (`ε`). The `car` pointer terminates in a circle, the `cdr` pointer terminates in an arrow.
```mermaid
graph LR
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```
Either or both can point to another cons cell:
```mermaid
graph LR
B(["(())"]) -- car --o A
B(["(())"]) -- cdr --> E
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```
```mermaid
graph LR
C(["()()"]) -- car --o E
C(["()()"]) -- cdr --> A
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```
```mermaid
graph LR
D(["(())()"]) -- car --o A
D(["(())()"]) -- cdr --> A
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreib3puribiy3hpgw4ftnvnfqqdctplnk7ray53czr4ankecrg4hk3q)