BASIC is a computer programming language developed in the mid 1960's by Professors John G. Kemeny and Thomas E. Kurtz at Dartmouth College. The primary motivation behind its design was educational (in contrast to the design goals for, e.g. COBOL and FORTRAN) and accordingly the language has always emphasized ease of use and understanding as opposed to simple machine efficiency. In July 1973, NBS published a "Candidate Standard for Fundamental BASIC" (2) by Prof. John

John A. N. Lee of the University of Massachusetts at Amherst. This work represented the beginning of

serious effort to standardize BASIC. The first meeting of the American National Standards Technical Committee on the Programming Language BASIC, X3J2, convened at CBEMA head quarters in Washington DC, on January 23-24, 1974, with Professor Kurtz as chairman. The committee adopted a program of work which envisioned development

of a nucleus language followed by modularized enhancements. The nucleus finally emerged as Minimal BASIC, which was approved as an ANSI standard January 17, 1978. As its name implies, the language defined in the standard is one which any implementation of BASIC should encompass.

Meanwhile, NBS had been developing a set of test programs, the purpose

of which was to exercise all the facilities defined in the standard and thereby test conformance of implementations to the standard. This test suite was released as NBSIR 78-1420-1, 2, 3, and 4, NBS Minimal BASIC Test Programs - Version 1 User's Manual in January 1978. NBS distributed this version to more than 60 users, many of whom made suggestions about how the test suite might be improved. NBS has endeavored to incorporate these suggestions and re-design the tests where it seemed useful to do so. The result is the current Version 2 of the test suite. Appendix A contains a summary of the differences between versions 1 and 2.

In order to

provide a larger selection of high level programming languages for the Federal

government's ADP activities, the Department of Commerce has incorporated the ANSI standard as Federal Information Processing Standard 68. This means, among other things, that implementations of BASIC sold

to the Federal government after an 18 month transition period must conform to the technical specifications of the ANSI standard: hence the NBS interest in developing a tool for measuring such conformance.

and

ANSI X3J2 is currently (April 1980) working on a language standard for a much richer version of BASIC, which will provide such features as real-time process control, graphics, string manipulation, file handling, exception handling,

array manipulation. The current expectation is for ANSI adoption of this standard sometime in

1982.

It is probable that such a standard for a full version of BASIC would be adopted as a Federal Information Processing Standard.

Minimal BASIC is distinguished among standardized computer languages by its simplicity and its suitability for the casual user. It is simple, not only because of its historic purpose as a computer language for the casual user, but also because the ANSI BASIC committee organized its work around the concept of first defining a

core

or nucleus language which one might reasonably expect any implementation of BASIC to include, to be followed by a standard for enhanced versions of the language. Therefore the tendency was to defer standardization of

all the sophisticated features and include only the simple features. In particular, Minimal BASIC has no facilities for file handling, string manipulation, or array manipulation and has only rudimentary control structures. Although BASIC was originally designed for interactive

use,

the standard does not restrict implementations to that use.

or

as

no

Minimal BASIC provides for only two types of data, numeric (with the properties usually associated with real floating-point numbers) and string. String data can be read input, printed as output, and moved and compared internally. The only legal comparisons, however, are e qual or not equal; collating sequence among characters is defined. Numeric data can be manipulated with the usual choice of operations : addition, subtraction, multiplication, division, and involution (sometimes called exponentiation). There is a modest assortment of numeric functions. One- and two-dimensional arrays are allowed, but only for numeric data, not string.

For control, there is a GOTO, an IF which can cause control to jump to any line

in

the program, a GOSUB and RETURN for internal subroutines, a FOR and NEXT statement to execute 1oops while incrementing a control-variable, and a STOP statement.

Input and output are accomplished with the INPUT

and

PRINT statements, both of which are designed for use on an interactive terminal. There is also a feature which has no real equivalent among the popular computer languages: a kind of internal file of data values, numeric and string, which can be assigned to variables with a READ statement (not to be confused with INPUT which handles external data). The internal set of values is created with DATA statements, and may be read repetitively from the beginning of the set by using the RESTORE statement.

The programmer may (but need not) declare the size of arrays with the DIM statement and specify that subscripts begin at 0 or 1 with an OPTION statement. The programmer may also establish numeric user-defined functions with the DEF statement, but only as simple expressions, taking one argument. The RANDOMIZE statement works in conjunction with the RND function. If RND is called without execution of RANDOMIZE, it always returns the same sequence of pseudo-random numbers for each execution of the program. Executing RANDOMIZE causes RND to return an unpredictable set of values each time.

insert

The REM statement allows the programmer to or remarks throughout the program.

comments

Although the facilities of the language are modest, there is one area in which the standard sets rather stringent requirements, namely, diagnostic messages. The mandate of the standard that implementations exhibit reasonable behavior even when presented with unreasonable programs follows directly from the design goal of

solicitude towards the beginning or casual user. Thus, the standard takes care to define what happens

if the user commits any

of a number of syntactic or semantic blunders. The need to test these diagnostic requirements strongly affected the overall shape of the test system as will become apparent in later sections.

There are many reasons for establishing a standard

for

a programming language: the promotion of well-defined and well-designed languages as consequence of the standardizing process itself, the ability to create language-based rather than machine-based software tools and techniques, the increase in programmer productivity which an industry-wide standard fosters, and so on. At bottom, however, there is one result essential to the success of a standard: program portability. The same program should not evoke perniciously different behavior in different implementations. Ideally, the same source code and data environment should produce the same output, regardless of the machine environment.

How does conformance to the standard work towards this goal? Essentially, the standard defines the set of syntactically legal programs, assigns a semantic meaning to all of them and then requires that implementations (sometimes called processors; we will use the two terms interchangeably throughout this document) actually produce the assigned meaning when presented with a legal program.

Program conformance, then, is a matter of syntax. We look at the source code and determine whether or not it obeys all the rules laid down in the standard. These rules are mostly spelled out in the syntax sections of the standard using a variant of Backus-Naur Form (BNF). They are supplemented, however, by certain context-sensitive constraints, which are contained in the semantics sections. Thus the rules form a ceiling for conforming programs. If a program has been constructed according to the rules, it meets the standard, without regard to its semantic meaning. The syntactic rules

arē

fully implementation independent: a standard program must be accepted by all standard

a

processors. Further, since we can tell if a program is standard by mere inspection, it would be a reasonably easy job to build a recognizer or syntax checker which could always discover whether or not a program is standard. Unfortunately, such recognizer could not be written in Minimal BASIC itself and this probably explains why no recognizer to check program conformance has gained wide acceptance. At least one such recognizer does exist, however. Called PBASIC (3), it was developed at the University of Kent at Canterbury and is written in PFORT, a portable subset of FORTRAN. PBASIC was used to check the syntax of the Version 2 Minimal BASIC Test Programs.

Implementation conformance is derivative of the more primitive concept of program conformance. In contrast to the way in which program conformance is described, processor conformance is

specified functionally, not structurally. The essential requirement is that an implementation accept any standard program and produce the behavior specified by the language standard. That is, the implementation

must make the proper connection between the syntax of the program and the operation of the computer system. Note that this is a black box description of the implementation. Whether the realization of the language is done with a compiler, an interpreter, firmware, or by being hard-wired, is irrelevant. Only the external behavior is important, not the internal structure quite the opposite of the way program conformance is determined.

is

The difference

in

the way conformance is defined for programs and processors radically affects the test methodology by which we determine whether the standard is met.

The relevant point

that there currently is no way to be certain that an implementation does conform to the standard, although we can sometimes be certain that it does not. In short, there is no algorithm, such as the recognizer that exists for programs, by which we can answer definitively the question, "! Is this a standard processor?"

at

Furthermore, the standard acts as a floor for processors, rather than a ceiling. That is, an implementation must accept and process least all standard programs, but

may also implement enhancements to the language and thus accept non-standard programs

as

well. Another difference between program and processor conformance

that the description of processor conformance allows for some implementation dependence even in the treatment of standard programs. Thus for some standard programs there is no unique semantic meaning, but rather a set of meanings, usually similar, among which implementations can choose.

is

3

DETERMINING IMPLEMENTATION CONFORMANCE

3.1

Test Programs AS Test Data, Not Algorithms

As

is

The test programs do not embody some definitive algorithm by which the question of processor conformance can be answered yes or no. There is an important sense in which it

only accidental that they are programs at all; indeed, some of them, syntactically, are not. Rather their primary function is as test data. It is readily apparent, for instance, that the majority of BASIC test programs are algorithmically trivial: some consist only

of

a series of PRINT statements. Viewed as test data, however, i.e., a series of inputs to a system whose behavior we wish to probe, the underlying motivation for their structure becomes intelligible. Simply put, it is the goal of the tests to exercise at least one representative of every

meaningfully distinct type

of
syntactic structure or

semantic behavior provided for in the language standard. This strategy is characteristic of testing in general: all one can do is submit a representative subset

the typically infinite number of possible inputs to

the system under investigation (the implementation) and see whether the results are in accord with the specifications for that system (the language standard).

of

Thus, successful results of the tests are necessary, but not sufficient to show that the specifications are met. A failed test shows that a language implementation is not standard. A passed test shows that it may be. A long series of passed tests which seem to cover all the various aspects of the language gives us a large measure of confidence that the implementation conforms to the standard.

It can scarcely be stressed too strongly that the test programs do not represent some self-sufficient algorithm which will automatically deliver correct results to a passive observer. Rather they are best seen as one component in a larger System comprising not only the programs, but the documentation of the programs, the documentation of the processor under test, and, not least, a reasonably well-informed user who must actively interpret the results of the tests in the context of some broad background knowledge about the programs, the processor, and the language standard. If, for example, a processor rejects a standard program, it certainly fails to conform to the standard ; yet this is a type of behavior which can hardly be detected by the

program itself: only a human observer who knows that the processor must accept standard programs, and that this program is standard, is capable of the proper judgment that this

processor therefore violates the language standard.