search

nim-lang / RFCs

A repository for your Nim proposals.
136 stars 23 forks source link

Support for Multiple Inheritence #262

Open avahe-kellenberger opened 4 years ago

avahe-kellenberger commented 4 years ago

What is Multiple Inheritance (MI)

MI allows an object/class to inherit the characteristics and features of more than one parent object or class.

From this point forward I am going to refer to object types as classes for simplicity.

Why would we want it?

I will start by saying, MI is not always the right tool for the job - but sometimes, it is (or at least is a decent option).

Multiple inheritance allows for easy composition of small classes that implement independent functionality and can manage their own state. When used correctly, we end up with a lot of small and reusable code without having to duplicate functionality or data structures.

Why don't you just use ECS?

I've yet to see an ECS implementation that wasn't tedious and difficult to deal with.

MI reads and writes cleanly.

Example of MI in Nim

This is how I envision multiple inheritance in Nim:

type
  Locatable = ref object of RootObj
    x*, y*: float
  Updatable = ref object of RootObj
    elapsedTime: float
  Player = ref object of Locatable, Updatable

method update*(this: Updatable, deltaTime: float) {.base.} = 
  this.elapsedTime += deltaTime

let player = Player(x: 3, y: 15)
echo "x: ", player.x, " y: ", player.y
player.update(1.17)

In this example, Player inherits the x and y properties of Locatable, and we could now invoke the method update with a Player as a parameter.

Locatable and Updatable are free to be reused by any new objects, without having to affect the structure of Player.

Deadly Diamond of Death!

Most complaints regarding the implementation of MI, is The Diamond Problem.

Here is an example: image

Let's create the problem with some Nim pseudo code to illustrate:

type
  Updatable = ref object of RootObj
    elapsedTime: float
  Projectile = ref object of Updatable
  ParticleEmitter = ref object of Updatable
  Missile = ref object of Projectile, ParticleEmitter

method update*(this: Updatable, deltaTime: float) {.base.} = 
  this.elapsedTime += deltaTime

method update*(this: Projectile, deltaTime: float) = 
  procCall Updatable(this).update(deltaTime)
  echo "I update projectiles"

method update*(this: ParticleEmitter, deltaTime: float) = 
  echo "I update particle emitters"
  procCall Updatable(this).update(deltaTime)

# Here, our Missile is a projectile that emits particles.
let missile = Missile()
missile.update(0.15)
# What happens when update is called?

The Diamond:

If we invoke missile.update(0.15) as shown above, we don't know which update should be invoked. Should it call Projectile's update, or Missile's update? In this case, a complier error should be thrown due to ambiguity.

Solutions

There are many ways other languages have solved the diamond problem (see this wiki article about mitigation)

My proposed solution is to force the user to implement the method, and use procCall to invoke any parent implementations they want.

From the above example, the user could write this for the Missile:

method update*(this: Missile, deltaTime: float) = 
  # Invoke both super class implementations of `update`
  procCall Projectile(this).update(deltaTime)
  procCall ParticleEmitter(this).update(deltaTime)

In this case, we could detect calls to the base class (Updatable) and structure our code to prevent multiple invocations. The code would be translated as:

method update*(this: Missile, deltaTime: float) = 
  echo "I update particle emitters"
  procCall Updatable(this).update(deltaTime)
  echo "I update projectiles"

Closing Thoughts

I've seen multiple people wanting some sort of multiple inheritance in Nim (see this post as a recent example) - I think it would be a good change that would not negatively affect those who don't care for the object oriented paradigm.

@Clyybber

mratsim commented 4 years ago

We removed multiple dispatch recently to make the compiler simpler and the code generated faster https://github.com/nim-lang/RFCs/issues/65

Multiple inheritance seems to be introducing complexity and also make the generate code slower as well due to having to introduce branches in the dispatching code (single or multiple inheritance then checking the class methods).

Furthermore, just like multi-dispatch can be implemented in a library with a visitor pattern for a single-dispatch language (not that I like it) with decent performance (all C++ compilers including Clang uses this pattern), you can use macro today to implement multiple inheritance on top of object variants or concepts or methods.

For example here is how you can emulate classes with variant types: https://github.com/mratsim/trace-of-radiance/blob/99f7d85d/trace_of_radiance/support/emulate_classes_with_ADTs.nim#L246-L268

  type
    Color = object
    Ray = object
    HitRecord = object

    Metal = object
    Lambertian = object
    Dielectric = object

  func scatter(self: Metal, r_in: Ray, rec: HitRecord): Option[tuple[attenuation: Color, scattered: Ray]] =
    debugEcho "Scatter on Metal"
  func scatter(self: Lambertian, r_in: Ray, rec: HitRecord): Option[tuple[attenuation: Color, scattered: Ray]] =
    debugEcho "Scatter on Lambertian"
  func scatter(self: Dielectric, r_in: Ray, rec: HitRecord): Option[tuple[attenuation: Color, scattered: Ray]] =
    debugEcho "Scatter on Dielectric"

  declareClass(Material)

  registerSubType(Material, Metal)
  registerSubType(Material, Lambertian)
  registerSubType(Material, Dielectric)
  registerRoutine(Material):
    func scatter(self: Material, r_in: Ray, rec: HitRecord): Option[tuple[attenuation: Color, scattered: Ray]]

You can easily go the over way around, create an abstract scatter type (or generic, or variant or inheritable) and then define your proc on top and via macro "register"/inherit them to other types. This would be significantly faster, especially for gamedev, because it completely avoids GC, uses static dispatch and preserve memory locality instead of dereferencing random heap location and incurring cache misses.

Now beyond what is possible today, instead of inheritance I'd rather have concepts be expanded to work on runtime types https://github.com/nim-lang/RFCs/issues/168 and encompass Rust traits and Go interfaces in terms of capability.

avahe-kellenberger commented 4 years ago

Now beyond what is possible today, instead of inheritance I'd rather have concepts be expanded to work on runtime types #168 and encompass Rust traits and Go interfaces in terms of capability.

Interfaces are okay, but having real multiple inheritance would be less restrictive.

For the implementation, if we can use something better than multiple dispatch I'm all for it. My main goal is to enable the programmer to have the functionality/syntax as I've described in the post.

Araq commented 4 years ago

Also relevant: https://oberoncore.ru/_media/library/templ_a_systematic_approach_to_multiple_inheritance_implementation.pdf

avahe-kellenberger commented 4 years ago

I like that approach, was a good read.

I think the main issue was described in my post, how to know what functions are called when the diamond exists. To reiterate:

Missile inherits Projectile and ParticleEmitter, which both inherit Updatable. These all have a common function, update.

method update*(this: Missile, deltaTime: float) = 
  echo "I update particle emitters"
  procCall Updatable(this).update(deltaTime)
  echo "I update projectiles"

This is the implementation of Missile's update function, when the user does not override the behavior. The procCall is a shared line of code to Updatable from both Projectile and ParticleEmitter. The args passed into the super class' function are unchanged, which is the most common use case - we can search for duplicate invocation in the diamond, like in this example, and reduce it to a single call.

The reason the first echo statement is before procCall, is the implementation of ParticleEmitter's update. This allows the programmer to order code as they see fit, and we maintain the order during compilation.

This was all stated previosly but not explicitly, just wanted to make sure I got the point across. If more explanation is needed, let me know. I could attempt drawing diagrams, write more examples, etc.

Araq commented 4 years ago

What is needed is a prototype implementation via Nim's macro system and then we can see if or how macros are less than ideal.

sighoya commented 3 years ago

What is needed is a prototype implementation via Nim's macro system and then we can see if or how macros are less than ideal.

I think a natural implementation with macros would be to automate the generation of type implementations given in the of list:

multitype Child of Mom, Dad:
    ...
method method_1(c:Child)=...
.
.
.
method method_n+m(c:Child)=...

==>

type Child = object
 var em:ExtendedMom
 var ed:ExtendedDad
 ....
method method_1(em:ExtendedMom,...)=...
.
.
.
method method_n(em:ExtendedMom,...)=...

method method_1(ed:ExtendedDad,...)=...
.
.
.
method method_m(ed:ExtendedDad,...)=...

But then, you are still required to explicitly extract the appropriate object out of Child when passing to a function expecting Mom or Dad which is the annoying part. Alternative solutions to allowing multiple inheritance would be to allow for implicit conversions or to overload the : operator in general, which would be the same thing, I think.

Another problem is to retrieve all methods of a type which lie somewhere in the current module in order to change the signatures to the generated extended types. I think we need some kind of reflection for this, don't know how to solve for this otherwise.

See also: https://dev.to/xflywind/zero-overhead-interface-exploration-in-nim-language-2b3d

sighoya commented 3 years ago

Multiple inheritance seems to be introducing complexity and also make the generate code slower as well due to having to introduce branches in the dispatching code (single or multiple inheritance then checking the class methods).

The question is if we could find a mixed approach to omit branching when multiple parents aren't available, i.e. we only use single inheritance here.

JordyScript commented 3 years ago

Dart has single inheritance but supports mixins. I'm no programming language designer, but it is my understanding that mixins are easier to implement than multiple inheritance, while preserving key benefits. As such it should also be more performant than multiple inheritance is my guess.

What are your thoughts ? has this already been considered? Is this an avenue worth exploring ? Could mixins be a suitable alternative to multiple inheritance for Nim without some of the drawbacks?

n0bra1n3r commented 3 years ago

Mixins can probably be elegantly implemented as a library if https://github.com/nim-lang/Nim/issues/13830 is fixed, combined with concepts maybe. Fixing that issue allows "mixing-in" procs and things outside of an nnkTypedef. There's also https://github.com/nim-lang/Nim/issues/13830#issuecomment-609031271.