Previous chapter: #26: New Iteration Protocol (Change)

Dylan Design Notes

Dylan Design Notes: #27: Pseudo-Generic Mappers (Change)

#27: Pseudo-Generic Mappers (Change)

Version 1, January 1994 Copyright (c) 1993-1994, Apple Computer
This design note changes the functions that iterate over an arbitrary number of collections to be functions rather than generic functions. The affected functions are: do, map, map-as, map-into, any?, every?, concatenate, and concatenate-as.
Change the functions do, any?, and every?, all currently specified as generic functions, to instead be specified as functions. Their definitions are unchanged.

Change the functions map-as and concatenate-as, both currently specified as generic functions, to instead be specified as functions. Add the requirement on the value class that size: with a non-negative integer value must be an acceptable initarg for make of the class. Add the following sentence to the description of map-as:

The new collection is created by calling make on the indicated class, with a size: initialization argument whose value is the number of corresponding elements in the argument collections.

Add the following sentence to the description of concatenate-as:

The new sequence is created by calling make on the indicated class, with a size: initialization argument whose value is the sum of the sizes of the arguments.

Change the description of <string> to specify that it supports the init-keywords size: and fill:. size: (default 0) tells how large a string to create. Change the description of <unicode-string> to specify that the default value for size: is 0.

Change the description of <table> and to specify that they support the init-keyword size:. When specified, it provides a hint to the implementation of the class as to the expected number of elements to be stored in the table, which might be used to control how much space to initially allocate for the table. The default value is unspecified.

Add a new abstract class <stretchy-collection>, which is a subclass of <collection> and a superclass of <table>, <stretchy-vector>, and <deque>. It is used to indicate that instances have the property that they may grow or shrink to accomodate adding or removing elements. Remove the corresponding sentence from the description of <stretchy-vector> since it is now redundant. Stretchy collections allow element-setter to be called with a key that is not present in the collection, expanding the collection as necessary to add a new element in that case. Each concrete subclass of <stretchy-collection> must provide or inherit a method for element-setter that behaves as follows when there is not already an element present for the indicated key:

If the class is a subclass of <explicit-key-collection>, adds a new element to the collection with the indicated key.

If the class is a subclass of <sequence>, first calls size-setter on the collection and the key + 1 to expand the sequence. The key must be a non-negative integer.

Change map-into, currently described as a generic function, to instead be specified as a function. Remove the G.F. Method for map-into when the destination is a table. Instead, add to the description of map-into the following (based on the removed method description):

When mutable-collection is an instance of <stretchy-collection>, the usual alignment requirement (described in the section on collection alignment) is relaxed. In this case, the key sequence of mutable-collection is not considered during alignment. Rather, only the key sequences for the source collections are aligned, with procedure called on the corresponding elements. The result of each call to procedure is then stored into mutable-collection with the corresponding key (possibly stretching mutable-collection in the process), using element-setter. Other keys in mutable-collection remain undisturbed.

Change the functions map and concatenate, currently specified as generic functions, to instead be specified as functions. Delete the second paragraph of the description of map, which discusses the default implementation and what additional methods might do in order to compute the result value, replacing it with:

map returns a collection whose value is an instance of the class-for-copy value for the first collection. The new collection is created by calling make on that class, with a size: initialization argument whose value is the number of corresponding elements in the argument collections.

Add the following to the description of concatenate:

concatenate returns a sequence whose value is an instance of the class-for-copy value for the first sequence. The new sequence is created by calling make on the indicated class, with a size: initialization argument whose value is the sum of the sizes of the argument sequences.

Clarify that the class returned by class-for-copy must be a subclass of <mutable-collection>. Add the requirement that it must support the init-keyword size:.


Notes

We made this change because the set of functions for collections specified in the Dylan book contains a number of generic functions that are difficult or impossible to implement efficiently for user defined collection classes. Many of them even present difficulties when only the collection classes defined by the language are involved. The suspect functions are those which accept and iterate over an arbitrary number of collections, and since the relevant argument positions cannot be specialized (they are part of a #rest argument), the effective method cannot directly implement the iteration over those arguments efficiently, but must instead use the generic iteration protocol.

Next chapter: #28: First, Second, Third are Functions (Change)