[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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:
assert.q
clib.q
comp.q
complex.q
cond.q
error.q
graphics.q
lambda.q
list.q
math.q
prelude.q
sort.q
stddecl.q
stdtypes.q
)
stdlib.q
stdtypes.q
stream.q
string.q
typec.q
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
).
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The stdlib.q
script provides frequently used list operations and
other stuff mostly adopted from [Bird/Wadler 1988].
abs X
all P Xs
Xs
satisfies the predicate
P
any P Xs
Xs
contains an element satisfying predicate
P
append Xs Y
Y
to the list or tuple Xs
apply X Y
X
to argument Y
cat Xs
compose X Y
compose X Y Z => X (Y Z)
cons X Xs
cst X
cst X Y => X
do F Xs
F
to each member of a list Xs
, return
()
drop N Xs
N
elements from the list Xs
dropwhile P Xs
Xs
while the predicate P
is satisfied
eq X Y
filter P Xs
foldl F A Xs
foldl1 F Xs
foldr F A Xs
foldr1 F Xs
fst Xs
hd Xs
hds Xs
id
id X => X
init Xs
Xs
without its last element
iter N F A
N
values A
, F A
,
F (F A)
, ...
last Xs
map F Xs
F
to each member of a list
max X Y
min X Y
mklist X N
N
X
's
neg P
neq X Y
null Xs
[]
resp. ()
)
nums N M
numsby K N M
pair X Y
pop Xs
prd Xs
push Xs X
cons
with arguments reversed)
reverse Xs
scan F A Xs
foldl
to every initial part of a list
scan1 F Xs
foldl1
to every nonempty initial part of a list
sgn X
snd Xs
sum Xs
take N Xs
N
elements from the list Xs
takewhile P Xs
Xs
while the predicate P
is satisfied
tl Xs
tls Xs
top Xs
transpose Xs
trd Xs
triple X Y Z
tuplecat Xs
until P F X
F
to X
until P
is satisfied
unzip Xs
unzip3 Xs
unzip
with triples
while P F A
F
to A
while P
is
satisfied
zip Xs Ys
zip3 Xs Ys Zs
zip
with three lists
zipwith F Xs Ys
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] | [ ? ] |
The string.q
script provides a collection of additional string
functions. Currently the following operations are implemented:
chars S
S
join DELIM Xs
DELIM
string
between each pair of consecutive strings in the list
split DELIM S
DELIM
string
strcat Xs
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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] | [ ? ] |
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
ischar X
isexcept X
Exception
values (cf. 10.6 Exception Handling)
isfile X
isfloat X
isint X
islist X
isnum X
isstr X
issym X
istuple X
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The sort.q
script provides mergesort and quicksort algorithms for
sorting a list using a given order predicate:
msort P Xs
qsort P Xs
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] [1,2,3,4,5] |
By reversing the order predicate, the list is sorted in descending order:
==> qsort (>) [1,5,3,2,4] [5,4,3,2,1] |
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 [(1,2),(1,1),(3,3),(4,5),(5,1)] |
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 [(5,1),(1,1),(1,2),(3,3),(4,5)] ==> qsort le1 _ [(1,1),(1,2),(3,3),(4,5),(5,1)] |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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] | [ ? ] |
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
Xs
array2 Xs
emptyarray
mkarray X N
N
X
's
mkarray2 X (N,M)
N
rows and M
columns
isarray X
X
is an array
null A
A
is the empty array
A1 = A2, A1 <> A2
#A
A!I
I
th member of an array
A!(I,J)
members A, list A
A
members2 A, list2 A
first A, last A
rmfirst A, rmlast A
insert A X
X
at the beginning of A
append A X
X
at the end of A
update A I X
I
th member of A
by X
update2 A (I,J) X
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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:
emptyheap
heap Xs
isheap X
X
is a heap
null H
H
is the empty heap
H1 = H2, H1 <> H2
#H
members H, list H
H
in ascending order
first H
H
rmfirst H
H
insert H X
X
into H
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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
:
emptyset
set Xs
isset X
X
is a set
null M
M
is the empty set
member M X
M
contains element X
M1 = M2, M1 <> M2
M1 < M2, M1 > M2, M1 <= M2, M1 >= M2
M1 + M2, M1 - M2, M1 * M2
#M
members M, list M
M
in ascending order
first M, last M
M
rmfirst M, rmlast M
M
insert M X
X
into M
delete M X
X
from M
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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] | [ ? ] |
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
:
emptydict
dict XYs
mkdict Y Xs
isdict X
null D
D
is the empty dictionary
member D X
D
contains X
as a key
D1 = D2, D1 <> D2
#D
D!X
Y
associated with X
in D
members D, list D
D
in ascending order by key
keys D
D
in ascending order
vals D
first D, last D
D
rmfirst D, rmlast D
D
insert D (X,Y)
(X,Y)
into D
; update an existing entry
for X
if present
delete D X
X
from D
update D X Y
insert D (X,Y)
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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
HDict
s is more involved than for Dict
s, as the member
lists of two "equal" HDict
s 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] | [ ? ] |
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) 7 ==> def bar = lambda X (lambda Y (2*X+Y)); bar 2 3 7 |
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 9 |
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) 202 |
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) '(6+1) |
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) '(2*3+1) |
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.
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
_A X, _L X, _T X
_I, _K K
_S X Y, _B X Y, _C X Y
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 |
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] | [ ? ] |
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:
listof EXPR CLAUSES |
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] | [ ? ] |
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
stream Xs
list Xs
numstream N
>=N
numstreamby K N
mkstream X
X
's
iterate F A
A
, F A
, F (F A)
,
...
streamcat Xs
streamof X CLAUSES
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 N
th 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] | [ ? ] |
The cond.q
script provides some functions for implementing
conditional expressions:
ifelse ~P X Y
matchp P ~X
switch CASES
match X CASES
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 33452526613163807108170062053440751665152000000000 ==> f (-1) 1 0 bar 1 ==> g (bar 9 10) 0.9 |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The math.q
script contains some additional operations on floating
point numbers:
asin X, acos X, tan X
lg X, log X
sinh X, cosh X, tanh X
asinh X, acosh X, atanh X
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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
abs Z, arg Z
re Z, im Z
conj Z
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] | [ ? ] |
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:
gsdev
ghostscript
program (see below)
gvdev
ghostview
(see below)
lpdev
lpr
(1))
filedev X
X
nulldev
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].
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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] | [ ? ] |
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 || closepath |
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] | [ ? ] |
The graphics.q
script defines the following collection of operations
to define the current path used by the painting and clipping operations:
newpath
closepath
clippath
moveto X Y
(X,Y)
rmoveto DX DY
DX
units in horizontal and DY
units in
vertical direction
lineto X Y
(X,Y)
rlineto DX DY
(DX,DY)
with
respect to the current point
curveto X1 Y1 X2 Y2 X3 Y3
(X3,Y3)
, using
(X1,Y1)
and (X2,Y2)
as control points
rcurveto DX1 DY1 DX2 DY2 DX3 DY3
arc X Y R A1 A2
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
arct X1 Y1 X2 Y2 R
(X1,Y1)
, and the second tangent connecting (X1,Y1)
and (X2,Y2)
charpath S T
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] | [ ? ] |
The following operations are provided for stroking and filling, and for displaying text:
stroke
fill, eofill
show S
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] | [ ? ] |
The following operations are used to determine the current clipping path, as described in 11.13.2 Overview of Graphics Operations:
clip, eoclip
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] | [ ? ] |
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:
gsave
grestore
savematrix
translate
, scale
and rotate
operations, see below
restorematrix
translate TX TY
TX
units in horizontal and
TY
units in vertical direction
scale SX SY
SX
in horizontal
and SY
in vertical direction
rotate A
0<=A<=360
degrees
setlinewidth X
X
units
setlinecap N
0
= butt caps, 1
= round caps,
2
= projecting square caps)
setlinejoin N
0
= miter joins, 1
= round joins,
2
= bevel joins)
setdash Xs DX
setgray X
0
= black, 1
= white)
setrgbcolor R G B
R
= red, G
= green, B
=
blue)
sethsbcolor H S B
H
= hue, S
= saturation,
B
= brightness)
setcmykcolor C M Y K
C
= cyan, M
= magenta,
Y
= yellow, K
= black)
setcolor C
C
(see below)
setfont S X
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] | [ ? ] |
showpage
copypage
showpage
, but do not erase the contents of the current page
flushpage
erasepage
copies N
showpage
psfile NAME
psstr S
psheader
ps CMD
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] | [ ? ] |
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] | [ ? ] |
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] | [ ? ] |