Concatenation of ordered types

[cmacmackin]

I'd originally intended to overload the concatenation operator for ordered data types. This was to be done by creating a deffered type-bound procedure in the abstract ordered type, like below:

type, extends(countable), abstract, public :: ordered
contains
  ! ...
  procedure(concat_func), private, deferred :: concat
  generic :: operator(//) => concat
end type ordered

abstract interface
  function concat_func(lhs, rhs)
    import ordered
    class(ordered), intent(in) :: lhs, rhs
    class(ordered), allocatable :: concat_func
  end function concat_func
end interface

One consequence is that this means that the returned, concatenated, object must be an allocatable abstract type. In some cases that can be useful, but in others it's a pain because it would require type-guards to assign it to a variable of the actual type.

Another problem is the question of the ordering of the concatenation. My preference would be to order it such that using the pop() method to iterate through the returned object would function as though pop() had been used to iterate through the lhs object and then to iterate through the rhs object. However, doing this requires knowledge of the internal structure of the derived type, which is not available if the interface makes the object class(ordered). Furthermore, the concatenation can be performed much more efficiently if you act on the internal structure of the derived type directly, rather than just accessing it through the (rather few) methods available for class(ordered) objects.

One possibility would be to remove the method definition from ordered and place separate definitions in each concrete derived type. This, of course, would mean that it can't be used in a polymorphic manner. Another possibility would be to keep the definition in the ordered type and use type-guards in each implementation. This would potentially be quite time consuming.

Thoughts?

[szaghi]

Good point @cmacmackin, however

My preference would be to order it such that using the pop() method to iterate through the returned object would function as though pop() had been used to iterate through the lhs object and then to iterate through the rhs object. However, doing this requires knowledge of the internal structure of the derived type, which is not available if the interface makes the object class(ordered).

I do not completely understand this issue. In particular why using pop() do you need low level details of the concrete type? An example can help me to understand.

Furthermore, the concatenation can be performed much more efficiently if you act on the internal structure of the derived type directly, rather than just accessing it through the (rather few) methods available for class(ordered) objects.

Also for this point an example can help me to understand you.

it's a pain because it would require type-guards to assign it to a variable of the actual type.

When dealing with abstracts, at some point, I think it is very difficult to avoid type-guards, at least for not so trivial algorithms. Indeed, I feel that the necessity to add type-guards will be not so hurting, it will clutter the sources, but not so hurting.

One possibility would be to remove the method definition from ordered and place separate definitions in each concrete derived type.

I think it could be preferable to have it in ordered and only if the your above issues cannot be resolved revert back to this solution.

Another possibility would be to keep the definition in the ordered type and use type-guards in each implementation.

This is where I am lost. Why keeping concat into ordered means type-gurads? I need an example, sorry.

Cheers

[cmacmackin]

I do not completely understand this issue. In particular why using pop() do you need low level details of the concrete type? An example can help me to understand.

Putting some more thought into this, I can see that it isn't inherently necessary to know the low-level details of the rhs argument.

Efficiency, however, still represents some obstacles. Let's take the example of a list, constructed from an array. In that case, I'm pretty sure the mot efficient (as in, quickest to run) way to concatenate two objects would be to create a new array from the existing two. However, in order to do that, you need to know the low-level details of the types. You could just use pop to get the information out of the rhs variable, but I'm almost certain that would be more expensive. Thus, if concatenation is defined in ordered, then type-guards would be needed for this sort of efficient manipulation.

Ultimately, I suspect that the best solution is to use type-guards to allow the concatenation to be performed efficiently if lhs (whose type is known, because concat has to be implemented for each concrete descendant of ordered) and rhs are of the same type and perform it less efficiently otherwise.

[szaghi]

Efficiency, however, still represents some obstacles. Let's take the example of a list, constructed from an array. In that case, I'm pretty sure the mot efficient (as in, quickest to run) way to concatenate two objects would be to create a new array from the existing two.

I think so, not sure if it is a golden rule.

Thus, if concatenation is defined in ordered, then type-guards would be needed for this sort of efficient manipulation.

What is intriguing me that type-guard is necessary if the concat result is an allocatable, thus I cannot see a solution without type-guard. In such a case, efficiency should come after a practical algorithm implemented (premature optimization could be dangerous).

I suspect that the best solution is to use type-guards to allow the concatenation to be performed efficiently if lhs (whose type is known, because concat has to be implemented for each concrete descendant of ordered) and rhs are of the same type and perform it less efficiently otherwise.

I agree, but for such a generic container some performance penalties must be taken into account. It would be nice to have a mechanism to immediately identify methods that are potentially not efficient, e.g. a naming conventions that alert users that method xy is not efficient while zy does (but maybe less permissive, non polymorphic, etc...).

[SourcerersApprentice]

I am borrowing from .Net again, here, but it seems that you could store a description of the underlying type in the container class and expose it with a GetType() function? Type information might then be made available to the ordered class using syntax like rhs%Index()%GetType()?

[cmacmackin]

That sounds like a good approach. I don't think I'll go as far as a get_type() method, but perhaps is_fifo() which will be true if it is a first-in-first-out data structure and false if it is last-in-first-out.

On 16-02-26 07:20 PM, SourcerersApprentice wrote:

I am borrowing from .Net again, here, but it seems that you could store a description of the underlying type in the container class and expose it with a GetType() function? Type information might then be made available to the ordered class using syntax like rhs%Index()%GetType()?

— Reply to this email directly or view it on GitHub https://github.com/Fortran-FOSS-Programmers/FIAT/issues/4#issuecomment-189439857.

Chris MacMackin cmacmackin.github.io http://cmacmackin.github.io

[SourcerersApprentice]

Pardon my collision of C# and Fortran style.