_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.