9 Dynamic Data Structures

The variables that we have declared so far (with @) are said to be static objects and the variable names are said to be static references.

Advanced programming requires more than just static data structures. In particular, list processing is based on the notion of dynamically created objects linked by pointers. Recursive procedures also rely on dynamically allocated activation records. More to the point, objects are generally created on demand with a new operator.

In BETA, pointers or dynamic references as they are called are declared very much as in C using the * token. Below, we declare refA and refB to be references to Point objects whereas the declaration for P1 and P2 cause storage space to be reserved for 2 points and associate (permanently) the names P1 and P2 to those points.

refA, refB: ^Point; P1,P2: @Point;

Initially, refA and refB point nowhere and have the value NONE whereas P1 and P2 designate real live points. Thus, we can assign data to P1 but not to refA.

P1 -> P2; (* OK *) P1 -> refA; (* run-time error because refA is NONE *)

This seems normal but reread these two imperatives carefully. Anyone having used pointers in other languages should notice that the BETA pointer concept is a little different that most other languages. We have used (correctly) the same notation for the variable and for the pointer. If this were C, with:

Point p1,p2; Point *refA,*refB;

then refA would represent the address of a Point and *refA would be used to denote the contents of that Point. In C, the assignments would have read

p2 = p1; *refA = p1;

Now we can return to the BETA approach to dynamic data which is quite different from the traditional one.

In BETA, a pointer is treated as a reference which may point to different objects (or to NONE) at different times during execution whereas a variable is considered to be a reference which will always denote the same object. Thus both are references but one is static and the other dynamic and they will be used in the same way to access the data. The concept of pointer storage address is avoided.

In BETA, simple use of a reference (static or dynamic) in an evaluation refers to the contents of the object referenced. Thus, assuming that refA and refB designate Points (and not NONE) then,

(0.0, 0.0) -> P1 -> refA -> refB -> P2 ;

means that the contents (or value) of each point is set to (0,0).

To manipulate references to objects and not just the contents, we need to use a reference operator. In BETA, this is a postfix operator written [] (read box). Thus the following imperative:

refA[] -> refB[];

has the effect that refB now points to (references) the same object as refA.

BETA's approach is the converse of C's: BETA uses a referencing operator and C uses a dereferencing operator.

In BETA, it is also possible to make a dynamic reference denote a static object. This can also be done in C:

BETA: P1[] -> refA[] C: refA = &P1;

This is one way to give dynamic references values other than NONE. The other and more obvious one involves dynamic creation of new objects at run-time. In BETA, the new operator is written &. Thus,

&Point

causes a new point object to be created. Now, comes a delicate aspect.

To create a new object and to get the address of this new Point, we also need the reference operator:

&Point[] -> refA[];

As mentioned in section 3.2.3 of the BETA book, this is a subtle point:

'The difference between &P and &P[] is very important: the expression &P means 'generate a new instance of P and execute it'; the expression &P[] means 'generate a new instance of P without executing it and return a reference to this new object'.'

In C a Point is allocated like this:

refA = (Point*) malloc(sizeof(Point));

The following program shows the use of static and dynamic references. This uses a Point user-type with integer attributes. There are 2 static references, P1 and P2, and a dynamic reference, refA. At various points in the program refA points to either P1 or P2 or to a dynamically allocated object. Note that access to Points via the static or dynamic variables is syntactically identical. We assign various values to the three references and use dump to show the contents of the first attributes of all three. This shows that effectively refA designates various Points during execution. At the end, we show the use of a dynamically generated Point in a cascaded assignment. In this case, the purpose is just to show that it can be done and what happens. Useful version of this dynamic generation will be shown later.

(111,333) -> &Point -> P1;

What happens here is that

• 1) a new Point object is created,
• 2) the values (111,333) are assigned to the variables in the enter list of the new Object,
• 3) the (empty) do part of the object is executed,
• 4) a value assignment is done between the exit list of the Point and the enter list of P1 and
• 5) finally, the (empty) do part of P1 is executed. The newly created Point is inaccessible and the space it occupies will be reclaimed by the garbage collector.

Instead using the reference operator gives:

(111,333) -> &Point[] -> refA[];

What happens here is that

• 1) a new Point object is created,
• 2) the values (111,333) are assigned to the variables in the enter list of the new object,
• 3) a reference assignment is done between newly created object and refA. refA now refers to the new object.

Program 9: StaticAndDynamic.bet

ORIGIN '~beta/basiclib/betaenv' ---- program: descriptor ---- (# (* Static and Dynamic references *) Point: (# X,Y: @integer; enter (X,Y) exit (X,Y) #); refA: ^Point; P1,P2: @Point; Dump: (# do 'P1: '->puttext; P1.X->screen.putint(# format:: (# do 3->width#)#); ', P2: '->puttext; P2.X->putint; ', refA: '->puttext; refA.X->putint; newline; #); do 'Dynamic references'->putline; newline; &Point[]->refA[]; (1,1)->P1->P2->refA; Dump; (2,2)->P2; (3,3)->refA; Dump; P1[]->refA[]; Dump; P2[]->refA[]; Dump; (1,1)->P1; (2,2)->P2; (3,3)->refA; Dump; (111,333)->&Point->P1; Dump; Newline; #)

The results from execution are shown below:

Dynamic references P1: 1, P2: 1, refA: 1 P1: 1, P2: 2, refA: 3 P1: 1, P2: 2, refA: 1 P1: 1, P2: 2, refA: 2 P1: 1, P2: 3, refA: 3 P1: 111, P2: 3, refA: 3