Section 2.8 ADTs

ADTs

After tuples, the next level of sophistication in data structures is the ADT (Aggregate Data Type), in which both the components and the structure itself are given names. Here is a declaration of a simple ADT, called Point, that represents a position in the integer grid:

	Point: adt
	{
		x, y: int;
	};

After this declaration, Point is a name, like int or string, that can be used to declare variables of that type:

	p: Point;

declares a Point called p, whose initial components are undefined. The components of p can be accessed as p.x and p.y and treated like other variables, array elements, and so on:

	p.x = 7;
	p.y = -1;
	sys->print("p = (%d, %d)\n", p.x, p.y);

There is a close relationship between ADTs and tuples: if an ADT and a tuple have the same types of components and the same order, they are said to have compatible types and can be used somewhat interchangeably. For example, we can write

	x := (3, 4);

to declare a tuple of two ints called x and then use it along with p:

	p = x;

will assign p.x the value 3 and p.y the value 4. This provides another way to unpack a tuple. Similarly, we can say

	x = p;

to assign the elements of p to the corresponding elements of x.

The first assignment is equivalent to the more explicit

	p = Point x;

which includes the conversion from tuple to Point. There are times when the conversion is useful, particularly when initializing a new variable:

	origin := Point (0, 0);

declares origin to be explicitly of type Point. Without mentioning Point explicitly, we couldn't name origin.x or origin.y.

ADTs can also have functions associated with them. Here is another definition of Point along with an operator to see if two Points are equal:

	Point: adt
	{
		x, y: int;
		equal: fn(p1, p2: Point): int;
	};

The equal function is then written as:

	Point.equal(p1, p2: Point): int
	{
		return p1.x==p2.x && p1.y==p2.y;
	}

We can then ask if two Points (or equivalent tuples) have the same value:

	if(Point.equal(p, origin))
		sys->print("p == (0,0)\n");

Used like this, the only advantage of embedding functions in ADTs is that we can have multiple functions with the same names but different types: checking equality of points in one case, circles in another, for example. However, we can go a little farther by making an ADT function accept an instance of the ADT as an implicit parameter, indicated by the keyword self. Rewriting and expanding our definition of Point:

	Point: adt
	{
		x, y: int;
		equal: fn(p1: self Point, p2: Point): int;
		add: fn(p1: self Point, p2: Point): Point;
		sub: fn(p1: self Point, p2: Point): Point;
	};

	Point.equal(p1: self Point, p2: Point): int
	{
		return p1.x==p2.x && p1.y==p2.y;
	}
	
	Point.add(p1: self Point, p2: Point): Point
	{
		return (p1.x+p2.x, p1.y+p2.y);
	}
	
	Point.sub(p1: self Point, p2: Point): Point
	{
		return (p1.x-p2.x, p1.y-p2.y);
	}

To use these new functions, we access them using a value instead of the explicit type name, and that value is the Point that serves as self and is passed implicitly. For example,

	p := Point(7, 8);
	p = p.add((1, 4));

leaves p set to (8, 12) by calling Point.add with p1 set to p, passed implicitly because p1 is the self parameter, and p2 set to (1, 4). Similarly,

	p.equal((0, 0))

is an expression to test whether p is at the origin. In this last example, notice the double parentheses: the outer set calls the function, the inner set defines a tuple to be passed as a Point.

This sort of function, bound to an implicitly passed type, is sometimes called a method. One of the strengths of methods is that they may be cascaded: the Point returned by one function can be used as a self parameter to another. For example,

	p.sub(p).equal(origin);

should always be true.

Of course, ADTs may have components of multiple types. Our Point contains a pair of ints but much richer structures can be built; we will see many examples in the chapters to come.