Proposal #9: Fast testing in PROGV

[Dan Hoey <hoey@nrl-aic.ARPA>]

    Date: Fri, 1 Aug 86 08:36 EDT
    From: David C. Plummer <DCP@scrc-QUABBIN.arpa>

        From: Dan Hoey <hoey@nrl-aic>

	    From: Jeff Barnett <jbarnett@nrtc>

	    ...looking for duplicate names in the variable-list argument
	    of a PROGV ... can be done in N*log N time.
   
        You can put a mark on the property lists of the variables
        for a linear algorithm.
    
    Nit: no you can't.

Antinit: Sure you can.

    Putting a mark on a property list takes linear time
    (length of the property list to see if it is already there)

I had in mind putting a GENSYMmed on the front of the property list and
only testing for it there.  (Nit me no nits about multiple processes
until they're in CLtL.)

    and you have to do this for N variables.  So you are back to
    N^2 again,

Nit: That's N E(L), for L the length of a property list.

    and you are likely consing,

My PROGV checker would keep all its conses for use the next time.

    and misusing property lists,

I would spend the extra CONS to keep the plists legal.

    and...

if there is further discussion, we can do it between ourselves.  Anyone
out there who wants to write a PROGV checker should check with David or
me for the latest in variable uniqueness theory.

Dan