\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[T1]{fontenc}
\usepackage{ae,aecompl}
\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 (X3.226-1994) 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
  \cl{type-error}] must be\footnote{\cl{concatenate} and \cl{merge}
    have ``is'' for ``must be'', but this makes no difference in
    standardized behaviour.} signaled if the result-type is neither a
  recognizable subtype of \cl{list}, nor a recognizable subtype of
  \cl{vector}.''

\item Specify that if a type specifier is not a \recsub{} of
  \cl{sequence}, or is a \recsub{} of \texttt{(or list vector)} but
  not of either \cl{list} or \cl{vector}, then an error [of type
  \cl{type-error}] must be signaled.

\item Specify that if a type specifier is a \recsub{} of
  \cl{sequence}, but not a \recsub{} of any of the types \texttt{(or
    list vector)}, \cl{list} or \cl{vector}, then the consequences are
  unspecified.
\end{itemize}
The square brackets above reflect the slightly different requirements
on the functions in their error signalling, as defined in
\citet[{Section 1.4.2}]{CLtS}; the intent of this proposal is to
preserve as much as possible the original requirements on these five
functions while allowing for expansion of the set of acceptable
sequence type specifiers.

\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.  In implementations
extending the \cl{sequence} class, 
\begin{verbatim}
(make-sequence '<sequence-class> 8)
\end{verbatim}
need not signal an error under this proposal.

\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}