ilc2005.tex 27.3 KB
Newer Older
pfdietz's avatar
pfdietz committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
\documentclass[11pt]{article}
% \setlength{\oddsidemargin}{0in}
% \setlength{\evensidemargin}{0in}
% \setlength{\footskip}{1in}
% \setlength{\textwidth}{6.5in}

\usepackage[letterpaper,textwidth=6.7in,textheight=8.7in]{geometry}
\usepackage{graphics}
\usepackage{url}
\usepackage{times}
%\usepackage[british]{babel}
% \usepackage{theorem}
\setlength{\topmargin}{.35in}
\newtheorem{theorem}{Theorem}

\pagestyle{empty}

\begin{document}
\title{The GCL ANSI Common Lisp Test Suite}
\author{Paul F. Dietz\footnote{Motorola Global Software Group, 1303
E. Algonquin Road, Annex 2, Schaumburg, IL 60196.  paul.f.dietz@motorola.com}}
\date{}
\maketitle
\thispagestyle{empty}

\begin{abstract}
I describe the conformance test suite for ANSI Common Lisp distributed
as part of GNU Common Lisp (GCL).  The test suite includes more than
20,000 individual tests, as well as random test generators for
exercising specific parts of Common Lisp implementations, and has
revealed many conformance bugs in all implementations on
which it has been run.
\end{abstract}

\section{Introduction}

One of the strengths of Common Lisp is the existence of a large,
detailed standard specifying the behavior of conforming
implementations.  The value of the standard to users is enhanced when
they can be confident that implementations that purport to conform
actually do.

In the 1990s I found substantial numbers of conformance bugs in many
Lisp implementations.  As a result, I decided to build a
comprehensive functional test suite for Common Lisp.  The goals of the
effort were, in no particular order:

\begin{itemize}
\item To thoroughly familiarize myself with the standard.
\item To provide a tool to locate conformance problems in CL
implementations, both commercial and free.
\item To enable implementors to improve CL implementations while
      maintaining conformance.
\item To explore the standard itself for ambiguities, unintended
      consequences, and other problems.
\item To explore different testing strategies.
\end{itemize}

I deliberately did not design the test suite to measure or rank
conformance of Lisp implementations.  For this reason, I will not here
report the overall score of any implementation.

I decided to locate the test suite in the GCL development tree for two
reasons.  First, its development team had a goal of making GCL more
ANSI compliant, and tests would assist there.  Secondly, the GCL CVS
tree is easily publicly accessible\footnote{See
\url{http://savannah.gnu.org/projects/gcl/}}, so any developers or users of
Common Lisp implementations would have easy access to it.

The test suite was constructed over the period from 1998 to 2005, with
most of the work done in 2002 to 2004.  
As of 24 May 2005, the test suite contains over 20,000 tests.

The test suite is based on a version of the ANSI Common Lisp
specification (ANSI/INCITS 226-1994, formerly ANSI X3.226-1994) that
was made publicly available by Harlequin (now LispWorks) in
hyperlinked form in 1996 \cite{X3J13:94}.

Table \ref{lispimpltab} contains a list of Lisp implementations on
which I am aware the test suite has been run.

\begin{table}
\begin{center}
\begin{tabular}{lr}
Implementation & Hardware Platforms \\ \hline
GNU Common Lisp & All debian platforms \\
GNU CLISP & x86 \\
CMUCL & x86, Sparc \\
SBCL & x86, x86-64, Sparc, MIPS, Alpha, PowerPC \\
Allegro CL (6.2, 7) & x86, Sparc, PowerPC \\
LispWorks (4.3) & x86 \\
OpenMCL & PowerPC \\
ABCL & x86 (JVM) \\
ECL & x86 \\
\end{tabular}
\end{center}
\caption{\label{lispimpltab} Implementations Tested}
\end{table}

\section {Infrastructure}

The test suite uses Waters' RT package \cite{Waters:91a}.  This
package provides a simple interface for defining tests.  In its
original form, tests are defined with a name (typically a symbol
or string), a form to be evaluated, and zero or more expected
values.  The test passes if the form evaluates to the specified
number of values, and those values are as specified.  See figure
\ref{examplefig} for an example from the test suite:

\begin{figure}
\begin{verbatim}
   (deftest let.17
     (let ((x :bad))
       (declare (special x))
       (let ((x :good)) ;; lexical binding
         (let ((y x))
           (declare (special x)) ;; free declaration
           y)))
     :good)
\end{verbatim}
\caption{\label{examplefig} Example of a test}
\end{figure}

As the test suite evolved RT was extended.  Features added include:
\begin{itemize}
   \item Error conditions raised by tests may be trapped.
   \item Tests may optionally be executed by wrapping the form to be
evaluated in a lambda form, compiling it, and calling the compiled
code.  This makes sense for testing Lisp itself, but would not be
useful for testing Lisp applications.
   \item A subset of the tests can be run repeatedly, in random order, a
style of testing called \emph{Repeated Random Regression} by Kaner,
Bond and McGee \cite{KanerBondMcGee:04}\footnote{This was previously
called `Extended Random Regression'; McGee renamed it to avoid the
confusing acronym.}
   \item Notes may be attached to tests, and these notes used to turn off
groups of tests.

\item Tests can be marked as being expected to fail.  Unexpected
      failures are reported separately.
\end{itemize}

\section {Functional Tests}

The bulk of the test suite consists of functional tests derived from
specific parts of the ANSI specification.  Typically, for each
standardized operator there is a file \emph{operator}.lsp containing
tests for that operator.  This provides a crude form of traceability.
There are exceptions to this naming convention, and many tests that
test more than one operator are located somewhat arbitrarily.
Table \ref{tab:testsize} shows the number and size of tests for each
section of the ANSI specification.

\begin{table}
\begin{center}
\begin{tabular}{|l|r|r|}
\hline
Section of CLHS & Size (Bytes) & Number of Tests \\
\hline \hline
Arrays & 212623 & 1109 \\
Characters & 38655 & 256  \\
Conditions & 71250 & 658 \\
Cons & 264208 & 1816 \\
Data \& Control Flow & 185973 & 1217 \\
Environment & 51110 & 206 \\
Eval/Compile & 41638 & 234 \\
Files & 26375 & 87 \\
Hash Tables & 38752 & 158 \\
Iteration & 98339 & 767  \\
Numbers & 290991 & 1382 \\
Objects & 283549 & 774 \\
Packages & 162203 & 493 \\
Pathnames & 47100 & 215 \\
Printer & 454314 & 2364 \\
Reader & 101662 & 663 \\
Sequences & 562210 & 3219 \\
Streams & 165956 & 796 \\
Strings & 83982 & 415 \\
Structures & 46271 & 1366 \\
Symbols & 106063 & 1141 \\
System Construction & 16909 & 77 \\
Types & 104804 & 599 \\
Misc & 291883 & 679 \\ \hline
Infrastructure & 115090 & \\
Random Testers & 190575 & \\
\hline
Total & 4052485 & 20702 \\
\hline
\end{tabular}
\end{center}

\caption{\label{tab:testsize} Sizes of Parts of the Test Suite}
\end{table}

Individual tests vary widely in power.  Some are as simple as a
test that {\tt (CAR NIL)} is {\tt NIL}.  Others are more involved.
For example, {\tt TYPES.9} checks that {\tt SUBTYPEP} is transitive
on a large collection of built-in types.

The time required to run the test suite depends on the implementation,
but it is not excessive on modern hardware.  SBCL 0.9.0.41 on a
machine with 2 GHz 64 bit AMD processor, for example, runs the test
suite in under eight minutes.

Error tests have been written where the error behavior is specified by
the standard.  This includes specifications in the `Exceptional
Situations' sections for operator dictionary entries, as well as tests
for calls to functions with too few or too many arguments, keyword
parameter errors, and violations of the first paragraph of CLHS
section 14.1.2.3.  When type errors are specified or when the CLHS
requires that some operator have a well-defined meaning on any Lisp
value, the tests iterate over a set of precomputed Lisp objects
called the `universe' that contains representatives of all
standardized Lisp classes.  In some cases a subset of this universe is
used, for efficiency reasons.

There are some rules that perform random input testing.  This testing
technique is described more fully in the next section.  Other tests
are themselves deterministic, but are the product of one of the
suite's high volume random test harnesses.  The `Misc' entry in table
\ref{tab:testsize} refers to these randomly generated tests.  Each of
these tests caused a failure in at least one implementation.

Inevitably, bugs have appeared in the test suite.  Running the test
suite on multiple implementations (see table \ref{lispimpltab})
exposes most problems.  If a test fails in most of them, it is likely
(but not certain) that the test is flawed.  Feedback from implementors
has also been invaluable, and is deeply appreciated.  In some cases,
when it has not been possible to agree on the proper interpretation
of the standard, I've added a note to the set of disputed tests so
they can be disabled as a group.  This is in keeping with the purpose
of the test suite -- to help implementors, not judge implementations.


\section {Random Testing}

Random testing (more properly, random-input testing) is a standard
technique in the testing of hardware systems.  However, it has been the
subject of controversy in the software testing community for more than
two decades.  Myers \cite{Myers:79} called it ``Probably the poorest
... methodology of all''.  This assessment presumes that the cost of
executing tests and checking their results for validity dominates the
cost of constructing the tests.  If test inputs can be constructed and
results checked automatically, it may be very cost-effective to
generate and execute many lower quality tests.  Kaner et
al. call this High Volume Automated Testing \cite{KanerBondMcGee:04}.

Duran and Ntafos \cite{DuranNtafos:81} report favorably on the ability
of random testing to find relatively subtle bugs without a great deal
of effort.  Random testing has been used to test Unix utilities
(so-called `fuzz testing') \cite{MillerFredriksenSo:90}, database
systems \cite{Slutz:98}, and C compilers \cite{McKeeman:98,Lindig:05,Faigon:05}.
Bach and Schroeder \cite{BachSchroeder:04} report that random input
testing compares well with the ability of the popular All-Pairs
testing technique at actually finding bugs.

Random input testing provides a powerful means of testing algebraic
properties of systems.  Common Lisp has many instances where such
properties can be checked, and the test suite tests many of them.
Random testing is used to test numeric operators, type operators,
the compiler, some sequence operators, and the readability of
objects printed in `print readably' mode.

One criticism of random testing is its irreproducibility.
With care, this needn't be a problem.  If a random failure
is sufficiently frequent, it can be reproduced with high
probability by simply running a randomized test again.  Tests
can also be designed so that on failure, they print sufficient
information so that a non-randomized test can be constructed
exercising the bug.  Most of the randomized tests in the test
suite have this property.

\subsection {Compiler Tests}
\label{sec:compilertests}

Efficiency of compiled code has long been one of Common Lisp's
strengths.  Implementations have been touted as in some cases
approaching the speed of statically typed languages.  Achieving this
efficiency places strong demands on Lisp compilers.  A sufficiently
smart compiler needs a sufficiently smart test suite.

Compilers (and Lisp compilers in particular) are an ideal target for
random input testing.  Inputs may have many parts that interact in
the compiler in unpredictable ways.  Because the language has a
well-defined semantics, it is easy to generate related, but different,
forms that should yield the same result (thereby providing a test
oracle.)

The Random Tester performs the following steps.  For some input
parameters $n$ and $s$ (each positive integers):
\begin{enumerate}
  \item Produce a list of $n$ symbols that will be the parameters
	of a lambda expression.  These parameters will have integer
	values.
  \item Produce a list of $n$ finite integer subrange types.  These
        will be	the types of the lambda parameters.  The endpoints of
	these types are not uniformly distributed, but instead follow
	an approximately exponential distribution, preferring small
	integers over larger ones.  Integers close in absolute value
        to integer powers of 2 are also overrepresented.
  \item Generate a random conforming Lisp form of `size' approximately $s$
        containing (mostly) integer-valued forms.  The parameters from
        step 1 occur as free variables.
  \item From this form, construct two lambda forms.  In the first,
	the lambda parameters are declared to have their integer
	types, and random {\tt OPTIMIZE} settings are included.  In the
	second, a different set of {\tt OPTIMIZE} settings is declared, and
	all the standardized Lisp functions that occur in the form
	are declared {\tt NOTINLINE}.  The goal here is to attempt to make
	optimizations work differently on the two forms.
  \item For each lambda form, its value on each set of inputs is
        computed.  This is done either by compiling the lambda form
	and calling it on the inputs, or by evaling forms in which
	the lambda form is the {\tt CAR} and the argument list the
	{\tt CDR}.
  \item A failure occurs if any call to the compiler or evaluator
	signals an error, or if the two lambda forms yield different
	results on any of the inputs.
\end{enumerate}
        
This procedure very quickly -- within seconds -- found failures in
every Lisp implementation on which it was tried.  Failures included
assertion failures in the compiler, type errors, differing return
values, code that caused segmentation faults, and in some cases code
that crashed the Lisps entirely.  Most of the 679 `Misc' tests in
table \ref{tab:testsize} were produced by this tester; each represents
a failure in one or more implementations.

Generating failing tests was easy, but minimizing them was tedious
and time consuming.  I therefore wrote a pruner that repeatedly tries
to simplify a failing random form, replacing integer-valued subforms
with simpler ones, until no substitution preserving failure
exists.  In most cases, this greatly reduced the size of the failing
form.  Others have previously observed that bug-exposing random inputs
can often be automatically simplified
\cite{HildZeller:02a,McKeeman:98}.  The desire to be able to
automatically simplify the failing forms constrained the tester;
I will discuss this problem later in section \ref{sec:future}.

\begin{table}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline Sourceforge Bug \# & Type of Bug & Description \\
\hline
813119 & C & Simplification of conditional forms \\
842910 & C & Simplification of conditional forms \\
842912 & R & Incorrect generated code \\
842913 & R & Incorrect generated code \\
858011 & C & Compiler didn't handle implicit block in {\tt FLET} \\
858658 & R & Incorrect code for {\tt UNWIND-PROTECT} and multiple values \\
860052 & C & Involving {\tt RETURN-FROM} and {\tt MULTIPLE-VALUE-PROG1}. \\
864220 & C & Integer tags in tagbody forms. \\
864479 & C & Compiler bug in stack analysis. \\
866282 & V & Incorrect value computed due to erroneous side effect \\
& & analysis in compiler on special variables \\
874859 & R & Stack mixup causing catch tag to be returned. \\
889037 & V & Bug involving nested {\tt LABELS}, {\tt UNWIND-PROTECT},
{\tt DOTIMES} forms. \\
890138 & R & Incorrect bytecodes for {\tt CASE}, crashing the Lisp. \\
1167991 & C & Simplification of conditional forms. \\ \hline
\end{tabular}

Legend:
\begin{tabular}{ll}
C & Condition thrown by the compiler (assert or type check failure.) \\
R & Condition thrown at runtime (incorrectly compiled code). \\
V & Incorrect value returned by compiled code. \\
\end{tabular}
\end{center}
\caption{\label{clispbugs} Compiler bugs found in GNU CLISP by Random Tester}
\end{table}

Table \ref{clispbugs} contains a list of the fourteen compiler bugs
detected by the random tester in GNU CLISP.  Roughly 200 million
iterations of the random tester were executed to find these bugs,
using a single 1.2 GHz Athlon XP+ workstation running intermittently
over a period of months.  All these bugs have been fixed (in CVS) and
CLISP now fails only when the random forms produce bignum values that
exceed CLISP's internal limit.

The greatest obstacle to using the random tester is the presence of
unfixed, high probability bugs.  If an implementation has such a bug,
it will generate many useless hits that will conceal
lower probability bugs.

\subsection {Types and Compilation}

Type inference and type-based specialization of built-in operators is a
vital part of any high performance Lisp compiler for stock hardware,
so it makes sense to focus testing effort on it.  The test suite
contains a facility for generating random inputs for operators and
compiling them with appropriate randomly generated type annotations,
then checking if the result matches that from an unoptimized version
of the operator.

As an example, the operator {\tt ISQRT} had this bug in one commercial
implementation:
\begin{verbatim}
  (compile nil '(lambda (x) (declare (type (member 4 -1) x)
                                     (optimize speed (safety 1)))
                            (isqrt x)))
  ==> Error: -1 is illegal argument to isqrt
\end{verbatim}
Amusingly, the bug occurs only when the negative integer is the second
item in the {\tt MEMBER} list.  The test that found this bug is
succinctly defined via a macro:
\begin{verbatim}
  (def-type-prop-test isqrt 'isqrt '((integer 0)) 1)
\end{verbatim}
The function to be compiled can be generated in such a way that it stores
the result value into an array specialized to a type that contains
the expected value.  This is intended to allow the result value to
remain unboxed.

The general random testing framework of section
\ref{sec:compilertests} is also useful for testing type-based compiler
optimizations, with two drawbacks: it currently only handles integer
operators, and it is less efficient than the more focused tests.
Even so, it was used to improve unboxed arithmetic in several
implementations (SBCL, CMUCL, GCL, ABCL).

\subsection {{\tt SUBTYPEP} Testing}

The test suite uses the algebraic properties of the {\tt SUBTYPEP}
function in both deterministic and randomized tests.  For example,
if {\tt T1} is known to be a subtype of {\tt T2}, we can also check:
\begin{verbatim}
    (subtypep '(not t2) '(not t1))
    (subtypep '(and t1 (not t2)) nil)
    (subtypep '(or (not t1) t2) t)
\end{verbatim}

The generator/pruner approach of the compiler random tester was
applied to testing {\tt SUBTYPEP}.  Random types were generated and,
if one was a subtype of the other, the three alternative formulas
were also tested.  If any return the two values (false, true), a
failure has been found.

Christophe Rhodes used feedback from this tester to fix logic and
performance bugs in SBCL's {\tt SUBTYPEP} implementation.  The
handling of {\tt CONS} types is particularly interesting, since
deciding the subtype relationship in the presence of cons types is
NP-hard.  At least one implementation's {\tt SUBTYPEP} will run wild
on moderately complicated cons types, consuming large amounts of
memory before aborting.

\subsection {Repeated Random Regression}

As mentioned earlier, RRR is a technique for executing tests in an
extended random sequence, in order to flush out interaction bugs and
slow corruption problems.  As an experiment, RT was extended to
support RRR on subsets of the tests.  The main result was to find many
unwanted dependencies in the test suite, particularly among the
package tests.  These dependencies had not surfaced when the tests had
been run in their normal order.

After fixing these problems, RRR did find one CLOS bug in CLISP,
involving interaction between generic functions and class
redefinitions.  The bug was localized by bisecting the set of tests
being run until a minimal core had been found, then minimizing the
sequence of invocations of those tests.  If more bugs of this kind are
found it may be worthwhile to add a delta debugging
\cite{HildZeller:02a} facility to perform automatic test minimization.

In Lisps that support preemptively scheduled threads, it would be
interesting to use RRR with subsets of the tests that lack global side
effects.  The tests would be run in two or more threads at once in
order to find thread safety problems.

\section {Issues with the ANSI Common Lisp Specification}

Building the test suite involved going over the standard in detail.
Many points were unclear, ambiguous, or contradictory; some
parts of the standard proved difficult to test in a portable
way.  This section describes some of these findings.

See `Proposed ANSI Revisions and Clarifications' on
\url{http://www.cliki.net/} for a more complete list that includes
issues arising from the test suite.

\subsection {Testability}

Some parts of the standard proved difficult to test in a completely
conforming way.  The specification of pathnames, for example, was
difficult to test.  The suite has assumed that UNIX-like filenames
are legal as physical pathnames.

Floating point operators presented problems.  The standard does not
specify the accuracy of floating point computations, even if it
does specify a minimum precision for each of the standardized float
types. \footnote{The standard does specify a feature indicating
the implementation purports to conform to the IEEE Standard for Binary
Floating Point Arithmetic (ANSI/IEEE Std 754-1985); this suite
does not test this.}  Some implementations have accuracy that varies
depending on the details of compilation; in particular, boxed values
may be constrained to 64 bits while unboxed values in machine
registers may have additional `hidden' bits.  These differences
make differential testing challenging.

The Objects chapter contains interfaces that are intended to be used
with the Metaobject Protocol (MOP).  Since the MOP is not part of the
standard, some of these cannot be tested.  For example, there is
apparently no conforming way to obtain an instance of class {\tt
METHOD-COMBINATION}, or to produce any subclass of {\tt
GENERIC-FUNCTION} except for {\tt STANDARD-GENERIC-FUNCTION}.

\subsection {Unintended Consequences}

There seem to be many issues associated with Common Lisp's type
system.  One example is the {\tt TYPE-OF} function.  According
to the standard, this function has the property that
\begin{quote}
  For any object that is an element of some built-in type: [\ldots]
  the type returned is a recognizable subtype of that built-in type.
\end{quote}
A \emph{built-in} type is defined to be
\begin{quote}
  built-in type {\it n}. one of the types in Figure 4-2.
\end{quote}
Figure 4-2 of the standard contains {\tt UNSIGNED-BYTE}, the type of
nonnegative integers.  These constraints imply that {\tt TYPE-OF} can
never return {\tt FIXNUM} or {\tt BIGNUM} for any nonnegative integer,
since neither of those types is a subtype of {\tt UNSIGNED-BYTE}.

A more serious set of problems involves {\tt
UPGRADED-ARRAY-ELEMENT-TYPE}. \footnote{I ignore the issue that,
strictly speaking, {\tt UPGRADED-ARRAY-ELEMENT-TYPE} is either an
identity function or is not computable, since as defined it must work
on {\tt SATISFIES} types.}  This function (from types to types) is
specified to satisfy these two axioms for all types $T_1$ and $T_2$:
\begin{displaymath}
   T_1 \subseteq UAET(T_1) 
\end{displaymath}
and
\begin{displaymath}
   T_1 \subseteq T_2 \Longrightarrow UAET(T_1) \subseteq UAET(T_2)
\end{displaymath}
A type $T_1$ is a \emph{specialized array element type} if $T_1 = UAET(T_1)$.
These axioms imply:
\begin{theorem}
If two types $T_1$ and $T_2$ are specialized
array element types, then so is $T_1 \cap T_2$.
\end{theorem}

This theorem has a number of unpleasant consequences.  For example,
if {\tt (UNSIGNED-BYTE 16)} and {\tt (SIGNED-BYTE 16)} are specialized
array element types, then so must be {\tt (UNSIGNED-BYTE 15)}.  Even
worse, since {\tt BIT} and {\tt CHARACTER} are required to be
specialized array element types, and since they are disjoint,
then {\tt NIL}, the empty type, must also be a specialized array
element type.  Topping all this off, note that
\begin{quote}
    A string is a specialized vector whose elements are of type
    character or a subtype of type character. (CLHS page for {\tt STRING})
\end{quote}
Since {\tt NIL} is a subtype of {\tt CHARACTER}, a vector with
array element type {\tt NIL} is a string.  It is
impossible for a conforming implementation to have only a
single representation of strings.\footnote{But since `nil strings' can
never be accessed, it's acceptable in non-safe code to just assume 
string accesses are to some other string representation.  The SBCL
implementors took advantage of this when using nil strings as a stepping
stone to Unicode support.}

\section {Directions For Future Work}
\label{sec:future}

The test suite still has a few areas that are not sufficiently tested.
Setf expanders need more testing, as do logical pathnames and file
compilation.  Floating point functions are inadequately tested.  As
mentioned earlier, it isn't clear what precision is expected of these
functions, but perhaps tests can be written that check if the error
is too large (in some sufficiently useful sense.)

The random compiler tester, as implemented, is constrained to generate
forms that remain conforming as they are simplified.  This limits the
use of certain operators that do not take the entire set of integers
as their arguments.  For example, {\tt ISQRT} appears only in forms
like {\tt (ISQRT (ABS ...))}, and this pattern is preserved during
pruning.  The forms also make very limited use of non-numeric types.

More sophisticated random tester could avoid these limitations.  One
approach would be to randomly generate trees from which Lisp forms
could be produced, but that also carry along information that would
enable pruning to be done more intelligently.  Another approach would
be to check each pruned form for validity on the set of chosen random
inputs by doing a trial run with all operators replaced by special
versions that always check for illegal behaviors.  I intend to explore
both options.

The test suite has been written mostly as a `black box' suite (aside
from the randomly generated Misc tests).  It would be interesting to
add more implementation knowledge, with tests that, while conforming,
will be more useful if the Lisp has been implemented in a particular
way.  The type propagation tester is an example of this kind of `gray
box' testing.

It would be interesting to determine the level of coverage achieved by
the test suite in various implementations.  The coverage is probably
not very good, since the suite cannot contain tests of nonstandardized
error situations, but this should be confirmed, and compared against
the coverage obtained from running typical applications.  Internal
coverage could also provide feedback for nudging the random tester
toward testing relatively untested parts of the compiler, say by using
an evolutionary algorithm on the parameters governing the construction
of random forms.

\section {Acknowledgments}

I would like to thank Camm Maguire, the head of the GCL development
team, for allowing the GCL ANSI test suite to be a part of that
project.  I also would like to thank users of the test suite who have
returned feedback, including Camm, Christophe Rhodes, Sam Steingold,
Bruno Haible, Duane Rettig, Raymond Toy, Dan Barlow, Juan Jos\'{e}
Garc\'{i}a-Ripoll, Brian Mastenbrook and many others.

\nocite{X3J13:94}
\nocite{McKeeman:98}
\nocite{DuranNtafos:81}
\nocite{KanerBondMcGee:04}
\nocite{Waters:91a}
\nocite{HildZeller:02a}
\nocite{BachSchroeder:04}
\nocite{Slutz:98}
\nocite{Lindig:05}
\nocite{Myers:79}

\bibliography{lisp}
\bibliographystyle{plain}

\end{document}