1 |
|
---|
2 | ;;; PARSE (&optional stream) [FUNCTION]
|
---|
3 | ;;; Parser of infis expressions with integer/rational coefficients
|
---|
4 | ;;; The parser will recognize two kinds of polynomial expressions:
|
---|
5 | ;;; - polynomials in fully expanded forms with coefficients
|
---|
6 | ;;; written in front of symbolic expressions; constants can be
|
---|
7 | ;;; optionally enclosed in (); for example, the infix form
|
---|
8 | ;;; X^2-Y^2+(-4/3)*U^2*W^3-5
|
---|
9 | ;;; parses to
|
---|
10 | ;;; (+ (- (EXPT X 2) (EXPT Y 2)) (* (- (/ 4 3)) (EXPT U 2) (EXPT W 3))
|
---|
11 | ;;; (- 5))
|
---|
12 | ;;; - lists of polynomials; for example
|
---|
13 | ;;; [X-Y, X^2+3*Z]
|
---|
14 | ;;; parses to
|
---|
15 | ;;; (:[ (- X Y) (+ (EXPT X 2) (* 3 Z)))
|
---|
16 | ;;; where the first symbol [ marks a list of polynomials.
|
---|
17 | ;;; -other infix expressions, for example
|
---|
18 | ;;; [(X-Y)*(X+Y)/Z,(X+1)^2]
|
---|
19 | ;;; parses to:
|
---|
20 | ;;; (:[ (/ (* (- X Y) (+ X Y)) Z) (EXPT (+ X 1) 2))
|
---|
21 | ;;; Currently this function is implemented using M. Kantrowitz's INFIX
|
---|
22 | ;;; package.
|
---|
23 | ;;;
|
---|
24 | ;;; ALIST-FORM (plist vars) [FUNCTION]
|
---|
25 | ;;; Translates an expression PLIST, which should be a list of polynomials
|
---|
26 | ;;; in variables VARS, to an alist representation of a polynomial.
|
---|
27 | ;;; It returns the alist. See also PARSE-TO-ALIST.
|
---|
28 | ;;;
|
---|
29 | ;;; ALIST-FORM-1 (p vars [FUNCTION]
|
---|
30 | ;;; &aux (ht (make-hash-table :test #'equal :size 16))
|
---|
31 | ;;; stack)
|
---|
32 | ;;;
|
---|
33 | ;;; POWERS (monom vars [FUNCTION]
|
---|
34 | ;;; &aux (tab (pairlis vars (make-list (length vars)
|
---|
35 | ;;; :initial-element 0))))
|
---|
36 | ;;;
|
---|
37 | ;;; PARSE-TO-ALIST (vars &optional stream) [FUNCTION]
|
---|
38 | ;;; Parse an expression already in prefix form to an association list
|
---|
39 | ;;; form according to the internal CGBlisp polynomial syntax: a
|
---|
40 | ;;; polynomial is an alist of pairs (MONOM . COEFFICIENT). For example:
|
---|
41 | ;;; (WITH-INPUT-FROM-STRING (S "X^2-Y^2+(-4/3)*U^2*W^3-5")
|
---|
42 | ;;; (PARSE-TO-ALIST '(X Y U W) S))
|
---|
43 | ;;; evaluates to
|
---|
44 | ;;; (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) .
|
---|
45 | ;;; -5))
|
---|
46 | ;;;
|
---|
47 | ;;; PARSE-STRING-TO-ALIST (str vars) [FUNCTION]
|
---|
48 | ;;; Parse string STR and return a polynomial as a sorted association
|
---|
49 | ;;; list of pairs (MONOM . COEFFICIENT). For example:
|
---|
50 | ;;; (parse-string-to-alist "[x^2-y^2+(-4/3)*u^2*w^3-5,y]" '(x y u w))
|
---|
51 | ;;; ([ (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1)
|
---|
52 | ;;; ((0 0 0 0) . -5))
|
---|
53 | ;;; (((0 1 0 0) . 1)))
|
---|
54 | ;;; The functions PARSE-TO-SORTED-ALIST and PARSE-STRING-TO-SORTED-ALIST
|
---|
55 | ;;; sort terms by the predicate defined in the ORDER package.
|
---|
56 | ;;;
|
---|
57 | ;;; PARSE-TO-SORTED-ALIST (vars &optional (order #'lex>) [FUNCTION]
|
---|
58 | ;;; (stream t))
|
---|
59 | ;;; Parses streasm STREAM and returns a polynomial represented as
|
---|
60 | ;;; a sorted alist. For example:
|
---|
61 | ;;; (WITH-INPUT-FROM-STRING (S "X^2-Y^2+(-4/3)*U^2*W^3-5")
|
---|
62 | ;;; (PARSE-TO-SORTED-ALIST '(X Y U W) S))
|
---|
63 | ;;; returns
|
---|
64 | ;;; (((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 2 3) . -4/3) ((0 0 0 0) .
|
---|
65 | ;;; -5)) and
|
---|
66 | ;;; (WITH-INPUT-FROM-STRING (S "X^2-Y^2+(-4/3)*U^2*W^3-5")
|
---|
67 | ;;; (PARSE-TO-SORTED-ALIST '(X Y U W) T #'GRLEX>) S)
|
---|
68 | ;;; returns
|
---|
69 | ;;; (((0 0 2 3) . -4/3) ((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 0 0) .
|
---|
70 | ;;; -5))
|
---|
71 | ;;;
|
---|
72 | ;;; PARSE-STRING-TO-SORTED-ALIST (str vars [FUNCTION]
|
---|
73 | ;;; &optional (order #'lex>))
|
---|
74 | ;;; Parse a string to a sorted alist form, the internal representation
|
---|
75 | ;;; of polynomials used by our system.
|
---|
76 | ;;;
|
---|
77 | ;;; SORT-POLY-1 (p order) [FUNCTION]
|
---|
78 | ;;; Sort the terms of a single polynomial P using an admissible monomial
|
---|
79 | ;;; order ORDER. Returns the sorted polynomial. Destructively modifies P.
|
---|
80 | ;;;
|
---|
81 | ;;; SORT-POLY (poly-or-poly-list &optional (order #'lex>)) [FUNCTION]
|
---|
82 | ;;; Sort POLY-OR-POLY-LIST, which could be either a single polynomial
|
---|
83 | ;;; or a list of polynomials in internal alist representation, using
|
---|
84 | ;;; admissible monomial order ORDER. Each polynomial is sorted using
|
---|
85 | ;;; SORT-POLY-1.
|
---|
86 | ;;;
|
---|
87 | ;;; POLY-EVAL-1 (expr vars order ring &aux (n (length vars))) [FUNCTION]
|
---|
88 | ;;; Evaluate an expression EXPR as polynomial
|
---|
89 | ;;; by substituting operators + - * expt with
|
---|
90 | ;;; corresponding polynomial operators
|
---|
91 | ;;; and variables VARS with monomials (1 0 ... 0), (0 1 ... 0) etc.
|
---|
92 | ;;; We use special versions of binary
|
---|
93 | ;;; operators $poly+, $poly-, $minus-poly, $poly* and $poly-expt
|
---|
94 | ;;; which work like the corresponding functions in the
|
---|
95 | ;;; POLY package, but accept scalars as arguments as well.
|
---|
96 | ;;;
|
---|
97 | ;;; POLY-EVAL (expr vars &optional (order #'lex>) [FUNCTION]
|
---|
98 | ;;; (ring *coefficient-ring*))
|
---|
99 | ;;; Evaluate an expression EXPR, which should be a polynomial
|
---|
100 | ;;; expression or a list of polynomial expressions (a list of expressions
|
---|
101 | ;;; marked by prepending keyword :[ to it) given in lisp prefix notation,
|
---|
102 | ;;; in variables VARS, which should be a list of symbols. The result of
|
---|
103 | ;;; the evaluation is a polynomial or a list of polynomials (marked by
|
---|
104 | ;;; prepending symbol '[) in the internal alist form. This evaluator is
|
---|
105 | ;;; used by the PARSE package to convert input from strings directly to
|
---|
106 | ;;; internal form.
|
---|
107 | ;;;
|
---|
108 | ;;; MONOM-BASIS (n [FUNCTION]
|
---|
109 | ;;; &aux
|
---|
110 | ;;; (basis
|
---|
111 | ;;; (copy-tree
|
---|
112 | ;;; (make-list n :initial-element
|
---|
113 | ;;; (list 'quote
|
---|
114 | ;;; (list (cons (make-list n :initial-element 0)
|
---|
115 | ;;; 1)))))))
|
---|
116 | ;;; Generate a list of monomials ((1 0 ... 0) (0 1 0 ... 0) ... (0 0 ...
|
---|
117 | ;;; 1) which correspond to linear monomials X1, X2, ... XN.
|
---|
118 | ;;;
|
---|
119 | ;;; CONVERT-NUMBER (number-or-poly n) [FUNCTION]
|
---|
120 | ;;; Returns NUMBER-OR-POLY, if it is a polynomial. If it is a number,
|
---|
121 | ;;; it converts it to the constant monomial in N variables. If the result
|
---|
122 | ;;; is a number then convert it to a polynomial in N variables.
|
---|
123 | ;;;
|
---|
124 | ;;; $POLY+ (p q n order ring) [FUNCTION]
|
---|
125 | ;;; Add two polynomials P and Q, where each polynomial is either a
|
---|
126 | ;;; numeric constant or a polynomial in internal representation. If the
|
---|
127 | ;;; result is a number then convert it to a polynomial in N variables.
|
---|
128 | ;;;
|
---|
129 | ;;; $POLY- (p q n order ring) [FUNCTION]
|
---|
130 | ;;; Subtract two polynomials P and Q, where each polynomial is either a
|
---|
131 | ;;; numeric constant or a polynomial in internal representation. If the
|
---|
132 | ;;; result is a number then convert it to a polynomial in N variables.
|
---|
133 | ;;;
|
---|
134 | ;;; $MINUS-POLY (p n ring) [FUNCTION]
|
---|
135 | ;;; Negation of P is a polynomial is either a numeric constant or a
|
---|
136 | ;;; polynomial in internal representation. If the result is a number then
|
---|
137 | ;;; convert it to a polynomial in N variables.
|
---|
138 | ;;;
|
---|
139 | ;;; $POLY* (p q n order ring) [FUNCTION]
|
---|
140 | ;;; Multiply two polynomials P and Q, where each polynomial is either a
|
---|
141 | ;;; numeric constant or a polynomial in internal representation. If the
|
---|
142 | ;;; result is a number then convert it to a polynomial in N variables.
|
---|
143 | ;;;
|
---|
144 | ;;; $POLY/ (p q ring) [FUNCTION]
|
---|
145 | ;;; Divide a polynomials P which is either a numeric constant or a
|
---|
146 | ;;; polynomial in internal representation, by a number Q.
|
---|
147 | ;;;
|
---|
148 | ;;; $POLY-EXPT (p l n order ring) [FUNCTION]
|
---|
149 | ;;; Raise polynomial P, which is a polynomial in internal
|
---|
150 | ;;; representation or a numeric constant, to power L. If P is a number,
|
---|
151 | ;;; convert the result to a polynomial in N variables.
|
---|
152 | ;;;
|
---|