2.58 Exercise 2.58

Changing to fully-parenthesized prefix notation is simple: In operation-selection procedures for the first argument (e.g. addend), use car.

(define (addend s) (car s))

(define (multiplier p) (car p))

(define (base x) (car x))

Then, inside the operation-construction procedures (e.g. make-sum), swap the positions of the operator and the first argument in the list.

(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))))

(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))))

(define (make-exponentiation base exponent)   (cond ((=number? exponent 0) 1)         ((=number? exponent 1) base)         ((=number? base 0) 0)         ((=number? base 1) 1)         ((and (number? base) (number? exponent))          (expt base exponent))         (else (list base '** exponent))))

Then, inside all of the operation-detection procedures (e.g. sum?), use cadr. You could also generalize this to an operator procedure, but I won’t.

(define (sum? x)   (and (pair? x) (eq? (cadr x) '+)))

(define (product? x)   (and (pair? x) (eq? (cadr x) '*)))

(define (exponentiation? x)   (and (pair? x) (eq? (cadr x) '**)))

To support a more conventional notation with omitted parentheses and an order of operations, we need to parse flat structures into more hierarchically structured forms. One way to think about the fully-parenthesized forms we’ve been dealing with now is as intermediate forms between the natural notation and the computed result. This is essentially the same idea that is behind Lisp’s syntax being representative of the abstract syntax tree.

For example, if we have the expression

we want to turn it into

But is this form a product or a sum? Or is it both? We can use the rules of differentiation to decide on a good answer. It is clear that d/dx 3+x*5 is the same as d/dx 3 + d/dx x*5, 5. However, this is not the same as

Since the rule for sums applies to the expression but the rule for products does not, it is reasonable to say that the expression is a sum and not a product. Intuitively, this is because an expression is a product only if the last operation performed is multiplication. In other words, the type of the expression is the operation in the expression with the least precedence in our order of operations.

To make this and a later task easier, we’ll first define a procedure for finding all of the items before and after a specific element in a list. If the element is not in the list, we will return false. If there are no elements in a group, we will return an empty list for that group.

(define (find-groups item x)   (define (group-iter item before after)     (cond ((null? after) #f)           ((eq? item (car after))            (cons before (cdr after)))           (else            (group-iter item                        (append before (list (car after)))                        (cdr after)))))   (group-iter item '() x))

Since summing is the least precedent operation, sum? is easy to define. We can use find-groups to determine if + is in the expression and if there are elements before and after it.

(define (sum? x)   (let ((groups (find-groups '+ x)))     (if groups         (and (not (null? (car groups)))              (not (null? (cdr groups))))         #f)))

To implement product?, since addition is the operation below multiplication in precedence, we can return true if the expression is a valid multiplication and if the expression is not a sum.

(define (product? x)   (let ((groups (find-groups '* x)))     (if groups         (and (not (null? (car groups)))              (not (null? (cdr groups)))              (not (sum? x)))         #f)))

However, this is obviously a good case for an abstraction. Since the order requirement does not depend on the group requirements, we can create a more general valid-operation? procedure and reimplement sum? and product? in terms of it:

(define (valid-operation? op x)   (let ((groups (find-groups op x)))     (if groups         (and (not (null? (car groups)))              (not (null? (cdr groups))))         #f)))

(define (sum? x)   (valid-operation? '+ x))

(define (product? x)   (and (valid-operation? '* x)        (not (sum? x))))

Exponentiation has precedence over multiplication, so we can implement this check by making sure that an expression is neither a product nor a sum, in addition to being a valid exponentiation.

(define (exponentiation? x)   (and (valid-operation? '** x)        (not (product? x))        (not (sum? x))))

Alternatively, instead of checking the order of operations inside of these procedures, you could define it in the general evaluator – in this case, deriv. If you tested them in order of ascending precedence, you would know, for example, if an expression was being tested as a product, it was definitely not a sum. When dealing with more operations, this becomes a better solutions – you can avoid a good amount of retesting and make your operation-testing procedures simpler. This is what we will be doing, leaving the final procedures as such:

(define (sum? x)   (valid-operation? '+ x))

(define (product? x)   (valid-operation? '* x))

(define (exponentiation? x)   (valid-operation? '** x))

To define the operand-selecting procedures, we can use the information from find-groups. Since this procedure just returns a pair, the new work we have to do is minimal.

(define (addend s) (car (find-groups '+ s)))

(define (augend s) (cdr (find-groups '+ s)))

(define (multiplier p) (car (find-groups '* p)))

(define (multiplicand p) (cdr (find-groups '* p)))

(define (base x) (car (find-groups '** x)))

(define (exponent x) (cdr (find-groups '** x)))

Our procedures for constructing sums, products, and exponentiations still return fully-parenthesized results. This does not need to be fixed. However, we do need to change how variables and numbers are handled, now that both operands are lists by default. An easy way to do this is to add another case to deriv for lists of a single value. This leaves deriv (already with the correct order of operations, by chance) as such:

(define (deriv exp var)   (cond ((number? exp) 0)         ((variable? exp)          (if (same-variable? exp var) 1 0))         ((and (list? exp) (null? (cdr exp)))          (deriv (car exp) var))         ((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))))         ((constant-exponentiation? exp)          (make-product           (make-product            (exponent exp)            (make-exponentiation (base exp)                                 (- (exponent exp) 1)))           (deriv (base exp) var)))         (else          (error "unknown expression type -- DERIV" exp))))

As one small point, we also must change constant-exponentiation? to expect the exponent to be in a list:

(define (constant-exponentiation? x)   (and (exponentiation? x) (number? (car (exponent x)))))

And with this, we’re done.