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

11. The Standard Library

This chapter gives an overview of the data types and operations provided by the standard library modules supplied with the Q programming system. The library currently consists of the following scripts:

print diagnostics
various system functions (external module)
comparison of lists and tuples
complex numbers
conditional expressions
print error messages
PostScript graphics interface
an implementation of the lambda calculus
list comprehensions
mathematical functions
standard prelude
algorithms to sort a list
shared declarations of the container data structures (cf. stdtypes.q)
a collection of common standard functions
a collection of efficient container data structures
an implementation of streams
additional string functions
type-checking predicates

The prelude.q script implements the standard prelude, which loads the entire collection (except graphics.q which must always be imported explicitly).

The stdlib.q script has those operations which will probably be used most frequently by the average programmer; it contains a lot of additional list processing functions and other useful stuff mostly adopted from [Bird/Wadler 1988]. This module is also included by many other library scripts. Historically, it was the first script written for the standard library.

The stdtypes.q script simply includes all modules which implement common container data structures; currently these are array.q, bag.q, dict.q, hdict.q, heap.q and set.q, see 11.6 Standard Types. Some declarations shared by these modules are in the stddecls.q script.

The clib.q module gives access to various useful "system" functions from the C library, including C-style formatted I/O, binary file I/O, process and thread management and regular expression routines. The operations of this module are mostly written in C, using the C language interface discussed in C. C Language Interface. This module is described in its own chapter, see 12. Clib.

Besides this, the standard distribution of the Q programming system also includes some additional modules for interfacing to GNU dbm, ODBC, Octave, Tcl/Tk, GGI (a portable graphics interface) and IBM's Data Explorer visualization software. Preliminary documentation for these modules can be found in the etc subdirectory of your Q installation directory (usually in /usr/share/q or /usr/local/share/q).

11.1 Standard Functions  
11.2 String Functions  
11.3 Comparison Functions  
11.4 Type-Checking Predicates  
11.5 Sorting Algorithms  
11.6 Standard Types  
11.7 Lambda Calculus  
11.8 List Comprehensions  
11.9 Streams  
11.10 Conditional Expressions  
11.11 Mathematical Functions  
11.12 Complex Numbers  
11.13 Graphics  
11.14 Diagnostics and Error Messages  

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

11.1 Standard Functions

The stdlib.q script provides frequently used list operations and other stuff mostly adopted from [Bird/Wadler 1988].

abs X
absolute value of X
all P Xs
verify that each element of the list Xs satisfies the predicate P
any P Xs
verify that the list Xs contains an element satisfying predicate P
append Xs Y
append a value Y to the list or tuple Xs
apply X Y
apply function X to argument Y
cat Xs
concatenate a list of lists
compose X Y
function composition: compose X Y Z => X (Y Z)
cons X Xs
prepend an element to a list or a tuple
cst X
constant-valued function: cst X Y => X
do F Xs
apply a function F to each member of a list Xs, return ()
drop N Xs
remove the first N elements from the list Xs
dropwhile P Xs
remove elements from the beginning of Xs while the predicate P is satisfied
eq X Y
syntactic equality (cf. 7.2 Non-Linear Equations)
filter P Xs
filter a list with a predicate
foldl F A Xs
foldl1 F Xs
fold-left over nonempty lists
foldr F A Xs
foldr1 F Xs
fold-right over nonempty lists
fst Xs
return first element of a tuple
hd Xs
return the head element of a list
hds Xs
return the list of all head elements in a list of lists
the identity function: id X => X
init Xs
return list Xs without its last element
iter N F A
generate the list of the first N values A, F A, F (F A), ...
last Xs
return the last element of a list
map F Xs
apply function F to each member of a list
max X Y
maximum of two values
min X Y
minimum of two values
mklist X N
create a list of N X's
neg P
negate a predicate
neq X Y
syntactic inequality
null Xs
check whether a string, list or tuple is empty ([] resp. ())
nums N M
generate a list of numbers in a given range
numsby K N M
generate a list of numbers with a given step size
pair X Y
construct a pair
pop Xs
remove the head element from a list or a tuple
prd Xs
product of a list of numbers
push Xs X
prepend an element to a list or a tuple (cons with arguments reversed)
reverse Xs
reverse a list
scan F A Xs
apply foldl to every initial part of a list
scan1 F Xs
apply foldl1 to every nonempty initial part of a list
sgn X
sign of a number
snd Xs
return second element of a tuple
sum Xs
sum of a list of numbers
take N Xs
select the first N elements from the list Xs
takewhile P Xs
select elements from the beginning of Xs while the predicate P is satisfied
tl Xs
remove the head element from a list
tls Xs
return a list of lists with all head elements removed
top Xs
return the head element from a list or a tuple
transpose Xs
transpose a list of lists
trd Xs
return third element of a tuple
triple X Y Z
construct a triple
tuplecat Xs
concatenate a list of tuples
until P F X
repeat applying F to X until P is satisfied
unzip Xs
transform a list of pairs into a pair of lists
unzip3 Xs
unzip with triples
while P F A
list repeated applications of F to A while P is satisfied
zip Xs Ys
take two lists and return a list of corresponding pairs
zip3 Xs Ys Zs
zip with three lists
zipwith F Xs Ys
take two lists and map a binary function to corresponding elements
zipwith3 F Xs Ys Zs
zipwith with three lists

The stdlib.q script also overloads succ and pred with the usual successor and predecessor functions on integers. For instance, succ 5 = 6 and pred 0 = -1.

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

11.2 String Functions

The string.q script provides a collection of additional string functions. Currently the following operations are implemented:

chars S
return the list of individual characters in S
join DELIM Xs
concatenate a list of strings, interpolating the given DELIM string between each pair of consecutive strings in the list
split DELIM S
split a string into a list of substrings delimited by characters in the given DELIM string
strcat Xs
concatenate a list of strings

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

11.3 Comparison Functions

The comp.q script overloads the =, <>, <, >, <= and >= operators with rules for deciding equality and inequality of lists and tuples, and rules for ordering lists lexicographically. That is, both tuples and lists can be compared with = and <>, which is done by checking that the operands are of the same size and recursively comparing all members of the operands. Lists can also be compared lexicographically by recursively comparing the list members; the first unequal members decide the comparison. This works just like the lexicographic comparison of strings. Thus, e.g., [1,2] is considered to be less than both [1,3] and [1,2,1], but more than [1,1,3] or [0,5].

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

11.4 Type-Checking Predicates

The typec.q script contains a collection of predicates which check whether an expression is of a given type. The following operations are provided:

isbool X
check for truth values
ischar X
check for single character strings
isexcept X
check for Exception values (cf. 10.6 Exception Handling)
isfile X
check for file objects
isfloat X
check for floating point numbers
isint X
check for integers
islist X
check for lists
isnum X
check for numbers
isstr X
check for strings
issym X
check for function and variable symbols (special form)
istuple X
check for tuples

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

11.5 Sorting Algorithms

The sort.q script provides mergesort and quicksort algorithms for sorting a list using a given order predicate:

msort P Xs
mergesort algorithm
qsort P Xs
quicksort algorithm

The mergesort algorithm is more involved than quicksort, but may run much faster if input lists are large enough and are already partially sorted. Both algorithms take an order predicate as their first argument, which makes it possible to sort lists using different criteria. The order predicate must be a function accepting two arguments, and must return true iff the first argument is strictly less than the second. For instance, to sort a list in ascending order, you could say:

==> qsort (<) [1,5,3,2,4]

By reversing the order predicate, the list is sorted in descending order:

==> qsort (>) [1,5,3,2,4]

Custom order predicates also allow you to sort a list according to different sort keys. For instance, the following example shows how to sort a list of pairs using the first component of each pair as the sort key (see 11.7 Lambda Calculus, for a description of the lambda function):

==> def L = [(1,2),(5,1),(3,3),(1,1),(4,5)]

==> def le1 = lambda X (lambda Y (fst X < fst Y))

==> qsort le1 L

Both algorithms provided by this module are "stable", i.e., they preserve the relative order of list elements with "equal" sort keys. This is important when successive sorts are used to order elements according to different criteria. For instance:

==> def le2 = lambda X (lambda Y (snd X < snd Y))

==> qsort le2 L

==> qsort le1 _

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

11.6 Standard Types

The stdtypes.q script implements a collection of efficient container data structures, which currently comprises arrays, heaps (priority queues), ordered sets and bags, and (ordered as well as hashed) dictionaries. The different data types are actually implemented in the scripts array.q, bag.q, dict.q, hdict.q, heap.q and set.q. Many operations of these modules are overloaded; the declarations of these operations can be found in the stddecl.q script which is included by the different modules.

All data structures support equality checking with = and <>, as well as the operation # to determine the size of an object (number of elements it contains). Furthermore, the set and bag data structures overload the <, >, <= and >= operators to implement subset/subbag comparisons and the +, - and * operators to compute the union, difference and intersection of two sets or bags, respectively.

11.6.1 Arrays  
11.6.2 Heaps  
11.6.3 Sets  
11.6.4 Bags  
11.6.5 Dictionaries  
11.6.6 Hashed Dictionaries  

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

11.6.1 Arrays

The array.q script provides a zero-based array data structure Array with logarithmic access times, implemented as size-balanced binary trees. The following operations are provided:

array Xs
create an array from list Xs
array2 Xs
create a two-dimensional array from a list of lists
return the empty array
mkarray X N
create an array consisting of N X's
mkarray2 X (N,M)
create a two-dimensional array with N rows and M columns
isarray X
check whether X is an array
null A
check whether A is the empty array
A1 = A2, A1 <> A2
array equality/inequality
size of an array
return Ith member of an array
two-dimensional subscript
members A, list A
list the members of A
members2 A, list2 A
list a two-dimensional array
first A, last A
return the first and last element of an array
rmfirst A, rmlast A
remove the first and last element from an array
insert A X
insert X at the beginning of A
append A X
append X at the end of A
update A I X
replace the Ith member of A by X
update2 A (I,J) X
update two-dimensional array

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

11.6.2 Heaps

The heap.q script provides an efficient heap (priority queue) data structure Heap implemented as size-balanced binary trees. Heaps allow quick (i.e., constant-time) access to the smallest element, and to insert new elements in logarithmic time. The present implementation does not allow fast random updates of heap members; if such functionality is required, bags should be used instead (see 11.6.4 Bags).

Heap members must be ordered by the <= predicate. Multiple instances of the same element may be stored in a heap; however, the order in which equal elements are retrieved is not specified.

The following operations are provided:

return the empty heap
heap Xs
construct a heap from a list of its members
isheap X
determine whether X is a heap
null H
check whether H is the empty heap
H1 = H2, H1 <> H2
heap equality/inequality
size of a heap
members H, list H
list the members of H in ascending order
first H
return the first element of H
rmfirst H
remove the first element from H
insert H X
insert X into H

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

11.6.3 Sets

The set.q script provides an ordered set data structure Set implemented as AVL trees, and thus guaranteeing logarithmic access times. The following operations are defined in set.q:

return the empty set
set Xs
create a set from a list of its members
isset X
check whether X is a set
null M
check whether M is the empty set
member M X
check whether M contains element X
M1 = M2, M1 <> M2
set equality/inequality
M1 < M2, M1 > M2, M1 <= M2, M1 >= M2
set comparison
M1 + M2, M1 - M2, M1 * M2
set union, difference and intersection
size of a set
members M, list M
list the members of M in ascending order
first M, last M
return the first and last member of M
rmfirst M, rmlast M
remove the first and last member from M
insert M X
insert X into M
delete M X
delete X from M

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

11.6.4 Bags

The bag.q script defines the type Bag as a variant of the set data structure which may contain multiple instances of the same element. The operations are analogous to those of the set data structure; see 11.6.3 Sets. The emptybag function returns the empty bag, and bag Xs constructs a bag from a list Xs of its members. The isbag predicate checks whether its argument is a bag.

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

11.6.5 Dictionaries

The dict.q script supplies an (ordered) dictionary data structure Dict which maps keys from an ordered set to corresponding values. Like sets and bags, dictionaries are implemented as AVL trees, thus guaranteeing logarithmic access times to individual members of the dictionary. The following operations are defined in dict.q:

return the empty dictionary
dict XYs
create a dictionary from a list of key/value pairs
mkdict Y Xs
create a dictionary from a list of keys and an initial value
isdict X
check whether X is a dictionary
null D
check whether D is the empty dictionary
member D X
check whether D contains X as a key
D1 = D2, D1 <> D2
dictionary equality/inequality
size of a dictionary
return the value Y associated with X in D
members D, list D
list the members (key/value pairs) of D in ascending order by key
keys D
list the keys of D in ascending order
vals D
list the corresponding values
first D, last D
return the first and last member of D
rmfirst D, rmlast D
remove the first and last member from D
insert D (X,Y)
insert a key/value pair (X,Y) into D; update an existing entry for X if present
delete D X
remove key X from D
update D X Y
same as insert D (X,Y)

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

11.6.6 Hashed Dictionaries

The hdict.q script implements hashed dictionaries (HDict type), a variation of the Dict type which uses hashed key values obtained with the builtin hash function. The actual key-value pairs are stored in "buckets" for each hash value. This kind of data structure is also known as "hashes" or "associative arrays" in other programming languages.

The main advantage of the HDict type is that key values can be of any type and do not have to belong to an ordered set. For instance, hdict [(0,1),(foo,2),("bar",3)] is a legal HDict value which maps the integer 0 to 1, the symbol foo to 2, and the string "bar" to 3.

There are some other notable differences between the Dict and the HDict type. First of all, a HDict stores it members in an apparently random order which may depend on the order in which new entries are added to the dictionary. Hence equality testing for HDicts is more involved than for Dicts, as the member lists of two "equal" HDicts may be arbitrary permutations of each other. This also means that the first, rmfirst, last and rmlast operations do not make much sense with hashed dictionaries and are not supported by the HDict type. Moreover, key values are always compared syntactically when looking up and updating entries. Hence, e.g., 0 and 0.0 are different key values in a HDict object, whereas they are considered to be the same for the Dict type.

Apart from these differences, the operations of the HDict and Dict types work analogously. The HDict constructors are named emptyhdict, hdict and mkhdict which take the same arguments as the corresponding Dict constructors, and the ishdict predicate checks for HDict values.

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

11.7 Lambda Calculus

The lambda.q script implements the special form lambda which can be used to create simple function objects "on the fly". The lambda function is invoked as:

lambda PAT EXPR

The PAT argument can be an arbitary expression which is to be matched against the actual parameter of the lambda function. If the parameter matches, the value of EXPR is returned, with the variables in PAT replaced by the corresponding values:

==> def foo = lambda (X,Y) (2*X+Y); foo (2,3)

==> def bar = lambda X (lambda Y (2*X+Y)); bar 2 3

As indicated, multi-argument functions are created using nested lambda's. Each variable is bound by the innermost lambda in which it occurs:

==> lambda X ((lambda X (X*X)) (X+1)) 2

Pattern matching is performed by traversing the pattern from left to right, and each variable is bound as it is matched. Note that, to speed up lambda compilation, it is not verified that the lambda pattern is "linear", i.e., contains each variable only once. Consequently, if a variable occurs more than once in the pattern, the different occurrences are simply matched independently from each other, and the value bound to the variable is the actual value which corresponds to the rightmost occurrence:

==> lambda (X,X) (2*X) (99,101)

If a pattern match fails, you will see some unevaluated matching "combinators" in the output. This can be cured by making judicious use of exceptions. (See the section on lambda internals below for more details on this.)

Lambdas can also be used to substitute variables in special forms like the quote operator:

==> lambda X '(X+1) (2*3)

Note that while the pattern and body of a lambda expression are special arguments, the actual parameter expected by the function created with lambda is non-special. Thus the value 2*3 in the example above is evaluated before it is substituted for the X variable. If you want to prevent lambda arguments from being evaluated, you have to protect them with a special form (e.g., a quote), and extract the value for use in the lambda body using an appropriate pattern:

==> lambda 'X '(X+1) '(2*3)

The lambda function normally expands nested lambdas in the body of a lambda, s.t. variables are always bound by the innermost lambda in which they occur. However, this recursive lambda expansion is inhibited inside the arguments of special forms. This means that lambda constructs inside a special form are effectively treated as literal expressions:

==> lambda X '(lambda X (2*X)) 77
'(lambda 77 (2*77))

(Special form detection uses static analysis of the lambda body, hence this only works with special forms explicitly present in the lambda body. That is, a non-special function in the lambda body will never be treated as special, even if it reduces to a special form at runtime.)

A word of caution: The lambda function uses free variable symbols in the pattern to denote the "lambda variables". However, for the interpreter a lambda term is just a normal expression, and hence it will perform its own variable replacement for left-hand side, i.e., bound, variables in an equation. Hence, if you have a lambda expression on the right-hand side of an equation, you should make sure that you only use free variable symbols for the lambda variables.

Lambda Internals

Chances are that when using lambdas, occasionally you will be confronted with partially evaluated function objects which consist of a bunch of weird-looking symbols like _A, _HK etc. A quick look "behind the scenes" will help you understand what's going on with these objects.

To improve performance, lambdas are not evaluated directly, but are "compiled" to function objects consisting of combinators which handle the variable matching and replacement process. The current implementation is based on the standard combinatorial calculus as described, e.g., in [Henson 1987], which has been extended to handle pattern matching, and to perform lambda substitutions in lists and tuples in an efficient manner.

A complete description of the combinatorial calculus is well beyond the scope of this little section, but here is a brief description of the most important combinators:

_H X, _HL X, _HT X, _HK K X
These are the matching combinators, which match, respectively, applications, lists, tuples and constants in the argument value.
_A X, _L X, _T X
Combinators for constructing function applications, lists and tuples.
_I, _K K
The identity and the constant function.
_S X Y, _B X Y, _C X Y
The "argument dispatching" combinators, which pass on an argument to the X and Y subfunctions. _S dispatches to both subterms, _B to Y, and _C to X only. Additional combinators like these, but named with a trailing L or T, are used to dispatch arguments into lists and tuples.

All combinators are implemented as special forms, in order to prevent the function body from being evaluated before the actual lambda parameter is applied. There also is an additional set just like the one sketched out above (stropped with two leading underscores instead of one), in which also the lambda argument is protected. These combinators are used to protect special argument subterms extracted from the lambda argument from premature evaluation.

For example, here is the combinator expression for the lambda (X,Y) (X*Y) function:

_HT (_B _HT (_B (_B (_HK ())) (*)))

This looks a bit frightening at first sight, but once we strip the matching combinators and the _B combinator which just dispatches argument values to the correct places, we are left with nothing but our familiar (*) function.

All combinators are provided as public symbols, so you can invoke them directly, if you know what you are doing. You can also extend the combinator definitions with additional rules, e.g., in order to implement exceptions in response to argument mismatches of the matching combinators. Here are some rules which will do the trick:

_H X Y                   = throw '(_H X Y);     // bad application
_HL X Y                  = throw '(_HL X Y);    // bad list
_HT X Y                  = throw '(_HT X Y);    // bad tuple
_HK K X Y                = throw '(_HK K X Y);  // bad constant
// combinators for special arguments
__H X Y                  = throw '(__H X Y);    // bad application
__HL X Y                 = throw '(__HL X Y);   // bad list
__HT X Y                 = throw '(__HT X Y);   // bad tuple
__HK K X Y               = throw '(__HK K X Y); // bad constant

Performance Considerations

The size of a compiled lambda, i.e., the size of the corresponding combinator expression, is at most quadratic in the size of the lambda expression, and at most linear in the pattern size. The time needed to actually perform the variable replacements for a given argument is roughly proportional to the size of the combinator term. This should be efficient enough for most practical purposes, as long as you avoid huge expressions in the lambda body.

It should also be pointed out that the size of combinator terms explodes combinatorically with nested lambda expressions, so there also is a practical limit on the parameter count in multi-argument lambdas. (So-called "supercombinators" might be used to cure this, but these have not been implemented yet.)

Thus lambdas are most useful for defining simple ad-hoc functions "on the fly". Don't expect any performance miracles. A conventional function definition using equations incurs much less overhead, since it uses the built-in pattern matching and reduction engine of the interpreter.

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

11.8 List Comprehensions

The list.q script provides the special form listof which allows to specify a list of values in a manner similar to the way sets are described in mathematics:


CLAUSES may either be a singleton value or a tuple consisting of binding clauses and conditional clauses. A binding clause is an expression of the form X in Xs (using the relational in operator, cf. 6.4.3 Relational Operators) which specifies that the (presumably linear) pattern X should be matched in turn to each member of the list Xs; only values matching the pattern will be extracted, and free variables in the pattern are bound to their corresponding values using lambda. Binding clauses are considered from left to right, which means that a clause may refer to any variable introduced in an earlier binding clause.

Any other expression specifies a conditional clause which must evaluate to a truth value; only those elements will be listed for which the conditional clause is satisfied.

List comprehensions are best illustrated by an example. The following equations define an operation which returns the list of all triples (I,J,I+J) s.t. 1<=J<I<=N and I+J is a prime number.

prime_sum_pairs N       = listof (I,J,I+J) (I in nums 1 N,
                          J in nums 1 (I-1), isprime (I+J));
isprime N               = (N>1) and then prime_test N 2;
prime_test N M          = true if M*M>N;
                        = false if N mod M = 0;
                        = prime_test N (M+1) otherwise;

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

11.9 Streams

The stream.q script implements streams, a variant of the list data structure with "call be need" evaluation. Streams can be used to represent infinite sequences of objects, since the objects in the sequence are only produced as they are required in the course of a computation.

The Stream type is declared as follows:

public type Stream = special const nil, bin X Xs;

Most list operations are overloaded and work analogously to their list counterparts. Furthermore, the script incorporates rules for comparing streams using the lexicographic order, and provides the following additional operations:

isstream X
check whether an object is a stream
stream Xs
convert a list to a stream
list Xs
convert a stream to a list
numstream N
generate the stream of all numbers >=N
numstreamby K N
generate a number stream with given step size
mkstream X
generate an infinite stream of X's
iterate F A
generate the stream of all values A, F A, F (F A), ...
streamcat Xs
concatenate a stream or list of streams and/or lists (see comments below)
streamof X CLAUSES
stream comprehensions (see discussion below)

Operations like #, all, foldl will of course cause troubles with infinite streams since it can take them an infinite time to compute the result. The same holds for the foldr function unless the folded operation is a special form.

The streamcat function (which is analogous to the cat function on lists defined in stdlib.q) concatenates a stream of streams in a fully lazy manner, i.e., you can concatenate a (possibly infinite) stream of (possibly infinite) streams. The argument of streamcat can actually be a list or stream, which consists of any mixture of streams and lists. The result is always a stream.

The streamof special form works like listof (see 11.8 List Comprehensions), except that it accepts both streams and lists, which may contain an arbitrary collection of stream and list values, and returns a stream instead of a list as the result. For instance, the following recursive definition is used to generate the stream of all possible permutations of a given list Xs:

perms []                = stream [[]];
perms Xs                = streamof [Y|Ys] (Y in stream Xs,
                          Ys in perms (filter (neq Y) Xs));

Here is an example for the use of infinite streams. It implements the well-known sieve of Erathosthenes:

ints N                  = bin N (ints (N+1));
primes                  = sieve (ints 2);
sieve (bin X Xs)        = bin X (sieve (filter (ndivby X) Xs));
ndivby M N              = N mod M <> 0;

A common pitfall with streams is that the size of a recursively defined stream expression can grow very fast, unless some care is taken. For instance, a Haskell programmer might be tempted to define the stream of all Fibonacci numbers as follows:

fibs = bin 1 (bin 1 (zipwith (+) fibs (tl fibs)));

However, this definition has a similar defect as the naive definition of the fib function in 7.1 Equations, in that fibs invokes itself twice, and hence the tails of this stream grow exponentially with the number of applied tl operations. Of course this also means that the time needed to extract the Nth member of the stream grows exponentially with N. Haskell programmers get away with this only because their compiler applies a clever optimization technique. In Q, the right way to define this stream is to work with a recursively defined stream which keeps track of pairs of consecutive Fibonacci numbers, like so:

fibs                    = fibs2 1 1;
fibs2 A B               = bin A (fibs2 B (A+B));

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

11.10 Conditional Expressions

The cond.q script provides some functions for implementing conditional expressions:

ifelse ~P X Y
simple conditional expression (special form)
matchp P ~X
match pattern against expression (special form)
switch CASES
general conditional expression
match X CASES
pattern-matching conditional

The ifelse special form has already been discussed in 9.1 Basic Concepts. It returns either X or Y, depending on whether the first argument is true or false.

A more general conditional expression is also provided, which allows you to discriminate between an arbitrary number of cases. It has the form

switch (case P1 X1, case P2 X2, ...)

and returns the first value X for which the corresponding condition P evaluates to true. The case tuple can also contain a default X expression which denotes the default value to be returned when the preceding cases have failed. If no case matches, and no default clause is present, switch returns (). The case and default symbols are special constructor symbols declared as follows:

public special const case X Y, default X;

The matchp predicate returns true if the expression given as the second argument matches the literal pattern in the first argument, false otherwise.

The match conditional is a specialized form of switch in which the first case argument of each case is a pattern to be matched against the given expression X. If the expression matches, the second case argument is evaluated, with the variables in the pattern bound to the corresponding values using lambda.

Some examples:

fac N                   = ifelse (N>0) (N*(fac (N-1))) 1;

f X Y Z                 = switch (case (X>0) (foo X),
                                  case (Y>0) (bar Y),
                                  default Z);

g X                     = match X (case (foo Y Z) (Y*Z),
                                   case (bar Y Z) (Y/Z),
                                   default X);

==> fac 41

==> f (-1) 1 0
bar 1

==> g (bar 9 10)

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

11.11 Mathematical Functions

The math.q script contains some additional operations on floating point numbers:

asin X, acos X, tan X
additional trigonometric functions
lg X, log X
base 2 and 10 logarithms
sinh X, cosh X, tanh X
hyperbolic functions
asinh X, acosh X, atanh X
inverse hyperbolic functions

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

11.12 Complex Numbers

The complex.q script implements complex numbers as pairs (X,Y) of integer or floating point values X and Y. It generalizes the usual arithmetic operations (including exponentiation), sqrt, exp, logarithms, trigonometric and hyperbolic functions accordingly. The following basic operations are also provided:

iscomplex Z
check whether argument is complex (including ordinary numbers)
abs Z, arg Z
absolute value and argument
re Z, im Z
real and imaginary part
conj Z
complex conjugate

All these operations apply to both real and complex numbers. The arg function returns the polar angle (in radians), thus (abs Z,arg Z) denotes the polar coordinates of a complex number Z.

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

11.13 Graphics

The graphics.q script implements an interface to Adobe's PostScript language [Adobe 1990]. PostScript is a page description language which has become one of the main standards in the desktop publishing world. The nice thing about PostScript is that page descriptions are device-independent -- the same page description can be used for different output devices such as a screen previewer or a laser printer. The graphics.q script allows you to produce graphics output on any PostScript device. Note that, as already pointed out, this script does not belong to the set of "standard" scripts included by the prelude, and hence has to be imported explicitly if you want to use the operations described in the following.

The graphics device is implemented by the GRAPHICS variable, which by default is assigned to standard output. This is useful for debugging purposes, but in a real application you will of course redirect the output to some PostScript file or device, which can be done by assigning a suitable value to the GRAPHICS variable. Any file object open for writing will do, however the script also provides the following convenience functions which each return an output file or pipe which can be used as the value of the GRAPHICS variable:

pipe to the ghostscript program (see below)
pipe to ghostview (see below)
printer device (usually a pipe to lpr(1))
filedev X
output file with name X
the null device (a synonym for filedev "/dev/null", or filedev "nul" under DOS/Windows)

For instance, you define the graphics device as a pipe to ghostscript as follows:

def GRAPHICS = gsdev;

You can either add this definition to your main script, or enter it directly at the command prompt of the interpreter (see B.2 Command Language).

Ghostscript is a popular PostScript previewer available for a wide range of different platforms. Ghostview is an improved X interface for ghostscript. A similar program, GSView, is also available for the Windows operating system.

Please note that currently only the nulldev and filedev devices are available when running under DOS or Windows (the remaining devices types are assigned to nulldev), since GSView currently does not support input from a pipe. To preview your PostScript output under DOS/Windows, use filedev to set up an output file and then invoke Ghostscript or GSView manually. For instance (assuming that the gsview32 program is on your DOS path):

==> def GRAPHICS = filedev "graphics.ps"

==> // output your PostScript graphics here ...

==> !gsview32 graphics.ps

If output goes to a printer or a file, you will probably need a minimal header which identifies the file as a PostScript document. To include such a header in the output file, use the psheader function before invoking any other graphics operation:

==> psheader

You can also set up a custom header and include other DSC and EPSF comments by means of the ps function; see 11.13.8 DSC and EPSF Comments, for details.

In the following we give an overview of the graphics operations in the PostScript language, as they are provided by this module, and describe the implemented functions. For more details about PostScript please refer to [Adobe 1990].

11.13.1 Coordinate System  
11.13.2 Overview of Graphics Operations  
11.13.3 Path Construction  
11.13.4 Painting  
11.13.5 Clipping  
11.13.6 Graphics State  
11.13.7 Miscellaneous Operations  
11.13.8 DSC and EPSF Comments  

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

11.13.1 Coordinate System

The PostScript coordinate system has its origin (0,0) in the lower left corner of the output page or display window, with the positive X and Y axes extending horizontally to the right and vertically upward, respectively. The default unit length is 1 point which is 1/72 of an inch.

The origin of the coordinate system, as well as the unit lengths and orientation of the X and Y axes can be changed by means of the translate, scale and rotate operations, cf. 11.13.6 Graphics State.

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

11.13.2 Overview of Graphics Operations

The process of painting a graphics object usually consists of the following three steps:

A path is an ordered sequence of straight and curved line segments. The individual segments may be connected to each other or they may be disconnected. Thus a path may consist of several connected pieces which are referred to as the subpaths of the path. In a subpath, each line segment starts at the point where the previous segment ends. The newpath function is used to begin a new path. A new subpath is obtained by invoking moveto which specifies the first point in the subpath. Various operations are provided to add straight and curved line segments to the current subpath. For instance, a path consisting of three straight line segments may be denoted as follows:

newpath || moveto 0 0 || lineto 1 0 || lineto 1 1 || lineto 0 1

The last point on the current subpath can be connected back to its starting point (usually the last point specified with moveto) by closing the subpath with the closepath operation. For instance, a rectangle is specified as follows:

newpath || moveto 0 0 || lineto 1 0 || lineto 1 1 || lineto 0 1 ||

Having constructed a path, the stroke function draws the line segments contained in the path. Alternatively, fill may be used to fill the interior of the path (for this purpose the entire path should consist of closed subpaths).

The precise appearance of stroked and filled objects on the output page is controlled by a collection of parameters referred to as the graphics state. Various operations are provided for changing these parameters. For instance, you can set the linewidth and dash pattern used by stroke, the color used by the stroke and fill operations, and the scale and translation of the coordinate axes. The current settings can be saved on a stack using gsave and restored (popped from the stack) with grestore.

Another important parameter is the current clipping path which specifies the regions on the page which can be affected by the painting operations. By default, the paintable area is the whole page. In order to restrict painting to a user-defined region, a path is constructed as usual, and then the clip function is used to set this path as the clipping path. Subsequent paint operations will only paint the interior of the clipping path, i.e., the region which would have been filled had we applied the fill operation instead of clip to the constructed path. Multiple applications of clip are accumulative. That is, clip intersects the current clipping area (as defined by previous invokations of clip) with the interior of the current path.

The treatment of textual output is somewhat special. It is possible to define a path consisting of the outlines of the characters in a given text string by means of the charpath function. More commonly, however, text strings are simply displayed at a given position which is accomplished by means of the show function. For instance, to display a text string S at a position (X,Y) on the current page the following expression is used:

moveto X Y || show S

The graphics.q script also provides several operations which deal with a graphics page as a whole. First of all, showpage emits the current page, and prepares for the next page by erasing the current page. The copypage operation is like showpage, but keeps the contents of the current page. This allows you to accumulate the contents of several pages. Both showpage and copypage are mainly used when output goes to a printer.

Two additional operations are provided for interactive use, when output goes to a display window. The erasepage function causes the contents of the current page to be erased. The flushpage operation updates the display, like showpage or copypage, but does not start a new page. (To improve performance, graphics output under the X window system is usually performed in larger chunks. The flushpage operation is required to synchronize the display by flushing any unwritten data.) Note that this operation is not part of the PostScript standard, but only works with Ghostscript and possibly some similar Postscript viewers.

If you want to achieve special effects which cannot be implemented in terms of the operations provided by graphics.q, you can directly invoke PostScript commands by means of the ps function. Also, you can copy a PostScript file to the graphics device with the psfile operation. As an example for the ps function, operations to display a string right-justified or centered at the current position can be implemented as follows:

showright S:String      = ps (psstr S++
                        " dup stringwidth pop neg 0 rmoveto show\n");
showcenter S:String     = ps (psstr S++
                        " dup stringwidth pop 2 div neg 0 rmoveto show\n");

(The psstr function converts a string to PostScript syntax; see 11.13.7 Miscellaneous Operations.) The ps function is also useful to include DSC and EPSF comments in your graphics output if this is necessary. See 11.13.8 DSC and EPSF Comments, for details.

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

11.13.3 Path Construction

The graphics.q script defines the following collection of operations to define the current path used by the painting and clipping operations:

start a new path

close the current subpath

set the current path to the current clipping path

moveto X Y
absolute move to position (X,Y)

rmoveto DX DY
move relatively by DX units in horizontal and DY units in vertical direction

lineto X Y
straight line segment between the current point and absolute location (X,Y)

rlineto DX DY
straight line segment specified by displacement (DX,DY) with respect to the current point

curveto X1 Y1 X2 Y2 X3 Y3
Bezier cubic section between the current point and (X3,Y3), using (X1,Y1) and (X2,Y2) as control points

rcurveto DX1 DY1 DX2 DY2 DX3 DY3
Bezier cubic section, with the points specified as displacements with respect to the current point

arc X Y R A1 A2
arc of a circle with radius R centered at location (X,Y) starting and ending at angles A1 and A2 (0<=A1,A2<=360), respectively; if there is a current point, it is connected by a straight line segment to the first point on the arc

narc X Y R A1 A2
negative arc; the arc is drawn in clockwise rather than in counter-clockwise direction

arct X1 Y1 X2 Y2 R
arc specified by tangent lines; the center of the arc is located within the inner angle of the tangents, with the first tangent connecting the current point and (X1,Y1), and the second tangent connecting (X1,Y1) and (X2,Y2)

charpath S T
path consisting of the character outlines that would result if the string S where shown at the current point using show; T is a truth value denoting whether the path should be used for stroking to draw the character outlines (T = false) or whether the path should be adjusted for use with fill or clip (T = true)

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

11.13.4 Painting

The following operations are provided for stroking and filling, and for displaying text:

draw the line segments in the current path
fill, eofill
fill the interior of the current path (any unclosed subpaths of the current path are closed automatically)
show S
paint string S at the current point

The fill function uses the "nonzero winding number" rule for determining which points lie "inside" the current path, while eofill uses the "even-odd" rule. Please refer to [Adobe 1990] for the details.

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

11.13.5 Clipping

The following operations are used to determine the current clipping path, as described in 11.13.2 Overview of Graphics Operations:

clip, eoclip
intersect the current clipping area with the interior of the current path

The clip and eoclip operations use the same rules for insideness testing as fill and eofill, respectively, see 11.13.4 Painting.

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

11.13.6 Graphics State

As already indicated in 11.13.2 Overview of Graphics Operations, the PostScript graphics state is a collection of parameters which control the behavior of the graphics operations. The graphics.q script provides the following operations to manipulate these parameters:

save the current graphics state

restore the previously saved graphics state

push the current transformation matrix (CTM) on the PostScript stack; the CTM is manipulated by the translate, scale and rotate operations, see below

restore the CTM from the stack

translate TX TY
move the origin of the coordinate system TX units in horizontal and TY units in vertical direction

scale SX SY
scale the unit lengths of the coordinate axes by SX in horizontal and SY in vertical direction

rotate A
rotate the coordinate system by an angle of 0<=A<=360 degrees

setlinewidth X
set the line width to X units

setlinecap N
set the line cap style (0 = butt caps, 1 = round caps, 2 = projecting square caps)

setlinejoin N
set the line join style (0 = miter joins, 1 = round joins, 2 = bevel joins)

setdash Xs DX
set the dash pattern (see below)

setgray X
set the gray shade (0 = black, 1 = white)

setrgbcolor R G B
set the color in the RGB model (R = red, G = green, B = blue)

sethsbcolor H S B
set the color in the HSB model (H = hue, S = saturation, B = brightness)

setcmykcolor C M Y K
set the color in the CMYK model (C = cyan, M = magenta, Y = yellow, K = black)

setcolor C
set the color specified by symbolic color value C (see below)

setfont S X
select font S scaled by X units (see below)

The setrgbcolor, sethsbcolor and setcmykcolor functions enable you to select arbitrary colors in the RGB, HSB and CMYK model, respectively. A more user-friendly, but less flexible, routine setcolor is provided which allows colors to be selected from a fixed set of symbolic constants implemented by the Color type. Please refer to graphics.q for a list of the possible color values.

The setdash function sets the dash pattern for straight and curved line segments. The first argument of setdash is a list of length values which alternately specify the lengths of the "on" and "off" segments of the line (i.e., dashes and gaps between the dashes). This list is cycled through by the stroke function. For instance, setdash [2,1] 0 specifies the dash pattern "2 on, 1 off, 2 on, 1 off, ...". If the list is empty (setdash [] 0) stroke produces solid lines. The second argument of setdash denotes the "phase" of the dash pattern, which is given by an offset into the pattern. E.g., setdash [2,3] 11 denotes the pattern "1 on, 3 off, 2 on, 3 off, 2 on, ...".

The setfont function takes as its first argument a string denoting a PostScript font name such as "Times-Roman" or "Helvetica-Oblique". The second argument denotes the size in units to which the font should be scaled. For instance: setfont "Helvetica" 10. (This function is implemented by a combination of the PostScript operators findfont, scalefont and setfont.)

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

11.13.7 Miscellaneous Operations

emit the current page
like showpage, but do not erase the contents of the current page
update the display (flush any buffered graphics)
erase the contents of the current page
copies N
number of copies to be emitted with showpage
psfile NAME
copy a PostScript file to the graphics device
psstr S
convert a string to PostScript syntax
output a minimal PostScript header
ps CMD
output a PostScript command

The showpage, copypage, flushpage and erasepage functions have already been discussed in 11.13.2 Overview of Graphics Operations. The copies operation determines the number of copies which should be printed when showpage is invoked:

==> copies 4 || showpage

To submit a PostScript file to the graphics device the psfile operation may be used. It takes one string argument, the name of the file. For instance:

==> psfile "foo.ps"

The ps function is used to directly invoke a PostScript command. Examples can be found in 11.13.2 Overview of Graphics Operations. The psstr function converts a string to PostScript format. It takes care of embedded backslashes and parentheses. For instance:

==> writes (psstr "(silly\\) example") || writec "\n"
(\(silly\\\) example)

The psheader function is used to begin the output file with a minimal header identifying the file as PostScript; see 11.13.8 DSC and EPSF Comments.

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

11.13.8 DSC and EPSF Comments

Appendix G and H of [Adobe 1990] define a standard set of comments which should be included in PostScript documents to make explicit the document structure, and to allow inclusion of PostScript files in other documents. These standards are known as the document structuring conventions (DSC) and the encapsulated PostScript file (EPSF) format. See [Adobe 1990] for a detailed discussion of the purpose of these formats.

The graphics.q script currently does not provide any specialized operations for sending DSC and EPSF comments to the graphics device, with the exception of the psheader function which outputs a minimum header to make your printer recognize a graphics file as PostScript. Invoke this function as follows, before calling any other graphics operation:

==> psheader

You can also call the psheader function at initialization time from within a script, using a line like the following:

def INIT = psheader;

To include other types of DSC and EPSF comments in the graphics output, you have to specify these comments explicitly using the ps function. For instance, a function writing out the necessary DSC header comments of an EPS file may be implemented as follows:

/* (X1,Y1) and (X2,Y2) denote the lower left and the upper right corner
   of the bounding box, respectively */
epsf_header X1:Num Y1:Num X2:Num Y2:Num
                        = ps "%!PS-Adobe-3.0 EPSF-3.0\n" ||
                          ps ("%%BoundingBox: "++join " "
                              [str X1, str Y1, str X2, str Y2]++"\n");

As indicated, each comment must be terminated by a newline character. Use the epsf_header function in place of the psheader function if you are composing an EPS file which is to be used in other documents. E.g., when invoked as epsf_header 5 5 105 105, the following header information will be written to the graphics device:

%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 5 5 105 105

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

11.14 Diagnostics and Error Messages

The assert.q script supplies the special form assert for printing diagnostic messages:

foo X                   = assert (X>0) || bar (1/X);

The assert function verifies that the given expression evaluates to true, in which case it returns (). Otherwise it uses the error function to abort evaluation after printing an error message of the following form:

! Error: assertion (X) failed, value (value of X)

Error messages are printed using the error operation of the error.q script which prints an error message and then simply stops evaluation using halt. For instance:

X/0                     = error "Division by zero!";

This will print an error message

! Error: Division by zero!

when executed, and halt evaluation.

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

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