CSC 302: define-type

From CSWiki

A define-type form introduces a new data type into a program. The symbol immediately following the keyword define-type is the name of the new data type.

A type predicate, which can be applied to any value and determines whether that value belongs to the new data type, is implicitly defined. The name of the type predicate is formed by appending a question mark to the name of the data type.

The new type has one or more variants, each of which has its own name. Each variant contains zero or more fields, each of which again has its own name. Fields in different variants can have the same name.

In the define-type form, each field is introduced in the form a two-element list in which the first element is the name of the field and the second is a predicate or contract that the value in that field must satisfy.

The specification for a variant is a list in which the first element is the name of the variant and each subsequent element introduces a field.

In the enclosing define-type form, specifications for the variants follow the name of the new data type.

Here's an example from page 6 of our textbook:

(define-type AE
  (num (n number?))
  (add (lhs AE?)
       (rhs AE?))
  (sub (lhs AE?)
       (rhs AE?)))

Here the name of the new data type is AE, and there are three variants, num, add, and sub. The num variant has one field, n, which must be a number. Each of the other variants has two fields, lhs and rhs, and each of these fields must be an AE (that is, it must satisfy the type predicate AE?).

In addition to the type predicate for the data type, the define-type form implicitly defines a constructor for each variant. The name of the constructor is the same as that of the variant, and its arity is the number of fields in the variant. (In the example above, three constructors are implicitly defined: the unary procedure num and the binary procedures add and sub.) Each of these variant constructors imposes a precondition on each of its arguments: the argument value must satisfy the contract specified for the corresponding field.

Furthermore, the define-type form implicitly defines, for each variant, a predicate that can be applied to any value of the data type to determine whether it belongs to the specified variant. The names of these predicates are the names of the variants with question marks appended. (In the example above, they would be called num?, add?, and sub?.)

Also, for each field of a variant, the define-type form implicitly defines a unary accessor procedure that takes a value belonging to that variant and returns the value stored in the specified field. The name of such an accessor procedure is formed by placing a hyphen between the name of the variant and the name of the field. (In the example above, they would be called num-n, add-lhs, add-rhs, sub-lhs, and sub-rhs.)

In Pretty Big PLAI Scheme, the define-type form also implicitly defines a binary mutator procedure for each field of a variant. The mutator takes a value belonging to the variant and another value, and (as a side effect) places the second argument value in the specified field. The name of such a mutator procedure is formed by concatenating "set-", the name of the variant, a hyphen, the name of the field, and an exclamation point. (In the example above, they would be called set-num-n!, set-add-lhs!, set-add-rhs!, set-sub-lhs!, and set-sub-rhs!.)

It is often convenient to use type-case expressions to operate on values of types introduced through define-type.