[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8. Types

Q uses dynamic typing like, e.g., Lisp or Smalltalk, as opposed to statically-typed languages such as Pascal, Eiffel or Haskell. In languages with static typing, a variable or function parameter can only hold a value which matches its prescribed type (which can be a "polymorphic" type in languages like Eiffel and Haskell, but still the type of the value is restricted). In dynamically typed languages, however, the actual value of a variable or function parameter is not known in advance. Consequently, in Q it is only possible to distinguish different types of objects -- such as search trees, queues, arrays and the like -- by selecting an appropriate set of constructor symbols for each type of object. This chapter discusses Q's notion of type guards which allows you to make the assignment of constructors to a type explicit, and to use this information in order to restrict the applicability of equations to objects of a given type.

8.1 Using Type Guards  
8.2 Built-In and Enumeration Types  
8.3 Sub- and Supertypes  

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.1 Using Type Guards

As in any programming language, the careful design of application-dependent data structures is one of the main concerns when developing Q scripts which go beyond simple numeric, string and list processing. As a typical example for a non-list data structure which plays a prominent role in many Q scripts, let us consider binary search trees, which are a convenient means to implement sets, bags, dictionaries and the like. We will use this data structure as a running example throughout this chapter.

A typical choice of constructors for binary trees is the following:

public const nil, bin X T1 T2;

To make explicit the fact that nil and bin belong to the binary tree type, we can also use a type declaration which introduces the type symbol BinTree, as discussed in 5. Declarations:

public type BinTree = const nil, bin X T1 T2;

This declaration tells the interpreter that each expression of the form nil or bin X T1 T2 should be considered as a member of the BinTree type. The type symbol can then be used as a guard on variables to ensure that a variable is only matched to objects of the given type, see 7.5 Type Guards. E.g., the following rule employs such a type guard in order to restrict the argument of the foo function to BinTree objects:

foo T:BinTree           = ...;

This makes it possible to avoid explicit argument patterns like

foo nil                 = ...;
foo (bin X T1 T2)       = ...;

in cases in which the component values are not actually required. This can simplify matters a lot, in particular if multiple arguments have to be matched to a given type. Also, it is more efficient than checking the type of an object in the qualifier part of a rule by using a user-defined predicate, since the interpreter can use the type information right away in the pattern matching process.

Another important reason for preferring type guards over explicit argument patterns is the issue of "information hiding". With the former definition of the foo function above we do not make any explicit reference to the constructor patterns making up the BinTree data type. This makes it possible to treat BinTree as an abstract data type (ADT) which hides the underlying implementation details (in particular the constructors), while still being able to verify that the proper kind of object is supplied as an argument. Any access to objects of the ADT will then be implemented by referring to the appropriate operations supplied by the type. In fact, we can make the constructors private symbols which are only accessible to the script which implements the BinTree type:

public type BinTree = private const nil, bin X T1 T2;

As a concrete example, let us assume the standard search tree operations insert T X and delete T X, which insert an element X into a tree T, and remove it from the tree, respectively. These operations can be implemented as follows (see [Bird/Wadler 1988]):

public insert T X, delete T X;
private join T1 T2, init T, last T;

insert nil Y            = bin Y nil nil;
insert (bin X T1 T2) Y  = bin X (insert T1 Y) T2 if X>Y;
                        = bin X T1 (insert T2 Y) if X<Y;
                        = bin Y T1 T2 if X=Y;

delete nil Y            = nil;
delete (bin X T1 T2) Y  = bin X (delete T1 Y) T2 if X>Y;
                        = bin X T1 (delete T2 Y) if X<Y;
                        = join T1 T2 if X=Y;
join nil T2             = T2;
join T1 T2              = bin (last T1) (init T1) T2 otherwise;

init (bin X T1 nil)     = T1;
init (bin X T1 T2)      = bin X T1 (init T2) otherwise;

last (bin X T1 nil)     = X;
last (bin X T1 T2)      = last T2 otherwise;

(Note that the last and init operations return the last element of a binary tree, and a binary tree with the last element removed, respectively. The join, init and last functions are for internal use only, and can hence be implemented as private functions.)

Furthermore, we assume the following function mkbintree which constructs a binary tree from a list, and the function members which returns the list of elements stored in a tree (in ascending order):

public mkbintree Xs;
mkbintree Xs:List       = foldl insert nil Xs;

public members T;
members nil             = [];
members (bin X T1 T2)   = members T1 ++ [X|members T2];

(The definition of mkbintree employs the standard foldl operation, see 11. The Standard Library.) We can use the interface operations of the BinTree ADT in order to implement the functions union and diff which add and remove all members of a tree to/from another tree:

public union T1 T2; // add elements of T2 to T1
union T1:BinTree T2:BinTree
                        = foldl insert T1 (members T2);

public diff T1 T2; // remove elements of T2 from T1
diff T1:BinTree T2:BinTree
                        = foldl delete T1 (members T2);

Observe that no explicit reference is made to the BinTree constructors; we only employ the public "interface" functions insert, delete and members of the BinTree ADT. This allows us to change the realization of the data structure without having to rewrite the definitions of union and diff. Still, the definitions of union and diff are "safe"; the BinTree type guard ensures that the arguments passed to union and diff are indeed BinTree objects capable of carrying out the requested operations.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.2 Built-In and Enumeration Types

Type guards are also the only way for verifying that the actual value of a variable belongs to one of the built-in types integers, floating point numbers, strings and files, since there is no way for writing out all "constructors" for these kinds of objects -- there are infinitely many (at least in theory). For this purpose, the type symbols Int, Float, String and File are predefined.

There also is a type named Num which, when used as a guard on variables, matches numeric (i.e., both integer and floating point) values, and the type Char which denotes the single-character strings. Technically, Num is the supertype of both Int and Float, and Char is a subtype of the String type; more about that in 8.3 Sub- and Supertypes. Moreover, Char is also treated as an enumeration type, see below.

The built-in List type matches all list expressions of the form [] or [X|Xs]. This type is used to restrict the applicability of an equation to list arguments. For instance, the following equations define a function reverse which reverses a list:

reverse Xs:List         = foldl push [] Xs;
push Xs:List X          = [X|Xs];

The Tuple type is completely analogous: it matches tuples of arbitrary sizes, i.e., expressions of the form () and (X|Xs).

The predefined Bool type is a means to refer to objects which are truth values. It can be thought of as being predefined as follows:

public type Bool = const false, true;

Types like the built-in Bool type, which only consist of nullary const symbols, are also called enumeration types. You can easily define such types yourself, e.g.:

type Day = const sun, mon, tue, wed, thu, fri, sat;

The Q language provides special support for enumeration types (including the built-in Bool type, and also the Char type), by means of the following operations:

Thus, for instance, sun < mon => true, ord sun => 0, and succ sun => mon. Note that there is no builtin operation for converting ordinal numbers back to the corresponding members of a given type. However, using the builtin isconst function (see 10.7 Miscellaneous Functions) and the standard library while function (see 11.1 Standard Functions), you can list all members of an enumeration type starting at a given constant A as follows:

enum A                  = while isconst succ A;

Now it is an easy matter to define a variable which stores the member list:

var days;
def days                = tuple (enum sun);

Note that we convert the list of days to a tuple here, which gives us constant-time access to the individual members, and is also more space-efficient. Using these definitions, we have the following:

==> days

==> days!4

As already mentioned, the built-in Char type is also an enumeration type, which consists of all the characters in the local character set. Thus the enum function defined above also works on character values.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.3 Sub- and Supertypes

The Q programming language also provides a subtype concept similar to the notion of single inheritance in object-oriented programming languages such as Smalltalk. For instance, we can modify our declaration of the BinTree type (cf. 8.1 Using Type Guards) in order to make BinTree a subtype of the supertype SearchTree as follows:

public type BinTree : SearchTree = private const nil, bin X T1 T2;

Quite often, supertypes are abstract types which do not provide their own set of constructor symbols, but are simply used to factor out common operations shared among several "concrete" types. For instance, the SearchTree type might have been declared simply as follows:

public type SearchTree;

Now variables of type SearchTree will also match objects of its subtype BinTree, as well as of any other subtype of SearchTree. We can turn the union and diff functions from 8.1 Using Type Guards, into operations on the SearchTree type as follows:

union T1:SearchTree T2:SearchTree
                        = foldl insert T1 (members T2);

diff T1:SearchTree T2:SearchTree
                        = foldl delete T1 (members T2);

As the next step, we might introduce another type AVLTree providing the same interface operations insert, delete and members as the BinTree type, but implementing these operations in terms of AVL trees rather than simple binary trees. (AVL trees are a variant of binary search trees in which the trees are kept balanced, and thus logarithmic insertion and deletion times can be guaranteed.) If we make AVLTree another subtype of SearchTree, then the union and diff operations can be applied to AVLTree objects just as well as to BinTree's. In fact, the operations will even work if we mix argument types, e.g., provide a BinTree as the first argument of union and an AVLTree as the second! By these means, it is possible to define polymorphic operations which are applicable to several different types sharing the same (subset of) interface functions.

For the sake of concreteness, here is an implementation of the AVLTree type. The shl, shr, rol and ror functions implement the common AVL tree rotation operations which are used to keep the tree balanced; see [Bird/Wadler 1988] for details. We assume that the declaration of the SearchTree type is in a separate module searchtree.q, along with the declarations of the shared members, insert and delete operations, as well as the declarations and definitions of the generic union and diff functions.

include searchtree;

/* H denotes the height of a nonempty AVL tree */

public type AVLTree : SearchTree = private const nil, bin H X T1 T2;

public mkavltree Xs;

private mknode X T1 T2;
private join T1 T2, init T, last T, height T, slope T, rebal T;
private rol T, ror T, shl T, shr T;

mkavltree Xs:List       = foldl insert nil Xs;

members nil             = [];
members (bin H X T1 T2) = members T1 ++ [X|members T2];

insert nil Y            = bin 1 Y nil nil;
insert (bin H X T1 T2) Y
                        = rebal (mknode X (insert T1 Y)) T2 if X>Y;
                        = rebal (mknode X T1 (insert T2 Y)) if X<Y;
                        = bin H Y T1 T2 if X=Y;

delete nil Y            = nil;
delete (bin H X T1 T2) Y
                        = rebal (mknode X (delete T1 Y) T2) if X>Y;
                        = rebal (mknode X T1 (delete T2 Y)) if X<Y;
                        = join T1 T2 if X=Y;

join nil T2             = T2;
join T1 T2              = rebal (mknode (last T1) (init T1) T2) otherwise;

init (bin H X T1 nil)   = T1;
init (bin H X T1 T2)    = rebal (mknode X T1 (init T2)) otherwise;

last (bin H X T1 nil)   = X;
last (bin H X T1 T2)    = last T2 otherwise;

/* mknode constructs a tree node, computing the height value */

mknode X T1 T2          = bin (max (height T1) (height T2) +1) X T1 T2;

/* height and slope compute the height and slope (difference between
   heights of the left and the right subtree), respectively */

height nil              = 0;
height (bin H T1 T2)    = H;

slope nil               = 0;
slope (bin H X T1 T2)   = height T1 - height T2;

/* rebal rebalances after single insertions and deletions */

rebal T                 = shl T if slope T = -2;
                        = shr T if slope T = 2;
                        = T otherwise;

/* rotation operations */

rol (bin H1 X1 T1 (bin H2 X2 T2 T3))
                        = mknode X2 (mknode X1 T1 T2) T3;
ror (bin H1 X1 (bin H2 X2 T1 T2) T3)
                        = mknode X2 T1 (mknode X1 T2 T3);

shl (bin H X T1 T2)     = rol (mknode X T1 (ror T2)) if slope T2 = 1;
                        = rol (bin H X T1 T2) otherwise;

shr (bin H X T1 T2)     = ror (mknode X T1 (ror T2)) if slope T2 = -1;
                        = ror (bin H X T1 T2) otherwise;

[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by Albert Gräf on October, 14 2003 using texi2html