Recent

Author Topic: Generics and simple types  (Read 1715 times)

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Generics and simple types
« on: May 30, 2020, 02:38:49 pm »
Apologies for what is almost certainly a dumb and tedious sequence of questions, which I'm sure have been answered many times before.

1) Is it possible to use generics to define min() and max() for arbitrary types for which comparison operators exist, i.e. scalars rather than just classes etc.?

2) What range of compiler versions support this?

3) Can this be inlined efficiently?

4) Can this be generalised efficiently to support e.g. max([a, b, c]); ?

@PascalDragon might recognise (4) as a variant of a tedious question about a reduction operator that I ask every few years :-)

I'm obviously aware that generics (AKA parameterised types) have been in some dialects of Pascal since the early 80s. I've just never had cause to use them.

MarkMLl


MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: Generics and simple types
« Reply #1 on: May 30, 2020, 03:54:54 pm »
@ (4)
Did you miss out on the math unit  ::)
https://www.freepascal.org/docs-html/rtl/math/maxvalue.html and its see also references.
Maybe not complete, but plenty of overloads, even for float type scalars in general.
It would be nice if generics would support more limitations, though, not just classes or interfaces.
« Last Edit: May 30, 2020, 04:17:28 pm by Thaddy »
Specialize a type, not a var.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Generics and simple types
« Reply #2 on: May 30, 2020, 05:49:13 pm »
@ (4)
Did you miss out on the math unit  ::)

No, I'm asking as a general question and using Max() as a convenient example.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Generics and simple types
« Reply #3 on: May 30, 2020, 07:24:02 pm »
1) Is it possible to use generics to define min() and max() for arbitrary types for which comparison operators exist, i.e. scalars rather than just classes etc.?

A generic can (currently) only use operators that are a "part" of the type in question. Meaning either builtin operators or for records operator overloads that are part of the record. Global operator overloads are not supported.

2) What range of compiler versions support this?

Support for generic routines (aka functions, procedures, methods) is added with 3.2. For older versions you'll have to define a generic class or record with non-generic class functions.

3) Can this be inlined efficiently?

As long as the implementation was already parsed (and the function is declared inline) the compiler will try to do so. Please note that 3.2 might be better here than 3.0, cause I had changed/improved a few things there when I implemented support for generic routines.

4) Can this be generalised efficiently to support e.g. max([a, b, c]); ?

As long as the types have builtin operators you should be able to do this with an open array parameter ("aVals: array of T").

Please note that FPC does not yet support implicit specializations (there exists a patch for it, but I've yet to review it), thus you need to specialize explicitly: specialize Max<Longint>([a, b, c]) or for mode Delphi: Max<LongInt>([a, b, c]) (though there might be situations where FPC does not yet parse an expression correctly as mode Delphi allows overloads of symbols (please report such ;) )).

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Generics and simple types
« Reply #4 on: May 30, 2020, 07:39:36 pm »
Thanks for all of that.

4) Can this be generalised efficiently to support e.g. max([a, b, c]); ?

As long as the types have builtin operators you should be able to do this with an open array parameter ("aVals: array of T").

Please note that FPC does not yet support implicit specializations (there exists a patch for it, but I've yet to review it), thus you need to specialize explicitly: specialize Max<Longint>([a, b, c]) or for mode Delphi: Max<LongInt>([a, b, c]) (though there might be situations where FPC does not yet parse an expression correctly as mode Delphi allows overloads of symbols (please report such ;) )).

OK. Must admit that I was thinking of reducing via recursion, i.e. Max([a, b, c]) becomes Max(a, Max([b, c])) and so on. Not sure that plays nicely with generics.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

lucamar

  • Hero Member
  • *****
  • Posts: 4219
Re: Generics and simple types
« Reply #5 on: May 30, 2020, 09:09:28 pm »
OK. Must admit that I was thinking of reducing via recursion, i.e. Max([a, b, c]) becomes Max(a, Max([b, c])) and so on. Not sure that plays nicely with generics.

It shouldn't pose any problem; you can do it with a normal function, why wouln't you be able inside a generic (or class/record method, or type helper or whatever)? Provided the compiler can resolve the expression unambiguosly, all should be dandy :)

Unless, of course, there's some "specialization" problem. It shouldn't, though.
« Last Edit: May 30, 2020, 09:11:38 pm by lucamar »
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus/FPC 2.0.8/3.0.4 & 2.0.12/3.2.0 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Generics and simple types
« Reply #6 on: May 30, 2020, 10:41:29 pm »
It shouldn't pose any problem; you can do it with a normal function, why wouln't you be able inside a generic (or class/record method, or type helper or whatever)? Provided the compiler can resolve the expression unambiguosly, all should be dandy :)

I've looked at implementing an APL-style reduction, i.e. applying an operator to reduce an array of rank n to one of n-1, and there /was/ a problem... unfortunately I can't recall the detail but there was some important bit of information that was lost during the operation.

That was obviously fairly esoteric and I didn't have any particular use for it. If I can find my notes I'll try it with the current compiler... last time was probably in the 2.7.1 era.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Generics and simple types
« Reply #7 on: May 31, 2020, 11:15:40 am »
Here is one example:

Code: Pascal  [Select][+][-]
  1. program tmax;
  2.  
  3. {$mode objfpc}
  4.  
  5. generic function Max<T>(const aArgs: array of T): T;
  6. begin
  7.   if Length(aArgs) = 1 then
  8.     Result := aArgs[0]
  9.   else begin
  10.     Result := specialize Max<T>(aArgs[1..High(aArgs)]);
  11.     if Result < aArgs[0] then
  12.       Result := aArgs[0];
  13.   end;
  14. end;
  15.  
  16. begin
  17.   Writeln(specialize Max<LongInt>([4,8,5]));
  18. end.

And for the fun of it here with Tail Recursion:

Code: Pascal  [Select][+][-]
  1. program tmax;
  2.  
  3. {$mode objfpc}
  4.  
  5. {$push}
  6. {$Optimization TAILREC}
  7. generic function TailMax<T>(const aArgs: array of T; aMax: T; aFirst: Boolean): T;
  8. begin
  9.   if Length(aArgs) = 0 then
  10.     Result := aMax
  11.   else begin
  12.     if aFirst then
  13.       aMax := aArgs[0]
  14.     else if aArgs[0] > aMax then
  15.       aMax := aArgs[0];
  16.     Result := specialize TailMax<T>(aArgs[1..High(aArgs)], aMax, False);
  17.   end;
  18. end;
  19. {$pop}
  20.  
  21. generic function Max<T>(const aArgs: array of T): T;
  22. begin
  23.   Result := specialize TailMax<T>(aArgs, Default(T), True);
  24. end;
  25.  
  26. begin
  27.   Writeln(specialize Max<LongInt>([4,8,5]));
  28. end.

If you look at the generated assembly you can see it generating a jump instruction instead of a call. ;)

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Generics and simple types
« Reply #8 on: May 31, 2020, 11:45:11 am »
If you look at the generated assembly you can see it generating a jump instruction instead of a call. ;)

Thanks for those, /very/ interesting and a substantial impetus to start looking at the 3.2 RC.

I've been looking through stuff and while I can't find the main demo I appeared to be handling reduction by declaring a REDUCE constant of an obscure type, then an operator which would allow me to do things like

Code: [Select]
  average := (REDUCE + arrayOfSomething) / Length(arrayOfSomething);

There was /something/- and I can't remember what- that made lopping dimensions off a dynamic-array-of-dynamic-arrays problematic. The fact that there's a fair chance that generics can now handle this suggests that it would be worth my while taking another look.

I remember that one minor problem was that there wasn't a predefined identity for each of the operators, and no obvious way of specifying one when an operator was redefined which impacts on applying e.g.  REDUCE +  to an empty array... arguably, it should be mandatory that e.g. the additive identity is redefined whenever the + operator is defined for a new type. Similar considerations apply to min and max values of types when the comparison operators are redefined.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Generics and simple types
« Reply #9 on: June 01, 2020, 03:24:28 pm »
I remember that one minor problem was that there wasn't a predefined identity for each of the operators, and no obvious way of specifying one when an operator was redefined which impacts on applying e.g.  REDUCE +  to an empty array... arguably, it should be mandatory that e.g. the additive identity is redefined whenever the + operator is defined for a new type. Similar considerations apply to min and max values of types when the comparison operators are redefined.

On consideration, the identity is the result of applying reduction+operator to an empty array, and the value of the identity is such that application of the operator to a single-element array returns just that element, so it doesn't need to be specified explicitly.

I've found my test file and can confirm that it works with 3.2.0-rc1. I've not yet tried modifying it to use generics- with or without tail recursion. I attach it in case anybody's into contrived language abuse :-)

Interestingly, this was last discussed in one of the MLs in May 2017, and the current 3.0.4 won't compile it due to an inline array constructor. Has 3.2 really been that long in gestation?

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

 

TinyPortal © 2005-2018