Hacker News Reader

Comment by Pxtl | Hacker News Reader

I can field that one. If a has A reference to B and B has a reference to C and C has a reference to A, then we have q cycle. Cycles play merry hell with garbage collectors and reference count destructors. Languages that force references to be a strict tree or DAG get cheap destruction in return - see C++ without pointers for example - I pop a local object off the stack and it's gone, along with all its children - no non-deterministic GC pause or delay, no Pythonic cycle check. Rust is built somewhat on this principle.

View on HN

Right. The way I'd put it is: in system software, the iron law is that you don't make the programmer pay for anything she doesn't need to buy.

What you pay (GC) for the privilege of having pointer cycles in your data is grossly disproportionate to the benefit. Yes, there are a lot of things that are O(k) with pointer cycles and O(log n) without them. If what you buy from this optimization is worth the cost of GC, you are doing a lot of these things... a lot.

But looking through code there are lots of references to gc, mark and sweep. Even with acyclic data models memory has to be cleared.

Rust does let you do circular references with Cell<&T> or Rc<Weak<T>>, but yeah, the standard assumption is that there are no circular references.

So "you really want your data model to be acyclic" means, "you want your programming language to forbid construction of cyclic data structures"? So, for example, connected graphs are not objects you can represent?

You can represent them symbolically, of course, as you do for instance in XML.

you can, but they become a special second-class type of reference separate from ownership.

They do - but arguably being forced to define the distinction between direct hierarchical references, and symbolic links, helps constrain your data model and make it more rigorous.

Note that relational databases don't have back pointers either. All references between tables are symbolic. Last century, people tried to make databases that were general pointer graphs (google "network database" or "object database") - broadly speaking, it was a disaster.

Did you mistype q cycle? I tried googling it, but found 0 relevant results.

I have never heard of it either, but I know some hoon and it makes intuitive sense to me.

If I tell you a linked list of atoms (@) is made from this tile (type):

[p=@ q=*]

it becomes obvious, right?

[p=1 q=[p=2 ..]]

[p=1 q=[p=2 q=[p=3 q=[p=4 q=~]]]]

This should look like building a list from 1-4. There are no cycles, ~ is a terminator.

Q is the reference to the next item in the list.

This would constitute a cycle:

z=[p=1 q=[p=2 q=z]]

My mistake, I think he meant to say "a cycle"

Oh, yeah. Sorry, typed that on phone. Just meant "a cycle".

Reply on news.ycombinator.com