Description
1 Symbolic differentiation 1.1 Polynomial expressions
In this assignment you will need to implement the tools for symbolic differentiation of expressions. Symbolic differentiation computes derivative of a given expression symbolically (i.e. as an expression), for example, given (1 + 2x)(x + y) the computed partial derivative with respect to variable y is 1 + 2x.
For start we will consider only expressions involving numeric constants, variables, binary addition and multiplication. The expressions will be given as valid Racket terms, for example:
‘(+ 1 x)
‘(* 2 y) ‘(*(+1(*2x))(+xy))
; 1 + x
; 2y
; (1+2x)(x+y)
To work with these expressions, you need to be able to traverse its structure. You can use number? predicate to check whether an expression is a number.
Exercise 1.1 (⋆). Implement the following predicates and functions:
(define (variable? expr) …)
(define (sum? expr) …)
(define (summand-1 expr) …)
(define (summand-2 expr) …)
(define (product? expr) …)
(define (multiplier-1 expr) …) ; extract first multiplier from a product (define (multiplier-2 expr) …) ; extract second multipler from a product
; check whether a given expression is a variable ; check whether a given expression is a sum ; extract first summand from a sum ; extract second summand from a sum
; check whether a given expression is a product
1
Now, whenever we have an expression we can check what kind of expression we have and decompose it into its constituent subexpressions.
Exercise 1.2 (⋆). Implement a recursive function derivative that computes a symbolic derivative of a given expression with respect to a given variable. At this point you are not expected to simplify expressions after differentiation:
(derivative ‘(+ 1 x) ‘x) ; ‘(+ 0 1)
(derivative ‘(* 2 y) ‘y) ; ‘(+ (* 0 y) (* 2 1))
(derivative ‘(* (+ x y) (+ x (+ x x))) ‘x)
; ‘(+ (* (+ 1 0) (+ x (+ x x))) (* (+ x y) (+ 1 (+ 1 1))))
Exercise 1.3 (⋆⋆). Implement a recursive function simplify that simplifies an expression using the following rules:
1. 0+e=eforallexpressionse,
2. e+0=eforallexpressionse,
3. 1∗e=eforallexpressionse,
4. e∗1=eforallexpressionse,
5. 0∗e=0forallexpressionse,
6. e∗0=0forallexpressionse,
7. sums and products of numeric constants should be computed.
Examples:
(simplify ‘(+ 0 1)) ;1
(simplify ‘(+ (* 0 y) (* 2 1))) ;2
(simplify ‘(+ (* (+ 1 0) (+ x (+ x x))) (* (+ x y) (+ 1 (+ 1 1))))) ; ‘(+ (+ x (+ x x)) (* (+ x y) 3))
Hint: it might be easier to implement a non-recursive function simplify-at-root that only simplifies expression if it matches exactly left-hand side of one of the rules. Then use simplify-at-root to implement a recursive function simplify.
Exercise 1.4 (⋆ ⋆ ⋆). Implement function normalize that simplifies any expression down to a poly- nomial of its variables. To achieve that you need to open parentheses using distributive property of multiplication over addition: x(y + z) = xy + xz. You will also need to simplify similar terms: xy + 2yz + 3xy = 4xy + 2yz.
Exercise 1.5 (⋆). Implement a recursive function to-infix that converts an expression into an infix form:
(to-infix ‘(+ (+ x (+ x x)) (* (+ x y) 3)) ; ‘((x + (x + x)) + ((x + y) * 3)
2
1.2 More functions
Exercise 1.6 (⋆). Update functions derivative and simplify to support the following functions (here e, e1 and e2 denote arbitary expressions):
1. exponentiation: ee2 1
2. trigonometric functions: sin e, cos e, tan e
3. natural logarithm: log e
Exercise 1.7 (⋆⋆). Update functions derivative and simplify to support the following polyvariadic1
sums and products:
(derivative ‘(+ 1 x y (* x y z)) ‘x)
; ‘(+ 0 1 0 (+ (* 1 y z) (* x 0 z) (* x y 0)))
(simplify ‘(+ 0 1 0 (+ (* 1 y z) (* x 0 z) (* x y 0)))) ; ‘(+ 1 (* y z))
1.3 Gradient
Exercise 1.8 (⋆⋆). Implement a function variables-of that returns a (sorted) list of distinct variables used in a given expression:
(variables-of ‘(+ 1 x y (* x y z))) ; ‘(x y z)
Exercise 1.9 (⋆⋆). Implement a function gradient that returns a gradient of a multivariable expres- sion (given explicitly the list of variables). Recall that the gradient ∇f is a vector consisting of partial
derivatives:
∂e ∂e ∂e⊤ ∇e= ∂x ∂x ···∂x
12n Represent gradient in Racket as a list of expressions:
(gradient ‘(+ 1 x y (* x y z)) ‘(x y z)) ; ‘((+ 1 (* y z)) (+ 1 (* x z)) (* x y))
1“polyvariadic” means that a function or operator can support arbitrary number of arguments; for example, + in Racket can accept as many arguments, as user wants: (+ 1 2 3 4) computes to 1+2+3+4 = 10.
3
