I posted a couple of days ago about one of the earlier exercises (ex1.33) in SICP. After some discussion with Brent Yorgey on Facebook I had another look at some of the definitions given in the book. Yes, if in doubt, re-read the question! :-)
The issue that needed clarified was whether I could justify treating the null-value argument as a full-blown identity element. The text says:
a null-value that specifies what base value to use when the terms run out.
(It’s worth noting that the definition of combiner also isn’t specified very well: a “procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms”.)
This isn’t abundantly clear but it suggests that null-value is the last element that can be included in the calculation, so that:
is allowed but
is not allowed, because I’m starting with my null-value (ie, 0) and adding the remaining values to it. In this case there is no difference in result. So I needed to find a situation where some element work as an identity on the right but not on the left. Wikipedia to the rescue!
The number 1 as an identity element for exponents if it’s the power but not if it’s the base. Using ^ as an infix exponent function, for any x:
but
We can create a chain of odd-numbered exponents to test our implementations of filter-accumulate:
(define (odd-exponent-chain a b)
(filtered-accumulate odd? expt 1 identity a inc b))
An implementation of filtered-accumulate which cleaves as closely as possible to the definitions should implement (odd-exponent-chain 2 6) as (expt 3 (expt 5 1)).
This conclusion that null-value only works as a right-identity has further repercussions — most of the answers published for iterative version of accumulate are wrong. Why?
(define (accumulate combiner null-value term a next b)
(define (go acc n)
(if (> n b)
acc
(go (combiner acc (term a)) (next n))))
(go null-value a))
The iterative versions always start with the null-value in the accumulator and slowly combine each new term until the end. But the definition above clearly states that null-value is to be combined with the results when there are no more terms left.
This is possible but not as elegant as the recursive solution by a long shot. There’s probably a good way of cleaning it up that I haven’t spotted yet.
(define (accumulate-iter combiner null-value term a next b)
(define (go acc n)
(if (n > b)
(combiner acc null-value)
(go (combiner acc (term n)) (next n))))
(if (a > b)
null-value
(go (term a) (next a))))
Having got this far we realise we can no longer implement filtered-accumulate in terms of accumulate: the first term forms the seed for the accumulator whether it is appropriate or not. In this case we do have to create a new filtered-accumulate which is more powerful than accumulate on its own.
(define (filtered-accumulate-iter filter combiner null-value term a next b)
(define (go acc n)
(if (n > b)
(combiner acc null-value)
(go (combiner acc (term n)) (next n))))
(define (start n)
(cond ((n > b) null-value)
((filter n) (go (term n) (next n)))
(else (start (next n)))))
(start a))
After all this it seems prudent to ask “who’s being pedantic here?” and whether the mistakes identified are the right ones.
- The lack of formal specification of parameters like
null-value encourages assumptions. Most people doing these exercises assumed that null-value works as an identity element per the examples of (+,0) and (*,1). These examples reinforced rather than highlighted the assumptions.
- With this assumption it is possible to implement
filtered-accumulate in terms of accumulate, contra the question. I haven’t found an instance online where someone spotted this mismatch.
- The “obvious” ways of writing the iterative and recursive
accumulate have different semantics if you don’t pay close attention. (Which is another way of saying one of them is wrong.) Hence the problem with making poor assumptions.
- The only way that requires a rewrite of
filtered-accumulate is one that doesn’t assume a left-identity element.
- There is an official tutor’s book published but not available online (presumably to prohibit cheating for universities who use this textbook). So we don’t know what the writers had in mind when they wrote that section.
It’s been an interesting few days of thinking! Many thanks to Brent for making me re-examine the text and my assumptions a further time. I think we got to the bottom of it in the end.