Generic Programming: modules parameterized over other modules

[certik]

@klausler suggested in #4 (comment):

From an implementation perspective, the form of polymorphism that I think would solve the most use cases with the least compiler grief would be modules parameterized over other modules, with explicit instantiation.

MODULE LIST(E)
  USE E, ONLY: ELEMENT
  TYPE :: NODE
    TYPE(ELEMENT) :: X
    TYPE(NODE), ALLOCATABLE :: LINK
   CONTAINS
    PROCEDURE :: LENGTH ! & c.
  END TYPE NODE
END MODULE LIST

MODULE MYTYPE
  TYPE :: ELEMENT
    ...
  END TYPE
END MODULE

PROGRAM
  USE MYTYPE, ONLY:
  USE LIST(MYTYPE), INSTANTIATE ! causes compilation of module template instance
END PROGRAM

[gronki]

I do not think this solution is good or generic at all. So what is required from the programmer is to have a module with derived type called in a particular way (ELEMENT). What about a list of integers? What if we have an arbitrary type where we do not control how type is called? Create a wrapper module like:

MODULE WRAPPER
USE MYTYPE2, ONLY: ELEMENT => WHATEVERNAMEWAS
END MODULE

What if I want to use the list for some higher generic container? How do we then ensure that the module has type called ELEMENT? I cannot then create a wrapper module. What if we need two lists, both containing different kind of items? What about generic programming in terms of real/integer kinds? 

I am against half-baked solutions that in 20 years everyone will hate but they will stay in the language forever because "backwards compatibility".

First of all, what do we need the generic programming for? We won't have it for everything unless full-blown C++-like tempates are implemented. Do we need it to create linked lists and containers? I think they should be provided by the language. Do we need it to write one code for any kind of real/integer? Then probably we need something better than parametrized derived types that do not solve any problem.

I think some realistic use cases from the industry should be taken. Everyone seems to be keen on writing containers (as they are missing from the language currently) but the truth is that should not even be the basic use case. So what else?

[gronki]

I did not mean to be disrespectful. What I meant was that i thought this solution was very specific (similarly to parametrized derived types).

[klausler]

I did not ask for this idea to be a top-level issue and I'm not going to waste time defending it.

[certik]

@septcolor thank you. @gronki yes, next time please try to formulate exactly the same point in a nicer way. Instead of saying:

I am against half-baked solutions that in 20 years everyone will hate but they will stay in the language forever because "backwards compatibility".

You can say:

I feel this proposal is half-baked in a sense that it does not solve the problem in its entirety, and it could easily happen that in 20 years that most people will end up not liking this feature, but we will be stuck with this feature forever, because we want Fortran to be backwards compatible. And if that is the case, I would be against it.

There are other ways to say it also. That way you still say exactly what you wanted to point out, and without risking of offending anyone, or putting anybody on the defense. We are all on the same team, and we have to trust each other that none of us wants to introduce some half-baked solutions into Fortran.

I really appreciate that you are participating here, and I am actually in the same camp as you are --- I think it's better if we can figure out how to put features into the language itself (such as arrays which are already in Fortran), as opposed to making the language more general like C++ that does not have arrays and as a consequence there are dozens of incompatible array implementations. However there are other valid points of views. It's not black and white.

[certik]

I did not ask for this idea to be a top-level issue and I'm not going to waste time defending it.

I put this as a top level issue as I think it's worth discussing because it's an interesting idea. Thank you for contributing it.

I am sorry some of the discussion wasn't the nicest, we will do better the next time.

[everythingfunctional]

I think this is an idea worth trying to flesh out. It seems to me you wouldn't want to restrict it to only be parameterized by other modules, because it implicitly couples other modules to the parameterized one. I.e. the module cannot be used if it doesn't conform to the "interface" the parameterized one expects, but this isn't made explicit anywhere. However, treating it like a preprocessor type feature that only operates at the source code level might be able to get you far enough. This all needs more thought.

[klausler]

Here is a draft proposal.

1. Introduction

This proposal defines a means by which modules may be parameterized and instantiated upon
other modules and use-names as a facility for generic programming.

2. Modified and additional requirements to Fortran 2018

An optional module-dummy-list is added to module-stmt; module-name is
replaced with module-spec in use-stmt.

(R1405) module-stmt ::= MODULE module-name [ ( module-dummy-list ) ]
(new)   module-dummy ::= module-dummy-name [ = default-module-spec ]
(new)   module-dummy-name ::= name
(new)   default-module-spec ::= module-spec
(new)   module-spec ::= module-name [ ( module-actual-list ) ]
                    OR  module-dummy-name [ ( module-actual-list ) ]
(new)   module-actual ::= [ module-dummy-name = ] module-spec
                      OR  [ module-dummy-name = ] use-name

(R1409) use-stmt ::= USE [ [ , module-nature ] :: ] module-spec [ , rename-list ]
                 ::= USE [ [ , module-nature ] :: ] module-spec, ONLY: [ only-list ]

3. Changes to text

C1404: "module-name shall be the name of an intrinsic module" shall be changed
to read "the module-spec shall have a module-name that is the name of an intrinsic module"

C1405: "module-name shall be the name of a nonintrinsic module" shall be changed
to read "the module-spec shall have a module-name that is the name of a nonintrinsic module"

14.2.2 paragraph 3, change "If the module-name is the name of both..." to read
"If the module-spec is a module-name without a module-actual-list, and
that module-name is the name of both...".

4. Additional constraints

(R1405) The module-dummy-names of a module-dummy-list shall be pairwise distinct.

(R1405) In a module-dummy-list, a module-dummy-name in a default-module-spec shall
be the module-dummy-name of a previous module-dummy in the same list.

(The usual positional and keyword-matching association scheme of Fortran applies
between a module-dummy-list and a module-actual-list, and will be described in
full later without surprises.)

5. Instantiation

A module with no module-dummy-list constitutes its own instantiation.

For each distinct instantiation of a module, there is corresponding instantiation
of each of its submodules.

A module-spec in a use-stmt constitutes a reference to an instantiation of a module.
In the body of each distinct instantiation of the module, and in each of its submodules,
wherever one of its module-dummy-names appears in a module-spec or as a use-name,
the module-dummy-name is replaced with the associated module-actual in the
module-actual-list of the module-spec that instantiates the module, or else the
default-module-spec of the module-dummy when the module-dummy-name is not
associated with a module-actual.

A module instantiation shall not reference itself directly or indirectly.

6. Example

  MODULE LISTS(MOD, T)
    USE MOD, ONLY: TYPE => T
    TYPE :: LIST
      TYPE(TYPE) :: VALUE
      TYPE(LIST), ALLOCATABLE :: LINK
     CONTAINS
      PROCEDURE :: EMPTY, LENGTH, PUSH_HEAD, BEGIN, NEXT
    END TYPE LIST
    INTERFACE
      MODULE LOGICAL FUNCTION EMPTY(L)
        TYPE(LIST), ALLOCATABLE, INTENT(IN) :: L
      END FUNCTION EMPTY
      MODULE INTEGER FUNCTION LENGTH(L)
        TYPE(LIST), ALLOCATABLE, INTENT(IN) :: L
      END FUNCTION LENGTH
      MODULE SUBROUTINE PUSH_HEAD(L, X)
        TYPE(LIST), ALLOCATABLE, INTENT(IN OUT) :: L
        TYPE(TYPE), INTENT(IN) :: X
      END SUBROUTINE PUSH_HEAD
      MODULE FUNCTION BEGIN(L)
        TYPE(LIST), ALLOCATABLE, INTENT(IN) :: L
        TYPE(LIST), POINTER :: BEGIN
      END FUNCTION BEGIN
      MODULE FUNCTION NEXT(P)
        TYPE(LIST), POINTER, INTENT(IN OUT) :: P
        TYPE(LIST), POINTER :: NEXT
      END FUNCTION NEXT
    END INTERFACE
  END MODULE LISTS

  SUBMODULE(LISTS) IMPLEMENTATIONS
   CONTAINS
    MODULE PROCEDURE EMPTY
      EMPTY = .NOT. ALLOCATED(L)
    END PROCEDURE EMPTY
    MODULE PROCEDURE LENGTH
      LENGTH = 0
      BLOCK
        TYPE(LIST), POINTER :: P
        P => L%BEGIN()
        DO WHILE (ASSOCIATED(P))
          LENGTH = LENGTH + 1
          P => P%NEXT()
        END DO
      END BLOCK
    END PROCEDURE LENGTH
    MODULE PROCEDURE PUSH_HEAD
      TYPE(LIST), ALLOCATABLE :: NEW
      ALLOCATE(NEW)
      NEW%VALUE = X
      IF (.NOT. L%EMPTY()) CALL MOVE_ALLOC(L, NEW%LINK)
      CALL MOVE_ALLOC(NEW, L)
    END PROCEDURE PUSH_HEAD
    MODULE PROCEDURE BEGIN
      IF (L%EMPTY()) THEN
        BEGIN => NULL()
      ELSE
        BEGIN => L
      END IF
    END PROCEDURE BEGIN
    MODULE PROCEDURE NEXT
      IF (ASSOCIATED(P)) THEN
        NEXT => P%LINK
      ELSE
        NEXT => NULL()
      END IF
    END PROCEDURE NEXT
  END SUBMODULE IMPLEMENTATIONS

  MODULE TYPES
    TYPE :: T1
      INTEGER :: FIELD
    END TYPE
  END MODULE

  PROGRAM DEMO
    USE TYPES
    USE LISTS(TYPES, T1), T1_LIST => LIST
    TYPE(T1_LIST), ALLOCATABLE :: T1S
    CALL T1S%PUSH_HEAD(T1(666))
    PRINT *, T1S%LENGTH()
  END PROGRAM

[vansnyder]

I proposed a general facility for parameterized modules in 2004. The J3 paper was 04-383r1. I think it does what Klausler asked for. It does what Magne Haveraaen asked for in Tokyo.

04-383r1.pdf

[klausler]

A variation on this idea seems attractive to me, so I'll jot it down here rather than forget it.

Fortran can support genericity with its current modules by using them as paradigms. For example, to define a generic linked list container, one would first write a model implementation with a fairly empty derived type for the payload in each node. This module would be compilable and testable, and would fully describe all of the requirements on the payload type.

Then, to build a linked list of some specific type, one would reinstantiate the paradigmatic module with a type substitution. The replacement type must support all of the interfaces published for the payload type in the paradigm, and this would be checked.

Substitution of types and parameters (or just their values) in paradigmatic modules would solve the most pressing use cases for generic programming that have been put forward, and would avoid a need for "requirements" or "concepts".