Description of "equal?" #329

chaw commented 2026年04月24日 23:22:42 +02:00

Should the description of the equal? predicate include a reference and/or more details on the unfolding of arguments into regular trees?

Should the description of the equal? predicate include a reference and/or more details on the unfolding of arguments into regular trees?

phm commented 2026年04月26日 14:52:57 +02:00

The R6RS uses the following wording:

The equal? predicate treats pairs and vectors as nodes with outgoing edges

That wording is more precise and I would support adding it to the description. I would also support a citation to Adam's and Dybvig's paper for an algorithm.

The R6RS uses the following wording: > The equal? predicate treats pairs and vectors as nodes with outgoing edges That wording is more precise and I would support adding it to the description. I would also support a citation to [Adam's and Dybvig's paper](https://michaeldadams.org/papers/efficient_equality/) for an algorithm.

readevalprintloop commented 2026年04月26日 18:41:50 +02:00

@phm wrote in #329 (comment):

The R6RS uses the following wording:

The equal? predicate treats pairs and vectors as nodes with outgoing edges

That wording is more precise and I would support adding it to the description. I would also support a citation to Adam's and Dybvig's paper for an algorithm.

I think the confusion stems from the wording "ordered tree" and "regular tree", which appears to be a term from automata theory. However, I couldn't find a good explanation on internet.

A tree is called ordered if there is an order among the successors of each of its nodes. The above definition of tree naturally suggests an order among the successors, which can be used to make the tree ranked.

https://en.wikipedia.org/wiki/Tree_(graph_theory)

Can someone find out the source reference of the definitions of these terms?

On the other hand, the rationale behind the definition is quite intuitive. It basically says the implementation of equal? should use some memorization technique to prevent recursive calling equal? being stuck on infinite loop. Maybe there's other way to formalize this intuition in spec.

@phm wrote in https://codeberg.org/scheme/r7rs/issues/329#issuecomment-13785584: > The R6RS uses the following wording: > > > The equal? predicate treats pairs and vectors as nodes with outgoing edges > > That wording is more precise and I would support adding it to the description. I would also support a citation to [Adam's and Dybvig's paper](https://michaeldadams.org/papers/efficient_equality/) for an algorithm. I think the confusion stems from the wording "ordered tree" and "regular tree", which appears to be a term from automata theory. However, I couldn't find a good explanation on internet. > A tree is called ordered if there is an order among the successors of each of its nodes. The above definition of tree naturally suggests an order among the successors, which can be used to make the tree ranked. https://en.wikipedia.org/wiki/Tree_(graph_theory) Can someone find out the source reference of the definitions of these terms? On the other hand, the rationale behind the definition is quite intuitive. It basically says the implementation of `equal?` should use some memorization technique to prevent recursive calling `equal?` being stuck on infinite loop. Maybe there's other way to formalize this intuition in spec.

phm commented 2026年04月26日 23:45:17 +02:00

@readevalprintloop wrote in #329 (comment):

I think the confusion stems from the wording "ordered tree" and "regular tree", which appears to be a term from automata theory. However, I couldn't find a good explanation on internet.

The trees are certainly not "regular" in the sense of that Wikipedia article. The R7RS-Small just replaces it with "tree."

According to Bruno Courcelle (1983), "Fundamental Properties of Infinite Trees", a tree is regular if the set of its subtrees is finite. That makes sense, because a circular data structure will repeat and hence have a finite number of subtrees, so this probably the definition in mind.

@readevalprintloop wrote in https://codeberg.org/scheme/r7rs/issues/329#issuecomment-13792976: > I think the confusion stems from the wording "ordered tree" and "regular tree", which appears to be a term from automata theory. However, I couldn't find a good explanation on internet. The trees are certainly not "regular" in the sense of that Wikipedia article. The R7RS-Small just replaces it with "tree." According to [Bruno Courcelle (1983), "Fundamental Properties of Infinite Trees"](https://www.labri.fr/perso/courcell/Textes1/FundPropInfTrees.pdf), a tree is regular if the set of its subtrees is finite. That makes sense, because a circular data structure will repeat and hence have a finite number of subtrees, so this probably the definition in mind.

phm commented 2026年07月06日 16:37:22 +02:00

I have reverted the text to the R7RS-Small's "into (possibly infinite) trees" instead of "regular trees." I think that referring to them as "regular" is likely to cause confusion than to help.

I have reverted the text to the R7RS-Small's "into (possibly infinite) trees" instead of "regular trees." I think that referring to them as "regular" is likely to cause confusion than to help.

mnw commented 2026年07月06日 18:02:44 +02:00

The precise definition is that equal? is the greatest equivalence relation such that the following holds: (equal? X Y) is true if and only if

• X and Y are non-pairs or non-vectors and are considered equal (which is defined earlier),
• X and Y are both pairs whose cars and cdrs are equal?, respectively,
• X and Y are both vectors of the same length whose corresponding elements are equal?.

The precise definition is that `equal?` is the greatest equivalence relation such that the following holds: `(equal? X Y)` is true if and only if - `X` and `Y` are non-pairs or non-vectors and are considered equal (which is defined earlier), - `X` and `Y` are both pairs whose cars and cdrs are `equal?`, respectively, - `X` and `Y` are both vectors of the same length whose corresponding elements are `equal?`.