interface Stream<T> {
T current();
Stream<T> next();
}
interface BiStream<T> extends Stream<T> {
void insert(T item);
}
The reason is that after applying the "next" operation, the resulting streams do not have "insert" operations. In other words, this program does not type-check.
void pushNext(BiStream<String> s) {
s.next().insert("test");
}
In the literature on static typing of OO languages, what we need here are Self types. Some languages, including Eiffel and Scala, have self types.
Why would you care? Well, there are lots of cases where this kind of modification is useful. Its another concept that is difficult to think about in current languages. The OO example above is nice, but type inheritance also applies to algebraic types (See my "Data Abstraction Revisited" essay for a discussion of the differences). Consider this type, written using Haskell notation:
data Diagram
= Rectangle Int Int Int Int
| Circle Int Int Int
| Composite [Diagram]
If we want to extend this to a new data type, for example, to include polygons and fill colors, we want to say something like this:
data ExtraDiagram inherit Diagram
with Polygon [(Int, Int)]
| Fill Color ExtraDiagram
What this means is Diagram extended with new alternatives, such that the recursive references to Diagram are changed to ExtraDiagram. I've been suggesting a while that functional programming could benefit from inheritance. This is just another example.
Posts
11 comments:
Unfortunately, Scala does *not* have usable self types. It has this.type, but that is exclusively the type of a particular instance. It allows the possibility of self-referential type bounds (trait Foo[T <: Foo[T]]) but this bound is not sufficiently tight. It has type members, but likewise the bounds that can be applied on type members are not sufficiently tight. It is possible to simulate self-types with implicits to a point, but there is actually no way in Scala to explicitly specify a type variable that represents the most-specific possible runtime type that is not the singleton type. Much to the dismay of many.
In your example:
void pushNext(Stream s) {
s.next().insert("test");
}
did you mean for the parameter s to be typed as BiStream? Otherwise, it would seem that it is correct that this does not type check -- since s may not be a BiStream.
Also, isn't this really only an issue with immutable, functional style interfaces? You sort of mix styles here, with next() returning a Stream, but insert() being void. If you also had next() return void, and presumed it worked by mutating the state of the stream, then, for a BiStream s, the following would certainly be legal:
s.next();
s.insert("test");
-- Ed
Ed, I fixed the typo. Thanks for pointing it out. Yes, in an imperative setting there are other alternatives. This doesn't change the basic concept I'm trying to illustrate. Rather than streams, you might prefer traversal of a tree. You cannot make an extended tree interface with more behavior at all levels. Since Haskell doesn't have imperative effects, perhaps type inheritance would be more useful.
Hello,
I am missing something about the problem you are talking about? The following code compiles fine in Java:
interface Stream<T, R extends Stream<T,R>> {
T current();
R next();
}
interface BiStream<T> extends Stream<T, BiStream<T>> {
void insert(T item);
}
void pushNext(BiStream<String> s) {
s.next().insert("test");
}
Best regards,
Arnaud
Steve --
I think something got messed up with the template parameters in your post -- for example, the first interface declaration looks like it is for "GenStream>".
In any case, I wanted to mention that I also did something very similar to this in my paper "Genericity Versus Inheritance Reconsidered: Self-Reference Using Generics" which appeared in OOPSLA '94. (I didn't reference your F-bounded polymorphism paper, but I did reference a paper that, I believe, was by you and Palsberg on "A Denotational Semantics of Inheritance and its Correctness" that appeared in OOPSLA '89.) Only I did it using the Ada generics mechanism.
The point is that you can separate self-referential typing from inheritance (in the just the sense of inclusion of namespace members from the superclass) from polymorphism/dynamic binding. In almost all cases, however, programming languages tend to combine one or more of these things -- each in a different way, but often still calling their specific combination "inheritence". Hence the source of a lot of arguments over this term!
-- Ed
Hi Arnaud, thanks for pointing out that encoding. I know it well, because it first appeared in my 1989 paper "F-Bounded Polymorphism for Object-Oriented Programming". To be realistic, you need to explain how Stream can be used as a type, and how BiStream could be extended. This is the full encoding:
[Here is the correct code]
interface GenStream<T, R extends GenStream<T,R>> {
T current();
R next();
}
interface Stream<T> extends GenStream<T, Stream<T>> {}
interface GenBiStream<T, R extends GenBiStream<T, R>> extends GenStream<T, R> {
void insert(T item);
}
interface BiStream<T> extends GenBiStream<T, BiStream<T>> {}
public class Main {
void pushNext(BiStream<String> s) {
s.next().insert("test");
}
}
The problem I've always had with the V<T, X extends V> encoding is that the type bound isn't sufficiently tight. For example, given that the BiStream interface has been defined elsewhere, it's possible to define another such interface where the type is not in fact self-referential:
interface MiStream<T> extends Stream<T, BiStream<T>> {
void insert(T item);
}
This means that any code defined to use subclasses of Stream end up using existential type bounds, which then robs you of a lot of the utility desired from the self-type reference in the first place.
In my opinion, a better approach is simply to use an "open" version of the Visitor pattern, where the visitor exposes a "visit" method for the base type - libraries extending from these types can then implement their own visitors atop this base.
Concerning BitStream, I think it is valid Java to tighten the return type of next() when subclassing as long as it is compatible with the superclass. Sure, this is cumbersome and requires changing the subclass whenever the superclass is changed but it solves your problem, i.e.
class BitStream extends Stream {
BitStream next();
void insert(T item);
}
boggle, the problem with that approach is that it requires that you know the refined type. This means you can't write code to abstract over arbitrary Streams, dramatically limiting the utility of the interface. The purpose of code is to be abstracted over; what we're talking about here is a fundamental limit on the abstractions that one can apply. Sure, if you have a concrete BiStream, and are calling methods on it directly, then your approach works. But who does that?
> I've been suggesting a while that functional programming could benefit inheritance.
Do you mean that "algebraic datatypes, as the central tool of type definition, should support inheritance", or that "when he recognizes the need for it, the functional programming should be able to use open recursion"?
I'm not convinced by your first idea. I think inheritance adds a lot of complexity, and its better not to have implicitly sneaking in our everyday designs without we really noticing.
But on the second point, open recursion can be made available to algebraic datatypes, if used explicitely.
data Diagram_ self
= Rectangle Int Int Int Int
| Circle Int Int
| Composite [self]
data Diagram = Diagram_ Diagram
data ExtraDiagram_ self
= SimpleDiagram (Diagram_ self)
| Fill Color self
data ExtraDiagram = ExtraDiagram_ ExtraDiagram
You will recognize the "tying the knot" style also apparent in functional translation of the object open recursion.
The additional indirection due to the SimpleDiagram constructor is not nice, though, we may want our extensions to be transparent. A solution to this problem is OCaml's "polymorphic variants" which try to be "open sum types". A good introduction to polymorphic variants is the paper Code Reuse Through Polymorphic Variants, by Jacques Garrigue, 2000, which interestingly enough makes use of this "open recursive type" pattern.
I am just suggesting that some syntactic/semantic support for open recursion might be useful. I think that "inheritance" in OO languages really is just syntactic support for "open recursion". I am seeing more and more uses of open recursion in functional languages, hence the suggestion to move from encodings to explicit support.
Post a Comment