3 ms·

Kent Pitman on Equal Rights -- and Wrongs -- in Lisp (1993)

28 points by gnosis 15y ago

krzysz00 15y ago
Ah! Now I am enlightened.
ScottBurson 15y ago
The problem with equality in Common Lisp is that the fundamental data structures don't come with enough semantics that one can tell, just by looking at one, what it is being used for. For instance, a list structure can represent a sequence, an unordered set, an s-expression (a tree of sequences), a binary tree of conses, an alist representing a map, etc. etc. Using higher-level data structures, each with a clear semantics, clarifies the meaning of both equality and copying. For example, my FSet functional collections library for CL has separate types for sets, sequences, maps, bags, and tuples, along with a generic function EQUAL? that has methods for all these different types. Thus one can construct nested types -- sets of sequences, maps whose domains are sets, etc. etc. -- and compare them by just calling EQUAL?. In bare CL one would pretty much have to write a separate equality function for each such type. A critical distinction, in order to make this work, is that between object types and value types. Objects have identity and state; value types do not. When used with user-defined types, FSet requires this distinction to be made explicit: you have to say whether your type is an object or a value, and you have to be consistent about it. This way, it's always clear when equality should be "shallow" or "deep": equality comparison of object types is always by identity ("shallow"), while comparison of value types is always by content ("deep").
- swannodette 15y ago
  This is one of Clojure's finer design choices, emphasis on values. Thus, = alway means deep equality, identical? for testing whether two values are actually the same object.
  - lurker19 15y ago
    You mean "whether two values are actually the same 'value'", right? (So, "(cons A (cons B C)) = (cons A (cons B C))" even though allocated separately as two distinct instances and not cleverly optimized to the same storage in memory) Otherwise, I do not understand your comment, whih is lauding Clojure's preference for values over objects.
    - swannodette 15y ago
      By "object" I mean same storage in memory. Clojure does optimize literal data and identical? test does come first when using =.
technomancy 15y ago
Any discussion of equality semantics would be incomplete without mentioning Baker's "Equal Rights for Functional Objects": http://home.pipeline.com/~hbaker1/ObjectIdentity.html http://home.pipeline.com/~hbaker1/ObjectIdentity.html tl;dr: meaningful equality predicates can only be defined on immutable values.

28 points by gnosis 15y ago

Ah! Now I am enlightened.

The problem with equality in Common Lisp is that the fundamental data structures don't come with enough semantics that one can tell, just by looking at one, what it is being used for. For instance, a list structure can represent a sequence, an unordered set, an s-expression (a tree of sequences), a binary tree of conses, an alist representing a map, etc. etc. Using higher-level data structures, each with a clear semantics, clarifies the meaning of both equality and copying. For example, my FSet functional collections library for CL has separate types for sets, sequences, maps, bags, and tuples, along with a generic function EQUAL? that has methods for all these different types. Thus one can construct nested types -- sets of sequences, maps whose domains are sets, etc. etc. -- and compare them by just calling EQUAL?. In bare CL one would pretty much have to write a separate equality function for each such type. A critical distinction, in order to make this work, is that between object types and value types. Objects have identity and state; value types do not. When used with user-defined types, FSet requires this distinction to be made explicit: you have to say whether your type is an object or a value, and you have to be consistent about it. This way, it's always clear when equality should be "shallow" or "deep": equality comparison of object types is always by identity ("shallow"), while comparison of value types is always by content ("deep").

swannodette 15y ago
This is one of Clojure's finer design choices, emphasis on values. Thus, = alway means deep equality, identical? for testing whether two values are actually the same object.
- lurker19 15y ago
  You mean "whether two values are actually the same 'value'", right? (So, "(cons A (cons B C)) = (cons A (cons B C))" even though allocated separately as two distinct instances and not cleverly optimized to the same storage in memory) Otherwise, I do not understand your comment, whih is lauding Clojure's preference for values over objects.
  - swannodette 15y ago
    By "object" I mean same storage in memory. Clojure does optimize literal data and identical? test does come first when using =.

technomancy 15y ago

Any discussion of equality semantics would be incomplete without mentioning Baker's "Equal Rights for Functional Objects": http://home.pipeline.com/~hbaker1/ObjectIdentity.html http://home.pipeline.com/~hbaker1/ObjectIdentity.html tl;dr: meaningful equality predicates can only be defined on immutable values.