Ex 2.56

The selectors for exponentiation don’t present much of a problem. Using the suggested notation, you’d want the expression to look like (** base exponent), and the selectors use car and cdr to get the proper part of that. The constructor should have the built-in rules that handle powers of 0 and 1, which is just a cons statement. Following the lead of make-sum and make-product, expressions that are purely numerical can be simplified using the built-in exponentiation operation (expt in my version).

Implementing the power rule is then a matter of converting the formula into the equivalent expression, using make-product and make-exponent as necessary. There’s the partially recursive element of the rule as well, in which we must take the derivative of u, which is just the base of the original exponentiation expression.

Ex 2.57

I’ll describe the process for make-sum only, since make-product follows the exact same pattern.

In order to make sums with an arbitrary number of arguments, we need to use dotted-tail notation. The first step is to put that in make-sum, so that our expressions can look the same as before. This ends up splitting the expression nicely: the first term is a single expression, and the rest is a list. In order to process that list, we need to write make-sum-with-list, which will run down the list of terms and recursively build a sum expression. There’s a bit of simplification that can happen by ungrouping the terms, although it’s not that easy to do this for every expression.

I find the hint in this problem about the augend and addend to be perplexing. Either they are confusing the terms, or they have an alternate recursive approach in mind that I’m not catching. As it is, augend has no need to change and will be the first summing term, and it is the addend that is built from the sum of the remaining terms. It’s interesting that this implementation is one of the few times that the term ‘augend’ actually has application, since the first term is distinct from the other addends in our program.

Ex 2.58

As the text describes, this change only involves the constructors and selectors, and we will not need to alter deriv at all to handle the new format.

The first part is just a repositioning of terms. If we know we will only ever see two terms in an expression, properly parenthesized, then every expression is a list containing three items: the ‘left-hand side’ (which may be number, symbol/variable, or a list), the operator in the middle, and then the ‘right-hand side’, which is similar to the first item in the list. The selectors then simply pick the corresponding element. The constructors change just slightly in the same way.

Part b is indeed a much more difficult task. We can no longer process our terms straight through from left to right. If we encounter a term ‘term’ here means ‘not an operator’ in our expression, we don’t yet know if it belongs with the operator to its left, or one to its right. Therefore, the process will look ahead until it finds the next operator, and only then is able to decide how to process that term.

With only addition and multiplication it’s about as simple as that. We don’t need to check more than one operator ahead. For example, in (a + b * c * d), we must ensure that b gets multiplied by c and not added to a, but it doesn’t really matter that the operator following c is multiplication as well (although having ‘chunked’ b * c, we still must continue to compare the operators to its left and its right). The multiple-argument versions of the selectors and constructors of 2.57 are also required to make the expressions natural. The main alteration to them is to locate the operator and group terms appropriately on its left and right.

That said, I actually implemented a more generic, but a bit more complicated system, in which every operator has a ranked precedence (determined by a prec procedure). When processing terms, it then becomes necessary to keep looking ahead at every step until we find two terms and an operator that have higher precedence than the other terms around them. Having processed any higher-precedence terms, we can back out, continuing to check the operators on either side.

One thing this generic approach allows is that it’s relatively simple to add new operators. As a bonus to this exercise, I added exponentiation as an infix operation. I don’t really wish to go into much more detail on how it all works, but you want to take a look at it, it’s in the solutions file.

Solutions 2.3.2