To: J3 J3/21-144r2 From: Tom Clune & generics subgroup Subject: Generics Use Cases Date: 2021-June-09 References: N2147, 18-110r1 1. Introduction =============== In WG5/N2147, "Fortran 202X Feature Survey Results -- Final", by Steve Lionel, the proposed F202X feature that had the most interest and the most comments was "Generic Programming or Templates". This feature had a score of 6.21, compared to the next highest score of 5.04 for "Automatic Allocation on READ into ALLOCATABLE character or array". It also had almost four pages of comments, while no other feature had as much as a full page of comments. In spite of the obvious demand for this feature, its complexity made it inappropriate to include in Fortran 202X. Instead it was planned that preliminary work on this feature would be fitted into the schedule of work on Fortran 202X in the hope that this would allow the completion of the work during the development of Fortran 202Y. Any syntax suggestions in this paper are notional, and only for illustrative purposes. This paper uses the term 'template' to refer to a generic entity that can be 'instantiated' into concrete implementations using sets of input 'template parameters'. While there are other possible approaches to generic programming, (e.g., intelligent macros), the guidance from J3 in the formation of the generics subgroup was to pursue something that is at least roughly along the lines of the template approach in other languages. We also note that previous work on Parameterized Modules easily fits within the intentionally vague definition of templates in this context. NOTE: This paper is intended to be a living document. As we develop the F202Y generics features, these use cases will be used for traceability in the subsequent requirements paper. If additional use cases are encountered, or existing ones require modifications, new versions of this use case paper will be submitted for vote. And if any previously approved use cases are subsequently shown to be unworkable or too difficult, the paper will be modified to reflect this. Straw votes will be captured and preserved in subsequent revisions to indicate the degree of support for specific elements. Ideally this paper will be stable once the corresponding requirements document is written and accepted. 2. Use Cases ============ The use cases in this paper are broken into broad categories. Partly this decomposition is to facilitate a gradual increase of complexity, but in some cases these are also expected to drive different sets of requirements. Use cases that have redundant requirements are generally suppressed in this paper, with the exception being when an otherwise redundant use case might resonate with segments of the user community or the committee. The identified categories of use cases are: * Geniric Algorithms (2.1) * Generic Containers (2.2) * Usability, verification, and composition (2.3) 2.1 [ALG] Generic algorithms ---------------------------- 2.1.1 Simple use case - SWAP Perhaps the most common use case of all is the desire to provide a generic template for swapping the values of two entities. The nontrivial aspect of this operation is the need to declare an auxiliary variable to hold one of the values during processing. The Fortran generics facility should provide the means to declare a SWAP template that is applicable for any type that supports assignment. Notionally, the instantiation of the template for a type T should be equivalent to: SUBROUTINE SWAP(a, b) TYPE(T), INTENT(INOUT) :: a TYPE(T), INTENT(INOUT) :: b TYPE(T) :: tmp tmp = a a = b b = tmp END SUBROUTINE SWAP A few variations of SWAP functionality are worth considering. These are primarily intended as proxies for analogous issues that naturally arise in a wide set of use cases that attempt to be as general as possible. In particular, these variants emphasize the important wrinkle that Fortran "type" does not include kind, rank, and other attributes. Variant 1: Arbitrary rank The SWAP instantiation above is designed to work with scalars, but the underlying algorithm is equally applicable to arrays of arbitrary (but consistent) shape. Rank agnostic features planned for F202X are of significant value in this context, but still require a lengthy SELECT RANK construct. It is desirable to provide simple means that enable developers to declare templates that are rank agnostic. E.g., one approach could be to allow integer template parameters that allow the rank to be specified explicitly and then more easily combined with already-planned rank-agnostic features. Variant 2: Parameterized types The instantiation above works for types that lack type parameters, but the underlying algorithm is equally applicable to parameterized types, provided that the actual type parameters of both dummy arguments agree. It is desirable to provide developers with a simple means to declare templates that work with arbitrary parameterized types subject to appropriate requirements. Variant 3: Optional attributes With minor modification the swap algorithm also works with pointers and allocatables. (3A) For pointers, the instantiation would declare the dummy arguments and local variable with the POINTER attribute and use pointer assignment. (3B) For allocatables, the instantiation would declare the dummy arguments and local variable with the ALLOCATABLE attribute and use MOVE_ALLOC. In the case of arrays, the ALLOCATABLE variant could relax the requirement that the shapes of the dummy arguments be the same. Likewise for the case of deferred length-type parameters, the requirement that deferred length type parameters be the same for both dummy arguments could be relaxed. It is desirable to provide developers with simple means to minimize duplication of logic across such variants. At the very least this implies the need for some mechanism to disambiguate ambiguous cases. Straw votes: Note that all straw votes in this paper are worded such that "YES" is the answer that reflects the consensus of generics subgroup. ALG-1: Should the generics facility enable developers to define a scalar SWAP template that will apply to any type that supports assigment? (YES, NO, UNDECIDED, ABSTAIN) ALG-2: Should the generics facility enable developers to easily define a SWAP template that will work with arbitrary ranks? (YES, NO, UNDECIDED, ABSTAIN) ALG-3: Should the generics facility enable developers to write a single SWAP template that can work with arbitrary parameterized types? (YES, NO, UNDECIDED, ABSTAIN) ALG-4: Should the generics facility enable developers to write a single SWAP template that can work with optional attributes? (YES, NO, UNDECIDED, ABSTAIN) 2.1.2 Generic analogs of intrinsic-like procedures --------------------------------------------------- A common category of use cases for generics is the desire to apply the algorithms used in Fortran intrinsic procedures to user-defined types. Indeed some intrinsic procedures are defined to work on any user type: PACK, RESHAPE, SHAPE, SPREAD, etc.. But others such as FINDLOC, MINLOC, MAXLOC, MINVAL, MAXVAL, etc. are restricted to intrinsic types. The primary reason for such restrictions is that, unlike the first set of named intrinsics, these require certain operations to be supported that are not necessarily satisfied by arbitrary user-defined types. Consider the prototypical example of FINDLOC. The underlying algorithm requires comparing individual elements of the array with a specified value. This works for intrinsics because they all support the '==' operator. A generic template for a generalized FINDLOC would work for any user-defined type T that likewise defined a '==' operator that returns a logical when passed two arguments of type T. We note here that one approach to satisfying this use case might be to simply relax the requirements on some intrinsics. While this might itself be desirable, our intent here is to introduce appropriately powerful capabilities to allow Fortran developers to define new templates with comparable functionality. Intrinsic procedures themselves are merely the tip of the proverbial iceberg of relevant use cases, but serve as examples that are readily familiar to all. Straw vote: ALG-5: Should the generics facility enable developers to define templates that extend Fortran intrinsics (FINDLOC, MINLOC, etc) to work with user defined types which support any operations required for a given algorithm? (YES,NO,UNDECIDED,ABSTAIN) 2.1.3 Sorting and Searching --------------------------- Sorting While the need to sort a list of items is somewhat rarer in typical Fortran applications than in some other software communities, it nonetheless arises often enough to be quite relevant. It is typically applied to a rank one array, but sorting algoritms can usually be generalized to other categories of containers (see next section) with appropriate iterators, e.g. Lists and Vectors. A given sorting algorithm can generally be applied to any type that provides a comparison ('<' or '>') operation, or equivalent binary logical predicate. With current Fortran capabilities, the algorithm must be re-implemented for each type. We note however, that some simplification is possible through the judicious use of include files and the newly introduced TYPEOF. A generic sorting procedure has the following requirements: * the ability to have a general type as a generic parameter either as an explicit parameter or as implicit in the iterators; * the ability to associate an assignment operation with a type parameter, either implicitly as a property of all types, or as a property of the type definition, or as an explicit parameter to the generic with a defined interface; * the ability to associate a comparison operation with a generic type parameter, either implicitly as a property of the type definition, or as an explicit parameter to the generic with a defined interface; * and the ability to take one or more iterators as instantiation parameters. It is often necessary to sort the same data according to different comparison criteria. It is therefore desirable that the Fortran generics facility provide means to specify the comparison operation as a separate template parameter. This functionality is less crucial here than it is for the containers use case in the next section, as the comparison operator could usually be passed as a dummy argument to the sorting procedure itself rather than as a template parameter. Searching Searching is the complement of sorting. One typically sorts an array so that it can be searched for specific elements. A binary search algorithm allows the searching of a sorted array with O(ln(n)) cost. For the search to be efficient, it must use the same comparison operation used in the sorting. With current Fortran capabilities, the algorithm must be re-implemented for each type - with some possible simplification through the use of include files. The requirements for the generic search are essentially the same as for the corresponding sort algorithm. Merging It is sometimes useful to merge two sorted collections into one sorted collection. The MERGE procedure must take two collections sorted using the same comparison operation, iterate through both of them in the same direction comparing current elements using the same comparison, and enter them into a third collection according to the results of the comparison. A generic MERGE procedure has the following requirements: * the ability to have a general type as a generic parameter either as an explicit parameter or as implicit in the iterators; * the ability to associate an assignment operation with a type parameter, either implicitly as a property of all types, or as a property of the type definition, or as an explicit parameter to the generic with a defined interface; * the ability to associate a comparison operation with a generic type parameter, either implicitly as a property of the type definition, or as an explicit parameter to the generic with a defined interface; * and the ability to take two iterators as instantiation parameters. Straw votes: ALG-6: Should Fortran generics facilities enable developers to implement a sorting template that works with any type satisfying the criteria listed above? (YES,NO,UNDECIDED,ABSTAIN) ALG-7: Should Fortran generics facilities enable developers to implement a searching template that works with any type satisfying the criteria listed above? (YES,NO,UNDECIDED,ABSTAIN) ALG-8: Should Fortran generics facilities enable developers to implement a merge template that works with any type satisfying the criteria listed above? (YES,NO,UNDECIDED,ABSTAIN) 2.1.4 Complex numerical algorithms ---------------------------------- Many complex numerical algorithms are written for specific intrinsic types and kinds, but are actually applicable to a broader set of types. The applicability of such algoritms is often narrower than the that of containers and intrinsic-like procedures, but templates could still provide powerful, efficient tools within those more specialized domains. Example: Block matrix algebra Mathematical descriptions of algorithms are often expressed in terms of block matrices (https://en.wikipedia.org/wiki/Block_matrix). While such algorithms can always be "flattened" into algorithms working on simple matrices, this conversion is tedious and error prone and generally makes implementations difficult to follow. Some developers may find it useful to implement a template that performs matrix operations on block matrices where types of the blocks are specified as types that support certain numerical operations. Note that each block might itself be a block matrix. As a concrete piece of such an algebra package, consider simple matrix-matrix multiplication on C = A x B Here A, B, and C are m by n, n by p, and m by p arrays of default reals. The (unoptimized) multiplication algorithm can be written for default REAL arrays as: INTEGER :: i, j, k INTEGER :: m, n, p REAL :: A(m,n) REAL :: B(n,p) REAL :: C(m,p) ... DO CONCURRENT (i=1:m, j=1:p) C(i,j) = SUM(A(i,:)*B(:,j)) END DO This algorithm can be generalized to types TA, TB, TC that satisfy certain properties. SUBROUTINE GENERIC_MATMUL(A,B,C) TYPE(TA), INTENT(IN) :: A(:,:) TYPE(TB), INTENT(IN) :: B(:,:) TYPE(TC), INTENT(IN) :: C(:,:) INTEGER :: i, j, k INTEGER :: m, n, p m = size(A,1) ! same as size(C,1) n = size(A,2) ! p = size(B,2) ! same as size(C,2) DO CONCURRENT (i=1:m, j=1:p) C(i,j) = SUM(A(i,:)*TB(:,j)) END DO END SUBROUTINE GENERIC_MATMUL The required properties on types TA, TB, and TC are: * Type TA must support (matrix) multiplication by type TB returning an intermediate type V * There must be an procedure SUM() that takes returns an intemediate type U given a 1d array of type V. Presumably implemented as a separate template. * Type TC must support assignment to the intermediate type U. Note 1: The intermediate types U and V may (and often will) be the same as any of TA, TB, and TC, but the implementation is intended to maximize generality/applicability. Note 2: The "scalar" multiplication of types TB and TB in the nested loop might itself be defined by using the same template, but the template itself is not recursive. Note 3: For performance purposes, it is important that the generic facilities have some mechanism that allows the developer to default over to optimized libraries (e.g., LAPACK) for types that correspond to single and double precision reals and complex. Straw votes: ALG-9: Should the Fortran generics facility provide sufficient generality to define numerical algorithms such as the generalized linear algebra described above? (YES,NO,UNDECIDED,ABSTAIN) ALG-10: Should the Fortran generics facility provide the means to specialize templates for particular types? E.g., to default to use of optimized libraries for intrinsic reals? (YES,NO,UNDECIDED,ABSTAIN) 2.2 [CONTAINERS] Generic Containers ----------------------------------- As scientific models become more complex, an increasing fraction of the lines of code are infrastructure as opposed to direct numerical calculation. Examples of such infrastructure include software layers that couple independently developed subsystems, frameworks for managing distributed parallelism, advanced I/O (e.g., checkpoint/restart via NetCDF), etc. Generally these infrastructure layers evolve as an attempt to avoid code duplication as multiple parts of the system require similar functionality. Software "containers" are abstractions that enable aggregating groups of related entities for convenient and efficient access of hte contained items. Many distinct varieties of software containers have been developed and used. By providing canonical and reliable means to perform common operations, containers can greatly simplify design and implementation of complex algorithms. A closely related construct is that of a container 'iterator', which provides a high-level mechanism to traverse all items within a given container. Such functionality becomes exceptionally important for cantainers which use non-trivial internal storage such as binary trees. Fortran arrays are one specific, and extremeley important variety of software container. Array containers are designed to optimize random access to a _fixed_ size collection of elements, and generally require all contained elements to be of the same dynamic type. Fortran provides excellent mechanisms for declaring and constructing arrays of any type (intrinsic and user-defined) as well as for accessing, storing, and modifying array members (elements) with succinct, tailored syntax: tuples of indices within parens: a(i,j) = x x = a(i,j) a(i,j) = a(i,j)**2 But arrays are merely one common variety of container, albeit exceptionally important for matrices and data represented on logically rectangular domains. Other commonly used container categories include List, Vector, Associative Array (aka Map or Dictionary), Set, Stack, Queue, etc. Unlike Array containers, these others ar generally more dynamic - growing in size as necessary when new elements are added to the container. Here we briefly describe some of the most common varieties of containers. We also note that one approach to supporting the use cases in this section would be to more directly add specific container varieties as 1st-order features of Fortran. However, the wide range of container varieties compounded with the even wider range of potential internal representations and algorithms suggests instead that language should instead provide developers the means to define high-quality container implementations. (We envision that an effort analogous to container templates in STL would readily emerge in the Fortran developer community.) 2.2.1 Vector containers In many ways, Vector containers are quite similar to one-dimensional arrays. Both provide for efficient random access of contained elements via a contiguous block of memory, but Vector containers also provide methods to insert and delete items at the 'back' of the container. If the reserved block of memory is insufficient for a given insertion, a new larger block is automatically allocated and existing data is transferred to the new storage. (Block size is typically doubled in such cases leading to O(n) asymptotic complexity for inserting n items.) Removal of items at other locations is supported, but the operation is inefficient. The need for vectors is often encountered when the number of items that match some criterion is not known in advance. Lacking such functionality, Fortran codes often implement these scenarios with 2 sweeps with nearly identical logic. The first sweep merely counts the number of matches and then allocates an array. The second sweep then populates the array. Use of containers makes such algorithms much simpler to understand in many respects. * As with arrays, vectors require no operations on the contained type except assignment. 2.2.2 Set containers Set containers are intended to store a sorted set of _unique_ objects and provides logarithmic complexity for searching, removal and insertion. * Set containers do not support random access, and therefore require some form of iterator for traversing contained items. * Set containers require that supported types provide an ordering operation. 2.2.3 Associative array (aka Map or Dictionary) Map containers store elements that are formed by a combination of unique keys and values, and thus generally involve 2 distinct types. To some degree, these containers can be regarded as a generalization of Arrays where the index can be something other than an integer, with strings being a common choice for keys. Items stored as a value in a map can be referenced via the key. E.g., temperature = state('temperature') ! "state" maps strings to reals ages('Bob') = 19 ! "ages" maps strings to integers Maps are particularly relevant for coupling complex physical models. The use of standardized names for physical quantities allows for unambigous exchange of data between subsystems. This is generally safer and more legible than using 'magic' indices or functions that look up indices. (The latter can be thought of as a crude implementation of a map.) * Map containers require no operation on the value type except assignment. * Some Map containers require that the key type provides an ordering operation, while others require that there is a hash function. 2.2.4 Miscellaneous containers The specific containers mentioned above are among the most common, but it is worth mentioning some other somewhat common varieties: * Bitset * List (singly linked, doubly linked) 2.2.5 Iterators Iterators provide a simple/consistent mechanism to efficiently loop through all of the elements in a container, or in some cases subsets of a container. For containers such as Vector and Array, these are relatively simple, but for containers such as Set and Map that are implemented with binary trees or hash buckets, the iterator abstraction is of exceptional value to the user of the container. Iterators simultaneously hide complexity and encourage safe coding styles. In pseudo-code iterator usage is typically something like: < declare container > C < declare container iterator > I < declare element > e I = begin(C) loop while I is not end(C) e = get(I) < do something with e > next(I) end loop It is desirable that the generics facility provides features which will allow container implementations to provide companion iterator implementations that provide clear and simple interfaces for container users. 2.2.6 Accessors One important obstacle to implementing convenient containers with existing Fortran syntax, is the inability to overload suitabe syntax for accessing individual container elements. This is in stark contrast with Fortran arrays which provide exceptionally elegant accessors (index list enclosed in parens) to access array elements, and can even be used on the left hand side of an assigment: x = a(i,j,k) + a(i+1,j,k) b(i,j,k) = y Ideally, Fortran should provide some means to enable analogous functionality for those containers that are indexable (e.g., Vector and Map). Variants: Some of the concerns mentioned in the discussion of SWAP in an earlier section, are of significant importance for creating containers that can be used in common contexts. Variant 1: Containing types with type parameters Ideally, a well-written Vector container template should be able to work with almost any type, as the algorithms involved make almost no assumptions about the types involved. However, kind and length type parameters introduce difficulties in how structure components, local variables, dummy variables, and function return values are declared in a generic context. The concern here is much greater than in the case of SWAP owing to the much larger cost of developing variant container templates to support such cases. This problem is particularly evident when one considers deferred-length strings - a common type for which support is desired. Consider the following declarations for an intent in dummy argument, a structure and a function return value for a simple type T: TYPE(T), INTENT(in) :: arg ! dummy TYPE :: CONTAINER TYPE(T), ALLOCATABLE :: elements(:) ! component END TYPE CONTAINER TYPE(T), POINTER :: value ! function return The analogous declarations in the case of a deferred length string dummy argument (due to the length parameter) would be: TYPE(T(LEN=*)), INTENT(in) :: arg TYPE :: WRAPPER TYPE(T), ALLOCATABLE :: string(:) END TYPE WRAPPER TYPE :: CONTAINER TYPE(WRAPPER), ALLOCATABLE :: elements(:) ! component END TYPE CONTAINER TYPE(T(len=:)), POINTER :: value ! function return Without strong support from the language, users of containers are likely to be forced to create wrapper types which will significantly impair the usability of containers. Each container interaction would involve at least one additional step to wrap or unwrap the desired object. Variant 2: Arbitrary rank contained objects The concerns here are similar to those of SWAP. In the case of containers, such use cases are probably somewhat less common than the type parameters, but by no means rare. Variant 3: Type attributes A very common use case for containers is to store pointers rather than actual objects. As above, a potential solution is to use wrapper types, but that would significantly impede the usability of the container. Variant 4: Alternative comparison operation Containers such as Set and Map that use comparison operations to order the contained objects are often used with the same type but different comparison criteria. A common use case of this is for a dictionary whose keys are strings to treat those keys as case-insensitive. Variant 5: Heterogeneous containers It is often desirable to have a container that can contain objects that are of any type that extends some base type, and in the extreme case, objects that are CLASS(*). The inconvenience of wrapper types in this variant is similar to the ALLOCATABLE case above. Straw votes: CONTAINERS-1: Should Fortran's generics facilities support the ability to develop templates for generic containers of arbitrary type T? (YES,NO,UNDECIDED,ABSTAIN) CONTAINERS-2: Should Fortran's generics facilities enable developers to create convenient iterators? (YES,NO,UNDECIDED,ABSTAIN) CONTAINERS-3: Should Fortran's generics facilities allow developers to define easy-to-use accessors both for obtaining objects and for assiging values to objects? (YES,NO,UNDECIDED,ABSTAIN) CONTAINERS-4: Should Fortran's generics facilities provide functionality that would allow a well-written container to work easily with types that have kind and/or length type parameters? (YES,NO,UNDECIDED,ABSTAIN) CONTAINERS-5: Should Fortran's generics facilities provide functionality that allows a well-written container to handle pointers? (YES,NO,UNDECIDED,ABSTAIN) CONTAINERS-6: Should Fortran's generics facilities enable users of relevant containers to indepndently specify a comparison operation at instantiation? (YES,NO,UNDECIDED,ABSTAIN) CONTAINERS-7: Should Fortran's generics facilities enable developers to define covenient-to-use heterogeneous containers? (YES,NO,UNDECIDED,ABSTAIN) 2.3 [CONCEPTS] Usability, verification, and composition ------------------------------------------------------- The use cases discussed in this section are of a rather different character than those above. Consider the following scenario: A complicated template procedure is developed that involves numerous nontrivial operators and/or procedure calls among the dummy arguments. Intantiations of such a template will generally be invalid except when the types passed in the template instantiation parameters support these required operations. A concrete example can be found in the block matrix multiplication use case described in the previous section. 2.3.1 Usability Developers of such a template desire to have a clear, concise, and canonical way to articulate requirements on the template type parameters. Likewise users of such templates would prefer to determine in advance whether their own types will satisify the requirements of a template. Lacking such a mechanism, users must resort to trial-and-error. Further, if their types do not quite work, they are at the mercy of the quality of compiler error messages to infer whether any deficiencies in their types might be remedied. Many users have expressed concern that mistakes in the use of deeply nested templates could be very difficult to debug without features that aid compilers in generating clear error messages. 2.3.2 Verification Developers of complex templates may not only desire to communicate their template requirements to potential users, but also verify that instantiations will produce correct code for all types that meet the requirements. I.e., to determine that their list of requirements is sufficient. Here we envision the case that a developer might miss documenting some necessary operation in the middle of complex code. The developer tests the template with types that just happen to support that undocumented operation, but some end user is not so fortunate. At the same time, while it is recognized that there is value to having enforcement of verification, these protections might be inconvenient during prototyping and/or introduction of additional scaffolding code. 2.3.3 Composition Consider a template that in turn uses one or more nontrivial templates internally. The requirements on such a template are a superset of the requirements for the internally used templates. To avoid tedious duplication, and the associated risks for long term maintenance, it should be possible to encapsulate template requirements as named entities that can be exported and reused. For instance, consider the earlier use case of the MATMUL template. That template uses another template procedure SUM, which requires support for an addition operator (and a "zero" operation) that induces the same requirement for MATMUL. The MATMUL template should be able to include those requirements on types used in SUM in some reasonably elegant manner that avoids code duplication. Straw votes: CONCEPTS-1: Should template developers be able to clearly and concisely communicate the implied requirements on the types used in the template? (YES,NO,UNDECIDED,ABSTAIN) CONCEPTS-2: Should template developers be able to verify that their templates do not use any unspecified implied requirements on the types used in the templates? (YES,NO,UNDECIDED,ABSTAIN) CONCEPTS-3: Should it be possible to encapsulate template requirements for reuse in a composable manner? (YES,NO,UNDECIDED,ABSTAIN)