Hey Pentti, We Did It!: A Fully Vector-Symbolic Lisp
Eilene Tomkins-Flanagan ([email protected]) · 2025
Read Hey Pentti, We Did It!: A Fully Vector-Symbolic Lisp by Eilene Tomkins-Flanagan ([email protected]) (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-2510-17889.txt.
Introduction
Eilene Tomkins-Flanagan and Mary A Kelly build a full Lisp programming language out of vectors that stand for symbols. The idea follows a suggestion by Kanerva that such a build should be possible. Their version covers the five basic Lisp functions, lambda forms, and helper functions from the classic Lisp 1.5 guide.
That small set is enough for full computing power, which the authors stress. A cleanup memory based on lookup tables keeps the vector codes readable. The paper links coding theory with the math of closed categories, and it shows that a vector-symbolic system can host a real language.
Catalog record
| CREATOR | Eilene Tomkins-Flanagan ([email protected]) |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-17889
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 It!: A Fully Vector-Symbolic Lisp Eilene Tomkins-Flanagan ([email protected]) Abstract Kanerva (2014) suggested that it would be possible to construct a complete Lisp out of a vector-symbolic architecture. We present the general form of a vector-symbolic representation of the five Lisp elementary functions, lambda expressions, and other auxiliary functions, found in the Lisp 1.5 specification McCarthy (1960) , which is near minimal and sufficient for Turing-completeness. Our specific implementation uses holographic reduced representations Plate (1995) , with a lookup table cleanup memory. Lisp, as all Turing-complete languages, is a Cartesian closed category nLab authors (2024) , unusual in its proximity to the mathematical abstraction. We discuss the mathematics, the purpose, and the significance of demonstrating vector-symbolic architectures’ Cartesian-closedness, as well as the importance of explicitly including cleanup memories in the specification of the architecture. Keywords: vector-symbolic architecture; Lisp; holographic reduced representations; cartesian closed category; modern hopfield network At Clojure/Conj 2023, the conference of the Clojure programming language, Meier (2023) introduced vector-symbolic architectures to the Clojure community. Her presentation echoed a motif oft heard listening to programmers who discover vector-symbolic architectures (VSAs) for the first time; namely, VSAs’ unusual properties and computational niceties are objects of fascination, but it is not immediately obvious what good a vector-symbolic architecture does for the programmer. We present an existence proof that VSAs are completely general computational tools. In technical terms, VSAs can do anything one wants. In pragmatic terms, “technically anything” does not answer questions of naturalness and ease of representation. To answer practical questions, VSAs have been used most frequently in representing human cognition, fruitfully in simultaneous localization and mapping (SLAM), and, pertinent to our analysis, promisingly in the syntactic manipulation of neural network states. In a remark at the end of her talk, Meier mentioned a “challenge”, issued by Kanerva, in “one of his papers”, to implement Lisp using exclusively a vector-symbolic architecture representing all the language’s expressions. However, the exact words read in the talk as a challenge, “One could create a ‘High dimensional computing-Lisp’ ”, do not seem to have been written by Kanerva. This apparent mistake is not Meier’s, as those exact words have been published in Neubert et al. (2019) , who attribute the enclosed quote to Kanerva (2014) . While the quote does not appear in Kanerva’s paper, the mistake is plausibly a case of miscitation of something said during the associated conference talk, and in any case it is not serious. Kanerva’s paper, disappointingly, does not include any challenge, but rather a discussion of how a vector-symbolic Lisp might be implemented, coupled with a loose specification of some of the tools that might be required to do so. We are going to pretend that counts as a challenge, and fully specify a Lisp language in terms of a generic VSA 1 1 1 Our implementation may be found at https://github.com/eilene-ftf/holis . Hold Up, What’s a VSA? 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”, 4. that is paired with a memory system \mathcal{M} that stores an inventory of known symbols for retrieval after lossy operations (e.g., inversion), 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. The + and \otimes operators behave analogously to disjunction and conjunction, or set-theoretic union and intersection. Additionally, VSAs may have an analogue for negation, often the vector rejection on Euclidean space \mathbf{rej}_{v}(u) Widdows & Cohen (2014) , and permutations \Pi , which are typically used to introduce asymmetry to the product operator, by applying different permutations to the operands. For a detailed review of vector symbolic architectures, see Kleyko et al. (2022) ; Kleyko et al. (2023) . Heddes et al. (2023) develop a software library for applying VSAs based on Torch. In our implementation, we use holographic reduced representations Plate (1995) . They are defined over Euclidean space \mathbb{R}^{n} , and have circular convolution as their product, cosine as their similarity, and atomic symbols sampled from a Gaussian distribution. Our memory system is a lookup table. Some VSAs (e.g., Kanerva (1996) ) are not defined over vector spaces per se, or otherwise relax some of the above properties, but behave sufficiently similarly to be used in a similar way. The programmer’s choice of VSA comes down to preference and different computational conveniences. For the most part, all VSAs are as good as all others. Vector-symbolic architectures are an answer to an old tension in cognitive science between the actual machinery of the brain and properties cognition is believed to necessarily possess. Brain states, to the one side, are described in terms of the activity of multiple cell populations, and they exist over a fixed number of cells. Information is typically assumed to be distributed over measured populations, degrading gracefully and uniformly when cells are disabled at random. To the other, Fodor & Pylyshyn (1988) made a compelling case that central cognition must have states that behave like discrete symbols, that can be strung together in a combinatorial syntax. But, the traditional tool for representing such syntaxes, computer memory, uses strings of bits for individual symbols, composed by concatenation into ever-longer strings. With disjunction (sum), conjunction (product), inverse, and similarity operations, plus a cleanup memory, a VSA is sufficient to describe any syntax one could want, to a finite precision. Thus, VSAs appear to satisfy the cognitive scientist’s parallel demands for syntax and biomimicry. Cartejian Clojure and Lisp A Cartesian closed category nLab authors (2024) is the mathematical generalization of what it means to compute. It generalizes the equivalence of universal Turing machines ( Li & Vitányi (2008) , ch. 1) with other definitions of computation, set theory, first-order logic, and, of interest to us, the recursively enumerable languages \mathbf{RE} Chomsky (1955) . All instances of a Cartesian closed category have the preceding equivalences; to say that C is Cartesian closed is also to say that it is Turing-complete. It follows that C can define \mathbf{RE} , and, therefore, any syntax, as the language generated by any syntax rules, or grammar, is a subset of that generated by \mathbf{RE} . Categories have two contents: objects and morphisms 2 2 2 Generally, a morphism is any way objects can be related such that, if you have two morphisms f , g , you can construct h=f\circ g such that h(a)=f(g(a)) for some appropriate notion of equivalence. . For example, while we normally treat vector spaces as sets of vectors augmented with some functions, they are equally categories that include both vectors (their objects) and functions (their morphisms). Cartesian closed categories in particular are useful because they are very simple,