Subtyping Functions Without Poking Your Eyes Out

Friday, June 1, 2012 | 2:12 PM

Pop quiz: suppose you see two Closure Compiler type annotations.

A) {function(Object)}
B) {function(Array)}

Which one is the subtype?

Telling you that the right answer is (A) feels a lot like driving on the wrong side of the road. Try reading it out loud.

Right Answer: "A function taking an Object IS A function taking an Array"
Wrong Answer: "A function taking an Array IS A function taking an Object"

Saying the right answer feels so wrong! Saying the wrong answer feels so right! We often have to do multiple rounds of whiteboarding the problem to try to explain it to other JS engineers.

This is not a unique problem to JavaScript. Most object oriented languages have the same issue. But JavaScript engineers are used to living without types. With Closure, suddenly you have types. And you have lots of complex function types that real OO languages don't have, and that you're probably unfamiliar with if you haven't used a functional language.

The problem, I think, goes back to a lot of "Intro to Objects and Classes" books that teach the "is-a" relationship. An apple IS A fruit. A blog IS A website. A werewolf IS A man but also IS A wolf.

The "is-a" wording is an oversimplification that breaks down if you're not careful. This wikipedia page gives a good counterexample, obtusely explained. Suppose you define "A Doctor" as a person that can treat all patients, and a Pediatrician as a person that can only treat children. If we need a Doctor that can treat all patients, then a Pediatrician is not an acceptable substitude. So, counterintuitively, a Pediatrician is not a subclass a Doctor.

Oddly, a Pediatrician is a superclass of this "Doctor." If you need a pediatrician, a doctor that can treat all patients is an acceptable substitute.

What you really want is to define a Doctor as "a person that can treat at least one patient." You might call this the Empty Doctor or (for the calculus nerds) the Epsilon Doctor. This doctor can treat some patient, somewhere. But if you go to see the Epsilon Doctor, it's likely that they won't know how to treat you. A pediatrician is a subclass of the Epsilon Doctor, because a pediatrician can treat some patients.

Conversely, when you have a {function(Object)}, this does not mean "a function that can take some object". It means "a function that knows how to handle all objects." A {function(Object)} is substitutable any place you need a {function(Array)}.


T.J. Crowder said...

"A {function(Object)} is substitutable any place you need a {function(Array)}."

Isn't that at odds with your claim that the first is the subtype? Either that, or you're using "subtype" in a rather unusual way.

In class-based languages, you can substitute a supertype declaration wherever you have a subtype declaration, not the other way around. If you have a Base and a Derived, then a foo(Derived) declaration can be replaced with a foo(Base) declaration, but not the other way around. Of course, foo may not be able to handle all of the subtypes of Base (which is probably why the original only accepted Derived!), but that's just as true of your {function(Object)} substitution for {function(Array)}.
T.J. Crowder
Independent Software Engineer
www / crowder software / com

Unknown said...

Stroustroup sort of recommends the "base" and "derived" terminology in relation to inheritance (instead of "class" and "subclass") for the reason you describe: "the data in a derived class is a superset of an object in its base class." (The C++ Programming Language, 3rd ed.)

Anonymous said...

+T.J. Crowder, "An X is substitutable any place you need a Y" is kindof the very definition of what is meant when we say "X is a subtype of Y". Put another way, "Every X is a (possibly more specialized) Y".

More concrete examples:

{Dog} is a subtype of {Animal}. A {Dog} is substitutable any place you need an {Animal}.

{Toyota} is a subtype of {Japanese Automobile}. A {Toyota} is substitutable any place you need a {Japanese Automobile}.

And, of course, the example about which Nick blogged: {function(Object)} is a subtype of {function(Array)}. A {function(Object)} is substitutable any place you need a {function(Array)}.