Extension Methods versus Structural Typing of Traits for solving the expression problem

Here is a neat little thing that is tying my brain up into knots: Given a Java-like language, what would you prefer Extension Methods (ala C#) or Traits + Structural Typing. My working (read as: probably incomplete) definition of a trait is an interface with concrete methods. Unless I am mistaken the expressiveness of the two techniques would overlap significantly:

Example 1 (extension methods):

class A {
  int m = 42;
  int f() { 
    return m; 
  }
}

extension B of A {
  int g() { 
    return f() * 2; 
  }
}

A x = new A();
print(x.g());

Example 2 (traits + structural-typing)

class A {
  int m = 42;
  int f() { return m; }
}

trait B {
  abstract int f(); 
  concrete int g() { return f() * 2; }
}

B x = new A(); // Notice: A never explicitly "implements" B
print(x.g());

I haven't looked at Scala in a while, so can you do this in it yet? I believe it is a direction they were going.

For what its worth, the second approach appeals to me a bit more, because it is more discplined, and doesn't clobber the nice encapsulation advantages of classes.

Now if I am not already way out in left-field, are these not both examples of solutions to the "expression problem" (http://www.daimi.au.dk/~madst/tool/papers/expression.txt)?

Well I know that in example two I am cheating because there is a cast of "A" to "B". So I would call it a solution to the "weak expression problem". You can guess what I mean by that.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

The idiomatic translation of

The idiomatic translation of your Example 1 into Scala uses implicit conversions and refinement types,

class A {
  val m = 42
  def f = m
}

implicit def extendedA(a : A) = new {
  def g = a.f*2
}

val x = new A
println(x.g)

As you can see the result has a very similar feel to C# extension methods.

Thanks Miles

Thanks Miles, that is a great example. I didn't realize the Scala did it so nicely.

Now what about example two? Is there an idiomatic translation into Scala?

Example 2

In Scala, given the way example 2 is written structural types wouldn't play a role. We can get pretty close to your example in Scala by mixing the B trait in at the point of object construction.

class A {
  val f = 42
}

trait B {
  def f : Int
  def g = f * 2
}

val x = new A with B

println(x.g)

Example 2 with Implicits

Example 2 can also be done with implicits

class A {
  val f = 42
}

trait B {
  def f : Int
  def g = f * 2
}

implicit def a2b(x : A) = new B {
   def f = x.f
}

val x : B = new A

println(x.g)

Thanks a lot!

I suspected this would be possible in Scala, thanks a lot for showing me how to do it.

Example 2 with Structural Types

Sorry for spamming here. I just realized Example 2 can be done in Scala with structural typing. It's a variant on the implicit a2b version but with a structural type as the input to the implicit.

class A {
  val f = 42
}

trait B {
  def f : Int
  def g = f * 2
}

implicit def withf2b(x : {def f : Int}) = new B {
   def f = x.f
}

val x : B = new A

println(x.g)

I promise this is the last time. :-)

Please continue!

This is cool. Is there a way to name the anonymous struct:
i.e. {def x : Int}?
Otherwise I fear it might have troubles scaling to non-trivial examples.
So far my favorite (as if it matters) is the sol'n you proposed using implicits.

Type aliases

Yes, in Scala you can create aliases for types. E.g. "type WithX = {def x : Int}". This is strictly a type alias like a C's "typedef" or Haskell's "type." It does not define a new type like Haskell's "newtype."

It depends on the language.

It depends on the language. Structural typing has a lot more uses than simply extending a class. Extension methods are a lot easier to implement without problem; a bit easier for most to understand.

Personally, I see extension methods as C# implements them as a (useful) hack. But I also don't think that raw structural typing is the way to go in a general purpose language. Too often there is some implied relation between members and 'just give me something with these two fields' is insufficient.

classic example: equals/hashCode

Too often there is some implied relation between members and 'just give me something with these two fields' is insufficient.

A classic example of this is Object.equals and Object.hashCode, both of which rely on each other to preserve invariants of the standard libraries. There's nothing in the language to ensure that when one is overridden, the other is as well (nor that the combination actually preserves the intended invariants).

Good point

This is a good point and a pervasive problem with programming: all of those unverified (and worse often unstated) assumptions in APIs.

I think perhaps if we allowed contractual specifications in traits and interface, could help with this. This way we could have something like:

trait Hashable
{
  interface {
    bool Equals(x : Hashable);
       ensures { 
         result <-> x.Equals(this);                         
         result -> HashCode() == x.HashCode(); 
         x == null -> result == false;
       }    
    int HashCode();
  }
  invariants {
     this.Equals(this);
  }
}

I think perhaps if we

I think perhaps if we allowed contractual specifications in traits and interface, could help with this.

Maybe. I think though that current mainstream languages don't have too much of a problem with those assumptions. You're already doing OOP, so the most onerous invariants can be contained within the class. I also think that requiring the programmer to explicitly inherit from a type is (usually) a sufficient contract that they won't foul things up (more than usual).

Currently I am of the opinion that the most practical approach is to distinguish between an interface (where an object must simply contain the members) and a class (where an object must explicitly inherit from or be the class). This can be pretty easily implemented within a structural type system. The behavior doesn't vary too much from what most programmers know, but provides a good amount of expressiveness.

I find this...

an awesome (as in superb) idea.

syntax is fine, but...

...what does your example mean? I think if you spend time looking into it, you'll find this far, far more complicated than it first appears. If the assertions of invariants in your code are to be ensured statically, you get to deal with theorem proving and the decades of accompanying research. If instead they're enforced dynamically, you get to deal with object contract checking, with precedent in Eiffel, PLT Scheme contracts, Spec# and the Boogie methodology. Dynamic contract checking has lots of fiendishly hard problems like how to check undecidable or computationally expensive properties, *when* checking should be performed, what guarantees are provided, and when/where are programs allowed to temporarily violate invariants (which is crucial).

We all want the ability to express and (ideally) mechanically verify properties of programs. Example programs without semantics are a good starting point, but they only get you so far.

So many subjects, so little time.

> if you spend time looking into it ...

Actually I have spent some "time" "looking" "into" "it" ... but I don't claim to be an expert ;-)

I think calling the implementation issues "fiendish" is overstating it a bit. I omitted the semantics because there are already a large number of working solutions to choose from.

I think that most people who have studied the problems of contract verification eventually accept that no solution is going to be perfect. I am operating on the premise that any solution is better than just writing assumptions in your docs.

Concepts

The "Concepts" feature in the new C++ standard is very much like this.

Yes, but...

...axioms in concepts are just fancy documentation, they are never checked, neither statically nor dynamically. Nor do they even have a defined meaning.

I prefer traits...

I prefer traits (or Perl roles, which are similar) since I find them more flexible and a more useful programming concept.

The problem I see with OOP is that classes are thought of as data that carries around its behaviour - you cannot separate the two. Traits allow that - for example, I can do (in Sim code):

trait Similarity
   fun isSimilar : any -> bool
   fun isNotSimilar (other : any) = not this.isSimilar(other)

fun do_something : Similarity -> ...

let x = 2

do_something(x extends Similarity with 
                              fun isSimilar(other : any) =
                                    match other with
                                       a : number ->
                                             return a * this >= 0    // Two numbers are similar if they
                                                                     // have the same sign                              
                                       _ -> return false
             )

do_something(x extends Similarity with
                              fun isSimilar(other : any) = 
                                    match other with
                                       s : Similarity ->
                                            // Potentially dangerous - we must ensure we don't cause an infinite loop...
                                            return s.isSimilar(this extends Similarity with fun isSimilar(_) = false)                          
                                       _ -> return false
             )

In this example, traits allow data and code (behaviour) to be "together appart" - the programmer can combine the two however he wants, but they still remain separate and thus extensible.

It is important to note, as RM Schellhas mentioned, that traits differ from (even statically infered) duck typing. This is where Perl 6 gets it right with roles, as implementing a specific role means following a contract (even if only implicit and not enforceable from within the language). For example, under duck typing, if something quack()s and walk()s, it is (assumed to be) a duck, but in reality, if something bark()s, it is not necessarily a dog, it might be a tree... Traits/roles prevent such wrong assumptions.

Traits are more flexible

The traits approach is more attractive because it is more flexible. A trait is not tied to a specific class.

For dodo I chose this approach, but I do not have the notion of "abstract" attribute... my idea is that the compiler would check the attribute exists the moment the trait is applied to a class. Which should be done statically as a result.

example 2 would look like:

class A {
  int m = 42
  int f() { return m }
}

qualifier B {
  int g() { return f() * 2 }
}

def Main:
Main() {
  A x
  qualify x is B
  console!Stdout().Puts(x.g())
}.