axiom-databases 20120501-8 / usr / share / axiom-20120501 / algebra / gloss.text

,`{\em (syntax)} a separator for items in a \spadgloss{tuple}, e.g. to separate
arguments of a function \spad{f(x,y)}.

?`1. {\em (syntax)} a suffix character for Boolean-valued \spadfun{function} names, e.g. \spadfun{odd?}.
2. Suffix character for pattern variables.

3. The special type \spad{?} means {\em don't care}.
For example,
the declaration \newline\center{\spad{x : Polynomial ?}}\newline, 
means that values assigned to x must be polynomials over an
arbitrary \spadgloss{underlying domain}.

!`{\em (syntax)} Suffix character for \spadgloss{destructive operations}.

=>`{\em (syntax)} the expression \spad{a => b} is equivalent to \spad{if a then}
\spadgloss{exit} \spad{b}.

abstract datatype`
a programming language principle used in \Language{}
where a datatype is defined in two parts:
(1) a {\em public} part describing a set of \spadgloss{exports}, principally
operations that apply to objects of that type, and
(2) a {\em private} part describing the implementation
of the datatype usually in terms of a \spadgloss{representation} for 
objects of the type. 
Programs which create and otherwise manipulate objects of the type
may only do so through its exports.
The representation and other implementation information is
specifically hidden.

abstraction`described functionally or conceptually without regard to implementation

accuracy`the degree of exactness of an approximation or measurement. In
computer algebra systems, computations are typically carried out
with complete accuracy using integers or rational numbers of 
indefinite size. Domain \spadtype{Float} provides a function
\spadfunFrom{precision}{Float} to change the precision for 
floating point computations. Computations using \spadtype{DoubleFloat}
have a fixed precision but uncertain accuracy.

algorithm`a step-by-step procedure for a solution of a problem; a program

application`{\em (syntax)} an expression denoting "application" of 
a function to 
a set of \spadgloss{argument} parameters. 
Applications are written as
a \spadgloss{parameterized form}.
For example, the form \spad{f(x,y)} indicates
the "application of the function \spad{f} to the tuple of arguments \spad{x}
and \spad{y}".
See also \spadgloss{evaluation} and \spadgloss{invocation}.

apply`See \spadgloss{application}.

argument`1. (actual argument) a value passed to a function at the 
time of a \spadglossSee{function call}{application}; also called an {\em actual
parameter}.
2. (formal argument) a variable used in the definition of a function
to denote the actual argument passed when the function is called.

assignment`{\em (syntax)} an expression of the form \spad{x := e}, 
meaning "assign the value of \spad{e} to x".
After \spadgloss{evaluation}, the \spadgloss{variable} x \spadglossSee{points}{pointer} 
to an object obtained by evaluating the expression \spad{e}.
If x has a \spadgloss{type} as a result of a previous \spadgloss{declaration},
the object assigned to x must have that type.
An interpreter must often \spadglossSee{coerce}{coercion}
the value of e to make that happen.
For example, in the interpreter,
\center{\spad{x : Float := 11}}
first \spadglossSee{declares}{declaration} x to be a float.
This declaration causes the interpreter to coerce 11 to 11.0 in order
to assign a floating point value to x.

attribute`a name or functional form denoting {\em any} useful
computational property.
For example, \spadatt{commutative("*")} asserts that 
"\spadfun{*} is commutative".
Also, \spadatt{finiteAggregate} is used to assert that
an aggregate has a finite number of immediate components.

basis`{\em (algebra)} \spad{S} is a basis of a module \spad{M} over a \spadgloss{ring} if
\spad{S} generates \spad{M}, and \spad{S} is linearly independent

block`{\em (syntax)}
a control structure where expressions are 
sequentially \spadglossSee{evaluated}{evaluation}.

body`a \spadgloss{function body} or \spadgloss{loop body}.

boolean`objects denoted by the \spadgloss{literals} \spad{true} and \spad{false};
elements of domain \spadtype{Boolean}.
See also \spadtype{Bits}.

built-in function`a \spadgloss{function} in the standard \Language{} 
library. Contrast \spadgloss{user function}.

cache`1. (noun) a mechanism for immediate retrieval of previously
computed data. For example, a function
which does a lengthy computation might store its
values in a \spadgloss{hash table} using argument as a key.
The hash table then serves as a cache for the function
(see also \spadsyscom{)set function cache}). 
Also, when \spadgloss{recurrence relations} which depend upon
n previous values are compiled,
the previous n values are normally cached
(use \spadsyscom{)set functions recurrence} to change this).
2. (verb) to save values in a cache.

capsule`the part of the \spadglossSee{body}{function body} 
of a \spadgloss{domain constructor} that defines the
functions implemented by the constructor.

case`{\em (syntax)} an operator used to conditionally evaluate 
code based on the branch of a \spadgloss{Union}.
For example, if value u is \spad{Union(Integer,"failed")},
the conditional expression \spad{if u case Integer then A else B}
evaluate \spad{A} if u is an integer and \spad{B} otherwise.

character`1. an element of a character set, as represented
by a keyboard key.
2. a component of a string. 
For example, the 0th element of the string \spad{"hello there"} is
the character {\em h}.


comment`textual remarks imbedded in code.
Comments are preceded by a double dash ({\em --}).
For \Language{} library code, stylized comments for on-line documentation 
are preceded by a two plus signs ({\em ++}).

compiler`a program that generates low-level code from a higher-level source
language. \Language{} has three compilers. A {\em graphics compiler} converts
graphical formulas to a compiled subroutine so that points
can be rapidly produced for graphics commands.
An {\em interpreter compiler} optionally compiles \spadgloss{user functions}
when first \spadglossSee{invoked}{invocation} (use \spadsyscom{)set functions compile} to turn
this feature on).
A {\em library compiler} compiles all constructors (not available in Release 1)

computational object`
In \Language{}, domains are objects.
This term is used to distinquish the objects which
are members of domains rather than domains themselves.

constructor`a \spadgloss{function} which creates a \spadgloss{category}, 
\spadgloss{domain}, or \spadgloss{package}.

continuation`
when a line of a program is so long that it must be broken into
several lines, then all but the first line are called {\em continuation lines}.
If such a line is given interactively, then each incomplete line must
end with an underscore.

conditional`a \spadgloss{control structure} of the form \spad{if A then B else C};
The \spadgloss{evaluation} of \spad{A} produces \spad{true} or 
\spad{false}. If \spad{true}, \spad{B} evaluates to produce a value;
otherwise \spad{C} evaluates to produce a value.
When the value is not used, \spad{else C} part can be omitted.

constant`{\em (syntax)} a reserved word used in \spadgloss{signatures} in
\Language{} programming language to signify 
that mark an operation always returns 
the same value. For example, the signature \spad{0: constant -> $} in
the source code of \spadtype{AbelianMonoid} tells the \Language{}
compiler that \spad{0} is a constant so that suitable optimizations
might be performed.

control structure`program structures 
which can specify a departure from normal sequential execution.
\Language{} has four kinds of control structures: 
\spadgloss{blocks}, \spadgloss{case} statements,
\spadgloss{conditionals}, and \spadgloss{loops}.

copying semantics`the programming language semantics used in
Pascal but {\em not} in \Language{}. See also \spadgloss{pointer semantics} 
for details.

data structure`a structure for storing data in the computer. Examples are
\spadgloss{lists} and \spadgloss{hash tables}.

datatype`equivalent to \spadgloss{domain} in \Language{}.

delimiter`a \spadgloss{character} which marks the beginning or end of some syntactically
correct unit in the language, e.g. \spadSyntax{"} for strings, blanks for 
identifiers.

documentation`
1. on-line or hard copy descriptions of \Language{};
2. text in library code preceded by {\em ++} comments as opposed to general
comments preceded by {\em --}.

empty`the unique value of objects with type \spadtype{Void}.

environment`a set of \spadgloss{bindings}.

evaluation`a systematic process which transforms an \spadgloss{expression} into
an object called the \spadgloss{value} of the expression.
Evaluation may produce \spadgloss{side effects}.

exit`{\em (reserved word)} an \spadgloss{operator} which forces an exit 
from the current block.
For example, the \spadgloss{block} \spad{(a := 1; if i > 0 then exit a; a := 2)}
will prematurely exit at the second statement with value 1 if the value of i is
greater than 0. See \spadgloss{=>} for an alternate syntax.

expose`
some constructors are {\em exposed}, others {\em unexposed}.
Exposed domains and packages are recognized 
by the interpreter.
Use \spadsys{)set expose} to control change what is exposed.
To see both exposed and unexposed constructors,
use \Browse{} with give the 
system command \spadsyscom{)set hyperdoc browse exposure on}.
Unexposed constructors will now appear prefixed by star(\spad{*}).

expression`1. any syntactically correct program fragment.
2. an element of domain \spadtype{Expression}

extend`see \spadgloss{category extension} or \spadgloss{domain extension}

field`{\em (algebra)}
a \spadgloss{domain} which is \spadgloss{ring} where every non-zero
element is invertible and where \spad{xy=yx};
a member of category \spadtype{Field}.
For a complete list of fields, click on {\em Domains} under {\em Cross Reference}
for \spadtype{Field}.

file`a program or collection of data stored on disk, tape or other
medium.

float`a floating-point number with user-specified precision;
an element of domain \spadtype{Float}.
Floats are \spadgloss{literals} which are written two ways: without an exponent
(e.g. \spad{3.1416}), or with an exponent
(e.g. \spad{3.12E-12}).
Use function \spadgloss{precision} to change the precision of
the mantissage (20 digits by default). See also \spadgloss{small float}.

formal parameter`(of a function) an identifier 
\spadglossSee{bound}{binding} to 
the value of an actual \spadgloss{argument} on \spadgloss{invocation}.
In the function definition \spad{f(x,y) == u}, for example,
x and y are the formal parameter.

frame`
the basic unit of an interactive session;
each frame has its own \spadgloss{step number}, \spadgloss{environment},
and \spadgloss{history}. In one interactive session, users can 
can create and drop frames, and have several active frames simultaneously.

function`
implementation of \spadgloss{operation}; it
takes zero or more \spadgloss{argument} parameters
and produces zero or more values.
Functions are objects which can be passed as parameters
to functions and can be returned as values of functions.
Functions can also create other functions (see also \spadtype{InputForm}).
See also \spadgloss{application} and \spadgloss{invocation}.

The terms {\em operation} and {\em function} are
distinct notions in \Language{}.
An operation is an abstraction of a function, described
by declaring a \spadgloss{signature}.
A function is created by providing an implementation of that
operation by some piece of \Language{} code.
Consider the example of defining
a user-function \spad{fact} to compute the \spadfun{factorial} of
a nonnegative integer. 
The \Language{} statement \spad{fact: Integer -> Integer}
describes the operation, whereas the
statement \spad{fact(n) = reduce(*,[1..n])}
defines the functions.
See also \spadgloss{generic function}.

function body`the part of a \spadgloss{function}'s definition which
is evaluated when the function is called at \spadgloss{run-time};
the part of the function definition to the right of the \spadSyntax{==}.

garbage collection`a system function that automatically recycles memory
cells from the \spadgloss{heap}.
\Language{} is built upon \spadgloss{Common LISP} which provides this
facility.

generic function`the use of one function to operate on
objects of different types;
One might regard \Language{} as supporting generic 
\spadgloss{operations} but not generic functions.
One operation
\spad{+: (D,D) -> D} exists
for adding elements in a ring; each ring however provides its own
type-specific function for implementing this operation.

Gaussian`a complex-valued expression, e.g. one with both a real and 
imaginary part;
a member of a \spadtype{Complex} domain.

Groebner basis`{\em (algebra)} a special basis for a polynomial ideal that allows a simple
test for membership. It is useful in solving systems of polynomial
equations.

group`{\em (algebra)} a monoid where every element has a multiplicative inverse.

history`a mechanism which records the results for an interactive 
computation.
Using the history facility, users
can save computations, review previous steps of a computation,
and restore a previous interactive session at some later time.
For details, issue the system command {\em )history ?} to the
interpreter.
See also \spadgloss{frame}.

ideal`{\em (algebra)} a subset of a ring that is closed under addition and 
multiplication by arbitrary ring elements, i.e. it's a module over the ring.

identifier`{\em (syntax)} an \Language{} name; 
a \spadgloss{literal} of type \spadtype{Symbol}.
An identifier begins with an alphabetical character or %
and may be followed by alphabetic characters, digits, ? or !.
Certain distinquished \spadgloss{reserved words} are not allowed as identifiers
but have special meaning in the \Language{}.

immutable`an object is immutable if it cannot be changed by an \spadgloss{operation};
not a \spadglossSee{mutable object}{mutable}.
Algebraic objects generally immutable:
changing an algebraic expression involves copying parts of
the original object.
One exception is a matrix object of type \spadtype{Matrix}.
Examples of mutable objects are data structures such as those of 
type \spadtype{List}.
See also \spadgloss{pointer semantics}.

index`1. a variable that counts the number of times a \spadgloss{loop} is repeated.  
2. the "address" of an element in a data structure (see also category \spadtype{LinearAggregate}).

instantiate`to build a \spadgloss{category}, \spadgloss{domain}, or \spadgloss{package}
at run-time

interactive`a system where the user interacts with the computer
step-by-step

integer`a \spadgloss{literal} object of domain \spadtype{Integer}, the class of
integers with an unbounded number of digits.
Integer literals consist of one or more consecutive digits (0-9)
with no embedded blanks.
Underscores can be used to separate digits in long integers if desirable.

interpreter`
the subsysystem of \Language{} responsible for handling user
input during an interactive session.
The following somewhat simplified description of the
typical action of the interpreter.
The interpreter 
parsers the user's input expression to
create an expression tree then does a 
bottom-up traversal of the tree.
Each subtree encountered which is not a value consists of a root node
denoting an operation name and one or more leaf nodes denoting 
\spadgloss{operands}.
The interpreter resolves type mismatches and
uses type-inferencing and a library database
to determine appropriate types of the operands and
the result, and an operation to be performed.
The interpreter then builds
a domain to perform the indicated operation, then
invokes a function from the domain to compute a value.
The subtree is then replaced by that value and the process
continues.
Once the entire tree has been processed, the value
replacing the top node of the tree is displayed
back to the user as the value of the expression.

iteration`
repeated evaluation of an expression or a sequence of expressions.
Iterations use the reserved words
\spadSyntax{for}, \spadSyntax{while}, and \spadSyntax{repeat}.

Join`a primitive \Language{} function taking two or more categories
as arguments and producing a category containing all of the
operations and attributes from the respective categories.

library`
In \Language{}, a
coolection of compiled modules
respresenting the
a \spadgloss{category} or \spadgloss{domain} constructor.

list`an object of a \spadtype{List} domain.

loop`1. an expression containing a \spadSyntax{repeat}
2. a collection expression having a \spadSyntax{for} or a \spadSyntax{while},
e.g. \spad{[f(i) for i in S]}.

loop body`the part of a loop following the \spadSyntax{repeat} that
tells what to do each iteration.
For example, the body of the loop \spad{for x in S repeat B} is B. 
For a collection expression, the body of the loop precedes the
initial \spadSyntax{for} or \spadSyntax{while}.

literal`an object with a special syntax in the language.
In \Language{}, there are five types of literals:
\spadgloss{booleans},
\spadgloss{integers},
\spadgloss{floats},
\spadgloss{strings},
and \spadgloss{symbols}.

mode`a type expression containing a question-mark ({\em ?}).
For example, the mode {\em P ?} designates 
{\em the class of all polynomials over an arbitrary ring}.

mutable`
objects which contain \spadgloss{pointers} to other objects and which have 
operations defined on them which
alter these pointers. Contrast \spadgloss{immutable}.
\Language{} uses \spadgloss{pointer semantics} as does \spadgloss{LISP}
in contrast with many other languages such as Pascal which use
\spadgloss{copying semantics}.
See \spadgloss{pointer semantics} for details.

name`
1. a \spadgloss{symbol} denoting a \spadgloss{variable}, 
i.e. the variable \spad{x}.
2. a \spadgloss{symbol} denoting an \spadgloss{operation},
i.e. the operation \spad{divide: (Integer,Integer) -> Integer}.

nullary`a function with no arguments, e.g. \spadfun{characteristic}.
 
quote`the prefix \spadgloss{operator} \spadSyntax{'} meaning 
{\em do not evaluate}.

Object`a category with no operations or attributes, from which
most categories in \Language{} are \spadglossSee{extensions}{category extension}.

object`a data entity created or manipulated by programs.
Elements of domains, functions, and domains themselves
are objects. Whereas categories are created by functions,
they cannot be dynamically manipulated in the current system and
are thus not considered as objects.
The most basic objects are \spadgloss{literals}; all other
objects must be created \spadgloss{functions}.
Objects can refer to other objects using \spadgloss{pointers}.
\Language{} language uses \spadgloss{pointer semantics} when dealing
with \spadgloss{mutable} objects.

object code`code which can be directly executed by hardware;
also known as {\em machine language}.

operand`an argument of an \spadgloss{operator}
(regarding an operator as a \spadgloss{function}).

operation`
an abstraction of a \spadgloss{function},
described by a \spadgloss{signature}. 
For example,
\center{\spad{fact: NonNegativeInteger -> NonNegativeInteger}}
describes an operation for "the factorial of a
(non-negative) integer".

operator`special reserved words in the language such as \spadop{+} and 
\spadop{*}; operators can be either \spadgloss{prefix}
or \spadgloss{infix} and have a relative \spadgloss{precedence}.

overloading`the use of the same name to denote
distinct functions;
a function is identified by a \spadgloss{signature} identifying its
name, the number and types of its arguments, and its return types.
If two functions can have identical signatures,
a \spadgloss{package call} must be made to distinquish the two.

package call`{\em (syntax)} an expression of the form \spad{f(x,y)$D} used to identify
that the function f is to be one from D.

package`
a domain whose exported operations depend solely
on the parameters and other explicit domains, e.g.
a package for solving systems of equations of polynomials over
any field, e.g. floats, rational numbers, complex rational functions,
or power series. 
Facilities for integration, differential equations,
solution of linear or polynomial equations, and group theory
are provided by "packages".

Technically, a package is a domain 
which has no \spadgloss{signature} containing 
the symbol $. While domains intuitively 
provide computational objects you can compute with,
packages intuitively provide 
functions (\spadgloss{polymorphic} functions) which will work
over a variety of datatypes. 

package constructor`same as \spadgloss{domain constructor}.

package call`{\em (syntax)} an expression of the form \spad{e $ D}
where \spad{e} is an \spadgloss{application} and \spad{D}
denotes some \spadgloss{package} (or \spadgloss{domain}).

parameter`see \spadgloss{argument}

pile`alternate syntax for a block, using indentation and column alignment
(see also \spadgloss{block}).

parameterized datatype`a domain that is built on another, for example,
polynomials with integer coefficients.

partially ordered set`a set with a reflexive, transitive and antisymetric
\spadgloss{binary} operation.

parse`1. (verb) to produce an internal representation 
of a user input string;
the resultant internal representation is then "interpreted"
by \Language{} to perform some indicated action.

parameterized form`a expression of the form \spad{f(x,y)},
an \spadgloss{application} of a function.

postfix`an \spadgloss{operator} that follows its single \spadgloss{operand}.
Postfix operators are not available in \Language{}.

pointer`a reference implemented by a link directed from one object to another 
in the computer memory.
An object is said to {\em refer} to another if it has a pointer to
that other object.
Objects can also refer to themselves (cyclic references are legal).
Also more than one object can refer to the same object.
See also \spadgloss{pointer semantics}.

reference`see \spadgloss{pointer}

pointer semantics`the programming language semantics used in
languages such as LISP which allow objects to be \spadgloss{mutable}.

Consider the following sequence of \Language{} statements:\begin{items}
\item \spad{x : Vector Integer := [1,4,7]}
\item \spad{y := x}
\item \spad{swap!(x,2,3)}    
\end{items}
The function \spadfunFrom{swap!}{Vector} is used to interchange the
2nd and 3rd value in the list x producing the value \spad{[1,7,4]}.
What value does y have after evaluation of the third statement?
The answer is different in \Language{} than it is in a language
with \spadgloss{copying semantics}.

In \Language{}, first the vector [1,2,3] is created and the variable
x set to \spadglossSee{point}{pointer} to this object. Let's call this object V.
Now V refers to its \spadgloss{immutable} components 1,2, and 3.
Next, the variable y is made to point to V just as x does.
Now the third statement interchanges the last 2 elements of V
(the {\em !} at the end of the name \spadfunFrom{swap!}{Vector} tells 
you that this operation is destructive, that is, it changes
the elements {\em in place}). Both x and y perceive this change to V.
Thus both x and y then have the value \spad{[1,7,4]}. 

In Pascal, the second statement causes a copy of V to be stored
under y. Thus the change to V made by the third statement does
not affect y.

precision`the number of digits in the specification of a number, e.g.
as set by \spadfunFrom{precision}{Float}.

predicate`
1. a Boolean valued function, e.g. \spad{odd: Integer -> Boolean}.
2. an Boolean valued expression 

Rep`a special identifier
used as \spadgloss{local variable} of a domain constructor body
to denote the representation domain for
objects of a domain.

recurrence relation`
A relation which can be expressed
as a function f with some argument n
which depends on the value of f at k previous values.
In many cases, \Language{} will rewrite a recurrence relation
on compilation so as to \spadgloss{cache} its previous k values
and therefore make the computation significantly more efficient.

recursive`
1. A function that calls itself, either directly or indirectly
through another function.
2. self-referential. See also \spadgloss{recursive}.

recursion`use of a self-reference within the body of a function. Indirect
recursion is when a function uses a function below it in the call chain.

reserved word`a special sequence of non-blank characters with
special meaning in the \Language{} language.
Examples of reserved words are names such as
\spadSyntax{for}, \spadSyntax{if}, and \spadSyntax{free}, operator
names such as \spadSyntax{+} and \spad{mod},
special character strings such as spadSyntax{==} and spadSyntax{:=}.

retraction`to move an object in a parameterized domain back to the
underlying domain, 
for example to move the object \spad{7} from a "fraction of integers"
(domain \spadtype{Fraction Integer})
to "the integers" (domain \spadtype{Integer}).

return`when leaving a function, the value of the expression following
\spadSyntax{return} becomes the value of the function.

ring`a set with a commutative addition, associative multiplication, a unit
element, and multiplication distributes over addition and subtraction.

run-time check`an error-checking which can be done only when the program
receives user input; for example, confirming that a value is in the proper
range for a computation.


semantics`the relationships between symbols and their meanings. The rules
for obtaining the {\em meaning} of any syntactically valid expression.

semigroup`{\em (algebra)} a \spadgloss{monoid} which need not have an identity; it is closed and
associative.

side effect`
action which changes a component or structure of a value.
See \spadgloss{destructive operation} for details.

destructive operation`
An operation which changes a component or structure of a value.
In \Language{}, all destructive operations have
names which end with an exclamation mark ({\em !}).
For example, domain \spadtype{List} has two operations to reverse
the elements of a list, one named \spadfunFrom{reverse}{List}
which returns a copy of the original list with the elements
reversed, another named
\spadfunFrom{reverse!}{List} which reverses the elements {\em in place}
thus destructively changing the original list.

signature`{\em (syntax)} an expression describing an \spadgloss{operation}.
A signature has the form
as \spad{name : source -> target}, where
\spad{source} gives the type of the arguments of the operation,
and \spad{target} gives the type of the result.

small float`the domain for hardware floating point arithmetic 
as provided by the computer hardware.

small integer`the domain for hardware integer arithmetic.
as provided by the computer hardware.

source`the \spadgloss{type} of the argument of a \spadgloss{function};
the type expression before the \spad{->} in a \spadgloss{signature}.
For example, the source of \spad{f : (Integer,Integer) -> Integer}
is \spad{(Integer,Integer)}.

target`the \spadgloss{type} of the result of a \spadgloss{function};
the type expression following the \spad{->} in a \spadgloss{signature}.

sparse`data structure whose elements are mostly identical (a sparse matrix
is one filled with mostly zeroes).

step number`the number which precedes user input lines in an
interactive session; the output of user results is also labeled by this number.

stream`an object of \spadtype{Stream(R)}, a generalization of a \spadgloss{list} to allow 
an infinite number of elements.
Elements of a stream are computed "on demand".
Strings are used to implement various forms of power series (\ignore{???}).

string`an object of domain \spadtype{String}.
Strings are \spadgloss{literals} consisting of
an arbitrary sequence of \spadgloss{characters} surrounded by
double-quotes (\spadSyntax{"}), 
e.g. \spad{"Look here!"}.

such that clause`the use of \spadSyntax{|} followed by an expression to filter
an iteration.

syntax`rules of grammar, punctuation etc. for forming correct expressions.

symbol`objects denoted by \spadgloss{identifier} \spadgloss{literals};
an element of domain \spadtype{Symbol}.
The interpreter defaultly converts a symbol x into \spadtype{Variable(x)}.

system commands`top-level \Language{} statements that begin with 
{\em )}. System commands allow users to query the database, 
read files, trace functions, and so on.

top-level`
refers to direct user interactions with the \Language{} interpreter.

totally ordered set`{\em (algebra)} a partially ordered set where any two elements are
comparable.

trace`use of system function \spadsys{)trace} to
track the arguments passed to a function and the values returned.

tuple`an expression of two or more other expressions separated by commas,
e.g. \spad{4,7,11}. 
Tuples are also used for multiple arguments 
both for \spadgloss{applications} (e.g. \spad{f(x,y)}) 
and in \spadgloss{signatures} (e.g. \spad{(Integer,Integer) -> Integer}).
A tuple is not a data structure,
rather a syntax mechanism for grouping expressions.

type checking`a system function which determines whether the datatype of an
object is appropriate for a given operation.

type inference`when the interpreter chooses the type for an object based on
context. 
For example, if the user interactively issues the 
definition \center{\spad{f(x) == (x + %i)**2}}
then issues \spad{f(2)}, the interpreter will infer
the type of f to be \spad{Integer -> Complex Integer}.

underlying domain`for a \spadgloss{domain} that has a single
domain-valued parameter, the {\em underlying domain} refers to that
parameter. 
For example, the domain "matrices of integers" (\spadtype{Matrix Integer})
has underlying domain \spadtype{Integer}.




unit`{\em (algebra)} an invertible element. 

user function`a function defined by a user during an interactive session.
Contrast \spadgloss{built-in function}.

value`
1. the result of \spadglossSee{evaluating}{evaluation} an expression.
2. a property associated with a \spadgloss{variable} in a \spadgloss{binding}
in an \spadgloss{environment}.

user variable`a variable created by the user at top-level during an interactive
session

Void`the type given when the \spadgloss{value} and \spadgloss{type}
of an expression are not needed.  Also used when there is no guarantee
at run-time that a value and predictable mode will result.

workspace`an interactive record of the user input and output held in an
interactive history file.
Each user input and corresponding output expression in the
workspace has a corresponding \spadgloss{step number}.
The current output expression in the workspace is referred
to as \spad{\%}.
The output expression associated with 
step number n is referred to by \spad{\%\%(n)}.
The k-th previous output expression relative to the current step number n
is referred to by \spad{\%\%(- k)}.
Each interactive \spadgloss{frame} has its own workspace.

dot notation`using an infix dot ({\em .}) for function application.  If u is
the list \spad{[7,4,-11]} then both \spad{u(2)} and \spad{u.2} return 4.
Dot notation nests to left. Thus \spad{f . g . h} is equivalent to
\spad{(f . g) . h}.

domain`{\em (basic concept)}
a domain corresponds to the usual notion of abstract datatypes: that of
a set of values and a set of "exported operations" for
the creation and manipulation of these values.
Datatypes are parameterized, dynamically constructed, and can combine
with others in any meaningful way, e.g. 
"lists of floats" (\spadtype{List Float}),
"fractions of polynomials with integer coefficients" 
(\spadtype{Fraction Polynomial Integer}),
"matrices of infinite \spadgloss{streams} of cardinal numbers"
(\spadtype{Matrix Stream CardinalNumber}).

The term {\em domain} is actually 
abbreviates {\em domain of computation}.
Technically, a domain denotes a class of objects,
a class of \spadgloss{operations} for creating and other manipulating
these objects, and a class of \spadgloss{attributes} describing
computationally useful properties.
Domains also provide \spadgloss{functions} for each operation often 
in terms of some \spadgloss{representation} for the objects.
A domain itself is an \spadgloss{object} 
created by a \spadgloss{function} called a \spadgloss{domain constructor}.

domain constructor`a function that creates domains,
described by an abstract datatype in the \Language{} programming language.
Simple domains like \spadtype{Integer} and \spadtype{Boolean}
are created by domain constructors with no arguments.
Most domain constructors take
one or more parameters, one usually denoting an
\spadgloss{underlying domain}. 
For example, the domain \spadtype{Matrix(R)} denotes
"matrices over R". 
Domains {\em Mapping}, {\em Record}, and {\em Union} are
primitive domains.
All other domains are written in the \Language{} programming language
and can be modified by users with access to the library source code.

domain extension`a domain constructor \spad{A} is said to 
{\em extend} a domain constructor \spad{B} if \spad{A}'s
definition has the form \spad{A == B add ...}.
This intuitively means "functions 
not defined by \spad{A} are assumed to come from \spad{B}".
Successive domain extensions form \spadgloss{add-chains} affecting the
the \spadglossSee{search order}{lineage} for functions not implemented
directly by the domain during \spadgloss{dynamic lookup}.

add-chain`a hierarchy formed by \spadgloss{domain extensions}.
If domain \spad{A} extends domain \spad{B} and 
domain \spad{B} extends domain \spad{C},
then \spad{A} has {\em add-chain} \spad{B}-\spad{C}.

category hierarchy`hierarchy formed by category extensions.
The root category is \spadtype{Object}. 
A category can be defined as a \spadgloss{Join} of two or more categories so
as to have multiple \spadgloss{parents}. Categories may also have parameterized so as
to allow conditional inheritance.

default package`a optional \spadgloss{package} of \spadgloss{functions} 
associated with a category. Such functions are necessarily defined in terms
over other functions exported by the category.

category`{\em (basic concept)}
second-order types which serve to
define useful "classification worlds" for domains, such as
algebraic constructs (e.g. groups, rings, fields), and
data structures (e.g. homogeneous aggregates, collections, dictionaries).
Examples of categories are 
\spadtype{Ring} ("the class of all rings") and
\spadtype{Aggregate} ("the class of all aggregates").
The categories of a given world are arranged in a hierarchy
(formally, a directed acyclic
graph). Each category inherits the properties of all its ancestors.
Thus, for example, the category of ordered rings (\spadtype{OrderedRing})
inherits the properties of the category of rings (\spadtype{Ring}) 
and those of the ordered sets (\spadtype{OrderedSet}).
Categories provide a database of algebraic knowledge and
ensure mathematical correctness, e.g. that
"matrices of polynomials" is correct but
"polynomials of hash tables" is not, that the multiply operation
for "polynomials of continued fractions" is commutative,
but that for "matrices of power series" is not.
optionally provide "default definitions" for operations they export.

Categories are defined in \Language{}
by functions called \spadgloss{category constructors}.
Technically, a category designates a class of domains with common
\spadgloss{operations} and \spadgloss{attributes} but usually with
different \spadgloss{functions} and \spadgloss{representations} for its
constituent \spadgloss{objects}. 
Categories are always defined using the \Language{} library language
(see also \spadgloss{category extension}). See also file {\em catdef.spad} for 
definitions of basic algebraic categories in \Language{}.

Category`the distinguished object denoting the type of a category; the
class of all categories.

category constructor`a function that creates categories,
described by an abstract datatype in the \Language{} programming language. 
For example, the
category constructor \spadtype{Module} is a function which takes a domain
parameter \spad{R} and creates the category "modules over \spad{R}".

category extension`created by a category definition, an expression
usually of the form \spad{A == B with ...}.
In English, this means "category A is a B with the new operations
and attributes as given by ... .
See, for example, file {\em catdef.spad} for a definitions of the
algebra categories in \Language{}, {\em aggcat.spad} for data structure
categories. 

coercion`an automatic transformation of an object of one \spadgloss{type}
to an object of a similar or desired target type.
In the interpreter, coercions and
\spadgloss{retractions} are done automatically by the interpreter
when a type mismatch occurs.
Compare \spadgloss{conversion}.

conversion`the transformation of an object on one \spadgloss{type}
to one of another type.
Conversions performed automatically are called \spadgloss{coercions}.
These happen when the interpreter has a type mismatch and
a similar or declared target type is needed.
In general, the user must use the infix operation \spadSyntax{::}
to cause this transformation.

polymorphic`
a \spadgloss{function} parameterized by one or more \spadgloss{domains};
a \spadgloss{algorithm} defined \spadglossSee{categorically}{category}.
Every function defined in a domain or package constructor
with a domain-valued parameter is polymorphic.
For example, the same matrix \spadSyntax{*} function is used to multiply
"matrices over integers" as "matrices over matrices over integers"
Likewise, various \ignore{???} in \ignore{???} solves polynomial equations
over any \spadgloss{field}.

representation`
a \spadgloss{domain} providing a data structure 
for elements of a domain;
generally denoted by the special identifier \spadgloss{Rep}
in the \Language{} programming language.
As domains are \spadgloss{abstract datatypes}, this
representation is not available to users of the domain,
only to functions defined in the \spadgloss{function body}
for a domain constructor.
Any domain can be used as a representation.

type constructor`a \spadgloss{domain constructor} or \spadgloss{category constructor}.

search string`a string entered into an \spadgloss{input area} on a
\HyperName{} screen

input area`a rectangular area on a \HyperName{} screen into which users can
enter text.

wild card`a symbol which matches any substring including the empty string;
for example, the search string {\em *an*} matches 
an word containing the consecutive letters {\em a} and {\em n}

ancestor`(of a domain) 
a category which is a \spadgloss{parent} of the domain, or
a \spadgloss{parent} of a \spadgloss{parent}, and so on.

parent`(of a domain)
a category which is explicitly declared in the source
code definition for the domain to be an \spadgloss{export} of the domain.

benefactor`(of a given domain)
a domain or package that the given domain explicitly references
(for example, calls functions from)
in its implementation 

client`(of a given domain)
any domain or package that explicitly calls functions from the given domain

default definition`
a function defined by a \spadgloss{category}.
Such definitions appear category definitions 
of the form \spad{C: Category == T add I} in 
an optional implmentation part \spad{I} to the right of the
keyword \spad{add}.

aggregate`a data structure designed to hold multiple values.
Examples of aggregates are \spadtype{List}, 
\spadtype{Set}, \spadtype{Matrix} and \spadtype{Bits}.

hash table`
A data structure that efficiency maps a given object to another.
A hash table consists of a set of {\em entries},
each of which associates a {\em key} with a {\em value}.
Finding the object stored under a key can be very fast even if 
there are a large number of entries since keys are {\em hashed}
into numerical codes for fast lookup.


dynamic`that which is done at \spadgloss{run-time} 
as opposed to \spadgloss{compile-time}.
For example, the interpreter will build the domain
"matrices over integers" dynamically in response to user input.
However, the compilation of all functions for matrices and integers
is done during \spadgloss{compile-time}.
Constrast \spadgloss{static}.

run-time`the time of doing a computation.
Contrast \spadgloss{compile-time}.
rather than prior to it; \spadgloss{dynamic} as opposed to \spadgloss{static}.
For example, the decision of the intepreter to build 
a structure such as "matrices with power
series entries" in response to user input is made 
at run-time.

compile-time`the time when category or domain constructors are
compiled. Contrast \spadgloss{run-time}.

static`that computation done before run-time,
such as compilation. 
Contrast \spadgloss{dynamic}.

variable`a means of 
referring to an object but itself 
{\bf not} an object.
A variable has a name and an associated \spadgloss{binding}
created by \spadgloss{evaluation} of \Language{} expressions
such as \spadgloss{declarations}, \spadgloss{assignments}, and \spadgloss{definitions}.
In the top-level \spadgloss{environment} of the interpreter,
variables are \spadgloss{global variables}. 
Such variables can be freely referenced
in user-defined functions although a \spadgloss{free} declaration
is needed to assign values to them.
See \spadgloss{local variable} for details.

local variable`(of a function) a variable \spadglossSee{bound}{binding} 
by that function and such that its binding
is invisible to any function that function calls.
Also called a {\em lexical} variable.
By default in the interpreter:\begin{items}
\item 1. any variable x which appears on the
left hand side of an assignment is regarded 
a local variable of that function.
If the intention of an assignment
is to change the value of a \spadgloss{global variable} x,
the body of the function must then contain the statement \spad{free x}.
\item 2. any other variable is regarded as a \spadgloss{free variable}.
\end{items}
An optional declaration \spad{local x} is available to
explicitly declare a variable to be a local variable.
All \spadgloss{formal parameters} to the function can be
regarded as local variables to the function.

local`{\em (syntax)} A keyword used in user-defined functions to declare
that a variable is a \spadgloss{local variable} of that function.
Because of default assumptions on variables, such a 
declaration is not necessary but is available to the user for clarity
when appropriate.

free`{\em (syntax)} A keyword used in user-defined functions to declare
that a variable is a \spadgloss{free variable} of that function.
For example, the statement \spad{free x} declares
the variable x within the body of a function f
to be a free variable in f.
Without such a declaration, any variable x which appears on the 
left hand side of an assignment is regarded as
a \spadgloss{local variable} of that function.
If the intention of the assignment 
is to give an value to a \spadgloss{global variable} x,
the body of that function must contain the statement \spad{free x}.

free variable`(of a function) a variable which appears in a 
body of a function but is not \spadglossSee{bound}{binding} by that function.
See \spadgloss{local variable} by default.

binding`the association of a variable with properties such as \spadgloss{value} and
\spadgloss{type}.
The top-level \spadgloss{environment} in the interpreter
consists of bindings for all user variables and functions.
Every \spadgloss{function} has an associated set of bindings,
one for each formal \spadgloss{argument} and \spadgloss{local variable}.

global variable`A variable which can be 
referenced freely by functions.
In \Language{}, all top-level user-defined variables 
defined during an interactive user session are global variables.
\Language{} does not allow {\em fluid variables},
that is, variables \spadglossSee{bound}{binding} by functions which can be
referenced by functions those functions call.

precedence`{\em (syntax)}
refers to the so-called {\em binding power} of an operator.
For example, \spad{*} has higher binding power than \spad{+}
so that the expression \spad{a + b * c} is equivalent
to \spad{a + (b * c)}.

suffix`{\em (syntax)} an \spadgloss{operator} which placed after
its operand. 
Suffix operators are not allowed in the \Language{} language.

invocation`(of a function) the run-time process involved
in \spadglossSee{evaluating}{evaluation} a
a \spadgloss{function} \spadgloss{application}.
This process has two steps.
First, a local \spadgloss{environment} is created where 
\spadgloss{formal arguments} are locally \spadglossSee{bound}{binding}
by \spadgloss{assignment} to their respective 
actual \spadgloss{argument}.
Second, the \spadgloss{function body} is evaluated in that local
environment.
The evaluation of a function is terminated either by completely
evaluating the function body or by the evaluation of a
\spadSyntax{return} expression.

LISP`
acronymn for List Processing Language, 
a language designed for the
manipulation of nonnumerical data.
The \Language{} library is translated into LISP then
compiled into machine code by an underlying LISP.

Common LISP`
A version of \spadgloss{LISP} adopted as an informal standard by
major users and suppliers of LISP

AKCL`
Austin Kyoto Common LISP, a version of \spadgloss{KCL} produced by William 
Schelter, Austin, Texas.

KCL`Kyoto Common LISP, a version of \spadgloss{Common LISP}
which features compilation of the compilation of LISP into the 
C Programming Language

dynamic lookup`In \Language{}, a \spadgloss{domain} may or may
not explicitly provide \spadgloss{function} definitions for all of its exported
\spadgloss{operations}. These definitions may instead come from
domains in the \spadgloss{add-chain} or from \spadgloss{default packages}.
When a \spadglossSee{function call}{application} 
is made for an operation in the domain,
up to five steps are carried out.\begin{items}
\item (1) If the domain itself implements a function for the operation,
that function is returned.
\item (2) Each of the domains in the \spadgloss{add-chain} are 
searched for one which
implements the function; if found, the function is returned.
\item (3) Each of the \spadgloss{default packages} for the domain are 
searched in order of the \spadgloss{lineage}. 
If any of the default packages implements the function, the first
one found is returned.
\item (4) Each of the \spadgloss{default packages} for
each of the domains in the \spadgloss{add-chain} are searched in the order
of their \spadgloss{lineage}.
If any of the default packages implements the function, the first
one found is returned.
\item (5) If all of the above steps fail, an error message is reported.
\end{items}

lineage`the sequence of \spadgloss{default packages}
for a given domain to be searched during \spadgloss{dynamic lookup}.
This sequence is computed first by ordering the category
\spadgloss{ancestors} of the domain according to their
{\em level number}, an integer equal to
to the minimum distance of the domain from the category.
Parents have level 1, parents of parents have level 2, and so on.
Among categories with equal level numbers, ones which appear in the
left-most branches of {\em Join}s in the source code come first.
See also \spadgloss{dynamic lookup}.

infix`
{\em (syntax)} an \spadgloss{operator} placed between two \spadgloss{operands};
also called a {\em binary operator}, e.g. \spad{a + b}.
An infix operator may also be
used as a \spadgloss{prefix}, e.g.
\spad{+(a,b)} is also permissable in the \Language{} language.
Infix operators have a relative \spadgloss{precedence}.

prefix`
{\em (syntax)} an \spadgloss{operator} such as \spad{-} and \spad{not} that is written
{\em before} its single \spadgloss{operand}.
Every function of one argument can be used as a prefix operator.
For example, all of the following have equivalent meaning in \Language{}:
\spad{f(x)}, \spad{f x}, and \spad{f.x}.
See also \spadgloss{dot notation}.

unary`operation or function with \spadgloss{arity} 1

binary`operation or function with \spadgloss{arity} 2

nullary`operation or function with \spadgloss{arity} 0

arity`1. (function) the number of arguments.
2. (operator or operation) corresponds to the arity
of a function implementing the operator or operation.

declaration`
{\em (syntax)}
an expression of the form \spad{x : T} where T is some \spad{type}.
A declaration forces all values \spadglossSee{assigned}{assignment} to T 
to be of that type. 
If a value is of a different type, 
the interpreter will try to \spadglossSee{coerce}{coercion} the value to type T.
Declarations are necessary 
in case of ambiguity or when a user wants to introduce an
an \spadglossSee{unexposed}{expose} domain.

type`
The type of any \spadgloss{subdomain} is the
unique symbol {\em Category}.
The type of a \spadgloss{domain} is any \spadgloss{category} that
domain belongs to.
The type of any other object is either the (unique) domain that object 
belongs to or any \spadgloss{subdomain} of that domain.
The type of objects is in general not unique.

subdomain`{\em (basic concept)} a \spadgloss{domain} together with a \spadgloss{predicate}
characterizing which
members of the domain belong to the subdomain.
The exports of a subdomain are usually distinct from the domain itself.
A fundamental assumption however is that values in the subdomain
are automatically \spadglossSee{coerceable}{coercion} to values in the domain.
For example, if n and m are declared to be members of a subdomain
of the integers, then {\em any} \spadgloss{binary} operation from \spadtype{Integer}
is available on n and m.
On the other hand, if the result of that operation is
to be assigned to, say, k, also declared to be of that subdomain,
a \spadgloss{run-time} check is generally necessary to ensure that
the result belongs to the subdomain.

export`\spadgloss{explicit export} or \spadgloss{implicit export} of 
a domain or category

explicit export`
1. (of a domain D) any 
\spadgloss{attribute}, \spadgloss{operation}, or \spadgloss{category}
explicitly mentioned in the \spadgloss{type}
specification part T for the domain constructor definition
\spad{D: T == I}
2. (of a category C) any
\spadgloss{attribute}, \spadgloss{operation}, or \spadgloss{category}
explicitly mentioned in the \spadgloss{type}
specification part T for the domain constructor definition
\spad{C: \spadgloss{Category} == T}

implicit export`(of a domain or category)
any \spadgloss{attribute} or \spadgloss{operation}
which is either an explicit export or else
an explicit export of some category which an explicit category export 
\spadglossSee{extends}{category extension}.

parse`the transformation of a user input string
representing a valid \Language{} expression
into an internal representation as a tree-structure.

Record`(basic domain constructor)
a domain constructor used to create a
inhomogeneous aggregate composed of pairs of 
"selectors" and \spadgloss{values}.
A Record domain is written in the form
\spad{Record(a1:D1,...,an:Dn)} (n > 0) where
\spad{a1},...,\spad{an} are identifiers called the {\em selectors} of
the record, and \spad{D1},...,\spad{Dn} are domains
indicating the type of the component stored under selector \spad{an}.

selector`an identifier used to address a component value of a gloss{Record}
datatype.

Union`(basic domain constructor)
a domain constructor used to 
combine any set of domains into a single domain.
A Union domain is written in the form
\spad{Union(a1:D1,...,an:Dn)} (n > 0) where
\spad{a1},...,\spad{an} are identifiers called the {\em tags} of
the union, and \spad{D1},...,\spad{Dn} are domains 
called the {\em branches} of the union. 
The tags \spad{ai} are optional, but required when
two of the \spad{Di} are equal, e.g.
\spad{Union(inches:Integer,centimeters:Integer)}.
In the interpreter, values of union domains are automatically coerced
to values in the branches and vice-versa as appropriate.
See also \spadgloss{case}.

tag`an identifier used to discriminate a branch of a \spadgloss{Union} type.

macro`{\em (syntax)}
1. An expression of the form \spad{macro a == b} where \spad{a}
is a \spadgloss{symbol} causes \spad{a} to be textually replaced
by the expression b at \spadgloss{parse} time.
2. An expression of the form \spad{macro f(a) == b} defines a parameterized
macro expansion for a parameterized form f
This macro causes a form f(x) to be textually replaced by
the expression c at parse time, where
c is the expression obtained by replacing \spad{a} by x everywhere in b. 
See also \spadgloss{definition} where a similar substitution
is done during \spadgloss{evaluation}.

definition`{\em (syntax)}
1. An expression of the form \spad{f(a) == b} defining function f 
with \spadgloss{formal arguments} \spad{a} and \spadgloss{body} b;
equivalent to the statement \spad{f == (a) +-> b}.
2. An expression of the form \spad{a == b} where \spad{a}
is a \spadgloss{symbol}, equivalent to 
\spad{a() == b}.
See also \spadgloss{macro} where a similar substitution
is done at \spadgloss{parse} time.

pattern match`
1. (on expressions) Given a expression called a "subject" u,
the attempt to rewrite u using a set of "rewrite rules".
Each rule has the
form \spad{A == B} where \spad{A} indicates a expression called
a "pattern" and \spad{B} denotes a "replacement".
The meaning of this rule is "replace \spad{A} by B".
If a given pattern \spad{A} matches a subexpression of u,
that subexpression is replaced by \spad{B}.
Once rewritten, 
pattern matching continues until no further changes occur.
2. (on strings) the attempt to match a string indicating a "pattern"
to another string called a "subject", for example, for the purpose
of identifying a list of names.
In \Browse{}, users may enter \spadgloss{search strings} for the
purpose of identifying constructors, operations, and attributes.

rule`{\em (syntax)}
1. An expression of the form \spad{rule A == B}
indicating a "rewrite rule".
2. An expression of the form \spad{rule (R1;...;Rn)}
indicating a set of "rewrite rules" R1,...,Rn.
See \spadgloss{pattern matching} for details.

garbage collector`
a mechanism for reclaiming storage in the \spadgloss{heap}.

heap`an area of storage used by data in programs.
For example, AXIOM will use the heap to hold the partial results
of symbolic computations. When cancellations occur, these results
remain in the heap until \spadglossSee{garbage collected}{garbage collector}.