www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - What is the best way to program over "abstract" types in D?

reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
One advantage of using abstract OO superclasses is that you can 
implement a lot of functionality on the superclass and save 
yourself some work when implementing concrete subclasses. 
However, virtual functions can be slow. In Rust you can do the 
same with "traits", but statically.

What is the best way to create generic interfaces with generic 
implementations of algorithms in D that works with structs (so 
you don't have to require Heap allocation with classes)?

I imagine one way to do it is using mixins in the concrete types, 
then the "abstract type" would essentially emerge as duck-typing. 
But that is really doing it on the wrong level and it is easy to 
make mistakes, so the typing becomes weak.

What would the best pattern in D be for doing statically resolved 
OO, with abstract super types that specify behaviour, over 
structs?
Nov 23 2019
next sibling parent reply mipri <mipri minimaltype.com> writes:
On Saturday, 23 November 2019 at 11:21:32 UTC, Ola Fosheim 
Grøstad wrote:

 ...


I read your question as "can I have typeclasses in D?"

I'll refer to typeclasses in a language other than Rust. You
don't need to know the language. I think you knowing Rust at
all might be clouding your vision, actually.

First, you have some definition of the typeclass:

   :- typeclass named(T) where [
       func name(T) = string
   ].

In English: a type T is a named(T) if there's a function
'name' that accepts a T and returns a string.

This definition might appear in a module with a bunch of
functions that operate on named(T), like

   :- func greeting(T) <= (named(T)).
   greeting(W) = "Hello, " ++ name(W).

This is a function that accepts a value of a type T (provided
that T is named) and then returns the concatenated string. This
looks an awful lot like OOP, but there's no runtime dispatch,
and there are no objects -- indeed, the type could be a
primitive type like int, or float. The exact 'name()' function
that gets called is statically determined.

Finally, there are declarations that some types are, in fact,
instances of the typeclass.

   :- type world ---> world.

   :- instance named(world) where [
       name(world) = "World"
   ].

   :- instance named(int) where [
       name(X) = "Anonymous Integer".
   ]. % (yes, all ints have the same name)

These might appear in completely different modules with their
own unrelated code, written by other people, at a later time,
and with this instance declaration, when the whole program is
compiled together, some integers or the 'world' abstract type
might be handled by a lot of code that only knows that it can
call some name() function to get a string. This code did not
need to be edited to add a 'world' case to a switch to provide
this functionality.

If you're thirsty when by a river you might drink from the
river. If you're thirsty when by a soda machine you might buy a
Coke. But rivers are not made of soda. People using FP
languages reach for typeclasses and people using OOP languages
reach for class hierarchies in the same kinds of situations,
even if there are enormous differences in the exact outcome.

One difference as you noted is that none of the name() calls
is virtual in the typeclass case.

So, what would you need for typeclasses in D? You need all the
same parts: a static declaration of some kind of typeclass, a
static restriction of functions to apply to the typeclass, and
static registration of types to the typeclass.

At least, you need all these parts if you want the same kind of
nice user interface, where invalid registrations are rejected
in a timely manner. Here's a hack, instead:

Typeclass declaration? There isn't one.

Maybe there's documentation:

   /+ Named(T)

      string name(T x);  // define me
   +/

Typeclass restriction? It looks for a magic member. You let
people into the building because they each came in with their
own badge and the badge looks right; you didn't consult a
filing cabinet containing descriptions of all the people
allowed in the building. You still accomplished the goal.
With some caveats: the filing cabinet might've said "cats can
come in too", but cats cannot show a badge. Likewise primitive
types like ints and floats can't be given static members.

   template isNamed(alias T) {
       enum isNamed = hasStaticMember!(T, "secretlyIsNamed");
   }

As used:

   string greet(T)(T x) if (isNamed!T) {
       return "Hello " ~ x.name;
   }

Typeclass registration? Add the member to your types. These
types have no other information to them:

   struct World {
     static char[0] secretlyIsNamed;
   }

   struct Bob {
     static char[0] secretlyIsNamed;
   }

And then of course, define the required functions:

   string name(Bob x) { return "Bob"; }

   string name(World x) { return "World"; }

And then you can call them with static dispatch:

   void main() {
     writeln(greet(World()));
     writeln(greet(Bob()));
   }


This all really works. You get your static polymorphism. The
compiler doesn't let you forget a name() function (if you try
to use it). You have generic code in a library that can be
reused with different types provided by users of the library.

But because it's a hack, there are some unwanted outcomes.
First, other parts of the language can see these
secretlyIsNamed members, and that might cause problems.
They're not really secret. Second, negative typeclasses are not
possible in FP langs, but we have them here:

   string greet(T)(T x) if (!isNamed!T) {
     return "Hello???";
   }

Third, not only can't we register primitive types into
typeclasses like this, we also can't register any type that
already exists or that's provided by third party code. In an FP
lang you could import a serialization module, import some kind
of special container from another module, and then in your own
code say, "special containers are serializeable too and this is
how they should be serialized", even though neither of the
module authors were aware of the other.

I'm sure that someone better at D could make enormous
improvements on this though, with non-intrusive type
registration and typeclass declarations that you can reflect
on, etc.

Here's a complete program:

   import std.stdio: writeln;
   import std.traits: hasStaticMember;

   template isNamed(alias T) {
       enum isNamed = hasStaticMember!(T, "secretlyIsNamed");
   }

   string greet(T)(T x) if (isNamed!T) {
       return "Hello " ~ x.name;
   }
   string greet(T)(T x) if (!isNamed!T) {
       return "Hello?";
   }

   struct World {
       static char[0] secretlyIsNamed;
   }

   string name(World x) { return "World"; }

   struct Alice { }
   string name(Alice x) { return "Alice"; }

   struct Bob {
       static char[0] secretlyIsNamed;
   }

   string name(Bob x) { return "Bob"; }

   void main() {
       writeln(greet(World()));
       writeln(greet(Alice()));
       writeln(greet(Bob()));
   }

Output:

   Hello World
   Hello?
   Hello Bob

https://godbolt.org/z/XgvfS3
Nov 23 2019
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Saturday, 23 November 2019 at 13:17:49 UTC, mipri wrote:

   template isNamed(alias T) {
       enum isNamed = hasStaticMember!(T, "secretlyIsNamed");
   }


this looks like a place to use a  Named uda!

 Named struct World {}
 Named struct Bob {}

or mebbe

 implements!Named

is an option to explore too. Then it cleans up the 
secretlyIsNamed reflection issue.
Nov 23 2019
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
On Saturday, 23 November 2019 at 15:09:44 UTC, Adam D. Ruppe 
wrote:

 On Saturday, 23 November 2019 at 13:17:49 UTC, mipri wrote:

   template isNamed(alias T) {
       enum isNamed = hasStaticMember!(T, "secretlyIsNamed");
   }


 this looks like a place to use a  Named uda!

  Named struct World {}
  Named struct Bob {}

 or mebbe

  implements!Named

 is an option to explore too. Then it cleans up the 
 secretlyIsNamed reflection issue.


I have little to no experience with UDA in D. So I would mark a 
struct as  SetLike or  ArrayLike, but how would I typecheck that 
it has the required methods and aliased types?

I guess it is possible to use introspection somehow?
Nov 23 2019
parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Saturday, 23 November 2019 at 20:22:44 UTC, Ola Fosheim 
Grøstad wrote:

 I guess it is possible to use introspection somehow?


Yeah, you have to write a function that checks it with 
introspection and then static assert on it somewhere.
Nov 23 2019
parent mipri <mipri minimaltype.com> writes:
On Saturday, 23 November 2019 at 21:52:40 UTC, Adam D. Ruppe 
wrote:

 On Saturday, 23 November 2019 at 20:22:44 UTC, Ola Fosheim 
 Grøstad wrote:

 I guess it is possible to use introspection somehow?


 Yeah, you have to write a function that checks it with 
 introspection and then static assert on it somewhere.


This is a little bit better. What it's still missing is
a "there's a function with the same signature as this
other function, s/type1/type2/" kinda check.


abstract class Named {
     string name();
}

template isNamed(alias T) {
     import std.traits: hasUDA;

     enum isNamed = hasUDA!(T, Named);
     static if (isNamed) {
         static foreach (f; __traits(getVirtualFunctions, Named, 
"name")) {
             static assert(__traits(compiles, name(T())));
             //static assert(__traits(compiles, f(T())));
         }
     }
}

string greet(T)(T x) if (isNamed!T) {
     return "Hello " ~ x.name;
}
string greet(T)(T x) if (!isNamed!T) {
     return "Hello?";
}

 Named struct World {};
struct Alice {};
 Named struct Bob {};

string name(World x) { return "World"; }
string name(Alice x) { return "Alice"; }
string name(Bob x) { return "Bob"; }

void main() {
     import std.stdio: writeln;

     writeln(greet(World()));
     writeln(greet(Alice()));
     writeln(greet(Bob()));
}
Nov 23 2019
prev sibling parent Ola Fosheim Gr <ola.fosheim.grostad gmail.com> writes:
On Saturday, 23 November 2019 at 13:17:49 UTC, mipri wrote:

 I read your question as "can I have typeclasses in D?"


I guess you could interpret it that way.



 I think you knowing Rust at
 all might be clouding your vision, actually.


I have hardly ever ran the Rust compiler outside of the online 
one... so not very likely. Though I am keeping an eye on what 
they are working on with traits and generic programming and what 
is coming look promising and clean, but still incomplete in the 
compiler. But yeah, Rust is getting better in the generic 
department.



 These might appear in completely different modules with their
 own unrelated code, written by other people, at a later time,
 and with this instance declaration, when the whole program is
 compiled together, some integers or the 'world' abstract type
 might be handled by a lot of code that only knows that it can
 call some name() function to get a string. This code did not
 need to be edited to add a 'world' case to a switch to provide
 this functionality.


Yes, the basic idea is to be able to specify all the behaviour 
for a full program without making any assumptions about binary 
representation, then at a later stage choose concrete types that 
can be swapped out freely without having any effect on 
correctness. That would be the ideal extreme case...

So you can easily switch between many different actual concrete 
implementations, debug-features, hardware types etc.

You basically write your program using concepts such as SetLike, 
StringLike, ArrayLike and so on, then worry about how they should 
be composed with concrete representations later.



 in a timely manner. Here's a hack, instead:

 Typeclass declaration? There isn't one.


That might be a bit problematic? The goal is to have strong 
typing support from the compiler.



 I'm sure that someone better at D could make enormous
 improvements on this though, with non-intrusive type
 registration and typeclass declarations that you can reflect
 on, etc.


Thanks for sharing your ideas on how to do typeclasses, I think 
you are onto something here.

I will probably resort to parameterising a struct as SetLike with 
a ConcreteSet as the parameter and then find some way to do 
matching as a start. I guess alias this can be used to "emulate" 
the super type binding. But it isn't quite clear to me how to 
best do it in D (or C++) yet.
Nov 23 2019
prev sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Saturday, 23 November 2019 at 11:21:32 UTC, Ola Fosheim 
Grøstad wrote:

 However, virtual functions can be slow.
 [...]
 (so you don't have to require Heap allocation with classes)?


Is your worry in slowness of virtual functions or heap allocation?

Neither is necessarily a problem with classes. The compiler can 
optimize out a lot of virtual calls, and heap allocation is 
pretty easily avoided in your own code (and in theory the 
compiler could optimize that too, but it doesn't as far as I know 
right now).

Take a look at this code:

---

class Base {
         void doLotsOfStuff() {
                 import std.stdio;
                 writeln("I am doing lots of stuff.");
                 writeln(childResult());
                 writeln("cool");
         }

         int defaultValue() { return 5; }

         abstract int childResult();
}

final class Child : Base {
         override int childResult() { return defaultValue() + 5; }
}

void workOnIt(T : Base)(T obj) {
         obj.doLotsOfStuff();
}

void main() {
         import std.typecons;
         auto c = scoped!Child; // on-stack store
         Child obj = c; // get the reference back out for template 
function calls

         workOnIt(obj);
}

---


The three lines in main around scoped make it a stack class 
instead of a heap one.

The `final` keyword on the Child class tells the compiler it is 
allowed to aggressively devirtualize interior calls from it (in 
fact, ldc optimizes that `childResult` function into plain 
`return 10;`) and inline exterior calls to it.

`workOnIt` can similarly optimized automatically in many cases, 
even a a plain function if it gets inlined, but here I showed a 
template. If the optimizer fails on the plain function, trying a 
template like this can allow that `final` to propagate even 
further. In my test, it simply inlined the call.

The only function here that didn't get devirtualized is the 
abstract method itself, childResult. All the surrounding stuff 
was though.


If you want to get even that devirtualized.... there's the 
curiously-recurring template pattern to make it happen.

----
// base is now a template too
class Base(T) {
	void doLotsOfStuff() {
		import core.stdc.stdio; // I switched to printf cuz cleaner asm
		printf("I am doing lots of stuff.\n");

                 // and this cast enables static dispatch...
		printf("%d\n", (cast(T) this).childResult());
		printf("cool\n");
	}

	int defaultValue() { return 5; }

	abstract int childResult();
}

// child inherits base specialized on itself, so it can see final
// down in the base as well as on the outside
final class Child : Base!(Child) {
  	override int childResult() { return defaultValue() + 5; }
}

void workOnIt(T : Base!T)(T obj) {
	obj.doLotsOfStuff();
}

void main() {
	import std.typecons;
	auto c = scoped!Child; // on-stack store
	Child obj = c; // get the reference back out

	workOnIt(obj);
}
----


It depends just how crazy you want to go with it, but I think 
this is less crazy than trying to redo it all with mixins and 
structs - classes and interfaces do a lot of nice stuff in D. You 
get attribute inheritance, static checks, and familiar looking 
code to traditional OO programmers.

BTW the curiously-recurring template pattern is fun because you 
also get static reflection through it! I wrote a little about 
this in my blog a few months ago: 
http://dpldocs.info/this-week-in-d/Blog.Posted_2019_06_10.html


If you really wanna talk about structs specifically, I can think 
about that too, just I wouldn't write off classes so easily! I 
legit think they are one of the most underrated D features in 
this community.
Nov 23 2019
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
On Saturday, 23 November 2019 at 15:06:43 UTC, Adam D. Ruppe 
wrote:

 Is your worry in slowness of virtual functions or heap 
 allocation?


I'm trying to measure how well optimised naive and very generic 
code is, basically an exploration of "expressiveness", "strong 
typing support" and "effort" vs "performance".  If the 
performance with classes and virtuals turns out to be close to 
static structs then that would be quite interesting, indeed.  I 
will probably try out both.

Basically exploring "how high level can I go without paying a 
high price?".


 void main() {
         import std.typecons;
         auto c = scoped!Child; // on-stack store
         Child obj = c; // get the reference back out for 
 template function calls


[…]

 The three lines in main around scoped make it a stack class 
 instead of a heap one.


Ok, thanks, that is worth exploring. Right now the objects I am 
looking at are pure values, so that might be a bit verbose though.


 The `final` keyword on the Child class tells the compiler it is 
 allowed to aggressively devirtualize interior calls from it (in 
 fact, ldc optimizes that `childResult` function into plain


Yes, LDC makes most sense for this purpose.


 The only function here that didn't get devirtualized is the 
 abstract method itself, childResult. All the surrounding stuff 
 was though.


I also guess LTO happens too late in the process to carry over 
information about whether virtuals have been specialised or not.


 If you want to get even that devirtualized.... there's the 
 curiously-recurring template pattern to make it happen.


[…]

 // child inherits base specialized on itself, so it can see 
 final
 // down in the base as well as on the outside
 final class Child : Base!(Child) {
  	override int childResult() { return defaultValue() + 5; }
 }


That was an interesting trick, maybe if LDC emitted information 
about specialization during compilation of individual files then 
the LTO pass could be modified to lock down virtuals as "has not 
been specialised"?



 It depends just how crazy you want to go with it, but I think 
 this is less crazy than trying to redo it all with mixins and 
 structs - classes and interfaces do a lot of nice stuff in D. 
 You get attribute inheritance, static checks, and familiar 
 looking code to traditional OO programmers.


Right, that would be one argument in favour of OO. As a first 
step I am trying to find ways that does not bring the optimizer 
at a disadvantage as a baseline. Then it might be interesting to 
compare that to doing it with OO. The measurable difference 
between two approaches, could be an interesting outcome, I think.



 If you really wanna talk about structs specifically, I can 
 think about that too, just I wouldn't write off classes so 
 easily! I legit think they are one of the most underrated D 
 features in this community.


Yes, I am starting with structs, because pure values ought to be 
easier on the optimizer. So one should be able to go to a fairly 
high abstraction level and still get good performance.

I plan to look at graphs later, and then classes as the main 
construct would make sense.
Nov 23 2019
parent Adam D. Ruppe <destructionator gmail.com> writes:
On Saturday, 23 November 2019 at 16:38:30 UTC, Ola Fosheim 
Grøstad wrote:

 Ok, thanks, that is worth exploring. Right now the objects I am 
 looking at are pure values, so that might be a bit verbose 
 though.


In many cases, you can just do

auto c = scoped!Class(args, to, ctor);

and it mostly works. The only time you need to explicitly mention 
the interface line is when passing to a template by value (since 
then it will try to copy the scoped instance and that is a 
compile error).

So you can frequently do it less verbosely than I did there.


 I also guess LTO happens too late in the process to carry over 
 information about whether virtuals have been specialised or not.


I don't know really. Maybe I used the wrong argument to ldc too 
to enable it.


 Yes, I am starting with structs, because pure values ought to 
 be easier on the optimizer. So one should be able to go to a 
 fairly high abstraction level and still get good performance.


Yeah, just I expect classes will win overall :) We'll see, I 
suppose.
Nov 23 2019