Issue CONCATENATE-SEQUENCE Writeup

Issue:        CONCATENATE-SEQUENCE

Forum:	      Editorial

References:   CONCATENATE (p249), COERCE (p51),

	      MAKE-SEQUENCE (p249), MAP (p249), MERGE (p260),

	      Issue SUBTYPEP-TOO-VAGUE

Category:     CLARIFICATION/CHANGE

Edit history: 01-Mar-91, Version 1 by Pitman 

	        (only about (CONCATENATE 'SEQUENCE ...))

	      15-Mar-91, Version 2 by Pitman 

	        (generalize per JonL, Moon, Barmar, MacLachlan)

	      17-Mar-91, Version 3 by Pitman 

	        (clarify for MacLachlan; also, include MAKE-SEQUENCE)

	      31-May-91, Version 4 by Pitman (amendments per X3J13)

Status:	      X3J13 passed v3 with amendments on 10-1 vote, Mar 91.

	      v4 reflects those amendments.


Problem Description:


  CLtL (p249) says that the RESULT-TYPE argument to CONCATENATE

   ``must be a subtype of SEQUENCE, as for the function COERCE''


  CLtL (p51) says:

   ``Any sequence type may be converted to any other sequence

     type, provided the new sequence can contain all actual

     elements of the old sequence ... If the sequence is already

     the specified type, it may be returned without copying it; 

     in this, (COERCE sequence type) differs from 

     (CONCATENATE type sequence), for the latter is required to

     copy the argument seqeunce.  In particular, if one specifies

     SEQUENCE, then the argument may simply be returned if it 

     already is a sequence.


  The passage about CONCATENATE suggests that sequence subtypes 

  valid to COERCE are valid to CONCATENATE.  But the type SEQUENCE

  is a subtype of SEQUENCE that is clearly permissible to COERCE.


  COERCE, MAKE-SEQUENCE, MAP, and MERGE are also impacted similarly.


Terminology:


  Draft 8.81 of the specification defines the following term:


    recognizable subtype n. (of a <type>)

     a <subtype> of the <type> which can be reliably detected 

     to be such by the <implementation>.


  The intent is that SUBTYPEP will be described as a function which 

  returns "T, T" when the first type argument is a "recognizable subtype"

  of the second.


Proposal (CONCATENATE-SEQUENCE:X3J13-MAR-91):


  1. Specify that CONCATENATE, MAKE-SEQUENCE, MAP, and MERGE are

     defined only when the target type argument is either a 

     recognizable subtype of LIST or a recognizable subtype of

     VECTOR.  [MAP is also permitted to special case NIL as a

     target type in a manner consisting with existing practice.]

     Otherwise, an error is signaled.


  2. Specify that if COERCE receives a target type argument which is 

     a recognizable subtype of SEQUENCE, but which is neither a 

     recognizable subtype of LIST nor a recognizable subtype of

     VECTOR, then the argument to be coerced must already be 

     of that type (in which case, COERCE behaves like IDENTITY for that

     argument).  Otherwise, an error is signaled.


  3. a. Specify that if COERCE, CONCATENATE, MAKE-SEQUENCE, MAP,

	or MERGE receives a target type argument which is any subtype

	of LIST, then the result is of type LIST.


     b. Specify that if COERCE receives a target type argument that

        is a subtype of array, and the object is already of that type,

	COERCE returns that object as its result.


     c. For COERCE in situations not covered by 3b, 

	CONCATENATE, MAKE-SEQUENCE, MAP and MERGE 

	when the target type argument is a subtype of ARRAY:


	 * If the implementation can determine the element type

 	   specified for the target type, the element type of the

	   resulting array is the upgraded array element type of 

	   the specified element type.


	 * Else if the implementation can determine that the element

	   type is unspecified, (or ``*'') the element type of the

	   resulting array defaults as for MAKE-ARRAY (to T).


	 * Else an error is signaled.


Rationale:


  This gives users a sense of what they can expect at minimum,

  and also gives implementors a sense for how they can go about 

  making extensions without violating user expectations.


  Note that although that specific terminology is not used, the

  specific constraints on recognizable subtypes are effectively 

  spelled out in issue SUBTYPEP-TOO-VAGUE.


Test Case:


 #1: (CONCATENATE 'SEQUENCE '(A B C) "DEF")


 #2: (COERCE '#1=#(1 0 1) '(OR NULL (EQL (1 0 1))))


 #3: (FLET ((SAME-TYPE-P (X Y)

	      (VALUES (AND (SUBTYPEP X Y) (SUBTYPEP Y X)))))

       (SAME-TYPE-P 

	 (ARRAY-ELEMENT-TYPE (MAKE-SEQUENCE '(ARRAY (UNSIGNED-BYTE 5)) 3))

	 (UPGRADED-ARRAY-ELEMENT-TYPE '(UNSIGNED-BYTE 5))))

     => T  ;or signals an error, if (UNSIGNED-BYTE 5) is not upgradable.


Current Practice:


 Symbolics Genera seems to approximately implement this proposal, 

 although it isn't quite right on the LIST side (e.g., it fails on test

 case #2).


Cost to Implementors:


  Small.


Cost to Users:


  None.  This was already not portable.


Cost of Non-Adoption:


  The language is left ambiguous.


Benefits:


  A tighter specification--better portability.


Aesthetics:


  Negligible.


Discussion:


 Pitman supports this.


 An earlier version of this proposal worried specifically about the case

 of function CONCATENATE and specifically about the argument named SEQUENCE

 but it was shown that the problem was bigger along both axes, so v2 starts

 over trying to do things a different way.