[previous] [up] [next]     [index]
Next: Processing Arbitrarily Large Data Up: Intermezzo 1 Syntax and Semantics Previous: Variable Definitions

Structure Definitions

We still have to understand the syntax and semantics of one more Scheme construct: define-struct. When we define a structure, we really define several primitive operations: a constructor, several selectors, and a predicate. Hence, define-struct is by far the most complex Scheme construct we use.

A structure definition is a third form of definition. The keyword define-struct distinguishes this form of definition from function and variable definitions. The keyword is followed by a name and a sequence of names enclosed in parentheses:

tex2html_wrap_inline71981 = (define-struct tex2html_wrap_inline71983 ( tex2html_wrap_inline71985 )) .

The names in a define-struct definition must be chosen as if they were function names, though none of them is used as a function (or variable) name.

Here is a simple example: 

  (define-struct point (x y z)) .
Since point, x, y, and z are variables and the parentheses are placed according to the grammatical pattern, it is a proper definition of a structure. In contrast, these two parenthesized sentences 
  (define-struct (point x y z))


  (define-struct point x y z)
are improper definitions, because define-struct is not followed by a single variable name and a sequence of variables in parentheses.

A define-struct definition introduces new primitive operations. The names of these operations are formed from those that occur in the definition. Suppose a data structure definition has the following shape: 

  (define-struct c (s-1 ... s-n))
Then Scheme introduces the following primitive operations:
  1. make-c: a CONSTRUCTOR;
  2. c-s-1 ... c-s-n: a series of SELECTORS; and
  3. c?: a PREDICATE.
These primitives have the same status as +, -, or *. Before we can understand the rules that govern these new primitives, however, we must return to the definition of values. After all, the purpose of define-struct is to introduce a new class of values: structures.

Simply put, the set of values no longer consists of just constants, but also of structures, which compound several values into one. In terms of our grammar of values, we must add one clause per define-struct:

tabular8477

Let us return to the points structures. Since the list of fields contains three names, (make-point u v w) is a value if u, v, and w are values.

Now we are in a position to understand the evaluation rules of the new primitives. If c-s-1 is applied to a c structure, it returns the first component of the value. Similarly, the second selector extracts the second component, the third selector the third component, and so on. The relationship between the new data constructor and the selectors is best characterized with n equations: 

(c-s-1 (make-c V-1 ... V-n)) = V-1
                   tex2html_wrap_inline71993  
(c-s-n (make-c V-1 ... V-n)) = V-n
where V-1 ... V-n is a sequence of values that is as long as s-1 ... s-n.

For our running example, we get the equations 

(point-x (make-point V U W)) = V
(point-y (make-point V U W)) = U 
(point-z (make-point V U W)) = W
In particular, (point-y (make-point 3 4 5)) is equal to 4, and (point-x (make-point (make-point 1 2 3) 4 5)) evaluates to (make-point 1 2 3) because the latter is also a value.

The predicate c? can be applied to any value. It returns true if the value is of kind c and false otherwise. We can translate both parts into equations. The first one, 

(c? (make-c V-1 ... V-n)) = true ,
relates c? and values constructed with make-c; the second one, 
(c? V) = false; if V is a value not constructed with make-c ,
relates c? to all other values.

Again, the equations are best understood in terms of our example. Here are the general equations: 

(point? (make-point V U W)) = true
(point? U) = false ; if U is value, but not a point structure.
Thus, (point? (make-point 3 4 5)) is true and (point? 3) is false.

Exercises

Exercise 8.7.1

Distinguish legal from illegal sentences:

  1. (define-struct personnel-record (name salary dob ssn))
  2. (define-struct oops ())
  3. (define-struct child (dob date (- date dob)))
  4. (define-struct (child person) (dob date))
  5. (define-struct child (parents dob date))

Explain why the sentences are legal define-struct definitions or how they fail to be legal define-struct definitions. Solution

Exercise 8.7.2

Which of the following are values?

  1. (make-point 1 2 3)
  2. (make-point (make-point 1 2 3) 4 5)
  3. (make-point (+ 1 2) 3 4) Solution

Exercise 8.7.3

Suppose the Definitions window contains 

(define-struct ball (x y speed-x speed-y))
Determine the results of the following expressions:
  1. (number? (make-ball 1 2 3 4))
  2. (ball-speed-y (make-ball (+ 1 2) (+ 3 3) 2 3))
  3. (ball-y (make-ball (+ 1 2) (+ 3 3) 2 3))

Also check how DrScheme deals with the following expressions:

  1. (number? (make-ball 1 3 4))
  2. (ball-x (make-posn 1 2))
  3. (ball-speed-y 5)
Verify your solutions with DrScheme. Solution

tabular8763

Figure: Beginning Student Scheme: The full grammar

  tex2html_wrap72017    

[previous] [up] [next]     [index]
Next: Processing Arbitrarily Large Data Up: Intermezzo 1 Syntax and Semantics Previous: Variable Definitions

PLT