2 More Languages, More Design

The grammars of programming languages tend to come with clauses that refer to themselves and/or at least to each other. The purpose of this lecture is to introduce such languages in Redex and functions that operate on them.

2.1 Example: Bigger Shapes

As always we start with a problem statement:

Sample Problem In addition to “atomic” shapes, your program should also be able to deal with overlays of shapes, i.e., combining two shapes by putting one on top of the other. Extend your data representation from the first problem statement and then design a function that computes the area of a given shape. For simplicity we consider the area of a composite shape the sum of its pieces.

This one extends the problem statement from Example: Shapes.

"shapes-area.rkt"
#lang racket

(require redex)

(define-language Shapes
  (s (circle p c n)
     (square p c n)
     (triangle p c n n)
     (combine s s))
  (c red green blue)
  (p (n n))
  (n natural)
  ; for the results
  (a number))

(define ex1 (term (circle (3 4) red 10)))
(define ex2 (term (square (10 0) green 3)))
(define ex3 (term (triangle (0 0) blue 3 4)))
(define ex4 (term (combine ,ex1 ,ex2)))
(define ex5 (term (combine ,ex3 ,ex4)))

(define-metafunction Shapes
  area : s -> a
  [(area (circle p c n_radius))
   ,(* pi (term n_radius) (term n_radius))]
  [(area (square p c n_side))
   ,(* (term n_side) (term n_side))]
  [(area (triangle p c n_height n_base))
   ,(* 1/2 (term n_height) (term n_base))]
  [(area (combine s_1 s_2))
   ,(+ (term (area s_1)) (term (area s_2)))])

(test-equal (term (area ,ex1)) (* 10 10 pi))
(test-equal (term (area ,ex2)) 9)
(test-equal (term (area ,ex3)) 6)
(test-equal (term (area ,ex4)) (+ (* 10 10 pi) 9))
(test-equal (term (area ,ex5)) (+ 6 (+ (* 10 10 pi) 9)))
Figure 1: The area of shapes

Let us work through the design recipe, revising it as necessitated by the problem statement and design recipe:

the language definition and data examples:

(define-language Shapes
  (s (circle p c n)
     (square p c n)
     (triangle p c n n)
; new:
     (combine s s))
  (c red green blue)
  (p (n n))
  (n natural)
  ; for the results
  (a number))

(define ex1 (term (circle (3 4) red 10)))
(define ex2 (term (square (10 0) green 3)))
(define ex3 (term (triangle (0 0) blue 3 4)))
; new:
(define ex4 (term (combine ,ex1 ,ex2)))
(define ex5 (term (combine ,ex3 ,ex4)))

Once again, note how the definitions of the two examples escape the term construction to use Racket names.

> (redex-match Shapes s ex4)
(list (match (list (bind 's '(combine (circle (3 4) red 10) (square (10 0) green 3))))))
> (redex-match Shapes s ex5)
(list (match (list (bind 's '(combine (triangle (0 0) blue 3 4) (combine (circle (3 4) red 10) (square (10 0) green 3)))))))
> (redex-match Shapes (combine s_1 s_2) ex5)
(list (match (list (bind 's_1 '(triangle (0 0) blue 3 4)) (bind 's_2 '(combine (circle (3 4) red 10) (square (10 0) green 3))))))

The redex-match expressions confirm that these examples belong to the language. The last one shows how to use the feature with complex patterns.

the purpose statement and signature of the metafunction remain the same:
; compute the area of a shape
(define-metafunction Shapes
area : s -> a
...)
The presence of a self-referential clause does not change anything with respect to the purpose or contract of the metafunction.

when it comes to functional examples, we need to work through composite shapes:

; given ex1, area should produce (* pi 10 10)
; given ex2, area should produce 9
; given ex3, area should produce (* 1/2 3 4)
; new:
; given ex4, area should add up the area for ex1 and ex2
; given ex5, area should add up the area for ex1 and ex4

The examples exploit the request from the problem statement that the area of a composite shape is the sum of the areas of the two pieces. You may wish to calculate out the answers for the last two lines before you continue.

the template construction experiences the most significant change:

(define-metafunction Shapes
  area : s -> a
  [(area (circle p c n_radius))
   ... (term n_radius) ... (term n_radius) ...]
  [(area (square p c n_side))
   ... (term n_side) ... (term n_side) ...]
  [(area (triangle p c n_height n_base))
   ... (term n_height) .. (term n_base) ...]
; new:
  [(area (combine s_1 s_2))
   ... (term (area s_1)) .. (term (area s_2)) ...])

The template has as many patterns as there are alternatives in the clause for the (major) input. On the right hand side, we can write down the pieces of data that the pattern provides. Since the data definition is self-referential, we indicate this self-reference with recursive calls in the corresponding clause.

in contrast, coding up the rest of the definition is straightforward:

; compute the area of a shape
(define-metafunction Shapes
  area : s -> a
  [(area (circle p c n_radius))
   ,(* pi (term n_radius) (term n_radius))]
  [(area (square p c n_side))
   ,(* (term n_side) (term n_side))]
  [(area (triangle p c n_height n_base))
   ,(* 1/2 (term n_height) (term n_base))]
; new
  [(area (combine s_1 s_2))
   ,(+ (term (area s_1)) (term (area s_2)))])

See how easy it was to design this recursive program? It took very little once we had developed the template in a systematic manner.

the tests are once again just encodings of the examples:

(test-equal (term (area ,ex1)) (* 10 10 pi))
(test-equal (term (area ,ex2)) 9)
(test-equal (term (area ,ex3)) 6)
; new
(test-equal (term (area ,ex4)) (+ (* 10 10 pi) 9))
(test-equal (term (area ,ex4)) (+ 6 (+ (* 10 10 pi) 9)))

To appreciate the design recipe for self-referential data definitions, you should visit the section in HtDP .

Figure 1 shows how you turn this development into a complete solution of the problem, suitable for submission as a homework solution. As you can tell from this figure, the results of the template step and the example step may not show up in the finished product. The former is visible from the actual solution, and if it isn’t, your solution is likely to be wrong. The latter usually becomes a part of the test suite; when the computation is complex and/or an actual calculation is called for, some additional comments on examples might be appropriate.

2.2 Accumulators

Some problems seem to require convoluted solutions at first glance. Here is one of them:

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.

The idea seem simple. Here is a sequence of relative distances:

1.7 3.2 2.1

It means the first point is 1.7m from the starting point, the second point is 3.2m from the first point, and the third point is 2.1m from the second point. Clearly, the following is the series of absolute distances:

1.7 4.9 7.0

All you have to get to do to get from the first to the second is add up the distances as you go along the series.

2.2.1 Brute Force

Let us solve this problem following the design recipe:

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

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.

2.2.2 Accumulator Functions

Except that this solution idea doesn’t fit into the picture with the obvious purpose statement and contract for this function. Recall that the problem calls for a function that consumes a sequence of numbers and that produces one, so the purpose statement and the contract are correct:

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

Keeping a running sum, however, calls for an additional parameter, which is not what the problem statement called for:

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

To resolve this seeming contradiction, we introduce the latter as an auxiliary function to which absolute immediately dispatches with a properly initialized second argument:

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

From a mathematical perspective, we say that we are strengthening the function’s signature.

Here is the definition of the auxiliary function:

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

In some sense, defining such functions is straightforward. In a different sense, this function is unique. To be precise, it differs from all other recursive functions you have seen so far. The key difference is that both arguments to the recursive call change, not just one. Furthermore, one of the arguments is a part of the original argument (structural recursion), the other one is a number that is not a part of the any structure.

"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
; into a list of absolute 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: From relative to absolute distances

Figure 2 shows the complete solution to the problem.

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

As far as the design of accumulator functions is concerned, it differs from plain structural recursions in four points:

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.
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.,
,(+ (term n) (term n_head))
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)) ...)

For more on accumulator design see HtDP , especially part IV.

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.

← prev up next →

1	Languages and Metafunctions
2	More Languages, More Design
3	Recursive Functions and Inductive Proofs