Difference between revisions of "Representational Equality"

From Adobe Open Source Wiki
Jump to: navigation, search
 
(Body)
 
Line 10: Line 10:
  
 
==Body==
 
==Body==
 +
 +
Definitions -
 +
 +
identical: I(a, b) - same instance, &a == &b
 +
representationally equal: R(a, b) - representation is equal
 +
logically equal: L(a, b) - all corresponding parts are equal
 +
 +
locational less than: - std::less<T*>(&a, &b)
 +
representationally less than:
 +
 +
I ==> R ==> L
 +
 +
I - complexity: small, constant time (pointer comparison)
 +
R - complexity: average small constant time, worst case O(area)
 +
L - complexity: may be significant - time to find corresponding parts
 +
 +
identical: &a == &b
 +
representationally equal: R(a, b) ==>
 +
 +
Desired attributes for logical less
 +
  symmetric with other operators - esp. + and *
 +
 +
Examples of types where < and/or == is problematic:
 +
 +
float and double - reason is NaN
 +
complex - operator < not defined because of symmetry with operator*()
 +
  solution is provide representational_less
 +
priority_queue - operator == and operator < not defined because of complexity and resource consumption
  
 
==Proposal==
 
==Proposal==

Latest revision as of 16:23, 15 February 2007

[This page is being used to collaborate on a paper. You are welcome to read and comment on it, but consider it a work in progress, not a final product.]

Title: Representational Equality

Authors: Sean Parent, Alex Stepanov

Contents

Abstract

Introduction

Body

Definitions -

identical: I(a, b) - same instance, &a == &b representationally equal: R(a, b) - representation is equal logically equal: L(a, b) - all corresponding parts are equal

locational less than: - std::less<T*>(&a, &b) representationally less than:

I ==> R ==> L

I - complexity: small, constant time (pointer comparison) R - complexity: average small constant time, worst case O(area) L - complexity: may be significant - time to find corresponding parts

identical: &a == &b representationally equal: R(a, b) ==>

Desired attributes for logical less

  symmetric with other operators - esp. + and *

Examples of types where < and/or == is problematic:

float and double - reason is NaN complex - operator < not defined because of symmetry with operator*()

  solution is provide representational_less

priority_queue - operator == and operator < not defined because of complexity and resource consumption

Proposal

Related Work

Acknowledgments