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

A new programming language is best conveyed through some examples, and therefore it is common practice to start a language description with an introductory chapter which treats the most essential language features in a fairly informal manner. This is also the purpose of the present chapter. We first show how some of the "standard features" of the Q programming language can be employed for using the Q interpreter effectively as a sophisticated kind of "desktop calculator". The remainder of this section then adresses the question of how you can extend the Q environment by providing your own definitions in Q scripts, and describes the evaluation process and the treatment of runtime errors in the interpreter.

2.1 Using the Interpreter | ||

2.2 Using the Standard Library | ||

2.3 Writing a Script | ||

2.4 Definitions | ||

2.5 Runtime Errors |

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

To begin with, let us show how the Q interpreter is invoked to evaluate
some expressions with the built-in functions provided by the Q
language. Having installed the Q programming system, you can simply
invoke the interpreter from your shell by typing `q`

. The
interpreter will then start up, display its sign-on, and leaves you at
its prompt:

==> |

This indicates that the interpreter is waiting for you to type an expression. Let's start with a simple one:

==> 23 23 |

Sure enough, that's correct. Whenever you type an expression, the interpreter just prints its value. Any integer is a legal value in the Q language, and the common arithmetic operations work on these values as expected. Q integers are "bignums", i.e., their size is only limited by available memory:

==> 16753418726345 * 991726534256718265234 16614809890429729930396098173389730 |

"Real" numbers (more exactly, their approximation using 64 bit double precision floating point numbers) are provided as well. Let's try these:

==> sqrt (16.3805*5)/.05 181.0 |

The `sqrt`

identifier denotes a built-in function which computes
the square root of its argument. (A summary of the built-in functions
can be found in Built-In Functions.)

What happens if you mistype an expression?

==> sqrt (16.3805*5)/,05 ! Syntax error >>> sqrt (16.3805*5)/,05 ^ |

As you can see, the interpreter not only lets you know that you typed
something wrong, but also indicates the position of the error. It is
quite easy to go back now and correct the error, using the interpreter's
"command history". With the up and down arrow keys you can cycle
through the expressions you have typed before, edit them, and resubmit a
line by hitting the carriage return key. Also note that what you typed
is stored in a "history file" when you exit the interpreter, which is
reloaded next time the interpreter is invoked. A number of other useful
keyboard commands are provided, see Readline: (readline)Command Line Editing section `Command Line Editing' in The GNU Readline Library. In
particular, you can have the command line editor "complete" function
symbols with the `<TAB>`

key. E.g., if you type in `sq`

and
press the `<TAB>`

key, you will get the `sqrt`

function.

Before we proceed, a few remarks about the syntax of function applications are in order. The first thing you should note is that in Q, like in most other modern functional languages, function application is simply denoted by juxtaposition:

==> sqrt 2 1.4142135623731 |

Multiple arguments are specified in the same fashion:

==> max 5 7 7 |

Parentheses can be used for grouping expressions as usual. In particular, if a function application appears as an argument in another function application then it must be parenthesized as follows:

==> sqrt (sqrt 2) 1.18920711500272 |

Another important point is that operators are in fact just functions in
disguise. You can turn any operator into a prefix function by enclosing
it in parentheses. Thus `(+)`

denotes the function which adds its
two arguments, and `X+1`

can also be written as `(+) X 1`

; in
fact, the former expression is nothing but "syntactic sugar" for the
latter, see Built-In Operators. You can easily verify this in the
interpreter:

==> (+) X 1 X+1 |

You can also have partial function applications like `(*) 2`

which
denotes a function which doubles its argument. Moreover, Q supports
so-called *operator sections* which allow you to specify a binary
operator with only either its left or right operand. For instance,
`(1/)`

denotes the reciprocal and `(+1)`

the "increment by
1" function:

==> (+1) 5 6 ==> (1/) 3 0.333333333333333 |

The interpreter maintains a global variable environment, in which you
can store arbitrary expression values. This provides a convenient means
to define abbreviations for frequently-used expressions and for storing
intermediate results. Variable definitions are done using the `def`

command. For instance:

==> def X = 16.3805*5 ==> X 81.9025 |

As indicated, variable symbols usually start with a capital letter; an
initial lowercase letter indicates a function symbol. This convention is
valid throughout the Q language. However, it is possible to explicitly
declare an uncapitalized symbol as a variable, using the `var`

command, and then assign values to it, like so:

==> var f ==> def f = sqrt |

You can also both declare a variable and initialize its value with a
single `var`

command:

==> var f = sqrt ==> f X/.05 181.0 |

Multiple variable declarations and definitions can be entered on a
single line, using commas to separate different definitions in a
`def`

or `var`

command, and you can separate multiple
expressions and commands on the same line with semicolons:

==> def X = 16.3805*5, f = sqrt; X; f X/.05 81.9025 181.0 |

You can also bind several variables at once by using an expression
*pattern* as the left-hand side of a variable definition:

==> def (f, X) = (sqrt, 16.3805*5); f X/.05 181.0 |

(Such pattern-matching definitions only work with `def`

; the
left-hand side of a `var`

declaration must always be a simple
identifier.)

Another useful feature is the built-in "anonymous" variable ``_'`,
which is always set to the value of the most recent expression value
printed by the interpreter:

==> _ 181.0 ==> 2*_ 362.0 |

Sometimes you would also like the interpreter to "forget" about a
definition. This can be done by means of an `undef`

statement:

==> undef X; X X |

Besides `def`

, `undef`

and `var`

, the interpreter
provides a number of other special commands. The most important command
for beginners certainly is the `help`

command, which displays the
online manual using the GNU info reader. You can also run this command
with a keyword to be searched in the info file. For instance, to find
out about all special commands provided by the interpreter, type the
following:

==> help commands |

(Type `q`

when you are done reading the info file.)

Other useful commands are `who`

which prints a list of the
user-defined variables, and `whos`

which describes the attributes
of a symbol:

==> who f ==> whos f sqrt f user-defined variable symbol = sqrt sqrt builtin function symbol sqrt X1 |

You can save user-defined variables and reload them using the
`save`

and `load`

commands:

==> save saving .q_vars ==> def f = 0; f 0 ==> load loading .q_vars ==> f sqrt |

Some statistics about the most recent expression evaluation can be
printed with the `stats`

command:

==> sum [1..123456] 7620753696 ==> stats 0.52 secs, 246916 reductions, 246918 cells |

The `stats`

command displays the (cpu) time needed to complete an
evaluation, the number of "reductions" (a.k.a. basic evaluation steps)
performed by the interpreter, and the number of expression "cells"
needed during the course of the computation. This information is often
useful for profiling purposes.

Other commands allow you to edit and run a script directly from the interpreter, and to inspect and set various internal parameters of the interpreter; see Command Language.

Of course, the Q interpreter can also carry out computations on
non-numeric data. In fact, Q provides a fairly rich collection of
built-in data types, and makes it easy to define your own. For instance,
*strings* are denoted by character sequences enclosed in double
quotes. Strings can be concatenated with the ``++'` operator and the
length of a string can be determined with ``#'`. Moreover, the
character at a given position can be retrieved with the (zero-based)
indexing operator ``!'`:

==> "abc"++"xyz"; #"abc"; "abc"!1 "abcxyz" 3 "b" |

The same operations also apply to *lists*, which are written as
sequences of values enclosed in brackets:

==> [a,b,c]++[x,y,z]; #[a,b,c]; [a,b,c]!1 [a,b,c,x,y,z] 3 b |

As in Prolog, lists are actually represented as right-recursive
constructs of the form ``[X|Xs]'` where `X`

denotes the head
element of the list and `Xs`

its tail, i.e., the list of the
remaining elements. This representation allows a list to be traversed
and manipulated in an efficient manner.

==> def [X|Xs] = [a,b,c]; X; Xs a [b,c] ==> [0|Xs] [0,b,c] |

Another useful list operation is "enumeration", which works with all
so-called "enumeration types" (cf. Enumeration Types), as well
as characters and numbers. Enumerations are constructed with the
`enum`

function, or using the familiar `[X..Y]`

notation which
is in fact only "syntactic sugar" for `enum`

:

==> enum "a" "k" ["a","b","c","d","e","f","g","h","i","j","k"] ==> ["a".."k"] ["a","b","c","d","e","f","g","h","i","j","k"] ==> [0..9] [0,1,2,3,4,5,6,7,8,9] ==> [0.1,0.2..1.0] [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0] |

*Tuples* are sequences of expressions enclosed in parentheses, which
are Q's equivalent of "vectors" or "arrays" in other languages. Like
lists, tuples can be concatenated, indexed and enumerated, but they use
an internal representation optimized for efficient storage and
constant-time indexing:

==> (a,b,c)++(x,y,z); #(a,b,c); (a,b,c)!1 (a,b,c,x,y,z) 3 b ==> (0..9) (0,1,2,3,4,5,6,7,8,9) |

Q also offers built-in operations to convert between lists and tuples:

==> tuple [a,b,c] (a,b,c) ==> list _ [a,b,c] |

Q provides yet another list-like data structure, namely "lazy" lists
a.k.a. *streams*, which are written using curly braces instead of
brackets. In difference to lists, streams only produce their elements
"on demand", when they are needed in the course of a computation. This
makes it possible to represent large and even infinite sequences of
values in an efficient manner. You can see this somewhat unusual
behaviour if you try streams interactively in the interpreter. For
instance, let's try to concatenate two streams:

==> {a,b,c}++{x,y,z} {a|{b,c}++{x,y,z}} |

You probably noticed that the tail of the resulting stream,
`{b,c}++{x,y,z}`

, has not been evaluated yet. But that is all
right, because it *will* be evaluated as soon as we need it:

==> _!4 y |

This lazy way of doing things becomes especially important when we work with infinite streams. We will have more to say about this in the following section.

It is quite instructive to keep on playing a bit like this, to get a feeling
of what the Q interpreter can do. You might also wish to consult
Built-In Functions, which discusses the built-in functions, and
Using Q, which shows how the interpreter is invoked and what additional
capabilities it offers. To exit the interpreter when you are finished,
invoke the built-in `quit`

function:

==> quit |

This function does not return a value, but immediately returns you to the operating system's command shell.

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

The standard library is a collection of useful functions and data
structures which are *not* provided as built-ins, but are
implemented by scripts which are mostly written in Q itself. Most of
these scripts are included in the "prelude script" `prelude.q`

,
which is always loaded by the interpreter, so that the standard library
functions are always available. See The Standard Library, for an
overview of these operations. You can check which standard library
scripts a.k.a. "modules" are actually loaded with the interpreter's
`modules`

command. With the standard prelude loaded, this command
shows the following:

==> modules assert clib* complex cond error math prelude rational sort stdlib stream string tuple typec |

As you can see, there are quite a few modules already loaded, and you can use the functions provided by these modules just like any of the built-in operations. The standard library provides a lot of additional functions operating on numbers, strings and lists. For instance, you can take the sum of a list of (integer or floating point) numbers simply as follows:

==> sum [1..5] 15 |

In fact, the library provides a rather general operation, `foldl`

,
which iterates a binary function over a list, starting from a given initial
value. Using the `foldl`

function, the above example can also be
written as follows:

==> foldl (+) 0 [1..5] 15 |

(There also is a `foldr`

function which works analogously, but
combines list members from right to left rather than from left to
right.)

Generalizing the notion of simple enumerations of numbers like
`[1..5]`

, the standard library also provides the general-purpose
list-generating function `while`

. For instance, we can generate the
list of all powers of 2 in the range `[1..1000]`

as follows:

==> while (<=1000) (2*) 1 [1,2,4,8,16,32,64,128,256,512] |

(Recall from the previous section that `(2*)`

is the doubling
function. And `(<=1000)`

is a predicate which checks its argument
to be less than or equal to `1000`

.)

If we want to generate a list of a given size, we can use `iter`

instead. So, for instance, we might compute the value of a finite
geometric series as follows:

==> sum (iter 4 (/3) 1) 1.48148148148148 |

The `map`

function allows you to apply a function to every member of a
list. For instance, the following expression doubles each value in the list
`[1..5]`

:

==> map (2*) [1..5] [2,4,6,8,10] |

Lists can also be filtered with a given predicate:

==> filter (>=3) [1..5] [3,4,5] |

The `scanl`

operation allows you to compute all the sums of initial
segments of a list (or accumulate any other binary operation over a
list):

==> scanl (+) 0 [1..5] [0,1,3,6,10,15] |

(Like `foldl`

, `scanl`

also has a sibling called `scanr`

which collects results from right to left rather than left to right,
starting at the end of the list.)

You can partition a list into an initial part with a given length and
the remaining part of the list with `take`

and `drop`

:

==> take 3 [1..5]; drop 3 [1..5] [1,2,3] [4,5] |

The `takewhile`

and `dropwhile`

functions have a similar
effect, but partition their input list according to a given predicate:

==> takewhile (<=3) [1..5]; dropwhile (<=3) [1..5] [1,2,3] [4,5] |

Another useful list operation is `zip`

which collects pairs of
corresponding elements in two input lists:

==> zip [1..5] ["a".."e"] [(1,"a"),(2,"b"),(3,"c"),(4,"d"),(5,"e")] |

The effect of `zip`

can be undone with `unzip`

which returns a
pair of lists:

==> unzip _ ([1,2,3,4,5],["a","b","c","d","e"]) |

The `zipwith`

function is a generalized version of `zip`

which
combines corresponding members from two lists using a given binary
function:

==> zipwith (*) [1..5] [1..5] [1,4,9,16,25] |

All the operations described above - and many others - are provided by
the `stdlib.q`

script. It is instructive to take a look at this
script and see how the operations are defined.

In addition, the standard library provides yet another list generating
function `listof`

which implements so-called "list
comprehensions". These allow you to describe list values in much the
same way as sets are commonly specified in mathematics. For instance,
you can generate a list of pairs `(I,J)`

with `1<=J<I<=5`

as
follows:

==> listof (I,J) (I in [1..5], J in [1..I-1]) [(2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(5,1),(5,2),(5,3),(5,4)] |

The language provides syntactic sugar for list comprehensions so that the above example can also be written as follows:

==> [(I,J) : I in [1..5], J in [1..I-1]] [(2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(5,1),(5,2),(5,3),(5,4)] |

The same kind of construct also works with tuples:

==> ((I,J) : I in [1..5], J in [1..I-1]) ((2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(5,1),(5,2),(5,3),(5,4)) |

We also have a random number generator, which is implemented by the
built-in `random`

function. Here is how we can generate a list of 5
pseudo random 32 bit integers:

==> [random : I in [1..5]] [1960913167,1769592841,3443410988,2545648850,536988551] |

To get random floating point values in the range [0,1] instead, we
simply divide the results of `random`

by `0xffffffff`

:

==> map (/0xffffffff) _ [0.456560674928259,0.41201544027124,0.801731596887515,0.592705060400233, 0.125027389993199] |

Lists can be sorted using quicksort (this one comes from `sort.q`

):

==> qsort (<) _ [0.125027389993199,0.41201544027124,0.456560674928259,0.592705060400233, 0.801731596887515] |

As already mentioned, the Q language also provides a "lazy" list data
structure called "streams". Streams are like lists but can actually be
infinite because their elements are only produced "on demand". The
standard library includes a module `stream.q`

which implements a
lot of useful stream operations. Most list operations carry over to
streams accordingly. For instance, if we want to create a geometric
series like the one generated with `iter`

above, but we do not know
how many elements will be needed in advance, we can employ the stream
generation function `iterate`

:

==> iterate (/3) 1 {1|iterate (/3) ((/3) 1)} |

The `{|}`

stream constructor works in the same way as the
`[|]`

list constructor, but is "special" in that it does
*not* evaluate its arguments, i.e., the head and the tail of the
stream. (Otherwise the call to `iterate`

would never terminate.)

To get all members of the series we can apply the `scanl`

function:

==> def S = scanl (+) 0 _; S {0|scanl (+) (0+1) (iterate (/3) ((/3) 1))} |

Now we can extract any number of initial values of the series using the
`take`

operation, and convert the resulting stream to an ordinary
list with the `list`

function. For instance, if we are interested
in the first five values of the series, we proceed as follows:

==> list (take 5 S) [0,1,1.33333333333333,1.44444444444444,1.48148148148148] |

Note that the stream `S`

is really infinite; if we want, we can
extract *any* value in the series:

==> S!9999 1.5 |

Let's see how many iterations are actually required to reach the limit
`1.5`

with an error of at most `1e-15`

:

==> #takewhile (>1e-15) (map (1.5-) S) 32 |

This means that the sum of the first 31 series terms is needed to get an
accuracy of 15 digits (which is the best that we can hope for with 64
bit floating point values). We can readily verify this using
`iter`

:

==> sum (iter 31 (/3) 1) 1.5 |

The standard library also implements stream enumerations and
comprehensions which work like the corresponding list and tuple
constructs but are evaluated in a lazy fashion, and the interpreter
provides syntactic sugar for these. In particular, the notation
`{X..}`

or `{X,Y..}`

can be used to specify an infinite
arithmetic sequence. For instance, here is another way to define the
infinite geometric series from above:

==> def S = scanl (+) 0 {1/3^N : N in {0..}} ==> list (take 5 S) [0,1.0,1.33333333333333,1.44444444444444,1.48148148148148] |

It is worth noting here that streams are just one simple example of a
lazy data structure, which happen to play an important role in many
useful algorithms so that it makes sense to provide them as a
builtin. The Q language makes it rather easy to define your own lazy
data structures using so-called *special forms*. In fact, special
forms provide a uniform means to define both lazy data constructors and
macro-like functions which take their arguments unevaluated, employing
"call by name" parameter passing. This will be discussed in detail in
Special Forms.

Special forms are an integrated part of Q which adds a great amount of
expressive power to the language. In particular, they allow specialized
constructs such as a "short-circuit" conditional expressions to be
defined in the standard library, just like "ordinary" functions,
rather than having to provide them as builtins. One example is the
conditional expression `if X then Y else Z`

which is nothing but
syntactic sugar for the standard library function `ifelse`

:

==> ifelse (5>0) "positive" "negative" "positive" ==> if 5>0 then "positive" else "negative" "positive" |

Another special form which is useful in many situations is `lambda`

(as of Q 7.1, this one is actually provided as a builtin), which allows
you to create little "anonymous" functions on the fly. The customary
notation `\X.Y`

is provided as a shorthand for ```
lambda X
Y
```

. These constructs are also called *lambda abstractions*, or
simply *lambdas*. For instance, the following interpreter command
defines the well-known factorial function using a lambda abstraction and
assigns the resulting function object to the variable `fac`

:

==> var fac = \N.if N>0 then N*fac (N-1) else 1 ==> fac \X1 . if X1>0 then X1*fac (X1-1) else 1 ==> map fac [1..10] [1,2,6,24,120,720,5040,40320,362880,3628800] |

Lambdas taking multiple arguments can be created like this:

==> \X Y.(1-X)*Y \X1 . \X2 . (1-X1)*X2 ==> _ 0.9 0.5 0.05 |

The lambda arguments can also be patterns to be matched against the actual parameters. For instance:

==> \(X,Y).(1-X)*Y \(X1,X2) . (1-X1)*X2 ==> _ (0.9,0.5) 0.05 |

Besides string and list processing functions and general utility
functions of the kind sketched out above, the standard library also
includes a collection of efficient "container" data structures which
are useful in many applications. For instance, so-called *hashed
dictionaries* (also known as "hashes" or "associative arrays") are
implemented by the `hdict.q`

script. The following expressions show
how to create a dictionary object from a list, and how to access this
dictionary using the index (`!`

), `keys`

and `vals`

operations. (Note that here we have to load the `hdict.q`

module
explicitly, as it is not automatically included via the prelude. We
could also import the `stdtypes.q`

module instead, to get hold of
all the container types.)

==> import hdict ==> def D = hdict [(foo,99),(bar,-1),(gnu,foo)]; D!gnu foo ==> keys D [foo,bar,gnu] ==> vals D [99,-1,foo] |

This completes our little tour through the standard library. To find out more, please refer to The Standard Library, or take a look at the scripts themselves.

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

Now that we have taken the first big hurdle and are confident that we can actually get the Q interpreter to evaluate us some expressions, let us try to define a new function for use in the interpreter. That is, we are going to write our first own Q "program" or "script".

In the Q language, there are actually two different ways to create new functions. As we have already seen in the previous sections, little "anonymous" functions are often computed on the fly by deriving them from existing functions using partial applications or lambda abstractions. The other way, which is often more convenient when the functions to be defined get more complicated, is the definition of named functions by the means of "equations", which works in a way similar to algebraic definitions in mathematics. We will discuss how to do this in the following.

Having exited the Q interpreter, invoke your favourite text editor and enter the following simple script which implements the factorial function:

fac N = N*fac(N-1) if N>0; = 1 otherwise; |

(Note that in order to define functions equationally, you really have to write a script file. For technical reasons there currently is no way to enter an equational definition directly in the interpreter.)

Save the script in the file `fac.q`

and then restart the
interpreter as follows (here and in the following ``$'` denotes the
command shell prompt):

$ q fac.q |

You can also edit the script from within the interpreter (using `vi`

or
the editor named by the `EDITOR`

environment variable) and then restart
the interpreter with the new script, as follows:

==> edit fac.q ==> run fac.q |

In any case, now the interpreter should know about the definition of
`fac`

and we can use it like any of the built-in operations:

==> map fac [1..10] [1,2,6,24,120,720,5040,40320,362880,3628800] |

For instance, what is the number of 30-element subsets of a 100-element set?

==> fac 100 div (fac 30*fac 70) 29372339821610944823963760 |

As another example, let us write down Newton's algorithm for computing
roots of a function. Type in the following script and save it to the
file `newton.q`

:

newton DX DY F = until (satis DY F) (improve DX F); satis DY F X = abs (F X) < DY; improve DX F X = X - F X / derive DX F X; derive DX F X = (F (X+DX) - F X) / DX; |

Restart the interpreter with the `newton.q`

script and try the
following. Note that the target function here is `\Y.Y^3-X`

which
becomes zero when `Y`

equals the cube root of `X`

.

==> var eps = .0001, cubrt = \X.newton eps eps (\Y.Y^3-X) X ==> cubrt 8 2.00000000344216 |

Well, this is not *that* precise, but we can do better:

==> def eps = 1e-12 ==> cubrt 8 2.0 |

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

As mentioned in the previous section, in the Q language function definitions take the form of equations which specify how a given expression pattern, the left-hand side of the equation, is transformed into a new expression, the right-hand side of the equation. In this section we elaborate on this some more to give you an idea about how these equational definitions work. Our explanations will necessarily be a bit sketchy at this point, but the concepts we briefly touch on in this section will be explained in much more detail later.

The left-hand side of an equation may introduce "variables" (denoted
by capitalized identifiers, as in Prolog) which play the role of formal
parameters in conventional programming languages. For instance, the
following equation defines a function `sqr`

which squares its
(numeric) argument:

sqr X = X*X; |

An equation may also include a condition part, as in the definition of the factorial function from the previous section:

fac N = N*fac(N-1) if N>0; = 1 otherwise; |

As indicated above, several equations for the same left-hand side can be
factored to the left, omitting repetition of the left-hand side.
Furthermore, the `otherwise`

keyword may be used to denote the
"default" alternative.

The left-hand side of an equation may actually be an arbitrary compound
expression pattern to be matched in the expression to be evaluated. For
instance, as we have already seen, the expressions `[]`

and
`[X|Xs]`

denote, respectively, the empty list and a list starting
with head element `X`

and continuing with a list `Xs`

of
remaining elements, just as in Prolog. We can use these patterns to
define a function `add`

which adds up the members of a list as
follows:

add [] = 0; add [X|Xs] = X+add Xs; |

Thus no explicit operations for "extracting" the members from a compound data object such as a list are required; the components are simply retrieved by "pattern matching". This works in variable definitions as well. For instance, in the interpreter you can bind variables to the head element and the tail of a list using a single definition as follows:

==> def [X|Xs] = [1,2,3]; X; Xs 1 [2,3] |

Pattern matching also works if the arguments take the form of function applications. For instance, the following definition implements an insertion operation on binary trees:

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

Note the symbols `nil`

and `bin`

which act as "constructors"
for the binary tree data structure in this example. (Q actually has no
rigid distinction between "function applications" and "data
constructors". This is unnecessary since function applications can be
"values" in their own right, as discussed below.)

The Q interpreter treats equations as "rewrite rules" which are used to reduce expressions to "normal forms". Evaluation normally uses the standard "leftmost-innermost" rule, also known as "applicative order" or "call by value" evaluation. Using this strategy, expressions are evaluated from left to right, innermost expressions first; thus the arguments of a function application (and also the function object itself) are evaluated before the function is applied to its arguments.

An expression is in normal form if it cannot be evaluated any further by applying matching equations (including some predefined rules which are used to implement the built-in operations, see Equations and Expression Evaluation). A normal form expression simply stands for itself, and constitutes a "value" in the Q language. The built-in objects of the Q language (such as numbers and strings) are always in normal form, but also compound objects like lists (given that their elements are in normal form) and any other symbol or function application which does not match a built-in or user-defined equation.

This means that Q is essentially an "exception-free" language. That
is, an "error condition" such as "wrong argument type" does
*not* raise an exception by default, but simply causes the offending
expression to be returned "as is". For instance:

==> hd [] hd [] ==> sin (X+1) sin (X+1) |

You may be disconcerted by the fact that expressions like `hd []`

and `sin (X+1)`

actually denote legal values in the Q
language. However, this is one of Q's key features as a term rewriting
programming language, and it adds a great amount of flexibility to the
language. Most importantly, it allows expressions, even expressions
involving variables, to be evaluated in a symbolic fashion. For
instance, you might add rules for algebraic identities and symbolic
differentiation to your script and have the interpreter simplify
expressions according to these rules. On the other hand, the Q language
also allows you to refine the definition of any built-in or user-defined
operation and thus it is a simple matter to add an "error rule" like
the following to your script when needed:

hd [] = error "hd: empty list"; |

(The `error`

function is defined in the standard library script
`error.q`

, see Diagnostics and Error Messages.) In order to
implement more elaborate error handling, you can also use Q's built-in
`throw`

and `catch`

functions to raise and respond to
exceptions on certain error conditions. This is discussed in
Exception Handling.

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

There are a few error conditions which may cause the Q interpreter to
abort the evaluation with a runtime error message. A runtime error
arises when the interpreter runs out of memory or stack space, when the
user aborts an evaluation with the interrupt key (usually `Ctl-C`

),
and when the condition part of an equation does not evaluate to a truth
value (`true`

or `false`

). (All these error conditions can
also be handled by the executing script, see Exception Handling.)

You can use the `break on`

command to tell the interpreter that it
should fire up the debugger when one of the latter two conditions
arises. After `Ctl-C`

, you can then resume evaluation in the
debugger, see Debugging. This is not possible if the interpreter
stumbles across an invalid condition part; in this case the debugger is
invoked merely to report the equation which caused the error, and to
inspect the call chain of the offending rule. Hitting the carriage
return key will return you to the interpreter's evaluation loop.

For instance, reload the `fac.q`

script from Writing a Script:

fac N = N*fac(N-1) if N>0; = 1 otherwise; |

Now enable the debugger with the `break`

command and type some
"garbage" like `fac fac`

:

==> break on; fac fac ! Error in conditional 0> fac.q, line 1: fac fac ==> fac*fac (fac-1) if fac>0 (type ? for help) : |

What happened? Well, the debugger informs us that the error occurred when the interpreter tried to apply the first equation,

fac N = N*fac(N-1) if N>0; |

to the expression `fac fac`

. In fact this is no big surprise since
we cannot expect the interpreter to know how to compare a symbol,
`fac`

, with a number, `0`

, which it tried when evaluating the
condition part of the above equation. So let us return to the
interpreter's prompt by hitting the carriage return key:

: <CR> ==> |

The interpreter now waits for us to type the next expression. (For a summary
of debugger commands please refer to Debugging. You can also
type `?`

or `help`

while in the debugger to obtain a list of
available commands.)

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

This document was generated by *Albert Gräf* on *February, 23 2008* using *texi2html 1.76*.