The path to function resolution is a winding one

Eek, it's been a while since I've written here. I've been putting off a few posts on subtypes and function resolution, because my ideas aren't fully fleshed out. But here's an update, which is mostly some insight into how my thought process is changing.

I originally had a fairly complicated subtyping scheme in mind, because I wanted to support various ways of composing types. A lot of that had to do with the fact that I wanted to be able to write code like:

data Foo(foo : String)
data Bar(bar : String)
data Buzz -- no args

a = Foo("something")
b : Foo = a Bar("another")
c : Foo Buzz = b

The first two assignments are simple, but the third is... weird.

• a is a Foo
• a Bar("another") is a Foo Bar, which is a subtype of Foo and can thus be assigned to a Foo-typed reference — in this case, b
• c : Foo Buz would be neat if it worked, but it'd require jumping through hoops with the subtyping

The reason I want that last line to work is that Buzz may have some neat behavior, including an override of default behavior. Here's a more concrete example:

getNames() : Stack[String] = ...
useNames(names : QuickSize Stack[String]) = ...
useNames( getNames() )

I'm using the definitions of Stack[A] and QuickSize from a while back. Basically, Stack[A] is Sizeable but has O(N) performance for getting a stack's size, while QuickSize can override a Sizeable object's size method to provide O(1) performance.

The problem is that useNames wants that O(1) performance, while getNames doesn't provide it. My original idea was to allow this with some weird, complicated subtyping rules; that's a bad idea, and I'm abandoning it. My next thought was to allow type declarations to implicitly create composite objects, such that this:

c : Foo Bar = Foo(789)

...would be sugar for this:

fTmp : Foo = Foo(789)
bTmp : Bar = Bar()
c : Foo Bar = fTmp bTmp

I think I'm going to abandon this as well, because it's still complicated and doesn't buy much. In fact, given that I want type inference to eliminate most explicit typing, putting so much semantic importance on declared types is actually a pretty counterproductive plan.

So here's my new idea: do nothing!

Here's how it works. Let's say you have getNames() and useNames as above. In that case, the call site just has to add the QuickSize itself:

useNames( QuickSize getNames() )

That's not so hard. It works because QuickSize (getNames()) creates a new object, the composition of the getNames() : Stack[String] and QuickSize. ("Creates" in the conceptual sense; it may be optimized to just a runtime check).

Better yet, the useNames method can get rid of the QuickSize requirement altogether, since it's just an optimization that polymorphism can handle within the method:

useNames(names : Stack[String]) =
  names = QuickSize names
  ...

So, that's where I am right now. This simplifies the subtyping system a lot, though I still have to figure out what to do with generics and covariance (Stack[Int] vs Stack[Num]). And those simplifications in turn simplify function resolution, which is where all this is really headed in the end.