LISP/computational thoughts

[harold]

Hello! And thanks again for the talk.

Perhaps in the spirit of Rich's talk, I hope you don't mind me using this space to write some thoughts on the fun 'puzzle' you hinted at re: computing atop these vectors.

I found this Kanerva paper: http://rctn.org/vs265/Kanerva-allerton2014.pdf

In section III.E (on page 4), we find this quote:

It is possible to define a 10,000-bit lisp on the same principle, by encoding each cell holographically as described above and by choosing vectors at random to serve as “pointers” to the next cell. It is unclear, however, whether a lisp of that kind would have any advantage over the Lisp we have now.

I am in complete agreement about this being 'unclear', but I also suspect that doing so might be a lot of fun (!).

One useful model that I know of is the metacircular evaluator described in SICP: https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-26.html

One question arises quickly:

Representing code as data: How might we encode a program as a vector (hdv)?

Taking baby steps, I can imagine this:

(add-hdv! 1)
(add-hdv! +)

But how might we then represent (+ 1 1)?

I am thinking about various cons cell representations that play well with the (non-nested) maps that are already implemented in this repository. But I'd like to hear other ideas you have perhaps around more directly storing lists with the protect operator, or any other ideas if you've thought along these lines already.

---

The metacircular evaluator seems conceptually attractive here because it allows us to incrementally move more and more of the notions into hdv space. Notably, the first version could take the program hdv vector (e.g., the vector encoding (+ 1 1)) and reconstitute it as a traditional list and pass it directly to Clojure's eval - thus computing 2.

Later, more and more of the evaluator itself (notably representable as lists of symbols) could be represented in hdv space. Possibly, the scaffolding originally borrowed from Clojure can be incrementally minimized and at some point the hdv lisp will be observable on its own. That's the first point I'd predict we might be able to spot some Kanervaian "advantage".

---

Would love to hear your thoughts and again to express my thanks for your fun talk and all the good stuff you bring to our community. It was an honor meeting you.

[gigasquid]

It was great meeting you too! Thanks for sparking the conversation here.

As far as the representation of (+ 1 1) as a cons cell using only the bind and bundle operations will run into problems when you want to deal with separate values that are similar. From the Kanerva paper you referenced:

This allows a sequence to be found by any of its elements, but it breaks down when different sequences contain the same or very similar elements

The protect operator is a way to overcome this - which would suggest that using that as a sequence structure might be a better approach.

I do really like your ideas around the metacircular evaluator, that would give it a nice pragmatic integration point - especially since computing with numbers would be easier in Clojure and one could focus more on the qualitative advantages of HDV.

It is very cool to to think of a single hyperdimensional vector that contains a data structure that represents a entire LISP program and then can eval and return another single hyperdimensional vector!

Of course the halting problem will still remain, but one might be able to give similarity metric to see how close another program would be to another that had finished :)

[harold]

Great thoughts! The point of lists with overlapping sub-lists is well-taken. Makes me think of Clojure's notion of structural sharing. (!)

I will think about program representation and come up with something.

It is very cool to to think of a single hyperdimensional vector that contains a data structure that represents a entire LISP program and then can eval and return another single hyperdimensional vector!

Yes. Very. Especially as the vector representing the lisp program includes, increasingly, relevant evaluation machinery. (:

[gigasquid]

A LISP also might be relevant for neuromorphic computing https://arxiv.org/pdf/2106.05268.pdf

[harold]

I intend to play with this, but came home from the conference w/ too many ideas. I'll be back! I promise :smile:

[harold]

gigasquid.vsa-data> (vb/reset-hdv-mem!)
{}
gigasquid.vsa-data> ;; We would like one plus one to be two...
gigasquid.vsa-data> (vb/add-hdv! nil)
#tech.v3.tensor<int8>[10000]
[-1 -1 -1 ... -1 1 1]
gigasquid.vsa-data> (vb/add-hdv! +)
#tech.v3.tensor<int8>[10000]
[1 -1 -1 ... 1 -1 1]
gigasquid.vsa-data> (vb/add-hdv! 1)
#tech.v3.tensor<int8>[10000]
[1 1 1 ... 1 1 -1]
gigasquid.vsa-data> ;; Code is data
gigasquid.vsa-data> (defn vsa-cons
                      [car cdr]
                      (map->vsa {:car car
                                 :cdr cdr}))
#'gigasquid.vsa-data/vsa-cons
gigasquid.vsa-data> (def plus-one-one (vsa-cons + (vsa-cons 1 (vsa-cons 1 nil))))
#'gigasquid.vsa-data/plus-one-one
gigasquid.vsa-data> (type plus-one-one)
tech.v3.datatype.unary_op$eval12168$fn$reify__12179
gigasquid.vsa-data> (count plus-one-one)
10000
gigasquid.vsa-data> ;; Now watch, as I pull a rabbit out of my hat...
gigasquid.vsa-data> (defn vsa-cons->list
                      [v]
                      (let [car (first (vsa-get v :car))
                            cdr (first (vsa-get v :cdr))]
                        (if (nil? cdr)
                          (cons car nil)
                          (cons car (vsa-cons->list cdr)))))
#'gigasquid.vsa-data/vsa-cons->list
gigasquid.vsa-data> (eval (vsa-cons->list plus-one-one))
2

:hand_over_mouth:

[gigasquid]

What! So Cool! Bravo 👏

[harold]

Ha! Thanks - I think it turned out well, I tried to match the spirit of the original work.

The whole thing is good for a giggle, thanks again for raising the topic and breaking the initial ground. Very cool.