Hey Pentti, We Did (More of) It!: A Vector-Symbolic Lisp With Residue Arithmetic

Connor Hanley, Eilene Tomkins-Flanagan, Mary Alexandria Kelly · 2025

Read Hey Pentti, We Did (More of) It!: A Vector-Symbolic Lisp With Residue Arithmetic by Connor Hanley, Eilene Tomkins-Flanagan, Mary Alexandria Kelly (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08767.txt.

Introduction

Connor Hanley, Eilene Tomkins-Flanaganm, and Mary Alexandria Kelly give a vector-symbolic computer a missing skill: arithmetic. Their starting point is an encoding of Lisp 1.5, a classic language, inside vectors with thousands of entries. The encoding uses frequency-domain holographic codes, where programs become structured neural states.

Residue hyperdimensional computing supplies number forms that support math directly in the vector space. Adding those tools extends the encoded language, so network states can hold richly structured, still readable forms. The authors discuss machine learning uses for such schemes. They also argue that more general intelligent agents will need networks whose behavior is sensitive to the structure of what they hold, not just to surface statistics.

Catalog record

CREATORConnor Hanley, Eilene Tomkins-Flanagan, Mary Alexandria Kelly
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-08767

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hey Pentti, We Did (More of) It!: A Vector-Symbolic Lisp With Residue Arithmetic Connor Hanley, Eilene Tomkins-Flanagan, Mary Alexandria Kelly Abstract Using Frequency-domain Holographic Reduced Representations (FHRRs), we extend a Vector-Symbolic Architecture (VSA) encoding of Lisp 1.5 with primitives for arithmetic operations using Residue Hyperdimensional Computing (RHC). Encoding a Turing-complete syntax over a high-dimensional vector space increases the expressivity of neural network states, enabling network states to contain arbitrarily structured representations that are inherently interpretable. We discuss the potential applications of the VSA encoding in machine learning tasks, as well as the importance of encoding structured representations and designing neural networks whose behavior is sensitive to the structure of their representations in virtue of attaining more general intelligent agents than exist at present. 1 Introduction [ 44 ] define an encoding for Lisp [ 29 ] in vector-space, as well as an interpreter defined over the encoded representations. This allows for the implementation of any computable procedure, and for the computation of that procedure, entirely in vector-space. To do this, they encode Lisp expressions in a vector-symbolic architecture, which when paired with a memory system, is as expressive as a Turing machine. In this paper, we contribute a novel integer encoding using Residue Hyperdimensional Computing 1 1 1 Our implementation may be found at https://github.com/hanleyc01/residuelisp . Residue Hyperdimensional Computing is a vector-symbolic architecture based on residue arithmetic, allowing for a unique code for any integer, as well carry-free arithmetic operations. In subsection 1.1 , we recapitulate the generalization of vector-symbolic algebras used in [ 44 ] . In subsection 1.2 , we give a short introduction to Residue arithmetic and the Residue Hyperdimensional Encoding proposed by [ 28 ] . In subsection 1.3 , we define Resonator networks following [ 24 , 12 ] , a state-of-the-art method for factorizing complex vector-symbolic expressions, used in the implementation of Residue Hyperdimensional Computing. In subsection 1.4 we discuss our novel contributions to the the encoding of Lisp in vector-symbolic architectures. In Section 2 , we provide definitions of the encoding of integers in the Lisp implementation, and associated semantic functions. In Section 3 , we discuss the importance of our contributions, motivating it by providing potential concrete use cases in learning tasks, as well as by appealing to recent literature on the need for algebraic representations for general intelligence. 1.1 Formalizing VSAs [ 44 ] define a generic vector-symbolic architecture (VSA) as follows: A vector-symbolic architecture is an algebra (i.e., a vector space with a bilinear product), 1. that is closed under the product \otimes:V\times V\to V (i.e., if u\otimes v=w , then u,v,w\in V ) 2. whose product has an “approximate inverse” \overline{\otimes} that, given a product w and one of its operands u or v , yields a vector correlated with the other operand 3. for which there is a dogma for selecting vectors from the space to be treated as atomic “symbols” (yielding themselves, thereby, to syntactic manipulations defined in terms of the algebra), 4. that is paired with a memory system \mathcal{M} that stores an inventory of known symbols for retrieval after lossy operations (e.g., involution), that can be recalled from \mathcal{M}(p) , and which is appendable \mathcal{M}\twoheadleftarrow t , and 5. possesses a measure of the correlation (a.k.a., similarity) of two vectors, \mathbf{sim}(u,v)\in[-1,1] , where 1 and -1 imply that u,v are colinear, 0 that they are linearly independent. Some VSAs relax some of the preceding properties [ 37 , 42 , 23 , 26 ] , but have behavior approximating all listed properties. Importantly, the “dogma for selecting symbols” may be freely chosen, so they can be arbitrary semantic embeddings , including the token embeddings of a neural network, photographs [ 22 ] , or (recursively) complex symbolic expressions generated by another VSA [ 21 ] . Most of our symbols will be drawn from a random overcomplete basis to minimize any possible influence of the distribution of the symbols on computations, but our numeric representations, importantly, are related to one another by a group structure [ 34 ] . Under the above definitions, it can be shown [ 44 ] that VSAs are Cartesian closed [ 33 ] , implying that Turing-complete languages can be described over any VSA. The VSA Lisp is accordingly described for a generic VSA, meaning that it can be implemented in any VSA. The reference implementation uses the Holographic Reduced Representations (HRRs) described by [ 36 ] . For this implementation, we used Fourier-domain Holographic Reduced Representations [ 38 , 34 , 47 , 26 ] (FHRRs), which are closed under the same algebraic properties, but have the added benefit of being a generalization over the arithmetical encoding. For example, the product \otimes is element-wise multiplication (i.e., the Hadamard product) \odot , the sum is element-wise addition + , the inverse of the product of two vectors u,v is (u\odot v)\odot\overline{u}\approx v w, and the similarity kernel for two vectors u,v of dimension D is \frac{\mathfrak{R}\{\overline{u^{T}}v\}}{D}, (1) with \overline{u^{T}} being the complex conjugate transpose of u , and \mathfrak{R} the real component of a complex vector. What distinguishes FHRRs from HRRs is, instead of converting the vectors into the Fourier-domain to implement circular convolution, which is the binding operation for HRRs, we rather remain entirely in the Fourier-domain. For a full comparison of HRRs and FHRRs, as well as the later introduced Residue Hyperdimensional Computing VSAs, see Table 1 . Table 1: Comparison of HRRs, FHRRs, and RHCs; first two reproduced from [ 26 ] VSA Space of atomic vectors Binding Unbinding Superposition Similarity HRR unit vectors circular convolution circular correlation element-wise additon dot product similarity FHRR complex unitary vectors element-wise product/ Hadamard product element-wise product with inverse element-wise addition cosine similarity RHC subset of complex unitary vectors additive binding and multiplicative binding element-wise product with inverse/ multiplicative binding with inverse modulo m element-wise addition cosine similarity 1.2 Residue Arithmetic and Residue Hyperdimensional Computing A residue number system, or residue coding, is a scheme by which we can uniquely encode integers into vectors of their value moduli a sequence of relative co-prime values [ 13 ] . Let M_{n}=[m_{1},m_{2},\ldots,m_{n}] be a vector of co-prime positive integers. To encode an arbitrary integer x into a residue number system with moduli M_{n} , we would have, [x\bmod m_{1},x\bmod m_{2},\ldots,x\bmod m_{n}]. (2) We are also able to define carry-free arithmetical operations over residue numbers, which are just element-wise sum and multiplication modulo m_{i} , for i=1,2,\ldots,n . In the same way that FHRRs sample uniformly from the range (0,2\pi] [ 26 ] in order to create complex-valued elements, for some moduli m_{i} we can sample from the m_{i} -th roots of unity of the unit circle for vector elements, which is called Residue Hyperdimensional Computing [ 28 ] (RHC). Encoding integers in D -dimensional RHC is a two-step process: First, define a set of D co-prime positive integer moduli M_{n}=[m_{1},m_{2},\ldots,m_{n}]. (3) For each m_{i} , i=1,2,\ldots,n , let \phi_{i}=[\theta_{1},\theta_{2},\ldots,\theta_{D}], (4) where each \theta_{j} , j=1,2,\ldots,D is a randomly sampled angle from the m_{i} -th roots of unity. E.g., suppose some m_{k} were 2 . Then, each of angle in \phi_{k} would be sampled from the set \{\pi,2\pi\} . The residue moduli are finally

Read the complete text