## Monday, June 02, 2008

### Java to Scala - Smaller Inheritance hierarchies with Structural Typing

I was going through a not-so-recent Java code base that contained the following structure for modeling the employee hierarchy of an organization. This looks quite representative of idiomatic Java being used to model a polymorphic hierarchy for designing a payroll generation application.

public interface Salaried {  int salary();}public class Employee implements Salaried {  //..  //.. other methods  @Override  public int salary() {    // implementation  }}public class WageWorker implements Salaried {  //..  //.. other methods  @Override  public int salary() {    // implementation  }}public class Contractor implements Salaried {  //..  //.. other methods  @Override  public int salary() {    // implementation  }}

And the payroll generation class (simplified for brevity ..) that actually needs the subtype polymorphism between the various concrete implementations of the Salaried interface.

public class Payroll {  public int makeSalarySheet(List<Salaried> emps) {    int total = 0;    for(Salaried s : emps) {      total += s.salary();    }    return total;  }}

While implementing in Java, have you ever wondered whether using public inheritance is the best approach to model such a scenario ? After all, in the above class hierarchy, the classes Employee, WageWorker and Contractor does not have *anything* in common except the fact that all of them are salaried persons and that subtype polymorphism has to be modeled *only* for the purpose of generating paysheets for all of them through a single API. In other words, we are coupling the entire class hierarchy through a compile time static relationship only for the purpose of unifying a single commonality in behavior.

Public inheritance has frequently been under fire, mainly because of the coupling that it induces between the base and the derived classes. Experts say Inheritance breaks Encapsulation and also regards it as the second strongest relationship between classes (only next to friend classes of C++). Interface driven programming has its advantages in promoting loose coupling between the contracts that it exposes and their concrete implementations. But interfaces in Java also pose problems when it comes to evolution of an API - once an interface is published, it is not possible to make any changes without breaking client code. No wonder we find design patterns like The Extension Object or strict guidelines for evolution of abstractions being enforced in big projects like Eclipse.

Finer Grained Polymorphism

Structural typing offers the ability to reduce the scope of polymorphism only over the subset of behaviors that need to be common between the classes. Just as in duck typing, commonality in abstractions does not mean that they belong to one common type; but only the fact that they respond to a common set of messages. Scala offers the benefit of both the worlds through its implementation of structural typing - a compile time checked duck typing. Hence we have a nice solution to unify certain behaviors of otherwise unrelated classes. The entire class hierarchy need not be related through static compile time subtyping relationship in order to be processed polymorphically over a certain set of behaviors. As an example, I tried modeling the above application using Scala's structural typing ..

case class Employee(id: Int) { def salary: Int = //.. }case class DailyWorker(id: Int) { def salary: Int = //.. }case class Contractor(id: Int) { def salary: Int = //.. }class Payroll {  def makeSalarySheet(emps: List[{ def salary: Int }]) = {    (0 /: emps)(_ + _.salary)  }}val l = List[{ def salary: Int }](DailyWorker(1), Employee(2), Employee(1), Contractor(9))val p = new Payrollprintln(p.makeSalarySheet(l))

The commonality in behavior between the above classes is through the method salary and is only used in the method makeSalarySheet for generating the payroll. We can generalize this commonality into an anonymous type that implements a method having the same signature. All classes that implement a method salary returning an Int are said to be structurally conformant to this anonymous type { def salary: Int }. And of course we can use this anonymous type as a generic parameter to a Scala List. In the above snippet we define makeSalarySheet accept such a List as parameter, which will include all types of workers defined above.

Actually it gets better than this with Scala. Suppose in the above model, the name salary is not meaningful for DailyWorkers and the standard business terminology for their earnings is called wage. Hence let us assume that for the DailyWorker, the class is defined as ..

case class DailyWorker(id: Int) { def wage: Int = //.. }

Obviously the above scheme will not work now, and the unfortunate DailyWorker falls out of the closure of all types that qualify for payroll generation.

In Scala we can use implicit conversion - I call it the Smart Adapter Pattern .. we define a conversion function that automatically converts wage into salary and instructs the compiler to adapt the wage method to the salary method ..

case class Salaried(salary: Int)implicit def wageToSalary(in: {def wage: Int}) = Salaried(in.wage)

makeSalarySheet api now changes accordingly to process a List of objects that either implement an Int returning salary method or can be implicitly converted to one with the same contract. This is indicated by <% and is known as a view bound in Scala. Here is the implementation of the class Payroll that incorporates this modification ..

class Payroll {  def makeSalarySheet[T <% { def salary: Int }](emps: List[T]) = {    (0 /: emps)(_ + _.salary)  }}

Of course the rest of the program remains the same since all conversions and implicit magic takes place with the compiler .. and we can still process all objects polymorphically even with a different method name for DailyWorker. Here is the complete source ..

case class Employee(id: Int) { def salary: Int = //.. }case class DailyWorker(id: Int) { def salary: Int = //.. }case class Contractor(id: Int) { def wage: Int = //.. }case class Salaried(salary: Int)implicit def wageToSalary(in: {def wage: Int}) = Salaried(in.wage)class Payroll {  def makeSalarySheet[T <% { def salary: Int }](emps: List[T]) = {    (0 /: emps)(_ + _.salary)  }}val l = List[{ def salary: Int }](DailyWorker(1), Employee(2), Employee(1), Contractor(9))val p = new Payrollprintln(p.makeSalarySheet(l))

With structural typing, we can afford to be more conservative with public inheritance. Inheritance should be used *only* to model true subtype relationship between classes (aka LSP). Inheritance definitely has lots of uses, we only need to use our judgement not to misuse it. It is a strong relationship and, as the experts say, always try to implement the least strong relationship that correctly models your problem domain.

Alaz said...

I've caught the whole idea, many thanks for the post, but there is some discrepancy in your last sample: what's the idea of declaring makeSalarySheet with view bound, while you make an implicit conversion of Contractor to Salaried in the List instantiation already -- as far as I understand the List already contains Salaried...

gambistics said...

I think you are not quite precise. You are talking about implementing an interface as if it was inheritance which it isn't.

Implementing an interface is like a marker. You specify that you adhere to a specific contract identified by the name and the package of the interface.

If you use structural subtyping you rely on a contract as well: That the implementing class has the method of the specified type and has the right semantics.

But: An interface and the contained type themselves don't specify the contract alone. The contract is made up from the interface specification in the programming language AND the written documentation which furtherly defines the expected semantics. And then it's given a name within a namespace.

If you implement the interface you explicitly say that you have understood what the interface (the contract) is about.

What you are proposing (which btw is exactly the same with duck typing) is omitting the namespace from a contract and solely relying on the types and the name of a method as a contract. That might be the right thing in smaller environments since there probably won't be any naming conflicts. In the large it probably will break sooner or later.
(For example if some consumer of your objects expects different semantics from their method salary:Int)

To sum up: interfaces and structural subtyping have the same purpose but different extents.

Interfaces are (hopefully) immutable and embedded in a namespace uniquely identifiable while structural subtyping only scratches the surface of a specification.

And the responsibilities are shifted: Implementors of interfaces have to make sure their implementation adheres to the documented interface semantics when implementing but the implementations are free to be used in that sense afterwards (as a perfectly valid example of the mentioned LSP btw). If you use structural subtyping you have to check the semantics when calling a consumer. So the consumer has to be documented to include some information what type of objects it expects.

Debasish said...

@gambistics: I fully agree with what u say and have never doubted the benefits of using interfaces and subtype polymorphism. But structural types allow implementing a level of polymorphism at a much lower granularity than the entire type hierarchy. I can say that Employee, Contractor and WageWorker do not have a common contract as far as the types are concerned. They are only related by the commonality that each of them needs to implement a method salary() that returns an Int (or a conversion thereof). This definitely can lead to accidental conformity with other unrelated types that implement the method with the same signature. But in Java we have lots of instances where there has been a plethora of interface explosion just for the sake of implementing fine grained commonality between otherwise unrelated classes. Structural typing provides a nice work around for such cases.
And u r right - this is nothing but duck typing. And for Scala it is statically checked duck typing.

Cedric said...

Hi Debasish,

In my experience, structural typing looks cute on the outside but doesn't scale when the type you are describing becomes more complex. Very quickly, you find yourself with a lot of repetition in your code which makes it 1) harder to read and 2) better captured in an interface or a trait that will convey the intent in a much more meaningful manner than a loose list of methods and properties.

More details here: http://beust.com/weblog/archives/000476.html

--
Cedric

Cedric said...

About your previous comment: actually, I see things from the opposite direction. Structural typing allows accidental matches from objects that do not necessarily conform to the contract you are expecting. Implementing an interface by accident is, on the other hand, extremely unlikely.

I don't see any problems with an explosion of interfaces. If they allow the developer to describe the problem space more accurately, then more power to both producers and consumers of that code. This is actually a direction that has intrigued me for a while, which I called "Quantum Software Design" a few years ago (http://beust.com/weblog/archives/000312.html) and that Rickard explores in much more depth under the name "Composite Oriented Programming" in his framework Qi4j (http://www.qi4j.org/).

Debasish said...

@cedric: Hi Cedric -
Thanks for visiting my blog!

I know you r a big proponent of interface based programming. However, sometimes I feel that people tend to overuse interfaces in Java. Like the example that I have mentioned in my post, the employee types do not have anything in common except the salary part. Do u think it is still better to model them based on a common supertype because of the fact that all of them get paid through a common interface ? Don't u feel that we r trying to couple them at a much bigger level through subtype polymorphism than the commonality that they deserve ? And that, for this case structural typing implements the level of polymorphism at a much smaller level, the method level, which they actually are, rather than the entire type level.

What do u think ?

Cedric said...

Hi Debasish,

I've been an avid reader of your blog for a while, today is just one of the few times where I disagree with some of your points :-)

Of course, interfaces can be abused, but I really don't think that the number of methods should be the deciding factor in the decision to use one, which is what you seem to imply here ("it's just one method, it's not worth introducing an interface for this"). I am absolutely fine with the idea of introducing an interface that only contains one method as long as it makes semantic sense. I much prefer to read ConvertibleToXml than looking inside a structural type for a method toXml() which might explain what this type is for. Or not. And if you expand this structural type to more than one method, it becomes extremely hard to justify its existence at all.

Also, to echo a point made above: to me, interfaces define contracts much more than they define a common subtype, so I don't see them increasing heavy coupling as much as you do (quite the opposite, actually).

My biggest gripe with structural typing remains the blatant violation of the DRY principle. Imagine three methods accepting the same structural type made of three methods or properties, and you are now facing code that is painfully redundant, needlessly verbose and that is screaming to your face "refactor me!".

Anyway, good stuff, keep it up!

--
Cedric

Daniel said...

You can actually do a little better than forcing the existing of a Salaried class:

implicit def wageToSalary(in: {def wage: Int}) = new {
def salary = in.wage
}

With respect to the suitability of structural types, I agree that this is probably a bad example. In this particular case, I would have used a superclass or trait instead of going with an anonymous interface (structural type).

On the flip side, I disagree that structural typing has no place in good OO design. There was a situation I ran into recently where structural typing saved a huge mess of contrived inheritance, making my life just that much easier. I'll agree that it's not a silver bullet, but it's still a nice tool to keep in your back pocket for when you really need it.

Debasish said...

Hi Cedric / Daniel -

I am not claiming that structural typing is a substitute for public inheritance or interface based programming in Java. But I think it addresses one of the weaknesses of Java type systems. In Java you have to statically bind a class to an interface in order to use the contract. In a way this is good since it enforces a discipline in how abstractions evolve. But it also robs us of the flexibility to adapt classes dynamically to an existing hierarchy based on methods that they implement. In the example that I have posted in the blog, if I had to adapt some employees from other systems that *do* not implement the specific Salaried interface (and I do not have access to that source code as well), there is no way in Java that I can treat them polymorphically in my paysheet generation routine. And structural typing offers an alternative towards this.

What do u think ?

gambistics said...

I would say, it changes not much.

In the most general case structural typing is as statically bound to the specific consumer as interfaces are bound to some implementation.

If you code your consumer(Payroll) you tailor it to fit onto a specific class(e.g. Employee). That more classes have {def salary:Int} defined with the right semantics is just coincidence. (The ruby guys would probably object because they say it would be the obvious thing, but obviousness and intuition are tricky things to come up with concrete decisions)
For other classes(DailyWorker) you need the adapter pattern which is the same situation you would be in if you had used interfaces.

While being somewhat critized I think adaptation is a natural pattern: First you have the Employee classes, then you have a consumer which needs a specific aspect of it. Then you have to think about how each Employee class is salaried ie fits these aspects.
You can then change the Employee and implement the interface - if you can change the source - or you use adaptation as the glue to make it work.

Tom said...

I look at nominal typing (interfaces) as having implicit namespacing that structural typing usually lacks. Folks are looking at adding explicit namespaces to structural typing in both ECMAScript and Ruby to get around the can-be-troublesome lack of namespaces there today. But by the time you get that far, I think the simple "I implement this interface" takes less manual work.

Daniel said...

Neither JavaScript nor Ruby have structural typing since the concept is by definition a figment of a static type system. There's no point in explicitly structurally typed code when using a dynamic type system.

Structural typing *is* less restrictive than nominal typing with interfaces, this is both part of its power and its curse. On the one hand, you cannot restrict the parameters to a certain inheritance hierarchy. But on the other hand, you also cannot use types which would satisfy the requirements (a properly implemented salary:Int method), but which don't implement the all-knowing interface.

In the end, they're two different (but similar) tools which each have their place. I'll admit that structural typing coupled with implicit conversions does indeed make the adapter pattern far less bulky, something I think we can all appreciate.

Tom said...

Duck typing vs. structural typing are equivalent for the concerns of my comment.

David R. MacIver said...

I'm not sure where the impression that structural types require repetition is coming from. They do if you don't have type aliasing... but not having type aliasing *already* causes too much repetition.

In Scala:

type Salaried = { def salary : Int }

Now I can use Salaried exactly like I could the original interface, but it refers to the structural type rather than requiring people to use an interface. Clearly you should be doing this any time you find yourself repeating the same structural type more than once.

david said...

@Daniel

You said, that this is a bad example and that structural typing is a tool as well as nominal typing. Can you give an example of when to use which tool? Are there any rules that I can apply of when to use which tool (except of "it depends")?

TheDet said...

Are there any rules that I can apply of when to use which tool (except of "it depends")?

Well, reading the article and the comments, I would come up with another perspective, I missed so far: Scoping.

Especially considering the term David R. MacIver provided:

type Salaried = { def salary: Int }

combined with the implicit conversion gives me a notion of "usable in local scope".

So the usage of structural typing seems to be comparable to using (named but private or even anonymous) inner classes.

Regarding that, we could ponder some statements which could lead to advices (no "rules"):

1.) Do I have access to the classes I want to cast into a contract?

If no, there's no chance to adorn them with an 'implements interface' expression, and applying the adapter pattern is the only solution.

The Java to Scala migration example is bad in so far that all classes were from ground up under control and had already a named interface implemented in Java.

So it is a good example for structural typing, but a bad example for when to use it.

2.) Does the contract reflect an essential concept in the problem domain?

Well, if you write an application e.g. for the HR or finance department, 'salaried' would perhaps indeed be a domain concept, so it should be visible as explicit type or contract.

3.) Is the contract OTOH only driven by implementation issues, then we could consider structural typing.

Here the question is: Is it published as part of an API?

Then it should be a named interface <=> an explicit contract.

Is it OTOH restricted to a local scope (assume makeSalarySheet being a private method only), then introducing an explicitly declared and namespaced interface type may indeed be oversized.

A structural type plus implicit conversion could be the better solution here.

Anonymous said...

Does Scala support recursvie structural types?

There's a paper that describes the Whiteoak language (http://whiteoak.sourceforge.net) which claims that recursive structural types are not allowed in Scala. Wonder what's the reason for this limitation?

Debasish said...

I think u can have structural recursion in Scala. Luc Duponcheel had a few posts explaining this .. http://lucdup.blogspot.com/2008/04/home_18.html

How would you compare structural typing against consumer-implemented wrapper classes for predefined types that implement consumer-specified interfaces? Is structural typing more elegant than wrapping classes? Or are the two effectively the same?

deamon said...

The Zen of Python says "explicit is better than implicit" and I think it is a good practise to use interfaces explicitly (traits / super classes) instead of using them implicitly like with structural typing.

The only real advantage of structural typing is the possibility to use existing classes with common methods like implementations of a certain interface.

I tried to summarize the arguments of this discussion in the Scala Forum.

Stephan.Schmidt said...

I've read the post now two years later. I think you've cheated with some points.

The evolution problem of Java interfaces still applies. If you ever only need one method on which Payroll depends, then your Java interface also only needs on method. If the interface needs more methods, most probalby because of the Payroll, then evidently you depend on more than one and all the workers need to change also.

The momentum is:

Java:
1. Payroll needs more methods