Algorithm for cycle-detecting comparison

Question

I am looking for an algorithm that I can use to compare nested and potentially recursive data structures, for example to implement the Scheme equal? function. equal? recursively compares two objects for equality and properly handles cycles. Specifically, the algorithm needs to return true iff the (possibly infinite) unfoldings of the graphs would be equal, e.g.

(letrec ((a (cons 1 (cons 2 a)))
         (b (cons 1 (cons 2 (cons 1 (cons 2 b))))
  (equal? a b))

is true because a and b are both cyclic lists that repeat the sequence (1 2) infinitely.

Destructive modification of traversed nodes is thread-unsafe, requires a spare bit in object headers, and requires a separate traversal to reset the bit. Using a hash table to store object addresses is not safe in the presence of a moving garbage collector unless the GC is blocked for the duration of the traversal (so the operation cannot be implemented except as a primitive).

Answer 1

There is no pure way to detect cycles, where by pure I mean without caring about representation details such as object addresses. If you only allow examining data by comparing fields at base types, then there is no way to distinguish e.g. a cyclic list from a very long list. If you start examining

(1 2 3 4 5 6 7 8 9 10 11 …
(1 2 3 4 5 6 7 8 9 10 11 …

then maybe one of them is the list (1 2 3 4 5 6 7 8 9 10 11) and the other is (repeat (1 2 3 4 5 6 7 8 9 10 11) where (repeat cycle) builds a cyclic list that repeats its arguments — but you need to examine one more node to find the difference. Since the difference could be arbitrary far, there's no way to prove that two cyclic lists are equal.

The most practical solution is to compare object addresses to detect cycles. I expect that this is how most Scheme implementations do it. This requires some knowledge of how the garbage collector works, and specifically the ability to temporarily prevent it from relocating any object that is within the already-traversed part of the data structure. Locking GC moves might not hurt much, it depends on the GC technology: a mark-and-sweep GC doesn't need to move objects.

By the way, mark-and-sweep GC usually detect cycles by using a spare bit in the object. But that doesn't generalize well to arbitrary processing of arbitrary data structures.

If you're building your own data structure, as opposed to having to cope with arbitrary data structures like equal?, then a good approach is to not store cycles. Purely functional data structures typically don't have cycles in the first place since they can only create cycles with a statically-known structure which is not very useful. As with many problems in computing, this is solved by adding a level of indirection: instead of having the data structure contain a pointer chain that loops back to itself, have it contain references, i.e. the data structure is represented as some kind of map from identifiers from elements and nested data structures are stored using their identifier. When doing this, it's useful to perform hash consing, i.e., when applying a constructor, verify if the result is already referenced in the map and if so use the existing identifier rather than making a new one. This can save memory, and also processing time since traversal algorithms never need to handle the same data structure twice. In particular, with this trick, you can test equality of data structures by simply testing equality of identifiers.