Hacker News Reader

Comment by aeonik | Hacker News Reader

I guess I'm curious how the implementation of Vector works in Lisps. I thought it would be some sort of combination of Atoms and Cons cells.

I looked into the Racket Repo to find something, but had a hard time finding the code.

View on HN

In Racket, a vector is a fixed-size contiguous array of memory. The values in each slot of a vector are tagged pointers so values like fixnums don't require any indirection to reach (i.e. they're unboxed). Racket also has specialized vector types for storing fixnums (fxvector), floats (flvector), strings (string) and bytes (bytes).

Other Schemes and Common Lisp have similar constructs. Just because a language is a lisp doesn't mean its primitives have to be implemented using cons cells.

As an example of other Schemes, here are the details of the representation used by Larceny (a Scheme):

https://www.khoury.northeastern.edu/home/lth/larceny/notes/n...

In a traditional-style Lisp which has atoms and cons cells, "atom" is not a specific type. It is a category which means "not a cons cell". Everything that is not a cons cell is an atom: symbol, string, number, character, vector, I/O stream, function, class object, ... Notice vector in there.

The purpose of a vector in Lisp is to provide contiguous storage with integer index addressing and O(1) access time.

Cons cells are typically used to provide lists with O(n) access time.

Reply on news.ycombinator.com