ghgonnet@watmum.UUCP (Gaston H. Gonnet) (10/31/85)
The following ideas were developed as an experiment to
solve the problem of "operators" in symbolic algebra. It is
"vox populi" that operators are needed in a symbolic algebra
system, although there is little consensus on what these should
be, what the semantics should be, allowable operations, syntax,
etc.
During the first Maple retreat (June 11-12, 1983, Research
Report CS-83-31) we established a basic design for operators. The
implementation of those was delayed until some remaining crucial
details were finally solved during the current year Maple retreat
(Sept 1985, CS technical report to be available).
We found useful to have some "witness" examples that we
want to solve in an elegant and general form. The two main
examples were:
How to represent the first derivative of f(x) at 0
(the above really refers to the differentiation operator)
Allow a special "multiplication" operator
(e.g. non-commutative multiplication)
Of course many systems solve the above problems, but in some cases
(in particular for the first example) as an ad-hoc solution, and not
as a general "operator solution"
We would like to insist that we are not claiming originality
nor the solution of all problems on earth, this is just a scheme
which may work, that we have implemented, and that we will be testing
in the near future.
Operators can be:
an unassigned name (e.g. "D")
an unassigned special name
(e.g. "&+")
a procedure (e.g. proc(x,y)
if y=0 then x^2 else x/y fi
end)
an "angle bracket operator"
(e.g. <x^2+sin(x)+1>)
any algebraic combination of the above
(Notes: The special names are just as any other name, except that they
have a special syntactic definition. These can be used as unary or
binary operators in the input.
E.g. a &+ b &- c
&det &inv A
The angle bracket operators are a special form of procedures.
The arguments can be omitted (all names are assumed to be the arguments:
<x^2+y^2>) or can be explicit (<x^2+b|x>, <a(x)|a,x>) or can additionally
have "local variables" ( <diff(f(x),x)|f|x> ). Other than that, angle
brackets operators are a shorthand for procedures.)
Operators, in any of the above forms, can be manipulated as algebraic
expressions in the system. They can be assigned, tested, passed as
parameters, involved in algebraic expressions, etc. Additionally we
have the following operations allowed for operators:
composition: a @ b
composes the operator a with operator b
repeated composition:
a @@ n
composes the operator a n times
(e.g. a@a@a@a = a@@4)
application: oper ( args )
applies the operator (or function) to the arguments
equality between operators:
arguments and local variables of operators are con-
sidered nameless for comparison purposes.
(e.g. <x^2+y|x,y> = <w+z^2|z,w> --> true)
(Notes: The semantics of the above can be illustrated by examples:
a @ <x> == <x> @ a == a
a @@ 1 == a
a@@m @ a@@n == a @@ (m+n)
a @ (a@@(-1)) == <x>
(a@b)(x) == a(b(x))
(a+b)(x) == a(x) + b(x)
(constant)(x) == constant
(a*b)(x) == a(x)*b(x)
<x^2+y|x>(5) == 25+y
other forms remain unevaluated )
The simplification of the operators is not completely
defined yet. Some rules or their inverses may be handled auto-
matically, or by the function expand or by the function simplify.
Examples of these rules are:
<a(x)|x> <===> a
D @ D @ ...(n times)... @ D <==> D @@ n
D(D(D(... n times ...(D(f)..)) <==> (D@@n)(f)
D(C(f)) <==> (D@C)(f)
Finally we have the function "define" which defines
new operator(s) when some special additional properties are
also wanted.
Define has two basic formats:
(1) defining known abstract algebraic objects, e.g.:
define( group( `&+`, 0, `&-`) );
(2) defining a set of known properties, e.g:
define( a, associative, identity=0, inverse=b )
Define produces the code for evaluation, simplification,
expansion, derivation, taylor, etc. as needed to handle
the operations involving the defined operators.
Addenda:
Several system functions will behave much better as
operators. The immediate candidates are diff, int and sum
(D, I and S) (for I and S we mean indefinite forms).
E.g.
D(cos) = -sin
I := D@@(-1); D(I(a)) --> a
S(<i>) --> <i*(i+1)/2>
D(f) --> D(f) (if f is undefined)
D(f)(0) --> D(f)(0) solves the first problem
(D@@n)(f)(0) --> represents the nth derivative of f at 0
Other functions, which accept a form and a variable, may accept
operators as a natural extension:
degree( <x^5+x^3+1> ) --> 5
taylor( <sin(x)> ) --> <x-x^3/6+O(x^5)>
solve( <sin(x)> = a ) --> arcsin(a)
That's all, no magic, no mirrors, simple (we hope).
Comments, references, critiques, etc. are solicited and welcome.
Symbolic Computation Group
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada
{decvax,ihnp4}!watmath!watmum!watmaple