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?

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

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.

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.

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.

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.

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?

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.

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.

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()));
}