\documentclass{article}

\author{Christophe Rhodes\footnote{Goldsmiths College, New Cross Road, London SE14 6NW, \texttt{c.rhodes@gold.ac.uk}}}
\title{Revisiting \texttt{CONCATENATE-SEQUENCE}}

\newcommand{\name}[1]{\texttt{#1}}
\newcommand{\cl}[1]{\name{\href{http://www.xach.com/clhs?q=#1}{#1}}}
\def\recsub{recognizable subtype}

\usepackage{url}
\usepackage{natbib}
\usepackage{geometry}
\usepackage{hyperref}

\begin{document}

\maketitle

\begin{abstract}
  While doing work to support user-extensible sequences
  \citep{UserExtSequences}, it was discovered that the ANSI CL
  standard forbids integration of certain functions with not only
  user-extensible sequences but also implementation extensions of
  \cl{sequence}.  Irrespective of the future of user-extensible
  sequences, we argue that the restriction on implementations imposed
  by the wording adopted is too stringent, and propose an alternative.
\end{abstract}

\section{Introduction}

In the X3J13 Issue \texttt{CONCATENATE-SEQUENCE}
\citep{ConcatenateSequence}, the ANSI CL committee worried about
various cases of sequence type specifiers passed to the five functions
\cl{make-sequence}, \cl{map}, \cl{merge}, \cl{concatenate} and
\cl{coerce}.  The essential problem which the
\texttt{CONCATENATE-SEQUENCE} Issue addresses is that a type specifier
can specify a \recsub{} of \cl{sequence} without unambiguously
specifying a concrete sequence type, needed because, except for a
special case in \cl{coerce}, these functions must create an object of
the specified type.

For instance, the type \cl{sequence} itself is a \recsub{} of
\cl{sequence}; however, the desire was that the call
\verb+(make-sequence 'sequence 8)+ should be in error; other such
ambiguous types can be constructed, such as
\verb+(simple-array (*) *)+, \verb+(or bit-vector string)+, and
\verb+(and sequence (not (eql "foo")))+; although types involving
conjunction, disjunction and negation are not required to be
\recsub{}s of \cl{sequence}, most current implementations recognize
these examples as such.

However, the ANSI CL standard also specifies that an implementation
may offer subtypes of \cl{sequence} that are not \cl{list} and
\cl{vector}:
\begin{quote}
  The types [\textit{sic}] vector and the type list are disjoint subtypes of
  type sequence, but are not necessarily an exhaustive partition of
  sequence.
\end{quote}
\begin{flushright}
  \citet[{System Class \cl{sequence}}]{CLtS}
\end{flushright}

Historically, this does not appear to have been a popular field for
implementation extension; at the time of writing, the author knows of
no implementation purporting to conform to Common Lisp which documents
non-standard sequence types, though there exist undocumented hooks in
at least GNU \textsc{Clisp} \citep{clispseq} which were used in a
pre-CLOS implementation of generalized sequences \citep{cloccseq}.

In light of this standard definition of the \cl{sequence} class, and of
the development of user-extensible sequences, however, the wording for
the Exceptional Situations of \cl{make-sequence} overreaches the
intent of the clarification of the \texttt{CONCATENATE-SEQUENCE}
issue:
\begin{quote}
  An error of type type-error must be signaled if the result-type is
  neither a \recsub{} of list, nor a
  \recsub{} of vector.
\end{quote}
\begin{flushright}
  \citet[{Function \cl{make-sequence}}]{CLtS}
\end{flushright}
Similar requirements are placed on \cl{map}, \cl{merge},
\cl{concatenate} and \cl{coerce}.

This requirement does not permit an implementation to extend
\cl{make-sequence} to type designators for non-standard sequences,
which does not seem to have been the intent behind the
\texttt{CONCATENATE-SEQUENCE} issue.  We therefore propose the
clarification, presented in the style of an issue in the next section.

\section{Issue \texttt{CONCATENATE-SEQUENCE-AGAIN}}

\paragraph{Issue:} \texttt{CONCATENATE-SEQUENCE-AGAIN}.

\paragraph{References:} \cl{coerce}, \cl{concatenate},
\cl{make-sequence}, \cl{map}, \cl{merge}, \citet{ConcatenateSequence}.

\paragraph{Category:} Clarification / Change.

\paragraph{Problem Description:} The specification says that an error
must be signalled in cases when a type specifier passed to
\cl{make-sequence} is not a \recsub{} of either
\cl{list} or \cl{vector}.  This prevents integration of non-standard
sequence types, expressly permitted by the description of
\cl{sequence}, with the standardized sequence functions.

This also affects \cl{coerce}, \cl{concatenate}, \cl{map} and
\cl{merge}.

\paragraph{Proposal \texttt{(CONCATENATE-SEQUENCE-AGAIN:GENERALIZE)}:}
\begin{itemize}
\item Remove from \cl{make-sequence}, \cl{merge}, \cl{map} and
  \cl{concatenate} the requirement that ``An error of type type-error
  must be signaled if the result-type is neither a recognizable
  subtype of list, nor a recognizable subtype of vector.''

\item Specify that if a type specifier is a \recsub{} of
  \cl{sequence}, and is recognized by the implementation as specifying
  a concrete subtype of \cl{sequence}, then a sequence of the
  specified type is returned from \cl{coerce}, \cl{concatenate},
  \cl{make-sequence}, \cl{map} and \cl{merge}, subject to the
  constraints on the type specifier agreeing with the required length
  of the result sequence.
\end{itemize}

\paragraph{Rationale:} This allows implementors to make extensions of
\cl{sequence}, as seems to have been the original intent.

\paragraph{Test Case:} No portable test case.

\paragraph{Current Practice:} Effectively compatible with both the
standard as specified and this proposal, as no implementation extends
\cl{sequence} as of the time of writing.

\paragraph{Cost to Implementors:} None.

\paragraph{Cost to Users:} Minimal.  Users can no longer have the
guarantee that code of the form
\begin{verbatim}
(assert (typep (ignore-errors (make-sequence *x* 8)) 
               '(or list vector)))
\end{verbatim}
never causes the assertion to fail.

\paragraph{Cost of Non-Adoption:} The specification remains inconsistent.

\paragraph{Benefits:} A natural way of providing extensions for the
\cl{sequence} type.

\paragraph{Aesthetics:} Minimal.

\bibliographystyle{apalike}
\bibliography{standard,sequences}

\end{document}