Comment by hayley-patton | Hacker News Reader

Comment by hayley-patton | Hacker News Reader

Parent Full thread

There is another page <https://github.com/naver/lispe/wiki/2.5--LispE-vs.-Python:-A...> on implementation details that I don't get either.

In particular, the hash table apparently cannot have collisions, as "variables are necessarily unique". Sure, but there are only 64 buckets for 65,536 names, so it is further necessary for all variable names to be unique modulo 64, which can't be guaranteed. One option (which I believe CPython uses, more or less, by numbering locals and arguments) is to use De Bruijn indexes [0], but I'm not sure how to make it work with a tree-walking interpreter.

I'm also not sure how it is possible to come up with a reference-counting algorithm that performs "recursive increments", as an assignment X := Y only ever adds one incoming reference to Y from X. The example suggests the reference counts are the number of ways each value is transitively reachable, which is unnecessary and no one does that; Collin's original paper on reference counting [1] describes it as "a tally of the number of arrows pointing to [an object]" which is not transitive.

[0] https://en.wikipedia.org/wiki/De_Bruijn_index

[1] https://dl.acm.org/doi/10.1145/367487.367501

Hello,

The hash-table is actually a sparse table, which is extended whenever it is needed. If you have less than 64 values, then one bucket is enough. If you have 70, then you need two buckets. Basically, this sparse table is a table of at most 1024 element tables.

Since variable ids are contiguous, it means that you can fill in this sparse table element by element, only creating new buckets when needed.

So basically, what I'm doing is the following:

id / 64 -> yields the sub-table id % 64 -> yields the position in the sub-table

These operations are very fast since we are dealing with basic binary arithmetic.

I have been dealing with reference counting for years as I have implemented other programming languages in the past (see Tamgu for instance).

I only increment the reference counter in two cases:

a) A value is pushed into a container b) A value is stored in a variable

The fact that containers are classes, with their own methods to store elements makes it very simple to handle these cases. I only decrement the reference counter, when the value is removed from the container or the variable is modified and released.

Now, one of the things I do is that when I push a container A into another container B, I DO NOT modified the references of the elements in A. There are no recursive increments.

I don't know of any reference counting implementations which ever recursively increment counts though, so I don't see how it's an improvement on anything else.

Reply on news.ycombinator.com