\begin{lisp:documentation}{parse}{FUNCTION}{{\sf \&optional} stream }
Parser of infis expressions with integer/rational coefficients
The parser will recognize two kinds of polynomial expressions:
$-$ polynomials in fully expanded forms with coefficients
 written in front of symbolic expressions; constants can be
optionally enclosed in (); for example, the infix form
X\symbol{94}2$-$Y\symbol{94}2+($-$4/3)*U\symbol{94}2*W\symbol{94}3$-$5 parses to
	(+ ($-$ (EXPT X 2) (EXPT Y 2)) (* ($-$ (/ 4 3)) (EXPT U 2) (EXPT W
3)) ($-$ 5)) 
$-$ lists of polynomials; for example
       [X$-$Y, X\symbol{94}2+3*Z]          
 parses to
	  (:[ ($-$ X Y) (+ (EXPT X 2) (* 3 Z)))
 where the first symbol [ marks a list of polynomials.
$-$other infix expressions, for example
       [(X$-$Y)*(X+Y)/Z,(X+1)\symbol{94}2]
parses to:
	(:[ (/ (* ($-$ X Y) (+ X Y)) Z) (EXPT (+ X 1) 2))
Currently this function is implemented using M. Kantrowitz's INFIX
package. 
\end{lisp:documentation}

\begin{lisp:documentation}{alist$-$form}{FUNCTION}{plist vars }
Translates an expression PLIST, which should be a list of polynomials
in variables VARS, to an alist representation of a polynomial.
It returns the alist. See also PARSE$-$TO$-$ALIST.
\end{lisp:documentation}

\begin{lisp:documentation}{alist$-$form$-$1}{FUNCTION}{p vars {\sf \&aux} (ht (make$-$hash$-$table :test \#'equal :size 16)) stack }
{\ } % NO DOCUMENTATION FOR ALIST-FORM-1
\end{lisp:documentation}

\begin{lisp:documentation}{powers}{FUNCTION}{monom vars {\sf \&aux} (tab (pairlis vars (make$-$list (length vars) :initial$-$element 0))) }
{\ } % NO DOCUMENTATION FOR POWERS
\end{lisp:documentation}

\begin{lisp:documentation}{parse$-$to$-$alist}{FUNCTION}{vars {\sf \&optional} stream }
Parse an expression already in prefix form to an association list
form according to the internal CGBlisp polynomial syntax: a
polynomial is an alist of pairs (MONOM . COEFFICIENT). For example:
 (WITH$-$INPUT$-$FROM$-$STRING (S
"X\symbol{94}2$-$Y\symbol{94}2+($-$4/3)*U\symbol{94}2*W\symbol{94}3$-$5") (PARSE$-$TO$-$ALIST '(X Y U W) S))
evaluates to
(((0 0 2 3) . $-$4/3) ((0 2 0 0) . $-$1) ((2 0 0 0) . 1) ((0 0 0 0) .
$-$5)) 
\end{lisp:documentation}

\begin{lisp:documentation}{parse$-$string$-$to$-$alist}{FUNCTION}{str vars }
Parse string STR and return a polynomial as a sorted association
list of pairs (MONOM . COEFFICIENT). For example:
(parse$-$string$-$to$-$alist
"[x\symbol{94}2$-$y\symbol{94}2+($-$4/3)*u\symbol{94}2*w\symbol{94}3$-$5,y]" '(x y u w)) ([ (((0 0 2 3) . $-$4/3) ((0 2 0 0) . $-$1) ((2 0 0 0) . 1)
    ((0 0 0 0) . $-$5))
   (((0 1 0 0) . 1)))
The functions PARSE$-$TO$-$SORTED$-$ALIST and
PARSE$-$STRING$-$TO$-$SORTED$-$ALIST sort terms by the predicate
defined in the ORDER package. 
\end{lisp:documentation}

\begin{lisp:documentation}{parse$-$to$-$sorted$-$alist}{FUNCTION}{vars {\sf \&optional} (order \#'lex$>$) (stream t) }
Parses streasm STREAM and returns a polynomial represented as 
a sorted alist. For example:
(WITH$-$INPUT$-$FROM$-$STRING (S
"X\symbol{94}2$-$Y\symbol{94}2+($-$4/3)*U\symbol{94}2*W\symbol{94}3$-$5") (PARSE$-$TO$-$SORTED$-$ALIST '(X Y U W) S))
returns
(((2 0 0 0) . 1) ((0 2 0 0) . $-$1) ((0 0 2 3) . $-$4/3) ((0 0 0 0) .
$-$5)) and
(WITH$-$INPUT$-$FROM$-$STRING (S
"X\symbol{94}2$-$Y\symbol{94}2+($-$4/3)*U\symbol{94}2*W\symbol{94}3$-$5") (PARSE$-$TO$-$SORTED$-$ALIST '(X Y U W) T \#'GRLEX$>$) S)
returns
(((0 0 2 3) . $-$4/3) ((2 0 0 0) . 1) ((0 2 0 0) . $-$1) ((0 0 0 0) .
$-$5)) 
\end{lisp:documentation}

\begin{lisp:documentation}{parse$-$string$-$to$-$sorted$-$alist}{FUNCTION}{str vars {\sf \&optional} (order \#'lex$>$) }
Parse a string to a sorted alist form, the internal representation
of polynomials used by our system.
\end{lisp:documentation}

\begin{lisp:documentation}{sort$-$poly$-$1}{FUNCTION}{p order }
Sort the terms of a single polynomial P using an admissible monomial
order ORDER. Returns the sorted polynomial. Destructively modifies P.
\end{lisp:documentation}

\begin{lisp:documentation}{sort$-$poly}{FUNCTION}{poly$-$or$-$poly$-$list {\sf \&optional} (order \#'lex$>$) }
Sort POLY$-$OR$-$POLY$-$LIST, which could be either a single
polynomial or a list of polynomials in internal alist representation,
using admissible monomial order ORDER. Each polynomial is sorted
using SORT$-$POLY$-$1.
\end{lisp:documentation}

\begin{lisp:documentation}{poly$-$eval$-$1}{FUNCTION}{expr vars order ring {\sf \&aux} (n (length vars)) }
Evaluate an expression EXPR as polynomial
by substituting operators + $-$ * expt with
corresponding polynomial operators
and variables VARS with monomials (1 0 ... 0), (0 1 ... 0) etc.
We use special versions of binary
operators \$poly+, \$poly$-$, \$minus$-$poly, \$poly* and
\$poly$-$expt which work like the corresponding functions in the
POLY package, but accept scalars as arguments as well.
\end{lisp:documentation}

\begin{lisp:documentation}{poly$-$eval}{FUNCTION}{expr vars {\sf \&optional} (order \#'lex$>$) (ring *coefficient$-$ring*) }
Evaluate an expression EXPR, which should be a polynomial
expression or a list of polynomial expressions (a list of expressions
marked by prepending keyword :[ to it) given in lisp prefix notation,
in variables VARS, which should be a list of symbols. The result of
the evaluation is a polynomial or a list of polynomials (marked by
prepending symbol '[) in the internal alist form. This evaluator is
used by the PARSE package to convert input from strings directly to
internal form.
\end{lisp:documentation}

\begin{lisp:documentation}{monom$-$basis}{FUNCTION}{n {\sf \&aux} (basis (copy$-$tree (make$-$list n :initial$-$element (list 'quote (list (cons (make$-$list n :initial$-$element 0) 1)))))) }
Generate a list of monomials ((1 0 ... 0) (0 1 0 ... 0) ... (0 0 ...
1) which correspond to linear monomials X1, X2, ... XN.
\end{lisp:documentation}

\begin{lisp:documentation}{convert$-$number}{FUNCTION}{number$-$or$-$poly n }
Returns NUMBER$-$OR$-$POLY, if it is a polynomial. If it is a number,
it converts it to the constant monomial in N variables. If the result
is a number then convert it to a polynomial in N variables.
\end{lisp:documentation}

\begin{lisp:documentation}{\$poly+}{FUNCTION}{p q n order ring }
Add two polynomials P and Q, where each polynomial is either a
numeric constant or a polynomial in internal representation. If the
result is a number then convert it to a polynomial in N variables.
\end{lisp:documentation}

\begin{lisp:documentation}{\$poly$-$}{FUNCTION}{p q n order ring }
Subtract two polynomials P and Q, where each polynomial is either a
numeric constant or a polynomial in internal representation. If the
result is a number then convert it to a polynomial in N variables.
\end{lisp:documentation}

\begin{lisp:documentation}{\$minus$-$poly}{FUNCTION}{p n ring }
Negation of P is a polynomial is either a numeric constant or a
polynomial in internal representation. If the result is a number then
convert it to a polynomial in N variables.
\end{lisp:documentation}

\begin{lisp:documentation}{\$poly*}{FUNCTION}{p q n order ring }
Multiply two polynomials P and Q, where each polynomial is either a
numeric constant or a polynomial in internal representation. If the
result is a number then convert it to a polynomial in N variables.
\end{lisp:documentation}

\begin{lisp:documentation}{\$poly/}{FUNCTION}{p q ring }
Divide a polynomials P which is either a numeric constant or a
polynomial in internal representation, by a number Q.
\end{lisp:documentation}

\begin{lisp:documentation}{\$poly$-$expt}{FUNCTION}{p l n order ring }
Raise polynomial P, which is a polynomial in internal
representation or a numeric constant, to power L. If P is a number,
convert the result to a polynomial in N variables.
\end{lisp:documentation}