Next: , Previous: , Up: srfi err5rs records   [Index]


2.32.2 Rationale

In most programming languages, records (aka structures or classes) are important because they can package component values of different types into a single object.

Scheme’s vectors and procedures provided that capability already, but records remained important for two reasons:

For many programmers, records were the most important new feature of the R6RS, but the specific record systems that were proposed by the R6RS have been widely criticized. Over 30% of those who voted against ratification mentioned the record systems as one of their reasons.

The ERR5RS record system described by this SRFI provides a simpler and fully portable alternative to the R6RS record system. The ERR5RS record system consists of:

The ERR5RS record system does not mandate support for the non–generative, sealed, and/or opaque features of the R6RS record system. Implementations of this SRFI may extend the ERR5RS record system to support those features, however, and this SRFI recommends an API to implementations that support those features. With those extensions, the ERR5RS record system has the same expressive power as the R6RS record system. Hence the record system described by this SRFI can serve as either or both of the following:

The following subsections develop the rationale for this SRFI by considering:

2.32.2.1 Records before R6RS

The importance of adding records to Scheme has been recognized for more than twenty years. The basic idea behind the SRFI-9 and R6RS record systems was outlined by Norman Adams on 8 July 1987, following similar ideas that had been implemented in T and MIT CScheme. Jonathan Rees posted a revision of Adams’s proposal on 26 May 1988. Pavel Curtis proposed an extension of Rees’s proposal on 18 August 1989, noting that it had been approved by consensus at the first meeting of BASH (Bay Area Scheme Hackers?). The rrrs-authors archive includes several responses to these proposals that are worth reading.

The Rees/Curtis proposal was revived in 1992. When the RnRS authors met on 25 June 1992 in Palo Alto, they felt that this proposal needed more discussion. Kent Dybvig objected to the proposal on several grounds, including the provision of inspection facilities, the inability to define immutable records, and the use of procedures instead of special forms. Although 9 authors favored adoption of the records proposal, 11 opposed it.

The topic of records was revived again on 23 April 1996 by Bruce Duba, Matthew Flatt, and Shriram Krishnamurthi. Alan Bawden and Richard Kelsey observed that the Duba/Flatt/Krishnamurthi proposal was essentially the same as Pavel Curtis’s, which Kelsey reposted. Kent Dybvig objected once again, on the same three grounds. He also argued that procedural interfaces are difficult to compile efficiently, and that this inefficiency would create portability problems.

In reality, however, procedural interfaces add no inefficiency. It is now agreed that syntactic interfaces offer no advantages for generative records. Even for non–generative records, the claimed inefficiency consists of a single load instruction, which optimizing compilers can eliminate — along with the entire runtime check that includes the load instruction — for all but the first of a sequence of operations that access the same record. (That optimization is a straightforward extension of the optimization that eliminates the pair check when computing the cdr of a list whose car has already been computed.) Furthermore, it turns out that even the occasional load instruction is no harder to remove using a procedural interface than when using a syntactic interface. In R6RS library chapter 6, therefore, both of the statements that claim an advantage in efficiency for the syntactic layer have no basis in fact. (These two statements appear in the next–to–last paragraph before section 6.1, and in the note that follows the specification of parent-rtd.)

On 24 April 1996, Bill Rozas suggested the idea of having two separate APIs, one procedural and one syntactic, for the same record facility. Two days later, Dybvig proposed a compromise along those lines that incorporated several artificial restrictions, which were apparently motivated by concerns about the alleged extra load instruction. Dybvig and Rozas continued to develop this proposal, and presented a summary of it following the 1998 Scheme Workshop. I have been unable to locate a written or online copy of this proposal.

SRFI-9, submitted by Richard Kelsey in July 1999, is a syntactic API in the tradition of the Rees, Curtis, and Duba/Flatt/Krishnamurthi proposals.

Single inheritance was added by Larceny in 1998, and by Chez Scheme in 1999.

SRFI 57, submitted by Andre van Tonder in September 2004, features label polymorphism, which can be considered a form of structural subtyping and multiple inheritance.

2.32.2.2 R6RS Records

The R6RS proposes a three–layer single inheritance system, with syntactic, procedural, and inspection layers.

R6RS Records: procedural layer

The R6RS procedural layer generally requires at least three separate definitions for each level of inheritance: the record–type descriptor, at least one record–constructor descriptor, and an actual constructor (if instances of the record–type are to be created).

The (unratified) R6RS rationale describes the constructor–descriptor mechanism as “an infrastructure for creating specialized constructors, rather than just creating default constructors that accept the initial values of all the fields as arguments. This infrastructure achieves full generality while leaving each level of an inheritance hierarchy in control over its own fields and allowing child record definitions to be abstracted away from the actual number and contents of parent fields.” Neither the (ratified) R6RS library document nor the (unratified) R6RS rationale consider the fact that the constructor–descriptor mechanism adds unnecessary complexity to what is by far the most common case: record definitions that do not require specialized constructors. Neither document considers the fact that the benefits of the constructor–descriptor mechanism are small even when specialized constructors are needed, as in the first example below.

The R6RS library specification of records says that a record type is “specified by a record–type descriptor, which is an object that specifies the fields of the record and various other properties that all records of that type share.” Since the record–type descriptor is an object, it can be the value of a variable that is exported by a library. As discussed below, however, the R6RS syntactic layer uses a different notion of record type that may be neither object nor syntax.

R6RS records: syntactic layer

The R6RS syntactic layer consists of a define-record-type syntax that is incompatible with the syntaxes of the same name defined by SRFI-9 and SRFI-99 (this SRFI).

According to R6RS library section 6.2, an R6RS define-record-type form binds the record name “to an expand–time or run–time representation of the record type [that] can be used as parent name in syntactic record–type definitions that extend this definition. It can also be used as a handle to gain access to the underlying record–type descriptor and constructor descriptor”.

Note that portable code cannot assume the record name is bound to a record–type descriptor. Portable code can only assume that the record name is bound to “an expand–time or run–time representation”, whose semantics is not otherwise explained by the R6RS and R6RS library documents. In particular, it is far from obvious that portable code can export the record name from a library; libraries can export names that are bound to objects or to syntax, but the R6RS does not require the denotation of a record name to be either of those things.

The mysterious entity to which a record name is bound can be used as a handle to recover a record–type descriptor or constructor descriptor by using the record-type-descriptor or record-constructor-descriptor syntaxes, respectively. The recovered record–type descriptor and constructor descriptor may be exported from a library, and that is apparently the only portable way for a library to export an R6RS record type that was defined using the R6RS syntactic layer.

The recovered record–type descriptor and constructor descriptor also provide a way for the procedural layer to define new record types that inherit from record types defined by the syntactic layer. Similarly, it is possible for the syntactic layer to use a parent-rtd clause to define new record types that inherit from record types defined by the procedural layer.

The two notions of record type that are used by the procedural and syntactic layers are not interchangeable, however. In either direction, defining a new record type that inherits from some previously defined record type requires the programmer to know whether the previously defined record type was defined using the procedural or the syntactic layer. If the procedural and syntactic layers of the R6RS were fully compatible, then changing a record type definition from procedural to syntactic (or vice versa) would be transparent to clients. As the R6RS record facility is defined, however, that minor change will break all code that inherits from the record type.

R6RS library chapter 6 attempts to excuse that incompatibility, and the interoperability and maintenance problems that result from it, on the basis of efficiency. Recall, however, that the claimed efficiency of the R6RS syntactic layer is illusory. In reality, the R6RS design offers no advantages over a simpler and more orthogonal design (such as the one specified by this SRFI) in which the syntactic and procedural layers both use the same notion of record type.

The problems described above were known and had been documented before the R6RS documents were put to a vote, but the R6RS documents were ratified anyway. At this point, the best that can be done is to use the SRFI process to specify a better record facility, and to warn programmers of the problems they will encounter if they use the record facilities described within the R6RS library document.

2.32.2.3 Design Rationale for ERR5RS Records

The ERR5RS syntactic layer described by this SRFI is based upon the Rees/Curtis/Duba/Flatt/Krishnamurthi/Kelsey/SRFI-9 tradition, changing only a few details to improve interoperability with records defined by the ERR5RS and R6RS procedural layers.

The define-record-type syntax specified by this SRFI is compatible with and extends SRFI-9, which is one of the more widely accepted SRFIs. The extensions include single inheritance and (optional) implicit naming, along with succinct abbreviations for specifying whether a field is immutable or mutable.

The procedural layer specified by this SRFI is fully compatible with its define-record-type syntax. Both the procedural and syntactic layers can define new record types that inherit from previously defined record types without requiring programmers to know which layer was used to define the parent type.

In implementations of the R6RS, a SRFI-99 record type coincides with the R6RS notion of a record–type descriptor. Portable libraries can safely export SRFI-99 record types even if they were defined using the syntactic layer of SRFI-99.

In procedure names, SRFI-99 uses rtd as an abbreviation for record–type descriptor. This naming convention prevents name clashes between SRFI-99 and the R6RS procedural and inspection layers, which makes it easier for R6RS programs to import SRFI-99 libraries. R6RS programs must take care when importing the R6RS syntactic layer, however, because that library’s exports conflict with both SRFI-9 and with SRFI-99.

When implemented properly, SRFI-99 records will be just as efficient as R6RS records. SRFI-99 is simpler than R6RS records, both in specification and in implementation. SRFI-99 is strictly less powerful than the R6RS records facility because SRFI-99 does not require implementations to provide sealed, opaque, or non–generative records. On the other hand, SRFI-99 describes three optional extensions (the sealed, opaque, and uid arguments to make-rtd) that would give SRFI-99 the same power as R6RS records. With those three extensions, SRFI-99 would become a simple and efficient foundation for implementing R6RS records.

The record system described by this SRFI has been implemented in Larceny. It is the primary record system used by Larceny’s implementation of the R6RS, including the (rnrs records syntactic (6)) library. Larceny demonstrates both the efficiency of ERR5RS records and the ease of interoperability between SRFI-9, ERR5RS, and the procedural and inspection layers of R6RS records.

2.32.2.4 Issues


Next: , Previous: , Up: srfi err5rs records   [Index]