I'm curious as to why EQUAL on arrays is essentially EQ, but there are
the special cases for strings and bit-vectors where EQUAL must look at
the contents of the array.
Why were these special cases done? Did early versions of EQUAL only
check EQ? Why not look at the contents for other array types?
Ray
Raymond Toy <···········@stericsson.com> writes:
> I'm curious as to why EQUAL on arrays is essentially EQ, but there are
> the special cases for strings and bit-vectors where EQUAL must look at
> the contents of the array.
>
> Why were these special cases done? Did early versions of EQUAL only
> check EQ? Why not look at the contents for other array types?
Well, I don't have the greatest historical knowledge, but I'll give this
a shot. Perhaps we can get additional comments from others more expert
in this area.
IIRC, strings were introduced into lisp well before general arrays and
vectors. So the extension of EQUAL to work with strings would have
preceded the availability of any general arrays. So there was a drive
for backwards compatibility to have EQUAL work with strings, but no such
need to avoid breaking existing programs with respect to more general
arrays.
I would guess that a desire to limit the complexity of EQUAL motivated
the standards committee to not expand the definition. Common Lisp then
also introduced EQUALP as a new equality predicate that would look into
the contents of vectors.
As for bit vectors, I'm not sure about their history.
--
Thomas A. Russ, USC/Information Sciences Institute
On 26 Jun 2009 10:12:23 -0700, ···@sevak.isi.edu (Thomas A. Russ) said:
> ...
> IIRC, strings were introduced into lisp well before general arrays and
> vectors. So the extension of EQUAL to work with strings would have
> preceded the availability of any general arrays. So there was a drive
> for backwards compatibility to have EQUAL work with strings, but no such
> need to avoid breaking existing programs with respect to more general
> arrays.
LISP 1.5 had arrays (Section 4.4 The Array Feature, p. 27), but the
name of an array was turned into a _function_, an accessor for the
elements of the array, so (apparently) arrays were not yet
first-class objects at the time.
---Vassil.
--
Vassil Nikolov <········@pobox.com>
(1) M(Gauss);
(2) M(a) if M(b) and declared(b, M(a)),
where M(x) := "x is a mathematician".
In article <···············@luna.vassil.nikolov.name>,
Vassil Nikolov <········@pobox.com> wrote:
> On 26 Jun 2009 10:12:23 -0700, ···@sevak.isi.edu (Thomas A. Russ) said:
> > ...
> > IIRC, strings were introduced into lisp well before general arrays and
> > vectors. So the extension of EQUAL to work with strings would have
> > preceded the availability of any general arrays. So there was a drive
> > for backwards compatibility to have EQUAL work with strings, but no such
> > need to avoid breaking existing programs with respect to more general
> > arrays.
>
> LISP 1.5 had arrays (Section 4.4 The Array Feature, p. 27), but the
> name of an array was turned into a _function_, an accessor for the
> elements of the array, so (apparently) arrays were not yet
> first-class objects at the time.
And this style was retained in Maclisp.
Strings were added to Maclisp at one point, using its "hunk" and
extended data types features. Hunks were a generalization of conses,
with power of 2 sizes up to 512, and one of the slots could also hold a
property list. The extended data type feature allowed you to treat
hunks with certain properties specially (I vaguely recall that's how it
worked -- the Pitmanual mentions but doesn't actually describe this
feature).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
···@sevak.isi.edu (Thomas A. Russ) writes:
> Raymond Toy <···········@stericsson.com> writes:
>
>> I'm curious as to why EQUAL on arrays is essentially EQ, but there are
>> the special cases for strings and bit-vectors where EQUAL must look at
>> the contents of the array.
>>
>> Why were these special cases done? Did early versions of EQUAL only
>> check EQ? Why not look at the contents for other array types?
>
> Well, I don't have the greatest historical knowledge, but I'll give this
> a shot. Perhaps we can get additional comments from others more expert
> in this area.
>
> IIRC, strings were introduced into lisp well before general arrays and
> vectors. So the extension of EQUAL to work with strings would have
> preceded the availability of any general arrays. So there was a drive
> for backwards compatibility to have EQUAL work with strings, but no such
> need to avoid breaking existing programs with respect to more general
> arrays.
Indeed, in LISP 1.5, there was internally strings (used to name symbols).
And EQUAL applied on strings was O(n/6). (with n = (length string))
> I would guess that a desire to limit the complexity of EQUAL motivated
> the standards committee to not expand the definition. Common Lisp then
> also introduced EQUALP as a new equality predicate that would look into
> the contents of vectors.
>
> As for bit vectors, I'm not sure about their history.
An EQUAL on bit vector could be O(n/32)...
--
__Pascal Bourguignon__
Raymond Toy <···········@stericsson.com> writes:
> I'm curious as to why EQUAL on arrays is essentially EQ, but there are
> the special cases for strings and bit-vectors where EQUAL must look at
> the contents of the array.
>
> Why were these special cases done? Did early versions of EQUAL only
> check EQ? Why not look at the contents for other array types?
I'd bet it's because of historical reasons. Arrays would tend to be
big, and contain a lot of numbers. So already you don't want equal on
the slots, since (not (equal 1 1.0)). And when you compare two
matrices, it may not be meaningful to compare them not cell by cell.
And if it was, it would be very slow, so it's better to let the
application implement its own comparison operator.
Now, of course, strings are different matter. Since we already have a
string= and string-equal, why not hook them in equal?
In any case, nowadays it looks strange, yes.
--
__Pascal Bourguignon__
On Fri, 26 Jun 2009 11:48:43 -0400, Raymond Toy <···········@stericsson.com> said:
> I'm curious as to why EQUAL on arrays is essentially EQ, but there are
> the special cases for strings and bit-vectors where EQUAL must look at
> the contents of the array.
> Why were these special cases done? Did early versions of EQUAL only
> check EQ? Why not look at the contents for other array types?
A concrete answer, of course, can be given by those who know (who
were there), and, also of course, Kent Pitman's excellent paper on
equalities [*] is required reading in this context.
[*] search?q=Kent+%22EQUAL.html%22
Just to add a thought ot two, with the exception of EQ and EQL, and
if we imagine we can discount the baggage of historical reasons, the
specification of any general-purpose equality test is based on one
or another set of heuristics, chosen to maximize, say in fancy
words, the utility-to-cost ratio for the average case (where cost
takes into account both implementation effort and performance
overhead). The utility depends, of course, on how often the (more
or less) arbitrary choice of the notion of equality matches the
user's requirement.
Sometimes we have a pretty good idea what most people will need most
of the time, e.g. with EQUAL for conses. At other times, we may be
reluctant to speculate: for example, would we be willing to provide
a general-purpose equality test which uses `=' element-wise when
comparing numeric matrices (which would be a direct but naive
transcription of the mathematical definition), given that (= 1 1.0)
=> T? It's not just that this is what some applications want and
others don't, but that _both_ of these categories of applications
are large enough.
---Vassil.
--
Vassil Nikolov <········@pobox.com>
(1) M(Gauss);
(2) M(a) if M(b) and declared(b, M(a)),
where M(x) := "x is a mathematician".
On Fri, 26 Jun 2009 23:10:58 -0400, Vassil Nikolov <········@pobox.com> said:
> ...
> Sometimes we have a pretty good idea what most people will need most
> of the time, e.g. with EQUAL for conses. At other times, we may be
> reluctant to speculate: for example, would we be willing to provide
> a general-purpose equality test which uses `=' element-wise when
> comparing numeric matrices (which would be a direct but naive
> transcription of the mathematical definition), given that (= 1 1.0)
> => T? It's not just that this is what some applications want and
> others don't, but that _both_ of these categories of applications
> are large enough.
One thing I missed saying is that EQ, EQL, EQUAL, and EQUALP have a
privileged position among all general-purpose equality predicates in
that only they are allowed for the hash tables built into the
language. Therefore when defining EQUAL and EQUALP (given that EQ
and EQL are clear-cut cases), one particularly important
consideration is what kind of equivalence classes would the most
typical user need _when_ fast lookup will be desired. I wonder if
someone has analyzed the experience of these past few decades to try
to determine how often and how well the chosen definitions have
matched what people have actually been doing.
---Vassl.
--
Vassil Nikolov <········@pobox.com>
(1) M(Gauss);
(2) M(a) if M(b) and declared(b, M(a)),
where M(x) := "x is a mathematician".
On Jun 26, 9:26 pm, Vassil Nikolov <········@pobox.com> wrote:
> I wonder if
> someone has analyzed the experience of these past few decades to try
> to determine how often and how well the chosen definitions have
> matched what people have actually been doing.
Personally, I recall using EQUAL and EQUAL hashing relatively rarely.
I think most uses have involved hashing strings, but I recall one
occasion where I used the full power of EQUAL hashing to key on
arbitrary s-expressions; it was very very handy in that situation.
I don't think I've ever used EQUALP for anything, hashing or
otherwise.
-- Scott