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

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

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

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

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

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