Title

Extensible record types

Author

Marc Nieper-Wißkirchen

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-136@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Received: 2016-06-23
60-day deadline: 2016-08-23
Draft #1 published: 2016-06-24
Draft #2 published: 2016-07-04
Draft #3 published: 2016-10-24
Draft #4 published: 2016-12-08
Draft #5 published: 2016-12-15
Finalized: 2016-12-25

Abstract

SRFI 9 and the compatible R7RS-small provide Scheme with record types. The basic problem that is solved by these record types is that they allow the user to introduce new types, disjoint from all existing types. The record type system described in this document is a conservative extension to SRFI 9 and R7RS record types (in other words, the keyword define-record-type defined in this specification can serve as the equally named keyword from SRFI 9 and R7RS and can thus be safely exported from (srfi 9) and (scheme base)) that is intended to solve another fundamental problem, namely the introduction of subtypes.

Issues

No issues at present.

Rationale

As mentioned in the abstract, the record type definitions of R7RS-small allow for the introduction of new disjoint types, called record types. Each value of such a record type denotes a set of locations, one location for each record field defined by the record type. Each field, that is the location corresponding to that field, can be either mutable or immutable depending on whether the record type definition defines a mutator procedure for that field or not. To give immutable fields a value, a suitable constructor procedure of the record type has to be defined and used.

What isn't specified by the record types of R7RS-small is a way to extend record types. Extending a record type means to create a new record type that extends the given record type by adding zero or more new fields to it. The newly created type is not disjoint to all existing types in the sense that it effectively becomes a subtype of the record type that is extended. In order to construct a value of an extended type, the constructor of the type that is extended has to be invoked on the way.

The purpose of this SRFI is to specify a syntactic extension to the record system of R7RS-small that allows extending record types in the manner described above. The constructor procedures that can be defined with the syntax of this SRFI are of a rather rigid form (for example, the first arguments of a constructor of a subtype have to correspond to the arguments of the constructor of the parent, if any). If constructors of a different signature are needed, it is expected that they are defined by the user using ordinary Scheme definitions and the constructor defined by the record type definition. Another syntactic layer on top of the record types defined here is also possible. The guiding principle of this proposal, however, is just to provide the primitives on which more sophisticated systems (like an object system with single inheritance) can be built.

This SRFI differs from related specifications like SRFI 131 in that it does not rely on the identity of field names in order to specify a constructor for record-subtypes. In SRFI 136, parent fields in a constructor specification are solely referred to by position. On the other hand, there hasn't been reached a consensus by the community yet whether parent field names in SRFI 131 are matched as symbols or identifiers (or rather whether the former is compatible with the semantics of R7RS). In fact, the main reason for developing SRFI 136 was that it is mostly agnostic to whether field names are symbols or identifiers.

Thus, SRFI 136 follows the R6RS's record system in that regard.

Without any further extension by further SRFIs or further revisions of R7RS, the syntactic interface makes the following guarantees:

An immutable field of a parent record type remains immutable in its subtypes.
A subtype cannot change the subset of those parent fields that are initialized in the constructor.
Subtypes cannot overwrite parent fields.

This specification also provides a minimal procedural interface and very basic introspection facilities, on which more sophisticated systems like the one specified by SRFI 99 can be built. R7RS leaves it open whether the record type descriptor is bound by a record-type definition to a runtime object or a syntactic representation. In order to be able to provide introspection facilities already at the expansion level, in this specification the choice of a syntactic representation as a keyword has been made. Due to this choice, the record type descriptor cannot serve as a descriptor for the record type in the procedural interface. However, a runtime record-type descriptor can be extracted from the keyword to be used in the procedural interface.

Specification

Syntax

This SRFI extends 7.1.6 of R7RS-small as follows:

 <definition>           
   -> <record-type definition>
 
 <record-type definition>
   -> (define-record-type <type spec>
        <constructor spec>
        <predicate spec>
        <field spec> ...)

 <type spec>  -> <type name>
              -> (<type name> <parent>)

 <constructor spec>
              -> #f
              -> <constructor name>
              -> (<constructor name> <field name> ...)

 <predicate spec>
              -> #f
              -> <predicate name>

 <field spec> -> (<field name> <accessor name>)
              -> (<field name> <accessor name> <mutator name>)

 <parent>           -> <keyword>
                    -> #f

 <type name>        -> <identifier>
 <constructor name> -> <identifier>
 <predicate name>   -> <identifier>
 <accessor name>    -> <identifier>
 <mutator name>     -> <identifier>
 <field name>       -> <identifier>
                    -> #f

It also extends 7.1.3 of R7RS-small as follows:

 <macro use>        -> (<type name> (<keyword> <datum> ...))
                    -> (<type name>)

The semantics of a record type definition is the same as in R7RS-small except for the following additions:

The record-type definition macro-expands into a cluster of definitions that:

defines a keyword <type name> as the record-type descriptor for the new record-type;
defines a constructor for instances of the new record-type (unless the constructor spec is #f);
defines a predicate that recognizes instances of the new record-type and its subtypes (unless the predicate spec is #f);
defines an accessor for each field name;
defines a mutator for each mutable field name

From the keyword that is bound to the record-type descriptor, a runtime representation for the use in procedural interface defined below can be extracted.

A record type definition extends R7RS-small with the following additional options:

If a <parent> expression is specified and not #f, then it must be an identifier bound to a record-type descriptor that serves as the parent record-type for the record-type being defined.
If #f is specified for the constructor or predicate, then no constructor or predicate procedure is defined. (This is useful when the record-type being defined will be used as an abstract base class and has no immutable fields.)
If the constructor name is specified as an identifier, then the constructor's arguments correspond to the arguments of the parent's constructor (if there is no parent constructor, the arguments correspond to the argument of the constructor of the parent's parent, and so on) followed by the new fields added by this record-type definition in the specified order.
If #f is specified for a field name that field is effectively unnamed.

When a constructor spec is of the form (<constructor name> <field name> ...) and the parent's constructor takes n arguments (if there is no parent constructor, the constructor of the parent's parent is considered, and so on):

The first n field names are arbitrary identifiers, which correspond to arguments of the parent's constructor. (While it is not strictly necessary to name these identifiers after the identifiers used in the parent's constructor, it will certainly help readability of the source.) The other arguments correspond to field names or accessor names (field names take precedence) declared in the same define-record-type form. (Here, an argument corresponds to an accessor name as if it was a variable reference corresponding to a variable.)
It is an error if the same identifier appears more than once in the field names of the constructor spec.

Let <type name> be the record-type descriptor for a record-type defined by:

 (define-record-type (<type name> <parent>)
   <constructor spec>
   <predicate spec>
   <field spec> ...)

Then the macro use

(<type name>
  (<keyword> <datum> ...))

macro-expands into:

 (<keyword> <datum> ... <parent> <field-spec> ...)

(If the record-type does not have a parent, <parent> is #f.)

Furthermore, the macro use (<type name>) macro-expands into an expression that evaluates to an object that serves as a runtime record-type descriptor for the procedural interface (see below).

Rationale: This allows the introspection of the record type at macro-expansion type. The arguments <keyword> and <datum> are to support CPS-techniques in macro programming. For example, a pattern matcher written using syntax-rules can support matching of record instances and can get hold of the record-type structure at macro-expansion time by using the macro (<type name> (<keyword> <datum> ...))

Procedures

The following set of procedures is defined:

(record? obj)

Returns #t if and only if obj is a record constructed by one of the constructors defined by this specification.

(record-type-descriptor? obj)

Returns #t if and only if obj is a runtime record-type descriptor.

(record-type-descriptor record)

Returns the runtime record-type descriptor of the record type of the record record.

(record-type-predicate rtd)

Returns a type predicate of the record type, for which rtd is the runtime record-type descriptor.

(record-type-name rtd)

Returns the name of the record-type, for which rtd is the runtime record-type descriptor, as a symbol.

(record-type-parent rtd)

Returns the runtime record-type descriptor of the parent of the record-type, for which rtd is the runtime record-type descriptor, or #f if there is no parent.

(record-type-fields rtd)

Returns a list of three-element lists of the form (field-name accessor mutator) corresponding to the fields (excluding those of parent record-types) defined by the record-type, for which rtd is the runtime record-type descriptor, such that:

field name is the name of the field as a symbol or #f if it is unnamed;
accessor is an accessor defined for the field;
mutator is a mutator defined for the field if it is mutable and #f otherwise.

(make-record-type-descriptor name fieldspecs)

(make-record-type-descriptor name fieldspecs parent)

If name evaluates to a symbol <type name> and parent evaluates to the runtime record-type descriptor of a record type definition of <parent> (if the argument parent is omitted, <parent> defaults to #f), and fieldspecs evaluates to a list of field specifiers, where each field specifier is either a

a symbol naming the (mutable) field,
a list of the form (mutable name), or
a list of the form (immutable name),

the application (make-record-type-descriptor name fieldspecs parent) evaluates to

 (let ()
   (define-record-type (<type name> <parent>)
     #f
     #f
     <field spec> ...)
   (<type name>))

where each <field spec> corresponds to a field specifier in fieldspecs as follows:

If the field specifier is a symbol name or a list of the form (mutable name), the corresponding <field spec> is (name accessor mutator), where accessor and mutator are fresh symbols
If the field specifier is of the form (immutable name), the corresponding <field spec> is (name accessor), where accessor is a fresh symbol.

Note that the newly bound runtime record type descriptor differs from any existing runtime record-type descriptor.

(make-record rtd field-vector)

Returns an instance of the record type, for which rtd is the runtime record-type descriptor, whose fields (including those of parent record-types with the fields of parent record-types coming first) are initialized with the objects in the vector field-vector in order. It is an error if the field-vector does not have as many elements as there are fields. It is unspecified whether the vector is shared with the newly created record.

Implementation

The sample implementation is given as an R7RS library, which only relies on the bindings exported by (scheme base). In particular, it is implemented using only syntax-rules macros and does not rely on more sophisticated/less beautiful macro facilities.

Source for the sample implementation.

The sample implementation is accompanied with an implementation of SRFI 131 on top of the syntax and procedures defined in this SRFI. Using this implementation, SRFI 131 and SRFI 136 record-types can mutually inherit each other and can thus be mixed in a program. (Caveat: SRFI 131 matches field names as symbols while the provided sample implementation of SRFI 136 matches field names on the syntactic level as identifiers. Thus, SRFI 131 record-types can only reference fields of SRFI 136 parents in their constructors if they are not being renamed during macro expansion.)

As the shape of constructors between SRFI 131 and SRFI 136 is incompatible, a SRFI 136 record-type with a SRFI 131 parent behaves as if the parent's constructor spec was given by a single identifier (that is without any field names as arguments).

For demonstration purposes of SRFI 137, the provided sample implementation for SRFI 136 builds upon that SRFI 137.

Source for the compatible SRFI 131 implementation.

Acknowledgements

Credit goes to all members of the Scheme Working Group 2, who participated in the discussion of record types in R7RS-large. Quite a lot of wording was copied verbatim from SRFI 131.

The author of this SRFI would also like to thank Sudarshan S Chawathe, Takashi Kato, and Jim Rees, whose participation on the mailing list was very helpful in bringing this SRFI into final shape.

Finally, the whole process of bringing this SRFI into life wouldn't have happened without the encouragement by John Cowan and the support of Arthur A. Gleckler.

Copyright

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Arthur A. Gleckler