[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Generative record types

This discussion about the exception system -- especially the condition
datatype portion of it -- and the talk of "multiple inheritance"
suggests that we should first resolve what the prevailing opinion is
going to be on generative datatypes.


For too long, Scheme has persisted in using lists to represent
aggregate data: usually, lists with a prefix tag.  Some macros (such
as variant-case) have been devised to simplify this task, but in
general this mechanism has several weaknesses.

Macros such as define-structure are an essentially identical approach.
They might use vectors instead of lists, and might automatically
create the predicate, constructor, accessors and mutators, but this
only simplifies the _manual_ labor involved: it does not especially
reduce the _conceptual_ labor.  For instance, is it not always obvious
why the procedure transform, given below,

  (define-structure (lexeme ...))

  (define transform
    (lambda (expr)
	((pair? expr) ...)
	((vector? expr) (list->vector (map transform (vector->list expr))))
	((lexeme? expr) ...)
	(else (error 'transform "invalid expr ~a" expr)))))

produces this error when fed a (make-lexeme ...) object:

  Error in transform: invalid expr lexeme.



  We would like the ability to create new Scheme "types" (some might
  pronounce that word as if it wer spelled `variant') which are
  aggregate objects and can be created, queried, accessed and mutated.
  The objects created by the constructor answer #f to all the existing
  Scheme type predicates, and #t to the predicate created along with
  the constructor.

One natural additional desideratum is,

  The objects created should answer #f to all existing Scheme
  predicates AND to any other generative record predicate.

Thus, the generative records do not all form a single type of Scheme
object; each declaration creates a new type.

There are various other criteria that one might wish to heap on.  For
instance (`H' for ``hypothetical''),

H1. The fields of the record should not be visible by any means unless
explicitly given access to by the programmer (``opacity'').

H2. Each _syntactic_ occurrence of a declaration, not each _dynamic_
occurrence, generates a new type (``syntactic generativity'').

H3. The specification should enable the programmer to disallow the
creation of accessors or setters for some or all fields.

We believe that criteria such as H1, H2 and H3 are tangential, and
should only be considered after some agreement has been reached on the
primary portion.

NOTE: The notion of opacity is a particularly controversial one.  In
this context, it is perhaps important to distinguish between the
concepts of _safety_ and _security_.  Opacity does not heighten the
_safety_ of the language; with or without opacity, operations will
still be checked, and incorrect operations will be caught.  However,
opacity is relevant for _security_, whereby the programmer may wish to
prevent others from examining the (sensitive) innards of the record.
We wish to concentrate on safety, and acknowledge that opacity can at
times be too constraining, eg, in the context of debugging.


Some Scheme implementations already provide a similar mechanism.  For
instance, Scheme 48's define-record-type appears to have this
property, as do Rice Scheme's define-structure and MzScheme
define-struct.  The syntax of MzScheme's construct is

  (define-struct <s-name> (<f-name-1> <f-name-2> ...))

which defines the following procedures:

  <s-name>? -- true iff argument is created by this make-<s-name>
  make-<s-name> -- constructor
  <s-name>-<f-name-1>, <s-name>-<f-name-2>, ... -- accessors
  set-<s-name>-<f-name-1>!, set-<s-name>-<f-name-2>!, ... -- setters

A variant of this includes additional syntax for preventing the
creation of certain accessors and setters.  Each (define-struct ...)
declaration creates a new type.

We primarily wish to incite discussion, but for the purpose of setting
up a stable target, we propose the adoption of the define-struct
mechanism with the semantics described.  Furthermore, opacity should
be left as an optional feature that individual implementations can
provide, while syntactic generativity should not be adopted.

Comments are solicited on this proposal.

Bruce Duba (bduba@microsoft.com),
Matthew Flatt (mflatt@cs.rice.edu) and
Shriram Krishnamurthi (shriram@cs.rice.edu)