10 Repetitions (Arrays)

In BETA arrays are called repetitions.

A: [10] @integer;

This repetition describes a set of static references to integers. 10 is called the range of the repetition (the upper bound). In spite that the lower bound is always 1, repetitions are flexible since the upper range is accessible as a local attribute of the repetition, they can be assigned, extended and sub-range access is possible (slices).

BETA repetitions compared to its C counterpart:


Language	BETA	C
Declaration	A: [10] @integer;	int [10] A;
Lower	1	0
Upper	A.range	9
Size	A.range	10
Access	A[i]	A[i]
Assignment	A -> B;	not possible
Extend	10 -> A.extend	not possible
Slices	A[2..3]	not possible

It should be noted that it is not possible to take the address of a repetition, i.e. A[] is illegal (legal in C as &A).

In the current Mjølner implementation, it is possible to declare repetitions of types: char, boolean, integer, real, and any object reference:

(# Record: (# ... #);
   A: [100] ^Record;
do &Record[] -> A[1][]; (* create a new instance of Record and 
                         * assign it to first entry in A *)
    ...
#)

Besides assigning values to the elements of a repetition, whole repetitions can be assigned to other repetitions regardless of their ranges, e.g.:

a: [10] @integer;
b: [1] @integer;
do (for i: A.range repeat (* initialize a *)
        i -> a[i]; (* put i into i'th position in repetition a *)
    for);
    14 -> b[1]; (* a is [1,2,3,4,5,6,7,8,9,10], and 
                 * b is [14]
                 *)
    a -> b;     (* make repetition assignment:
                 * a is [1,2,3,4,5,6,7,8,9,10], and 
                 * b is [1,2,3,4,5,6,7,8,9,10]
                 *)

The next program illustrates how to use repetitions in a simple sorting program called quick sort, originating from C.A.R Hoare. Given a repetition, one element is chosen and the others partitioned into two subsets: those less than and those greater than or equal to the partition element. The same process is then applied recursively to the two subsets. When a subset has fewer than two elements it does not need any sorting and the recursion stops.

In BETA it is illegal to use the reference operator on repetitions, and since the quick sort algorithm is inherently recursive with the repetition as function argument in each recursion, we face a problem. However, this problem is easily solved in BETA. We simply define a pattern containing a repetition, and using an object of this type as the argument to quick sort.

numberRepetition: (# r: [1] @Integer #);
  qsort:
    (# nr: ^numberRepetition;
    enter (nr[], ...)
    do ....
  #);
  numbers: @numberRepetition;
do
  ...
  qsort(numbers[],...);

So the limitation of not being allowed to take a reference to repetitions is easily circumvented.

The quick sort algorithm also uses a swap operation, that swaps two elements in the repetition. This operation can be define locally inside (statically nested inside) qsort, so swap can operate on the same repetition:

qsort:
    (# nr: ^numberRepetition;
       swap:
         (# i,j: @Integer;
            temp: @Integer;
         enter (i,j)
         do nr.r[i] -> temp;
            nr.r[j] -> nr.r[i];
            temp -> nr.r[j];
         #);
    enter (nr[], ...)
    do ...
    #);

The complete code including a loop for reading numbers to be sorted from the keyboard follows below:

Program 10: QuickSort.bet

ORIGIN '~beta/basiclib/betaenv';
---program: descriptor---
(# (* Hoare QuickSort program illustrating how to use 
    * repetitions, simple pattern declarations,
    * block structure and recursion.
    *)
   numberRepetition: (# r: [1] @Integer #);
   qsort: 
     (# nr: ^numberRepetition;
        left, right, last: @Integer;
        swap: 
          (# i,j: @Integer;
             temp: @Integer;
          enter (i,j)
          do nr.r[i]->temp;
             nr.r[j]->nr.r[i];
             temp->nr.r[j];
          #);
     enter (nr[], left, right)
     do L: (if left >= right then (* stop if rep. contains *) 
               leave L;           (* fewer than two elements *)
            else
               (* move partition element to nr.r[1] *)
               (left, (left+right)/2) -> swap;
               left->last;
               (* partition *)
               (for i: right-left repeat
                    (if nr.r[i+left] < nr.r[left] then
                        last+1->last;
                        (last,i+left) -> swap;
                    if);
               for);
               (left,last) -> swap; (* restore partition element *)
               (nr[],left,last) -> qsort;
               (nr[],last+1,right) -> qsort;
           if);
     #);
   numbers: @numberRepetition;
   t: ^Text;
   i: @Integer;
do
   (* initialize a repetition with numbers typed
    * by the user
    *)
   'Type some numbers: '->puttext;
   getline->t[]; (* read all what the user types until newline *)
   1->i;
   t.reset;
   L: (if not t.eos then
          (* parse the text;
           * assuming that the user only types numbers
           *)
          (if i>numbers.r.range then 
              (* remember to extend the repetition *)
              numbers.r.range->numbers.r.extend;
          if);
          t.getint->numbers.r[i];
          i+1->i;
          restart L;
      if);
   
   (* sort the repetition *)
   (numbers[],1,i-1) -> qsort;
   
   'Sorted numbers: '->puttext;
   (for j: i-1 repeat
        numbers.r[j]->putint; ' '->put;
   for);
   newline;
#)

Running the program and typing some numbers results in the following output:

nil% QuickSort
Type some numbers: 9 8 4 6 3 8 2 7 12 45 2 78 5 6 1 0 2
Sorted numbers: 0 1 2 2 2 3 4 5 6 6 7 8 8 9 12 45 78

Libraries Tutorial

[Modified: Thursday October 19^th 2000 at 14:10]