| blob | 66f940682db34d6e02521e6475ce3b1e92492fc9 |
1 ;;; -*- Mode: Lisp; Package: Maxima; Syntax: Common-Lisp; Base: 10 -*- ;;;;
2 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
3 ;;; The data in this file contains enhancements. ;;;;;
4 ;;; ;;;;;
5 ;;; Copyright (c) 1984,1987 by William Schelter,University of Texas ;;;;;
6 ;;; All rights reserved ;;;;;
7 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
8 ;;; (c) Copyright 1980 Massachusetts Institute of Technology ;;;
9 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
15 ;;;; I think this is described in Chapter 3 of J. Moses' thesis,
16 ;;;; "Symbolic Integration", MIT-LCS-TR-047. A scanned version of the
17 ;;;; thesis is available at
18 ;;;; http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-047.pdf.
19 ;;;;
20 ;;;; Unfortunately, some important pages in the scan are all black.
21 ;;;;
22 ;;;; A version with the missing pages is available (2008-12-14) from
23 ;;;; http://www.softwarepreservation.org/projects/LISP/MIT
24 ;;;;
25 ;;;; Schatchen is Yiddish for "matchmaker" and Schatchen here is a
26 ;;;; pattern matching routine.
47 ;;VARIOUS SIMPLE PATTERNS
69 ;;; SCHATCHEN pattern matcher.
70 ;;;
71 ;;; Match the (maxima) expression in E with the pattern given by P.
72 ;;;
73 ;;; The pattern language is partially described in Moses thesis. We
74 ;;; summarize here some of the main ideas. (This is mostly taken from
75 ;;; his thesis.)
76 ;;;
77 ;;; A variable in the pattern is written in the form (VAR name pred
78 ;;; arg1 arg2 ... argn)
79 ;;;
80 ;;; where
81 ;;;
82 ;;; name = name of variable
83 ;;; pred = predicate associated with the variable
84 ;;; argi = arguments 2 through n+1 for pred
85 ;;;
86 ;;; The first arg of pred is assumed to the expression that the match
87 ;;; assigns to the variable.
88 ;;;
89 ;;; If the variable has a mode, it is written in prefix form. Thus
90 ;;; A*x, where A is a number and is a coefficient of plus or times
91 ;;; becomes (coeffpt (var a number) x).
92 ;;;
93 ;;; Some modes:
94 ;;;
95 ;;; coefft - coefficient of TIMES (matches A in A*x) coeffp -
96 ;;; coefficient of PLUS (matches B in x + B) coeffpt - coefficient of
97 ;;; PLUS and TIMES (like coefft and coeffp and matches things like
98 ;;; 2*x^2+sqrt(2)*x^2 so that the coefficient of x^2 is 2+sqrt(2).
99 ;;;
100 ;;; A brief description of the algorithm:
101 ;;;
102 ;;; If E equals P, the match succeeds.
103 ;;;
104 ;;; If P is of the form (VAR name pred arg1 ... argn), then (pred e
105 ;;; arg1 arg2 ... argn) is evaluated. If the value of the pred is
106 ;;; true, the match succeeds and ((name . e) is appended to the
107 ;;; answer. Otherwise the match fails.
108 ;;;
109 ;;; If P is of the form (op p1 ... pn) and op is not PLUS, TIMES, or
110 ;;; EXPT, then E must be of the form (op1 e1 ... en) and each pi must
111 ;;; match i1 and op must match op1. Otherwise the match fails.
112 ;;;
113 ;;; If the pattern is of the form (EXPT p1 p2) then
114 ;;; 1) e is (EXPT e1 e2) and p1 matches e1 and p2 matches e2 or
115 ;;; 2) e is 0 and p1 matches 0 or
116 ;;; 3) e is 1 and
117 ;;; a) p2 matches 0 or
118 ;;; b) p1 matches 1
119 ;;; 4) p2 matches 1 and p1 matches e
120 ;;;
121 ;;; Otherwise the match fails
122 ;;;
123 ;;; If the pattern is of the form (op p1 p2 ... pn) and op = PLUS or
124 ;;; TIMES, then if E is not of the form (op e1 ... em), E is
125 ;;; transformed to (op E). In this case an attempt is made to match
126 ;;; each pi with some ej. The scan starts with p1 matched with e1.
127 ;;; If that fails p1 is matched with e2. If pi matches some ej, ej is
128 ;;; deleted (destructively) from E and the scan continues with pi=1
129 ;;; matched with he first subexpression remaining in E. If for some
130 ;;; pi no ej can be found to match it, then pi is matched with 0 if op
131 ;;; = PLUS or 1 if op = TIMES. If that also fails, the match fails.
132 ;;; If all the pi have been matched, but some ej have not, the match
133 ;;; fails.
134 ;;;
135 ;;; Exceptions to the above are due to modes. If op = PLUS, and pi is
136 ;;; of the form (coeffpt (var name pred arg1 ... argn) p1 ... pk),
137 ;;; then the remaining expression is traversed with the pattern
138 ;;; (coefft (var name pred arg1 ... argn) p1 ... pk). Each
139 ;;; subexpression that is thus matched is deleted from the expression.
140 ;;; The simplified sum of the result of the scan becomes the value of
141 ;;; the variable. If no subexpression could thuse be matched, then
142 ;;; (pred 0 arg1 ... argn) is attempted. If this too fails, the match
143 ;;; fails.
144 ;;;
145 ;;; If op = PLUS and pn is of the form (coeffp (var name pred arg1
146 ;;; ... argn), then if e is currently of the form (PLUS ei ... en),
147 ;;; then (pred e arg1 ... argn) is evaluated. If the value of pred is
148 ;;; true, ((name . e)) is appended. If no subexpressions remain in e,
149 ;;; then pred 0 arg1 ... argn) is attempted. If it succeeds, ((name
150 ;;; . )) is appended. Otherwise, the match fails.
151 ;;;
152 ;;; If op = PLUS and pi is of the form (coefft (var name pred arg1
153 ;;; ... argn) p1 ... pk) then (times p1 .... pk) is matched with e.
154 ;;; If the match succeeds and e remains of the form (times e1 ... en),
155 ;;; then (pred e arg1 ... argn) is attempted. If it fails, the match
156 ;;; fails. If no subexpressions remain in e, then (pred 1 arg1
157 ;;; ... argn) is attempted. If this succeeds, ((name . 1) is
158 ;;; appended.
163 ;;THE RESTORE FUNCTIONS RESTORE THE SPEC-VAR ANS
164 ;;AND RETURN TRUE OR FALSE AS FOLLOWS
165 ;;RESTORE - FALSE
166 ;;RESTORE1 - TRUE AND CLEARS UP ANS
167 ;;RESTORE2 - TRUE AND CLEARS OFF *LOOP INDICATORS
168 ;; DOES NOT FIX UP THE EXPRESSION AND
169 ;; IS THUS TO BE USED ONLY INTERNALLY
170 ;;
171 ;;TO INSURE THAT THERE IS NO CONFLICT IN SPECIAL VARIABLES,
172 ;;ESPECIALLY WITH THE VAR* (SET) MODE ALL SCHATCHEN VARIABLES
173 ;;ARE TO BE PRECEDED BY A "%"
230 x)
279 ;;; IND = T MEANS AN INTERNAL CALL (USUALLY FROM LOOPP)
293 t)
324 l ;;; EACH TIME HERE WE HAVE CDR'D DOWN THE EXP.
350 nil)
361 ;MOST OF THE THE GARBAGE ON ANS IT
394 nil))
522 ;;WHEN THE CAR OF ALA IS VAR* THE CADR IS A LIST OF
523 ;;THE VARIOUS SWITCHES WHICH MAY BE SET.
524 ;;UVAR- INDICATES THIS SHOULD MATCH SOMETHING WHICH IS ALREADY ON ANS.
525 ;;SET - ACTUALLY SET THIS VARIABLE TO ITS VALUE IF IT MATCHES.
526 ;;COEFFPT - SPECIAL ARGUMENT IF IN COEFFPT.
552 ;; ALA IS THE PREDICATE LIST (VAR PREDFN ARG2 ARG3 ARG4 . . .)
573 ;;;THE LAMBDA IS HERE ONLY BECAUSE OF SIN!!!
594 ;; Evaluate a symbol which has a value.
596 ;; Otherwise return the symbol.
597 q))
599 args)))
623 exp1)
630 ;; Execute BODY with the variables in VARS bound using ALIST. If any variable is
631 ;; missing, it is set to NIL.
632 ;;
633 ;; Example usage:
634 ;; (alist-bind (a b c) some-alist (+ a b c))
639 for var in vars
644 ;; Factor out the common logic to write a COND statement that uses the Schatchen
645 ;; pattern matcher.
646 ;;
647 ;; Each clause in CLAUSES should match (TEST VARIABLES &body BODY). This will be
648 ;; transformed into a COND clause that first runs TEST and binds the result to
649 ;; W. TEST is assumed to boil down to a call to M2, which returns an alist of
650 ;; results for the matched variables. VARIABLES should be a list of symbols and
651 ;; the clause only matches if each of these symbols is bound in the alist.
652 ;;
653 ;; As a special rule, if the CAR of TEST is of the form (AND F1 F2 .. FN) then
654 ;; the result of evaluating F1 is bound to W and then the clause only matches if
655 ;; F2 .. FN all evaluate to true as well as the test described above.
656 ;;
657 ;; If the clause matches then the result of the cond is that of evaluating BODY
658 ;; (in an implicit PROGN) with each variable bound to the corresponding element
659 ;; of the alist.
660 ;;
661 ;; To add an unconditional form at the bottom, use a clause of the form
662 ;;
663 ;; (T NIL F1 .. FN).
664 ;;
665 ;; This will always match and doesn't try to bind any extra variables.
671 for clause in clauses
672 collecting
676 ;; A clause matches in the cond if TEST returns non-nil and
677 ;; binds all the expected variables in the alist. As a special
678 ;; syntax, if the car of TEST is 'AND, then we bind W to the
679 ;; result of the first argument and then check the following
680 ;; arguments in an environment where W is bound (but the
681 ;; variables aren't).
693 ;; If the clause matched, we explicitly bind all of those
694 ;; variables in a let form and then evaluate the
695 ;; associated body.
699 ;;(declare-top (unspecial var ans))