Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk1.iso/altsrc/articles/10648

Text File | 1994-06-19 | 62KB | 1,652 lines

Path: wupost!cs.utexas.edu!howland.reston.ans.net!xlink.net!fauern!news.th-darmstadt.de!news.uni-mainz.de!ag
From: [e-mail] (Albert Graef)
Newsgroups: alt.sources
Subject: Q - applicative programming language V1.7 - part 12/19
Followup-To: alt.sources.d
Date: 14 Jun 1994 08:51:33 GMT
Organization: Musikinformatik, JoGu-Uni Mainz
Lines: 1639
Distribution: world
Message-ID: <2tjr2l$[e-mail]>
NNTP-Posting-Host: muwiinfa.geschichte.uni-mainz.de

Archive-name: q-1.7/part12
Submitted-by: [e-mail]

#!/bin/sh
# this is q-1.7.shar.12 (part 12 of a multipart archive)
# do not concatenate these parts, unpack them in order with /bin/sh
# file q-1.7/qdoc.info continued
#
if test ! -r _shar_seq_.tmp; then
    echo 'Please unpack part 1 first!'
    exit 1
fi
(read Scheck
 if test "$Scheck" != 12; then
    echo Please unpack part "$Scheck" next!
    exit 1
 else
    exit 0
 fi
) < _shar_seq_.tmp || exit 1
if test ! -f _shar_wnt_.tmp; then
    echo 'x - still skipping q-1.7/qdoc.info'
else
echo 'x - continuing file q-1.7/qdoc.info'
sed 's/^X//' << 'SHAR_EOF' >> 'q-1.7/qdoc.info' &&
X
X   All kinds of exceptions listed above are "hard" error conditions in
Xthe sense that they cannot be repaired by application programs.
X
X   In contrast, error handling in the built-in operations is implemented
Xaccording to the general rule that an expression which cannot be
Xevaluated is in normal form and hence stands for itself. This means
Xthat "error conditions" such as argument mismatch, division by zero
X(which is actually a form of argument mismatch) or attempt to open a
Xnonexisting file with the built-in `fopen' function do *not* cause
Xruntime errors, but are handled by returning the offending expression
X"as is."
X
X
XFile: qdoc.info,  Node: Scripts,  Next: Types,  Prev: Equations and Expression Evaluation,  Up: Top
X
XScripts
X*******
X
X   In order to make a given set of definitions available for use in the
Xinterpreter, you just collect the relevant declarations, variable
Xdefinitions and equations in a source file, called a "script". The
Xscript can then be submitted to the compiler for translation into an
Xobject file which is loaded by the interpreter (see *Note Using Q::). A
Xscript may also be empty, in which case it does not provide any
Xadditional definitions at all.
X
X   If you put all definitions into a single script, that's all there is
Xto it. However, you might wish to break down a larger script into
Xseveral different source files which can be managed separately. For
Xthis purpose, the Q language allows you to include other source files
Xin a script, by means of an "include directive":
X
X     include                 : 'include' string ';'
X
X   The include directive instructs the compiler to include the given
Xsource file (specified by the filename enclosed in double quotes) at
Xthe given point. Escape sequences in the filename are treated as usual
X(see *Note Lexical Matters::). Although `include''s are usually placed
Xat the beginning of a script, they are permitted at any place where an
Xequation may begin.
X
X   Each source file included in a script can have its own set of
X"private" function and variable symbols, see *Note Declarations and
XVariable Definitions::. This makes it possible to prevent name clashes
Xand to hide implementation details.
X
X   The syntax of a script can now be stated as follows:
X
X     script                  : {include|declaration|definition|equation}
X
X   That is, a script is simply a (possibly empty) sequence of include
Xdirectives, declarations, variable definitions and equations, which may
Xappear in any order.
X
X   In the following, we describe the use of include directives and
Xprivate declarations in more detail.
X
X* Menu:
X
X* Include Scripts::
X* Private Symbols::
X
X
XFile: qdoc.info,  Node: Include Scripts,  Next: Private Symbols,  Prev: Scripts,  Up: Scripts
X
XInclude Scripts
X===============
X
X   The Q programming system currently does not support separate
Xcompilation of scripts, in the way you can compile modules written in
Xthe C programming language and link the corresponding object files
Xlater. However, it is possible to process multiple source files in one
Xcompilation, and you can make the dependencies between scripts explicit
Xby means of the `include' directive.
X
X   The include directive causes inclusion of the specified file, whose
Xname is enclosed in double quotes. For instance, if you have a script
Xnamed `myfuns.q' and wish to include the definitions contained in that
Xscript in another script, you can write:
X
X     include "myfuns.q";
X
X   Include directives may be nested; for instance, the `myfuns.q' script
Xcould contain `include''s as well. The compiler keeps track of all
Xincluded files, such that each file is only included *once*, at the
Xtime the first `include' for a given source file is encountered. This
Xmakes it possible to have a directed acyclic graph of module
Xdependencies rather than a simple tree. (The compiler identifies source
Xfiles by their *name*, stripping off path information and the suffix.
XTherefore the names of all scripts included in a program must be
Xunique, even if they are located in different directories.)
X
X   Unless explicit paths are specified, include files are usually
Xsearched for in the current directory and system-dependent locations
Xwhere "library scripts" are kept. This is also the place where the
Xstandard library scripts distributed with the Q programming system are
Xlocated. The directories to be searched can be specified by means of
Xthe `QPATH' environment variable, see *Note Using Q::.
X
X   Although all definitions of included files are available for use
X*anywhere* in a program, it is strongly recommended that you explicitly
Xstate at the beginning of each script which other modules are used by
Xthat script. The compiler then makes sure that all scripts are linked
Xtogether properly. For instance, suppose your program consists of three
Xmodules named `main.q', `lib.q' and `misc.q' with both `main.q' and
X`misc.q' depending on the definitions in `lib.q'. Then you should
Xinclude the `lib.q' script in *both* `main.q' and `misc.q'.
X
X   A word of caution: Since you will usually not be able to predict the
Xorder in which different scripts are linked together in one program, it
Xis bad style to have overlapping equations for a given expression
Xpattern being scattered out over different source files. The Q compiler
Xissues a warning message in such cases. Also, cyclic inclusion chains,
Xwhile being allowed, warrant a corresponding message from the compiler.
X(You can turn these messages off by invoking the compiler with the `-w'
Xoption, cf.  *Note Running Compiler and Interpreter::.)
X
X
XFile: qdoc.info,  Node: Private Symbols,  Prev: Include Scripts,  Up: Scripts
X
XPrivate Symbols
X===============
X
X   As already noted, each script included in a program can have its own
Xset of private function and variable symbols. Normally, any symbol
Xoccurring in a script is treated as "public" which means that it is
Xavailable for use anywhere in a program. Making all symbols public is
Xthe easiest way to go, but it bears the danger that you may
Xaccidentally "redefine" a symbol of another script which was actually
Xreserved for use within that script. As a remedy in such situations,
Xyou can declare a symbol private as follows:
X
X     private foo;
X
X   This also works with variable and type symbols. For instance:
X
X     private var C;
X     private type Color = const red, green, blue;
X
X   Any constructor symbol declared in a private type declaration will
Xalso be private, unless an explicit `public' scope prefix is used; see
X*Note Declarations and Variable Definitions::.
X
X   Private symbols are kept in a separate namespace which is accessible
Xonly to the script which declares the symbol. This prevents name clashes
Xwith public and private symbols in other scripts. If a private symbol of
Xa script happens to have the same name as a public symbol defined
Xelsewhere, the public symbol is hidden in that script. To be precise,
Xany occurrences of the symbol following its `private' declaration will
Xrefer to the private symbol. Thus you can still gain access to the
Xpublic symbol of the same name, but all its uses must precede the
X`private' declaration of the symbol. For instance, you can define
Xyourself a synonym for a public symbol which is later redeclared
Xprivate as follows:
X
X     public_foo              = foo;
X     private foo;
X     foo X                   = public_foo (bar X);
X
X   You can specify private symbols in the interpreter by using the
Xnotation `.NAME.SYMBOL', where NAME stands for the name of the script
Xwhich declares the symbol. For instance, you denote the private symbol
X`foo' declared in the script `myprog.q' as `.myprog.foo'. The same
Xnotation is used when the interpreter prints a private symbol, and by
Xthe built-in `str', `strq', `write' and `writeq' functions.
X
X
XFile: qdoc.info,  Node: Types,  Next: Special Forms,  Prev: Scripts,  Up: Top
X
XTypes
X*****
X
X   Q is an untyped programming language, and thus it is only possible to
Xdistinguish different "types" of objects - such as search trees, queues,
Xarrays and the like - by selecting an appropriate set of "constructor"
Xsymbols for each type of object. This chapter discusses Q's notion of
X"type guards" which allows you to make the assignment of constructors to
Xa type explicit, and to use this information in order to restrict the
Xapplicability of equations to objects of a given type.
X
X* Menu:
X
X* Using Type Guards::
X* Built-In Types::
X* Sub- and Supertypes::
X
X
XFile: qdoc.info,  Node: Using Type Guards,  Next: Built-In Types,  Prev: Types,  Up: Types
X
XUsing Type Guards
X=================
X
X   As in any programming language, the careful design of
Xapplication-dependent data structures is one of the main concerns when
Xdeveloping Q programs which go beyond simple numeric, string and list
Xprocessing. As a typical example for a non-list data structure which
Xplays a prominent role in many Q programs, let us consider binary
Xsearch trees, which are a convenient means to implement sets, bags,
Xdictionaries and the like. We will use this data structure as a running
Xexample throughout this chapter.
X
X   A typical choice of constructors for binary trees is the following:
X
X     public const niltree;
X     public bintree X T1 T2;
X
X   To make explicit the fact that `niltree' and `bintree' belong to the
Xbinary tree type, we can also use a type declaration which introduces
Xthe type symbol `BinTree', as discussed in *Note Declarations and
XVariable Definitions:::
X
X     type BinTree = const niltree
X                  | bintree X T1 T2
X                  ;
X
X   The type symbol can then be used as a "guard" on variables to ensure
Xthat a variable is only matched to objects of the given type, see *Note
XType Guards::. E.g., the following rule employs such a type guard in
Xorder to restrict the argument of the `foo' function to `BinTree'
Xobjects:
X
X     foo T:BinTree           = ...;
X
X   This makes it possible to avoid explicit argument patterns like
X
X     foo niltree             = ...;
X     foo (bintree X T1 T2)   = ...;
X
Xin cases in which the component values are not actually required. This
Xcan simplify matters a lot, in particular if multiple arguments have to
Xbe matched to a given type. Also, it is more efficient than checking
Xthe type of an object in the qualifier part of a rule by using a
Xuser-defined predicate, since the interpreter can use the type
Xinformation right away in the pattern matching process.
X
X   Another important reason for preferring type guards over explicit
Xargument patterns is the issue of "information hiding." With the former
Xdefinition of the `foo' function above we do not make any explicit
Xreference to the constructor patterns making up the `BinTree' data
Xtype. This makes it possible to treat `BinTree' as an "abstract data
Xtype" ("ADT") which hides the underlying implementation details (in
Xparticular the constructors), while still being able to verify that the
Xproper kind of object is supplied as an argument. Any access to objects
Xof the ADT will then be implemented by referring to the appropriate
Xoperations supplied by the type. In fact, we can make the constructors
Xprivate symbols which are only accessible to the script which
Ximplements the `BinTree' type:
X
X     type BinTree = private const niltree
X                  | private bintree X T1 T2
X                  ;
X
X   As a concrete example, let us assume the standard search tree
Xoperations `insert T X' and `delete T X', which insert an element `X'
Xinto a tree `T', and remove it from the tree, respectively. These
Xoperations can be implemented as follows (see [Bird/Wadler 1988]):
X
X     private join T1 T2, init T, last T;
X
X     insert niltree Y        = bintree Y niltree niltree;
X     insert (bintree X T1 T2) Y
X                             = bintree X (insert T1 Y) T2 if X>Y;
X                             = bintree X T1 (insert T2 Y) if X<Y;
X                             = bintree Y T1 T2 if X=Y;
X
X     delete niltree Y        = niltree;
X     delete (bintree X T1 T2) Y
X                             = bintree X (delete T1 Y) T2 if X>Y;
X                             = bintree X T1 (delete T2 Y) if X<Y;
X                             = join T1 T2 if X=Y;
X
X     join niltree T2         = T2;
X     join T1 T2              = bintree (last T1) (init T1) T2 otherwise;
X
X     init (bintree X T1 niltree)
X                             = T1;
X     init (bintree X T1 T2)  = bintree X T1 (init T2) otherwise;
X
X     last (bintree X T1 niltree)
X                             = X;
X     last (bintree X T1 T2)  = last T2 otherwise;
X
X   (Note that the `last' and `init' operations return the last element
Xof a binary tree, and a binary tree with the last element removed,
Xrespectively. The `join', `init' and `last' functions are for internal
Xuse only, and can hence be implemented as private functions.)
X
X   Furthermore, we assume the following function `mkBinTree' which
Xconstructs a binary tree from a list, and the function `members' which
Xreturns the list of elements stored in a tree (in ascending order):
X
X     mkBinTree Xs:List       = foldl insert niltree Xs;
X
X     members niltree         = [];
X     members (bintree X T1 T2)
X                             = members T1 + [X|members T2];
X
X   The definition of `mkBinTree' employs the `foldl' operation which
Xhas already been mentioned in *Note Higher-Order Functions:::
X
X     foldl F A []            = A;
X     foldl F A [X|Xs]        = foldl F (F A X) Xs;
X
X   We can use `foldl' and the interface operations of the `BinTree' ADT
Xin order to implement the functions `union' and `diff' which add and
Xremove all members of a tree to/from another tree:
X
X     /* union T1 T2: add elements of T2 to T1 */
X
X     union T1:BinTree T2:BinTree
X                             = foldl insert T1 (members T2);
X
X     /* diff T1 T2: remove elements of T2 from T1 */
X
X     diff T1:BinTree T2:BinTree
X                             = foldl delete T1 (members T2);
X
X   Observe that no explicit reference is made to the `BinTree'
Xconstructors; we only employ the public "interface" functions `insert',
X`delete' and `members' of the `BinTree' ADT.  This allows us to change
Xthe realization of the data structure without having to rewrite the
Xdefinitions of `union' and `diff'. Still, the definitions of `union'
Xand `diff' are "safe;" the `BinTree' type guard ensures that the
Xarguments passed to `union' and `diff' are indeed `BinTree' objects
Xcapable of carrying out the requested operations.
X
X
XFile: qdoc.info,  Node: Built-In Types,  Next: Sub- and Supertypes,  Prev: Using Type Guards,  Up: Types
X
XBuilt-In Types
X==============
X
X   Type guards are also the only way for verifying that the actual
Xvalue of a variable belongs to one of the built-in types integers,
Xfloating point numbers, strings and files, since there is no way for
Xwriting out all "constructors" for these kinds of objects - there are
Xinfinitely many.  For this purpose, the type symbols `Int', `Float',
X`String' and `File' are predefined. For instance, a predicate verifying
Xthat an expression is an integer can be implemented as follows:
X
X     isint X:Int             = true;
X     isint X                 = false otherwise;
X
X   There also is a type named `Num' which, when used as a guard on
Xvariables, matches numeric (i.e. both integer and floating point)
Xvalues.  Technically, `Num' is the "supertype" of both `Int' and
X`Float'; more about that in *Note Sub- and Supertypes::. E.g., here is a
Xdefinition of a function `abs' which returns the absolute value of an
Xinteger or floating point number:
X
X     abs X:Num               = X if X>=0;
X                             = -X otherwise;
X
X   The built-in `List' type matches all list expressions of the form
X`[]' or `[X|Xs]'. This type is used to restrict the applicability of an
Xequation to list arguments. For instance, the following equations
Xdefine a function `reverse' which reverses a list:
X
X     reverse Xs:List         = foldl push [] Xs;
X     push Xs:List X          = [X|Xs];
X
X   (Note that there is no built-in `tuple' type in the Q language.
XThere is no point in introducing such a type symbol, since *any*
Xexpression in the Q language is a tuple. To match empty tuples `()' and
Xpairs `(X,Xs)', the corresponding patterns must be used explicitly.)
X
X   Finally, the predefined `Bool' type is a convenient means to refer to
Xobjects which are truth values. It can be thought of as being
Xpredefined as follows:
X
X     type Bool = const false, true;
X
X
XFile: qdoc.info,  Node: Sub- and Supertypes,  Prev: Built-In Types,  Up: Types
X
XSub- and Supertypes
X===================
X
X   The Q programming language also provides a subtype concept similar
Xto the notion of single inheritance in object-oriented programming
Xlanguages such as SMALLTALK. For instance, we can modify our
Xdeclaration of the `BinTree' type (cf. *Note Using Type Guards::) in
Xorder to make `BinTree' a subtype of the supertype `SearchTree' as
Xfollows:
X
X     type BinTree : SearchTree = private const niltree
X                               | private bintree X T1 T2
X                               ;
X
X   Usually, supertypes will be "abstract" types which do not provide
Xtheir own set of constructor symbols, but are simply used to factor out
Xcommon operations shared among several "concrete" types. For instance,
Xthe `SearchTree' type might have been declared as follows:
X
X     type SearchTree;
X
X   Now variables of type `SearchTree' will also match objects of its
Xsubtype `BinTree', as well as of any other subtype of `SearchTree'. We
Xcan turn the `union' and `diff' functions from *Note Using Type
XGuards::, into operations on the `SearchTree' type as follows:
X
X     union T1:SearchTree T2:SearchTree
X                             = foldl insert T1 (members T2);
X
X     diff T1:SearchTree T2:SearchTree
X                             = foldl delete T1 (members T2);
X
X   As the next step, we might introduce another type `AVLTree' providing
Xthe same interface operations `insert', `delete' and `members' as the
X`BinTree' type, but implementing these operations in terms of AVL trees
Xrather than simple binary trees. (AVL trees are a variant of binary
Xsearch trees in which the trees are kept balanced, and thus logarithmic
Xinsertion and deletion times can be guaranteed.) If we make `AVLTree'
Xanother subtype of `SearchTree', then the `union' and `diff' operations
Xcan be applied to `AVLTree' objects just as well as to `BinTree''s. In
Xfact, the operations will even work if we mix argument types, e.g.,
Xprovide a `BinTree' as the first argument of `union' and an `AVLTree'
Xas the second! By these means, it is possible to define polymorphic
Xoperations which are applicable to several different types sharing the
Xsame (subset of) interface functions.
X
X   For the sake of concreteness, here is an implementation of the
X`AVLTree' type. The `shl', `shr', `rol' and `ror' functions implement
Xthe common AVL tree rotation operations which are used to keep the tree
Xbalanced; see [Bird/Wadler 1988] for details.
X
X     include "stdlib.q";     % for the foldl and max functions
X
X     /* H denotes the height of a nonempty AVL tree */
X
X     type AVLTree : SearchTree = private const niltree
X                               | private bintree H X T1 T2
X                               ;
X
X     private mknode X T1 T2;
X     private join T1 T2, init T, last T, height T, slope T, rebal T;
X     private rol T, ror T, shl T, shr T;
X
X     mkAVLTree Xs:List       = foldl insert niltree Xs;
X
X     members niltree         = [];
X     members (bintree H X T1 T2)
X                             = members T1 + [X|members T2];
X
X     insert niltree Y        = bintree 1 Y niltree niltree;
X     insert (bintree H X T1 T2) Y
X                             = rebal (mknode X (insert T1 Y)) T2 if X>Y;
X                             = rebal (mknode X T1 (insert T2 Y)) if X<Y;
X                             = bintree H Y T1 T2 if X=Y;
X
X     delete niltree Y        = niltree;
X     delete (bintree H X T1 T2) Y
X                             = rebal (mknode X (delete T1 Y) T2) if X>Y;
X                             = rebal (mknode X T1 (delete T2 Y)) if X<Y;
X                             = join T1 T2 if X=Y;
X
X     join niltree T2         = T2;
X     join T1 T2              = rebal (mknode (last T1) (init T1) T2) otherwise;
X
X     init (bintree H X T1 niltree)
X                             = T1;
X     init (bintree H X T1 T2)
X                             = rebal (mknode X T1 (init T2)) otherwise;
X
X     last (bintree H X T1 niltree)
X                             = X;
X     last (bintree H X T1 T2)
X                             = last T2 otherwise;
X
X     /* mknode constructs a tree node, computing the height value */
X
X     mknode X T1 T2          = bintree (max (height T1) (height T2) +1)
X                                     X T1 T2;
X
X     /* height and slope compute the height and slope (difference between
X        heights of the left and the right subtree), respectively */
X
X     height niltree          = 0;
X     height (bintree H T1 T2)
X                             = H;
X
X     slope niltree           = 0;
X     slope (bintree H X T1 T2)
X                             = height T1 - height T2;
X
X     /* rebal rebalances after single insertions and deletions */
X
X     rebal T                 = shl T if slope T = -2;
X                             = shr T if slope T = 2;
X                             = T otherwise;
X
X     /* rotation operations */
X
X     rol (bintree H1 X1 T1 (bintree H2 X2 T2 T3))
X                             = mknode X2 (mknode X1 T1 T2) T3;
X
X     ror (bintree H1 X1 (bintree H2 X2 T1 T2) T3)
X                             = mknode X2 T1 (mknode X1 T2 T3);
X
X     shl (bintree H X T1 T2)
X                             = rol (mknode X T1 (ror T2)) if slope T2 = 1;
X                             = rol (bintree H X T1 T2) otherwise;
X
X     shr (bintree H X T1 T2)
X                             = ror (mknode X T1 (ror T2)) if slope T2 = -1;
X                             = ror (bintree H X T1 T2) otherwise;
X
X
XFile: qdoc.info,  Node: Special Forms,  Next: Built-In Functions,  Prev: Types,  Up: Top
X
XSpecial Forms
X*************
X
X   As discussed in *Note Equations and Expression Evaluation::, the Q
Xinterpreter evaluates expressions in applicative, i.e.
Xleftmost-innermost, order. This means that the arguments of a function
Xare usually evaluated before the function is applied to them.
XOccasionally, it is useful or even essential to defer the evaluation of
Xarguments until they are actually required in the course of a
Xcomputation. For this purpose, the Q language lets you introduce
Xso-called "special forms". This chapter discusses how these constructs
Xare defined and used.
X
X* Menu:
X
X* Basic Concepts::
X* Form of Special Declarations::
X* Special Constructors::
X* Built-In Special Forms::
X* The Special Form Quote::
X
X
XFile: qdoc.info,  Node: Basic Concepts,  Next: Form of Special Declarations,  Prev: Special Forms,  Up: Special Forms
X
XBasic Concepts
X==============
X
X   Consider the following definition from the standard library script
X`special.q' which implements a kind of conditional expression:
X
X     cond P X Y              = X if P;
X                             = Y otherwise;
X
X   The `cond' function takes as its first argument a truth value which
Xis used to determine whether the second or third argument is to be
Xreturned as the value of the conditional expression. Although the above
Xdefinition is perfectly correct, using applicative order evaluation
Xwith this definition is clearly inappropriate since all arguments must
Xalready have been evaluated before the `cond' function gets applied to
Xthem. Since either the second or third argument is simply thrown away,
Xthe effort involved in the evaluation of this argument is wasted. As an
Xextreme case, e.g., `Y' might not have a terminating evaluation at all,
Xin which case the evaluation of `cond P X Y' would not terminate either
Xeven though `Y' is actually not required if `P' happens to evaluate to
X`true'.
X
X   Instead, we would like to have `cond' evaluate its arguments only as
Xthey are required. In the Q language, this can be done simply by
Xdeclaring `cond' as a "special form". All we have to do is to precede
Xthe above equations with the following declaration:
X
X     special cond P X Y;
X
X   This tells the Q interpreter that the `cond' function expects three
Xarguments `P', `X' and `Y' which should be left unevaluated until their
Xvalues are actually required to reduce the qualifier or the right-hand
Xside of an equation in `cond''s definition. Thus, when the interpreter
Xcomes to consider the first rule,
X
X     cond P X Y              = X if P;
X
Xit will first evaluate `P' to obtain the value of the condition part of
Xthis rule. If `P' evaluates to `true', `X' will be evaluated and
Xreturned as the value of the left-hand side expression. Otherwise (if
X`P' evaluates to `false'), `X' will be left unevaluated, and the
Xinterpreter considers the next rule,
X
X     cond P X Y              = Y otherwise;
X
Xwhich causes it to evaluate `Y' and reduce `cond P X Y' to this value.
X
X   Note that a "special" argument is evaluated any time its value is
Xrequired on the right-hand side of a definition. Consider, for instance:
X
X     special foo P X;
X     foo P X                 = X * sqrt X if P;
X                             = 0 otherwise;
X
X   As the first rule is applied `X' actually gets evaluated twice, once
Xfor each occurrence on the right-hand side of the equation. We can avoid
Xthis by introducing an auxiliary function `bar' as follows:
X
X     special foo P X;
X     foo P X                 = bar X if P;
X                             = 0 otherwise;
X     bar X                   = X * sqrt X;
X
X   Now, the `X' parameter is evaluated before the `bar' function is
Xapplied to it, since `bar' is implemented as an "ordinary"
X(non-`special') function.
X
X   It should be noted that in the Q language special forms are indeed a
Xruntime feature. This means that special forms are not only recognized
Xat compile time, but also when they are passed as arguments or returned
Xas function results in the course of a computation (which usually
Xcannot be predicted at compile time). For instance, if we define `foo'
Xas follows:
X
X     special bar X;
X     foo                     = bar;
X
Xthen `foo (1+1)' evaluates to `bar (1+1)' and *not* to `bar 2',
Xalthough `foo' itself is not declared to be a special form. This also
Xworks if you pass `bar' as a functional parameter:
X
X     special bar X;
X     foo F X                 = F (X+1);
X
X   Given the above definition, `foo bar 1' will evaluate to `bar (1+1)'.
X
X   On the other hand, you must take care that arguments to special
Xfunctions which are passed on by other functions are not evaluated too
Xearly. For instance, if the `apply' function is defined as follows:
X
X     apply F X               = F X;
X
Xand is then invoked as `apply bar (1+1)' then `(1+1)' will be evaluated
Xeven though `bar' is a special form. The reason is that the argument
X`(1+1)' is evaluated *before* `apply' is applied to it, since we have
Xnot declared `apply' as a special form as well.  (Actually, this effect
Xis commonly used deliberately to force evaluation of special form
Xarguments.)
X
X   As a general rule, you should make any function a special form that
Xpasses its arguments to another special form, unless you explicitly
Xwish to evaluate these arguments.
X
X
XFile: qdoc.info,  Node: Form of Special Declarations,  Next: Special Constructors,  Prev: Basic Concepts,  Up: Special Forms
X
XForm of Special Declarations
X============================
X
X   The syntax of `special' declarations has already been introduced in
X*Note Declarations and Variable Definitions::. The `special' keyword
Xmust be followed by a function identifier and a sequence of variable
Xsymbols (the variable symbols only serve to specify the number of
Xarguments, and are otherwise treated as comments). If the argument list
Xis omitted, the symbol is actually treated as an ordinary (non-special)
Xsymbol. Otherwise the argument list specifies the number of parameters
Xwhich should be protected from being evaluated. For instance, if `foo'
Xis declared as
X
X     special foo X Y;
X
Xand is then invoked as `foo X Y Z' then only `X' and `Y' will be left
Xunevaluated, while `Z' will be evaluated as usual.
X
X
XFile: qdoc.info,  Node: Special Constructors,  Next: Built-In Special Forms,  Prev: Form of Special Declarations,  Up: Special Forms
X
XSpecial Constructors
X====================
X
X   Special forms prevent their arguments from being evaluated until
Xthey are used in a context which is not "protected" by another special
Xform. In particular, you can also have special "constructors" which
Xprotect their arguments until they are extracted in an ordinary
Xcontext. A prime example for this are "streams", a kind of infinite
Xlist data structure. We can implement streams using a type definition
Xlike the following:
X
X     type Stream = const nilstream | special binstream X Xs;
X
X   Just like lists, a stream consists of a head element, `X', and a
Xstream of remaining elements, `Xs'. Now the "head" and "tail" operations
Xfor lists (cf. *Note Equations::) carry over to streams as follows:
X
X     hd (binstream X Xs)     = X;
X     tl (binstream X Xs)     = Xs;
X
X   LISP programmers should note that this implementation does not
Xrequire any explicit "delay" and "force" operations; all necessary
Xevaluations are performed implicitly by the Q interpreter. For
Xinstance, consider the stream of all integers starting from `N':
X
X     ints N                  = binstream N (ints (N+1));
X
X   With leftmost-innermost evaluation, this definition would certainly
Xcause severe troubles, because of the recursive invokation of `ints'.
XHowever, since `binstream' is a special form we have the following:
X
X     => def S = ints 1
X
X     => S
X     binstream 1 (ints (1+1))
X
X     => hd S
X     1
X
X     => tl S
X     binstream 2 (ints (2+1))
X
X   We can also have finite streams if we use the `nilstream' constant to
Xsignal the end of a stream, and most common list operations carry over
Xto streams accordingly. In difference to lists, streams produce their
Xelements only "on demand." This paves the way for some important and
Xpowerful programming techniques. For instance, streams are a useful
Xdevice to implement different kinds of backtracking and dynamic
Xprogramming algorithms in a uniform setting. Please refer to
X[Abelson/Sussman 1985] for more details. The standard library includes
Xan implementation of streams which is described in *Note The Standard
XLibrary::.
X
X
XFile: qdoc.info,  Node: Built-In Special Forms,  Next: The Special Form Quote,  Prev: Special Constructors,  Up: Special Forms
X
XBuilt-In Special Forms
X======================
X
X   Some built-in operations of the Q language are actually implemented
Xas special forms. This is necessary, in particular, in the case of the
Xlogical connectives `and' and `or' which are usually evaluated in
X"short-circuit mode." For instance, the `and' operator first evaluates
Xits first argument and checks whether it denotes a truth value (if not,
Xthe rule fails). Then, if the first argument evaluated to `false',
X`false' is returned - there is no need to take a look at the second
Xargument. Otherwise, the second argument is evaluated and returned as
Xthe value of the expression. The `or' operation is defined analogously.
XThese rules allow the Q interpreter to perform the following reductions
Ximmediately, without ever having to evaluate the second argument `foo
XX':
X
X     true or foo X           => true
X     false and foo X         => false
X
X   The fact that `and' and `or' are special forms must be taken into
Xaccount when overloading these operations. In fact, this becomes a
Xnuisance when trying to implement algebraic simplification rules for
Xlogical expressions in a style similar to the distributivity and
Xassociativity rules for `+' and `*' mentioned in *Note Equations::.
XTherefore it is possible to turn off the special treatment of these
Xoperations by means of the `-c' option of the compiler (cf. *Note
XRunning Compiler and Interpreter::). The `-c' option instructs the
Xcompiler to treat the connectives `and' and `or' as ordinary operations
Xjust like `+' and `*', s.t. logical expressions are evaluated completely
Xusing the standard leftmost-innermost evaluation rule. This makes the
Xfollowing script, which is used to transform symbolic logical
Xexpressions into disjunctive normal form, work as expected:
X
X     % compile with -c
X     % eliminate double negations:
X     not not A               = A;
X     % push negations inward (deMorgan's laws):
X     not (A or B)            = not A and not B;
X     not (A and B)           = not A or not B;
X     % distributivity laws:
X     A and (B or C)          = A and B or A and C;
X     (A or B) and C          = A and C or B and C;
X
X   As already mentioned, operator sections (cf. *Note Sections::) are
Xalso implemented by means of certain special forms, namely `leftsect'
Xand `rightsect'. The definition of these operations is fairly
Xstraightforward. In fact, the programmer could easily define them
Xhimself or herself as follows:
X
X     special leftsect X Y Z, rightsect X Y Z;
X
X     leftsect X Y Z          = X Y Z;
X     rightsect X Y Z         = X Z Y;
X
X   Now a construct such as `(1/)' or `(/2)' can be represented as
X`leftsect (/) 1' and `rightsect (/) 2', respectively. As an exercise,
Xthe reader may verify that the above definitions produce the correct
Xresults with expressions like `(1/) 3' and `(/2) 3'.
X
X   The reason that `leftsect' and `rightsect' are implemented as
Xspecial forms is that this makes sections involving special operators
Xsuch as `and' and operands invoking operations with side-effects (see
X*Note Built-In Functions::) work as expected. For instance, let the
X`loop' symbol stand for a nonterminating evaluation:
X
X     loop                    = loop;
X
X   Then `(and loop) false' still correctly reduces to `false' since the
Xoperand `loop' will not be evaluated before it is passed to `(and)'.
XSimilarly, a section like `(||writec "\n")' will not evaluate the
X`writec "\n"' operand until the first operand is supplied. On the other
Xhand, this means that for a non-special operator the specified operand
Xwill be evaluated any time the section is applied to a given
Xexpression. E.g., the section `(+1/3)' will evaluate `1/3' any time it
Xis applied to an argument.
X
X
XFile: qdoc.info,  Node: The Special Form Quote,  Prev: Built-In Special Forms,  Up: Special Forms
X
XThe Special Form Quote
X======================
X
X   Another built-in special form is the predefined function symbol
X`quote', which acts as a constructor that protects its single argument
Xexpression from being evaluated:
X
X     special quote X;
X
X   This construct is useful if you wish to treat certain expressions
X(which may or may not be in normal form) as literal objects rather than
Xhaving them evaluated. For instance:
X
X     => quote (1+1)
X     quote (1+1)
X
X   LISP programmers should note that `quote' is in fact a constructor,
Xand *not* a function which returns its single argument unevaluated.
XThis is essential since in the Q language an expression only remains
Xunevaluated as long as it is protected by a special form - any
Xexpression which occurs outside the context of a special form is always
Xin normal form.
X
X   The reason that `quote' is supplied as a built-in in the Q language
Xis that certain built-in operations return quoted expressions as
Xresults or take such expressions as arguments, cf. *Note Built-In
XFunctions::.
X
X
XFile: qdoc.info,  Node: Built-In Functions,  Next: The Standard Library,  Prev: Special Forms,  Up: Top
X
XBuilt-In Functions
X******************
X
X   Besides the built-in operators already discussed in *Note
XExpressions::, the Q language also provides a collection of predefined
Xfunctions which cover a variety of elementary operations. The built-in
Xfunctions can be divided into five major groups, numeric functions,
Xstring functions, conversion functions, I/O functions, and
Xmiscellaneous functions. We will describe each of these in turn.
X
X* Menu:
X
X* Numeric Functions::
X* String Functions::
X* Conversion Functions::
X* I/O Functions::
X* Miscellaneous Functions::
X
X
XFile: qdoc.info,  Node: Numeric Functions,  Next: String Functions,  Prev: Built-In Functions,  Up: Built-In Functions
X
XNumeric Functions
X=================
X
X`exp X'
X     exponential function
X
X`ln X'
X     natural logarithm
X
X`sqrt X'
X     square root
X
X`sin X'
X     sine
X
X`cos X'
X     cosine
X
X`atan X'
X     arcus tangent
X
X`random'
X     random number
X
X`seed N'
X     initialize random number generator
X
X   This group includes the usual trigonometric and exponential
Xfunctions, logarithms and square root. All these functions take both
Xinteger and floating point arguments. They return a floating point
Xnumber. Besides this, there is a parameterless function `random' which
Xreturns a pseudo random floating point value in the range 0 <= x < 1.
XThe current implementation uses the portable random number generator
Xdeveloped by George Marsaglia and Arif Zaman [Marsaglia/Zaman 1987]. The
Xgenerator is initialized automatically with a seed taken from the system
Xclock at the time the interpreter starts up. The `seed' function allows
Xto initialize the generator explicitly with a given integer seed; this
Xis useful if it is necessary to reproduce random sequences.
X
X
XFile: qdoc.info,  Node: String Functions,  Next: Conversion Functions,  Prev: Numeric Functions,  Up: Built-In Functions
X
XString Functions
X================
X
X   This group consists of two operations for extracting substrings from
Xa string and searching for occurrences of a substring in a string:
X
X`substr S K L'
X     return substring of length `L' at position `K' in `S'
X
X`pos S1 S'
X     position of substring `S1' in `S'
X
X   Positions are specified as integers ranging from `0' to `(#S-1)',
Xwith `0' denoting the position of the first character in a string (just
Xas with the indexing operator `!'). The `pos' function returns `-1' if
Xthere is no occurrence of the given substring in the string.  The
X`substr' function takes three arguments: the subject string `S', the
Xindex `K' at which the substring begins, and the number `L' of
Xcharacters to be extracted from the subject string. If `K' is less than
Xzero, it is assumed to be zero. If `L' is less than or equal to zero,
Xor if `K>=#S', the empty string is returned. If `L' exceeds the number
Xof characters behind position `K', the remainder of the string is
Xreturned.
X
X
XFile: qdoc.info,  Node: Conversion Functions,  Next: I/O Functions,  Prev: String Functions,  Up: Built-In Functions
X
XConversion Functions
X====================
X
X   This group consists of functions for converting between different
Xkinds of objects:
X
X`trunc X'
X     truncate floating point to integer value
X
X`round X'
X     round floating point to nearest integer value
X
X`int X'
X     integer part of floating point number
X
X`frac X'
X     fraction part of floating point number
X
X`ord C'
X     character number in local character set
X
X`chr N'
X     character with given number
X
X`str X'
X     convert expression to string
X
X`strq X'
X     convert quoted expression to string
X
X`val S'
X     convert string to expression
X
X`valq S'
X     convert string to quoted expression
X
X   The `str' function converts its argument expression to the
Xcorresponding print representation conforming to the Q expression
Xsyntax, which is returned as a string; the argument is evaluated as
Xusual. The `strq' function is similar, but converts a quoted expression
X(cf.  *Note The Special Form Quote::). For instance:
X
X     str (1+1)               => "2"
X     strq (quote (1+1))      => "1+1"
X
X   The `val'/`valq' functions are the counterpart of `str' and `strq';
Xthey convert a string containing the print representation of an
Xexpression back to an expression. In the case of `val', the expression
Xis evaluated, while `valq' returns the parsed expression as it is,
Xprotected with `quote':
X
X     val "1+1"               => 2
X     valq "1+1"              => quote (1+1)
X
X   These functions require that the contents of their string arguments
Xconform to the Q expression syntax. In case of a syntax error, the
Xbuilt-in rules fail.
X
X
XFile: qdoc.info,  Node: I/O Functions,  Next: Miscellaneous Functions,  Prev: Conversion Functions,  Up: Built-In Functions
X
XI/O Functions
X=============
X
X   This group provides functions for handling input/output from/to the
Xterminal or a text file. These functions implement operations with
Xside-effects; the side-effects consist in modifying the terminal
Xdisplay or a file.
X
X`fopen NAME MODE'
X     open file `NAME' in mode `MODE'
X
X`popen CMD MODE'
X     open pipe `CMD' in mode `MODE'
X
X`read, fread F'
X     read an expression from the terminal or a file
X
X`readq, freadq F'
X     read a quoted expression from the terminal or a file
X
X`readc, freadc F'
X     read a character from the terminal or a file
X
X`reads, freads F'
X     read a string from the terminal or a file
X
X`write X, fwrite F X'
X     write an expression to the terminal or a file
X
X`writeq X, fwriteq F X'
X     write a quoted expression to the terminal or a file
X
X`writec C, fwritec F C'
X     write a character to the terminal or a file
X
X`writes S, fwrites F S'
X     write a string to the terminal or a file
X
X`eof, feof F'
X     check for end-of-file on the terminal or a file
X
X* Menu:
X
X* Terminal I/O::
X* File I/O::
X* Pipes::
X
X
XFile: qdoc.info,  Node: Terminal I/O,  Next: File I/O,  Prev: I/O Functions,  Up: I/O Functions
X
XTerminal I/O
X------------
X
X   Input from the terminal (i.e. the standard input device) is done
Xthrough the parameterless functions `read', `readq', `readc' and
X`reads' which read and return, respectively, an expression, a quoted
Xexpression, a single character, and a string. Terminal input is
Xline-buffered which means that you must type an entire input line
Xbefore anything is returned by these functions.
X
X   The `reads' function obtains one line of input, strips off the
Xtrailing newline character, and returns the result as a string. For
Xinstance (here and in the following, `<CR>' means that you hit the
Xcarriage return key to terminate the input line, rather than actually
Xtyping the string `"<CR>"'):
X
X     => reads
X     one line of text<CR>
X     "one line of text"
X
X   The `readc' function allows you to read input character by character;
Xat the end of a line the newline character `"\n"' is returned:
X
X     => readc
X     <CR>
X     "\n"
X
X   The `read' and `readq' functions read one line from the input, as
Xwith `reads', and convert the resulting string to an expression, as with
X`val' and `valq', respectively. For instance:
X
X     => read
X     1+1<CR>
X     2
X
X     => readq
X     1+1<CR>
X     quote (1+1)
X
X   The corresponding functions for producing output on the terminal are
Xnamed `write', `writeq', `writec' and `writes'. They print an
Xexpression, a quoted expression, a character and a string, respectively.
XThese functions take one argument, the object to be printed, and return
Xthe empty tuple `()'. For instance:
X
X     => writec "x"
X     x()
X
X     => writes "one line of text\n"
X     one line of text
X     ()
X
X     => write (1+1)
X     2()
X
X     => writeq (quote (1+1))
X     1+1()
X
X   (Output operations are invoked solely for their side-effects.
XHowever, any Q expression must have a value, and since there is no
Xother meaningful value to return, the `write' functions return `()'. In
Xthe above examples, this value is output by the interpreter after the
Xprinted text, which explains, e.g., the `x()' in response to `writec
X"x"'.)
X
X   It is common practice to combine these operations by means of the
X`||' operator in order to implement dialogs such as the following
Xprompt/input interaction:
X
X     => writes "Input: " || reads
X     Input: one line of text<CR>
X     "one line of text"
X
X   You will also often encounter several output operations for
Xinterpolating data into text fragments:
X
X     => writes "The result is " || writeq (quote (1+1)) || writes ".\n"
X     The result is 1+1.
X     ()
X
X   Finally, the `eof' function allows you to check for "end-of-file" on
Xthe terminal. Actually, this causes another line of input to be read
Xfrom the terminal if no input is currently available, to see whether the
Xend of the input has been reached. Most operating systems allow you to
Xtype a special character to indicate end-of-file, such as the `Ctl-D'
Xcharacter on the UNIX system:
X
X     => eof
X     <Ctl-D>
X     true
X
X
XFile: qdoc.info,  Node: File I/O,  Next: Pipes,  Prev: Terminal I/O,  Up: I/O Functions
X
XFile I/O
X--------
X
X   File input and output is implemented by the functions `fread',
X`freadq', `freadc', `freads', `fwrite', `fwriteq', `fwritec' and
X`fwrites'. There also is an `feof' function which allows to check
Xwhether the end of a file has been reached. These operations are
Xanalogous to their terminal equivalents, but take an additional first
Xargument, a "file object". A file object is a special kind of
Xelementary object in the Q language which is returned by the built-in
X`fopen' function.
X
X   The `fopen' function takes two string arguments, the "name" of the
Xfile to be opened (which is the name under which the file is known by
Xthe operating system), and the "mode" in which the file is to be
Xopened. The mode string must consist of a single character. The
Xcharacter `"r"' means to open an existing file for reading, `"w"' to
Xopen a new file for writing (existing files are truncated to zero
Xsize), and `"a"' to create a new or append to an existing file.
X
X   For instance, a function checking whether a file exists and is
Xaccessible for reading can be implemented as follows:
X
X     exists NAME             = isfile (fopen NAME "r");
X     isfile X:File           = true;
X     isfile X                = false otherwise;
X
X   Files are closed automatically when the corresponding file objects
Xare no longer accessible in a computation. Therefore no explicit
Xoperation for closing a file is required. E.g., with the above
Xdefinition of the `exists' function, if you invoke this function as
X`exists "myfile"', then the file object returned by `fopen "myfile" "r"'
X(assuming that the file actually exists) will become inaccessible as
Xsoon as it has been processed by the `isfile' function, at which point
Xit gets closed. Similarly, if you assign a file to a variable in the
Xinterpreter,
X
X     => def F = fopen "myfile" "r"
X
Xthe file will be closed as soon as you undefine the variable:
X
X     => undef F
X
X   As an example for the use of file I/O, here's a function which copies
Xthe contents of one file opened in read mode to another file opened in
Xwrite or append mode:
X
X     fcopy F G               = () if feof F;
X                             = fwritec G (freadc F) || fcopy F G otherwise;
X
X   There is also a tail-recursive implementation of `fcopy' which
Xprevents stack overflows (cf. *Note Tail Recursion::):
X
X     fcopy F G               = () if feof F;
X                             = fcopy F (fwritec G (freadc F) || G) otherwise;
X
X   Note that file objects are indeed modified by input and output
Xoperations; at least, the file pointer is moved accordingly. Otherwise
Xthe above definitions would not work. This also becomes apparent when
Xmanipulating files interactively:
X
X     => def F = fopen "xyz" "r"
X
X     => freads F
X     "FIRST LINE IN FILE XYZ"
X
X     => freads F
X     "SECOND LINE IN FILE XYZ"
X
X     ...
X
X   It should be noted that all file objects in the Q language are
Xactually implemented as text files; binary files are *not* supported,
Xalthough some systems may allow you to interpret a binary file as a
Xfile of characters (this is considered non-portable, and hence should be
Xavoided). We also remark that since file objects have no printable
Xrepresentation, the functions `str', `strq', `write' and `writeq'
Xunparse such objects employing the special notation `<<file>>'. (This
Xnotation also prevents such objects from being reparsed using `val',
X`valq', `read' and `readq', of course.)
X
X
XFile: qdoc.info,  Node: Pipes,  Prev: File I/O,  Up: I/O Functions
X
XPipes
X-----
X
X   The `popen' function is used to create a file object connected to a
X"pipe". The file objects constructed with `popen' allow you to pipe
Xdata into an operating system command, and to read the output of such a
Xcommand from a file. Like `fopen', `popen' takes two string arguments.
XThe first parameter denotes the command to be executed, and the second
Xparameter specifies the mode in which the pipe is to be opened. The
Xmode argument must be either `"r"' (read from the output of the given
Xcommand) or `"w"' (write to the input of the command), and causes a
Xfile object open for reading or writing to be returned, respectively.
X
X   Input pipes are typically employed for retrieving information from
Xthe host operating system. For instance, on UNIX systems we can use the
X`ls' command to obtain a list of filenames matching a given wildcard
Xspecification. A corresponding function `ls' which returns such a list
Xcan be implemented as follows:
X
X     ls S:String             = freadls (popen ("ls "+S) "r");
X     freadls F:File          = [] if feof F;
X                             = [freads F|freadls F] otherwise;
X
X   As an example for an output pipe, the following function `more'
Xpipes a file through the `more' program which displays the file page by
Xpage:
X
X     more F:File             = fcopy F (popen "more" "w");
X
X   (The definition of `fcopy' is as in *Note File I/O::.)
X
X   Just like ordinary files, pipes are closed automatically when the
Xcorresponding file object is no longer accessible. Furthermore, the
Xinterpreter waits for the command started with `popen' to finish when
Xclosing the pipe.
X
X   Output pipes are a convenient means to implement specialized output
Xdevices in the Q language. For instance, the standard library script
X`graphics.q' writes its graphics output to a file `GRAPHICS' which is
Xusually implemented as a pipe to a PostScript previewer like, e.g.,
XGhostscript:
X
X     def GRAPHICS = popen "gs -q -" "w";
X
X
XFile: qdoc.info,  Node: Miscellaneous Functions,  Prev: I/O Functions,  Up: Built-In Functions
X
XMiscellaneous Functions
X=======================
X
X   This group consists of some special operations which do not fit into
Xany of the other groups treated above.
X
X`halt'
X     halt evaluation
X
X`quit'
X     exit the Q interpreter
X
X`break'
X     invoke the debugger
X
X`quote X'
X     quote constructor
X
X`leftsect X Y Z, rightsect X Y Z'
X     left and right section
X
X`isspecial X'
X     predicate checking whether argument is a special form
X
X`isconst X, isfun X, isvar X'
X     predicates checking whether argument is a constant, function or
X     variable symbol, respectively
X
X`isdef X'
X     predicate checking whether the variable X has been assigned a value
X
X   The `halt' function never returns, but causes the evaluation process
Xto be aborted. This last resort is commonly used in case of a fatal
Xerror condition. The `quit' function is like `halt', but it also exits
Xfrom the interpreter and returns you to the operating system shell; this
Xoperation is often used interactively to terminate a session with the
Xinterpreter. The `break' function interrupts an evaluation and invokes
Xthe symbolic debugger built into the Q interpreter (cf. *Note
XDebugging::); it returns `()'. This operation allows you to set
Xbreakpoints in a script. For instance,
X
X     foo X                   = break || bar X;
X
Xcauses the debugger to be invoked as soon as the rule is executed.
X
X   The `quote' constructor allows to protect expressions from being
Xevaluated; it has already been described in *Note The Special Form
XQuote::.  The special forms `leftsect' and `rightsect' are used for the
Xinternal representation of operator sections; however, you can also
Xinvoke them directly. See *Note Built-In Special Forms:: for a
Xdiscussion of these functions.
X
X   The predicate `isspecial' allows you to determine whether an
Xexpression is a special form which will receive its next argument
Xunevaluated. The predicates `isconst', `isfun' and `isvar' are special
Xforms which are used to check whether an expression is a constant symbol
X(including the built-in constants `true', `false', `[]' and `()'),
Xother function symbol (including the built-in operators `(+)', `(*)',
Xetc.), or variable symbol, respectively. Finally, the special form
X`isdef' can be used to check whether its argument (a variable) has been
Xassigned a value using `def'.
X
X
XFile: qdoc.info,  Node: The Standard Library,  Next: Q Language Grammar,  Prev: Built-In Functions,  Up: Top
X
XThe Standard Library
X********************
X
X   This chapter gives an overview of the data types and operations
Xprovided by the standard library modules supplied with the Q
Xprogramming system.  The library currently consists of the following
Xscripts:
X
X`assert.q'
X     print diagnostics
X
X`error.q'
X     print error messages
X
X`graphics.q'
X     graphics interface
X
X`lambda.q'
X     an implementation of the lambda calculus
X
X`lex.q'
X     lexicographic ordering on lists and tuples
X
X`list.q'
X     list comprehensions
X
X`math.q'
X     mathematical functions
X
X`plain.q'
X     empty Q script (see *Note Getting Started::)
X
X`sort.q'
X     a collection of sorting algorithms
X
X`special.q'
X     miscellaneous special forms
X
X`stdlib.q'
X     a collection of common standard functions
X
X`stdtypes.q'
X     a collection of efficient container data structures
X
X`stream.q'
X     an implementation of streams
X
X`string.q'
X     additional string functions
X
X`type.q'
X     a collection of expression predicates
X
X   Use the `std.q' script to load all modules except `math.q',
X`graphics.q' and `lex.q'. To include the `math.q' script, too, use
X`stdm.q' instead. (This still does not include the `graphics.q' and
X`lex.q' modules which are "added value" scripts that must be included
Xexplicitly.)
X
X   The `stdlib.q' script is probably the one which will be used most
Xfrequently by the average programmer; it contains a lot of additional
Xlist processing functions and other useful stuff mostly adopted from
X[Bird/Wadler 1988]. This module is also included by many other library
Xscripts.  Historically, it was the first script written for the
Xstandard library.
X
X   The `stdtypes.q' script simply includes all modules which implement
Xcommon container data structures; currently these are `array.q',
X`bag.q', `dict.q', `heap.q' and `set.q', see *Note Standard Types::. It
Xis also possible to load a single script such as `array.q' if you do
Xnot need the entire collection.
X
X* Menu:
X
X* Standard Functions::
X* Additional String Functions::
X* Expression Predicates::
X* Sorting Algorithms::
X* Standard Types::
X* Lambda Calculus::
X* List Comprehensions::
X* Streams::
X* Other Special Forms::
X* Mathematical Functions::
X* Graphics::
X* Lexicographic List Ordering::
X* Diagnostics and Error Messages::
X
X
XFile: qdoc.info,  Node: Standard Functions,  Next: Additional String Functions,  Prev: The Standard Library,  Up: The Standard Library
X
XStandard Functions
X==================
X
X   The `stdlib.q' script provides frequently used list operations and
Xother stuff mostly adopted from [Bird/Wadler 1988]. Here is a list of
Xthe operations provided by this module:
X
X`abs X'
X     absolute value of X
X
X`append Xs Y'
X     append a value `Y' to the list `Xs'
X
X`apply X Y'
X     apply function `X' to argument `Y'
X
X`applyq X Y'
X     quoted application
X
X`cat Xs'
X     concatenate a list of lists
X
X`compose X Y'
X     function composition: `compose X Y Z => X (Y Z)'
X
X`cons X Y'
X     construct a list node `[X|Y]'
X
X`consq X Y'
X     quoted list node
X
X`cst X'
X     constant-valued function: `cst X Y => X'
X
X`do F Xs'
X     apply a function `F' to each member of a list `Xs', return `()'
X
X`drop N Xs'
X     remove the first `N' elements from the list `Xs'
X
X`dropwhile P Xs'
X     remove elements from the beginning of `Xs' while the predicate `P'
X     is satisfied
X
X`each P Xs'
X     verify that each element of the list `Xs' satisfies the predicate
X     `P'
X
X`eq X Y'
X     syntactic equality (cf. *Note Non-Linear Equations and Syntactic
X     Equality::)
X
X`exist P Xs'
X     verify that the list `Xs' contains an element satisfying predicate
X     `P'
X
X`filter P Xs'
X     filter a list with a predicate
X
X`foldl F A Xs'
X     fold-left
X
X`foldl1 F Xs'
X     fold-left over nonempty lists
X
X`foldr F A Xs'
X     fold-right
X
X`foldr1 F Xs'
X     fold-right over nonempty lists
X
X`fst Xs'
X     return first element of a pair
X
X`genlist F P A'
X     generate the list of values `A', `F A', `F (F A)', ...  satisfying
X     a given predicate `P'
X
X`hd Xs'
X     return the first element of a list
X
X`id'
X     the identity function: `id X => X'
X
X`init Xs'
X     return list `Xs' without its last element
X
X`last Xs'
X     return the last element of a list
X
X`map F Xs'
X     apply function `F' to each member of a list
X
X`max X Y'
X     maximum of two values
X
X`min X Y'
X     minimum of two values
X
X`mklist X N'
X     create a list of `N' `X''s
X
X`neq X Y'
X     syntactic inequality
X
X`pair X Y'
X     construct a pair
X
X`pairq X Y'
X     quoted pair
X
X`pop Xs'
X     remove the first element from a list
X
X`prd Xs'
X     product of a list of numbers
X
X`push Xs X'
X     prepend an element to a list
X
X`range N M'
X     return a range of integers
X
X`repeat F P X'
X     repeat applying `F' to `X' (one or more times) until `P' is
X     satisfied
X
X`reverse Xs'
X     reverse a list
X
X`scan F A Xs'
X     apply `foldl' to every initial part of a list
X
X`scan1 F Xs'
X     apply `foldl1' to every nonempty initial part of a list
X
X`sgn X'
X     sign of a number
X
X`snd Xs'
X     return second element of a pair
X
X`sum Xs'
X     sum of a list of numbers
X
X`take N Xs'
X     select the first `N' elements from the list `Xs'
X
X`takewhile P Xs'
X     select elements from the beginning of `Xs' while the predicate `P'
X     is satisfied
X
X`tl Xs'
X     return the tail of a list
X
X`top Xs'
X     return the first element from a list
X
X`until P F X'
X     repeat applying `F' to `X' (zero or more times) until `P' is
X     satisfied
X
X`unzip Xs'
X     take a list of pairs into a pair of lists
X
X`value X'
X     return the value of a quoted expression
X
X`zip Xs'
X     take a pair of lists into a list of pairs of corresponding elements
X
X   Besides this, the `stdlib.q' script also overloads the `=' and `<>'
Xoperators with rules for deciding equality/inequality of lists, tuples
Xand truth values.
X
X
XFile: qdoc.info,  Node: Additional String Functions,  Next: Expression Predicates,  Prev: Standard Functions,  Up: The Standard Library
X
XAdditional String Functions
X===========================
X
X   The `string.q' script provides a collection of additional string
Xfunctions. Currently the following operations are implemented:
X
X`chars S'
X     return the list of individual characters in `S'
X
X`join DELIM Xs'
X     concatenate a list of strings, interpolating the given `DELIM'
X     string between each pair of consecutive strings in the list
X
X`split DELIM S'
X     split a string into a list of substrings delimited by characters
X     in the given `DELIM' string
X
X`strcat Xs'
SHAR_EOF
true || echo 'restore of q-1.7/qdoc.info failed'
fi
echo 'End of  part 12'
echo 'File q-1.7/qdoc.info is continued in part 13'
echo 13 > _shar_seq_.tmp
exit 0