Friday, May 22, 2009

Structural versus Nominal typing

M has a structural type system. Most programming languages today, and in particular most OO languages, have a strict nominal typing system.

Given that types are used in 2 ways (validation/constraints and value construction), how do programmers generally feel about one versus the other?

Do programmers need both? In which case is one better than the other? 

Do programmers really understand both?

I'd love your thoughts.

9 comments:

Unknown said...

I prefer the flexibility you get with a structural type system. If I've got a duck, why should I care if it inherits from DuckBase or implements IDuck (unless I'd like to inherit some default functionality)? All I should have to care about is whether it has a Beak and can Quack().

Lars Corneliussen said...

I think for m structural subtyping is great. Don't think it's hard to understand. But to understand all impacts is sometimes hard.

What were your main arguments when deciding to do duck typing?

Anonymous said...

@Ehren That isn't quite how structural typing works. Duck typing is really the absence of a type system - everything is totally late-bound. If the object has all the necessary members, awesome. Otherwise, epic failure ensues, especially when it comes to functions with side effects.

Structural typing is quite different. Objects have specific types, and so do l-values (variables, fields, and parameters). The only difference from an ordinary static type system is that an object's type is solely defined by what members that type specifies. This means that any value can be assigned to any l-value as long as the value's type is a superset of the l-value's type. This means that a duplicate of any type is considered to be exactly equivalent, unlike, say, C#.

This system is pretty nifty, but it falls apart when it comes to generating interfaces for other languages to M-based repositories. The concept of structural typing is totally incompatible with .NET, and this pretty much destroys any opportunity for end-to-end modeling (from database to application), throwing away one of the key benefits of modeling.

Pinky said...

@anonymous - that's right.
I like to think of it this way.

Nominal typing means you can only hang out with your family tree.

[That could be good unless you don't like your family :)]

Structural typing allows you the freedom to hang out with a more diverse crowd!

Pinky said...

@anonymous - tell me more what you mean by "falls apart".

Why?

What's the issue(s)?

Pinky said...

@lars - why is it harder to understand?

Håvard Jørgensen said...

I see you are interested in the opinions of programmers, not modellers ;)

For model-driven applications where models are executed directly without code generation and compilation, where models will evolve during execution, conventional type checking should be replaced by user-defined business rules to enforce constraints. You should e.g. be allowed to state
Donald : Duck;
Donald : CartoonCharacter;
unless there is a business rule that states that the two types are disjoint.

What modellers need is incremental value construction, sometimes called feature composition, where new types may be added to an instance dynamically, resulting in the addition of missing type features to the instance.

Alongside nominal typing, the single instantiation class constraint of OO is a major barrier to this, in M as well. When all features of an object must be defined at the time of its creation, there is no evolution.

You should in some cases also allow users to remove a type from an instance, e.g. to reflect that "Pluto is no longer a planet".

Sometimes, you should even tolerate inconsistencies, in order to reflect the uncertainty of the modelled information, e.g. if Pluto is defined as a Dog in one module and a Planet in another, we cannot immediately assume which interpretation applies in a third context. Of course, in a robust model-driven environment, the errors are not epic disasters, you can always push the problem up to the user/modeller with rather simple error messages.

Encapsulation is the final language constraint that should be relaxed in model-driven execution. In some cases it is perfectly reasonable to ask any object to
Quack like_a Duck;
Walk like_a Duck;
even though it is not a duck, as long as the behaviour can be delegated to a Duck implementation available in the execution context. Side effects could lead to addition of features to the object, which is probably what the modeller/user wanted.

I guess the key question is which use cases you want M to handle directly, in the spectrum from .Net code generation to completely user controlled model-driven applications. Though M takes some steps in the right direction with dynamic typing, there are still a number of constraints that I will have to code around if I decide to use Oslo as a platform for writing my own model interpreters/activators/executors. M currently takes a middle-of-the-road approach, probably not satisfying any of the ends of the spectrum. An alternative would be to define an agnostic language that lets the implementers of runtime model interpreters decide what kind of typing model and other language constraints they would like to apply.

Pinky said...

@Havard,
Great comments!

I'll blog a bit more about M's type system (past, present and future). The goal is to enable many of the capabilities you talk about.

Lars Corneliussen said...

Hi Jeff, don't think it's harder to understand in general. Just that we are more used to nominal typesystems, so it is hard to see all the implications of duck typing.

I agree with Havard, that for modelling purposes structural subtyping is more adequate hence more flexible.

I also agree, that the constraints you can describe in M are to on/off at the moment. I would suggest adding warnings, and adding userfriendly messages for constraint violations.

Checks in Eclipse Modelling Framework (former part of openArchitectureWare) is a good example.

In M it could look like this:
type Person
{
FirstName:Text;
LastName:Text;
Age:Integer;
} where {
warn "Not a good idea. Don't like that name!": value.FirstName.Length > value.LastName.Length;

error "Don't do this! People have names!": value.FirstName.Length == 0;
}