### 7` `Accumulators

Sample Problem Someone measured the relative distances between a series of points. What is needed, however, is the list of absolute distances of each point to the first one.

1.7 3.2 2.1 |

1.7 4.9 7.0 |

#### 7.1` `Brute Force

- the data definition:
(define-language Lon (l (n ...)) (n number)) The natural representation for sequences of numbers are lists of numbers. Here are the examples from above in this language: - purpose statement and contract
; turn a list of relative distances into a list of absolute distances

- we already have one example and it is easy to make up others:
; given example1, expect back example2 ; given (term (1 1 1)), expect back (term (1 2 3)) - the template
(define-metafunction Lon absolute : l -> l [(absolute ()) .....] [(absolute (n_head n_rest ...)) ..... n_head ..... (absolute (n_rest ...)) .....]) - time to code:
(define-metafunction Lon absolute : l -> l [(absolute ()) ()] [(absolute (n_head n_rest ...)) ,(cons (term n_head) (term (add-to-all n_head (absolute (n_rest ...)))))]) Question is what is this add-to-all function doing here?Here is the problem. We know that n_head is first element of the given list and we know what (absolute (n_rest ...)) computes the absolute distances for the rest of the list. But, these absolute distances do not take into account n_head because a mathematical function knows nothing but its inputs, and n_head is not an input to this recursive calls.

At this point you should say “no problem” because it is straightforward to define a function that adds n_head to all the elements of the list. We call this function add-to-all and we provide its definition (in the form of a homework solution) without going through the whole design recipe:; add n to all numbers on l (define-metafunction Lon add-to-all : n l -> l [(add-to-all n ()) ()] [(add-to-all n (n_head n_rest ...)) ,(cons (+ (term n) (term n_head)) (term (add-to-all n (n_rest ...))))]) (test-equal (term (add-to-all 1 (1 2))) (term (2 3))) If you have any doubts about this definition, work through the design steps.For the ,(cons ... ...) part, recall that unquote takes the calculation back to Racket. If you look up cons’s documentation, you will find out that it constructs a list from a given element and another list. Thus, ,(cons 1 (term (2 3))) yields (term (1 2 3)).

- tests
(test-equal (term (absolute (1 1 1))) (term (1 2 3))) (test-equal (term (absolute ,example1)) (term (1.7 ,(+ 1.7 3.2) ,(+ 1.7 3.2 2.1)))) Since the tests succeed, we know that add-to-all works, too. If not, we would equip the latter with tests derived from these just to make sure the helper function works before we debug anything else.

The problem with this solution is twofold. First, we should need two functions that traverse entire lists to transform a list of relative distances into a list of absolute distances. Second, if you recall your algorithms, you know that the nesting of traversals requires O(n2) iterations over a list of n elements. As mentioned above, the naive solution is to just keep a running sum.

#### 7.2` `Accumulator Functions

; turn a list of relative distances into a list of absolute distances (define-metafunction Lon absolute : l -> l)

; turn a list of relative distances into a list of absolute distances ; relative to the given starting distance n (define-metafunction Lon running-sum : l n -> l)

; turn a list of relative distances into a list of absolute distances (define-metafunction Lon absolute : l -> l [(absolute l_0) (absolute-accu l_0 0)])

; turn a list of relative distances into a list of absolute distances ; relative to the already accumulated distance n ; accumulator: n is the sum of numbers between l_0 and l (define-metafunction Lon absolute-accu : l n -> l [(absolute-accu () n) ()] [(absolute-accu (n_head n_rest ...) n) ,(cons (+ (term n) (term n_head)) (term (absolute-accu (n_rest ...) ,(+ (term n) (term n_head)))))])

"relative-to-absolute.rkt"

#lang racket (require redex) (define-language Lon (l (n ...)) (n number)) (define example1 (term (1.7 3.2 2.1))) (define example2 (term (1.7 4.9 7.0))) ; turn a list of relative distances (define-metafunction Lon absolute : l -> l [(absolute l) (absolute-accu l 0)]) ; turn a list of relative distances into a list of absolute ; distances relative to the already accumulated distance n ; accumulator: n is the sum of numbers between l_0 and l (define-metafunction Lon absolute-accu : l n -> l [(absolute-accu () n) ()] [(absolute-accu (n_head n_rest ...) n) ,(cons (+ (term n) (term n_head)) (term (absolute-accu (n_rest ...) ,(+ (term n) (term n_head)))))]) (test-equal (term (absolute ())) (term ())) (test-equal (term (absolute (1 1 1))) (term (1 2 3))) (test-equal (term (absolute ,example1)) (term (1.7 ,(+ 1.7 3.2) ,(+ 1.7 3.2 2.1))))

Figure 2 shows the complete solution to the problem.

#### 7.3` `Designing with Accumulators

The absolute-accu function is an example of a function that uses an accumulator. The design of accumulator-based functions is initiallyExperienced programmers recognize the problem before they even write down the template a reaction to a convoluted structural design, that is, when you recognize that your function needs to traverse a structural piece of data several times because it “forgets” the pieces that it has already processed. In the above example, the first design of absolute forgets the numbers that it has seen.

First determine the purpose of the accumulator. Write it down as a purpose statement that explains the accumulator as what it remembers about the difference between the root of the given data structure and the current point.

In our running example, the complete list is l_0 and the current list l is a part of it. For example, if we start with1.7 3.2 2.1

then after two recursive calls, the current sequence is2.1

meaning that the difference between the two lists are the numbers1.7 3.2

Given the purpose of our function, it suffices to keep the sum of this difference and that is precisely what the accumulator statement says:; accumulator: n is the sum of numbers between l_0 and l (define-metafunction Lon absolute-accu : l n -> l ...) In other applications, you may need some other combination of the numbers or you may need all of them including their ordering.The second step is to decide on what the initial value should be for the accumulator. In the case of a running sum, it is obviously 0.

- The third step is to formulate the argument for the recursive call(s) so that the accumulator statement is maintained. In our example, it is relatively obvious that we need to add the first element to the current value of the accumulator, i.e.,
- Lastly, you need to figure out when to use the accumulator value. It may become the result of the computation when the major structural argument is exhausted; it may contribute to the result in another way; or it may simply be used to terminate the algorithm. The running example adds the accumulator to each element of the resulting list, that is,

In the area of programming languages, accumulator-style functions are commonly used to check context-sensitive properties of programs. The accumulator’s purpose is after all to keep track of the context of the given argument.