The Parser Package

parse

$\parbox{\pboxargslen}{\em {\sf \&optional} stream \/}$ [FUNCTION]

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^2$-$Y^2+($-$4/3)*U^2*W^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^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)^2] parses to: (:[ (/ (* ($-$ X Y) (+ X Y)) Z) (EXPT (+ X 1) 2)) Currently this function is implemented using M. Kantrowitz's INFIX package.

alist$-$form

$\parbox{\pboxargslen}{\em plist vars \/}$ [FUNCTION]

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.

alist$-$form$-$1

$\parbox{\pboxargslen}{\em p vars {\sf \&aux} (ht (make$-$hash$-$table :test \char93 'equal :size 16)) stack \/}$ [FUNCTION]

powers

$\parbox{\pboxargslen}{\em monom vars {\sf \&aux} (tab (pairlis vars (make$-$list (length vars) :initial$-$element 0))) \/}$ [FUNCTION]

parse$-$to$-$alist

$\parbox{\pboxargslen}{\em vars {\sf \&optional} stream \/}$ [FUNCTION]

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^2$-$Y^2+($-$4/3)*U^2*W^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))

parse$-$string$-$to$-$alist

$\parbox{\pboxargslen}{\em str vars \/}$ [FUNCTION]

Parse string STR and return a polynomial as a sorted association list of pairs (MONOM . COEFFICIENT). For example: (parse$-$string$-$to$-$alist "[x^2$-$y^2+($-$4/3)*u^2*w^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.

parse$-$to$-$sorted$-$alist

$\parbox{\pboxargslen}{\em vars {\sf \&optional} (order \char93 'lex$\gt$) (stream t) \/}$ [FUNCTION]

Parses streasm STREAM and returns a polynomial represented as a sorted alist. For example: (WITH$-$INPUT$-$FROM$-$STRING (S "X^2$-$Y^2+($-$4/3)*U^2*W^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^2$-$Y^2+($-$4/3)*U^2*W^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))

parse$-$string$-$to$-$sorted$-$alist

$\parbox{\pboxargslen}{\em str vars {\sf \&optional} (order \char93 'lex$\gt$) \/}$ [FUNCTION]

Parse a string to a sorted alist form, the internal representation of polynomials used by our system.

sort$-$poly$-$1

$\parbox{\pboxargslen}{\em p order \/}$ [FUNCTION]

Sort the terms of a single polynomial P using an admissible monomial order ORDER. Returns the sorted polynomial. Destructively modifies P.

sort$-$poly

$\parbox{\pboxargslen}{\em poly$-$or$-$poly$-$list {\sf \&optional} (order \char93 'lex$\gt$) \/}$ [FUNCTION]

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.

poly$-$eval$-$1

$\parbox{\pboxargslen}{\em expr vars order ring {\sf \&aux} (n (length vars)) \/}$ [FUNCTION]

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.

poly$-$eval

$\parbox{\pboxargslen}{\em expr vars {\sf \&optional} (order \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

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.

monom$-$basis

$\parbox{\pboxargslen}{\em n {\sf \&aux} (basis (copy$-$tree (make$-... ... (list 'quote (list (cons (make$-$list n :initial$-$element 0) 1)))))) \/}$ [FUNCTION]

Generate a list of monomials ((1 0 ... 0) (0 1 0 ... 0) ... (0 0 ... 1) which correspond to linear monomials X1, X2, ... XN.

convert$-$number

$\parbox{\pboxargslen}{\em number$-$or$-$poly n \/}$ [FUNCTION]

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.

$poly+

$\parbox{\pboxargslen}{\em p q n order ring \/}$ [FUNCTION]

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.

$poly$-$

$\parbox{\pboxargslen}{\em p q n order ring \/}$ [FUNCTION]

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.

$minus$-$poly

$\parbox{\pboxargslen}{\em p n ring \/}$ [FUNCTION]

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.

$poly*

$\parbox{\pboxargslen}{\em p q n order ring \/}$ [FUNCTION]

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.

$poly/

$\parbox{\pboxargslen}{\em p q ring \/}$ [FUNCTION]

Divide a polynomials P which is either a numeric constant or a polynomial in internal representation, by a number Q.

$poly$-$expt

$\parbox{\pboxargslen}{\em p l n order ring \/}$ [FUNCTION]

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.