[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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] | [ ? ] |
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] | [ ? ] |
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:
succ
and pred
functions (see 10.1 Arithmetic Functions) produce the successor and the predecessor of an enumeration
type member.
ord
function (see 10.4 Conversion Functions) computes the
ordinal number of an enumeration type member.
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 (sun,mon,tue,wed,thu,fri,sat) ==> days!4 thu |
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] | [ ? ] |
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] | [ ? ] |