Explorer: Mixin phase 1

[DarshalShetty]

Overview

This PR contains an initial implementation of a mixin language feature inspired
from other programming languages like Swift. This implementation is used to
flesh out the details of the mixin proposal which will be coming out in the
future. The ideas behind this PR and the mixin proposal that we are working on
are based off of this document which summarizes the outcome of the open
discussions about mixins with some of the leads. The minutes of the mixin
related open discussions can be found here (in the January discussions) and here
(in the December discussions).

Class inheritance in OOP allows for both code reuse, and subtyping which in turn
allows polymorphism. Currently, interfaces allow for polymorphism while mixins
will be a way to allow code reuse in Carbon. Mixins will also be a way of having
multiple inheritance since we can mix multiple mixins into a class.

A basic example that demonstrates code reuse using mixins is shown below. The
example demonstrates how the Operations mixin’s member method Square can be
reused in both the Point and Complex classes using the mix declaration which
is a member of both classes.

__mixin Operations { // a mixin declaration
  fn Square[me: Self](x:i32) -> i32{
    return x * x;
  }
}

class Point {
  fn Origin() -> Point {
    return {.x = 0, .y = 0};
  }

  var x: i32;
  var y: i32;
  __mix Operations; // a mix declaration
}

class Complex {
  fn Zero() -> Complex {
    return {.r = 0, .i = 0};
  }

  var r: i32;
  var i: i32;
  __mix Operations; // a mix declaration
}


fn Main() -> i32 {
  var p: Point = Point.Origin();
  var c: Complex = Complex.Zero();
  p.x = 3;
  c.r = 3;
  return p.Square(p.y) - c.Square(c.i);
}

The “__” prefix before the “mix” and “mixin” keywords indicate that these
features are experimental, and will be finalized when the proposal for mixins is
ready.

Implementation concepts

What does it mean to mix a mixin into a class/mixin?

A mixin is mixed into a class or mixin declaration by adding a mix declaration
as a member. A mix declaration collects all the members of the mixin mentioned
in the mix declaration and conceptually merges it into the list of members of
the enclosing class/mixin.

Duality of Self in a mixin

The Self in an interface is a type variable, and the Self of a mixin needs
to also behave like a type variable because when a mixin is mixed into a class,
the Self type variable needs to behave like the enclosing class type. So we
need to substitute the Self type variable with the type of the enclosing
class. In the Main function of the above example, the type of the Square
method accessed through the p object of type Point becomes fn Square[me:Point](x:i32) -> i32 after the substitution of Self type variable.

However, it should also be possible to access other mixin members in a mixin
member method body through the Self type. In this way the Self of a mixin
should behave like the Self in a class where it’s just an alias to the type of
the declaration. Thus, the Self of a mixin needs to behave as both the Self
type in a class and the Self type in an interface.

In this PR, the Self in a mixin is a GenericBinding so that it behaves like
a type variable. As a result, it doesn’t behave like the Self in a class and
within a mixin member method we can’t access other mixin members through “me”
which has the type Self. In the final version, the Self in a mixin will be
implemented as new class that has both the properties of the Self in classes and
interfaces.

Summary of changes

New declaration classes for mixin and mix declarations have been added.
MixinDeclaration is very similar to InterfaceDeclaration. A MixDeclaration
holds an expression that will eventually evaluate into a MixinPseudoType (see
next paragraph). During type checking, a pointer to the evaluated
MixinPseudoType is assigned to the MixDeclaration field named
mixin_value_.

The MixinPseudoType class has been created which is very similar to
InterfaceType. This class is the value associated with a MixinDeclaration.
Similarly, the TypeOfMixinPseudoType has also been created which is the type
assigned to a MixinDeclaration. These “values” are not allowed to be used in a
type expression.

The new FindMixedMethodAndType function does the substitution of Self with a
concrete type (as explained in the “duality of Self” section above) while type
checking class member access expressions.

The FindFunction method of NominalClassType has been modified to recursively
search for the function by following the mixins mentioned in MixDeclaration
members.

A collected_members_ field has been added to the TypeChecker class that
stores all the direct and indirect members of all class and mixin declarations.
Indirect members are those members which have been exported by a mixin through a
mix declaration. FindCollectedMembers and CollectMember are helper methods
that retrieve members and add a new member for a particular class/mixin
declaration, respectively. When we have mix declarations as members, we traverse
a graph of MixinDeclaration nodes connected through MixDeclaration members
in order to fetch all indirect members of a class/mixin. This list of indirect
members along with direct members will be used to check for name clashes among
all members during the type checking phase. This means that if a
MixinDeclaration node has multiple in-edges i.e. multiple classes/mixins mix
with the same mixin, then we would have to fetch the indirect members of that
MixinDeclaration multiple times. We don’t need to perform this indirect member
fetching graph traversal multiple times because collected_members_ acts as a
memoized cache that stores the direct and indirect members of all classes/mixins
after they are encountered once during the graph traversal that happens during
type checking. We need not worry about loops forming in the graph at the type
checking phase because the name resolution phase disallows mixing mixins that
haven’t been declared yet.

Mixin features implemented by this PR

• Create a mixin using mixin declarations
• Mix mixins into a class using mix declarations
• Mix mixins into other mixins using mix declarations
• Currently mixins support method members (no field members)

Mixin features that are planned for the future

• Field members within mixin declarations
• Implement a new class for Self of a mixin that behaves as the Self of a class
  as well as the Self of an interface. This means the body of a mixin method
  will be able to access other mixin members.
• Implement the for clause of a mixin declaration which will add constraints
  to another class/mixin trying to mix that mixin. This means that the body of a
  mixin method can access interface members that the classes mixing this mixin
  implements.
• Add type parameters to mixin declarations i.e. generic mixins
• Named mix declarations that will allow to resolve member name clashes without
  changing the names of the members of mixin declarations

Timeline

Now	- Self as type param - Mixed member access through class instance
End of September	- Call mixin method inside mixin declaration - Imports (constraints on entities mixing with a mixin) - private exports
End of October	- Resolve injected mixin member clash (named mix declarations) - impls in mixin declarations
End of November	(until now all mixin members were methods only) - Fields and constructors

[josh11b]

(Commenting just on the PR description so far.)

Leads-question issue #1000 is also relevant. Looks like you are taking the "data fields" approach, which I think is aligned with the thinking at the beginning of the year.

Looking through the past discussions, I'm wondering what position is being taken on these design questions (as a plan):

• Support for external either for members declared in the mixin definition? Or when the mixin is included in a type? Or allow either? Or default to external and use an explicit inject to say that a mixin's member is also a name in its containing type? inject is also a possible way of specifying whether an implementation of an interface is for the containing type.
• Do classes give a name to mixins? You include names as future work, but as an optional feature having to do with avoiding name collisions. I recall names being useful (maybe even needed?) for the constructor (once you support data fields in mixins), and helpful for being able to disambiguate references to mixin members (particularly if things can be external).
• What approach do you intend to use to allow a mixing in the same mixin multiple times? Example use case is a type that can be in multiple intrusive lists. Approaches (probably need both):
  • requiring the mixin to have different parameters in each instantiation, much like our story for implementing an interface multiple times
  • either requiring that all the members of the mixin are external (or none are injected) or at most one use in a type is not external (not sure if you want to insist on one of these or allow both)

My main concern is that it looks to me like some changes are needed to the current approach to support things we expect to need. Right now it looks like all members are injected, which is going to make it hard to support the intrusive list use case (and evolution). And the lack of name when including a mixin in a type is going to make adding data members tricky unless you have some other plan. There are other use cases I expect we need to address, like injecting implementations of virtual methods defined in a base of the containing class, mixins extending base types, and so on, but that looks independent of what is in the current PR.

The "Duality of Self in a mixin" section is a bit at odds with the earlier mixin discussions, where the mixin type and the containing type are distinct. I think this is important, particularly once you start supporting members that are not injected into the containing type, or want to talk about the address of the mixin distinctly from the address of the containing type (though we may need to discuss if that is needed, or if it is sufficient to talk just about the address of members of the mixin). In earlier discussions, the T in mixin Foo for T:! Bar was the containing type, which would implicitly be rewritten to T:! Bar & HasMixin(Foo), Self always meant the mixin itself with type Foo for T, and with casting between T and Self defined in both directions.

[josh11b]

I've only reviewed the test cases, not the code.

[josh11b]

Also:

__mixin M1 {
  fn F1[me: Self](x: Self) -> Self {
     return x;
  }
}

__mixin M2 {
  fn F2() {
  }
  __mix M1;
}

__mixin M3 {
  __mix M1;
  __mix M2;
}

Also:

__mixin M1 {
  fn F1[me: Self](x: Self) -> Self {
     return x;
  }
}

__mixin M2 {
  fn F2() {
  }
  __mix M1;
}

class C {
  __mix M1;
  __mix M2;
}

Are these constructs only a problem if they introduce name conflicts? What happens if the mixins have no members that conflict? Example:

__mixin M1 {
}

__mixin M2 {
  __mix M1;
  __mix M1;
}

Also:

__mixin M1 {
}

class C {
  __mix M1;
  __mix M1;
}

[DarshalShetty]

Yes, all these examples would work because there's no name conflicts. We could add a more thorough check in the future. I'll try to address this in the proposal.

[josh11b]

What if M1 doesn't have any members to conflict (or later they are all marked external or something)? Should this be an error or allowed? It is definitely a problem if it has any members that take space.

__mixin M1 {
  __mix M1;
}

[josh11b]

Isn't M1 incomplete at this point? We haven't seen the closing } of its definition yet. I guess that opens the question about whether you can mix a mixin that has only a forward declaration at the moment.

[josh11b]

FYI, this is counter to my expectation for Self. I'd only expect this test to work with T of for T:! Type.

[jsiek]

We've had trouble understanding the purpose of for T. Perhaps you could explain?
What is your expectation for Self?

The meaning that we're currently using for Self inside a mixin is that it is a placeholder for the class type that the mixin will become a part of.

[josh11b]

My expectation for Self is that it represents the mixin object, and T would represent the containing type.

[jsiek]

(Commenting just on the PR description so far.)

Leads-question issue #1000 is also relevant. Looks like you are taking the "data fields" approach, which I think is aligned with the thinking at the beginning of the year.

Hi Josh,

These are all good questions. The main thing to realize is that the current PR just represents a baby step of exploration on mixins and does not represent any kind of commitment to particular design decisions. We're mainly figuring out the various mechanisms and algorithms that are needed in the type checker and interpreter.

Regarding the data fields vs. base class approaches... the current PR is closer to what you call the base class approach, but like I said, that's not set in stone.

Regarding name clashes... the current PR has zero support for resolving them, but of course we will need to address that.

[jsiek]

Great first step Darshal. Let's keep exploring!