**Exercise 2.56**

Working in top-down fashion we start by adding a rule for taking derivatives of exponentiation expressions to the *deriv* procedure:

```
(define (deriv exp var)
(cond ((number? 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))))
((exponentiation? exp) ; Rule for handling exponentiation.
(make-product (exponent exp)
(make-product (make-exponentiation (base exp)
(- (exponent exp) 1))
(deriv (base exp) var))))
(else (error "unknown expression type --DERIV" exp))))
```

Having done this we can choose a representation for the exponentiation expression data abstraction and implement the predicate *exponentiation?*, the constructor *make-exponentiation*, and the selectors *base* and *exponent*.

The exponentiation expression data abstraction is represented as a list whose first element is the symbol ****, followed by the base and the exponent.

The rule that anything raised to the power *0* is *1* and anything raised to the power *1* is the thing itself is “built” in the constructor *make-exponentiation*.

```
(define (make-exponentiation base exponent)
(cond ((=number? exponent 0) 1)
((=number? exponent 1) base)
(else (list '** base exponent))))
(define (exponentiation? exp)
(and (pair? exp) (eq? (car exp) '**)))
(define (base e)
(cadr e))
(define (exponent e)
(caddr e))
```

**Exercise 2.57**

A sum of more than two terms can be represented as a list whose first element is the symbol *+* followed by the terms.

To implement this new representation we have to redefine the constructor *make-sum* and the selector *augend*. The new version of the selector evaluates to the third element of the list if the list contains three elements, or to the sum of all the elements after the second if the list contains more than three elements.

```
(define (make-sum . args)
(if (>= (length args) 2)
(cons '+ args)
(error "A sum must have at least 2 arguments.")))
(define (augend s)
(if (= (length s) 3)
(caddr s)
(cons '+ (cddr s))))
```

Products of more than two terms can be implemented in a similar way.

Only the definitions of the constructor *make-product* and the selector *multiplicand* have to be changed:

```
(define (make-product . args)
(if (>= (length args) 2)
(cons '* args)
(error "A product must have at least 2 arguments.")))
(define (multiplicand p)
(if (= (length p) 3)
(caddr p)
(cons '* (cddr p))))
```

**Exercise 2.58**

The case where the expressions are fully parenthesized and contain only the operations *+* and *** which always take two arguments is trivial to handle.

Sums can be represented as lists of three elements, the second one of which is the symbol *+*, and the other two are the terms to be added. *Sum?*, *addend*, *augend*, and *make-sum* can be defined as follows:

```
(define (sum? s)
(and (pair? s) (eq? (cadr s) '+)))
(define (addend s)
(car s))
(define (augend s)
(caddr s))
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list a1 '+ a2))))
```

Products are represented in a similar way:

```
(define (product? p)
(and (pair? p) (eq? (cadr p) '*)))
(define (multiplier p)
(car p))
(define (multiplicand p)
(caddr p))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list m1 '* m2))))
```

However, If the expressions are not fully parenthesized, the problem becomes considerably more difficult.

Instead of designing a complete parser we can use the following observation: the “type” of an expression (sum or product) is determined by the last operation that is performed during its evaluation. For example the expression *(x + y * z)* is a sum since we first multiply *y* by *z* and than as a last operation add the result to *x*.

So, in order to determine the “type” of an expression, we can “scan” the expression list examining the top-level operation symbols it contains. If both *+* and *** symbols are found we can safely say that the expression is a sum – the last operation to be performed will be an addition, since multipkication(s) takes precedence and will be performed earlier in the computation.

In case of multiple symbols *+* which addition will be performed last? Here we have several choices. If we assume that the leftmost addition is performed last than we are creating an *right-associative* system with regard to addition. If we assume that the rightmost addition is performed last than we are creating an *left-associative* system. In case of addition (and by the way multiplication) the choice we make is actually irrelevant, since this operation obeys the *associativity law*.

Having the above in mind we can say that an expression list is a sum if it contains the symbol *+* at the top level (not inside a nested list). This allows us to implement the predicate *sum?* as a recursive search:

```
(define (sum? exp)
(cond ((null? exp) #f)
((not (pair? exp)) #f)
((eq? (car exp) '+) #t)
(else (sum? (cdr exp)))))
```

Defining selectors becomes much cleaner if we define two helper procedures: *lhs (left-hand-side)*, and *rhs (right-hand-side)* which take as arguments an expression and an operation symbol and return respectively the expression to the left of the first occurence of the symbol and the expression to the right of it:

```
(define (lhs exp op)
(if (eq? (car exp) op)
'()
(cons (car exp) (lhs (cdr exp) op))))
(define (rhs exp op)
(if (eq? (car exp) op)
(cdr exp)
(rhs (cdr exp) op)))
```

The fact that these procedures stop at the first (leftmost) occurrence of the operation makes the system *right-associative*. For the purposes of the exercise this is adequate, since we are dealing only with addition and multiplication. But if we would like at some later stage to add other operations, including *left-associative* ones, a change in the definitions of *lhs* and *rhs* will be required.

The selectors *addend* and *augend* take respectively the expression to the left and to the right of the operator and remove the list wrapper if the corresponding list consists of only one element:

```
(define (addend s)
(let ((left (lhs s '+)))
(if (= (length left) 1)
(car left)
left)))
(define (augend s)
(let ((right (rhs s '+)))
(if (= (length right) 1)
(car right)
right)))
```

No change in the constructor *make-sum* is required – it can remain the same as in the fully parenthesized version.

The implementation of products is similar to that of sums.

An expression is a product if it contains a top-level symbol ***, and furthermore it is not a sum.

When implementing the predicate *product?*, we can exploit the fact that in our definition of *deriv* we first check if the argument is a sum before applying *product?*. So we can assume that the argument of *product?* will never be a sum and an explicit check for that is not necessary. This makes the code more efficient but less maintainable.

```
(define (product? exp)
(cond ((null? exp) #f)
((not (pair? exp)) #f)
((eq? (car exp) '*) #t)
(else (product? (cdr exp)))))
```

The definitions of the selectors *multiplier* and *multiplicand*, and of the constructor *make-product* follow:

```
(define (multiplier p)
(let ((left (lhs p '*)))
(if (= (length left) 1)
(car left)
left)))
(define (multiplicand p)
(let ((right (rhs p '*)))
(if (= (length right) 1)
(car right)
right)))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list m1 '* m2))))
```