equiv.ss: Extensible Recursive Equivalence

_equiv.ss: Extensible Recursive Equivalence_

Written by: Carl Eastlund (cce at ccs dot neu dot edu)
Keywords: _equivalence_ _equality_ _comparison_ _predicate_

This software is distributed under a BSD-style license (see license.txt).

================================================================================

_Equivalence Algorithm_

This module provides a method for generating equivalence relations.  These
relations are based on an equal?-like algorithm, but may be extended to new
datatypes and can compare cyclic structures without infinite recursion.

The equivalence algorithm is parameterized over a set of equivalence rules.
Each rule defines the equivalence relation on a specific set of values.  For a
given set of rules, the equivalence algorithm proceeds in four steps.

(1) Values that are eq? are equivalent.

(2) Values previously visited by the same comparison are equivalent.

(3) Values are compared with the most recently added applicable rule.

(4) If there is no applicable rule, values are compared structurally using the
current inspector.  Opaque values are inequivalent.

Steps 3 and 4 may result in recursive comparison of the values' substructure.
In this case, recursive calls share the same equivalence rules and set of
previously-visited value pairs.

--------------------------------------------------------------------------------

This module provides the following values:

> equiv-rules/c : FlatContract

Recognizes a set of equivalence rules.

> (equiv-rules? v) : Boolean
  v : Any

Reports whether v is a set of equivalence rules.

> default-equiv-rules : EquivRules

The default set of equivalence rules.  Defines equivalence on: null, booleans,
symbols, characters, numbers, strings, byte strings, pairs, boxes, vectors, and
hash tables.

> (add-equiv-rule type? type=? rules) : EquivRules
  type? : (Any -> Boolean) such that (type? v) iff v : T
  type=? : (Any Any -> Boolean) T T -> Boolean
  rules : EquivRules

Adds a new equivalence rule to a set.  The predicate type? determines the values
for which the new rule applies.  The relation type=? defines equivalence over
the applicable values.  The type=? procedure's first argument is the equivalence
relation used for recursive comparisons.

Example:
(define-struct triple (a b c))
(define (triple=? recursive=? t1 t2)
  (and (recursive=? (triple-a t1) (triple-a t2))
       (recursive=? (triple-b t1) (triple-b t2))
       (recursive=? (triple-c t1) (triple-c t2))))
(define new-equiv-spec
  (add-equiv-rule triple? triple=? default-equiv-spec))

> (add-equiv-rule/leaf type? type=? rules) : EquivRules
  type? : (Any -> Boolean) such that (type? v) iff v : T
  type=? : T T -> Boolean
  rules : EquivRules

Adds a new equivalence rule to a set in the special case that no recursive
comparisons are required.  Works just like add-equiv-rule, but type=? has no
extra argument for a recursive equivalence procedure.

Example:
(define-struct point (x y))
(define (point=? p1 p2)
  (and (= (point-x p1) (point-x p2))
       (= (point-x p1) (point-x p2))))
(define new-equiv-spec
  (add-equiv-rule/leaf point? point=? default-equiv-spec))

> (add-binary-equiv-rule pred? pair=? rules) : EquivRules
  pred? : (Any Any -> Boolean) such that (pred? v1 v2) iff v1 : A and v2 : B
  pair=? : (Any Any -> Boolean) A B -> Boolean
  rules : EquivRules

Adds a new binary equivalence rule to a set.  This allows rules that treat one
value differently from another.  Symmetry of equivalence is preserved because
the rule is applied to pairs of values in both orders.

The predicate pred? determins pairs of values for which the rule applies.  The
predicate pair=? defines equivalence over pairs, given a predicate for recursive
comparisons.  For values a,b to be compared with recursive predicate =?, if
(pred? a b) holds, then (pair=? =? a b) determines equivalence.  Otherwise, if
(pred? b a) holds, then (pair=? =? b a) determines equivalence.

Example (equivalence that unboxes values before comparison):
(define (one-box? one two) (box? one))
(define (unbox-one=? equiv one two) (equiv (unbox one) two))
(define unboxing-equiv-spec
  (add-binary-equiv-rule one-box? unbox-one=? default-equiv-spec))
(define unbox=? (make-equiv unboxing-equiv-spec))
(unbox=? (box 1) (box (box 1)))

> (make-equiv rules) : Any Any -> Boolean
  rules : EquivRules

Produces an equivalence relation from a set of rules.  Operates according to the
Equivalence Algorithm, above.

> current-equiv-rules : (Parameter EquivRules)

This parameter contains a set of equivalence rules.

> (equiv? one two) : Boolean
  one,two : Any

Compares values according to current-equiv-rules.  Equivalent to:
((make-equiv (current-equiv-rules)) one two)

--------------------------------------------------------------------------------

REFERENCES:

_SRFI 85: Recursive Equivalence Predicates_ (DRAFT)
This module is closely related to SRFI 85, but is not currently intended to
represent either a complete or correct implementation of that SRFI.

--------------------------------------------------------------------------------

ACKNOWLEDGEMENTS:

Thanks to Will Clinger (author of SRFI 85) for his insights on combining
extensibility with comparison of cyclic structures.

Thanks to Sam Tobin-Hochstadt and Richard Cobbe for many helpful discussions on
this topic.