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.

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