Previous chapter: #5: Regularization of the Type System (Change)

Dylan Design Notes: #6: Limited Types (Addition)

Dylan Design Notes

#6: Limited Types (Addition)

Version 1, March 1993

This design note introduces a new generic function, limited, for constructing limited types, and specific methods for creating limited integer types and limited collection types. For example, (limited <integer> min: 0 max: 255) and (limited <array> of: <single-float>) are useful types.

Limited types are not classes. See Dylan Design Note #5: Regularization of the Type System for the general framework allowing types that are not classes.

  1. Limited Type Constructor
  2. Add a new function, limited, with the following definition:

    limited class #key => type [Generic Function] The function limited returns a limited subtype of class. The available keyword arguments depend on the class. Not all classes support limited; the methods for limited are documented individually.

  3. Limited Integer Types
  4. Specify a method for creating limited subtypes of <integer>:

    limited (singleton <integer>) #key min max => type [G. F. Method] Returns a limited integer type, which is a subtype of <integer> whose instances are integers greater than or equal to min (if min: is specified) and less than or equal to max (if max: is specified). If no keyword arguments are specified, the result type is equivalent to <integer>. Limited integer types are not instantiable.

    ;accepts integers between -1000 and 1000 inclusive.
    (define-method f ((x (limited <integer> min: -1000 max: 1000)) ...) 
    ;accepts all strictly positive integers.
    (define-method f ((x (limited <integer> min: 1) ...) ...)
    If w, x, y, and z are integers, the following equivalences hold:
    (instance? x (limited <integer> min: y max: z))
       iff (and (instance? x <integer>) (<= y x z))
    (instance? x (limited <integer> min: y))
       iff (and (instance? x <integer>) (<= y x))
    (instance? x (limited <integer> max: z))
       iff (and (instance? x <integer>) (<= x z))
    (subtype? (limited <integer> min: w max: x) 
              (limited <integer> min: y max: z))
       iff (and (>= w y) (<= x z))
    (subtype? (limited <integer> min: w ...) (limited <integer> min: y))
       iff (>= w y)
    (subtype? (limited <integer> ... max: x) (limited <integer> max: z))
       iff (<= x z)

  5. Limited Collection Types
  6. Specify a method for creating a limited subtype of a collection class:

    limited collection-class #key of size => type [G. F. Method] Returns a limited collection type: a subtype of collection-class whose instances are limited to have elements of a particular type and/or limited to a particular number of elements. A limited collection type is instantiable and accepts the same keyword arguments to make as the collection-class from which it is derived.

    collection-class must be instantiable and not sealed, thus among the predefined collection classes, the following are acceptable: <table>, <array>, <vector>, <stretchy-vector>, <string>, <deque>, and <range>.

    If of: type is specified, each element must be an instance of type. Fetching an element of the collection is guaranteed to return an instance of type. Setting or initializing an element will check that the new element is an instance of type and signal an error of type <type-error> if it is not.

    If size: integer is specified, there must be exactly integer elements. This keyword argument is not accepted if collection-class is stretchy (e.g. <table>, <stretchy-vector>, or <deque>). For <array>, the argument can be a sequence of integers.

    Here are some example expressions that return useful types:

    (limited <array> of: <single-float>)
    (limited <vector> of: (limited <integer> min: 0 max: 255))
    (limited <stretchy-vector> of: <window>)
    (limited <vector> of: <single-float> size: 100)
    (limited <table> of: <symbol>)
    Two limited collection types are disjoint unless they match exactly, because any operation that works on an instance of a supertype must work on an instance of a subtype.

    If c1 and c2 are instantiable, unsealed subclasses of <collection>, t1 and t2 are types, t3 is a type other than a limited collection type, and n1 and n2 are integers, the following equivalences hold:

    (subtype? (limited c1 of: t1 size: n1) (limited c2 of: t2 size: n2))
       iff (and (id? c1 c2) (subtype? t1 t2) (subtype? t2 t1) (id? n1 n2))
    (subtype? (limited c1 of: t1) (limited c2 of: t2))
       iff (and (id? c1 c2) (subtype? t1 t2) (subtype? t2 t1))
    (subtype? (limited c1 size: n1) (limited c2 size: n2))
       iff (and (id? c1 c2) (id? n1 n2))
    (subtype? (limited c1 ...) t3) iff (subtype? c1 t3)


We needed to specify that two limited collection types are disjoint unless they match exactly, because any operation that works on an instance of a supertype must work on an instance of a subtype. Only if the element types are identical can the element and element-setter operations on the supertype also work on the subtype. Otherwise either element on the subtype could return values that a caller of element on the supertype would not expect, or else element-setter on the subtype could fail to accept values that element-setter on the supertype accepts.

Implementation Notes:

Like any type, limited subtypes must be supported by the generic function dispatch mechanism. If the usual approach is used, where the generic function effectively calls object-class and uses that class as a key for a table lookup that finds the applicable methods, then when the class has limited subtypes used as method specializers, an additional dispatch is required. This is similar to the way singletons are usually handled, so the implementation should be straightforward. Perhaps the real cost is implementing the compiler optimizations that are made possible by this, which are not required by the language but which nearly everyone will want to do.

Type-limited collections can be used to hoist type checking from the time when an element is extracted from a collection, back to the time when the element is put into the collection, which could be useful with any user-defined element type. Often the compiler can prove the type check in (setter element) is unnecessary and optimize it out. Limiting the size of a collection allows the compiler to optimize out array bounds checking.

Next chapter: #7: Union Types (Addition)