I'm a beginner in LISP programming. I find this extremely difficult. This
is only the 2nd programming assignment for this quarter, and I"m already
stuck. I have absolutely no idea how to start, and what kind of approach I
should take.
================
I. Overview
================
Write a scheme program to perform symbolic differentiation
of algebraic expressions, as described in Abelson et. al. Chapter 2
pp. 142--153.
For the purposes of this assignment, an algebraic expression is
any expression whose only primitive procedures are +, *, -, /, and ** (expt).
You may assume all exponents are constant; contrary to what was first
announced in lecture, we will *not* differentiate exponentials
(expressions including terms of the form 2**x, 3**x, etc.).
We *will* differentiate polynomials (i.e. sums of constant multiples
of terms only of the form x**2, x**3, etc.), and quotients of
polynomials.
For example,
(define exp2 '(/ (+ (* 2 (** x 2)) (* 5 (** x 3))) (- (** x 2) (** x 3))) )
is a scheme-legal representation of the algebraic expression
more commonly denoted as
2*x**2 + 5*x**3
exp2 = ----------------- ;
x**2 - x**3
whose derivative is calculated as ...
> (deriv exp2 'x)
(/ (- (* (+ (* 2 (* 2 x)) (* 5 (* 3 (** x 2)))) (- (** x 2) (** x 3)))
(* (+ (* 2 (** x 2)) (* 5 (** x 3))) (- (* 2 x) (* 3 (** x 2)))))
(** (- (** x 2) (** x 3)) 2))
... which is a mostly unsimplified representation (to which I
have manually added some indentation) of the derivative
of "exp2" obtained by following the quotient rule:
(2*x**2 + 5*x**3)'*(x**2 - x**3) - (2*x**2 + 5*x**3)*(x**2 - x**3)'
exp2' = -------------------------------------------------------------------
(x**2 - x**3)**2
(4*x + 15*x**2)*(x**2 - x**3) - (2*x**2 + 5*x**3)*(2*x - 3*x**2)
= ----------------------------------------------------------------
(x**2 - x**3)**2.
Note that the following scheme expressions are *not* algebraic expressions;
(sin x), (cos x), (expt 2 x), (log x) .
As in the text, you are *not* required to express answers
in simplest form; however, your code should automatically simplify trivial
binary numerical expressions (e.g., (* 3 9)) as well as all trivial symbolic
expressions of the form (* e 1), (+ e 0), (/ e 1), (- 0 e), and (- e 0),
where in this context "e" denotes an arbitrary algebraic expression.
You are free to copy verbatim any code appearing in the text.
To earn full credit, your program must implement the
"extensions" described in exercises 2.56 - 2.58 on pp. 150-151.
Exercise 58 is significantly harder than 56 and 57.
One way to do it is to implement recursive procedures that convert
infix expressions ( x + 3*x**2 ) to prefix expressions (+ x (* 3 (** x 2)))
and back again. More suggestions on 58 will be posted here soon.
In addition to the extensions in exercises 2.56-2.58, your program
must be able to handle differences (subtraction)
and quotients (division) of algebraic expressions.
Some important mathematical rules to know for finding the
derivative f' of a function f follow. Note that the notation
for these rules is "mathematical"; it is not the same notation
you will use in Scheme.
Let a, b, and n denote arbitrary constants (numbers).
Let f, and g denote functions of (or algebraic expressions in) x.
We are differentiating expressions with respect to variable x.
x**n denotes "x raised to the power n";
"a*x**n" means a * ( x**n ), or in Scheme, (* a (expt x n)).
i) a' = 0
ii) (x**n)' = n*x**(n-1)
iii) (f + g)' = f' + g'
iv) (a*f)' = a*f'
v) (f*g)' = f'*g + f*g'
vi) (f/g)' = (f'*g - f*g') / (g*g) (assuming g not zero)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Well, I'd start by reading the chapter in the referenced book from which the
problem is taken. Even though it's not in Common Lisp, it gives a fairly
good overview of symbolic differentiation. Or check out Norvig's book,
"Paradigms of Artificial Intelligence Programming : Case Studies in Common
Lisp": http://www.amazon.com/exec/obidos/ASIN/1558601910
It goes into exhaustive detail.
--
Frank A. Adrian
First DataBank
············@firstdatabank.com (W)
······@europa.com (H)
This message does not necessarily reflect those of my employer,
its parent company, or any of the co-subsidiaries of the parent
company.
········@my-dejanews.com wrote in message
<············@nnrp1.dejanews.com>...
>I'm a beginner in LISP programming. I find this extremely difficult. This
>is only the 2nd programming assignment for this quarter, and I"m already
>stuck. I have absolutely no idea how to start, and what kind of approach I
>should take.
>
>================
>I. Overview
>================
>Write a scheme program to perform symbolic differentiation
>of algebraic expressions, as described in Abelson et. al. Chapter 2
>pp. 142--153.
>
>For the purposes of this assignment, an algebraic expression is
>any expression whose only primitive procedures are +, *, -, /, and **
(expt).
>You may assume all exponents are constant; contrary to what was first
>announced in lecture, we will *not* differentiate exponentials
>(expressions including terms of the form 2**x, 3**x, etc.).
>We *will* differentiate polynomials (i.e. sums of constant multiples
>of terms only of the form x**2, x**3, etc.), and quotients of
>polynomials.
>
>For example,
>
>(define exp2 '(/ (+ (* 2 (** x 2)) (* 5 (** x 3))) (- (** x 2) (** x
3))) )
>
>is a scheme-legal representation of the algebraic expression
>more commonly denoted as
>
> 2*x**2 + 5*x**3
> exp2 = ----------------- ;
> x**2 - x**3
>
>whose derivative is calculated as ...
>
>> (deriv exp2 'x)
>(/ (- (* (+ (* 2 (* 2 x)) (* 5 (* 3 (** x 2)))) (- (** x 2) (** x 3)))
> (* (+ (* 2 (** x 2)) (* 5 (** x 3))) (- (* 2 x) (* 3 (** x 2)))))
> (** (- (** x 2) (** x 3)) 2))
>
>... which is a mostly unsimplified representation (to which I
>have manually added some indentation) of the derivative
>of "exp2" obtained by following the quotient rule:
>
> (2*x**2 + 5*x**3)'*(x**2 - x**3) - (2*x**2 + 5*x**3)*(x**2 -
x**3)'
> exp2'
-------------------------------------------------------------------
> (x**2 - x**3)**2
>
>
> (4*x + 15*x**2)*(x**2 - x**3) - (2*x**2 + 5*x**3)*(2*x - 3*x**2)
> = ----------------------------------------------------------------
> (x**2 - x**3)**2.
>
>Note that the following scheme expressions are *not* algebraic expressions;
> (sin x), (cos x), (expt 2 x), (log x) .
>
>As in the text, you are *not* required to express answers
>in simplest form; however, your code should automatically simplify trivial
>binary numerical expressions (e.g., (* 3 9)) as well as all trivial
symbolic
>expressions of the form (* e 1), (+ e 0), (/ e 1), (- 0 e), and (- e 0),
>where in this context "e" denotes an arbitrary algebraic expression.
>
>You are free to copy verbatim any code appearing in the text.
>To earn full credit, your program must implement the
>"extensions" described in exercises 2.56 - 2.58 on pp. 150-151.
>Exercise 58 is significantly harder than 56 and 57.
>One way to do it is to implement recursive procedures that convert
>infix expressions ( x + 3*x**2 ) to prefix expressions (+ x (* 3 (** x 2)))
>and back again. More suggestions on 58 will be posted here soon.
>
>In addition to the extensions in exercises 2.56-2.58, your program
>must be able to handle differences (subtraction)
>and quotients (division) of algebraic expressions.
>
>Some important mathematical rules to know for finding the
>derivative f' of a function f follow. Note that the notation
>for these rules is "mathematical"; it is not the same notation
>you will use in Scheme.
>
>Let a, b, and n denote arbitrary constants (numbers).
>Let f, and g denote functions of (or algebraic expressions in) x.
>We are differentiating expressions with respect to variable x.
>x**n denotes "x raised to the power n";
>"a*x**n" means a * ( x**n ), or in Scheme, (* a (expt x n)).
>
> i) a' = 0
> ii) (x**n)' = n*x**(n-1)
> iii) (f + g)' = f' + g'
> iv) (a*f)' = a*f'
> v) (f*g)' = f'*g + f*g'
> vi) (f/g)' = (f'*g - f*g') / (g*g) (assuming g not zero)
>
>
>-----------== Posted via Deja News, The Discussion Network ==----------
>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
[Crossposted from comp.lang.lisp to comp.lang.scheme. F-t: c.l.s]
········@my-dejanews.com writes:
[Homework assignment, see <············@nnrp1.dejanews.com>]
First, have you asked your TA or fellow students yet? These things
are generally easier to explain face to face.
Second, when posting homework to a news groups you should try to give
some indication that you have tried to solve this on your own. Code
fragments, thought fragments, whatever.
Third, Scheme questions are better put in comp.lang.scheme than
comp.lang.lisp. Any answers you get on c.l.lisp will tend to have its
code written in different ways than what you are used to from your
class.
Fourth, try to chose a better subject line than 'Lisp programming'.
Almost _all_ the articles here are about Lisp programming.
To the problem itself: I think this will be easier if you divide the
problem into two: First diffrenciate, then simplify. Each part is
solved by picking the expression into pieces using car and cdr, then
putting the results back together again.
A Lisp/Scheme expression is simply a list like any other list. The
first element (the car) is the function, the rest of the elements (the
cdr) is the arguments to that function. Use the car to decide what to
do with the expression, then call recursively on the elements of the
cdr and combine the results.
When simplifying, remember to simplify the subexpressions _before_
deciding if the full expression can be simplified.
Hope this helps.
Stig Hemmer,
Jack of a Few Trades.
I think the solution you are looking for is something like this:
(define (deriv exp var)
(cond ((constant? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))))
(define (constant? x) (number? x))
(define (variable? x) (symbol? x))
(define (atom? x) (or (number? x) (symbol? x)))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))
(define (sum? x)
(if (not (atom? x)) (eq? (car x) '+) nil))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (product? x)
(if (not (atom? x)) (eq? (car x) '*) nil))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
;;; Better versions of make-sum and make-product
(define (make-sum a1 a2)
(cond ((and (number? a1) (number? a2)) (+ a1 a2))
((number? a1) (if (= a1 0) a2 (list '+ a1 a2)))
((number? a2) (if (= a2 0) a1 (list '+ a1 a2)))
(else (list '+ a1 a2))))
(define (make-product m1 m2)
(cond ((and (number? m1) (number? m2)) (* m1 m2))
((number? m1)
(cond ((= m1 0) 0)
((= m1 1) m2)
(else (list '* m1 m2))))
((number? m2)
(cond ((= m2 0) 0)
((= m2 1) m1)
(else (list '* m1 m2))))
(else (list '* m1 m2))))
········@my-dejanews.com wrote:
> I'm a beginner in LISP programming. I find this extremely difficult. This
> is only the 2nd programming assignment for this quarter, and I"m already
> stuck. I have absolutely no idea how to start, and what kind of approach I
> should take.
>
> ================
> I. Overview
> ================
> Write a scheme program to perform symbolic differentiation
> of algebraic expressions, as described in Abelson et. al. Chapter 2
> pp. 142--153.
>
> For the purposes of this assignment, an algebraic expression is
> any expression whose only primitive procedures are +, *, -, /, and ** (expt).
> You may assume all exponents are constant; contrary to what was first
> announced in lecture, we will *not* differentiate exponentials
> (expressions including terms of the form 2**x, 3**x, etc.).
> We *will* differentiate polynomials (i.e. sums of constant multiples
> of terms only of the form x**2, x**3, etc.), and quotients of
> polynomials.
>
> For example,
>
> (define exp2 '(/ (+ (* 2 (** x 2)) (* 5 (** x 3))) (- (** x 2) (** x 3))) )
>
> is a scheme-legal representation of the algebraic expression
> more commonly denoted as
>
> 2*x**2 + 5*x**3
> exp2 = ----------------- ;
> x**2 - x**3
>
> whose derivative is calculated as ...
>
> > (deriv exp2 'x)
> (/ (- (* (+ (* 2 (* 2 x)) (* 5 (* 3 (** x 2)))) (- (** x 2) (** x 3)))
> (* (+ (* 2 (** x 2)) (* 5 (** x 3))) (- (* 2 x) (* 3 (** x 2)))))
> (** (- (** x 2) (** x 3)) 2))
>
> ... which is a mostly unsimplified representation (to which I
> have manually added some indentation) of the derivative
> of "exp2" obtained by following the quotient rule:
>
> (2*x**2 + 5*x**3)'*(x**2 - x**3) - (2*x**2 + 5*x**3)*(x**2 - x**3)'
> exp2' = -------------------------------------------------------------------
> (x**2 - x**3)**2
>
> (4*x + 15*x**2)*(x**2 - x**3) - (2*x**2 + 5*x**3)*(2*x - 3*x**2)
> = ----------------------------------------------------------------
> (x**2 - x**3)**2.
>
> Note that the following scheme expressions are *not* algebraic expressions;
> (sin x), (cos x), (expt 2 x), (log x) .
>
> As in the text, you are *not* required to express answers
> in simplest form; however, your code should automatically simplify trivial
> binary numerical expressions (e.g., (* 3 9)) as well as all trivial symbolic
> expressions of the form (* e 1), (+ e 0), (/ e 1), (- 0 e), and (- e 0),
> where in this context "e" denotes an arbitrary algebraic expression.
>
> You are free to copy verbatim any code appearing in the text.
> To earn full credit, your program must implement the
> "extensions" described in exercises 2.56 - 2.58 on pp. 150-151.
> Exercise 58 is significantly harder than 56 and 57.
> One way to do it is to implement recursive procedures that convert
> infix expressions ( x + 3*x**2 ) to prefix expressions (+ x (* 3 (** x 2)))
> and back again. More suggestions on 58 will be posted here soon.
>
> In addition to the extensions in exercises 2.56-2.58, your program
> must be able to handle differences (subtraction)
> and quotients (division) of algebraic expressions.
>
> Some important mathematical rules to know for finding the
> derivative f' of a function f follow. Note that the notation
> for these rules is "mathematical"; it is not the same notation
> you will use in Scheme.
>
> Let a, b, and n denote arbitrary constants (numbers).
> Let f, and g denote functions of (or algebraic expressions in) x.
> We are differentiating expressions with respect to variable x.
> x**n denotes "x raised to the power n";
> "a*x**n" means a * ( x**n ), or in Scheme, (* a (expt x n)).
>
> i) a' = 0
> ii) (x**n)' = n*x**(n-1)
> iii) (f + g)' = f' + g'
> iv) (a*f)' = a*f'
> v) (f*g)' = f'*g + f*g'
> vi) (f/g)' = (f'*g - f*g') / (g*g) (assuming g not zero)
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own