ERR5RS:Records
From SchemePunks
Contents |
[edit] Records
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:
- Records make it easier to index components by their names.
- Records can introduce new types in the sense that all previous type predicates return false for instances of the new record type, while the new predicate associated with the new record type returns true only for instances of the new record type.
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. [1]
How did this happen?
[edit] History
The importance of adding records to Scheme has been
recognized for more than twenty years.
[2]
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.
[3]
Jonathan Rees posted a revision of Adams's proposal on
26 May 1988.
[4]
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?).
[5]
The rrrs-authors archive includes several responses to
these proposals that are worth reading.
The Rees/Curtis proposal was revived in 1992. [6] When the RnRS authors met on 25 June 1992 in Palo Alto, they felt that this proposal needed more discussion. [7] 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. [8] 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, arguing (incorrectly) that procedural interfaces are difficult to compile efficiently, and concluding (incorrectly) that this alleged inefficiency would create portability problems. [9]
On 24 April 1996, Bill Rozas suggested the idea of having two separate APIs, one procedural and one syntactic, for the same record facility. [10] Two days later, Dybvig proposed a "compromise" along those lines [11], incorporating several artificial restrictions because Dybvig feared his compiler would be unable to generate efficient code for the general case. [12]
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. [13]
Single inheritance was added by Larceny in 1998, and by Chez Scheme in 1999. [14]
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. [15]
[edit] R6RS Records
The R6RS proposes a three-layer single inheritance system, with syntactic, procedural, and inspection layers. [16] 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 R6RS editors have attempted to justify the complexity of this API by claiming that hardly anyone would actually use it; they allege that programmers would use the syntactic interface instead. Meanwhile, gratuitous design errors impede interoperation between procedural and syntactic layers, and Dybvig's bogus claims about the inefficiency of higher order procedures were ratified as part of the R6RS. [17]
When it comes to records, ERR5RS should not attempt to remain bug-compatible with the R6RS. Fortunately, it is possible to design good APIs for ERR5RS records that will interoperate well with the R6RS's procedural and inspection layers, even though ERR5RS APIs may differ in some important respects.
The R6RS syntactic layer uses a fundamentally different notion of record type than the R6RS procedural layer, so it is impossible to design good APIs for records that remain fully bug-compatible with both the R6RS syntactic and procedural layers. It would not be hard to design a less awful syntactic layer than the one in the R6RS, but that is not a worthwhile goal for ERR5RS. The ERR5RS syntactic layer is therefore 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.
[edit] Issues
Should ERR5RS records support single inheritance?
Should ERR5RS records support the non-generative feature of R6RS records?
Should ERR5RS records support the optional "sealed" feature of R6RS records?
Should ERR5RS records support the optional "opaque" feature of R6RS records?
Should ERR5RS records support the per-field mutable/immutable feature of R6RS records?
Should ERR5RS support the record-constructor
descriptors of R6RS records? (Note that the R6RS
make-record-constructor-descriptor
procedure could still be used with ERR5RS record
types even if ERR5RS does not itself support
record-constructor descriptors.)
- Andre and Will would prefer not.
For the draft spec below, I have assumed ERR5RS does support single inheritance and mutable/immutable fields but does not support non-generative, sealed, or opaque records, and does not support record-constructor descriptors. (Wclinger 08:45, 2 October 2007 (PDT))
Should mutable or immutable be the default for fields that specify neither property explicitly?
- For the draft spec below, the default is mutable, mainly because that is more compatible with Scheme's tradition. Andre and Will would prefer that immutable be the default, but that would require some new syntax to allow the convenience of implicit naming for the accessors and mutators of mutable fields.
[edit] Procedural Layer
When a procedure is said to be equivalent to an R6RS procedure, the equivalence holds only when all arguments have the properties required of them by the R6RS specification. ERR5RS does not mandate the R6RS exception semantics for programs that violate the specification.
(make-rtd name fieldspecs)
(make-rtd name fieldspecs parent)
name is a symbol, which matters only to the rtd-name procedure of the inspection layer.
fieldspecs is a vector of field specifiers, where
each field specifier is one of
- a symbol naming the (mutable) field;
- a list of the form
(mutable name), where name is a symbol naming the mutable field; - a list of the form
(immutable name), where name is a symbol naming the immutable field.
The optional parent is an rtd or #f.
It is an error for any of the symbols in fieldspecs to
name more than one of the fields specified by fieldspecs,
but the field names in fieldspecs may shadow field names
in the parent record-type.
- (The non-generative, sealed, and/or opaque features could be specified by symbols that follow the optional parent argument, which is why I am suggesting
#fbe allowed as the parent.) (Wclinger 08:45, 2 October 2007 (PDT))
Returns an R6RS-compatible record-type descriptor. Could be defined (without the recommended error checking) in terms of the R6RS procedural layer by
(define (make-rtd name fieldspecs . rest)
(make-record-type-descriptor
name
(if (null? rest) #f (car rest))
#f #f #f
(vector-map (lambda (fieldspec)
(if (symbol? fieldspec)
(list 'mutable fieldspec)
fieldspec))
fieldspecs)))
(rtd? obj)
Equivalent to the record-type-descriptor?
procedure of the R6RS.
(rtd-constructor rtd)
(rtd-constructor rtd fieldspecs)
rtd is a record-type descriptor, and fieldspecs is an optional vector of symbols.
If no fieldspecs argument is supplied, then
rtd-constructor returns a procedure
that expects one argument for each field of the
record-type described by rtd and returns an
instance of that record-type with its fields
initialized to the corresponding arguments.
Arguments that correspond to the fields of the
record-type's parent (if any) come first.
If fieldspecs is supplied, then
rtd-constructor returns a procedure
that expects one argument for each element of
fieldspecs and returns an instance of the
record-type described by rtd with the named
fields initialized to the corresponding arguments.
It is an error if some symbol occurs more than once in fieldspecs. Fields of a derived record-type shadow fields of the same name in its parent; the fieldspecs argument cannot be used to initialize a shadowed field.
- Note: The optional second argument was proposed by Pavel Curtis, and interoperates well with SRFI 9.
Could be defined in terms of the R6RS procedural layer and ERR5RS inspection layer by:
(define (rtd-constructor rtd . rest)
; Computes permutation and allocates permutation buffer
; when the constructor is created, not when the constructor
; is called. More error checking is recommended.
(define (make-constructor fieldspecs allnames maker)
(let* ((k (length fieldspecs))
(n (length allnames))
(buffer (make-vector n 'some-unspecified-value))
(reverse-all-names (reverse allnames)))
(define (position fieldname)
(let ((names (memq fieldname reverse-all-names)))
(assert names)
(- (length names) 1)))
(let ((indexes (map position fieldspecs)))
; The following can be made quite efficient by
; hand-coding it in some lower-level language,
; e.g. Larceny's mal. Even case-lambda would
; be good enough in most systems.
(lambda args
(assert (= (length args) k))
(for-each (lambda (arg posn)
(vector-set! buffer posn arg))
args indexes)
(apply maker (vector->list buffer))))))
(if (null? rest)
(record-constructor
(make-record-constructor-descriptor rtd #f #f))
(begin (assert (null? (cdr rest)))
(make-constructor
(vector->list (car rest))
(vector->list (record-type-all-field-names rtd))
(record-constructor
(make-record-constructor-descriptor rtd #f #f))))))
(rtd-predicate rtd)
Equivalent to the record-predicate procedure of the R6RS.
(rtd-accessor rtd field)
field is a symbol that names a field of the record-type described by the record-type descriptor rtd. Returns a unary procedure that accepts instances of rtd (or any record-type that inherits from rtd) and returns the current value of the named field.
Fields in derived record-types shadow fields of the same name in a parent record-type.
(rtd-mutator rtd field)
field is a symbol that names a field of the record-type described by the record-type descriptor rtd. Returns a binary procedure that accepts instances of rtd (or any record-type that inherits from rtd) and a new value to be stored into the named field, performs that side effect, and returns an unspecified value.
Fields in derived record-types shadow fields of the same name in a parent record-type.
[edit] Inspection Layer
When a procedure is said to be equivalent to an R6RS procedure, the equivalence holds only when all arguments have the properties required of them by the R6RS specification. ERR5RS does not mandate the R6RS exception semantics for programs that violate the specification.
(record? obj)
Equivalent to its R6RS namesake.
(record-rtd record)
Equivalent to its R6RS namesake.
(rtd-name rtd)
Equivalent to the record-type-name procedure of the R6RS.
(rtd-parent rtd)
Equivalent to the record-type-parent procedure of the R6RS.
(rtd-field-names rtd)
Equivalent to the record-type-field-names
procedure of the R6RS. (That is, it returns
a vector of the symbols that name the fields of the
record-type represented by rtd, excluding
the fields of parent record-types.)
(rtd-all-field-names rtd)
Returns a vector of the symbols that name the fields
of the record-type represented by rtd, including
the fields of its parent record-types, if any, with
the fields of parent record-types coming before the
fields of its children, with each subsequence in the
same order as in the vectors that would be returned
by calling rtd-field-names on rtd
and on all its ancestral record-type descriptors.
Could be defined by
(define (rtd-all-field-names rtd)
(define (loop rtd othernames)
(let ((parent (rtd-parent rtd))
(names (append (vector->list
(rtd-field-names rtd))
othernames)))
(if parent
(loop parent names)
(list->vector names))))
(loop rtd '()))
(rtd-field-mutable? rtd field)
rtd is a record-type descriptor, and field
is a symbol naming a field of the record-type
described by rtd. Returns #t
if the named field is mutable; otherwise returns
#f.
[edit] Syntactic Layer
The syntactic layer consists of SRFI 9 extended with single inheritance and (optional) implicit naming.
All ERR5RS record-type definitions are generative, but ERR5RS drops the SRFI 9 restriction to top level, mainly because the R6RS allows generative definitions wherever a definition may appear.
The syntax of an ERR5RS record-type definition is
<definition>
-> <record type definition> ; addition to 7.1.6 in R5RS
<record type definition>
-> (define-record-type <type spec>
<constructor spec>
<predicate spec>
<field spec> ...)
<type spec> -> <type name>
-> (<type name> <parent>)
<constructor spec>
-> #f
-> #t
-> <constructor name>
-> (<constructor name> <field name> ...)
<predicate spec>
-> #f
-> #t
-> <predicate name>
<field spec> -> <field name>
-> (<field name>)
-> (<field name> <accessor name>)
-> (<field name> <accessor name> <mutator name>)
<parent> -> <expression>
<type name> -> <identifier>
<constructor name> -> <identifier>
<predicate name> -> <identifier>
<accessor name> -> <identifier>
<mutator name> -> <identifier>
<field name> -> <identifier>
The semantics of a record type definition is the same as in SRFI 9: the record type definition macro-expands into a cluster of definitions that
- define the
<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.
An ERR5RS record type definition extends SRFI 9 with the following additional options:
- If a
<parent>expression is specified, then it must evaluate to an rtd that serves as the parent record-type for the record-type being defined. - If
#fis 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.) - If
#tis specified for the constructor or predicate, then the name of the constructor is the type name prefixed bymake-, and the name of the predicate is the type name followed by a question mark (?). - If the constructor name is specified as
#tor as an identifier, then the constructor's arguments correspond to the fields of the parent (if any) followed by the new fields added by this record-type definition. - If a field spec consists of a single identifier, then
- the field is immutable;
- the name of its accessor is the type name followed by a hyphen (
-) followed by the field name.
- If a field spec consists of a list of one identifier, then
- the field is mutable;
- the name of its accessor is the type name followed by a hyphen (
-) followed by the field name; - the name of its mutator is the type name followed by a hyphen (
-) followed by the field name followed by-set!.
[edit] Record Identity
Two ERR5RS records with fields are eqv?
if and only if they were created by the same (dynamic)
call to some record constructor. Two ERR5RS records
are eq? if and only if they are
eqv?.
Apart from the usual constraint that equivalence
according to eqv? implies equivalence
according to equal?, the behavior of
equal? on ERR5RS records is unspecified.
- (Historical note: Pavel Curtis proposed that
equal?behave the same aseqv?; the R6RS apparently does not specify the behavior ofequal?on records.)
A define-record-type form macro-expands
into code that calls make-rtd each time
the expanded record-type definition is executed.
Two ERR5RS record-type descriptors are eqv?
if and only if they were created by the same (dynamic)
call to make-rtd.
[edit] Examples
R6RS library section 6.3 includes two extended examples that provide a nice comparison of the R6RS and ERR5RS record systems, especially since these two examples were designed to highlight the use of R6RS record-constructor descriptors in combination with inheritance.
Using ERR5RS records, the first example becomes:
(define rtd1
(make-rtd 'rtd1 '#((immutable x1) (immutable x2))))
(define rtd2
(make-rtd 'rtd2 '#((immutable x3) (immutable x4)) rtd1))
(define rtd3
(make-rtd 'rtd3 '#((immutable x5) (immutable x6)) rtd2))
(define protocol1
(lambda (p)
(lambda (a b c)
(p (+ a b) (+ b c)))))
(define protocol2
(lambda (n)
(lambda (a b c d e f)
(let ((p (n a b c)))
(p (+ d e) (+ e f))))))
(define protocol3
(lambda (n)
(lambda (a b c d e f g h i)
(let ((p (n a b c d e f)))
(p (+ g h) (+ h i))))))
(define make-rtd1
(protocol1 (rtd-constructor rtd1)))
(define make-rtd2
(let ((maker2 (rtd-constructor rtd2)))
(protocol2
(protocol1
(lambda (x1 x2)
(lambda (x3 x4)
(maker2 x1 x2 x3 x4)))))))
(define make-rtd3
(let ((maker3 (rtd-constructor rtd3)))
(protocol3
(protocol2
(protocol1
(lambda (x1 x2)
(lambda (x3 x4)
(lambda (x5 x6)
(maker3 x1 x2 x3 x4 x5 x6)))))))))
(make-rtd3 1 2 3 4 5 6 7 8 9)
; evaluates to a record whose fields contain
; 3 5 9 11 15 17
The purpose of the R6RS record-constructor descriptors is to automate the idiom shown in the definitions of make-rtd1, make-rtd2, and make-rtd3 above, and to provide an alternative to procedural abstraction when eliminating the duplication of code seen in make-point/abs and make-cpoint/abs below.
The second example illustrates the shadowing of fields in a parent record-type by fields in a derived record-type. Using ERR5RS records, the second example becomes:
(define :point
(make-rtd 'point '#((mutable x) (mutable y))))
(define make-point (rtd-constructor :point))
(define point? (rtd-predicate :point))
(define point-x (rtd-accessor :point 'x))
(define point-y (rtd-accessor :point 'y))
(define point-x-set! (rtd-mutator :point 'x))
(define point-y-set! (rtd-mutator :point 'y))
(define p1 (make-point 1 2))
(point? p1) => #t
(point-x p1) => 1
(point-y p1) => 2
(point-x-set! p1 5)
(point-x p1) => 5
(define :point2
(make-rtd 'point2 '#((mutable x) (mutable y)) :point))
(define make-point2
(rtd-constructor :point2))
(define point2? (rtd-predicate :point2))
(define point2-xx (rtd-accessor :point2 'x))
(define point2-yy (rtd-accessor :point2 'y))
(define p2 (make-point2 1 2 3 4))
(point? p2) => #t
(point-x p2) => 1
(point-y p2) => 2
(point2-xx p2) => 3
(point2-yy p2) => 4
(define make-point/abs
(let ((maker (rtd-constructor :point)))
(lambda (x y)
(maker (abs x) (abs y)))))
(point-x (make-point/abs -1 -2)) => 1
(point-y (make-point/abs -1 -2)) => 2
(define :cpoint
(make-rtd 'cpoint '#((mutable rgb)) :point))
(define make-cpoint
(let ((maker (rtd-constructor :cpoint)))
(lambda (x y c)
(maker x y (color->rgb c)))))
(define make-cpoint/abs
(let ((maker (rtd-constructor :cpoint)))
(lambda (x y c)
(maker (abs x) (abs y) (color->rgb c)))))
(define cpoint-rgb
(rtd-accessor :cpoint 'rgb))
(define (color->rgb c)
(cons 'rgb c))
(cpoint-rgb (make-cpoint -1 -3 'red)) => (rgb . red)
(point-x (make-cpoint -1 -3 'red)) => -1
(point-x (make-cpoint/abs -1 -3 'red)) => 1
[edit] Reference Implementation
ERR5RS records are easy to implement using the R6RS procedural and inspection layers. A quick-and-dirty reference implementation is available at http://www.ccs.neu.edu/home/will/ERR5RS/records.sch
[edit] References
- ↑ http://www.r6rs.org/ratification/results.html
- ↑ http://swiss.csail.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1987/msg00135.html
- ↑ http://swiss.csail.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1987/msg00131.html
- ↑ http://swiss.csail.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1988/msg00155.html
- ↑ http://www-swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1989/msg00147.html
- ↑ http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1992/msg00036.html
- ↑ http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1992/msg00199.html
- ↑ http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1996/msg00086.html
- ↑ http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1996/msg00101.html
- ↑ http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1996/msg00103.html
- ↑ http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1996/msg00115.html
- ↑ http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1996/msg00124.html
- ↑ http://srfi.schemers.org/srfi-9/srfi-9.html
- ↑ http://srfi.schemers.org/srfi-76/srfi-76.html
- ↑ http://srfi.schemers.org/srfi-57/srfi-57.html
- ↑ http://www.r6rs.org/
- ↑ http://www.r6rs.org/ratification/results.html
