;;; PARSE (&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 (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 (p vars                                             [FUNCTION]
;;;               &aux (ht (make-hash-table :test #'equal :size 16))
;;;               stack)
;;;
;;; POWERS (monom vars                                               [FUNCTION]
;;;         &aux (tab (pairlis vars (make-list (length vars)
;;;         :initial-element 0))))
;;;
;;; PARSE-TO-ALIST (vars &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 (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 (vars &optional (order #'lex>)             [FUNCTION]
;;;                        (stream t))
;;;    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 (str vars                           [FUNCTION]
;;;                               &optional (order #'lex>))
;;;    Parse a string to a sorted alist form, the internal representation
;;;    of polynomials used by our system.
;;;
;;; SORT-POLY-1 (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 (poly-or-poly-list &optional (order #'lex>))           [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 (expr vars order ring &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 (expr vars &optional (order #'lex>)                    [FUNCTION]
;;;            (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.
;;;
;;; MONOM-BASIS (n                                                   [FUNCTION]
;;;              &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.
;;;
;;; CONVERT-NUMBER (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+ (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- (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 (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* (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/ (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 (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.
;;;