Lab 23: Accumulating Numbers

Implement this lab with the Intermediate Student Language with Lambda.

Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.

Choose the initial Head and Hands, and get started!

Busy Work

By the age of 8 Johann Carl Friedrich Gauss was a troublesome student. To stay his mewling, his teacher came up with a tedious task for him to perform: adding together the numbers 1 through 100. Much to the teacher’s chagrin, Gauss responded with 5050 after only a moment’s thought.

Of course, we can easily perform the same task.

Ex 1: Define a function sum-all that returns the sum of the natural numbers from 1 to the given natural number n. Write it using the standard structural template over the natural numbers.

Gauss came up with his sum in only a moment. Per the International System of Units, a moment is just over 3 seconds. I’m pretty sure we’ve got him beat. Let’s test it by timing the execution of sum-all on 100.

> (time (sum-all 100))

cpu time: 0 real time: 1 gc time: 0

5050

Pssh, it only took us a millisecond. Take that Gauss! I bet we can even sum the first million numbers in less time than Gauss took for the first hundred.

> (time (sum-all 1000000))

cpu time: 649 real time: 671 gc time: 162

500000500000

Not bad. But can we do better? Let’s look at what sum-all is doing when it executes.

Ex 2: Step through (sum-all 5) and in a comment write down the full addition expression that executes after all the sum-all terms are gone. (There should only be numbers and +.)

Ex 3: Which addition is performed first? Which addition is performed last? Write your answer down in a comment.

In What Direction?

Is it possible to add the numbers from 5 down to 1, you ask? Yes indeed! But we need an extra argument to accumulate the result as we calculate, so we’ll call it sum-all/acc.

; sum-all/acc : Natural Natural -> Natural

; Sum the naturals from n to 1.

(define (sum-all/acc n a)

(cond [(zero? n) a]

[else (sum-all/acc (sub1 n) (+ n a))]))

What’s the difference here? Rather than building a big expression that is then added together like sum-all, sum-all/acc performs one addition each time it recurs and simply returns the result once it reaches zero. Of course, we must give an initial value for the accumulator to sum-all/acc.

Ex 4: What should be the initial value for the accumulator in sum-all/acc? Define a function sum-all-down with the same signature as sum-all, which gives the given number and correct initial accumulator to sum-all/acc.

Ex 5: Step through (sum-all-down 5). Confirm that it does not build a large addition expression while it executes. What additions does it perform? Write them down in a comment.

Now what’s the point? Let’s look at the cost of summing the first million numbers using sum-all-down.

> (time (sum-all-down 1000000))

cpu time: 80 real time: 80 gc time: 0

500000500000

Whoa

Swap Head and Hands!

That beat our old time by nearly an order of magnitude.

And we can sum much larger numbers than the original sum-all.

Ex 6: Run a bunch of tests to see how large an input causes sum-all to run out of memory. Try to get sum-all-down to run out of memory too.

Ex 7: Why do you think sum-all-down executes faster than sum-all? How is it related to the fact that it can sum larger numbers? Discuss this with your partner, and feel free to ask other groups as well.

That’s just the beginning. Recall the function fib from the last lab.

; fib : Natural -> Natural

; Return the nth term in the Fibonacci sequence.

(define (fib n)

(cond [(= 0 n) 0]

[(= 1 n) 1]

[else (+ (fib (- n 1)) (fib (- n 2)))]))

Note that, like our original sum-all, the addition is performed on the outside of the recursive calls to fib. This forces ISL+ to remember the rest of the work that needs to be performed (add the right recursive call to fib) while it recurs down the left recursive call. But if we define fib with an accumulator, there’s no need to remember each recursive addition.

Ex 8: Define fib/acc with the signature Natural Natural -> Natural. Consider: what is (1) the proper initial accumulator value and (2) what is the proper result in the base cases?

Hint: Use one of the recursive calls to fib/acc as the new accumulator value to the other recursive call.

> (check-expect (time (fib/acc 40 0)) (time (fib 40)))

cpu time: 52417 real time: 52413 gc time: 26 cpu time: 69273 real time: 69435 gc time: 70 The test passed!

Not as impressive a difference as for sum-all, but still a noticeable improvement!

Generalizing

Like any inductively defined data, natural numbers have a fold that follows the structural template. The given operation f is applied first on the base case result b and 1, then that result and 2, and so on, so we’ll call it foldu for "fold-up".

; foldu : [Natural X -> X] X Natural -> X

(define (foldu f b n)

(cond [(zero? n) b]

[else (f n (foldu f b (sub1 n)))]))

Ex 9: Implement sum-all/up in terms of foldu. Test its performance against the original sum-all. Does it exhibit the same behavior?

Ex 10: Design the function foldd with the same signature as foldu, which instead folds the natural numbers down using an accumulator.

Ex 11: Implement sum-all/down in terms of foldd. Test its performance against sum-all-down. Does it exhibit the same behavior?