Visitors to Lisp from ML-land often ask: “Why does eq work on immutable objects? ‘The same object’ isn't meaningful without mutation!”

The reasoning goes like this:

  1. Lisp supports mutable data, because state is a useful tool (even if we don't like to use it too much). So identity is meaningful.
  2. Since values are usually represented as tagged pointers, identity comparison can be implemented as simple pointer comparison.
  3. This happens to work for immutable objects as well.
  4. The Lisp Way is to be permissive, so we won't disable eq in situations where it's not thought to be interesting. (Besides, it would take additional work to disable it.)

It turns out to be useful. For one thing, eq is very fast. We can arrange to make it equivalent to another predicate, without losing its speed, by interning the values: only keeping one of each set of equivalent values (as determined by the other predicate). This is how symbols work.

eq is also the only general way to detect shared structure. This is essential for things like *print-circle*, which makes printing circular data safe.

eq is total: it works on everything. This makes it handy for implementing general-purpose library code. In particular, it's a good default method for equality predicates. It's also handy when you want to distinguish one value from all others, of any type.

Finally, object identity is a basic fact of implementations. It shouldn't be hidden without a good reason. Allowing programs to see it helps you learn to “feel the bits between your toes”. In addition to being fun, that's important to writing efficient code.

Yes, eq exposes a detail of representation which usually doesn't matter. But it's a harmless exposure. No program has a bug because it is possible to compare its values for identity; neither do any interesting properties of programs cease to be true. So we get a variety of uses for free.

That's why Lisp has eq.

No comments:

Post a Comment

It's OK to comment on old posts.