19.4 Limited types

Some of Dylan's built-in types are extremely general. When these types are used, the compiler's type inferencing is thwarted, and less efficient code will be generated. The place where this situation is most obvious is in the <collection> types, where the elements of a collection are essentially like multiple slots, all with the same type constraint. For the built-in collections, elements typically have a general default type (often simply <object>), and there can be an arbitrary number of them. The limited mechanism is a way to specify that you expect to store objects of a particular type in the collection, and to specify how many elements will be in the collection.

As an example, in Section 17.2, page 259, the generate-gates method returns a <vector>. Without further information, the compiler must assume that that vector might contain objects of any types. As a result, the following code in the build-simple-airport method from Section 17.5, page 277, will be inefficient:

  let gates = generate-gates(gates-per-terminal, capacity);
  ...
  for (gate in gates)
    gate.connected-to := taxiway-vector;
  end for;

Because the compiler can infer only that gates is a <vector>, it must generate extra code to determine whether each gate has a connected-to method on it. We can use limited types to constrain gate-instances as follows:

define constant <gate-vector> = limited(<vector>, of: <gate>);
define method generate-gates
    (gates-per-terminal :: <vector>, default-gate-capacity :: <size>)
 => (gates :: <gate-vector>)
  let result = make(<gate-vector>, size: reduce1(\+, gates-per-terminal));
  ...
  values(result);
end method generate-gates;

With the limited constraint of the return value of generate-gates, the compiler can ensure that only gate objects will ever be stored in the vector; hence, it can be sure that each gate will be a <gate> and will have a connected-to method.

Note that limited-collection types are instantiable types; that is, you can make an object of a limited type. This capability is different from similar constructs in certain other languages, in which those constructs are only an assertion about the range or type of values to be stored in the collection. Having declared the return value of generate-gates to be a <gate-vector>, it would be an error to return a <vector> instead; hence, we changed the argument to make when constructing result to be <gate-vector> instead of the original <vector>.

If <gate> and connected-to are not open (as described in Section 19.9 and Section 19.10), the compiler can infer that connected-to is used here to set a slot in the gate instance and to further optimize the code generated. We do not delve into the exact details of what the compiler has to know to make this optimization, but it is worth noting that, if either the class or the generic function were open, the optimization could not be made.

Comparison with C++: The Dylan limited-collection types provide a capability similar to that offered by the C++ template classes. Unlike in C++, the base type of a limited-collection type (the equivalent of a C++ class template — in the example above, <vector>) is also a valid type. Dylan's dynamic capabilities mean that Dylan can defer determining the element type of a collection until run time, in effect adapting the class template as it goes along. By using a limited type, the compiler can generate more efficient code.

Another use of limited types is to allow compact representations. We can use limited with the built-in type <integer> to specify numbers with a limited range that can be stored more compactly than integers. It is especially useful to use a limited range in combination with a limited collection; for example,

define constant <signed-byte-vector> 
  = limited(<simple-vector>,
            of: limited(<integer>, min: -128, max 127));

In the preceding example, we define a type that can be represented as a one-dimensional array of 8-bit bytes.

Comparison with C: C provides efficient data representations, because its data types typically map directly to underlying hardware representations. A drawback of C is that its efficient data representations are often not portable: The size of a short int may vary across platforms, for instance. Dylan takes the more abstract approach of describing the requirements of a data type, and letting the compiler choose the most efficient underlying representation. A drawback of the Dylan approach is that it cannot easily be used for low-level systems programming, where data structures must map reliably to the underlying hardware. Most Dylan systems provide a foreign-function interface to allow calling out to C or some other language more suitable to these low-level tasks. Some Dylan systems augment the language with machine-level constructs that provide the level of control necessary while staying within the object model as much as possible.

Comparison with Java: Java recognizes that portable programs need well-defined data types, rather than types that map to the particular underlying hardware differently in each implementation. However, Java retains some of C's concreteness in simply specifying four distinct sizes of integer (in terms of how many binary digits they hold), and forcing the programmer to convert integer types to objects manually, when object-oriented operations are to be performed. In contrast, Dylan's limited-integer types specify, at the program level, the abstract requirements of the type, giving the compiler freedom to map the program requirements as efficiently as possible to the underlying architecture.