Symbolic Integration using CLIPS

John is a programmer/analyst at the Texas Department of Human Services. He can be contacted at [email protected].

There are two fundamentally different approaches to integration. Numerical techniques, like those presented by Dann Corbit in "Numerical Integration: From Trapezoids to RMS" (DDJ, "Algorithm Alley," October 1996), always work, but roundoff and other arithmetic errors can make it hard to trust the answers. Conversely, symbolic techniques (the methods you were taught in calculus class) provide exact answers, but they don't always work; for example, cannot be evaluated symbolically. This month, John Swartz examines techniques for symbolic integration.

-- Tim Kientzle

I recently read a comment by John McCarthy indicating that one of his students, James Slagle, had a program that took three minutes to determine an integral on MIT's IBM 7090 computer. Several searches of library databases and one interlibrary loan later, I read Dr. Slagle's 1961 dissertation "A Heuristic Program that Solves Symbolic Integration Problems in Freshman Calculus, Symbolic Automatic Integrator (SAINT)." One of the approval signatures on the dissertation was Marvin Minsky's.

Slagle's original program was written in LISP, but the source code was not included with the dissertation. Fortunately, his description is quite detailed, and I was able to use it to implement a subset of his system in CLIPS, a "C Language Integrated Production System" (see the accompanying text box for more details on CLIPS).

The Art of the Integral

Slagle considered three different solution methods:

• Standard forms, corresponding to the basic integrals found in first-year calculus texts.
• Algorithmic transformations, which are always applicable.
• Heuristics, which may or may not be appropriate.

Although Slagle identified 26 standard forms, I'll focus on the 14 listed in Figure 1.

Algorithm-like Transformations

If an integrand is not in standard form, Slagle tries an algorithm-like transformation. An appropriate algorithm-like transformation is a transformation that is the correct next step to bringing the current goal nearer to achievement.

Figure 2 shows Slagle's eight algorithm-like transformations. My prototype only used the transform in Figure 2(c).

Heuristic Transformations

Slagle's symbolic integration system used trial-and-error to apply a suite of symbolic integration tricks, a concept known as "backtracking." He describes this approach as follows:

A transformation of a goal is called heuristic when, even though it is applicable and plausible, there is a significant risk that it is not the appropriate next step. A transformation may be inappropriate either because it leads no closer to the solution or because some other transformation would be better. The heuristic transformations are analogous to methods of detachment, forward chaining and backward chaining in general AI theory.

Slagle used ten heuristic transformations (described later) in his dissertation. My prototype only implemented two of them, heuristics b(3) and e. I implemented the heuristics as CLIPS rules. I include all the heuristics in case you want to work further with this problem.

What follows is one continuous, if slightly paraphrased, quotation from Slagle's dissertation:

"a. Transform an elementary function of trigonometric functions.

An integrand (which was not itself generated by a transformation of this type) and which is an elementary function of trigonometric functions; i.e., is of the form elf {sinv, cosv, tanv, cotv, secv, cscv} is transformed into two or three of the following forms:

1. elf {sinv, cosv, sinv/cosv, cosv/sinv, 1/cosv, 1/sinv} when the integrand is not already an elementary function of sines and cosines (seventh characteristic);

2. elf {tanv/secv, 1/secv, tanv, 1/tanv, secv, secv/tanv} when the integrand is not already an elementary function of secants and tangents (eighth characteristic);

3. elf {1/cscv, cotv/cscv, 1/cotv, cotv, cscv/cotv, cscv} when the integrand is not already an elementary function of cosecants and cotangents (ninth characteristic).

b. Substitute for a trigonometric function.

The form of the integrand often suggests a substitution for a particular trigonometric function.

1. When the integrand is an elementary function of sines and cosines (seventh characteristic) and, in fact, is of the form elf {sinv, cos²v)} cos²ⁿ⁺¹v where elf {sinv, cos²v)} is an elementary function of sines and even powers of cosines and where n is an integer. Substitution of u=sinv often transforms the goal into the often simpler subgoal

elf{u, 1-u²} (1-u²)ⁿ du

2. Similarly when the integrand is of the form elf{cosv, sin²v} sin²ⁿ⁺¹, try u=cosv.

3. Similarly when the integrand is of the form elf{tan v , sec² v} try u=tanv.

4. Similarly when the integrand is of the form elf{cotv, csc²v}, try u=cotv.

5. Similarly when the integrand is of the form elf{secv, tan²v} tan²ⁿ⁺¹v, try u=secv.

6. Similarly when the integrand is of the form elf{cscv, cot²v} cot²ⁿ⁺¹v, try u=cscv.

c. Substitute for a subexpression whose derivative divides the integrand.

Let g(v) be the integrand. For each nonconstant nonlinear subexpression s(v) such that neither its main connective is MINUS nor is it a product with a constant factor and such that the number of nonconstant factors of the fraction g(v)/s(v) (after cancellation) is less than the number of factors of g(v), try substituting u=s(v).

d. Integrate by parts.

For each partition into a product of two factors G*h of an integrand which is partial (eleventh characteristic) such that G 1 and such that this procedure, with the allotment of no resources, finds integral(h dv)=H, try integration by parts.

e. Eliminate the middle term of a quadratic subexpression.

For each quadratic subexpression: q(v)=c₃+c₂v +c₁v² where c₁ and c₂ are nonzero constants, eliminate the middle term by the substitution u=v+c₂/2c_1, which transforms q(v) into c₃-c_2²/4c₁+c₁u².

f. Distribute nonconstant sums.

If at least one nonconstant sum occurs as a factor of a product in the integrand, try transforming the integrand by distributing the products with respect to all such sums.

g. Trigonometric substitution

For each quadratic subexpression of the form c₂+c₁ v² where c₁ and c₂ are nonzero constants:

1.If both c₁ and c₂ are positive, try the substitution

v = tan u.

2.If c₁ is negative and c₂ is positive, try the substitution

v = sin u.

3.If c₁ is positive and c₂ is negative , try the substitution

v = sec u.

h. Expand positive integer powers of nonconstant sums.

If the integrand contains at least one nonconstant sum raised to an integer power n>1, try expanding all such sums.

i. Exponent base.

Suppose the integrand has an exponent base b which is not NIL; i.e., has the form elf {bⁿ_1v, bⁿ_2v ..., b^n_kv} where n₁, n₂, ..., n_k are integers. Let g be the greatest common divisor or these integers. Try the substitution u = b^gv

j. Rational function of sines and cosines.

When the integrand is a rational function of sines and cosines (sixth characteristic), try substituting u=tan(v/2) which replaces sin v by 2u/(1+u²) and replaces cos v by (1-u²)/(1+u²) and replaces dv by 2/(1+u²)du. This substitution transforms the integrand into a rational function."

Code Walkthrough

My source-code implementation of Slagle's technique (available electronically; see "Availability," page 3) has four sections:

1. The template section contains the knowledge base. CLIPS uses a LISP-like syntax in which structures and statements are bounded by parentheses.

2. The utility functions cope with the type constraints of CLIPS. Symbolic and string types are lexemes, which are distinct from the numeric type. These functions perform simple arithmetic on string types.

3. The rules section contains the executable portion of the program. The rule syntax is more accessible than the Horn clause notation used by Prolog. In CLIPS, the required conditions (hypotheses) precede the implication arrow, which points to the right. The rule actions (conclusions) follow the implication arrow. Figure 3 presents the rule syntax. Each rule must be surrounded by parentheses. Each of the rule conditions and actions must be surrounded by parentheses. Single field variables begin with a question mark; for example, "?alfa." Multifield variables begin with a combination dollar-sign question mark; for example, "$?beta." The integrate rule performs a pattern match against the standard integral forms. Execution of this rule means the integration was successful. The integer rule handles the case where the integrand is just an integer. The plusform rule distributes the integral across a sum. The spawn rule activates the transform and heuristic rules when the integrand is a multifield value.

4. The final section is the initial state rule, which contains an assertion for each standard integral form. The final line of the program is the statement of the problem to be solved. The listing contains statements for three integration problems. The code example is constructed to execute one problem assertion at a time. To disable execution of an assertion, insert a comment-tag (semicolon) in front of the assertion. I toggle out two of these using the semicolon comment tag. The uncommented assertion executes.

Program Output

The output corresponds to integrating Figure 4. The dissertation states that the original system successfully accomplished this problem in 18 minutes. I wanted to see how much time my version would take. As you can see from the difference between the start time value and the end time value, the problem took 98 seconds.

I used CLIPS' built-in debugging capabilities to track the integration through its various steps. These are the watch activations and watch facts lines just following the date-time group at the top of the output.

The start of the runstream output shows the initial state rules being asserted. You then see that fact f-16, the problem statement, activates the spawn rule.

You can read down the output listing and watch rules activating and facts asserting until you encounter the "value of integral is" line at the bottom. This is followed by the date time group at the end of the output listing (available electronically).

The difference in the execution times is not the whole story. If my system were fully implemented, execution would take longer due to the system's need to check out more rules. Also my treatment of the algebraic manipulations of the intermediate results is somewhat ad hoc and cursory, and more time would be used here.

James Slagle's Conclusions

In the spirit of beginning the second half-century of the information age, it is illuminating to assess some of the conclusions from this 36-year old dissertation.

Under the heading "Natural Intelligence -- pedagogy," Slagle asserted "the integral calculus teacher should teach in detail each of the algorithm-like and heuristic transformations which [characterize the system]. First the student should learn the algorithm-like transformations which he then could apply to solve suitable problems. Then the student should learn and use the heuristic transformations."

Under the heading "Artificial Intelligence -- computer design," he stated "some computers should be designed with symbol manipulating applications in mind, e. g., much computer time and space could be saved if one computer instruction represented the very frequently used symbol manipulating functions, such as, an f-r chain in LISP."

Conclusion

Slagle's second conclusion was in fact implemented in the 1980s, resulting in special-purpose LISP machines and the Great AI Stampede. This, as we all know, was followed by the Great AI Bust. My experience has taught me that, except in a very few well defined cases -- communications and graphics--hard-wired solutions to software problems are not the way to go.

His first conclusion is as yet unimplemented. So we don't know if it is true or not. I believe it yet holds some promise. An extension of the implementation presented here, together with more explanation capabilities, would serve to walk a calculus student through some meaty examples and save the lecturer a lot of tutoring time.

Regarding the automation of symbolic integration, I conclude that, based on the rapid prototype presented here, calculus lecturers are still telling their students that automation is not the way to go. It looks like coding up the symbolic integration rules is analogous to the implementation of computer chess. It can be implemented in stages and every year it will improve, but there will always be a case it can't handle.

I hope I have convinced you of the usefulness of the CLIPS language, particularly as a rapid prototyping tool. I continue to be amazed by the power and elegance of this system, especially for the price (CLIPS is free).

Since 1984, Dr. Slagle has been Distinguished Professor of Computer Science at the University of Minnesota.

Acknowledgment

Thanks to my associate Brian Lynch, who reviewed this article in detail for me.

DDJ