Scheme Datatype Facility

A datatype facility may be added to Scheme by loading the file datatype.ss into Chez Scheme.

Syntax

The following extended-BNF rules indicate extensions to Scheme's syntax provided by this facility. Ellipsis (...) indicates zero-or-more occurrences of the preceding syntactic element. Square brackets [ ] indicate an optional element. Terminals are bold and non-terminals are italic.

definition --> ( define-datatype type ( variant component ... ) ... )

expression --> ( type-case type expression type-case-clause ... [ ( else expression ... ) ] )

type-case-clause --> ( ( variant variable ... ) expression ... )

type --> name

variant --> name

component --> name | ( name predicate )

predicate --> name

A name is a Scheme identifier, but not a keyword, and variable is a Scheme variable name. The definition and expression rules extend those of Scheme.

Semantics

( define-datatype type ( variant component ... ) ... ) defines the following with the customary meanings:

• a new 'type' named type

• constructors named make-variant ...

• predicates named type?..

( type-case type expression type-case-clause ... [ ( else expression ... ) ] ) is a conditional expression that evaluates type and expression, checks that type is a 'type' and the value of expression is an element of the given type, and finds the clause that corresponds to its constructor. The matching clause is then evaluated by binding the given variable names to the component values in corresponding position and then evaluating the clause expressions in order and returning the value of the last one. If none of the clauses match, the else clause is evaluated as in a cond expression, if there is an else clause, and an error is raised otherwise.

Example

The following transcript is an example in which:

1. a new datatype analogous to Scheme lists, called dlist, is defined with constructors dcons and dnull (instead of cons and '())
2. a dlist analogous to the Scheme list (1 2) is created
3. a procedure dlength is defined that is analogous to the Scheme lenght procedure
4. the procedures dlength and dlist? are tested.

> (define-datatype dlist (null) (cons first (rest dlist?)))
> (define a-dlist (make-cons 1 (make-cons 2 (make-null))))
> (define dlength
    (lambda (a-dlist)
      (type-case dlist a-dlist
        ((null) 0)
        ((cons f r) (+ (dlength r) 1)))))
> (dlength a-dlist)
2
> (dlist? a-dlist)
#t
> (dlist? 3)
#f

As a further example, the following code implements the finite function ADT of EOPL section 3.6.2, omitting extended-ff* and using the Chez Scheme version of error.

(define-datatype fftype
  (empty-ff)
  (extended-ff sym val ff))

(define create-empty-ff make-empty-ff)

(define extend-ff make-extended-ff)

(define apply-ff
  (lambda (ff symbol)
    (type-case fftype ff
      ((empty-ff)
       (error 'apply-ff "no association for symbol: ~s" symbol))
      ((extended-ff sym val ff)
       (if (eq? symbol sym)
         val
         (apply-ff ff symbol))))))