

                                the
                               Small
                              booklet



                            December 1998



Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1
Small: the language. . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
    Data and declarations. . . . . . . . . . . . . . . . . . . . . . . . .  8
    Functions  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
    General syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
    Operators and expressions  . . . . . . . . . . . . . . . . . . . . . . 25
    Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
    Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
    Proposed function library  . . . . . . . . . . . . . . . . . . . . . . 39
    Pitfalls: differences from C . . . . . . . . . . . . . . . . . . . . . 44
    Assorted tips  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Small: the compiler  . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
    Compiler diagnostics . . . . . . . . . . . . . . . . . . . . . . . . . 50
The abstract machine . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
    Using the abstract machine . . . . . . . . . . . . . . . . . . . . . . 59
    Extension modules  . . . . . . . . . . . . . . . . . . . . . . . . . . 61
    Function reference . . . . . . . . . . . . . . . . . . . . . . . . . . 63
    Error codes  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
    A: Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
    B: Design of the abstract machine  . . . . . . . . . . . . . . . . . . 80
    C: Abstract machine reference  . . . . . . . . . . . . . . . . . . . . 86
    D: Code generation notes . . . . . . . . . . . . . . . . . . . . . . . 95
Index  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
ii

"Java" is a trademark of Sun Microsystems, Inc.
"Lua" is a product of, and copyrighted by TeCGraf, PUC-Rio, Brazil.
"Microsoft" and "Microsoft Windows" are registered trademarks of Microsoft
    Corporation.
"CompuPhase" is a registered trademarks of ITB CompuPhase.



Copyright (c) 1997--1998, ITB CompuPhase; Brinklaan 74-b, 1404GL Bussum, The
Netherlands (Pays Bas); voice: (+31)-(0)35 6939 261; fax: (+31)-(0)35 6939
293
e-mail: info@compuphase.com, CompuServe: 100115,2074
WWW: http://www.compuphase.com

The information in this manual and the associated software are provided "as
is". There are no guarantees, explicit or implied, that the software and the
manual are accurate.

Requests for corrections and additions to the manual and the software can be
directed to ITB CompuPhase at the above address.

Typeset with TEX in "Computer Modern" 11 points.
                                                               o  1

                            Introduction

******************************************************************************
------------------------------------------------------------------------------

Small is a simple, typeless, 32-bit extension language with a C-like syntax.
The Small compiler outputs P-code (or bytecode) that subsequently runs on an
abstract machine. Execution speed, stability, simplicity and a small footprint
were essential design criterions for both the language and the abstract
machine.

An application or tool cannot do or be everything of all users. This not
only justifies the diversity of editors, compilers, operating systems and
many other software systems, it also explains the presence of extensive
configuration options and macro or scripting languages in applications. My
own have applications contained a variety of little languages; most were
very simple, some were extensive. And most needs could have been solved by a
general purpose language with a special purpose library.

The Small language was designed as a flexible, general purpose language. The
tool set (compiler, abstract machine) were written so that they were easily
extensible and would run on different software/hardware architectures.

                                 <*>

Many years ago, I retyped the "Small C" compiler from Dr. Dobb's Journal, by
Ron Cain and James Hendrix. Having just grasped the basics of the C language,
working on the Small C compiler was a learning experience of its own. The
compiler, as published, generated code for a 8080 assembler. The first
modification I needed to make was to adapt it to the 8086 processor. Through
the years that I used it (to write low level system software) I expanded the
compiler with new features and fixed many details. Eventually, as I was moving
towards bigger applications in more conventional environments, the Small C
compiler was replaced by main-stream development environments.

In early 1998, I was looking for a scripting language for an animation
toolkit. Among the languages that I evaluated were Lua, bob, Scheme, rexx,
Java, ScriptEase and Forth. None of these languages covered my requirements
completely. I have always felt that the C language is a flexible and conveni-
ent language whose basics can be mastered in a week. While experimenting with
Quincy (from Al Stevens), I decided that a simplified C would probably be a
good fit. I dusted off Small C. This is the result.
2  o  Introduction

Small is a descendent of the original Small C, which at its turn was a subset
of C. The most fundamental changes that I did were the removal of the type
system and the substitution of pointers by references. The motivations
to adapt the C language to (yet another) tiny language are best discussed
elsewhere (see the rationale in appendix A), but by scrapping the type system
and the support for pointers, I could hardly call my language a "subset of
C" or a "C dialect". Therefore, I stripped off the "C" from the title and
kept the name "Small".

I am indebted to Ron Cain and James Hendrix (and more recently, Andy Yuen),
and to Dr. Dobb's Journal to get this ball rolling. Although I must have
touched nearly every line of the original code multiple times, the Small C
origins are still clearly visible.

                                 <*>

This booklet tries to unite two books:
* a manual for the Small compiler and the abstract machine that I wrote;
* a definition of the Small language, independent of the current implementa-
  tion.

These goals reflect the two main parts of the booklet entitled: "Small:
the language" and "Small: the compiler". The third part of the booklet,
"Appendices", provides relevant supplementary information and a rationale
for the design.
                                                               o  3

                         Small: the language

******************************************************************************
------------------------------------------------------------------------------

Small is a simple programming language with a syntax reminiscent to the "C"
programming language. A Small program consists of a set of functions and a
set of variables. The variables are data objects and the functions contain
instructions (called "statements") that operate on the data objects or that
perform tasks.

The first program in almost any computer language is one that prints a simple
string; printing "Hello world" is a classic example. In Small, the program
would look like:

    --------------------------------------------------------------------------
    #include <console>

    main()
       print("Hello world^n");
    --------------------------------------------------------------------------

Small separates the language from the function library. Since Small is
designed to be an extension language for applications, the function set that a
Small program has at its disposal depends on the implementation. It also means
that the Small language has no intrinsic knowledge of any function; a program
must declare every function that it uses. In this first example, the print
function must be declared, either by writing the definition (the function's
prototype) somewhere near the top of the source file, or by including a text
file that contains the required definition (along, perhaps, with definitions
of constants and of other functions). The "Hello world" example uses the
latter approach, as its first line exhibits.

A stand-alone Small program starts execution with function main. Here, the
function main contains only a single instruction, which is typed at the line
below the function head itself. Line breaks and indenting are insignificant;
the invocation of the function print could equally well be on the same line as
the head of function main.

The arguments of a function are always enclosed in parentheses. If a function
does not have any arguments, like function main, the opening and closing
parentheses are still present. The single argument of the print function is a
4  o  Small: the language


string (see page 23), which must be enclosed in double quotes. The characters
"^n" near the end of the string form a control character, in this case they
indicate a "newline" symbol. When print encounters the newline control
character, it advances the cursor to the first column of the next line. A list
of control characters is at page 22.

Every statement, with an exception of the compound statement (see page 33),
ends with a semicolon. The definition of a function (like that of the function
main) is not a statement. The execution (invocation) of a function is a
statement.

This first example also highlights several differences between Small and the C
language:
* the filename for the #include directive usually does not require a specific
  extension;
* when the body of a function is a single instruction, the braces (for a
  compound instruction) are optional;
* "escape characters" are called "control characters" in Small, and they
  start with a caret ("^") rather than a backslash ("\"), but see also
  page 38 or page 49 to change this special character.

Fundamental elements of most programs are calculations, decisions (conditional
execution), iterations (loops) and variables to store input data, output data
and intermediate results. The next program example illustrates many of these
concepts. The program calculates the greatest common divisor of two values
using an algorithm invented by Euclides.

    --------------------------------------------------------------------------
    /* greatest common divisor of two values, using the Euclidian algorithm */
    #include <console>

    main()
       {
       print("Input two values^n");
       new a = getvalue();
       new b = getvalue();
       while (a != b)
          if (a > b)
              a = a - b;
          else
              b = b - a;
       printf("The greatest common divisor is %d^n", a);
       }
    --------------------------------------------------------------------------
                                              Small: the language  o  5


When the body of a function contains more than one statement, these statements
must be embodied in braces (the "{" and "}" characters). This groups the
instructions to a single compound statement (page 33). The notion of grouping
statements in a compound statement applies as well to the bodies of if--else
and loop instructions.

The new keyword creates a variable. The name of the variable follows new. It
is common, but not imperative, to assign a value to the variable already
at the moment of its creation. The getvalue function (also part of the
"console" function set) reads in a value from the keyboard and returns
the result. Note that Small is a typeless language, all variables are numeric
cells that can hold a signed integral value. Data declarations are covered in
more detail starting at page 8.

Loop instructions, like while, repeat a single instruction as long as the
loop condition, the expression between parentheses, is "true" (page 36). To
execute multiple instructions in a loop, again, requires one to group these
in a compound statement. The if--else instruction has one instruction for the
"true" clause and one for the "false" clause (page 35).

Next to simple variables with a size of a single cells, Small supports arrays
and symbolic constants, as exemplified in the program below. It displays a
series of prime numbers using the well known "sieve of Eratosthenes".

    --------------------------------------------------------------------------
    /* Print all primes below 100, using a "Sieve of Eratosthenes" algorithm*/
    #include <console>

    main()
       {
       const max_primes = 100;
       new series[max_primes] = { true, ... };

       for (new i = 2; i < max_primes; ++i)
          if (series[i])
              {
              printf("%d ", i);
6  o  Small: the language

              /* filter all multiples of this "prime" from the list */
              for (new j = 2 * i; j < max_primes; j += i)
                 series[j] = false;
              }
       }
    --------------------------------------------------------------------------

Like simple variables, arrays may be initialized upon creation. Small offers
a convenient shorthand to initialize all elements to a fixed value, see page
9 for details. The symbols true and false are predefined constants (see page
24).

When a simple variable, like the variables i and j in the primes sieve
example, is declared in the first expression of a for loop, the variable
is valid only inside the loop. Variable declaration has its own rules; it is
not a statement (although it looks like one). One of those rules is that the
first expression of a for loop may contain a variable declaration (page 34).

Larger programs separate tasks and operations into functions. Using functions
increases the modularity of programs and functions, when well written, are
portable to other programs. The following example implements a function to
calculate numbers from the Fibonacci series.

The Fibonacci sequence was discovered by Leonardo "Fibonacci" of Pisa, an
Italian mathematician of the 13th century---whose greatest achievement was
popularizing for the Western world the Hindu-Arabic numerals. The Fibonacci
numbers describe a surprising variety of natural phenomena. For example,
the two or three sets of spirals in pineapples, pine cones and sunflowers
usually have consecutive Fibonacci numbers between 5 and 89 as their number of
spirals. The numbers that occur naturally in branching patterns (e.g. that of
plants) are indeed Fibonacci numbers. Finally, although the Fibonacci sequence
is not a geometric sequence, the further the sequence is extended, the more
closely the ratio between successive terms approaches the golden ratio, of
1.6188...that appears so often in art and architecture.

The assert instruction at the top of the fibonacci function deserves explicit
mention; it guards against "impossible" or invalid conditions (see page 33).

    --------------------------------------------------------------------------
    /* Calculation of Fibonacci numbers by iteration */
    #include <console>
                                              Small: the language  o  7


    fibonacci(n)
       {
       assert n>0;

       new a = 0, b = 1;
       for (new i = 2; i < n; i++)
          {
          new c = a + b;
          a = b;
          b = c;
          }
       return a + b;
       }

    main()
       {
       print("Enter a value: ");
       new v = getvalue();
       printf("The value of Fibonacci number %d is %d^n",
             v, fibonacci(v) );
       }
    --------------------------------------------------------------------------

If you now the C programming language, you will have seen many concepts that
you are familiar with, and a few new ones. If you don't know C, the pace
of this introduction has probably been quite high. Whether you are new to C
or experienced in C, I encourage you to read the following pages carefully.
This booklet attempts to be both an informal introduction and a (more formal)
language specification at the same time, perhaps succeeding at neither. Since
it is also the only book on Small, the focus of this booklet is on being
accurate and complete, rather than being easy to grasp.

The double nature of this section of the booklet shows in the order at which
it presents the subjects. The larger conceptual parts of the language,
variables and functions, are covered first. The operators, the statements
and general syntax rules follow later; not that they are less important, but
they are easier to learn, to look up, or to take for granted.
8  o  Data and declarations

Data and declarations

Small is a typeless language. All data elements are of type "cell", and
a cell can hold an integral number. The size of a cell (in bytes) is system
dependent (usually, a cell is 32-bits).

A new variable is declared with the keyword new. A simple variable declaration
creates a variable that occupies one "cell" of data memory. Unless it is
explicitly initialized, the value of the new variable is zero.

A variable declaration may occur:
* at any position where a statement would be valid (local variables);
* at any position where a function prototype or a function definition would be
  valid (global variables);
* in the first expression of a for loop instruction.

Local declarations
      A local declaration appears inside a compound statement. A local
      variable can only be accessed from within the compound statement, and
      from nested compound statements. A declaration in the first expression
      of a for loop instruction is also a local declaration.

Global declarations
      A global declaration appears outside a function and a global vari-
      able is accessible to any function. Global data objects can only be
      initialized with static expressions.


Arrays

The syntax name[constant] declares name to be an array of "constant" ele-
ments, where each element is a single cell. If there is no value between the
brackets, the number of elements is set equal to the number of initiallers.


Initialization

Data objects can be initialized at their declaration. The initialler of a
global data objects must be a constant (see "Constants" on page 22). Arrays
must also be initialized with constants.

Uninitialized data defaults to zero.
                                            Data and declarations  o  9

Examples:
    --------------------------------------------------------------------------
    new i = 1;
    new j;              /* j is zero */
    new k = 'a';        /* k holds the character code for the letter 'a' */

    new a[] = {1,4,9,16,25};            /* a has 5 elements */
    new s1[20] = {'a','b'};             /* the other 18 elements are 0 */

    new s2[] = "Hello world...";        /* a unpacked string */
    --------------------------------------------------------------------------

Examples of invalid declarations:
    --------------------------------------------------------------------------
    new c[3] = 4;               /* an array cannot be set to a value */
    new i = "Good-bye";         /* i should be an array for this initialler */
    new q[];                    /* unknown size of array */
    new p[2] = { i + j, k - 3 };    /* array initiallers must be constants */
    --------------------------------------------------------------------------



Progressive initiallers for arrays

The ellipsis operator continues the progression of the initialisation con-
stants for an array, based on the last two initialized elements. The ellipsis
operator (three dots, or "...") initializes the array up to its declared
size.

Examples:
    --------------------------------------------------------------------------
    new a[10] = { 1, ... };  /* fills all ten elements of the array with 1s */
    new b[10] = { 1, 2, ... };        /* sets: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10*/
    new c[8] = { 1, 2, 40, 50, ... }; /* sets: 1, 2, 40, 50, 60, 70, 80, 90 */
    new d[10] = { 10, 9, ... };       /* sets: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1*/
    --------------------------------------------------------------------------
10  o  Data and declarations

Tagnames

A tagname is a label that denotes the objective of ---or the meaning of--- a
variable, a constant or a function result. Tagnames are entirely optional,
their only purpose is to allow a stronger compile-time error checking of
operands in expressions, of function arguments and of array indices.

Tagnames should not be confused with variable types in C and other languages.
A tagged variable is still a cell, which holds an integral number.
* a type specifies the memory layout and range of variables and function
  results
* a tagname labels the purpose of variables, constants and function results

A tagname consists of a symbol name followed by a colon; it has the same
syntax as a label (see also page 33). A tagname precedes the symbol name of a
variable, constant or function. In an assignment, only the right hand of the
"=" sign may be tagged.

Examples of valid tagged variable and constant definitions are:
    --------------------------------------------------------------------------
    new bool:flag = true;      /* "flag" can only hold "true" or "false" */

    const error:success = 0;
    const error:fatal= 1;
    const error:nonfatal = 2;

    error:errno = fatal;
    --------------------------------------------------------------------------

The sequence of the constants success, fatal and nonfatal could more conveni-
ently be declared using an enum instruction, as illustrated below. The enum
instruction is covered in more detail at page 24. The enumeration instruction
below creates four constants, success, fatal, nonfatal and error, all with the
tagname error.
    --------------------------------------------------------------------------
    enum error {
       success,
       fatal,
       nonfatal,
    }
    --------------------------------------------------------------------------
                                                     Functions  o  11

A typical use of "tagged" enum's is in conjunction with arrays. If every
field of an array has a distinct purpose, you can use a tagged enum to declare
the size of an array and to add tagname checking to the array usage in a
single step:
    --------------------------------------------------------------------------
    enum rectangle {
       left,
       top,
       right,
       bottom
    }

    new my_rect[rectangle];        /* array is declared as having 4 cells */

    my_rect[left] = 10;
    my_rect[top] = 5;
    my_rect[right] = 30;
    my_rect[bottom] = 12;

    for (new i = 0; rectangle:i < rectangle; ++i)
       my_rect[rectangle:i] *= 2;
    --------------------------------------------------------------------------

After the above declaration, you can access the second field of my_rect with
my_rect[top], but saying my_rect[1] will give a parser diagnostic (a warning
or error message). A tagname override (or a tagname cast) adjusts a function,
constant or variable to the desired tagname. The for loop at the last two
lines in the preceding example depicts this: the loop variable i is a plain,
untagged cell, an it must be cast to the tagname rectangle before as an index
in the array my_rect. Note that the enum construct has created both a constant
and a tagname with the name "rectangle".



Functions

A function declaration specifies the name of the function and, between
parentheses, its formal parameters. A function may also return a value. A
function declaration must appear on a global level (i.e. outside any other
functions) and is globally accessible.

If a semicolon follows the function declaration (rather than a statement),
the declaration denotes a function prototype; that is, a forward declaration.
12  o  Functions

The full declaration of the function, with a non-empty body, is implemented
elsewhere.

Function prototypes are needed when calling functions prior to their defini-
tion or when calling "native" functions (page 20).

The return statement sets the function result. For example, function sum()
(see below) has as result the value of both its arguments added together. The
return expression is optional for a function, but one cannot use the value of
a function that does not return a value.
    --------------------------------------------------------------------------
    sum(a, b)
       return a + b;
    --------------------------------------------------------------------------

Another example of a complete definition of the function leapyear() (which
returns true for a leap year and false for a non-leap year):
    --------------------------------------------------------------------------
    leapyear(y)
       return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
    --------------------------------------------------------------------------

The logical and arithmetic operators used in the leapyear example are covered
on page 30 and page 26 respectively.

Usually, a function contains local variable declarations and consists of a
compound statement:
    --------------------------------------------------------------------------
    power(x, y)
       {
       /* returns x raised to the power of y */
       new r = 1;
       for (new i = 0; i < y; i++)
          r *= x;
       return r;
       }
    --------------------------------------------------------------------------
                                                     Functions  o  13

Function arguments (call-by-value versus call-by-reference)

The "faculty" function in the next program has one parameter which it uses
in a loop to calculate the faculty of that number. What deserves attention is
that the function modifies its argument.

    --------------------------------------------------------------------------
    /* Calculation of the faculty of a value */
    #include <console>

    faculty(n)
       {
       assert n>=0;

       new result = 1;
       while (n > 0)
          result *= n--;

       return result;
       }

    main()
       {
       print("Enter a value: ");
       new v = getvalue();
       new f = faculty(v);
       printf("The faculty of %d is %d^n", v, f);
       }
    --------------------------------------------------------------------------

Whatever (positive) value that "n" had at the entry of the loop, "n"
will be zero at the end of the loop. In the case of the faculty function,
the parameter is passed "by value", so the change of "n" is local to
the faculty function. In other words, function main passes "v" as input to
function faculty, but upon return of faculty, "v" still has the same value
as before the function call.

Arguments that occupy a single cell can be passed by value or by reference.
The default is "pass by value". To create a function argument that is passed
by reference, prefix the argument name with the character &.

Example:
14  o  Functions

    --------------------------------------------------------------------------
    swap(&a, &b)
       {
       new temp = b;
       b = a;
       a = temp;
       }
    --------------------------------------------------------------------------

To pass an array to a function, append a pair of brackets to the argument
name. You may optionally indicate the size of the array; doing so improves
error checking of the parser.

Example:
    --------------------------------------------------------------------------
    addvector(a[], b[], size)
       {
       for (new i = 0; i < size; i++)
          a[i] += b[i];
       }
    --------------------------------------------------------------------------

Arrays are always passed by reference. To pass an array of literals to a
function, use the same syntax as for array initiallers: a literal string or
the series of array indices enclosed in braces (see page 23).

The following snippet calls addvector to add five to every element of the
array "vect":
    --------------------------------------------------------------------------
    new vect[3] = { 1, 2, 3 };

    addvector(vect, {5, 5, 5}, 3);

    /* vect[] now holds the values 6, 7 and 8 */
    --------------------------------------------------------------------------

The invocation of function print with the string "Hello world^n" in the first
ubiquitous program (page 3) is another example of passing a literal array to
a function.
                                                     Functions  o  15

Named parameters versus positional parameters

In the previous examples, the order of parameters of a function call was
important, because each parameter is copied to the function argument with the
same sequential position. For example, with the function weekday (which uses
Zeller's congruence algorithm) defined as below, you call weekday(12,31,1999);
to get the week day of the last day of this century.
    --------------------------------------------------------------------------
    weekday(month, day, year)
       {
       /* returns the day of the week: 0=Saturday, 1=Sunday, etc. */
       if (month <= 2)
          month += 12, --year;
       new j = year % 100;
       new e = year / 100;
       return (day + (month+1)*26/10 + j + j/4 + e/4 - 2*e) % 7;
       }
    --------------------------------------------------------------------------

Date formats vary according to culture and nation. While the format
month/day/year is common in the United States of America, European countries
often use the day/month/year format, and technical publications sometimes
standardize on the year/month/day format. In other words, no order of
arguments in the weekday function is "logical" or "conventional". That being
the case, the alternative way to pass parameters to a function is to use
"named parameters", as in the next examples (the three function calls are
equivalent):

    --------------------------------------------------------------------------
     new wkday1 = weekday( .month = 12, .day = 31, .year = 1999);

     new wkday2 = weekday( .day = 31, .month = 12, .year = 1999);

     new wkday3 = weekday( .year = 1999, .month = 12, .day = 31);
    --------------------------------------------------------------------------

With named parameters, a period (".") precedes the name of the function
argument. The function argument can be set to any expression that is valid for
the argument. The equal sign ("=") does in the case of a named parameter not
indicate an assignment; rather it links the expression that follows the equal
sign to one of the function arguments.
16  o  Functions

Default values of function arguments

A function argument may have a default value. When the function call specifies
an argument placeholder instead of a valid argument, the default value
applies. The argument placeholder is the underscore character (_). The
argument placeholder is only valid for function arguments that have a default
value.

If the rightmost argument placeholder may simply be stripped from the function
argument list. For example, if function increment() is defined as:
    --------------------------------------------------------------------------
    increment(&value, incr=1) value += incr;
    --------------------------------------------------------------------------

the following function calls are all equivalent:
    --------------------------------------------------------------------------
    increment(a);
    increment(a, _);
    increment(a, 1);
    --------------------------------------------------------------------------

Default argument values for passed-by-reference arguments are useful to make
the input argument optional. For example, if the function divmod() is designed
to return both the quotient and the remainder of a division operation through
its arguments, default values make these arguments optional:
    --------------------------------------------------------------------------
    divmod(a, b, &quotient=0, &remainder=0)
       {
       quotient = a / b;
       remainder = a % b;
       }
    --------------------------------------------------------------------------

With the preceding definition of function divmod, the following function calls
are now all valid:
    --------------------------------------------------------------------------
    new p, q;

    divmod(10, 3, p, q);
    divmod(10, 3, p, _);
    divmod(10, 3, _, q);
    divmod(10, 3, p);
    --------------------------------------------------------------------------
                                                     Functions  o  17

Default arguments for array arguments are often convenient to set a default
string or prompt to a function that receives a string argument.


Variable arguments

A function that takes a variable number of arguments, uses the "ellipsis"
operator ("...") in the function header to denote the position of the first
variable argument. The function can access the arguments with the predefined
functions numargs, getarg and setarg. (see page 39).

Function sum returns the summation of all of its parameters. It uses a
variable length parameter list.
    --------------------------------------------------------------------------
    sum(...)
       {
       new result = 0;
       for (new i = 0; i < numargs(); ++i)
          result += getarg(i);
       return result;
       }
    --------------------------------------------------------------------------

This function could be used in:
    --------------------------------------------------------------------------
    new v = sum(1, 2, 3, 4, 5);
    --------------------------------------------------------------------------

A tagname (page 10) may precede the ellipsis to enforce that all subsequent
parameters have the same tag, but otherwise there is no error checking with a
variable argument list and this feature should therefore be used with caution.


Coercion rules

If the function argument, as per the function definition (or prototype), is a
value, the caller can pass as a parameter to the function:
* a value, which is passed by value;
* a reference, whose dereferenced value is passed;
* an (indexed) array element, which is a value.

If the function argument is a reference, the caller can pass to the function:
* a value, whose address is passed;
18  o  Functions

* a reference, which is passed by value because it has the type that the
  function expects;
* an array, whose starting address is passed;
* an (indexed) array element, which is a value.

If the function argument is an array, the caller can pass to the function:
* an array, whose starting address is passed;
* an (indexed) array element, in which case the address of the element is
  passed.


Recursion

A faculty example function earlier in this chapter (page 13) used a simple
loop. An example function that calculated a number from the Fibonacci series
also used a loop and an extra variable to do the trick (page 6). These two
functions are the most popular routines to illustrate recursive functions, so
by implementing these as iterative procedures, you might be inclined to think
that Small does not support recursion.

Well, Small does support recursion, but I think that both the calculation
of faculties and of Fibonacci numbers are good examples of when not to
use recursion. Faculty is easier to understand with a loop as it is with
recursion. Solving Fibonacci numbers by recursion indeed simplifies the
problem, but at the cost of being extremely inefficient: the recursive
Fibonacci calculates the same values over and over again.

The program below is an implementation of the famous "Towers of Hanoi" game
in a recursive function:
    --------------------------------------------------------------------------
    #include <console>

    move(from, to, spare, numdisks)
       {
       if (numdisks > 1)
          move(from, spare, to, numdisks-1);
       printf("Move disk from pillar %d to pillar %d^n", from, to);
       if (numdisks > 1)
          move(spare, to, from, numdisks-1);
       }

    main()
       {
                                                     Functions  o  19

       print("How many disks: ");
       new disks = getvalue();
       move(1, 3, 2, disks);
       }
    --------------------------------------------------------------------------



Public functions, function main()

A stand-alone program must have the function main(). This function is the
starting point of the program. The function main() may not have arguments.

A function library need not to have a main() function, but it must have
it either a main function, or at least one public function. Function main
is the primary entry point into the compiled program; the public functions
are alternative entry points to the program. The virtual machine can start
execution with one of the public functions. A function library may have a main
function to perform one-time initialization at startup.

To make a function public, prefix the function name with the keyword pub-
lic. For example, a text editor may call the public function "onkey" for
every key that the user typed in, so that the user can change (or reject)
keystrokes. The onkey function below would replace every "~" character (code
126 in the ISO Latin-1 character set) by the "hard space" code in the ANSI
character table:
    --------------------------------------------------------------------------
    public onkey(keycode)
       {
       if (key=='~')
          return 160;     /* replace ~ by hard space (code 160 in Latin-1) */
       else
          return key;     /* leave other keys unaltered */
       }
    --------------------------------------------------------------------------

Functions whose name starts with the "@" symbol are also public. So an
alternative way to write the public function onkey function is:
    --------------------------------------------------------------------------
    @onkey(keycode)
       return key=='~' ? 160 : key;
    --------------------------------------------------------------------------
20  o  Functions

Native functions

A Small program can call application-specific functions through a "native
function". The native function must be declared in the small program by means
of a prototype. The function name must be preceded by the keyword native.

Examples:
    --------------------------------------------------------------------------
    native getparam(a[],b[],size);

    native multiply_matrix(a[],b[],size);

    native openfile(name[]);
    --------------------------------------------------------------------------
                                                 General syntax  o  21

General syntax

Format
      Identifiers, numbers and tokens are separated by spaces, tabs, carriage
      returns and "form feeds". Series of one or more of these separators
      are called white space.

Comments
      Text between the tokens /* and */ (both tokens may be at the same line
      or at different lines) and text behind // (up to the end of the line)
      is a programming comment. The compiler treats a comment as white space.
      Comments may not be nested.

Identifiers
      Names of variables, functions and constants. Identifiers consist of
      the characters a...z, A...Z, 0...9, _ or @; the first character may
      not be a digit. The characters @ and _ by themselves are not valid
      identifiers, i.e. "_Up" is a valid identifier, but "_" is not.

      Small is case sensitive.

      A parser may truncate an identifier after a maximum length. The number
      of significant characters is implementation defined, but should be at
      least 16 characters.

Reserved words (keywords)
       Statements Operators Directives  Other

       assert     char      #assert     const
       break      defined   #else       enum
       case       sizeof    #emit       native
       continue             #endif      new
       default              #endinput   public
       do                   #if
       else                 #include
       exit
       for
       goto
       if
       return
       switch
       while
22  o  General syntax

      Next to reserved words, Small also has knows several predefined
      constants (page 24), you cannot use the symbol names of the predefined
      constants for variable or function names.

Constants (literals)
      Numeric constants
            binary
                  0b followed by a series of the digits 0 and 1.
            decimal
                  a series of digits between 0 and 9.
            hexadecimal
                  0x followed by a series of digits between 0 and 9 and the
                  letters a to f (lower case letters only).

      Character constants
            A single ASCII character surrounded by single quotes is a
            character constant (for example: 'a', '7', '$'). Character
            constants are assumed to be numeric constants.

            Control characters

            '^a'        Audible alarm (beep)
            '^b'        Backspace
            '^f'        Formfeed
            '^n'        Newline
            '^r'        Carriage Return
            '^t'        Horizontal tab
            '^v'        Vertical tab
            '^^'        ^the caret itself
            '^''     '  single quote
            '^"'     "  double quote
            '^ddd;'     character code with decimal code "ddd"

            The semicolon after the ^ddd; code is optional. Its purpose is
            to give the control character sequence an explicit termination
            symbol when it is used in a string constant.

            The caret ("^") is the default control character. You can
            set a different control character with the #pragma ctrlchar
            directive (page 38).
                                                 General syntax  o  23

      String constants
            String constants are assumed to be arrays with a size that is
            sufficient to hold all characters plus a terminating 0. Each
            string is stored at a unique position in memory; there is no
            elimination of duplicate strings.

            An unpacked string is a series of zero or more ASCII characters
            surrounded by double quotes. Each array element contains a
            single character.

            unpacked string constant:

                "the quick brown fox..."

            A packed string literal follows the syntax for an unpacked
            string, but a "!" precedes the first double quote.

            packed string constant:

                !"...packed and sacked the lazy dog"

            In the case of a packed string, the compiler packs as many
            characters in a cell as will fit. A character is not addressable
            as a single unit, instead each element of the array contains
            multiple characters. The first character in a "pack" occupies
            the highest bits of the array element. In environments that
            store memory words with the high byte at the lower address
            (Big Endian, or Motorola format), the individual characters
            are stored in the memory cells in the same order as they are in
            the string. A packed string ends with a zero character and the
            string is padded (with zero bytes) to a multiple of cells.

            Control characters may be used within strings.

      Array constants
            A series of numeric constants between braces is an array
            constant. Array constants can be used to initialize array
            variables with (see page 8) and they can be passed as function
            arguments (see page 13).

Symbolic constants
      A source file declares symbolic constants with the const and the enum
      instructions.
24  o  General syntax

      const identifier = constant expression ;
            Creates a symbolic constant with the value of the constant
            expression on the right hand of the assignment operator. The
            constant can be used at any place where a literal number is
            valid (expressions, array declarations, directives like #if,
            ...).

      enum name - constant list "
            The enum instruction creates a series of constants with incre-
            menting values. The constant list is a series of identifiers
            (page 21) separated by commas. Unless overruled, the first
            constant of an enum list has the value 0 and every subsequent
            constant has the value of its predecessor plus 1.

            Both the value of a constant and the increment value can be set
            by appending the value to the constant's identifier. To set a
            value, use

                  name = value
            in the constant list. To set the increment, use:

                  name : increment
            The increment value is reset to 1 after every constant symbol
            declaration in the constant list.

            The name token that follows the enum keyword is optional. If it
            is included, this name is used as the tagname for every symbol
            in the constant list. In addition, the enum command creates
            an extra constant with name for the constant name and tagname.
            See page 10 for examples of the enum constant declarations.
            The value of the last constant is the value of the last symbol
            in the constant list plus the increment value of that last
            constant.

            The symbols in the constant list may not be tagged.

      A symbolic constant that is defined locally, is valid throughout
      the block. A local symbolic constant may not have the same name as a
      variable (local or global), a function, or another constant (local or
      global).

Predefined constants
      false    0 (this constant is tagged as bool:)
                                        Operators and expressions  o  25

      true     1 (this constant is tagged as bool:)
      cellbits The size of a cell in bits; usually 32.
      cellmax  The largest valid positive value that a cell can hold;
               usually 2147483647.
      cellmin  The largest valid negative value that a cell can hold;
               usually -2147483648.
      charbits The size of a character in bits; 8 when using the ASCII or
               ISO Latin-1 characters sets and 16 when using the Unicode
               character set.
      charmax  The largest valid character value; 255 for 8-bit characters
               and 65535 for 16-bit characters.
      charmin  The smallest valid character value, currently set at zero
               (0).
      debug    One (1) if the compiler generates code for assertions and
               run-time bounds checking, zero (0) otherwise.

Tagnames
      A tagname consists of an identifier (page 21) followed by a colon.
      There may be no white space between the identifier and the colon.

Predefined tagnames
      bool     For "true/false" flags. The predefined constants true and
               false have this tagname.



Operators and expressions

Notational conventions

Some operators are only valid or behave differently with specific operands.
Therefore, operands are notated thus:
  e   any expression;
  v   any expression to which a value can be assigned (these expressions are
      also called lvalue expressions);
  a   an array
  f   a function.
26  o  Operators and expressions

Expressions

An expression consists of one or more operands with an operator. The operand
can be a variable, a constant or another expression. An expression followed by
a semicolon is a statement.

Examples of expressions:
    --------------------------------------------------------------------------
    v++
    f(a1, a2)
    v = (ia1 * ia2) / ia3
    --------------------------------------------------------------------------



Arithmetic
      +     e1 + e2
            Results in the addition of e1 and e2.


      -     e1 - e2
            Results in the subtraction of e1 and e2.

            -e
            Results in the arithmetic negation of a (two's complement).


      *     e1 * e2
            Results in the multiplication of e1 and e2.


      /     e1 / e2
            Results in the division of e1 by e2. The result is truncated
            to the nearest integral value that is less than or equal to the
            quotient. Both negative and positive values are rounded towards
            minus infinity.
                                        Operators and expressions  o  27

      %     e1 % e2
            Results in the modulus (remainder of the division) of e1 by e2.
            The modulus is always a positive value.

      ++    v++
            increments v by 1; results in the value of v before it is incre-
            mented.

            ++v
            increments v by 1; results in the value of v after it is incre-
            mented.

      --    v--
            decrements v by 1; results in the value of v before it is decre-
            mented.

            --v
            decrements v by 1; results in the value of v after it is decre-
            mented.


      Notes:The unary + is not defined in Small.
            The operators ++ and -- modify the operand. The operand must be
            an lvalue.


Bit manipulation
      ~     ~e
            results in the one's complement of e.


      >>    e1 >> e2
            results in the arithmetic shift to the right of e1 by e2 bits.
            The shift operation is signed: the leftmost bit of e1 is copied
            to vacant bits in the result.

      >>>   e1 >>> e2
            results in the logical shift to the right of e1 by e2 bits. The
            shift operation is unsigned: the vacant bits of the result are
            filled with zeros.
28  o  Operators and expressions

      <<    e1 << e2
            results in the value of e1 shifted to the left by e2 bits; the
            rightmost bits are set to zero. There is no distinction between
            an arithmetic and a logical left shift

      &     e1 & e2
            results in the bitwise logical "and" of e1 and e2.


      |     e1 | e2
            results in the bitwise logical "or" of e1 and e2.


      ^     e1 ^ e2
            results in the bitwise "exclusive or" of e1 and e2.


Assignment

The result of an assignment expression is the value of the left operand after
the assignment. The left operand may not be tagged (page 10).


      =     v = e
            assigns the value of e to v.


      Note: the following operators combine an assignment with an arithmetic
            or a bitwise operation; the result of the expression is the value
            of the left operand after the arithmetic or bitwise operation.

      +=    v += e
            increments v with a.
      -=    v -= e
            decrements v with e
                                        Operators and expressions  o  29

      *=    v *= e
            multiplies v with e
      /=    v /= e
            divides v by e.
      %=    v %= e
            assigns the remainder of the division of v by e to v.
      >>=   v >>= e
            shifts v arithmetically to the right by e bits.
      >>>=  v >>>= e
            shifts v logically to the right by e bits.
      <<=   v <<= e
            shifts v to the left by e bits.
      &=    v &= e
            applies a bitwise "and" to v and e and assigns the result to v.
      |=    v |= e
            applies a bitwise "or" to v and e and assigns the result to v.
      ^=    v ^= e
            applies a bitwise "exclusive or" to v and e and assigns the result to v.


Relational

A logical "false" is represented by an integer value of 0; a logical
"true" is represented by any value other than 0. Relational and Boolean
expressions result in either 0 or 1


      ==    e1 == e2
            results in a logical "true" if e1 is equal to e2.


      !=    e1 != e2
            results in a logical "true" if e1 differs from e2.


      <     e1 <e2
            results in a logical "true" if e1 is smaller than e2.


      <=    e1 <= e2
            results in a logical "true" if e1 is smaller than or equal to e2.
30  o  Operators and expressions

      >     e1 >e2
            results in a logical "true" if e1 is greater than e2.


      >=    e1 >= e2
            results in a logical "true" if e1 is greater than or equal to e2.



Boolean
      !     !e
            results to a logical "true" if e was logically "false".


      ||    e1 || e2
            results to a logical "true" if either e1 or e2 (or both) are
            logically "true". The expression e2 is only evaluated if e1 is
            logically "false".

      &&    e1 && e2
            results to a logical "true" if both e1 and e2 are logically
            "true". The expression e2 is only evaluated if e1 is logically
            "true".


Miscellaneous
      [ ]   a[e]
            array index: results to cell e from array a.


      { }   a{e}
            array index: results to character e from array a.


      ( )   f(e1,e2,...eN)
            results to the value returned by the function f. The function is
            called with the arguments e1, e2, ...eN. The order of evaluation
            of the arguments is undefined (an implementation may choose to
            evaluate function arguments in reversed order).


      ? :   e1 ? e2 : e3
                                        Operators and expressions  o  31

            results in either e2 or e3, depending on the value of e1. The
            conditional expression is a compound expression with a two part
            operator, ? and :. Expression e2 is evaluated if e1 is logically
            "true", e3 is evaluated if e1 is logically "false".

      :     tagname: e
            tagname override; the value of the expression e does not change,
            but its tagname changes. See page 10 for more information.

      ,     e1, e2
            results in e2, e1 is evaluated before e2. If used in function
            argument lists or a conditional expression, the comma expression
            must be surrounded by parentheses.

      defined
            returns the value 1 if the symbol is defined. The symbol may be a
            constant (page 22), or a global or local variable.

      sizeof
            returns the size in cells of the specified variable.

      char  e char
            returns the number of cells that are needed to hold a packed
            array of e characters.



Operator precedence

In the table beneath, operators with equal precedence are grouped. The top of
the table lists the operator group with the highest precedence.

If the expression evaluation order is not explicitly established by par-
entheses, it is determined by the association rules. For example: a*b/c is
equivalent with (a*b)/c because of the left-to-right association, and a=b=c is
equivalent with a=(b=c).
32  o  Operators and expressions


--------------------------------------------------------------------
   ()         function call                           left-to-right
   []         array index (cell)
   {}         array index (character)
--------------------------------------------------------------------
   !          logical not                             right-to-left
   ~          one's complement
   -          two's complement (unary minus)
   ++         increment
   --         decrement
   :          tagname override
   char       convert number of packed characters to cells
   defined    symbol definition status
   sizeof     symbol size in cells
--------------------------------------------------------------------
   *          multiplication                          left-to-right
   /          division
   %          modulus
--------------------------------------------------------------------
   +          addition                                left-to-right
   -          subtraction
--------------------------------------------------------------------
   >>         arithmetic shift right                  left-to-right
   >>>        logical shift right
   <<         shift left
--------------------------------------------------------------------
   <          smaller than                            left-to-right
   <=         smaller than or equal to
   >          greater than
   >=         greater than or equal to
--------------------------------------------------------------------
   ==         equality                                left-to-right
   !=         inequality
--------------------------------------------------------------------
   &          bitwise and                             left-to-right
   ^          bitwise exclusive or                    left-to-right
   |          bitwise or                              left-to-right
--------------------------------------------------------------------
   &&         logical and                             left-to-right
--------------------------------------------------------------------
   ||         logical or                              left-to-right
--------------------------------------------------------------------
   ? :        conditional                             right-to-left
--------------------------------------------------------------------
   =          assignment                              right-to-left
   *= /= %= += -= >>= >>>= <<= &= ^= |=
--------------------------------------------------------------------
   ,          comma                                   left-to-right
--------------------------------------------------------------------
                                                    Statements  o  33

Statements

A statement may take one or more lines, whereas one line may contain two or
more statements. With the exception of a compound statement, every statement
ends with a semicolon.

Control flow statements (if, if--else, for, while, do--while and switch) may
be nested.

Statement label
      A label consists of an identifier (page 21) followed by a semicolon
      (:). A label is a "jump target" of the goto statement.

      Each statement may be preceded by a label. There must be a statement
      after the label; an empty statement is allowed.

      The scope of a label is the function in which it is declared (a goto
      statement cannot therefore jump out off the current function to another
      function).

Compound statement
      A compound statement is a series of zero or more statements surrounded
      by braces ({ and }). The final brace (}) should not be followed by
      a semicolon. Any statement may be replaced by a compound statement.
      A compound statement is also called a block. A compound statement
      with zero statements is a special case, and it is called an "empty
      statement".

Expression statement
      Any expression becomes a statement when a semicolon (;) is appended to
      it.

Empty statement
      An empty statement performs no operation and consists of a compound
      block with zero statements; that is, it consists of the tokens "{ }".
      Empty statements are used in control flow statements if there is no
      action (e.g. while (!iskey()) {}) or when defining a label just before
      the closing brace of a compound statement. An empty statement does not
      end with a semicolon.

assert expression
      Aborts the program with a run-time error if the expression evaluates to
      logically "false".
34  o  Statements

break
      Terminates and exits the smallest enclosing do, for or while statement
      from any point within the loop other than the logical end. The break
      statement moves program control to the next statement outside the loop.

continue
      Terminates the current iteration of the smallest enclosing do, for or
      while statement and moves program control to the condition part of the
      loop. If the looping statement is a for statement, control moves to the
      third expression in the for statement (and thereafter to the second
      expression).

do statement while ( expression )
      Executes a statement before the condition part (the while clause) is
      evaluated. The statement is repeated while the condition is logically
      "true". The statement is at least executed once.

exit expression
      Abort the program. The expression is optional. If included, it returns
      the expression value to the operating system or to the higher level
      shell. The significance and purpose of exit codes is implementation
      defined.

for ( expression 1 ; expression 2 ; expression 3 ) statement
      All three expressions are optional.

      expressionE1valuated only once, and before entering the loop. This
                expression may be used to initialize a variable. This
                expression may also hold a variable declaration, using
                the new syntax (see page 8). A variable declared in this
                expression exists only in the for loop.

      expressionE2valuated before each iteration of the loop and ends the
                loop if the expression results to logically "false".
                If omitted, the result of expression 2 is assumed to be
                logically "true".

      expressionE3valuated after each execution of the statement. Program
                control moves from expression 3 to expression 2 for the
                next (conditional) iteration of the loop.

      The statement for( ; ; ) is equivalent with while (true).
                                                    Statements  o  35

goto label
      Moves program control (unconditionally) to the statement that follows
      the specified label. The label must be within the same function as the
      goto statement (a goto statement cannot jump out of a function).

if ( expression ) statement 1 else statement 2
      Executes statement 1 if the expression results to logically "true".
      The else clause of the if statement is optional. If the expression
      results to logically "false" and an else clause exists, the statement
      associated with the else clause (statement 2) executes.

      When if statements are nested and else clauses are present, a given
      else is associated with the closest preceding if statement in the same
      block.

return expression
      Terminates the current function and moves program control to the
      statement following the calling statement.

      The expression is optional, but if it is included the value of the
      expression is returned as the function result.

switch ( expression ) - case list "
      Transfers control to different statements within the switch body
      depending on the value of the switch expression. The body of the switch
      statement is a compound statement, which contains a series of "case
      clauses".

      Each "case clause" starts with the keyword case followed by a
      constant list and one statement. The constant list is a series of
      expressions, separated by comma's, that each evaluates to a constant
      value. The constant list ends with a colon.

      The switch statement moves control to a "case clause" if the value
      of one of the expressions in the constant list is equal to the switch
      expression result.

      The "default clause" consists of the keyword default and a colon. The
      default clause is optional, but if it is included, it must be the last
      clause in the switch body. The switch statement moves control to the
      "default clause" is executed if none of the case clauses match the
      expression result.
36  o  Directives

      Example:

      switch (weekday(12,31,1999))
          {
          case 1, 7:         /* 1 == Sunday, 7 == Saturday */
             print("weekend");
          case 2:
             print("Monday");
          case 3:
             print("Tuesday");
          case 4:
             print("Wednesday");
          case 5:
             print("Thursday");
          case 6:
             print("Friday");
          default:
             print("invalid week day");
          }

while ( expression ) statement
      Evaluates the expression and executes the statement if the expression
      result yields logically "true". After the statement has executed,
      program control returns to the expression again. The statement is thus
      executed while the expression is true.



Directives

All directives must appear first on a line (they may be preceded by white
space, but not by any other characters). All directives start with the
character # and the complete instruction may not span more than one line.

#assert constant expression
      Issues a compile time error if the supplied constant expression eval-
      uates to zero. The #assert directive is most useful to guard against
      implementation defined constructs on which a program may depend, such
      as the cell size in bits, or the number of packed characters per cell.
      See also "Predefined constants" on page 24.
                                                    Directives  o  37

#emit opcode, parameters
      The #emit directive serves as an inline assembler. It is currently used
      only for testing the abstract machine.

#endinput
      Closes the current file and thereby ignores all the text below the
      #endinput directive.

#include "filename" or filename
      Inserts the contents of the specified file at the current position
      within the current file. A filename between double quotes refers to
      a local file, and filename between angle brackets refers to a system
      file. A Small parser (compiler or interpreter) may treat system files
      in a special way; for example, a system file need not be a physical
      file for a Small parser that "magically" knows the contents of each
      system file.

      The proposed default extension of include files is ".INC".

#if constant expression, #else, #endif
      Portions of a program may be parsed or be ignored depending on certain
      conditions. The Small parser (compiler or interpreter) generates code
      only for those portions for which the condition is true.

      The directive #if must be followed by a constant expression. To check
      whether a variable or constant is defined, use the defined operator.

      The #else directive reverses the parsing state. If the parser ignored
      lines up to the directive, it starts parsing and if it parsed lines, it
      stops parsing. There should only be one #else associated with each #if,
      but a Small parser need not impose this restriction.

      The #endif directive terminates a program portion that is parsed
      conditionally. Conditional directives can be nested and each #if
      directive must be ended by an #endif directive.

#pragma extra information
      A pragma is a hook for a parser to specify additional settings, such as
      warning levels or extra capabilities. Common pragmas are:
38  o  Directives

      #pragma dynamic value
            Sets the size of the memory block for dynamic data (the stack
            and the heap) to the value specified by the expression. The
            default size of the dynamic data block is implementation
            defined. An implementation may also choose to grow the block on
            an as-needed basis. See appendix C for details.

      #pragma ctrlchar character
            Defines the character to use to indicate a "control character"
            (see page 22). By default, the control character is "^".

            For example
            #pragma ctrlchar '$'
                                        Proposed function library  o  39

Proposed function library

Since Small is targeted as an application extension language, most of the
functions that are accessible to Small programs will be specific to the
application. Nevertheless, a small set of functions may prove useful to many
environments.


Core functions

The "core" module consists of a set of functions that support the language
itself. Several of the functions are needed to pull arguments out of a
variable argument list (see page 17).

Since there are only few functions, I have opted to arrange them per category,
rather than alphabetically.

heapspace()
      Return the free space on the heap. The stack and the heap occupy a
      shared memory area.

funcidx(name[])
      Returns the index of the named public function. An application runs a
      public function from the script by passing the public function's index
      to amx_Exec() (see page 65). With this function, the script can query
      the index of a public function, and thereby return the "next function
      to call" to the application.

      If no public function with the given name exists, funcidx returns - 1.

                                <*>

numargs()
      Return the number of arguments passed to a function; numargs() is
      useful inside functions with a variable argument list.

getarg(arg, index=0)
      Retrieve an argument from a variable argument list. When the argument
      is an array, the index parameter specifies the index into the array.
      The return value is the retrieved argument.
40  o  Proposed function library

setarg(arg, index=0, value)
      Set the value of an argument from a variable argument list. When the
      argument is an array, the index parameter specifies the index into
      the array. The return value is false if the argument or the index are
      invalid, and true on success.

                                <*>

strlen(string[])
      Returns the length of a string, either packed or unpacked, as the
      number of characters (not the number of cells).

strpack(dest[], source[])
      Copy a string from source to dest where the destination string will
      be in packed format. The source string may either be a packed or an
      unpacked string.

strunpack(dest[], source[])
      Copy a string from source to dest where the destination string will
      be in unpacked format. The source string may either be a packed or an
      unpacked string.

tolower(c)
      Returns the character code of the lower case letter of "c" if there
      is one, or the character code of "c" if the letter "c" has no lower
      case equivalent.

toupper(c)
      Returns the character code of the upper case letter of "c" if there
      is one, or the character code of "c" if "c" has no upper case
      equivalent.

                                <*>

      Properties are general purpose names or values. The property list
      routines maintain a list of these name/value pairs that is shared
      among all abstract machines. The property list is therefore a way for
      concurrent abstract machines to exchange information.

      All "property maintenance" functions have an optional "id" para-
      meter. You can use this parameter to indicate which abstract machine
      the property belongs to. (An application that supports concurrent
      abstract machines will usually provide each abstract machine with a
                                        Proposed function library  o  41

      unique id.) When querying (or deleting) a property, the id value that
      you pass in is matched to the id values of the list.

      A property is identified with its "abstract machine id" plus either
      a name or a value. The name-based interface allows you to attach a
      value (e.g. the handle of an object) to a name of your choosing. The
      value-based interface allows you to attach a string to a number. The
      difference between the two is basically the search key versus the
      output parameter.

      All property maintenance functions have a "name" and a "value"
      parameter. Only one of this pair must be filled in. When you give
      the value, the getproperty function stores the result in the string
      argument and the setproperty function reads the string to store from
      the string argument.

      The number of properties that you can add is limited only by available
      memory.

getproperty(id=0, name[]="", value=cellmin, string[]="")
      Returns the value of a property when the name is passed in; fills in
      the string argument when the value is passed in. The name string may
      either be a packed or an unpacked string. If the property does not
      exist, this function returns zero.

setproperty(id=0, name[]="", value=cellmin, string[]="")
      Add a new property or change an existing property.

deleteproperty(id=0, name[]="", value=cellmin)
      Returns the value of the property and subsequently removes it. If the
      property does not exist, the function returns zero.

existproperty(id=0, name[]="", value=cellmin)
      Returns true if the property exists and false otherwise.


Console functions

For testing purposes, the console functions that read user input and that
output strings in a scrollable window or on a standard terminal display are
often convenient.
42  o  Proposed function library

getvalue(base=10, end=^'r', ...)
      Read a value (a signed number) from the keyboard. The getvalue()
      function allows you to read in a numeric radix from 2 to 36 (the base
      parameter) with decimal radix by default.

      By default the input ends when the user types the enter key, but one or
      more different keys may be selected (the end parameter and subsequent).
      In the list of terminating keys, a positive number (like '^r') displays
      the key and terminates input, and a negative number terminates input
      without displaying the terminating key.

print(str[], foreground=-1, background=-1)
      Prints a simple string on the console. The foreground and background
      colours may be optionally set. See CONSOLE.INC for a list of colours.

printf(format[], ...)
      Prints a string with embedded codes:
      %c  print a character at this position
      %d  print a decimal number at this position
      %s  print a character string at this position

      The printf function works similarly to the printf function of the C
      language.


Fixed point arithmetic

Small does not support floating point arithmetic. Through a set of native
functions, Small supports fixed point arithmetic. A fixed point number in
Small is a 32-bit number with 18 bits for the integral part of the value and
14 bits for the fractional part. This gives a precision of four decimal digits
and a range of - 131072 to +131071.

To convert from integers to cells, use one of the functions fixed or fixedstr.
The function fixed creates a fixed point number with the same integral value
as the input value and a fractional part of zero. Function fixedstr makes a
fixed point number from a string, which can include a fractional part.

To convert back from fixed point numbers to plain cells, use the functions
fround and ffract. Function fround is able to round upwards, to round down-
wards (truncation) and to round to the nearest integer. Function ffract gives
the fractional part of a fixed point number, but still stores this as a fixed
point number.
                                        Proposed function library  o  43

Adding and subtracting operations on fixed point values can use the conven-
tional + and - operators. For multiplication and division, one must use the
fmul and fdiv functions.

fixed:fixed(value)
      Create a fixed point number with the same (integral) value as the
      parameter value.

fixed:fixedstr(string[])
      Create a fixed point number from a string. The string may specify a
      fractional part, e.g., "123.45".

fixed:fmul(fixed:oper1, fixed:oper2)
      Multiply two fixed point numbers.

fixed:fdiv(fixed:dividend, fixed:divisor)
      Fixed point division.

fixed:ffract(fixed:value)
      Returns the fractional part if value.

fround(fixed:value, fround_method:method=fround_round)
      Round a fixed point number and return the value as a cell. The rounding
      method may be one of:
      fround_roundround to the nearest integer (default)
      fround_floorround downwards (truncate)
      fround_ceilround upwards

      When rounding negative values upwards or downwards, note that - 2 is
      considered smaller than - 1.
44  o  Pitfalls: differences from C

Pitfalls: differences from C

* First and foremost (and hardly a subtle difference) is that Small lacks the
  typing mechanism of C. Small is an "integer-only" variety of C; there are
  no floating point operations and no structures or unions.

* The second fundamental difference in Small is the lack of pointers. For
  the purpose of passing function arguments by reference, Small provides a
  "reference" argument, (page 13). The "placeholder" argument replaces
  some uses of the NULL pointer (page 16).

* Escape sequences ("\n", "\t", etc.) are replaced by control characters.
  The main difference is that the caret ("^") replaces the backslash
  ("\"). See "Character constants" on page 22; see also #pragma ctrlchar
  on page 38.

* Cases in a switch statement are not "fall through". Only a single in-
  struction many (and must) follow each case label. To execute multiple
  instructions, you must use a compound statement. The default clause of a
  switch statement must be the last clause of the switch statement. More on
  page 35.

* Numbers can have hexadecimal, decimal or binary radix. Octal radix is not
  supported. See "Constants" on page 22. Hexadecimal numbers must start
  with "0x" (a lower case "x"), the prefix "0X" is invalid.

* Function declarations are required, even though Small is a typeless lan-
  guage.

* The "extern" and "static" keywords do not exist in Small; the current
  implementation of the compiler has no "linking phase".

* The compiler directives differ from C's preprocessor commands. Notably, the
  #define directive can only add numeric constants, and #ifdef and #ifndef are
  replaced by the more general #if directive (see "Directives" on page 36).
  To create numeric constants, see also page 24.

* char is an operator, not a type. See page 31 and the tips on page 45.

* The empty instruction is an empty compound block, not a semicolon (page
  33). This modification avoids a frequent error.
                                                  Assorted tips  o  45

* defined is an operator, not a preprocessor directive. The defined operator
  in Small operates on constants (with const and enum), global variables,
  local variables and functions.

* The sizeof operator returns the size of a variable in cells, not in
  "bytes".

* The direction for truncation for the operator / is always towards the
  smaller value, where -2 is smaller than -1. The % operator always gives a
  positive result, regardless of the signs of the operands. See page 26.

* There is no unary + operator, which is a "no-operation" operator anyway.



Assorted tips


Working with characters and strings

Strings can be in packed or in unpacked format. In the packed format, each
cell will typically hold four characters (in the current implementations, a
cell is 32-bit and a character is often 8 bit). In this configuration, the
first character in a "pack" of four is the highest byte of a cell and the
fourth character is in the lowest byte of each cell.

A string must be stored in an array. For an unpacked string, the array must
be large enough to hold all characters in the string plus a terminating
zero cell. That is, in the example below, the variable ustring is defined as
having five cells, which is just enough to contain the string with which it is
initialized:
    --------------------------------------------------------------------------
    new ustring[5] = "test";
    --------------------------------------------------------------------------

In a packed string, each cell contains several characters and the string
ends with a zero character. The char operator helps with declaring the the
array size to contain the required number of characters. The example below
will allocate enough cells to hold five packed characters. In a typical
implementation, there will be two cells in the array.
    --------------------------------------------------------------------------
    new pstring[5 char] = !"test";
    --------------------------------------------------------------------------
46  o  Assorted tips

In other words, the char operators divides its left operand by the number of
bytes that fit in a cell and rounds upwards. Again, in a typical implementa-
tion, this means dividing by four and rounding upwards.

You can design routines that work on strings in both packed and unpacked
formats. To find out whether a string is packed or unpacked, look at the first
cell of a string. If its value is higher than the maximum possible value of
a character (higher than 255 for 8 bit characters), the string is a packed
string. Otherwise it is an unpacked string.

The code snippet below returns true if the input string is packed and false
otherwise (also note the use of tagnames):
    --------------------------------------------------------------------------
    bool: ispacked(string[])
       return bool: (string[0] > charmax);
    --------------------------------------------------------------------------

See also page 39 for proposed core functions that operate on both packed and
unpacked strings.

An unpacked string ends with a full zero cell. The end of a packed string is
marked with only a zero character. Since there may be up to four characters
in a cell, this zero character may occur at any of the four positions in the
"pack". The { } operator extracts a character from a cell in an array.
Basically, one uses the cell index operator ("[ ]") for unpacked strings and
the character index operator ("{ }") to work on packed strings.

For example, a routine that returns the length in characters of any string
(packed or unpacked) is:
    --------------------------------------------------------------------------
    my_strlen(string[])
       {
       new len = 0;
       if (ispacked(string))
          while (string{len} != '^0')     /* get character from pack */
              ++len;
       else
          while (string[len] != '^0')     /* get cell */
              ++len;
       return len;
       }
    --------------------------------------------------------------------------
                                                  Assorted tips  o  47

If you make functions to work exclusively on either packed or unpacked
strings, it is a good idea to add an assertion to enforce this condition:
    --------------------------------------------------------------------------
    strupper(string[])
       {
       assert ispacked(string);

       for (new i=0; string{i} != '^0'; ++i)
          string{i} = toupper(string{i});
       }
    --------------------------------------------------------------------------

Although, in preceding paragraphs we have assumed that a cell is 32 bits wide
and a character is 8 bits, this cannot be relied upon. The size of a cell is
implementation defined; the maximum and minimum values are in the predefined
constants cellmax and cellmin. There are similar predefined constants for
characters, see page 24. One may safely assume, however, that both the size
of a character in bytes and the size of a cell in bytes are powers of two.

The char operator allows you to determine how many packed characters fit in a
cell. For example:
    --------------------------------------------------------------------------
    #if     4 char == 1
          /* code that assumes 4 packed characters per cell */
    #else
     #if   4 char == 2
          /* code that assumes 2 packed characters per cell */
     #else
       #if 4 char == 4
          /* code that assumes 1 packed character per cell */
       #else
          #assert 0 /* unsupported cell/character size */
       #endif
     #endif
    #endif
    --------------------------------------------------------------------------
48  o  Assorted tips

Concatenating lines

Small is a free format language, but the parser directives (see page 36) must
be on a single line. Strings may not run over several lines either. When this
is inconvenient, you can use a backslash character ("\") at the end of a
line to "glue" that line with the next line.

For example:
    --------------------------------------------------------------------------
    #define max_path    max_drivename + max_directorystring + \
                        max_filename + max_extension
    --------------------------------------------------------------------------

You also use the concatenation character to cut long literal strings over
multiple lines. Note that the "\" eats up all leading white space on the
next line. The example below prints "Hello world" with one space between the
two words (because there is a space between "Hello" and the backslash):
    --------------------------------------------------------------------------
    print("Hello \
         world");
    --------------------------------------------------------------------------
                                                               o  49

                         Small: the compiler

******************************************************************************
------------------------------------------------------------------------------

The Small compiler is currently the only translator (or parser) that imple-
ments the Small language, and it will likely remain the only implementation.
The Small compiler translates a text file with source code to a binary file
for an abstract machine. The format of the output file is in appendix C.


Usage


      sc <options> [filename]

The input file name is any legal filename. If no extension is given, ".SMA"
is assumed. The compiler creates an output file with, by default, the same
name as the input file and the extension ".AMX".

The options are:
-a      "assembler", generate a text file with the pseudo-assembler code
        for the Small abstract machine, instead of binary code;
-csize  set the character size, size must be 8 (for ASCII & ISO Latin-1) or
        16 for Unicode;
-dlevel debug level: 0 = none, 1 = bounds checking and assertions only, 2 =
        full symbolic information;
-ename  set the name of the error file (when this option is set, there is no
        output to the screen);
-oname  set the output filename and path;
-v      "verbose", display additional information on the screen while
        compiling;
-\      control characters start with "\" instead of "^";
sym=val define constant "sym" with the given (numeric) value.

All options should be separated by at least one space.

When the compiler finds an error in a file, it outputs a message giving, in
this order:
* the name of the file
* the line number were the compiler detected the error between parentheses,
  directly behind the filename
* the error class ("Error", "Fatal" or "Warning")
* an error number between square brackets
50  o  Compiler diagnostics

* a descriptive error message

For example:

      demo.c(3): Error [001]: expected token: ";", but found "{"

If the "verbose" option is active, the erroneous line is displayed too.

Note: the line number given by the compiler may specify a position behind
the actual error, since the compiler cannot always establish an error before
having analyzed the complete expression.

After termination, the return code of the compiler is:
0   no errors
1   errors found
2   warnings found
3   aborted by user

These return codes may be checked within batch processors (such as the
"make" utility).



Compiler diagnostics

Errors are separated into three classes:

Errors      Describe situations where the compiler is unable to generate
            appropriate code. Errors messages are numbered from 1 to 99.

Fatal errorsFatal errors describe errors from which the compiler cannot
            recover. Parsing is aborted. Fatal error messages are numbered
            from 100 to 199.

Warnings    Warnings are displayed for unintended compiler assumptions and
            common mistakes. Warning messages are numbered from 200 to 299.


Errors

001    expected token: token, but found token
       A required token is omitted.
                                            Compiler diagnostics  o  51

002    local variables not allowed within switch
       Within an active switch statement, no variables may be declared.
       Instead, add a compound block for each case instruction that contains
       the local variables.

003    reserved
       Reserved (unused) error message.

004    function name not defined
       Functions must be defined or prototyped before the first statement
       (page 11).

005    function may not have arguments
       The function main() is the program entry point. It may not have
       arguments.

006    must be assigned to an array
       String literals must be assigned to an array.

007    assertion failed
       Compile-time assertion failed (see the "#assert" directive on page
       36).

008    must be a constant expression; assumed zero
       The size of arrays and the parameters of most directives must be
       constant values.

009    invalid array size (negative or zero)
       The number of elements of an array must always be 1 or more.

010    illegal function or declaration
       The compiler expects a declaration of a global variable or of a
       function at the current location, but it cannot interpret it as such.

011    invalid outside functions
       The instruction or statement is invalid at a global level. Local
       labels and (compound) statements are only valid if used within
       functions.

012    invalid function call, not a valid address
       The symbol is not a function.
52  o  Compiler diagnostics

013    no entry point (no public functions)
       The file does not contain a main function or any public function.
       The compiled file thereby does not have a starting point for the
       execution.

014    invalid statement; not in switch
       The statements case and default are only valid within an active switch
       statement.

015    "default" must be the last clause in switch statement
       Small requires the default clause to be the last clause in a switch
       statement.

016    multiple defaults in "switch"
       Each switch statement may only have one default clause.

017    undefined symbol symbol
       The symbol (variable, constant or function) is not declared.

018    initialization data exceeds declared size
       An array with a specified size is initialized, but the number of
       initiallers exceeds the number of elements specified (e.g. "arr[3] =
       { 1, 2, 3, 4 };" the array is specified to have three elements, but
       there are four initiallers). See page 8.

019    not a label: name
       A goto statement branches to a symbol that is not a label.

020    invalid symbol name
       A symbol may start with a letter, an underscore or an "at" sign
       ("@") and may be followed by a series of letters, digits, underscore
       characters and "@" characters. See page 21 for the syntax rules for
       identifiers.

021    symbol already defined: identifier
       The symbol was already defined at the current level.

022    must be lvalue
       The symbol that is altered (incremented, decremented, assigned a
       value, etc.) must be a variable that can be modified (this kind of
       variable is called an lvalue). Functions, string literals, arrays and
       constants are no lvalues.
                                            Compiler diagnostics  o  53

023    reserved
       Reserved (internal) error message.

024    "break" or "continue" is out of context
       The statements break and continue are only valid inside the context of
       a loop (a do, for or while statement). Unlike the languages C/C++ and
       Java, break does not jump out of a switch statement.

025    function heading differs from prototype
       The number of arguments given at a previous declaration of the
       function does not match the number of arguments given at the current
       declaration.

026    no matching "#if..."
       The directive #else or #endif was encountered, but no matching #if
       directive was found.

027    invalid character constant
       Probably caused by an unknown control character, like "^x". See page
       22 for valid control characters.

028    cannot subscript, not an array
       The subscript operators "[" and "]" are only valid with arrays.

029    invalid expression, assumed zero
       The compiler could not interpret the expression.

030    compound statement not closed at the end of file
       An unexpected end of file occurred. One or more compound statements
       are still unfinished (i.e. the closing brace """ has not been
       found).

031    unknown directive
       The character "#" appears first at a line, but no valid directive
       was specified.

032    array index out of bounds
       The array index is larger than the highest valid entry of the array.

033    array must be indexed (variable name)
       An array as a whole cannot be used in a expression; you must indicate
       an element of the array between square brackets.
54  o  Compiler diagnostics

034    argument does not have a default value (argument index)
       You can only use the argument placeholder when the function definition
       specifies a default value for the argument.

035    argument type mismatch (argument index)
       The argument that you pass is different from the argument that the
       function expects, and the compiler cannot convert the passed-in
       argument to the required type. For example, you cannot pass the
       literal value "1" as an argument when the function expects an array
       or a reference.

036    empty statement
       The line contains a semicolon that is not preceded by an expression.
       Small does not support a semicolon as an empty statement, use an empty
       compound block instead (page 33).

037    invalid string
       A string was not well-formed; for example, the filename for the #in-
       clude directive was not enclosed in double quotes or angle brackets.

038    extra characters on line
       There were trailing characters on a line that contained a directive (a
       directive starts with a # symbol, see page 36).

039    constant symbol has no size
       A variable has a size (measured in a number of cells), a constant has
       no size. That is, you cannot use a (symbolic) constant with the sizeof
       operator, for example.

040    duplicate "case" label (value value)
       A preceding "case label" in the list of the switch statement
       evaluates to the same value.

041    invalid ellipsis, array size is not known
       You used a syntax like "arr[] = { 1, ... };", which is invalid,
       because the compiler cannot deduce the size of the array from the
       declaration.

042    invalid combination of class specifiers
       A function is denoted as both "public" and "native", which is
       unsupported.
                                            Compiler diagnostics  o  55

043    character constant exceeds range for packed string
       Usually an attempt to store a Unicode character in a packed string
       where a packed character is 8-bits.

044    mixing named and positional parameters
       You must either use named parameters or positional parameters for all
       parameters of the function.

045    too many function arguments
       The maximum number of function arguments is currently limited to 64.


Fatal Errors

100    cannot read from file: filename
       The compiler cannot find the specified file or does not have access to
       it.

101    cannot write to file: filename
       The compiler cannot write to the specified output file, probably
       caused by insufficient disk space or restricted access rights (the
       file could be read-only, for example).

102    table overflow: table name
       This is an internal error of the compiler, caused by the limited size
       of its internal tables. The "table name" is one of the following:

       "staging buffer": the staging buffer holds the code generated for
       one expression. The buffer can overflow on very long expressions.

       "loop table": the loop table is a stack used with nested do, for,
       and while statements. The table allows nesting of these statements up
       to 10 levels.

       "compiler stack": the compiler uses a stack to store temporary
       information it needs while parsing. An overflow of this stack is
       probably caused by deeply nested (or recursive) file inclusion or
       complex expression involving function calls with many arguments.

103    insufficient memory
       General "out of memory" error.

104    invalid assembler instruction symbol
       An invalid opcode in an #emit directive.
56  o  Compiler diagnostics

Warnings

200    symbol is truncated to 16 characters
       The symbol is longer than sixteen characters. Truncation may cause
       different symbol names to become equal (e.g. both VeryLongIdentifier
       and VeryLongIdentification are truncated to VeryLongIdentifi). This
       warning message may cause error 021.

201    redefinition of constant (symbol name)
       The symbol was previously defined to a different value.

202    number of arguments does not match definition
       At a function call, the number of arguments passed to the function
       (actual arguments) differs from the number of formal arguments
       declared in the function heading. To declare functions with variable
       argument lists, use an ellipsis (...) behind the last known argument
       in the function heading; for example:
       print(formatstring,...); (see page 17).

203    symbol is never used: identifier
       A symbol is defined but never used. Public functions are excluded from
       the symbol usage check (since these may be called from the outside).

204    symbol is assigned a value that is never used: identifier
       A value is assigned to a symbol, but the contents of the symbol are
       never accessed.

205    redundant code: constant expression is zero
       Where a conditional expression was expected, a constant expression
       with the value zero was found, e.g. "while (0)" or "if (0)".
       The the conditional code below the test is never executed, and it is
       therefore redundant.

206    redundant test: constant expression is non-zero
       Where a conditional expression was expected, a constant expression
       with a non-zero value was found, e.g. if (1). The test is redundant,
       because the conditional code is always executed.

207    unknown "#pragma"
       The compiler ignores the pragma. The #pragma directives may change
       between compilers of different vendors and between different versions
       of a compiler of the same version.
                                            Compiler diagnostics  o  57

208    function uses both "return;" and "return value;"
       The function returns both with and without a return value. The
       function should be consistent in always returning with a function
       result, or in never returning a function result.

209    function should return a value
       The function does not have a return statement, or it does not have an
       expression behind the return statement, but the function's result is
       used in a expression.

210    possible use of symbol before initialization: identifier
       A local (uninitialized) variable appears to be read before a value
       is assigned to it. The compiler cannot determine the actual order of
       reading from and storing into variables and bases its assumption of
       the execution order on the physical appearance order of statements an
       expressions in the source file.

211    possibly unintended assignment
       Where a conditional expression was expected, the assignment operator
       (=) was found instead of the equality operator (==). As this is
       a frequent mistake, the compiler issues a warning. To avoid this
       message, put parentheses around the expression, e.g. if ( (a=2) ).

212    possibly unintended bitwise operation
       Where a conditional expression was expected, a bitwise operator (&
       or |) was found instead of a Boolean operator (&& or ||). As this
       is a frequent mistake, the compiler issues a warning. To avoid this
       message, put parentheses around the expression, e.g. if ( (a&2) ).

213    tagname mismatch
       A tagname mismatch occurs when:
       * assigning to a tagged variable a value that is untagged or that has
         a different tag
       * the expressions on either side of a binary operator have different
         tags
       * in a function call, passing an argument that is untagged or that has
         a different tag than what the function argument was defined with.
       * indexing an array which requires a tagged index with no tagname or a
         wrong tagname

       Tagnames are discussed on page 10
58  o  Compiler diagnostics

214    ambiguous mix of operators, use parentheses
       Some operators in Small have an unexpected precedence level. There-
       fore, when mixing operators of different groups (e.g. a = b << c +
       d), you should add parentheses to make clear what the intent of the
       expression is. See page 31 for the operator precedence table.

215    expression has no effect
       The result of the expression is apparently not stored in a variable or
       used in a test. The expression or expression statement is therefore
       redundant.

216    nested comment
       Small does not support nested comments.

217    loose indentation
       Statements at the same logical level do not start in the same column;
       that is, the indents of the statements are different. Although Small
       is a free format language, loose indentation frequently hides a
       logical error in the control flow.


Run time errors

The function library that forms the abstract machine returns error codes.
These error codes encompass both errors for loading and initializing a binary
file and run-time errors due to programmer errors. See page 72 for a list of
run-time errors.
                                                               o  59

                         The abstract machine

******************************************************************************
------------------------------------------------------------------------------

The abstract machine is a C function library. There are several version: one
that is written in ANSI C, and optimized versions that use GNU C extensions or
assembler subroutines.



Using the abstract machine

To use the abstract machine:
* create an abstract machine for a compiled program with amx_Init,
* register all modules that the program uses with amx_Register,
* run the program with amx_Exec,

The example (in C) below illustrates these steps:
    --------------------------------------------------------------------------
    int main(int argc,char *argv[])
    {
    extern AMX_NATIVE_INFO core_Natives[];
    extern AMX_NATIVE_INFO console_Natives[];

     AMX amx;
     cell ret;
     int err;
     void *program;

     if (argc != 2 || (program = loadprogram(&amx,argv[1])) == NULL) {
       printf("Usage: SRUN <filename>\n\n"
             "The filename must include the extension\n");
       return 1;
     } /* if */

     amx_Register(&amx, core_Natives, -1);
     err = amx_Register(&amx, console_Natives, -1);
     if (err == AMX_ERR_NONE)
       err = amx_Exec(&amx, &ret, AMX_EXEC_MAIN, 0);

     if (err != AMX_ERR_NONE)
       printf("Run time error %d on line %ld\n", err, amx.curline);
60  o  Using the abstract machine

     else if (ret != 0)
       printf("%s returns %ld\n", argv[1], (long)ret);

     free(program);
     return 0;
    }
    --------------------------------------------------------------------------

The cell data type is defined in AMX.H, it currently is a 32-bit integer. The
future may bring 16-bit or 64-bit versions of the abstract machine.

The preceding example checks for run time errors that may occur while execut-
ing the Small program. Such errors are usually flagged by native functions or
by assert instructions (see page 33) in the source code of the Small program.

The abstract machine API has no functions that read a program from file into
memory. The kernel routines of the abstract machine API do not use dynamic
memory allocation. Routines to allocating memory for the bytecode compiled
program and to load it from disk must be provided by you. The snippet below is
a typical example that does this:
    --------------------------------------------------------------------------
    void *loadprogram(AMX *amx,char *filename)
    {
     FILE *fp;
     AMX_HEADER hdr;
     void *program = NULL;

     if ((fp = fopen(filename,"rb")) != NULL) {
       fread(&hdr, sizeof hdr, 1, fp);
       if ((program = malloc((int)hdr.stp)) != NULL) {
         rewind(fp);
         fread(program, 1, (int)hdr.size, fp);
         fclose(fp);
         if (amx_Init(amx,program) == AMX_ERR_NONE)
          return program;
         free(program);
       } /* if */
     } /* if */
     return NULL;
    }
    --------------------------------------------------------------------------
                                              Extension modules  o  61

Extension modules

An extension module provides a Small program with application-specific
("native") functions. Creating an extension module is a three-step process:
1  writing the native functions (in C);
2  making the functions known to the abstract machine;
3  writing an include file that declares the native functions for the Small
   programs.


1. Writing the native functions

Every native function must have the following prototype:
    --------------------------------------------------------------------------
    cell func(AMX *amx, cell *params);
    --------------------------------------------------------------------------

The identifier "func" is a placeholder for a name of your choice. The AMX
type is a structure that holds all information on the current state of the
abstract machine (registers, stack, etc.); it is defined in the include file
AMX.H. The params argument points to an array that holds the parameter list
of the function. The value of params[0] is the number of bytes passed to the
function (divide by the size of a cell to get the number of parameters passed
to the function); params[1] is the first argument, and so forth.

For arguments that are passed by reference, function amx_GetAddr converts the
"abstract machine" address from the "params" array to a physical address.
The pointer that amx_GetAddr returns lets you access variables inside the
abstract machine directly. Function amx_GetAddr also verifies whether the
input address is a valid address.

Strings, like other arrays, are always passed by reference. However, neither
packed strings nor unpacked strings are universally compatible with C strings
(on Big Endian computers, packed strings are compatible with C strings).
Therefore, the abstract machine API provides two functions to convert C
strings to and from Small strings: amx_GetString and amx_SetString.

A native function may abort a program by calling amx_RaiseError with a non-
zero code. The non-zero code is what amx_Exec() returns.
62  o  Extension modules

2. Linking the functions to the abstract machine

An application uses amx_Register to make any native functions known to the
abstract machine. Function amx_Register expects a list of AMX_NATIVE_INFO
structures. Each structure holds a pointer to the name of the native function
and a function pointer.

Below is a full example of a file that implements two simple native functions:
raising a value to a power and calculating the square root. The list of
AMX_NATIVE_INFO structures is at the bottom of the example.
    --------------------------------------------------------------------------
    #include "amx.h"

    static cell power(AMX *amx, cell *params)
    {
     /* power(value, exponent);
      *   params[1] = value
      *   params[2] = exponent
      */
     cell result = 1;
     while (params[2]-- > 0)
       result *= params[1];
     return result;
    }

    static cell sqroot(AMX *amx, cell *params)
    {
     /* sqroot(value);
      *   params[1] = value
      * This routine uses a simple successive approximation algorithm.
      */
     cell div = params[1];
     cell result = 1;
     while (div > result) {       /* end when div == result, or just below
    */
       div = (div + result) / 2;   /* take mean value as new divisor */
       result = params[1] / div;
     } /* while */
     return div;
    }

    AMX_NATIVE_INFO power_Natives[] = {
     { "power",  power },
                                                     amx_Allot  o  63

     { "sqroot", sqroot },
     { 0, 0 }       /* terminator */
    };
    --------------------------------------------------------------------------

In you application, you must also add a call to amx_Register with the list of
native functions, as shown below:
    --------------------------------------------------------------------------
    extern AMX_NATIVE_INFO power_Natives[];

    err = amx_Register(&amx, power_Natives, -1);
    --------------------------------------------------------------------------



3. writing an include file for the native functions

The first step implements the native functions and the second step makes
the functions known to the abstract machine. Now the third step is to make
the native functions known to the Small compiler. To that end, one writes
an include file that contains the prototypes of the native functions and all
constants that may be useful in relation to the native functions.
    --------------------------------------------------------------------------
    native power(value, exponent);
    native sqroot(value);
    --------------------------------------------------------------------------



Function reference

With one exception, all functions return an error code if the function fails.
A return code of zero means "no error". See page 72 for the defined error
codes. (The exception is amx_NativeInfo.)



==============================================================================
amx_Allot                       Reserve stack space in the abstract machine

Syntax:   amx_Allot(AMX *amx,int cells,cell *amx_addr,cell **native_addr)

          amx        The abstract machine.

          cells      The number of cells to reserve.
64  o  amx_Callback

          amx_addr   The address of the allocated cell as the Small program
                     (that runs in the abstract machine) can access it.

          native_addrThe address of the cell for C programs to access.

Notes:    You can fill the allocated stack space by writing through nat-
          ive_addr. Pass amx_addr to the Small function when you call the
          function through amx_Exec.

          Remove the stack space with amx_Release.

See also: amx_Exec, amx_Release



==============================================================================
amx_Callback                                        The default callback

Syntax:   int amx_Callback(AMX *amx, cell index, cell *result, cell *params)

          amx        The abstract machine.

          index      Index into the native function table; it points to the
                     requested native function.

          result     The function result (of the native function) should be
                     returned through this parameter.

          params     The parameters for the native function, passed as a
                     list of long integers. The first number of the list
                     is the number of bytes passed to the native functions
                     (from which the number of arguments can be computed).

Returns:  The callback should return an error code, or zero for no error.
          See page 72 for the error codes. When the callback returns a
          non-zero code, amx_Exec aborts execution.

Notes:    The abstract machine has a default callback function, which
          works in conjunction with amx_Register. You can override the
          default operation by setting a different callback function using
          amx_SetCallback.

          If you override the default callback function, you may also need
          to provide an alternative function for amx_Registers.
                                                 amx_FindPublic  o  65

See also: amx_Exec, amx_RaiseError, amx_SetCallback



==============================================================================
amx_Exec                                                     Run code

Syntax:   int amx_Exec(AMX *amx, long *retval, int index, int numparams, ...)

          amx        The abstract machine from which to call a function.

          retval     Will hold the return value of the called function upon
                     return.

          index      An index into the "public function table"; it
                     indicates the function to execute. See amx_FindPublic
                     for more information. Use AMX_EXEC_MAIN to start
                     executing at the main function.

          numparams  The number of function parameters that follow.

          ...        Optional parameters for the function. All these
                     parameters must be cast to the type cell, which is
                     usually a 32-bit integer.

Notes:    This function calls the callback function for any native function
          call that the code in the AMX makes. amx_Exec assumes that all
          native functions are correctly initialized with amx_Register.

See also: amx_FindPublic, amx_Register



==============================================================================
amx_FindPublic                        Return the index of a public function

Syntax:   int amx_FindPublic(AMX *amx, char *name, int *index)

          amx        The abstract machine from which to call a function.

          name       The name of the public function to find.

          index      Upon return, this parameter holds the index of the
                     requested public function.
66  o  amx_Flags

See also: amx_Exec, amx_GetPublic, amx_NumPublics



==============================================================================
amx_Flags                                          Return various flags

Syntax:   int amx_Flags(AMX *amx,unsigned short *flags)

          amx        The abstract machine from which to call a function.

          flags      A set of bit flags is stored in this parameter. It is
                     a set of the following flags:
                     AMX_FLAG_CHAR16if a character is 16-bits rather than
                                  the default of 8 bits
                     AMX_FLAG_DEBUGif the program contains symbolic
                                  information

Notes:    A typical use for this function is to check whether the compiled
          program contains symbolic (debug) information. There is no use
          in installing a debugger callback if the program has no symbolic
          information.



==============================================================================
amx_GetAddr                                       Resolve an AMX address

Syntax:   int amx_GetAddr(AMX *amx,cell v,cell **addr)

          amx        The abstract machine.

          v          The address relative to the abstract machine.

          addr       A pointer to the variable that will hold the memory
                     address of the indicated cell.

Notes:    This function returns the memory address of an address in the
          abstract machine. One typically uses this function in an extension
          module, because it allows you to access variables inside the
          abstract machine.
                                                amx_GetUserData  o  67

==============================================================================
amx_GetPublic                               Return a public function name

Syntax:   int amx_GetPublic(AMX *amx, int index, char *funcname)

          amx        The abstract machine.

          index      The index of the requested module. Use zero to
                     retrieve the name of the first public function.

          funcname   The string that will hold the name of the public
                     function.

Notes:    The string should be large enough to hold longest function name
          plus the terminating zero byte. Use amx_NameLength to inquire this
          length.

See also: amx_FindPublic, amx_NameLength, amx_NumPublics



==============================================================================
amx_GetString                   Retrieve a string from the abstract machine

Syntax:   int amx_GetString(char *dest, cell *source)

          dest       A pointer to a character array of sufficient size to
                     hold the converted source string.

          source     A pointer to the source string. Use amx_GetAddr to
                     convert a string address in the AMX to the physical
                     address.

Notes:    This function converts both packed strings and unpacked strings
          from the "Small" format to the "C" format.

See also: amx_SetString



==============================================================================
amx_GetUserData                           Return general purpose user data

Syntax:   int amx_GetUserData(AMX *amx, int index, void **ptr)
68  o  amx_Init

          amx        The abstract machine.

          index      The index of the requested user pointer. This must be
                     a positive value below AMX_USERNUM.

          ptr        Will hold a pointer to the requested user data upon
                     return.

Notes:    The AMX does not use "user data" in any way. The storage can be
          used for any purpose.

See also: amx_SetUserData



==============================================================================
amx_Init                   Create an abstract machine, load the binary file

Syntax:   int amx_Init(AMX *amx, void *program)

          amx        This variable is initialized with the specific
                     settings of the abstract machine.

          program    A pointer to the bytecode stream of the program.

Description:amx_Init initializes the abstract machine with the settings
          from the binary file. The resources are released with a call to
          amx_Release.

See also: amx_Release



==============================================================================
amx_NameLength                              Return the maximum name length

Syntax:   int amx_NameLength(AMX *amx, int *length)

          amx        The abstract machine.

          length     Will hold the maximum name length upon return. The
                     returned value includes the space needed for the
                     terminating zero byte.

See also: amx_GetPublic
                                                 amx_RaiseError  o  69

==============================================================================
amx_NativeInfo                         Return a structure for amx_Register

Syntax:   AMX_NATIVE_INFO *amx_NativeInfo(char *name, AMX_NATIVE func)

          name       The name of the function (as known to the Small
                     program)

          func       A pointer to the native function.

Notes:    This function creates a list with a single record for amx_Register.
          To register a single function, use the code snippet (where
          my_solve is a native function):
              --------------------------------------------------------------
              err = amx_Register(amx, amx_NativeInfo("solve", my_solve), 1);
              --------------------------------------------------------------

          This function returns a pointer to a static record.

See also: amx_Register



==============================================================================
amx_NumPublics                        Return the number of public functions

Syntax:   int amx_NumPublics(AMX *amx, int *number)

          amx        The abstract machine.

          number     Will hold the number of public functions upon return.

Notes:    The function returns number of entries in the file's "pub-
          lic functions" table. To retrieve the function names, use
          amx_GetPublic.

See also: amx_GetPublic



==============================================================================
amx_RaiseError                                            Flag an error

Syntax:   int amx_RaiseError(AMX *amx, int error)
70  o  amx_Register

          amx        The abstract machine.

          error      The error code. This is the code that amx_Exec()
                     returns.

Notes:    This function should be called from a native function. It lets the
          default callback routine return an error code.



==============================================================================
amx_Register                                  Make native functions known

Syntax:   int amx_Register(AMX *amx, AMX_NATIVE_INFO *list, int number)

          amx        The abstract machine.

          list       An array with structures where each structure holds
                     a pointer to the name of a native function and a
                     function pointer. The list is optionally terminated
                     with a structure holding two NULL pointers.

          number     The number of structures in the list array, or -1
                     if the list ends with a structure holding two NULL
                     pointers.

Notes:    If this function returns the error code AMX_ERR_NOTFOUND, one or
          more native functions that are used by the Small program are not
          found in the provided list. You can call amx_Register again to
          register additional function lists.

See also: amx_NativeInfo



==============================================================================
amx_Release                        Free stack space in the abstract machine

Syntax:   int amx_Release(AMX *amx,cell amx_addr)

          amx        The abstract machine.

          amx_addr   The address of the allocated cell as the Small program
                     (that runs in the abstract machine) sees it. This
                     value is returned by amx_Allot.
                                                  amx_SetString  o  71

Notes:    amx_Allot allocates memory in descending stack order (the stack
          grows downwards). The amx_addr value passed to amx_Release frees
          all memory below that address. In other words, a single call to
          amx_Release can free multiple calls to amx_Allot if you pass the
          amx_addr value of the first allocation.

See also: amx_Exec, amx_Release



==============================================================================
amx_SetCallback                                Install a callback routine

Syntax:   int amx_SetCallback(AMX *amx, AMX_CALLBACK callback)

          amx        The abstract machine.

          callback   The address for a callback function. See amx_Callback
                     for the prototype and calling convention of a callback
                     routine.

Notes:    If you change the callback function, you should not use func-
          tions amx_Register or amx_RaiseError. These functions work in
          conjunction with the default callback function.



==============================================================================
amx_SetString                        Store a string in the abstract machine

Syntax:   int amx_SetString(cell *dest, char *source, int pack)

          dest       A pointer to a character array in the AMX where the
                     converted string is stored. Use amx_GetAddr to convert
                     a string address in the AMX to the physical address.

          source     A pointer to the source string.

          pack       Non-zero to convert the source string to a packed
                     string in the abstract machine, zero to convert the
                     source string to a cell string.

See also: amx_GetString
72  o  amx_SetUserData

==============================================================================
amx_SetUserData                              Set general purpose user data

Syntax:   int amx_SetUserData(AMX *amx, int index, void *ptr)

          amx        The abstract machine.

          index      The index of the user pointer. This must be a positive
                     value below AMX_USERNUM.

          ptr        A pointer to the user data.

Notes:    The AMX does not use "user data" in any way. The storage can be
          used for any purpose.

See also: amx_GetUserData



==============================================================================
amx_StrLen                             Get the string length in characters

Syntax:   int amx_StrLen(cell *cstring, int *length)

          cstring    The string in the abstract machine.

          length     This parameter will hold the string length upon
                     return.

Notes:    This function determines the length in characters of the string,
          not including the zero-terminating character (or cell). A packed
          string occupies less cells than its number if characters.



Error codes

AMX_ERR_NONE
      No error.

AMX_ERR_EXIT
      Program aborted execution. This is usually not an error.

AMX_ERR_ASSERT
      A run-time assertion failed.
                                                   Error codes  o  73

AMX_ERR_STACKERR
      Stack or heap overflow; the stack collides with the heap.

AMX_ERR_BOUNDS
      Array index is out of bounds.

AMX_ERR_MEMACCESS
      Accessing memory that is not allocated for the program.

AMX_ERR_INVINSTR
      Invalid instruction.

AMX_ERR_STACKLOW
      Stack underflow; more items are popped off the stack than were pushed
      onto it.

AMX_ERR_HEAPLOW
      Heap underflow; more items are removed from the heap than were inserted
      into it.

AMX_ERR_CALLBACK
      There is no callback function, and the program called a native func-
      tion.

AMX_ERR_NATIVE
      Native function requested the abortion of the abstract machine.

AMX_ERR_DIVIDE
      Division by zero.

AMX_ERR_MEMORY
      General purpose out-of-memory error.

AMX_ERR_FORMAT
      Invalid format of the memory image for the abstract machine.

AMX_ERR_VERSION
      This program requires a newer version of the abstract machine.

AMX_ERR_NOTFOUND
      The requested native functions are not found.

AMX_ERR_INDEX
      Invalid index (invalid parameter to a function).
74  o

                             Rationale                              Appendix A

******************************************************************************
------------------------------------------------------------------------------

The first issue in the presentation of a new computer language should be: why
a new language at all?

Indeed, I did look at several existing languages before I designed my own.
Not surprisingly these days, I specifically considered using Java. It turned
out quickly, though, that Java's design goals were not my design goals. For
example, where Java promotes distributed computing where "packages" reside
on diverse machines, Small is designed so that the compiled applets can be
easily stored in a compound file together with other data; and where Java
is designed to be architecture neutral and application independent, Small is
designed to be tightly coupled with an application; native functions are a
taboo to some extent in Java (at least, it is considered "impure"), whereas
native functions are the reason to be for Small.

Small is targeted as an extension language, meant to write application-
specific macros or subprograms with. Small is not the language for creating
business applications or operating systems. Small is designed to be easily
integrated with, and embedded in, other systems.

The first and foremost criterions for the Small language were execution speed
and reliability. Reliability in the sense that a Small program should not be
able to crash the application or tool in which it is embedded. Although this
limits the capabilities of the language significantly, the advantages are
twofold:
* the application vendor can rest assured that its application will not crash
  due to user additions or macros,
* the user is free to experiment with the language with no (or little) risk of
  damaging the application files.

Speed is essential, because Small programs would probably run in an abstract
machine (I do not foresee native code Small compilers), and abstract machines
are notoriously slow. I had to make a language that has low overhead and a
language for which a fast abstract machine can be written.

As Dennis Ritchie said, by intent the C language confines itself to facilities
that can be mapped relatively efficiently and directly to machine instruc-
tions. The same is true for Small, and this is also a partial explication why
Small looks so much like C.
                                                     Rationale  o  75

A brief analysis showed that the instruction decoding logic for an abstract
machine would quickly become the bottleneck in the performance of the abstract
machine. To keep the decoding simple, each opcode should have the same size
(excluding operands), and the opcode should fully specify the instruction
(including the addressing methods, size of the operands, etc.). That meant
that for each operation on a variable, the abstract machine needed a separate
opcode for every combination of variable type, storage class and access method
(direct, or dereferenced). For even three types (int, char and unsigned int),
two storage classes (global and local) and three access methods (direct,
indirect or indexed), a total of 18 opcodes (3*2*3) are needed to simply fetch
the value of a variable.

At the same time, to keep the abstract machine small and manageable, I set
a maximum of approximately 100 instructions (1). With 18 opcodes to load a
variable in a register, 18 more to store a register into a variable, another
18 to get the address of a variable, etc... I was quickly approaching (and
exceeding) my limit of a hundred opcodes.

The languages bob and rexx inspired me to design a typeless language. This
saved me a lot of opcodes. At the same time, the language could no longer
be called a "subset of C". I was changing the language. Why, then, not
go a foot further in changing the language? This is where a few more design
guidelines came into play:
* give the programmer a general purpose tool, not a special purpose solution
* avoid error prone language constructs; promote error checking
* be pragmatic

A general purpose tool: Small is targeted as an extension language, without
specifying exactly what it will extent. Typically, the application or the
tool that uses Small for its extension language will provide many, optimized
routines or commands to operate on its native objects, be it text, database
records or animated sprites. The extension language exists to permit the
user to do what the developer forgot, or decided not to include. Rather than
providing a comprehensive library of functions to sort data, match regular
expressions, or draw cubic Bzier splines, Small should supply a (general

-------------------
(1) 126 Opcodes are defined at this writing. To exploit performance gains by
    forcing proper alignment of memory words, the current abstract machine
    uses 32-bit opcodes. There is no technical limit on the number of opcodes,
    but in the interest of a small footprint, the number of opcodes should be
    restricted.
76  o  Rationale

purpose) means to use, extend and combine the specific ("native") functions
that an application provides.

Small lacks a comprehensive standard library. By intent, Small also lacks
features like pointers, dynamic memory allocation, direct access to the
operating system or to the hardware, that are needed to remain competitive in
the field of general purpose application or system programming. You cannot
build linked lists or dynamic tree data structures in Small, and neither can
you access any memory beyond the boundaries of the abstract machine. That is
not to say that a Small program can never use dynamic, sorted symbol tables,
or change a parameter in the operating system; it can do that, but it needs
to do so by calling a "native" function that an application provides to the
abstract machine.

In other words, if an application chooses to implement the well known peek
and poke functions (from BASIC) in the abstract machine, a Small program
can access any byte in memory, insofar the operating system permits this.
Likewise, an application can provide native functions that insert, delete or
search symbols in a table and allows several operations on them. The proposed
core functions getproperty and setproperty are an example of native functions
that build a linked list in the background.

Promote error checking: As you may have noticed, one of the foremost design
criterions of the C language, "trust the programmer", is absent from my
list of design criterions. Users of script languages are not always full time
programmers; and even if they are, Small will probably not be their primary
language. Most Small programmers will keep learning the language as they
go, and will even after years not have become experts. Enough reason, hence,
to replace error prone elements from the C language (pointers) with saver,
albeit less general, constructs (references) (2). References are copied from
C++. They are nothing else than pointers in disguise, but they are restricted
in various, mostly useful, ways. Turn to a C++ book to find more justification
for references.

I find it disturbing that many, even modern, programming languages have so
little built-in, or easy to use, support for confirming that programs do

-------------------
(2) You should see this remark in the context of my earlier remark that many
    "Small" programmers will be novice programmers. In my (teaching)
    experience, novice programmers make many pointer errors, as opposed to
    experienced C/C++ programmers.
                                                     Rationale  o  77

as the programmer intended. I am not referring to theoretical correctness
(which is too costly to achieve for anything bigger than toy programs), but
practical, easy to use, verification mechanisms as a help to the programmer.
Small provides both compile time and execution time assertions to use for
preconditions, postconditions and invariants.

The typing mechanism in most programming languages is also an automatic
"catcher" of a whole class of bugs. By virtue of being a typeless language,
Small lacked these error checking abilities. This was clearly a weakness, and
I invented the "tagname" mechanism to re-introduce the ability to verify
function parameter passing, array indexing and other operations.

Be pragmatic: The object-oriented programming paradigm has not entirely lived
up to its promise, in my opinion. On the one hand, OOP solves many tasks
an easier or cleaner way, due to the added abstraction layer. On the other
hand, contemporal object-oriented languages leave you struggling with the
language as much as with the problem. Jean-Paul Tremblay and Paul Sorenson
criticize the C language's large operator set with the argument that studies
have shown that people have difficulty with memorizing and understanding
deep hierarchies (3). The same argument also applies to the class hierarchies
in object-oriented programming libraries. Object-oriented programming is not
a solution for a non-expert programmer with little patience for artificial
complexity. The criterion "be pragmatic" is a reminder to seek solutions,
not elegancy. With a sarcastic twinkle, I have referred to Small as the first
subject oriented language.


Practical design criterions

The fact that Small looks so much like C cannot be a coincidence, and it
isn't. Small started as a C dialect and stayed that way, because C has a
proven track record. The changes from C were mostly born out of necessity
after rubbing out the features of C that I did not want in a scripting
language: no preprocessor, no pointers, no variable types.

Small, being a typeless language, needed a different means to declare vari-
ables. In the course of modifying this, I also dropped the C requirement that

-------------------
(3) "The Theory and Practice of Compiler Writing", McGraw-Hill, 1985, pp. 92.
78  o  Rationale

all variables should be declared at the top of a compound statement. Small is
a little more like C++ in this respect.

C language functions can pass "output values" via pointer arguments. The
standard function scanf, for example, stores the values or strings that it
reads from the console into its arguments. You can design a function in C so
that it optionally returns a value through a pointer argument; if the caller
of the function does not care for the return value, it passes NULL as the
pointer value. The standard function strtol is an example of a function that
does this. This technique frequently saves you from declaring and passing
dummy variables. Small replaces pointers with references, but references
cannot be NULL. Thus, Small needed a different technique to "drop" the
values that a function returns via references. Its solution is the use of an
"argument placeholder" that is written as an underscore character ("_");
Prolog programmers will recognize it as a similar feature in that language.
The argument placeholder reserves a temporary anonymous data object (called a
"cell" in Small) that is automatically destroyed after the function call.

The temporary cell for the argument placeholder should still have a value.
Therefore, a function must specify for each passed-by-reference argument what
value it will have upon entry when the caller passes the placeholder instead
of an actual argument. By extension, I also added default values for arguments
that are "passed-by-value". The feature to optionally remove all arguments
with default values from the right was copied from C++.

When speaking of BCPL and B, Dennis Ritchie said that C was invented in part
to provide a plausible way of dealing with character strings when one begins
with a word-oriented language. Small provides two options for working with
strings, packed and unpacked strings. In a packed string, every character
fits in a cell. The overhead for a typical 32-bit implementation is large: one
character would take four bytes. Packed strings store up to four characters in
one cell, at the cost of being significantly more difficult to handle if you
could only access full cells. Modern BCPL implementations provide two array
indexing methods: one to get a word from an array and one to get a character
from an array. Small copies this concept, although the syntax differs from
that of BCPL. The packed string feature also led to the new operator char.

Unicode applications often have to deal with two characters sets: 8-bit
for legacy file formats and standardized transfer formats (like many of
the Internet protocols) and the 16-bit Unicode character set. Although
the Small compiler has an option that makes characters 16-bit (so only two
characters fit in a 32-bit cell), a more convenient approach may be to store
8-bit character strings in packed strings and 16-bit (Unicode) strings in
                                                     Rationale  o  79

unpacked strings. This turns a weakness in Small, the need to distinguish
packed strings from unpacked strings, into a strength: Small can make that
distinction quite easily.

Notwithstanding the above mentioned changes, plus those in the chapter
"Pitfalls: differences from C" (page 44), I have tried to keep close to
C. For example, Small has the same operator set (with the exception of a few
operators that deal with structures and unions) as C. It is generally agreed
upon that some operators in this table have counterintuitive precedence. In
an expression parser that I wrote for the interactive multimedia development
system EGO, which has an equally large set of operators, I have had favorable
experiences with a different organization of operators in their precedence
levels. It would have been a simple step to adapt Small to the operator set
and the precedence levels that I prefer. For the sake of similarity with C, I
resigned from such a change.
80  o

                    Design of the abstract machine                  Appendix B

******************************************************************************
------------------------------------------------------------------------------

The first issue is: why an abstract machine at all? By compiling into the
native machine language of the processor of your choice, the performance will
be so much better.

There is only one real reason to use an abstract machine: cross-platform com-
patibility of the compiled binary code. At the time that Small was designed,
both 16-bit and 32-bit platforms on the 80x86 processor series were important
for me. By the time I can forget about 16-bit operating systems, alternate
microprocessors (like PowerPC and DEC Alpha) may have become essential.

Other reasons (while not essential) are:

* It is far easier to keep a program running in an abstract machine inside
  its "sandbox". For example, an unbounded recursion in an abstract machine
  crashes the abstract machine itself, but not much else. If you run native
  machine code, the recursive routine may damage the system stack and crash
  the application. Although modern operating systems support multithreading,
  with a separate stack per thread, the default action for an overrun of any
  stack is still to shut down the entire application.

* It is easier to design a language where a data object (an array) can contain
  bytecode which is later executed. Modern operating systems separate code and
  data sections: you cannot write into a code section and you cannot execute
  data; that is, not without serious effort.

  The current Small language does not have the ability to execute bytecode
  from an array, but the abstract machine is not too tightly coupled to the
  language. That is, future versions of the Small language may provide a means
  to execute a code stream from a variable without requiring me to redesign
  the abstract machine.

My first stab at designing an abstract machine was to look at current im-
plementations. It appears that it is some kind of a tradition to implement
                                   Design of the abstract machine  o  81

abstract machines as stack machines, even though the design for micropro-
cessors has moved towards register based implementations. All the abstract
machines I encountered are stack based. These include:

*  Microsoft C/C++ 7.0 (P-code option)*  Java VM (JVM)
*  Lua                            *  the B language (predecessor of C)
*  bob                            *  the Amsterdam Compiler Kit


Stack machines are surely compact, flexible and simple to implement, but they
are also more difficult to optimize for speed. To see why, let's analyze a
specific example.

       a = b + 2;     /* where "a" and "b" are simple variables */

Native code
In 32-bit assembler, this would be:

       mov     eax, [b]
       add     eax, 2
       mov     [a], eax

Stack based abstract machine
Forth is the archetype for a stack machine, I will therefore use it as an
example. The same routine in Forth would be:

       b @ 2 + a !

where each letter is an instruction (the "@" stands for "fetch" and "!"
for store; note that stack machines run code in "reverse polish notation").
So these are six instructions in bytecode, but the code expands to:

       b      push    offset b
       @      pop     eax
              push    [eax]
       2      push    2
       +      pop     edx
              pop     eax
              add     eax, edx
              push    eax
       a      push    offset a
       !      pop     edx
              pop     eax
              mov     [edx], eax
82  o  Design of the abstract machine

Two observations: 1. the stack machine makes heavy use of memory (bad for
performance) and 2. the expanded code is quite large when compared to the
native code (12 instructions versus 3).

The expanded code is what a "just-in-time" compiler (JIT) might make
from it (though one may expect an optimizing JIT to reduce the redundant
"pushes" and "pops" somewhat). When running the code in an abstract
machine, the abstract machine must also expand the code, but in addition, it
has overhead for fetching and decoding instructions. This overhead is at least
two native instructions per bytecode instruction (more on this later). For six
bytecode instructions, one should add another 12 native instructions to the 12
native instructions of the expanded code. And still, the example is greatly
simplified, because the code runs on the systems stack and uses the systems
address space.

In other words, a stack-based abstract machine runs a native 3-instruction
code snippet in 6 bytecode instructions, which turn out to take 24 native
instructions, and more if you want to run the abstract machine on its own
stack and in its own (protected) data space.

Register-based abstract machine
Microprocessors have use registers since their theoretical inception by Von
Neumann. Extending this architecture to an abstract machine is only natural.
There are two advantages: the abstract machine instructions map better to
the native instructions (you may actually use the processor's registers
to implement the abstract machine's registers) and the number of virtual
instructions that is needed to executed a simple expression can be reduced.

As an example, here is the code for the Small "AMX", a two-register abstract
machine (AMX stands for "Abstract Machine eXecutive"):

       load.pri    b   ; "pri" is the primary register, i.e. the accumulator
       const.alt   2   ; "alt" is the alternate register
       add           ; pri = pri + alt
       stor.pri    a   ; store "pri" in variable "a"

In expanded code, this would be:

       load.pri   b       mov   eax, [b]
       const.alt  2       mov   edx, 2
       add               add   eax, edx
       stor.pri   a       mov   [a], eax
                                   Design of the abstract machine  o  83

The four bytecode instructions map nicely to native instructions. Here again,
we will have to add the overhead for fetching and decoding the bytecode
instructions (2 native instructions per bytecode instruction). When compared
to a stack-based abstract machine, the register-based abstract machine runs
twice as fast; in 12 native instructions, versus 24 native instructions for a
stack-based abstract machine.

There is more: in my experience, stack-based abstract machines are easier to
optimize for size and register-based abstract machines are easier to optimize
for speed. So a register-based abstract machine can indeed be twice as fast as
a stack-based abstract machine.

To elaborate a little further on optimizing: I have intentionally chosen to
add "2" to a variable. Incrementing or decrementing a value by one or two
is such a common case that Forth has a special operator for them: the word
"2+" adds 2 to a value. Assuming that a good (stack-based) abstract machine
also has special opcodes for common operations, using this "2+" word instead
of the general words "2" and "+" removes one bytecode instruction and
3 native instructions. This would brings the native instruction count down
to 21. However, the same optimization trick applies to the register-based
abstract machine. The Small abstract machine has an "add.c" opcode that adds
a constant value to the primary register. The optimized sequence would be:

       load.pri  b        mov   eax, [b]
       add.c     2        add   eax, 2
       stor.pri  a        mov   [a], eax

which results to 3 native instructions plus 6 instructions of overhead for
fetching and decoding the bytecode instructions. The register-based abstract
machine (which needs 9 native instructions) is still approximately twice as
fast as the stack-based abstract machine (at 21 native instructions).


Threading

In an indirect threaded interpreter, each opcode is an index in a table
that contains a "jump address" for every instruction. In a direct threaded
interpreter, the opcode is the jump address itself. Direct threading often
requires that all opcodes are "relocated" to jump addresses upon compilation
or upon loading a pre-compiled file. The file format of the Small abstract
machine is designed such that both indirect and direct threading are possible.

A threaded abstract machine is conventionally written in assembler, because
most high level languages cannot store label addresses in an array. The GNU C
84  o  Design of the abstract machine

compiler (GCC), however, extends the C language with an unary "&&" operator
that returns the address of a label. This address can be stored in a "void
*" variable type and it can be used later in a goto instruction. Basically,
the following snippet does the same a "goto home":

       void *ptr = &&home;
       goto *ptr;

The ANSI C version of the abstract machine uses a large switch statement to
choose the correct instructions for every opcode. The GNU C version of the
abstract machine runs twice as fast as the ANSI C version. Fortunately, GNU C
runs on quite a few platforms. This means that the fast GNU C version is still
fairly portable.


Optimizing in assembler

The following discussion assumes an Intel 80386 or compatible processor. The
same technique also applies to 16-bit processors and to processors of other
brands, but the names (and number) of registers will be different.

It is beneficial to use the processor's registers to implement the registers
of the abstract machine. The details of the abstract machine for the Small
system are in appendix C. Further assumptions are:
* PRI is an alias for the processor's register EAX and ALT is EDX
* ESI is the code instruction pointer (CIP)
* table is an array of 32-bit addresses for every opcode
* EDI points to the start of the data segment, ECX is the stack pointer (STK),
  EBX is the frame pointer (FRM) and EBP is available as a general purpose
  intermediate register; the remaining registers in the AMX (STP and HEA, see
  appendix C) are local variables.

Every opcode has a set of machine instructions attached to it, plus a trailer
that branches to the next instruction. The trailer is identical for every
opcode. As an example, below is the implementation of the ADD.C opcode:

       add     eax, [esi]     ; add constant
       add     esi, 4         ; skip constant
       ; the code below is the same for every instruction
       add     esi, 4         ; pre-adjust instruction pointer
       jmp     [esi-4]        ; jump to address

Note that the "trailer" which chains to the next instruction via (direct)
threading consists of two instructions; this trailer was the origin of the
                                   Design of the abstract machine  o  85

premise of a 2-instruction overhead for instruction fetching and decoding in
the earlier analysis.

In the implementation of the abstract machine, one can hand-optimize the
sequences further. In the above example, the two "add esi, 4" instructions
can, of course, be folded into a single instruction that adds eight to ESI.
86  o

                      Abstract machine reference                    Appendix C

******************************************************************************
------------------------------------------------------------------------------

The abstract machine consists of a set of registers, a proposed (or imposed)
memory layout and a set of instructions. Each is discussed in a separate
section.


Register layout

The abstract machine mimics a dual-register processor. In addition to the two
"general purpose" registers, it has a few internal registers. Below is the
list with the names and description of all registers:
PRI  primary register (ALU, general purpose).
ALT  alternate register (general purpose).
FRM  stack frame pointer, stack-relative memory reads and writes are relative
     to the address in this register.
CIP  code instruction pointer.
DAT  offset to the start of the data.
COD  offset to the start of the code.
STP  stack top.
STK  stack index, indicates the current position in the stack. The stack runs
     downwards from the STP register towards zero.
HEA  heap pointer. Dynamically allocated memory comes from the heap and the
     HEA register indicates the top of the heap.

Notably missing from the register set is a "flags" register. The abstract
machine keeps no separate set of flags; instead all conditional branches are
taken depending on the contents of the PRI register.


Memory image

The heap and the stack share a memory block. The stack grows downwards from
STP towards zero; the heap grows upwards. An exception occurs when the
STK and the HEA registers collide. (An exception means that the abstract
machine aborts with an error message. There is currently no exception trapping
mechanism.)

Alternative layouts are possible. Specifically, an implementation may choose
to keep the heap and the stack in a separate memory block next to the memory
block for the code, the data and the prefix. The top of the figure represents
the lowest address in memory.
                                       Abstract machine reference  o  87

The file format is a dump of the memory image. That is, the binary file
starts with the prefix, and is followed by the code and data sections. The
heap and stack sections are not stored in the binary file, the abstract
machine can build them from information in the "prefix" section. The prefix
also contains startup information, and the definitions of native and public
functions.

All multiple byte values are stored with the low byte at the lower address
(Little Endian). This is valid for the prefix and for the generated code and
data.
   ---------------------------------------------------------------------------
   size     4 bytes   size of the memory image, excluding the stack/heap
   magic    2 bytes   must be F1E0 (hexadecimal), unless the code is password
                      protected
   version  2 bytes   required minimal version of the abstract machine
   flags    2 bytes   flags, see below
   defsize  2 bytes   size of a structure in the "native functions" and the
                      "public functions" tables
   cod      4 bytes   start of the code section
   dat      4 bytes   start of the data section
   hea      4 bytes   initial value of the heap, end of the data section
88  o  Abstract machine reference


   stp      4 bytes   stack top value (the total memory requirements)
   cip      4 bytes   starting address (main() function), zero if none
   num-exp  2 bytes   number of public functions
   exp-off  4 bytes   offset to the "public functions" table
   num-ext  2 bytes   number of native functions
   ext-off  4 bytes   offset to the "native functions" table
   public   variable  public functions table (see below)
   native   variable  native functions table (see below)
   ---------------------------------------------------------------------------

Each bit in the flags field contains one setting. Currently, the defined
settings are:
   ---------------------------------------------------------------------------
   0 if set, a character (in a packed string) is 16-bit
   1 if set, the file contains symbolic (debug) information
   ---------------------------------------------------------------------------

The fixed part of the prefix followed by the public functions table and the
native functions table. Each table contains zero or more records. The size
of these records is in the defsize field in the prefix. The public functions
records have the format:

   ---------------------------------------------------------------------------
   address  4 bytes       the address (relative to COD) of the function
   name     defsize - 4   the name of the public function
   ---------------------------------------------------------------------------

The format of the native functions table is very similar (see below). The
order of the records in the table is important, because the parameter of the
SYSREQ.C instruction is an index into the native functions table.

   ---------------------------------------------------------------------------
   address  4 bytes       used internally, should be zero in the file
   name     defsize - 4   the name of the native function
   ---------------------------------------------------------------------------


Instruction reference

Every instruction consists of an opcode followed by zero or one parameters.
Each opcode is one byte in size; an instruction parameter has the size of a
cell (usually four bytes). A few "debugging" instructions (at the end of the
list) form an exception to these rules: they have two or more parameters and
those parameters are not always cell sized.

Many instructions have implied registers as operands. This reduces the number
of operands that are needed to decode an instruction and, hence, it reduces
the time needed to decode an instruction. In several cases, the implied
                                       Abstract machine reference  o  89

register is part of the name of the opcode. For example, PUSH.pri is the name
of the opcode that stores the PRI register on the stack. This instruction has
no parameters: its parameter (PRI) is implied in the opcode name.

The instruction reference is ordered by opcode. The description of two opcodes
is sometimes combined in one row in the table, because the opcodes differ only
in a source or a destination register. In these cases, the opcodes and the
variants of the registers are separated by a "/".

The "semantics" column gives a brief description of what the opcode does.
It uses the C language syntax for operators, which are the same as those of
the Small language. An item between square brackets indicates a memory access
(relative to the DAT register, except for jump and call instructions). So,
PRI = [address] means that the value read from memory at location DAT + ad-
dress is stored in PRI.


  opcode mnemonic       parameters  semantics
  ---------------------------------------------------------------------------
   1/2   LOAD.pri/alt   address     PRI/ALT = [address]
   3/4   LOAD.S.pri/alt offset      PRI/ALT = [FRM + offset]
   5/6   LREF.pri/alt   address     PRI/ALT = [ [address] ]
   7/8   LREF.S.pri/alt offset      PRI/ALT = [ [FRM + offset] ]
   9     LOAD.I                     PRI = [PRI] (full cell)
   10    LODB.I         number      PRI = "number" bytes from [PRI] (read 1/2/4 bytes)
   11/12 CONST.pri/alt  value       PRI/ALT = value
   13/14 ADDR.pri/alt   offset      PRI/ALT = FRM + offset
   15/16 STOR.pri/alt   address     [address] = PRI/ALT
   17/18 STOR.S.pri/alt offset      [FRM + offset] = PRI/ALT
   19/20 SREF.pri/alt   address     [ [address] ] = PRI/ALT
   21/22 SREF.S.pri/alt offset      [ [FRM + offset] ] = PRI/ALT
   23    STOR.I                     [ALT] = PRI (full cell)
   24    STRB.I         number      "number" bytes at [ALT] = PRI (write 1/2/4 bytes)
   25    LIDX                       PRI = [ ALT + (PRI x cell size) ]
   26    LIDX.B         shift       PRI = [ ALT + (PRI  shift) ]
   27    IDXADDR                    PRI = ALT + (PRI x cell size) (calculate indexed address)
   28    IDXADDR.B      shift       PRI = ALT + (PRI  shift) (calculate indexed address)
   29/30 ALIGN.pri/alt  number      Little Endian: PRI/ALT  ^= cell size- number
   31    LCTRL          index       PRI is set to the current value of any of the special registers.
                                    The index parameter must be: 0=COD, 1=DAT, 2=HEA,
                                    3=STP, 4=STK, 5=FRM, 6=CIP (of the next instruction)
   32    SCTRL          index       set the indexed special registers to the value in PRI.
                                    The index parameter must be: 2=HEA, 4=STK, 5=FRM,
                                    6=CIP
90  o  Abstract machine reference


   33/34 MOVE.pri/alt               PRI=ALT / ALT=PRI
   35    XCHG                       Exchange PRI and ALT
   36/37 PUSH.pri/alt               [STK] = PRI/ALT, STK = STK - cell size
   38    PUSH.R         value       Repeat value x: [STK] = PRI, STK = STK - cell size
   39    PUSH.C         value       [STK] = value, STK = STK - cell size
   40    PUSH           address     [STK] = [address], STK = STK - cell size
   41    PUSH.S         offset      [STK] = [FRM + offset], STK = STK - cell size
   42/43 POP.pri/alt                STK = STK + cell size, PRI/ALT = [STK]
   44    STACK          value       ALT = STK, STK = STK + value
   45    HEAP           value       ALT = HEA, HEA = HEA + value
   46    PROC                       [STK] = FRM, STK = STK - cell size, FRM = STK
   47    RET                        STK = STK + cell size, FRM = [STK],
                                    STK = STK + cell size, CIP = [STK],
                                    The RET instruction cleans up the stack frame and returns
                                    from the function to the instruction after the call.
   48    RETN                       STK = STK + cell size, FRM = [STK],
                                    STK = STK + cell size, CIP = [STK],
                                    STK = STK + [STK]
                                    The RETN instruction removes a specified number of bytes
                                    from the stack. The value to adjust STK with must be
                                    pushed prior to the call.
   49    CALL           address     [STK] = CIP + 5, STK = STK - cell size
                                    CIP = address
                                    The CALL instruction jumps to an address after storing the
                                    address of the next sequential instruction on the stack.
   50    CALL.I                     [STK] = CIP + 1, STK = STK - cell size
                                    CIP = PRI
                                    jumps to the address in PRI after storing the address of the
                                    next sequential instruction on the stack.
   51    JUMP           address     CIP = address (jump to the address)
   52    JREL           offset      CIP = CIP + offset (jump "offset" bytes from current
                                    position)
   53    JZER           address     if PRI == 0 then CIP = [CIP + 1]
   54    JNZ            address     if PRI != 0 then CIP = [CIP + 1]
   55    JEQ            address     if PRI == ALT then CIP = [CIP + 1]
   56    JNEQ           address     if PRI != ALT then CIP = [CIP + 1]
   57    JLESS          address     if PRI  ALT then CIP = [CIP + 1] (unsigned)
   58    JLEQ           address     if PRI  = ALT then CIP = [CIP + 1] (unsigned)
   59    JGRTR          address     if PRI  ALT then CIP = [CIP + 1] (unsigned)
   60    JGEQ           address     if PRI  = ALT then CIP = [CIP + 1] (unsigned)
   61    JSLESS         address     if PRI  ALT then CIP = [CIP + 1] (signed)
                                       Abstract machine reference  o  91


   62    JSLEQ          address     if PRI  = ALT then CIP = [CIP + 1] (signed)
   63    JSGRTR         address     if PRI  ALT then CIP = [CIP + 1] (signed)
   64    JSGEQ          address     if PRI  = ALT then CIP = [CIP + 1] (signed)
   65    SHL                        PRI = PRI  ALT
   66    SHR                        PRI = PRI  ALT (without sign extension)
   67    SSHR                       PRI = PRI  ALT with sign extension
   68    SHL.C.pri      value       PRI = PRI  value
   69    SHL.C.alt      value       ALT = ALT  value
   70    SHR.C.pri      value       PRI = PRI  value (without sign extension)
   71    SHR.C.alt      value       ALT = ALT  value (without sign extension)
   72    SMUL                       PRI = PRI * ALT (signed multiply)
   73    SDIV                       PRI = PRI / ALT (signed divide), ALT = PRI mod ALT
   74    SDIV.alt                   PRI = ALT / PRI (signed divide), ALT = ALT mod PRI
   75    UMUL                       PRI = PRI * ALT (unsigned multiply)
   76    UDIV                       PRI = PRI / ALT (unsigned divide), ALT = PRI mod ALT
   77    UDIV.alt                   PRI = ALT / PRI (unsigned divide), ALT = ALT mod PRI
   78    ADD                        PRI = PRI + ALT
   79    SUB                        PRI = PRI - ALT
   80    SUB.alt                    PRI = ALT - PRI
   81    AND                        PRI = PRI & ALT
   82    OR                         PRI = PRI |ALT
   83    XOR                        PRI = PRI   ^ALT
   84    NOT                        PRI = !PRI
   85    NEG                        PRI = -PRI
   86    INVERT                     PRI = ~PRI
   87    ADD.C          value       PRI = PRI + value
   88    SMUL.C         value       PRI = PRI * value
   89/90 ZERO.pri/alt               PRI/ALT = 0
   91    ZERO           address     [address] = 0
   92    ZERO.S         offset      [FRM + offset] = 0
   93/94 SIGN.pri/alt               sign extent the byte in PRI or ALT to a cell
   95    EQ                         PRI = PRI == ALT ? 1 : 0
   96    NEQ                        PRI = PRI != ALT ? 1 : 0
   97    LESS                       PRI = PRI  ALT ? 1 : 0 (unsigned)
   98    LEQ                        PRI = PRI  = ALT ? 1 : 0 (unsigned)
   99    GRTR                       PRI = PRI  ALT ? 1 : 0 (unsigned)
  100    GEQ                        PRI = PRI  = ALT ? 1 : 0 (unsigned)
  101    SLESS                      PRI = PRI  ALT ? 1 : 0 (signed)
  102    SLEQ                       PRI = PRI  = ALT ? 1 : 0 (signed)
  103    SGRTR                      PRI = PRI  ALT ? 1 : 0 (signed)
  104    SGEQ                       PRI = PRI  = ALT ? 1 : 0 (signed)
92  o  Abstract machine reference


  105    EQ.C.pri       value       PRI = PRI == value ? 1 : 0
  106    EQ.C.alt       value       PRI = ALT == value ? 1 : 0
  107/108 INC.pri/alt               PRI = PRI + 1 / ALT = ALT + 1
   109   INC            address     [address] = [address] + 1
   110   INC.S          offset      [FRM + offset] = [FRM + offset] + 1
   111   INC.I                      [PRI] = [PRI] + 1
  112/113 DEC.pri/alt               PRI = PRI - 1 / ALT = ALT - 1
   114   DEC            address     [address] = [address] - 1
   115   DEC.S          offset      [FRM + offset] = [FRM + offset] - 1
   116   DEC.I                      [PRI] = [PRI] - 1
   117   MOVS           number      Copy memory from [PRI] to [ALT]. The parameter
                                    specifies the number of bytes. The blocks should not
                                    overlap.
   118   CMPS           number      Compare memory blocks at [PRI] and [ALT]. The parameter
                                    specifies the number of bytes. The blocks should not
                                    overlap.
   119   FILL           number      Fill memory at [ALT] with value in [PRI]. The parameter
                                    specifies the number of bytes, which must be a multiple
                                    of the cell size.
   120   HALT           0           Abort execution (exit value in PRI), parameters other than 0
                                    have a special meaning.
   121   BOUNDS         value       Abort execution if PRI  value or if PRI  0
   122   SYSREQ.pri                 call system service, service number in PRI
   123   SYSREQ.C       value       call system service
   124   FILE           size ord name         source file information pair:
                                              name and ordinal (see below)
   125   LINE           line ord              source line number and file
                                              ordinal (see below)
   126   SYMBOL         size offs flgs name   symbol information (see below)
  ---------------------------------------------------------------------------


Cross-platform support

There is some level of cross-platform support in the abstract machine. Both
Big Endian and Little Endian memory addressing schemes are in common use
today. Big Endian is the "network byte order", as it is used for various
network protocols, notably the Internet protocol suite. The Intel 80x86 and
Pentium CPU series use Little Endian addressing.

The abstract machine is optimized for manipulating "cells", 32-bit quantit-
ies. Bytes or 16-bit words can only be read or written indirectly, by first
generating an address and then use the LODB.I or STRB.I instructions. The
ALIGN.pri instruction helps in generating the address.
                                       Abstract machine reference  o  93

The abstract machine assumes that when multiple characters are packed in a
cell, the first character occupies the highest bits in the cell and the last
character is in the lowest bits of the cell. This is how the Small language
stores packed strings (see page 23). On a Big Endian computer, the order of
the characters is "natural" in the sense that the first character of a pack
is at the lowest address and the last character is at the highest address.
On a Little Endian computer, the order of the characters is reversed. When
accessing the second character of a pack, you should read/write from a lower
address then when accessing the first character of the pack.

The Small compiler could easily generate the required extra code to adjust
the address for each character in the pack. The draw-back would be that a
module written for a Big Endian computer would not run on a Little Endian
computer and vice versa. So instead, the Small compiler generates a special
ALIGN instruction, whose semantics depend on whether the abstract machine
runs on a Big Endian or a Little Endian computer. More specifically, the
ALIGN instruction does nothing on a Big Endian computer and performs a simple
bitwise "exclusive or" operation on a Little Endian computer.


Debugger support

There is limited support for source level debuggers, built-in in the instruc-
tion set. These opcodes are not "regular" in the sense that they have more
than one parameter.

The size parameter of the FILE and SYMBOL instructions gives the length of the
instruction in bytes, excluding the bytes for the opcode and of the size field
itself. The value of the size should always be a multiple of the size of a
cell.

The name parameter of the FILE and SYMBOL instructions is a variable length,
zero terminated string.

The ord parameter of the FILE and LINE instructions and the offs parameter of
the SYMBOL instruction are regular cell-sized parameters. The line parameter
of the LINE instruction also has the size of a cell.

The flgs parameter of the SYMBOL opcode holds the class and the type of the
symbol. The type is in the lowest byte; it is one of the following values:
1    a variable
2    a "reference", a variable that contains an address to another variable
     (in other words, a pointer).
3    an array
94  o  Abstract machine reference

4    a reference to an array (a pointer to an array)
9    a function
10   a reference to a function (a pointer to a function)

The class is in the second byte; its value is zero (0) if the symbol refers to
a global variable or to a function, and one (1) for a local variable.

The "offs" parameter is relative to either:
COD  if the symbol refers to a function
DAT  if the symbol refers to a global variable
FRM  if the symbol refers to a local variable

An instruction for symbolic information is stored near the place where the
variable or function to which it refers is created or declared. For local
symbols, the symbolic information precedes the instructions that allocate, and
optionally fill, the stack space for the variable(s). There is no run-time
allocation for global symbols; therefore a symbolic debugger must browse
through the code section to parse the symbolic information instructions and
to collect the global symbols. This strategy was chosen as a compromise that
minimized the overall effort to add symbolic debugging support to the compiler
and to create a debugger. Writing the compiler was much easier when the
symbolic information could be written where the variable was declared in the
source code. A debugger should have a disassembler anyway. Combining these two
resulted in decent debugger support with a low cost in terms of complexity.

The Small compiler generates a LINE instruction before any other instruction
for that line. The "ord" parameter is the file number to which the line
relates. The Small compiler generates the FILE instruction at the point
where the file is read. So a debugger would gather the filenames (and their
ordinals) in the same way (and perhaps in the same phase) as the global
symbols.
                                                               o  95

                        Code generation notes                appendix d

******************************************************************************
------------------------------------------------------------------------------

The code generation of the Small compiler is fairly straightforward (also due
to the simplicity of the abstract machine). A few points are worth mentioning:

* The abstract machine has instructions that the Small compiler currently
  does not generate. For example, the LREF.pri instruction works like the
  dereference operator ("*") in C/C++. Small does not support pointers
  directly, but references are just pointers in disguise. Small only supports
  references in function arguments, however, which means that the "pointer
  operations" in Small are always stack-relative. In other words, the Small
  compiler does not generate the LREF.pri instruction, although if does
  generate the LREF.S.pri instruction.

  The abstract machine is fairly independent from the Small language, even
  though they were developed for each other. The Small language can easily
  grow in the future, possibly with a "reference" variable type, thereby
  giving the LREF.pri instruction a reason of being. The abstract machine
  cannot easily grow, however, because new instructions immediately make the
  new abstract machine incompatible with previous versions. That is, programs
  compiled for the new abstract machine won't run on the earlier release.

* For a native function, the Small compiler generates a SYSREQ.C instruction
  instead of the normal function call. The parameter of the SYSREQ.C instruc-
  tion is an index in the native function table. A function in Small cleans
  up its arguments that were pushed on the stack, because it returns with the
  RETN instruction. The SYSREQ.C instruction does not remove items from the
  stack, so the Small compiler does this explicitly with a STACK instruction
  behind the SYSREQ.C instruction.

  The arguments of a native function are pushed on the stack in the same
  manner as for a normal function.

  In the "Small" implementation of the abstract machine (see page 59), the
  "system request" instructions are linked to the user-installed callback
  function. Thus, a native function in a Small program issues a call to a
  user-defined callback function in the abstract machine.
96  o  Code generation notes

* At a function call, a Small program pushes the function arguments onto
  the stack in reverse order (that is, from right to left). It ends the list
  of function arguments on the stack by pushing the number of bytes that
  it pushed to the stack. Since the Small compiler only passes cell-sized
  function arguments to a function, the number of bytes is the number of
  arguments multiplied by the size of a cell.

  A function in Small ends with a RETN instruction. This instruction removes
  the function arguments from the stack.

* When a function has a "reference" argument with a default value, the
  compiler allocates space for that default value on the heap.

* The arguments of a function that has "variable arguments" (denoted
  with the ... operator, see page 17) are always passed by reference. For
  constants and expressions that are not lvalues, the compiler copies the
  values to a cell that is allocated from the heap, and it passes the address
  of the cell to the function.
                                                               o  97

                               Index

******************************************************************************
------------------------------------------------------------------------------



* Names of persons (not products) are in italics.
* Function names, constants and compiler reserved words are in typewriter
  font.



Abstract Machine eXecutive, 59--72
  design, 82
  file format, 87
  opcodes, 89
  registers, 86
  stack based, 80
Argument placeholder, 16            Data declarations, 8--9
Arrays, 8                            arrays, 8
  Progressive initiallers, 9         default initialization, 8
ASCII, 25, 49                        global, 8
Assembler, 83, 84                    local, 8
Assertions, 25, 76
                                    Default arguments, 16
                                    Default initialization, 8
BCPL, 78                            Diagnostic, 11
Big Endian, 23                      Directives, 36--38
Binary radix, 22, 44
BOB, 75, 81
Byte order, 87                      EGO, 79

                                    Ellipsis, 17

Cain, Ron, 1                        enum, 24
Call by value, 13                   Eratosthenes, 5
char, 44                            Errors, 50--58
Coercion rules, 17                   run-time, 72
Comments, 21
Constants, 22                       Escape characters, 4
  predefined, 24                    Euclides, 4
Control characters, 22              Extension modules, 61, 95
98  o  Index


Faculty, 13
Fibonacci, 6
Fibonacci numbers, 6                Latin-1 (character set), See ISO Latin-
Fixed point arithmetic, 42           1
Floating point, 42                  LBF (Low Byte First), See Little Endian
Forth, 81                           Leap year, 12
Function library, 39                Leonardo of Pisa, 6
Functions, 11--20                   Little Endian, 87
  call by reference, 13             Local variables, 8
  call by value, 13                 Low Byte First, See Little Endian
  coercion rules, 17
  default arguments, 16             Lua, 81
  index, 39                         lvalue, 25
  native, 61
  prototype, 11
  public, 19                        Named parameters, 15
  standard library, 39              Native functions, 20, 61
  variable arguments, 17

                                    Octal radix, 44
Global variables, 8                 Operator precedence, 31
GNU C, 83                           Operators, 25--31
Golden ratio, 6
Greatest Common Divisor, 4
                                    Packed string, 23, 40, 45, 78
                                    Placeholder, See Argument placeholder
Hanoi, the Towers of ~, 18          Positional parameters, 15
Hendrix, James, 1                   power, 12
Hexadecimal radix, 22, 44           Precedence table, 31

                                    Prime numbers, 5

Identifiers, 21                     Progressive initiallers, 9
Implicit conversions, See coercion  Prototypes, 11
  rules                             Public functions, 19
Internet, 78                         index, 39
ISO Latin-1, 25, 49

                                    Recursive functions, 18
Java, 74, 81                        Reference arguments, 13
                                    Reserved words, 21
                                    REXX, 75
Keywords, See reserved words        Ritchie, Dennis, 74, 78
                                                         Index  o  99


Scaled integers, See Fixed point arithmetic
Small C, 1                          The Towers of Hanoi, 18
Sorenson, P., 77                    Thompson, Ken, 81
Standard function library, 39       Threading, 83
Statements, 33--36                  Tremblay, J.P., 77
Stevens, Al, 1
String
  packed, 23, 40, 45, 78            Unicode, 25, 49, 78, 88
  unpacked, 23, 40, 45, 78          Unpacked string, 23, 40, 45, 78
Subject oriented, 77
Symbolic information, 49, 93
Syntax rules, 21                    Variable arguments, 17
                                    Variables, See Data declarations
                                    Virtual machine, See Abstract machine
Tagname, 10                         Von Neuman, 82
  and enum, 24
  override, 11, 31
  predefined, 25                    Warnings, 56--58
  syntax, 25                        weekday, 15, 36
Tagnames, 77                        White space, 21
