Lisp and hash tables

I don't know if this has already been said by anyone else, but:

It’s well known that lisp is based on lists, but lists are based on pairs, so lisp is based on pairs, but pairs are actually vectors of length two, so lisp is based on vectors, but vectors are a very simple case of hash tables, so in the end lisp is based on hash tables.

What do you think?


On what are hash tables based?

How about a cons-cell consisting of two pointers?

Hi @matteo-daddio ,

Where are you actually trying to get at with this reasoning?

Such chains can generally be made very long, and each connection is kind of arbitrary. For example, you ended in hash tables, but @joskoot went further to cons cells. You could also go to axiomatic set theory.

On the other hand, Lisp's syntax is very close to lambda calculus, which starts a wholly different chain.

Incidentally, this discussion makes me think about The Glass Bead Game - Wikipedia :

The game is essentially an abstract synthesis of all arts and sciences. It proceeds by players making deep connections between seemingly unrelated topics.

It’s only a joke :slightly_smiling_face:

But thinking about it better, hash tables are trees and trees are lists of lists, so we are back to the beginning.

I think the basic idea are graphs. Every data structure can be seen as a graph, even programs, that are indeed data, are graphs.

In racket, with mutable pairs, is possible to create graphs, so is possible to create every data structure.


1 Like

You could say that everything is a mutable vector, because that's what computer memory is.

Well... maybe what it was, decades ago, on a small personal computer.

Today that linear address space is an illusion backed by a whole hierarchy of cache levels, pages mapped to various RAM chips, swap files on "disk", etc.

So I suppose everything is a hash-table of hash-tables, after all. :smile:


There are two point of view: make complex data structure with simple data structure and consider small data structure as a simple case of complex data structure.

For example hash tables are made of pairs and pairs can be seen as very simple hash tables.

Also complex numbers: real numbers are complex numbers with zero imaginary part and complex numbers can be seen as a couple of real numbers.