[no subject]

[Kent M. Pitman <KMP at MIT-MC>]

Here's more data on an oddity originally introduced by ROD@SAIL in mail 
to BUG-LISP. He pointed out that in Maclisp,

    (setq x '(a b) y '(a b))	=> (a b)
    (eq x y)			=> NIL
    (subst 'foo x (list y y y))	=> (FOO FOO FOO) 

As he points out, the definition of SUBST in the Maclisp manual is:

    (subst x y z) substitutes x for all occurrences of y in z, and returns
	the modified copy of z.  The original z is  unchanged, as subst
	recursively copies all of z replacing elements eq to y as it goes.
	If x and y are nil, z is just copied, which is a convenient way to
	copy arbitrary list structure. ... subst could have been defined by:

        (defun subst (x y z)
            (cond ((eq z y) x)    ;if item eq to y, replace.
                  ((atom z) z)    ;if no substructure, return arg.
                  ((cons (subst x y (car z))  ;otherwise recurse.
                         (subst x y (cdr z))))))

The problem is in fact much more far-reaching than he described, and there
seems to be little agreement, so I thought I would present the rest of the
story for comment... Here's what a sampling of the other dialects turns up...

	Test case:	(setq new '(new list))
			(setq old '(a b))
			(setq test '((a b) a b))
			(subst new old test)			

In ITS Maclisp, back at least to Maclisp 1293, 

		(subst new old test)	=> ((NEW LIST) NEW LIST)
		(eq (car *) new)	=> T

	This contradicts documentation in the manual. 

In Multics Maclisp, 

		(subst new old test)	=> ((a b) a b) ; all copied structure

In LispMachine Lisp,

		(subst new old test)	=> ((NEW LIST) A B)
		(eq (car *) new)	=> T

	This contradicts documentation in the manual. Their documentation
	is essentially equivalent to that of Maclisp.

Franz Lisp has no SUBST function listed in their manual.

In Interlisp, according to their documentation (I have no way to test this),

		(subst new old test)	=> ((NEW LIST) A B)
		(eq (car *) new)	=> NIL	; excuse the Maclisp notation

For the curious, Interlisp documents its subst as follows...

    subst[new;old;expr] Value is the result of substituing the S-expression 
      new for all occurrences of the S-expression old in the S-expression 
      expr. Substitution occurs whenever old is EQUAL to CAR of some sub-
      expression, or when old is both atomic and not NIL and EQ to CDR of 
      some subexpression of expr. For example:
    
	subst[A;B;(C B (X . B))] = (C A (X . A))
    
	subst[A;(B C);((B C) D B C)] = (A D B C),
	  not (A D . A).
    
      The value of SUBST is a copy of expr with the appropriate changes. 
      Furthermore, if new is a list, it is copied at each substitution.