Copyright (C) 2007 Nils M Holm
<nmh @ t3x . org>
This document describes ML-style records for the Scheme programming language. This record system allows to specify records "on the fly" without having to declare the record type first. At the same time records are type safe, because assignments to a record field cannot change the type of that field.
The following text describes
A record is a compound data structure that associates keys with values, much in the same way as an association list. Each key/value pair of a record is called a field. The key of a field is called its tag. Tags are used to address individual fields of records.
Records have a unique external representation that is introduced
by the prefix #r and consists of a list of two-element
lists. Each inner list contains a tag in its car field and a box
(represented by a list) containing a value in its cdr field:
#r((tag1 value1) ... (tagn valuen))
Unlike association lists records are opaque. Values of fields can only by accessed through the interface formed by the procedures described in the following.
A signature of a record is another record whose values are symbols representing types. Each symbol stored in a value slot specifies the type of the value stored in the corresponding field of the original record.
For instance, the record
#r((name "Doe") (phone 12345) (member #f))
has the signature
#r((name string) (phone number) (member boolean))
Two records are of the same record type, if they have the same signature.
Records should have a unique external representation that can be used to specify record literals. Analogous to the vector syntax, records use the general form
#r((tag value) ...)
where each tag is a symbol and each value is a datum
of any type. Each tag in a record must be unique. The form
#r() represents the empty record.
Values of record fields may be records:
#r((name "Doe" #r((mail "john@doe.foo") (phone 12345))))
The record type should be added to the list of disjoint types.
equal?The equal? predicate should be extended in such a
way that it applies record-equal? to two arguments of
the type record.
(record expr ...) => recordCreate a fresh record from arguments. Each expr must evaluate to a valid record field (i.e. a two-element list with a symbol tag in the first slot). No two fields may contain the same tag.
Examples:
(record) => #r()
(record `(foo ,(cons 1 2))) => #r((foo (1 . 2)))
(record '(foo #t) '(bar #\x)) => #r((foo #t) (bar #\x))
(record '(foo #r((bar 0)))) => #r((foo #r((bar 0))))
(record? expr) => booleanReturn #t if expr is a record #f
if expr is not a record.
Examples:
(record? '#r()) => #t
(record? (record '(foo bar))) => #t
(record? 'foo) => #f
(record? '((foo bar))) => #f
(record-ref record tag) => formExtract the value of the field named tag from the given record and return it. If the record has no field with the given tag, report an error.
Examples:
(record-ref '#r((foo bar)) 'foo) => bar
(record-ref '#r((a 1) (b 2) (c 3)) 'c) => 3
(record-ref '#r((foo #r((bar baz)))) 'foo) => #r((bar baz))
(record-ref '#r((foo bar)) 'xxx) => wrong!
(record-set! record tag expr) => unspecificStore the value of expr in the value slot of the field named tag in the given record. The value already stored in the value slot must have the same type as expr. If their types differ, report an error. In addition, if both values are records, they must have the same signature.
Examples:
(define R (record (list 'a 1)
(list 'b "x")
(list 'c #r((x 7)))))
R => #r((a 1) (b "x") (c #r((x 7))))
(record-set! R 'a 5) R => #r((a 5) (b "x") (c #r((x 7))))
(record-set! R 'b "test") R => #r((a 5) (b "test") (c #r((x 7))))
(record-set! R 'c '#r((x 0))) R => #r((a 5) (b "test") (c #r((x 0))))
(record-set! R 'a "foo") => wrong!
(record-set! R 'c '#r((y 7))) => wrong!
(record-set! R 'c '#r((x #t))) => wrong!
(list->record list) => recordConvert a list of fields into a record. The list must either be empty or contain two-element lists with symbols in their car parts exclusively. No two sub-lists may contain the same symbol in their car parts.
Examples:
(list->record '()) => #r()
(list->record '((foo bar))) => #r((foo bar))
(list->record '((a 1) (b "2") (c #\3))) => #r((a 1) (b "2") (c #\3))
(record->list record) => listConvert a record to an association list.
Examples:
(record->list '#r()) => ()
(record->list '#r((a 1) (b "2"))) => ((a 1) (b "2"))
(record->list '#r((a #r((b c))))) => ((a #r((b c))))
(record-equal? record1 record2) => booleanCheck whether two records are equal. Two records R1 and R2 are equal if all of the following conditions are met:
equal?) to the value stored in
the field T of R2.
The order of fields in each record does not matter.
Examples:
(record-equal? '#r() '#r()) => #t
(record-equal? '#r((a 1) (b "2")) '#r((a 1) (b "2"))) => #t
(record-equal? '#r((b "2") (a 1)) '#r((a 1) (b "2"))) => #t
(record-equal? '#r((a 1)) '#r((a 2))) => #f
(record-equal? '#r((a 1)) '#r((b 1))) => #f
(record-equal? '#r((a #r((b 2)))) '#r((a #r((b 2))))) => #t
(record-equal? '#r((a #r((b 2)))) '#r((a #r((b "x"))))) => #f
(record-equal? '#r((a #r((b 2)))) '#r((a #r((x 2))))) => #f
(record-copy record) => recordCreate a fresh copy of the given record.
Examples:
(record-copy '#r()) => #r()
(record-copy '#r((foo bar))) => #r((foo bar))
(record-copy '#r((a 1) (b "2"))) => #r((a 1) (b "2"))
(record-signature record) => signatureReturn the type signature of the given record.
Examples:
(record-signature '#r()) => #r()
(record-signature '#r((foo bar))) => #r((foo symbol))
(record-signature '#r((a 1) (b #t) (c "x")))
=> #r((a number) (b boolean) (c string))
(record-signature '#r((point #r((x 5) (y 7)))))
=> #r((point (record #r((x number) (y number)))))
(record-type-matches? signature record) => booleanCheck whether the given record has the given signature.
Return #t, if the record matches the signature and otherwise
return #f.
Examples:
(define S (record-signature #r((a 1) (b "2") (c #f)))) (record-type-matches? S #r((a 1) (b "2") (c #f) )) => #t (record-type-matches? S #r((a 123) (b "hello") (c #t) )) => #t (record-type-matches? S #r((a 123) (b "hello") (c 123))) => #f (record-type-matches? S #r((a 1) (x "2") (c #f) )) => #f (record-type-matches? S #r((a 1) (b "2") )) => #f
(assert-record-type signature record) => recordCheck whether the given record has the given signature. When the record matches the signature, return the record and otherwise report an error.
Examples:
(define S (record-signature #r((a 1) (b "2")))) (assert-record-type S #r((a 1) (b "2") )) => #r((a 1) (b "2")) (assert-record-type S #r((a 123) (b "hello"))) => #r((a 123) (b "hello")) (assert-record-type S #r((a 123) (x "hello"))) => wrong! (assert-record-type S #r((a 1) (b 123) )) => wrong!
This portable implementation excludes the external representation for records.
(define (wrong m x)
(display m)
(display ": ")
(display x)
(newline)
(#f))
(define record-tag (list '%record))
; Idea of using vectors to introduce a new disjoint type
; taken from SRFI-9 by Richard Kelsey.
(define real-vector? vector?)
(define (vector? x)
(and (real-vector? x)
(or (zero? (vector-length x))
(not (eq? record-tag (vector-ref x 0))))))
(define (record? x)
(and (real-vector? x)
(> (vector-length x) 0)
(eq? record-tag (vector-ref x 0))))
(define (list->record x)
(letrec
((valid-fields?
(lambda (x)
(or (null? x)
(and (pair? (car x))
(symbol? (caar x))
(pair? (cdar x))
(null? (cddar x))
(valid-fields? (cdr x)))))))
(if (valid-fields? x)
(list->vector (cons record-tag x))
(wrong "list->record: bad record structure" x))))
(define (record . x) (list->record x))
(define (record->list x)
(if (record? x)
(cdr (vector->list x))
(wrong "record->list: expected record, got" x)))
(define (record-box x t)
(cond ((assq t (record->list x))
=> (lambda (x) (cdr x)))
(else (wrong "record-box: no such tag"
(list 'record: x 'tag: t)))))
(define (record-ref x t)
(car (record-box x t)))
(define (type-of x)
(cond ((boolean? x) 'boolean)
((char? x) 'char)
((null? x) 'nil)
((number? x) 'number)
((and (pair? x)
(eq? (car x) record-tag))
'record)
((pair? x) 'pair)
((port? x) 'port)
((procedure? x) 'procedure)
((string? x) 'string)
((symbol? x) 'symbol)
((vector? x) 'vector)
(else (wrong "type-of: unknown type" x))))
(define (record-equal? a b)
(letrec
((equal-fields?
(lambda (a b)
(cond ((null? a) #t)
((assq (caar a) b)
=> (lambda (x)
(and (equal? (cadar a) (cadr x))
(equal-fields? (cdr a) b))))
(else #f)))))
(let ((la (record->list a))
(lb (record->list b)))
(and (= (length la) (length lb))
(equal-fields? la lb)))))
(define old-equal? equal?)
(define (equal? a b)
(if (record? a)
(and (record? b) (record-equal? a b))
(old-equal? a b)))
(define (record-copy x)
(letrec
((copy
(lambda (x)
(if (pair? x)
(cons (copy (car x))
(copy (cdr x)))
x))))
(list->record (copy (record->list x)))))
(define (record-signature x)
(letrec
((make-sig
(lambda (x)
(map (lambda (x)
(if (record? (cadr x))
(list (car x)
(list (type-of (cadr x))
(record-signature (cadr x))))
(list (car x) (type-of (cadr x)))))
x))))
(list->record (make-sig (record->list x)))))
(define (types-match a b)
(let ((ta (type-of a))
(tb (type-of b)))
(or (eq? ta tb)
(and (eq? ta 'pair) (eq? tb 'nil))
(and (eq? ta 'nil) (eq? tb 'pair)))))
(define (record-set! x t v)
(let ((b (record-box x t)))
(if (types-match (car b) v)
(if (or (not (record? v))
(record-equal? (record-signature (car b))
(record-signature v)))
(set-car! b v)
(wrong "record-set!: type mismatch"
(list 'record: x 'tag: t 'value: v)))
(wrong "record-set!: type mismatch"
(list 'record: x 'tag: t 'value: v)))))
(define (record-type-matches? sig x)
(record-equal? sig (record-signature x)))
(define (assert-record-type sig x)
(if (not (record-type-matches? sig x))
(wrong "record type assertion failed"
(list 'signature: sig 'record: x))
x))
Copyright (C) 2007 Nils M Holm. All Rights Reserved.
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.