Preliminary Specification of the BX Programming Language

                               Rich Skrenta
                               Tom Markson

                               August 1990



       BX is designed to be compiled for standard machine architectures
       but still provide powerful facilities often found only in
       interpretive languages.  Safety has been emphasized in BX with
       regard to type checking and traditionally problematic areas such
       as pointers and unions.


       2.  Overview of BX

       2.1  Some Notations

       Comments in BX extend from a # symbol to the end of a line.
       For example,

            x := y;       #  This is a comment
            y := 10;      #  So is this

       As with C, when a program is run the proc or func "main" is
       called first.  If the program needs to return a completion
       status, an integer function "main" should be used.

       "Procedure" in this document refers to 'proc', 'func' and
       'generator' interchangeably.  When it matters, proc, func or
       generator will be specified.

       2.2  Primary Constructs

       A BX program is a series of definitions.  In addition to
       variable declarations, a definition may be one of the
       following:

              box        Similar to a Pascal record or a C struct,
                         but may hold definitions of the other
                         primary constructs such as proc, func,
                         etc. as well.

              concept    Represents a set a properties a box must
                         have to match the concept.

              func       A standard function declaration.

              generator  Produces instantiations of a series of
                         variables.  Used by the for loop.

              proc       A standard procedure declaration.

              take       Defines a function which may appear on the
                         left side of an assignment statement.

              union      May hold only one of its components at a
                         time.  The tag on a union is implicit and
                         maintained by the compiler.



       3.  BX Constructs

       3.1  Atomic Data Types

       BX supports the standard atomic data types.  Declarations
       follow the C syntax:

            int x;       # declares an integer
            char c;      # declares a character
            float f;     # declares a real number
            double d;    # declares a doulbe precision real
            short s;     # declares a short integer
            bool b;      # boolean value, either true or false
            long l;      # long integer
            complex u4;  # complex variable, real and imaginary parts
            ushort u1;   # unsigned short
            uint u2;     # unsigned integer
            ulong u3;    # unsigned long

       3.1.1  Assignment

       The assignment symbol in BX is ':='.  The equality symbol is '=='.
       The single character '=' symbol is not valid in BX.  This was
       done to avoid the confusion that '=' often causes.  The ':='
       is used only as assignment in other programming languages,
       including Pascal.  '==' is used for equality in C.  However,
       '=' alone is used for assignment in C, for equality in Pascal,
       and for both in many other languages.  Thus, to avoid confusion
       and to make the programmer "say what he means" we decided not to
       use the '=' character at all.

       Assignment can be applied to aggregate structures as well as
       atomic types:

            box foo {
                int i;
                char c;
            }

            foo A,B;

            A := B;     # copies entire contents of B
                        # into A

       To assign a complex number to a variable, use the form

            complex_variable:=<real part>i<imaginary part>

       For example, the following are all valid assignments to
       complex variables:


            u4:=10i5           # assignment complex 10real, 5imaginary to u4
            u4:=10.123i56.12
            u4:=-5i-4          # assigns -5real, -4imaginary to u4
            u4:=5i-4           # assigns 5real , -4imaginary to u4

       3.1.2  Pointers

       BX includes pointers but restricts them in attempt to make
       them less dangerous to use.  BX also provides automatic
       memory allocation and garbage collection (provided by a
       compiler-maintained refenence count associated with the target
       of the pointer, when necessary).  Pointers are declared with the
       "ref" keyword:

            ref int x;   # x is a pointer to an integer
                         # x is initially NULL;
                         #   this is guaranteed by the compiler

            assert (x == NULL);  # generate a run-time error if x != NULL

            x^ := 12;    # Compiler will allocate memory for
                         # the integer and store 12 in it

            x := NULL;   # Compiler will free the memory pointed
                         # to by x

       Pointers can be assigned to other pointers.  The compiler
       will maintain the reference count associated with the object
       that the pointers refer to.

            ref int x,y;

            x^ := 12;     # allocates space for an int
                          # and stores 12 in it

            y := x;       # y now points to the 12 also;
                          # a reference count associated with
                          # the integer now indicates that two
                          # pointers point to it

            x := NULL;    # the reference count is decremented, but
                          # the memory is not freed because y still
                          # points to it

            y := NULL;    # the reference count becomes zero
                          # the memory is freed

       If the compiler can determine that only one pointer will
       point to an object, it may decide to omit the reference
       count.

       If a structure which contains non-NULL pointers is freed, BX
       will signal a run-time error.  Before a block of memory is
       freed, however, the proc "auto_done" associated with the box
       will first be called.  This gives the box a chance to
       deallocate its own pointers.  For example:

            box foo {
                int x;
                ref foo a;
            }

            ref foo ptr;

            ptr^.x := 12;
            ptr^.a^.x := 14;

            ptr := NULL;

       The foo box referred to by ptr has a non-NULL pointer 'a'.
       This will generate a run-time error.

       3.2  Proc and Func Definition

       BX procedures, defined by the 'proc' keyword, are similar to
       procedures in other languages such as Pascal.  BX functions,
       defined by the 'func' keyword, are also similar to Pascal
       functions.  BX procs and funcs may take value or reference
       parameters.

            proc Sample_Procedure (int x; var char c) {
                x := 12;
                c := 'a';
            }

            int num := 0;
            char letter := 'z';

            func factorial (int num) {
                if (num <= 1)
                    factorial := 1;
                else
                    factorial := num * factorial(num - 1)
            }

            proc main{
            int x;
                    Sample_Procedure (num,letter);
                    assert (num == 0);
                    assert (letter == 'a');
                    x:=factorial(5);
                    assert (x == 120);
            }


       3.2.1  Return_Codes

       It is often necessary to signal various conditions returned from
       a procedure.  Often functions which return integer codes to the
       caller will be used to signal a condition.  Also, procedures
       often need to return information to the caller depending
       on the completion status.  Global variables are often used
       to communicate this information, or a pointer to a temporary
       structure is returned.  C makes extensive use of embedded return
       information in function return values.  However, this technique
       can be error prone and confusing, as different "special values"
       are used for each function.  For example, in C the 'fopen()'
       call returns NULL if it fails, whereas 'open()' returns -1.

       Because return codes are commonly used, and since there is a
       clear need to be able to return different information to the
       caller depending on the return code, BX supports these ideas
       directly.  Return codes can be specified after the formal
       parameter list of a procedure (but not a function) before
       the '{' symbol.  Additionally, the return codes can be
       parameterized with the types they will return to the caller.
       For example

            proc do_something (int x)
                ret ERROR(int,int);
                ret WARNING(int);
                ret SUCCESS(char);
            {
            const int errnum := 10, severity := 20;

                if (x < 0)
                    return ERROR(errnum,severity);
                else if (x == 0)
                    return WARNING(10);
                else
                    return SUCCESS('a');
            }

            do_something(0) {
                case ERROR(int errno,sever):
                    printf("Error number %d, severity %d",errno,sever);
                case WARNING(int warning_num):
                    printf("Warning number: %d",warning_num);
                case SUCCESS(char c):
                    printf("got the char: %c",c);
            }

       Using return codes in this way makes the code neater and the
       function more obvious.  There no longer need to be constant
       definitions for integer return codes from functions, nor do
       there need to be "special values" tucked into the return
       value from a function.  The compiler will handle the
       implementation of the return and ensure that no incorrect
       return codes are specified.  Global variables are no longer
       necessary to communicate information back to the caller, nor
       does the caller need to extract values from a temporary
       returned structure.

       Return codes may not be specified after a function because
       they may be used in expressions, and the syntactic solutions
       to allowing returns codes in such a case are not obvious.
       Also, procedures with return codes can return values,
       although not to expressions.  Hopefully by removing the case
       of returing status codes to function callers with optional
       parameters from functions will allow them to be used more
       selectively, and code that needs to make use of return codes
       will be checkable by the compiler and will no longer need
       global variables or pointers to structures for
       communication.

       3.3  Give

       A complement to the take construct is the give construct.
       Give is very similar to func, except it instantiates a
       variable rather than returning a value.  This allows
       take/give pairs to be used to construct dotted chains:

            foo(n).bozo(f).bar(z) := 10;

       In this case, foo and bozo must both be give definitions,
       and bar must be a take.  The definition for a give contains
       the 'produce' statement instead of an assignment to the
       function variable:

            give int foo(int n) {
                produce X[n];         # must be a variable reference
            }

       3.4  Take Definition

       Given a reference to a function, the function will produce a value.
       A take, on the other hand, is the inverse of a function.  The value
       assigned to the take is brought into the take body.  For example:

            func int max(int x,y) {         # func returns an int
                if (x > y)
                    max:=x;                 # if x > y return x
                else
                    max:=y;                 # else return y
            }

            take int max(var int x,y) {     # take accepts an int
                if (x>y)
                    x:=max;                 # will assign value to whichever variable
                else                        # is greater
                    y:=max;
            }

            proc main {
            int x:=1, y:=3;                 # declare and initialize

                printf("%d",max(x,y));      # func call
                max(x,y):=100;              # take call
                assert (x == 1);
                assert (y == 100);
            }

       Take and func may have the same name and the compiler will
       differentiate between them.  In the take call
       "max(x,y):=100", the value 100 is bound to max; so x:=max
       actually becomes "x:=100" when the take is called.

       This is a feature unique to BX.  Take together with func (or
       give, described later) tend to go together to create a
       virtual variable.  That is, a pair of func/takes may
       actually appear as, and operate as a standard variable. For
       example:

       func int foo {
               printf("foo was called");
               foo:=1;
       }
       take int foo {
               printf("foo was assigned to %d",foo);
       }
       foo:=1; # will generate:
       foo was assigned to 1
       x:=foo; # will result in:
       foo was called

       Thus, with take, we have essentially created the possibility
       of two-way functions.  These may be used in place of
       standard variables. Take/func pairs are used extensively in
       BX even if the programmer is unaware of it.  For example, an
       array makes use of take and func to generalize the accessing
       of its values by index:

            x[15]:=12;      is identical to   x.index(15):=12;
            y:=x[15];       is identical to   y:=x.index(15);

       So, when you access an array, you may actually be calling a
       take or func to perform the work.  This allows any box which
       has a take/func pair called index to be treated as an array,
       no matter what else the box contains.  In other words, the
       programmer may allow any data structure to be treated as an
       array simply by providing a take/func pair called "index".
       Since take/func pairs are treated as if they are variables,
       the following are legal:

            x[15] := x[15] + 1;           # x.index(15):=x.index(15)+1;
            max(x,y) := max(x,y) / 100;

                # becomes:
                #
                #   if (x > y)
                #       x := 100;
                #   else
                #       y := 100;

       Thus, take/func pairs may be used in expressions as long as
       take appears on the left side of the assignment and func
       appears on the right.  Take and func may appear alone,
       however.  One does not require the other.

       3.5  Box Definition and Use

       The box is the primary data constructor in BX.  It is
       similar to a Pascal record or a C struct, except it may
       contain code as well as data.  For example,

            box foo {
                int x;
                char c;
            }

       declares a box type "foo" which contains an integer x and a
       character c.

            foo bozo;

       would declare a variable "bozo" of type foo.  The elements
       are accessed by naming them:

            bozo.x := 10;
            bozo.c := 'a';

       In addition to containing variables, boxes may also group
       procedural code.  We could include an initialization
       procedure in box foo:

            box foo {
                int x;
                char c;

                proc init {
                    x := 10;
                    c := 'a';
                }
            }

       Now invoking the "init" procedure has the same effect as
       assigning the elements directly:

            bozo.init;

       Boxes may contain all of the procedural and data structure
       constructs.

       Box type definitions may be parameterized to make them more
       general: For example, suppose we wanted to construct a
       binary tree of records, each containing one integer.  We
       might use

            box data {
                int value;
                ref data left,right;
            }

       to declare our node containing the integer "value" and left
       and right pointers.  However, this is not a general
       solution.  Storing the data along with the organization
       information (the left and the right pointers) makes the
       design brittle.  If we decided to organize the integers in a
       hash table instead, for example, we would have to change all
       of the references to box data.  Similarly, code written to
       operate on trees constructed with the above record is not
       generalizable to trees containing other data.

       A much better approach is to parameterize the box definition
       to allow box templates to be defined, and instantiated upon
       declaration.  We separate the definition of the node data
       from the definition of the node itself:

            box data {
                int value;
            }

            box node <type T> {
                T info;
                ref node left, right;
            }

       our declaration then becomes:

            node<data> X;

       The above box type only defines the node type of the tree,
       however.  A complete description of a tree requires the
       pointer to the base of the tree as well as code to implement
       operations on a tree.  A more practical definition of a tree
       might look like

            box tree <type T> {
                box node {
                    T data;
                    ref node left, right;
                }

                ref node head;

                proc insert (T entry) {
                    if (head == NULL)
                        head^ := entry;
                    else {
                    ref node tmp := head, back_ptr;

                        do {
                            back_ptr := tmp;
                            if (tmp^.data < entry)
                                tmp := tmp^.left;
                            else
                                tmp := tmp^.right;
                        } until (tmp == NULL);
                        if (back_ptr^.data < entry)
                            back_ptr^.left^.data := entry;
                        else
                            back_ptr^.right^.data := entry;
                    }
                }
            }

       This declares a box which implements a generic tree, with
       one operation, insert.  Note that pointers are automatically
       set to NULL upon definition, so explicitly initializing them
       is not necessary.  Trees of various types can be declared
       given the above definition:

            box foo {
                int x;
                char c;
            }

            tree <int> X;         # declares X as a tree of integers
            X.insert(12);         # add the value 12 to the tree

            tree <foo> Y;         # declares Y as a tree of box foo
            foo tmp;

                tmp.x := 12;
                tmp.c := 'a';

                Y.insert(tmp);    # insert tmp into Y

       Procedures which are passed boxes in their formal parameter
       lists are not restricted to accepting instantiated boxes
       only.  Variables may be specified in the parameter lists to
       conform to whatever box type is passed to the procedure.
       For example, a procedure which only took a tree of integers
       as a parameter could be specified by

            proc restricted_procedure (tree <int> X) {
            int local_variable;

                    # X may only be a tree of integers
            }

       However, the procedure may also have variables which will
       conform to the type of the box passed to it:

            proc general_procedure (tree <type T> X) {
            T local_variable;

                    # X may be a tree of any type
                    # Local_Variable will be of the same
                    #   type as the contents of the tree
            }

       3.5.1  Special_Procedures  There are two special procs which
       may be associated with each box:  auto_init and auto_done.
       Auto_init is called when the box is created.  If the box is
       created by a pointer assignment, auto_init will be called
       just after the memory has been allocated for the box.
       Auto_done is called just before a box is destroyed.  This
       would occur just before deallocation of the memory for the
       box.  In the case of global boxes, auto_init will be called
       before proc main is called, and auto_done after main
       terminates.


       4.  Instantiation

       Instantiation is the process by which a generalized proc,
       func, take, give or type is reduced to a distinct and
       unit.In the case of a variable declaration, instantiation
       produces a specific variable type from a parameterized box
       definition.  This can be illustrated with a standard BX
       array declaration :

            array<int,20> x

       Array is a parameterized box definition, and x is a specific
       instance of array.  Any box which is parameterized must be
       instantiated when a variable is declared of its type.
       Procedures may accept fully instantiated types as paramters.
       However, procedures may also be written to conform to any
       instantiation of a box definition.  For example:

            box array<type T;int size> {
                # definition of 'array'
            }

       Thus, when you declare array<int,20> X, int is bound to T in
       the array declaration and 20 is bound to size.  The box is
       "rewritten" by the compiler with all references to T changed
       to int and all references to size changed to 20.  X is then
       bound to this new type.

       Any box may be parameterized. For example :

            box foo <type S; int size> {
                array<S,size> V;
            }

                # create an instance of that box in k

            foo<char,200> K;

       When invoked, this will make an instance of type foo which
       will create an array of 200 chars inside of box foo.  While
       this is a trivial example, it begins to show the power of
       type instantation.

       The box is given a new name so foo may be instanciated to
       different types without name collisions.  A procedure may be
       written to take advantage of type instantiation :

            proc bar (foo<type T; int size> parm ) {
            T x;
            int i:=0;

                while (i < size) {
                    x:=parm.V[i];
                    i := i + 1;
                }
            }

       This permits data structures that are similar in structure
       but which contain different types to be used in one
       procedure.  An excellent example of this is when the
       following statements are given:

            proc main {
                foo<float,100> real;
                foo<int,100> simple;
                bar(simple);
                bar(real);
            }

       Procedure bar can therefore be used to process both floats
       and ints without any change to the procedure code.

       Note that run-time instantiation is not allowed.  The
       arguments to parameterized boxes must be constant at compile
       time.

       4.1  Union Definitions

       BX provides a union type similar to C's, except that the
       union tag is provided by BX and automatically maintained by
       the compiler.  This was done because the union in C is
       almost always declared nested inside a struct in order to
       provide the tag.  By integrating the union tag into the
       language, BX can perform safety checks on the usage of the
       union components and make union use simpler.

            union foo {
                int i;
                char c;
                float f;
            }

            foo X;

            X.i := 12;    # X holds an integer now
            x.c := 'a';   # X holds a character
            X.f := 10.5;  # X now holds a float


       Only one of the components of the union may be active at a
       time.  If the int part of union foo is active, for example,
       it is illegal to access the char or float components.  An
       access to an inactive component of a union will result in a
       run-time error.  The union tag is maintained based on the
       components present in the union.  In C you might provide
       definitions for the tag followed by the struct:

            #define    FOO_i   1
            #define    FOO_c   2
            #define    FOO_f   3

            struct foo {
                int tag;
                union foo_data {
                    int i;
                    char c;
                    float f;
                }
            }

       In BX, however, the compiler provides the definitions of the
       tag values and the outer struct containing the tag integer.
       It also provides tag value maintainence as well as error
       checking.

       There are two ways to determine which component of a union
       is active.  The boolean nfunction 'isactive' returns true if
       a particular component of a union is active:

            X.i := 12;
            if (isactive(X,i))
                printf("X contains integer %d",X.i);

            if (X.c == 'a')   # run-time error;
                ...           # X.c is not active

       Alternatively, the proc 'active' produces a return code for
       each component of the union:

            active(X) {
                case int:     printf("%d",X.i);
                case char:    printf("%c",X.c);
                case float:   printf("%f",X.f);
            }

       The design of the BX union lets the compiler perform the
       necessary job of maintaining the tag.  The compiler can
       automatically maintain union tags efficiently, and moving
       the burden to the compiler allows it to check their correct
       usage.  This design appears to be cleaner than either C's
       unions or Pascal's variant records.  C's unions are simpler
       and ultimately more flexible, but they require the
       programmer to do all of the necessary work and do not
       provide error-safe operation.


       Pascal variant records could similarly be argued to be more
       powerful than BX's unions.  However, it is questionable
       whether complex forms of variant records are ever used in
       actual practice.  Also, some research suggests that the tag
       value is seldom changed after initialization8[1]9 , which
       suports the BX style.

       4.2  Generators

       BX supports generators which produce a series of values or
       instantiated values.  Generators add greatly to data
       abstraction by separating the knowledge about the internal
       organization of the data structure from the code that must
       use it.  They are typically associated with data structure
       definitions, although stand-alone generators are also
       sometimes useful.  Generators have appeared in other
       languages, including Icon and Alphard8[2]9.  However, BX
       generators differ from generators in these languages in that
       they may produce instantiations of the generated variable as
       well as values.  This also allows BX to have a cleaner
       design for generators than is found in other languages.

       For example, suppose we wish to initialize every element of
       some array A to zero.  In Pascal, this could look like

            const max = 20;

            A: array[1..max] of integer;

            for i := 1 to max do
                A[i] := 0;

       In order to carry out the simple idea "clear array A to
       zeroes" we must define an extra variable i to be used in the
       for loop, and know how large the array is.

       Some languages make the size of the array accessible through
       the array name itself:

            for i := 1 to A'size do     or     for i in A do
                A[i] := 0;                     A[i] := 0;

       These are steps in the right direction, but we still have a
       temporary integer index necessary to access the array, and
       our implementation is still rather inflexible. We can easily
       change the size of the array, but if we wanted to change our
       implementation to a linked list or a tree instead of an
       array the loop would need to be replaced.

       It is much better if the generator can instantiate the
       actual value from the data structure.  In BX this would look
       like

            array <int,20> A;

            for int x := A.all do
                x := 0;

       Within the definition of box 'array' is a generator 'all'.
       The for loop names the generator, which will instantiate
       every element of A within the body of the loop.  The
       implementation of A could be changed to a tree or a linked
       list, and provided that they implemented a similar generator
       "all", the loop would not change.  A generator for a linked
       list would look like

            box llist <type T> {
                box node {
                    T data;
                    ref node next;
                }

                ref node head;

                generator T all {
                ref node tmp := head;

                    while (tmp != NULL) {
                        generate tmp^.data;
                        tmp := tmp^.next;
                }
            }

       Since generators in other languages typically can only
       return values, they cannot take assignments.  Thus the array
       generator is restricted to returning only the index of the
       desired value, instead of an instantiation of the value
       itself.  This severely limits the usefulness of generators
       and the power they offer to data abstraction.

       The BX for loop may have a 'while' clause with a boolean
       expression.  The for loop will continue to execute as long
       as there are remaining values to be generated and as long as
       the while condition is satisfied:

            for int i := upto(1,10)
                while (i <= 5) do
                    printf("i is %d",i);

       will generate the values 1 through 5.

       4.2.1  First  Sometimes only the first element of a stream
       of generated values is desired.  In this case, the 'first'
       construct should be used:

            first int i := upto(5,10) do
                printf("i is %d",i);

       will only generate the number 5.  The first loop may contain
       a 'suchthat' clause; values will be generated until the
       condition is satisfied, and then the body will be executed:

            first int i := upto(1,10) suchthat (i == 5) do
                printf("i is %d",i);

       will produce 5.  If no values are generated, or if no
       generated values satisfy the 'suchthat' clause, an 'else'
       clause can be provided:

            first int i := upto(1,10) suchthat (i == 11) do
                 printf("i is %d",i)
            else
                 printf("i was never 11");

       In this case, "i was never 11" will be printed.


       4.3  Concept Definition

       The concept is a template which specifies matching
       requirements for a box.  A concept may be used in place of a
       box in a procedure parameter list.  Any box which matches
       the concept can then be passed to the procedure; the
       procedure will be instantiated for each type of box passed
       to it.

       For example, a vector (1 dimensional array) can be thought
       of as a data structure which allows the referencing of the
       individual items with an index.  A "complete" vector will
       also contain it's starting and ending indices.  To create a
       concept for this abstraction,the programmer would define the
       following:

            concept VECTOR <type T> {
                    func T index(int);
                    take T index(int);
                    func int first();
                    take int last();
            }

       This creates the concept of a vector.The type is
       parameterized as T.  By convention, concepts are usually
       defined with names of all capital letters.  The data
       structure will be implemented via a box and all of the
       functions defined in the concept header must be present in
       the box for the structure to be treated as an vector.  A
       box, however, may contain more functions/variables than are
       specified in the concept.

       A procedure may be written which refers to the concept
       template instead of an actual box:

            proc foo(VECTOR<int>X);

       This indicates that procedure 'foo' will accept any box
       which conforms to the concept vector defined above.
       However, but that the vector must be of type int.  The
       procedure may access or update the individual members of the
       vector by using the box's take/func pair 'index'.  Note that
       a procedure may only make use of procedures and functions
       present in the concept even if the actual box which is
       passed to the proc implements other features not specified
       in the concept.  For example:

            proc swap(var VECTOR<int> X; int i,j) {
            int temp;

                temp := X[i];       # shorthand for: temp := X.index(i)
                X[i] := X[j];       # X.index(i) := X.index(j)
                X[i] := temp;
            }

       The concept can be manipulated exactly as if it were a box.
       A procedure which accepts a concept instead of a box in its
       parameter list will be instantiated for each type of box
       with which it is called.  For example, if 3 boxes are
       written to conform to concept VECTOR, and call swap, swap
       will be instatiated for each of the three boxes.

       To truly generalize the procedure swap, we should allow it
       to operate on any type.  We replace 'int' with 'type T':

            proc swap(var VECTOR<type T> X; int i,j) {
            T temp;
                temp:=X[i];
                X[i]:=X[j];
                X[i]:=temp;
            }

       If swap is called with a character array, T will be
       instantiated to a character.  If swap is called with an
       integer array, T will be instantiated to an integer.  A
       matrix is an m by n double dimensional array.  The
       components may be accessed via two indices (i.e.  X[1,2]).
       A sparse matrix is conceptually the same, but may be very
       large and may contain many unused elements, making it
       ineffiencent to store in the traditional way.  Such matrices
       are used heavily in such areas as graph theory.  To concept
       of a matrix looks like this:

            concept MATRIX<type T; int sizeh,sizev> {
                take T index(int,int);
                func T index(int,int);
                int maxhoriz;          # maximum horizonal elements
                int maxvert;           # maximum vertical elements
            }

       This formally defines what must be present in a box for it
       to qualify as a matrix.  Procedures may use matrix as a
       parameter:

            proc do_something(MATRIX<type T;int sizeh,sizev> foobar) {
            T x;
                x := foobar[1,2];         # or
                x := foobar.index(1,2);   # shorthand for [1,2]

                    #any code.
            }

       Thus, a box which which wishes to look like a matrix may be
       implemented using the standard methods, or it may be
       implemented using a linked list or a tree.  If it contains
       everything listed in the concept it may be treated as an
       matrix.

       To call the procedure, one mearly needs to use the
       instanciation of the box which conforms to MATRIX.  Thus, if
       box "sparse" contains at least everything listed in the
       concept heading, the following code is legal:

            proc main {
                    sparse<int,10,10> s; # declare a sparse matrix of int,
                                         #  horizonal size=10,vertical size=10
                    do_something(s);     # call routine with the sparse matrix
            }

       Concept precludes the inclusion of static procedure
       variables in BX for two reasons.  First, several instances
       of each procedure may be generated in target code and
       therefore it is not obvious whether the static will belong
       to all instances or individual instances.  Further, if the
       static variable is defined to be of a type instantiated in
       the procedure, then there must be multiple copies of the
       static variable of different types.  This obscures the
       meaning of static procedure variables.  The role that static
       procedure variables play in traditional algorithmic
       languages has been shifted to boxes in BX;  thus, they are
       not missed.

       Note that a take/func or take/give pair for a tyhpe will
       match a simple definition for the same type:

            box one {
                int x;
            }

            box two {
                take int x;
                func int x;
            }

            concept foo {
                int x;
            }

            concept bar {
                take int x;
                func int x;
            }

       Either one or two will match foo or bar.  'Give' could be
       substituted above for 'func'.

       4.4  Path

       In order to avoide having to repeatedly type box names which
       encapsulate often-used procedures, BX provides a way to
       specify a default box search path:

            path basic_io, stringlib, my_box;

       Would set up a path searching the named boxes.  If a box
       name was used as if it were a top-level definition:

            newline;

       The list of boxes would be searched in the order given for
       the procedure.  The compiler will interpret the reference as
       if it were fully specified:

            basic_io.newline;

       The path statement must be the first statement in a file.


       5.  The Standard Type Library

       One of the great advantages of using BX is that type
       libraries may be constructed and types used interchangeably.
       This is also an advantage of object oriented languages, but
       BX provides type libraries along with sophisticated type
       checking within a standard algorithmic language.

       Throughout the design of BX we have envisioned many useful
       types which deserve to be part of the BX language but which
       shouldn't be part of the syntax.  Rather, since they are
       constructable within BX itself (although not necessarily
       efficiently) we decided to provide a standard type library,
       analogous to the C standard library.

       5.1  Arrays

       The standard array is provided.  Arrays can be constructed
       of any type, and arrays can be nested (by using another
       array itself as the constructed type).  Standard arrays must
       have a fixed size known at compile time.  An array type
       which may grow beyond its suggested size if needed is also
       provided.

                # The standard array
            array <type T; int Size>;

            xarray <type T; int Size;int Max := 0>;
                # An extendable array

            array <int,20> A;      # an array of 20 integers
                                   # they are not initialized upon creation

            xarray <int,20> A;     # A has space for 20 integers set aside;
                                   # access to these 20 integer will be fast
                                   # The array may grow unlimited beyond 20
                                   # elements, however.  The compiler will
                                   # implement this by using dynamic memory
                                   # allocation

            xarray <int,20,300> A; # A will have 20 elements reserved.  It may
                                   # grow to 300 elements, but attempts to access
                                   # any higher elements will cause a run-time
                                   # error

            array<array<int,20>,10> A;
                                   #  A holds 10 arrays of 20 integers each


       Operations Defined:

            generator T all;       # generates all of the elements of the
                                   # array, in order

            take T index(int n);   # provides A.index(n) := (expr)
            func T index(int n);   # provides reference to A.index(n)

            #  Note that any reference of the form A[n] will be
            #  rewritten to A.index(n), both on the left side of
            #  assignment statements and also in expressions.
            #
            #  Thus any BX box type may be used like an array so
            #  long as an "index" take/func pair is supplied
            #
            #  Multidimensional arrays may be constructed as well;
            #  simply add more arguments to the "index" take/func pair

       5.2  Strings

       BX provides two standard string types, mirroring the array
       types.  One has a fixed size any may not grow beyond the
       specified size, also it may be smaller.  The other may
       extend via automatic memory allocation.

            string <20> S;       # S is a string which may have at most
                                 # 20 characters

            xstring <20> S;      # A block large enough to hold 20 characters
                                 # has been set aside; however, the string may
                                 # be larger

            xstring <20,300> S;  # The string may not grow beyond 300 characters

       5.3  Infinite Precision Numbers

       BX has several infinite-precision (limited only by
       allocateable memory) types which mirror their finite but
       efficient atomic counterparts.

            xint i;      # i is an infinite integer; it may grow
                         # without bounds

            xfloat f;    # f is an inifinite real; most likely the precision
                         # for the various components of the real values (mantissa,
                         # exponent, etc) will have to be declared

       xcomplex c;  # a complex number constructed from xfloat


       6.  Automatic Rewriting

       The BX compiler will rewrite certain expression to allow
       user-defined box types to emulate atomic types and to
       specify actions.  In each case a syntactic construction such
       as an expression will be changed to make the reference to a
       procedural component of the box type.


       The first example of this is array index rewriting.  Any box
       type may be used like an array, provided it has a take and
       func definition with the identifier "index".  Thus, array
       references are actually written

            array_variable.index(element)

       As a syntactic convenience this may instead be written

            array_variable[element]

       A two dimensional reference such as

            array_variable[elem1,elem2]

       will be rewritten to the corresponding index reference

            array_variable.index(elem1,elem2)

       at which time the standard-type checking rules will apply.

       Infix operators, the trigonometric functions and assignment
       are also rewritten to reference the object.  Thus

            a + b       cos(a)    a := b

       becomes

            a.plus(b)   a.cos     a.assign(b)

       This allows user-defined types to be as powerful as the
       compiler-supported atomics, and allows a powerful type
       library to be constructed.  To the programmer, the usage of
       user-defined types and atomics is completely transparent.


       7.  BX Language Reference

       7.1  Symbols

       Logical Operators

       && Logical AND          || Logical OR           -| Logical XOR
       !  Logical Not

       Relational Operators

       == Equality test        != Non-Equality         <  Less than
       >  Greater than         <= Less than or equal   >= Greater or equal

       Expression Operators

       *  Multiplication       /  Division             %  Modulus
       +  Addition             -  Subtraction

       Unary Symbols

       ^  Pointer symbol       -  Unary Minus sign     +  Unary Plus Sign




       7.2  Keywords

       NULL          continue      generate      ref           type
       bool          default       generator     ret           typeof
       box           double        goto          return        uint
       break         else          if            short         ulong
       case          false         int           static        union
       char          float         label         switch        ushort
       concept       for           long          take          var
       const         func          proc          true          while



       7.3  Formal Syntax of BX

       file            : declarations
                       |       /* null */
                       ;

       simple_type     : INT  | SHORT  | LONG  | CHAR  |
                         UINT | USHORT | ULONG | BOOL  | DOUBLE | FLOAT
                       ;

       type_name       : REF type_var
                       | type_var
                       ;

       type_var        : simple_type
                       | complex_var
                       ;

       declarations    : declarations declaration
                       | declaration
                       ;

       declaration     : concept_decl
                       | func_decl
                       | proc_decl
                       | union_decl
                       | take_decl
                       | box_decl
                       | generator_decl
                       | var_decl
                       | const_decl
                       ;

       instantiator    :
                       | '<' instance_list '>'
                       ;

       instance_list   : instance_list ';' instantiation
                       | instantiation
                       ;

       instantiation   : type_name non_init_vars
                       | TYPE non_init_vars
                       ;

       var_list        : var_list ',' var                 | var
                       ;

       non_init_vars   : non_init_vars ',' ident                 |
       ident                 ;

       var             : ident
                       | ident ASSOP cexpr
                       ;

       box_decl        : BOX ident instantiator '{' declarations '}'
                       ;

       union_decl      : UNION ident instantiator '{' union_header ';' '}'
                       ;

       take_decl       : TAKE type_name ident formal_parms block
                       ;

       proc_decl       : PROC ident formal_parms return_codes block
                       ;

       const_decl      : CONST type_name var_list ';'
                       ;

       block           : '{' statements '}'
                       | '{' declarations statements '}'
                       | '{' declarations '}'
                       | '{' '}'
                       ;

       func_decl       : FUNC type_name ident formal_parms return_codes  block
                       ;

       concept_decl    : CONCEPT ident instantiator concept_body
                       ;

       generator_decl  : GENERATOR type_name ident formal_parms block
                       ;

       var_decl        : type_name inst_call var_list ';'
                       ;

       concept_body    : '{' concept_header ';' '}'
                       | '{' '}'
                       ;

       concept_header  : concept_header ';' concept_var
                       | concept_var
                       ;

       concept_var     : type_name inst_call non_init_vars
                       | FUNC type_name inst_call ident formal_parms
                       | TAKE type_name inst_call ident formal_parms
                       | PROC ident formal_parms
                       ;

       union_header    : union_header ";" union_var
                       | union_var
                       ;

       union_var       : type_name non_init_vars
                       ;

       statements      : statements statement
                       | statement
                       ;

       statement       : LABEL ident           ';'
                       | GOTO ident            ';'
                       | CONTINUE              ';'
                       | BREAK                 ';'
                       | do_loop
                       | while_loop
                       | for_loop
                       | if_construct
                       | proc_call
                       | assign_construct
                       | block
                       | case_construct
                       | /* Null */            ';'
                       ;

       for_loop        : FOR type_name ident ASSOP ident opt_parms statement
                       ;

       do_loop         : DO statement WHILE '(' expr ')'
                       ;

       while_loop      : WHILE '(' expr ')' statement
                       ;

       if_construct    : IF '(' expr ')' statement
                       | IF '(' expr ')' statement ELSE statement
                       ;

       assign_construct: complex_var ASSOP expr ';'
                       | take_or_func ASSOP expr ';'
                       ;

       complex_var     : ident
                       | pointer_var
                       | index_variable
                       | field_designator
                       ;
       take_or_func    : complex_var req_parms
                       ;

       pointer_var     : complex_var '^'
                       ;

       index_variable  : complex_var '[' index_expr_list ']'
                       ;

       index_expr_list : index_expr_list ',' expr
                       | expr
                       ;

       field_designator: complex_var '.' ident
                       ;

       proc_call       : complex_var opt_parms ';'
                       ;

       inst_call       : '<' inst_list '>'
                       |
                       ;

       inst_list       : inst_list ',' inst
                       | inst
                       ;

       inst            : CONSTANT
                       | '(' cexpr ')'
                       | type_name inst_call
                       | type_name ident inst_call
                       | TYPE ident
                       ;

       return_codes    : r_codes ';'
                       |
                       ;

       r_codes         : r_codes ';' RET r_code_list
                       | RET r_code_list
                       |
                       ;

       r_code_list     : r_code_list ',' r_code
                       | r_code
                       ;

       r_code          : ident '(' type_list ')'
                       | ident
                       ;

       type_list       : type_list ',' type_name
                       | type_name
                       ;

       opt_parms       : req_parms
                       | /* Null */
                       ;

       req_parms       : '(' parm_list ')'
                       ;

       parm_list       : parm_list ',' parm
                       | parm
                       ;

       parm            : expr
                       ;

       addop           : '+'
                       | '-'
                       | BOOLOR
                       | BOOLXOR
                       ;

       mulop           : '*'
                       | '/'
                       | '%'
                       | BOOLAND
                       ;

       relop           : EQOP
                       | '<'
                       | '>'
                       | LEOP
                       | GEOP
                       | NEOP
                       ;

       sign            : '-'
                       | '+'
                       ;

       expr            : simple_expr
                       | simple_expr relop simple_expr
                       ;

       simple_expr     : term
                       | simple_expr addop term
                       ;

       term            : factor
                       | term mulop factor
                       ;

       factor          : sign factor
                       | primary
                       ;

       primary         : CONSTANT
                       | complex_var req_parms
                       | complex_var
                       | '(' expr ')'
                       | '!' primary
                       ;

       case_construct  : SWITCH '(' expr ')' '{' case_body '}'
                       ;

       case_body       : cases
                       | cases case_default
                       ;

       cases           : cases case_entry
                       | case_entry
                       ;

       case_entry      : CASE expr ':' statements
                       ;

       case_default    : DEFAULT ':' statements
                       ;


       formal_parms    : /* null */
                       | '(' formal_par_list')'
                       ;

       formal_par_list : formal_par_list ';' formal_par
                       | formal_par
                       ;

       formal_par      : VAR type_name inst_call var_list
                       | FUNC type_name inst_call ident formal_parms
                       | PROC ident formal_parms
                       | type_name inst_call var_list
                       ;

       cexpr           : csimple_expr
                       | csimple_expr relop csimple_expr
                       ;

       csimple_expr    : cterm
                       | csimple_expr addop cterm
                       ;

       cterm           : cfactor
                       | cterm mulop cfactor
                       ;

       cfactor         : sign cfactor
                       | cprimary
                       ;

       cprimary        : ident
                       | '(' cexpr ')'
                       | CONSTANT
                       | BOOLNOT cprimary
                       ;

       ident           : IDENTIFIER
                       ;


                                References



        1. "Early Experience with Mesa" Charles M. Geschke, James
           H. Morris Jr., and Edwin H. Satterhwaite in
           Communications of the ACM, August 1977, volume 20,
           number 8, pages 540-553.

        2. "Abstraction and Verification in Alphard: Defining and
           Specifying Iteration and Generators", by Mark Shaw,
           William A. Wulf and Ralph L. London in Communications of
           the ACM, Auust 1977, volume 20, number 8, pages 553-564.