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. 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:

   (define example1 (term (1.7 3.2 2.1)))

   (define example2 (term (1.7 4.9 7.0)))

2. purpose statement and contract

   ; turn a list of relative distances into a list of absolute distances

3. 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))

4. the template

   (define-metafunction Lon

   absolute : l -> l

   [(absolute ()) .....]

   [(absolute (n_head n_rest ...))

   ..... n_head ..... (absolute (n_rest ...)) .....])

5. 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 1))) (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)).

6. 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.

; 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)))))])

1. 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 with

   1.7    3.2   2.1

   then after two recursive calls, the current sequence is

   2.1

   meaning that the difference between the two lists are the numbers

   1.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.

2. 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.

3. 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.,

   ,(+ (term n) (term n_head))

4. 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,

   ,(cons (+ (term n) (term n_head)) ...)