Re: [spr2273] porting

[dm@Franz.COM (David Margolies)]

>  Return-Path: <ralph@kahuna.math.hawaii.edu>
>  Date: Thu, 22 Nov 90 13:43:31 HST
>  To: allegro-cl@ucbvax.Berkeley.EDU
>  Subject: porting
>  
>          Here are two differences between lucid and allegro that I
>  noticed.
>  
>  1.  In allegro (and some other lisps I tried) (remove foo list) 
>  always returns a copy of list, even if foo is
>  not in  list. This is not true for lucid. So
>  
>  (let ((list '(a b c)))
>       (eq list (remove 'd list)))
>  
>  returns nil with allegro but t with lucid. The second edition of
>  Steele makes it clear that an implementation is not required to return
>  a copy if nothing is removed, so neither one is wrong. In my opinion
>  it would have been a better choice to always require that remove 
>  return a copy of list. [...]
>  
>  2. The effect of
>  
>  (remove-duplicates list :from-end t :test #'(lambda (x y) (mytest x y)))
>  
>  in allegro is the same as
>  
>  (remove-duplicates list :from-end t :test #'(lambda (y x) (mytest x y)))
>  
>  in lucid (and vise versa).  This is pretty obscure since usually mytest
>  will be some equality-like predicate so (mytest x y) = (mytest y x).
>  However there are some uses of this when "mytest" is not symmetric,
>  eg. you can find the minimal sets from a list of sets by apply
>  remove-duplicates twice, once with :from-end t, using a test based
>  on subsetp. "Common Lisp, the Reference" states clearly that allegro 
>  is right but Steele is less definitive.
>  
>  		Ralph Freese
>  		Dept. of Math.
>  		Univ. of Hawaii
>  		Honolulu, HI.
>  		ralph@kahuna.math.hawaii.edu

Here are a few comments about the issues raised.

1.  [In response to 1 above.]  I would like to make clear that
    in cases like this where the standard permits implementors to
    either copy a sequence or not, portable code must assume the 
    most conservative possibility (in this case, that the returned
    sequence *may* be EQ to the argument sequence).  It is in 
    the control of the ANSI X3J13 committee to decide whether the 
    standard should be tightened or not.

2.  [In response to 2 above] Ralph Freese is quite right that `Common
    Lisp: the Reference' says explicitly that sequence elements are 
    passed to the test function which is the value of the :TEST argument 
    in the order in which the elements appear in the sequence 
    *regardless* of the value of the :FROM-END argument.  E.g., in 
    the description of the :TEST keyword argument on page 827, it says:

      If the arguments passed to the predicate [which is the value of
      :TEST] are from the same sequence (as with DELETE-DUPLICATES),
      the elements are passed in the same order as they appear in the
      sequence.  This is true even if the :FROM-END keyword argument
      is non-NIL.

    Ralph further says that Steele is less definitive.  Below I give
    the sentences in CLtL-1 on which we base our position and also
    another sentence which supports the Lucid position.  But the
    important point here is that it is *not* appropriate to leave
    this issue up to the implementors.  I am submitting a cleanup
    issue to X3J13 so that they can decide which behavior is correct.

    Look at page 247 of CLtL-1 and consider the second to last paragraph
    before section 14.1.  It says in part:

      You may depend on the order in which the arguments are given
      to TESTFNC [which is the value of the :TEST or :TEST-NOT
      argument]; this permits the use of a non-commutative test
      functions in a predictable manner. [...] If a sequence function
      gives two elements from the same sequence argument to TESTFNC,
      they are given in the same order in which they appear in
      the sequence.

    The statement in `Common Lisp: the Reference' quoted above is
    based on this passage from CLtL-1.  On the other hand, the middle
    paragraph on page 246 of CLtL-1 says in part:

      For some operations it can be useful to specify the direction
      in which the sequence is conceptually processed.  In this case, 
      the basic operation normally processes the qequence in the forward 
      direction, and processing in the reverse direction is indicated
      by a non-NIL value for the keyword argument :FROM-END.

    Now, I think that the text supports the Franz interpretation more
    than the Lucid one (e.g. the first quote from CLtL-1 says `appear
    in the sequence' rather than `are processed') but a ruling from
    X3J13 will settle the matter.

    Here is an example that illustrates the issue:

    (defun testfnc (x y) (< x y))

    (setq lis (list 1 2))

    (remove-duplicates lis :test #'testfnc) -> (2) in both Allegro CL
                                                   and Lucid Common Lisp.

    (remove-duplicates lis :test #'testfnc :from-end t)
                      -> (1) in Allegro CL
                      -> (1 2) in Lucid Common Lisp 

    [Note that if the Allegro interpretation of the effect of
    :FROM-END is correct, returning (2) in the first case and (1)
    in the second is correct since the description of REMOVE-
    DUPLICATES on page 255 of CLtL-1 says `if any two match,
    then the one occuring earlier is discarded (but if the
    :FROM-END argument is true, then the one later in the
    sequence is discarded).']

    CLtL-2 has no changes or comments on this particular issue (i.e.
    all the text quoted appears unchanged in CLtL-2, see e.g. pages
    390, 391, 401, and 402).

This matter has been given the Franz internal tracking number
[spr2273].  We would appreciate it if people who wish to comment
on the issue use that tracking number in their message.

David Margolies
Franz Inc.