systile 1.0.0

Matmul-native data structures & algorithms: 17 structures (holographic memory, semiring graphs, automata, attention, DFT, Viterbi, k-NN, Bloom, sort, scan, …) whose core operation reduces to a dense matmul, built on a TPU-style tiled tensor with a systolic reference engine.
Documentation 
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

//! Tests for the hyperdimensional algebra.

use systile::Hyper;

#[test]
fn atom_is_bipolar() {
    let a = Hyper::atom(1024, 1, 0);
    assert!(a.as_slice().iter().all(|&x| x == 1.0 || x == -1.0));
}

#[test]
fn atom_is_deterministic() {
    assert_eq!(Hyper::atom(512, 7, 3), Hyper::atom(512, 7, 3));
}

#[test]
fn different_ids_differ() {
    assert_ne!(Hyper::atom(512, 7, 3), Hyper::atom(512, 7, 4));
}

#[test]
fn different_seeds_differ() {
    assert_ne!(Hyper::atom(512, 1, 0), Hyper::atom(512, 2, 0));
}

#[test]
fn distinct_atoms_are_near_orthogonal() {
    let a = Hyper::atom(8192, 42, 0);
    let b = Hyper::atom(8192, 42, 1);
    // Random bipolar vectors of dim d have cosine ~ N(0, 1/d); |cos| << 0.1.
    assert!(a.cosine(&b).abs() < 0.1, "cosine was {}", a.cosine(&b));
}

#[test]
fn atom_is_unit_under_cosine_with_self() {
    let a = Hyper::atom(1024, 3, 9);
    assert!((a.cosine(&a) - 1.0).abs() < 1e-6);
}

#[test]
fn bind_is_self_inverse() {
    let a = Hyper::atom(1024, 1, 0);
    let b = Hyper::atom(1024, 1, 1);
    assert_eq!(a.bind(&b).bind(&b), a);
}

#[test]
fn bind_is_commutative() {
    let a = Hyper::atom(256, 1, 0);
    let b = Hyper::atom(256, 1, 1);
    assert_eq!(a.bind(&b), b.bind(&a));
}

#[test]
fn bind_is_dissimilar_to_operands() {
    let a = Hyper::atom(8192, 1, 0);
    let b = Hyper::atom(8192, 1, 1);
    let c = a.bind(&b);
    assert!(c.cosine(&a).abs() < 0.1);
    assert!(c.cosine(&b).abs() < 0.1);
}

#[test]
fn bundle_is_similar_to_members() {
    let a = Hyper::atom(8192, 1, 0);
    let b = Hyper::atom(8192, 1, 1);
    let mut bundle = Hyper::zeros(8192);
    bundle.bundle_into(&a);
    bundle.bundle_into(&b);
    // The superposition is positively correlated with each member.
    assert!(bundle.cosine(&a) > 0.5);
    assert!(bundle.cosine(&b) > 0.5);
}

#[test]
fn unbundle_reverses_bundle() {
    let a = Hyper::atom(512, 1, 0);
    let b = Hyper::atom(512, 1, 1);
    let mut bundle = a.clone();
    bundle.bundle_into(&b);
    bundle.unbundle(&b);
    assert_eq!(bundle, a);
}

#[test]
fn sign_returns_bipolar() {
    let v = Hyper::from_vec(vec![3.0, -2.0, 0.0, -0.5]);
    assert_eq!(v.sign().as_slice(), &[1.0, -1.0, 1.0, -1.0]);
}

#[test]
fn permute_then_inverse_is_identity() {
    let a = Hyper::atom(257, 1, 0);
    assert_eq!(a.permute(5).inverse_permute(5), a);
}

#[test]
fn permute_changes_the_vector() {
    let a = Hyper::atom(256, 1, 0);
    assert_ne!(a.permute(1), a);
}

#[test]
fn permute_preserves_norm() {
    let a = Hyper::atom(256, 1, 0);
    assert!((a.permute(7).norm() - a.norm()).abs() < 1e-6);
}

#[test]
fn dot_of_atom_with_self_is_dim() {
    let a = Hyper::atom(1024, 1, 0);
    assert_eq!(a.dot(&a), 1024.0);
}