►7400:   i  PPL
►Working with Redex
▼Lecture 1
    ← prev  up  next → 

5 Example: Shapes

Here is a first illustration of the design recipe, starting with a problem statement:

Sample Problem A shape is either a square, or a triangle, or a circle. The description of each shape includes its location in the plane and a color (red, green, or blue). A triangle comes with a specification of the width of its base and its height; a square also comes with a specification of its size; and a circle has a radius. All numbers are natural numbers. Design a function that computes the area of a given shape.

  1. the language definition and data examples:
    (define-language Shapes
      (s (circle p c n)
         (square p c n)
         ; (triangle Position Color Height Base)
         (triangle p c n n))
      (c red green blue)
      (p (n n)) ; Cartesian positions in the plane
      (n natural)
      (a number)) ; for the results
     
    (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)))
     
    (redex-match Shapes s ex1)
    (redex-match Shapes s ex2)
    (redex-match Shapes s ex3)
    The redex-match expressions confirm that these examples belong to the language.

  2. the purpose statement and signature of the metafunction:
    ; compute the area of a shape
    (define-metafunction Shapes
      area : s -> a
      ...)
    You see that is why we added a to the grammar. Areas are measured in arbitrary numbers even if the dimensions of the shape are measured in natural numbers.

  3. the functional examples:
    ; given ex1, area should produce (* pi 10 10)
    ; given ex2, area should produce 9
    ; given ex3, area should produce (* 1/2 3 4)
    By calculating out the answer, you mentally prepare the coding step.

  4. the template:
    (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) ...])
    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. The output of the function must be computed from these pieces.

  5. the full definition:
    ; 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))])
    Note the underlines in pattern variables. The base of the identifier specifies what kind of datum you expect (e.g., n a natural number). The subscript provides a unique name for readability and/or uniqueness (when more than one n occurs in the pattern).

    On the output side, we escape with , to the Racket level and call the * function on the specified pieces. The nested terms escape back into the Redex level and provide the values from the matched pattern.

  6. the test:
    (test-equal (term (area ,ex1)) (* 10 10 pi))
    (test-equal (term (area ,ex2)) 9)
    (test-equal (term (area ,ex3)) 6)
    This is the easiest step and the reward for systematic development. When you follow the recipe, you tend to get all test cases thru quickly.

    ← prev  up  next →