[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Proposal #9 Status: Variable Name Conflicts
Date: Wed, 30 Jul 86 13:55:54 PDT
From: Jeff Barnett <jbarnett@nrtc>
It was assumed in this and a previous message that looking for duplicate
names in the variable-list argument of a PROGV is an N**2 operation. Not
true. In the first place, if the list is short N**2 is small. In the
second place it can be done in N*log N time. To wit: (1) copy the list--
order n, (2) sort the list--order N*log N, and (3) search the ordered
list for adjacent duplicates--order N.
Any implementation that did this would probably discourage users from
using PROGV because it would be costly (inefficient) to use. copying
the list conses and takes time. Sorting can potentially cons, may be
NlogN, but is quite expensive in the smaller cases. PROGV has so real
and valid uses; it should be relatively inexpensive to use.
I think PROGV should be removed from the list of forms that check for
variable name conflicts. I think variable name conflicts should be
detected by the compiler; not the runtime system. I think the semantics
of PROGV are that the LAST symbol/value pair takes presedence in case
there is more than one pair for a given symbol.