4 ms·

Having circular references is a logic bug. I don't believe there's any algorithm in existence that requires circular references.

chris_overseas 11y ago
As a trivial example of a data structure with circular references, how about a doubly linked list? Admittedly there are alternative data structures to solve the same problem (eg an array), but that changes the performance characteristics too and may not be optimal for your particular use case. This isn't the point though. A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this. Even if such a restriction was in place it would have to be enforced at runtime which doesn't sound like a trivial problem from a performance point of view.
- bsdetector 11y ago
  An even more trivial example is a singly-linked list with a sentinel node (the last node points back to it). But that's not really the question here. Any linked list is not an algorithm, it's a data structure. The question is what operations can you do using circular references cannot be done without. I think otabdeveloper1 is right, because you can use a garbage collection type process to 'run' any other algorithm on a graph with cycles in it, using temporary lists and stacks to do whatever the algorithm would use circular references for.
  - mikeash 11y ago
    It seems obvious that you can do anything without circular references. Proof: implement a Turing machine without using them. The question is whether it's a reasonable constraint for real-world programs. In theory, Malbolge can be used to perform any algorithm, but few people would actually want to. Circular references are really convenient in many cases. For example, view hierarchies typically have a pointer from a view back to its parent view. This means you can walk up the view hierarchy as well as down, so you can find sibling views, remove a view from its parent, invalidate a parent's layout when the view's sizing needs change, and stuff like that. Without circular references you could still accomplish all this, it just becomes slower and more painful. In practice, reference cycles are a big problem for ARC. One of the most common questions I see with Objective-C and Swift programmers is when it's necessary to use a weak reference to self in a block, and when it's necessary to use a strong reference. It's difficult enough that I've seen a lot of people just punt on the entire question and go for "always capture self as a weak reference no matter what." Which works most of the time, and occasionally creates entertaining bugs. Even for experienced developers it's easy to miss a spot occasionally, and end up with a silent leak or a subtle bug.
- otabdeveloper1 11y ago
  > As a trivial example of a data structure with circular references, how about a doubly linked list? Not really, no. There's no reason why the backlink should increment the reference count. Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. E.g., circular references are never a problem in C++. > A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this. Really? Why not? "We don't support refcounted circular references, please rewrite your code if you use them" is a perfectly valid design decision. Personally, I'd rather have that than some rube-goldberg type monstrocity of a memory management system just to support a very obscure corner case.
  - lispm 11y ago
    > Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. How so?
  - mikeash 11y ago
    If you allow backlinks which don't increment the reference count, then you have circular references. You're just helping a reference counting implementation deal with them. The end result is the same as a GC, except you need more programmer intervention, and the only sign that you've got your intervention wrong is a memory leak, a crash, or mysterious misbehavior.
    - paulhodge 11y ago
      More specifically.. a link that doesn't touch the reference count is a weak reference. It's a known strategy and it does avoid the problem where a cycle can't be collected. If the weak references are safe (as in, their pointer is assigned to 0 when the target object is collected) then I think there can be performance issues (compared to the competition of a tracing GC). If the weak references aren't safe, then you have a data structure that's more in the realm of manual memory management, so it's hard to draw a fair comparison with fully memory-managed objects.
vog 11y ago
It depends on how closely you define "circular references". Assume you have an algorithm that does make use of circular references. Then, you could replace all pointers by integers. And you could put all referenced data into a large array. That way you would have "broken up" all circular references. However, from another point of view, you could argue that your algorithm still makes use of circular references, they are just expressed differently. (Also, now no garbage collector will help you cleaning up that thing, other than releasing that large array at once. So that's not really an improvement.)
nhaehnle 11y ago
Constant-space iteration over the elements of a balanced binary tree requires parent pointers and therefore requires circular references.
- cwzwarich 11y ago
  That isn't strictly true. If you add the qualifier "without mutating the tree" then you are correct. Otherwise, you can avoid parent pointers by reversing pointers while you traverse, but this requires using a bit per node (which you can generally steal from a pointer in practice) to indicate whether a visited node was the left or right child of its parent. Getting rid of the extra bit is trickier, but it can be done, e.g. Robson traversal that uses the links of leaf nodes to store the stack.
chrisseaton 11y ago
Why do you think circular references are a logic bug?

chris_overseas 11y ago

As a trivial example of a data structure with circular references, how about a doubly linked list? Admittedly there are alternative data structures to solve the same problem (eg an array), but that changes the performance characteristics too and may not be optimal for your particular use case. This isn't the point though. A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this. Even if such a restriction was in place it would have to be enforced at runtime which doesn't sound like a trivial problem from a performance point of view.

bsdetector 11y ago
An even more trivial example is a singly-linked list with a sentinel node (the last node points back to it). But that's not really the question here. Any linked list is not an algorithm, it's a data structure. The question is what operations can you do using circular references cannot be done without. I think otabdeveloper1 is right, because you can use a garbage collection type process to 'run' any other algorithm on a graph with cycles in it, using temporary lists and stacks to do whatever the algorithm would use circular references for.
- mikeash 11y ago
  It seems obvious that you can do anything without circular references. Proof: implement a Turing machine without using them. The question is whether it's a reasonable constraint for real-world programs. In theory, Malbolge can be used to perform any algorithm, but few people would actually want to. Circular references are really convenient in many cases. For example, view hierarchies typically have a pointer from a view back to its parent view. This means you can walk up the view hierarchy as well as down, so you can find sibling views, remove a view from its parent, invalidate a parent's layout when the view's sizing needs change, and stuff like that. Without circular references you could still accomplish all this, it just becomes slower and more painful. In practice, reference cycles are a big problem for ARC. One of the most common questions I see with Objective-C and Swift programmers is when it's necessary to use a weak reference to self in a block, and when it's necessary to use a strong reference. It's difficult enough that I've seen a lot of people just punt on the entire question and go for "always capture self as a weak reference no matter what." Which works most of the time, and occasionally creates entertaining bugs. Even for experienced developers it's easy to miss a spot occasionally, and end up with a silent leak or a subtle bug.
otabdeveloper1 11y ago
> As a trivial example of a data structure with circular references, how about a doubly linked list? Not really, no. There's no reason why the backlink should increment the reference count. Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. E.g., circular references are never a problem in C++. > A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this. Really? Why not? "We don't support refcounted circular references, please rewrite your code if you use them" is a perfectly valid design decision. Personally, I'd rather have that than some rube-goldberg type monstrocity of a memory management system just to support a very obscure corner case.
- lispm 11y ago
  > Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. How so?
- mikeash 11y ago
  If you allow backlinks which don't increment the reference count, then you have circular references. You're just helping a reference counting implementation deal with them. The end result is the same as a GC, except you need more programmer intervention, and the only sign that you've got your intervention wrong is a memory leak, a crash, or mysterious misbehavior.
  - paulhodge 11y ago
    More specifically.. a link that doesn't touch the reference count is a weak reference. It's a known strategy and it does avoid the problem where a cycle can't be collected. If the weak references are safe (as in, their pointer is assigned to 0 when the target object is collected) then I think there can be performance issues (compared to the competition of a tracing GC). If the weak references aren't safe, then you have a data structure that's more in the realm of manual memory management, so it's hard to draw a fair comparison with fully memory-managed objects.

vog 11y ago

It depends on how closely you define "circular references". Assume you have an algorithm that does make use of circular references. Then, you could replace all pointers by integers. And you could put all referenced data into a large array. That way you would have "broken up" all circular references. However, from another point of view, you could argue that your algorithm still makes use of circular references, they are just expressed differently. (Also, now no garbage collector will help you cleaning up that thing, other than releasing that large array at once. So that's not really an improvement.)

nhaehnle 11y ago

Constant-space iteration over the elements of a balanced binary tree requires parent pointers and therefore requires circular references.

cwzwarich 11y ago
That isn't strictly true. If you add the qualifier "without mutating the tree" then you are correct. Otherwise, you can avoid parent pointers by reversing pointers while you traverse, but this requires using a bit per node (which you can generally steal from a pointer in practice) to indicate whether a visited node was the left or right child of its parent. Getting rid of the extra bit is trickier, but it can be done, e.g. Robson traversal that uses the links of leaf nodes to store the stack.

chrisseaton 11y ago

Why do you think circular references are a logic bug?