Greetings everyone,
I'm trying to write a program to do symbolic integration. I'm fairly
new to Lisp so I'm having trouble getting started. I don't know Lisp
well enough to know what type of strategy I should attack the problem
with.
Any suggestions? Source code I could look at?
Thanks in advance!
"Jason C." <·········@yahoo.com> wrote in message
·································@posting.google.com...
> Greetings everyone,
>
> I'm trying to write a program to do symbolic integration. I'm fairly
> new to Lisp so I'm having trouble getting started. I don't know Lisp
> well enough to know what type of strategy I should attack the problem
> with.
You might try searching the MIT AI Lab publications archive. More than
likely, the original thesis on STUDENT (?), the original symbolic
integration program done there, is still available.
> Any suggestions? Source code I could look at?
Well, there's always Maxima, the GPL Macsyma clone.
http://maxima.sourceforge.net/
John R. Strohm wrote:
> "Jason C." <·········@yahoo.com> wrote in message
> ·································@posting.google.com...
> > Greetings everyone,
> >
> > I'm trying to write a program to do symbolic integration. I'm fairly
> > new to Lisp so I'm having trouble getting started. I don't know Lisp
> > well enough to know what type of strategy I should attack the problem
> > with.
>
> You might try searching the MIT AI Lab publications archive. More than
> likely, the original thesis on STUDENT (?), the original symbolic
> integration program done there, is still available.
Not STUDENT. That solved word problems ("A man works
three hours a day for four days. How many hours does
he work?").
I'm not sure what the first symbolic integration program
was. There was an early one called SIN, written (most
amusingly) by Moses.
--
Gareth McCaughan ················@pobox.com
.sig under construc
"Gareth McCaughan" <················@pobox.com> wrote in message
···································@g.local...
> John R. Strohm wrote:
> > "Jason C." <·········@yahoo.com> wrote in message
> > ·································@posting.google.com...
> > > Greetings everyone,
> > >
> > > I'm trying to write a program to do symbolic integration. I'm fairly
> > > new to Lisp so I'm having trouble getting started. I don't know Lisp
> > > well enough to know what type of strategy I should attack the problem
> > > with.
> >
> > You might try searching the MIT AI Lab publications archive. More than
> > likely, the original thesis on STUDENT (?), the original symbolic
> > integration program done there, is still available.
>
> Not STUDENT. That solved word problems ("A man works
> three hours a day for four days. How many hours does
> he work?").
>
> I'm not sure what the first symbolic integration program
> was. There was an early one called SIN, written (most
> amusingly) by Moses.
I did the search, here's the results.
----------------------------------------------------------------------------
----
AIM-97
Symbolic Integration
Author[s]: Joel Moses
Date: June 1966
PS Download: ftp://publications.ai.mit.edu/ai-publications/0-499/AIM-097.ps
PDF Download: ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-097.pdf
Abstract: A program has been written which is capable of integrating all but
two of the problems solved by the Siagle's symbollic integration program
SAINT. In contrast to SAINT, it is a purely algorithmic program and it has
achieved running times two to three orders of magnitude faster than SAINT.
This program and some of the basic routines which it uses are described. A
heuristic for integration, called the Edge heuristic, is presented. It is
claimed that this heuristic with the aid of a few algorithms is capapble of
solving all the problems solved by the algorithmic program and many others
as well.
----------------------------------------------------------------------------
----
AIM-97A
Symbolic Integration II
Author[s]: Joel Moses
Date: October 1966
PS Download: ftp://publications.ai.mit.edu/ai-publications/0-499/AIM-097a.ps
PDF Download: ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-097a.pdf
Abstract: In this memo we describe the current state of the integration
program originally described in AI Memo 97 (MAC-M-310). Familiarity with
Memo 97 is assumed. Some of the algorithms described in that memo have been
extended. Certain new algorithms and a simple integration by parts routine
have been added. The current program can integrate all the problems which
were solved by SAINT and also the two problems which were solved. Due to the
addition of a decision procedure the program is capable of identifying
certain integrands (such as e or e/ x) as not integrable in closed form.
----------------------------------------------------------------------------
----
AITR-226
Symbolic Integration
Author[s]: Joel Moses
Date: September 1967
PS Download: ftp://publications.ai.mit.edu/ai-publications/0-499/AITR-226.ps
PDF Download: ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-226.pdf
Abstract: SIN and SOLDIER are heuristic programs in LISP which solve
symbolic integration problems. SIN (Symbolic INtegrator) solves indefinite
integration problems at the difficulty approaching those in the larger
integral tables. SIN contains several more methods than are used in the
previous symbolic integration program SAINT, and solves most of the problems
attempted by SAINT in less than one second. SOLDIER (SOLution of Ordinary
Differential Equations Routine) solves first order, first degree ordinary
differential equations at the level of a good college sophomore and at an
average of about five seconds per problem attempted. The differences in
philosophy and operation between SAINT and SIN are described, and
suggestions for extending the work presented are made.
----------------------------------------------------------------------------
----
·········@yahoo.com (Jason C.) writes:
> Greetings everyone,
>
> I'm trying to write a program to do symbolic integration. I'm fairly
> new to Lisp so I'm having trouble getting started. I don't know Lisp
> well enough to know what type of strategy I should attack the problem
> with.
>
> Any suggestions?
For starting read the chapter 8 from paradigms of Artificial
Intelligense Programming from Peter Norvig
> Source code I could look at?
How about checking out maxima?
http://maxima.sourceforge.net/
Regards
Friedrich
Hi Jason,
There's a chapter in building problem solvers (Forbus & De Kleer) that
talks about using a truth maintenence system to do symbolic integration.
There's a fair bit of code in there too. But far from production quality
stuff. Greater emphasis on instruction and clarity, after all.
Sunil
Jason C. wrote:
> Greetings everyone,
>
> I'm trying to write a program to do symbolic integration. I'm fairly
> new to Lisp so I'm having trouble getting started. I don't know Lisp
> well enough to know what type of strategy I should attack the problem
> with.
>
> Any suggestions? Source code I could look at?
>
> Thanks in advance!
Hi Jason,
You might consider looking at building problem solvers by Forbus and De
Kleer. In there is an example using a truth maintenence system for doing
symbolic integration. Lots of code, but with emphasis on simplicity and
clarity for instructional purposes.
Sunil
Jason C. wrote:
> Greetings everyone,
>
> I'm trying to write a program to do symbolic integration. I'm fairly
> new to Lisp so I'm having trouble getting started. I don't know Lisp
> well enough to know what type of strategy I should attack the problem
> with.
>
> Any suggestions? Source code I could look at?
>
> Thanks in advance!
"Jason C." <·········@yahoo.com> wrote in message
·································@posting.google.com...
> Greetings everyone,
>
> I'm trying to write a program to do symbolic integration. I'm fairly
> new to Lisp so I'm having trouble getting started. I don't know Lisp
> well enough to know what type of strategy I should attack the problem
> with.
>
> Any suggestions? Source code I could look at?
>
> Thanks in advance!
Check out Peter Novig's book it has a chapter about implementing a subst of
Macsyma in ANSI CL, and deals with both symbolic diff. and symbolic
integration.
"Why bother 2 learn math when U can have UR computer do it 4 U." Anon. Math
Student
·········@yahoo.com (Jason C.) wrote in message news:<····························@posting.google.com>...
> Greetings everyone,
>
> I'm trying to write a program to do symbolic integration. I'm fairly
> new to Lisp so I'm having trouble getting started. I don't know Lisp
> well enough to know what type of strategy I should attack the problem
> with.
>
> Any suggestions? Source code I could look at?
>
> Thanks in advance!
Ok thanks to your guys' help, I'm well on my way :) I ran into a
roadblock along the way though. When the user inters an integration
problem it's entered as such:
(integrate <variable to integrate with respect to> <integration
problem>)
i.e.: ('x '^ 'x 2) = S (x^2) dx.
The official definition is: (defun integrate (respect &rest integral)
)
What I'm trying to do is compare the user input against different
forms of integrals. So using the above example, I'm trying to do
this:
(if (equal respect (format t "(^ ~a ~a)" respect (last integral)))
(print "It works!")
Theoretically, if the user formats his problem correctly, the if
statement should recognize it and print "It works!". However this is
not the case. Once again I'll state that I am new to Lisp and I
realize I'm probably doing something trivial wrong. Can you catch my
mistake?
Also I'd like to add that if any of you see a different, *better* way
to do what I'm doing, feel free to comment :)
Thanks again for all your input thus far. The Lisp community is
really great!
"Jason C." wrote:
> Ok thanks to your guys' help, I'm well on my way :) I ran into a
> roadblock along the way though. When the user enters an integration
> problem it's entered as such:
>
> (integrate <variable to integrate with respect to> <integration
> problem>)
>
> i.e.: ('x '^ 'x 2) = S (x^2) dx.
>
> The official definition is: (defun integrate (respect &rest integral))
>
> What I'm trying to do is compare the user input against different
> forms of integrals. So using the above example, I'm trying to do
> this:
>
> (if (equal respect (format t "(^ ~a ~a)" respect (last integral)))
> (print "It works!"))
>
> Theoretically, if the user formats his problem correctly, the if
> statement should recognize it and print "It works!". However this is
> not the case. Once again I'll state that I am new to Lisp and I
> realize I'm probably doing something trivial wrong. Can you catch my
> mistake?
First, you missed off the last parenthesis, but I'm
guessing you didn't do that in the real code. Second,
you didn't indent it right, but that isn't why it
doesn't work. I've fixed both of those above. :-)
Now:
1. What sort of object is RESPECT? Is it a string? a symbol?
a list?
2. What do you think (FORMAT T "..." ...) returns? Caution:
what it *returns* need not be the same as what it *prints*.
3. Is RESPECT really the thing you want to be checking anyway?
I'd have expected it to be INTEGRAL or something.
4. I may be missing some context, but I'd expect you to find
this whole thing easier if you get users to specify their
integrands in the usual Lisp s-expression form. So, e.g.,
"integrate x^2 w.r.t. x" might be entered as
(x (^ x 2))
and "integrate sin(x^3)+3 w.r.t. x" as
(x (+ (sin (^ x 3)) 3))
It's possible that what you're doing is really equivalent
to that except that you've implicitly stripped off the
outer layer of parentheses from the integrand. It's not
entirely clear to me.
5. What do you think the function LAST does? For instance,
what do you expect this to return?
(last '(x ^ x 2))
Ponder these matters, and some degree of enlightenment may dawn...
--
Gareth McCaughan ················@pobox.com
.sig under construc
"Gareth McCaughan" <················@pobox.com> wrote in message
···································@g.local...
> "Jason C." wrote:
>
> > Ok thanks to your guys' help, I'm well on my way :) I ran into a
> > roadblock along the way though. When the user enters an integration
> > problem it's entered as such:
> >
> > (integrate <variable to integrate with respect to> <integration
> > problem>)
> >
> > i.e.: ('x '^ 'x 2) = S (x^2) dx.
> >
> > The official definition is: (defun integrate (respect &rest integral))
> >
> > What I'm trying to do is compare the user input against different
> > forms of integrals. So using the above example, I'm trying to do
> > this:
> >
> > (if (equal respect (format t "(^ ~a ~a)" respect (last integral)))
> > (print "It works!"))
> >
> > Theoretically, if the user formats his problem correctly, the if
> > statement should recognize it and print "It works!". However this is
> > not the case. Once again I'll state that I am new to Lisp and I
> > realize I'm probably doing something trivial wrong. Can you catch my
> > mistake?
>
> First, you missed off the last parenthesis, but I'm
> guessing you didn't do that in the real code. Second,
> you didn't indent it right, but that isn't why it
> doesn't work. I've fixed both of those above. :-)
>
> Now:
>
> 1. What sort of object is RESPECT? Is it a string? a symbol?
> a list?
Respect would have to be a var. if it were a symbol it would be 'respect.
The var. could hold a string symbol or list.
(setf respect "respect") ;; string
(setf respect 'respect) ;; symbol
(setf respect 2) ;; number
(setf respect #'(lambda (x) (* x x))) ;; a function.
I can't tell what the var holds from your code.
>
> 2. What do you think (FORMAT T "..." ...) returns? Caution:
> what it *returns* need not be the same as what it *prints*.
>
Format on my system usually returns two values what it prints, and nil to
tell you it finished printing. If you down capture multiple-varibles the
function will see nil.
> 3. Is RESPECT really the thing you want to be checking anyway?
I don't know.
> I'd have expected it to be INTEGRAL or something.
>
> 4. I may be missing some context, but I'd expect you to find
> this whole thing easier if you get users to specify their
> integrands in the usual Lisp s-expression form. So, e.g.,
> "integrate x^2 w.r.t. x" might be entered as
>
> (x (^ x 2))
>
> and "integrate sin(x^3)+3 w.r.t. x" as
>
> (x (+ (sin (^ x 3)) 3))
>
> It's possible that what you're doing is really equivalent
> to that except that you've implicitly stripped off the
> outer layer of parentheses from the integrand. It's not
> entirely clear to me.
>
You could use . lists
((^ x x) . x)
((sin x) . x)
((+ (^ x 2) (^ y 2)) . (x y))
In box notation
[[(^ x x)]]==pointer==>[[x]]
car of List cdr of List
> 5. What do you think the function LAST does? For instance,
> what do you expect this to return?
>
> (last '(x ^ x 2))
It returns 2.
>
> Ponder these matters, and some degree of enlightenment may dawn...
>
Most people can help you with the Lisp aspects of your
code--weather or not it will help you implement you
algorithm is an other story.
> --
> Gareth McCaughan ················@pobox.com
> .sig under construc
Michael Israel wrote:
[I said to someone calling himself "Jason C.":]
> > 1. What sort of object is RESPECT? Is it a string? a symbol?
> > a list?
> Respect would have to be a var. if it were a symbol it would be 'respect.
[etc]
I think you may have mistaken the intent of my questions.
I wasn't asking because I don't know the answers. I wasn't
asking because I think they're helpful questions for
everyone. I was asking because I think answering them
would help Jason. :-)
However, some comments on your comments:
> The var. could hold a string symbol or list.
When I asked "What sort of object is RESPECT?" I meant:
"what sort of object is the value of the variable RESPECT?".
I'm sorry if that wasn't clear.
> > 2. What do you think (FORMAT T "..." ...) returns? Caution:
> > what it *returns* need not be the same as what it *prints*.
> >
> Format on my system usually returns two values what it prints, and nil to
> tell you it finished printing. If you don't capture multiple-varibles the
> function will see nil.
If FORMAT on your system does that, then it is broken.
> > 4. I may be missing some context, but I'd expect you to find
> > this whole thing easier if you get users to specify their
> > integrands in the usual Lisp s-expression form. So, e.g.,
> > "integrate x^2 w.r.t. x" might be entered as
> >
> > (x (^ x 2))
...
> > It's possible that what you're doing is really equivalent
> > to that except that you've implicitly stripped off the
> > outer layer of parentheses from the integrand. It's not
> > entirely clear to me.
>
> You could use . lists
> ((^ x x) . x)
My "implicitly stripped parentheses" conjecture is
equivalent except that it puts the CAR and the CDR
the other way around.
> > 5. What do you think the function LAST does? For instance,
> > what do you expect this to return?
> >
> > (last '(x ^ x 2))
> It returns 2.
Actually, it doesn't. But I suspect Jason expects it
to return something other than (1) 2 and (2) the thing
it actually returns.
--
Gareth McCaughan ················@pobox.com
.sig under construc
Michael Israel wrote:
>
> > 2. What do you think (FORMAT T "..." ...) returns? Caution:
> > what it *returns* need not be the same as what it *prints*.
> >
> Format on my system usually returns two values what it prints, and nil to
> tell you it finished printing. If you down capture multiple-varibles the
> function will see nil.
Strictly speaking, the previous is incorrect, FORMAT does not return
multiple values. (whatever it prints is a side effect, not a returned
value)
CLHS:
result---if destination is non-nil, then nil; otherwise, a string.
> > 5. What do you think the function LAST does? For instance,
> > what do you expect this to return?
> >
> > (last '(x ^ x 2))
> It returns 2.
Are you quite sure? My machine doesn't seem to agree.
--
> > > 5. What do you think the function LAST does? For instance,
> > > what do you expect this to return?
> > >
> > > (last '(x ^ x 2))
> > It returns 2.
>
> Are you quite sure? My machine doesn't seem to agree.
>
Mine returned
(2)
You need (first (last '(x^x 2)))
to get 2.
I guess I forgot to type the perens.
> --