ahas a method
foo, and object
balso has a method
foo, then how does the composed object
(a <?> b)behave? In this post, I'd like to explore a separate but related pair of problems: what's the type of
a <?> b, both at run-time and compile-time?
(Before you get too far into this post, a disclaimer: this post describes a method of composition and then explains why it doesn't work. If that strikes you as meandering and pointless — if you prefer to read about ideas that might work, rather than those that definitely won't — then you might want to skip this post.)
As before, let me set this up with an example. As an added bonus, you'll get to see the latest revision of Effes' syntax, which is pretty close to complete (now I really mean it!). Since I haven't laid out how composition works, I'll use
<?>as a placeholder for "some variant of composition." With that said:
type List[A] = data Node(head:A, tail:List[A]) | Nothing put e:A -> List[A] = TODO get -> (Maybe[A], List[A]) = TODO type Box[A] = Maybe[A]: put e:A -> Box[A] = TODO get -> Maybe[A] = TODO myList : List[Int] = TODO myBox : Box[Int] = TODO myContainer = myList <?> myBox
Here we have two simple types: one representing a linked list, and one representing a box that can contain zero or one items. Their details aren't important. We also have three references: one of type
List[A], one of
Box[A], and one representing the composition of the first two.
As I discussed in the last post, we have some options with a call like
myContainer.put 1. We can take the Schrodinger approach, in which we invoke
puton both components of
myContainerand then compose those two results; or we can pick one as the "winning" binding and only invoke it.
Let's say we pick the single-bound, "winner" approach; that's the option I was leaning towards in the last post. To make it concrete, let's say that the left-hand side always wins out. That seems reasonable, but what about this situation:
myContainer2 = myContainer.put 123 myVal : Maybe[Int] myVal = case myContainer2 of Box[Int] -> myContainer.get _ -> Nothing
In this snippet, we check to see if
Box[Int]. It is, so the first pattern will match. This casts
Box[Int]and, within that new context, invokes
get. Note that
gethere has to be bound to the
List[A]version has a different return type (it returns a pair containing the list's possible head and its tail).
The problem is that
myContainer.putwas bound to the
List[A]method, meaning that the
123inserted into it: the value of
123! This is fully consistent, but it's confusing and violates the principle of least surprise. There has to be a better way!
One possibility is to limit composition such that
myContainer2does not have a runtime type of
Box[Int]: the second (catch-all) pattern matches, and the value of
Of course, we always want the runtime type to be a subtype of the compile-time type, so this new approach means that the composed object's compile-time type can't include
Box[Int]. We can't generalize that to all compositions, or else the whole idea of composition falls apart and becomes shorthand for the not-very-useful function
a <?> b = a.
We can come up with a more precise limit on composition, one that doesn't just throw away the RHS altogether. One approach to compose objects in multiple phases. Here's one such algorithm, in rough terms:
- Decompose the RHS object to its constituent objects.
- Fold each one of those into the LHS, one at a time. As you fold each object, check to see whether it has any methods that conflict with methods on the composed object; if so, ignore that object (don't fold it in).
- Check whether the resulting object has any abstract methods (that weren't given a concrete definition in the composed object). If so, remove the objects that introduced those methods.
type List[A] = ... (put/get, as above) size -> Int type Box[A] = ... (put/get, as above) type Container: isEmpty -> Bool -- abstract method type Container Box[A]: @override isEmpty -> Bool = TODO intsList : List[Int] = list(1, 2, 3) intsBox : Box[Int] = box(4) intsContainer1 = intsBox <?> Container
Box[A]types are as before, except that
List[A]now also has a
Let's look at that last line. The LHS is
get, while the RHS is
Containerwith just one method,
isEmpty. There's no overlap in methods, so the composition is straightforward and results in
Box[Int] <?> Containerfor both the compile-time and runtime type.
Okay, so that case works fine. But what about this?
intsContainer2 : Container = intsContainer1 composed2 = intsContainer2 <?> intsList composedSize = composed2.size
At compile time, that last line looks like
Container <?> List[Int], which has no conflicts and thus doesn't remove any types. But the
isEmptymethod isn't implemented, so it's removed: the resulting type is
List[Int]. We call its
sizemethod, which is a pretty reasonable operation to call on a list.
At runtime, the composition looks like
(Box[Int] <?> Container) <?> List[Int], and there is a conflict:
List[Int]'s methods collide with
Box[Int], and we therefore don't fold
List[Int]into the composition. That means that the resulting type is just
Box[Int] <?> Container— the inverse of the compile-time type! And in particular, there's no
sizemethod on that object. Boom.
I've tried a few variants on this sort of decompose-and-recompose theme: decomposing both sides, different handling of abstract methods, etc. Inevitably, the mismatch between runtime and compile-time types always blows up in my face. I don't think there's a way around it.
Unfortunately, I think this leads me to the conclusion that if I'm going to do composition, I have to do composition all the way: Schrodinger-style. This means I'll need to figure out various issues about collapsing the wave form: how does pattern-matching work, and what happens when an object is composed with an object of the same type? For instance, how does
"foo" <?> "bar"work?