%%%% -*- Mode: LaTeX -*-

%%%% extra-num-types.tex --
%%%% Extra types for Common Lisp.


\documentclass[fleqn]{article}

\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{alltt}


\newcommand{\tm}{$^\mathsf{tm}$}
\newcommand{\cfr}{\emph{cfr.}}

\newcommand{\Lisp}{\textsf{Lisp}}
\newcommand{\CL}{\textsf{Common~Lisp}}

\newcommand{\checkcite}[1]{{\textbf{[Missing Citation: #1]}}}
\newcommand{\checkref}[1]{{\textbf{[Missing Reference: #1]}}}

\newcommand{\missingpart}[1]{{\ }\vspace{2mm}\\
{\textbf{[Still Missing: #1]}}\\
\vspace{2mm}}

\newcommand{\marginnote}[1]{%
\marginpar{\begin{small}\begin{em}
\raggedright #1
\end{em}\end{small}}}

\newcommand{\code}[1]{\texttt{#1}}

\newcommand{\term}[1]{\texttt{#1}}
\newcommand{\nonterm}[1]{\textit{$<$#1$>$}}


\title{
\LARGE{\bfseries Sub-interval Numerical Types for \CL{}}}

\author{
Marco Antoniotti\\
\vspace{2mm}
\texttt{mantoniotti} at \texttt{common-lisp.net}}

%\date{}


%\includeonly{}

\begin{document}

\maketitle

\begin{abstract}
This document presents a new set of portable type specifiers that can
be used to improve the ``precision'' of type declarations in numerical
code.
\end{abstract}

\section{Introduction}

When working on numerical algorithms it is sometimes useful to further
constrain the types of certain values to sub-intervals of the usual
types present in Common Lisp.  A typical example is that of indices
running over the dimensions of an array: such integers values should
not be negative.  While several \CL{} implementations already
have certain special ``sub-interval'' type specifiers that can be used
in implementation dependent code, it seems natural and relatively
uncontroversial to propose a set of specialized types that codify
usual mathematical numerical sets and intervals.  This document puts
forward such a proposal.

The rest of this document is organized in two parts: a description
of the new types proposed,
% a description of the (very simple) reference implementation
and a brief discussion pertaining to the rationale and the foreseen costs
of adoption by the various implementers.


\section{Description}

The extra types are presented in terms of the original \CL{} type they
partition.  As it will appear in the following, most types are simply
partitions around the appropriate \emph{zero}.


\subsection{Numerical Sub-interval Types}

There are several numerical types which represent traditional
mathematical sets in their representation-dependent implementations.
The numerical types are the following:
\begin{itemize}
\item \code{negative-}$T$
\item \code{non-positive-}$T$
\item \code{non-negative-}$T$
\item \code{positive-}$T$
\item \code{array-index}
\end{itemize}
where $T$ is one of \code{fixnum}, \code{integer}, \code{rational},
\code{ratio}, \code{real}, \code{float}, \code{short-float},
\code{single-float}, \code{double-float}, \code{long-float}.
Each of these types is defined in a very straightforward way.  The
pseudo-code in the subsections hereafter shows how each type can be
defined.

\subsubsection{\texttt{FIXNUM} Sub-interval Types}

The subtypes of type \texttt{fixnum}\footnote{There is no \emph{class}
  for \texttt{fixnum} in the ANSI specification , only a \emph{type}.
  This is a consequence of several factors and choices made in
  standardization process.} may be defined as follows.  Note that
\texttt{fixnum} does not allow for compound type specifiers.

\begin{alltt}
   (deftype negative-fixnum ()
      `(integer ,most-negative-fixnum -1))

   (deftype non-positive-fixnum ()
      `(integer ,most-negative-fixnum 0))

   (deftype non-negative-fixnum ()
      `(integer 0 , most-positive-fixnum))

   (deftype positive-fixnum ()
      `(integer 1 ,most-positive-fixnum))
\end{alltt}
The predicates following predicates are also defined in
the most straightforward way.
\begin{itemize}
\item \code{negative-fixnum-p}
\item \code{non-positive-fixnum-p}
\item \code{non-negative-fixnum-p}
\item \code{positive-fixnum-p}
\end{itemize}




\subsubsection{\texttt{INTEGER} Sub-interval Types}

The subtypes of type \code{integer} may be defined as follows.

\begin{alltt}
   (deftype negative-integer ()
      '(integer * -1))

   (deftype non-positive-integer ()
      '(integer * 0))

   (deftype non-negative-integer ()
      '(integer 0 *))

   (deftype positive-integer ()
      '(integer 1 *))
\end{alltt}
The following predicates are also defined in
the most straightforward way.
\begin{itemize}
\item \code{negative-integer-p}
\item \code{non-positive-integer-p}
\item \code{non-negative-integer-p}
\item \code{positive-integer-p}
\end{itemize}




\subsubsection{\texttt{RATIONAL} Sub-interval Types}

The subtypes of type \code{rational} may be defined as follows.

\begin{alltt}
   (deftype negative-rational ()
      '(rational * (0)))

   (deftype non-positive-rational ()
      '(rational * 0))

   (deftype non-negative-rational ()
      '(rational 0 *))

   (deftype positive-rational ()
      '(rational (0) *))
\end{alltt}
The following predicates are also defined in
the most straightforward way.
\begin{itemize}
\item \code{negative-rational-p}
\item \code{non-positive-rational-p}
\item \code{non-negative-rational-p}
\item \code{positive-rational-p}
\end{itemize}



\subsubsection{\texttt{RATIO} Sub-interval Types}

The subtypes of type \code{ratio} may be defined as follows.  Note
that \code{ratio} does not allow for compound type specifiers.  Also,
there are other technical difficulties in this case if we wanted to be
\emph{very} coherent with the background of the ANSI specification.
\code{ratio}s are defined exactly as the \emph{ratio of two non-zero
  integers, whose greatest common divisor is one and of which the
  denominator is greater than one}\footnote{A consequence of the
  definition is that, in general  \code{(typep 42
    'ratio)}~$\Rightarrow$~\code{NIL}, and, in particular,
  \code{(typep 0 'ratio)}~$\Rightarrow$~\code{NIL}.}.
This makes it very difficult
to use the type specifier machinery effectively, and we must resort to the
\code{satisfies} type specifier.  A possible
definition of the \code{ratio} sub-interval based on \code{satisfies}
needs therefore the definition of the \code{ratiop} predicate (which
is absent from the ANSI specification) alongside the
\code{ratio-plusp} and \code{ratio-minusp} predicates.

\begin{alltt}
   (defun ratiop (x)
      (and (rationalp x)
           (> (denominator x) 1)))

   (defun ratio-plusp (x)
      (and (ratiop x) (plusp x)))

   (defun ratio-minusp (x)
      (and (ratiop x) (minusp x)))
\end{alltt}
These predicates could be implemented more efficiently by a given
implementation.

\noindent
Now it is possible to define the \code{ratio} types.
\begin{alltt}
   (deftype negative-ratio ()
      '(satisfies ratio-minusp))

   (deftype non-positive-ratio ()
      'negative-ratio)

   (deftype non-negative-ratio ()
      'positive-ratio)

   (deftype positive-ratio ()
      '(satisfies ratio-plusp))
\end{alltt}
The following predicates are also defined in
the most straightforward way.
\begin{itemize}
\item \code{negative-ratio-p}
\item \code{non-positive-ratio-p}
\item \code{non-negative-ratio-p}
\item \code{positive-ratio-p}
\end{itemize}


\subsubsection{\texttt{REAL} Sub-interval Types}

The subtypes of type \code{real} may be defined as follows.

\begin{alltt}
   (deftype negative-real ()
      '(real * (0)))

   (deftype non-positive-real ()
      '(real * 0))

   (deftype non-negative-real ()
      '(real 0 *))

   (deftype positive-real ()
      '(real (0) *))
\end{alltt}
The following predicates are also defined in
the most straightforward way.
\begin{itemize}
\item \code{negative-real-p}
\item \code{non-positive-real-p}
\item \code{non-negative-real-p}
\item \code{positive-real-p}
\end{itemize}





\subsubsection{\texttt{FLOAT} Sub-interval Types}

The subtypes of the various \emph{float} types may be defined as
follows.

\begin{alltt}
   (deftype negative-\(T\) () '(\(T\) * (\(\mathrm{\textit{zero}}\))))
   (deftype non-positive-\(T\) () '(\(T\) * \(\mathrm{\textit{zero}}\)))
   (deftype non-negative-\(T\) () '(\(T\) \(\mathrm{\textit{zero}}\) *))
   (deftype positive-\(T\) () '(\(T\) (\(\mathrm{\textit{zero}}\)) *))
\end{alltt}
where $T$ is one of \code{float}, \code{short-float},
\code{single-float}, \code{double-float}, and \code{long-float}.
Also, $\mathrm{\textit{zero}}$ is written in the appropriate syntax;
i.e.,
\begin{itemize}
\item \code{0.0E0} for \code{float} types
\item \code{0.0S0} for \code{short-float} types
\item \code{0.0F0} for \code{single-float} types
\item \code{0.0D0} for \code{double-float} types
\item \code{0.0L0} for \code{long-float} types
\end{itemize}
as per the ANSI specification.

The appropriate type predicates (whose names are not listed here) can
be implemented in the usual straightforward way.


\subsubsection{\texttt{ARRAY-INDEX} Sub-interval Type}

The \code{array-index} type is obviously useful and used in many
implementations.  It is just not standardized.  The definition of
\code{array-index} could be the following one.

\begin{alltt}
   (deftype array-index ()
      `(integer 0 (,array-dimension-limit)))
\end{alltt}
The \code{array-index-p} predicate can thus be defined immediately.


\section{Discussion}

The proposed types are obviously just a convenience, yet they may be
used to improve the ``self-documenting'' nature of programs.  Some of
the definitions are directly useful.  Looping through an array can be
done in several ways, but often one just forgoes to write down the
proper index declaration or resorts to the practically omni-present
implementation-dependent equivalent of \code{array-index}.

The cost of adoption is very small for this facility.  Legacy code is
not affected and new code may - as stated - become more
self-documenting, and possibly efficient.

% Some of the names are long.  This is in the tradition of \CL{}.
% However, it would be possible to provide abbreviated versions by
% shortening them using the following scheme
% \begin{itemize}
% \item \code{negative} becomes \code{neg}
% \item \code{non-negative} becomes \code{nonneg}
% \item \code{positive} becomes \code{pos}
% \item \code{non-positive} becomes \code{nonpos}
% \end{itemize}

\begin{thebibliography}{9}

\bibitem{ANSIHyperSpec} K. M. Pitman
\textit{The \CL{} Hyperspec,}
published online at \texttt{http://www.lisp.org/HyperSpec/FrontMatter/index.html},
1994.

\end{thebibliography}


% \appendix

% \section{License}

% This document is put in the public-domain.

\end{document}

%%%% end of file -- extra-num-types.tex --