Article on adding type constructors to Java

So I recently saw this article on Lambda the Ultimate about adding type constructors to the Java language. I have to admit, it took me several re-readings of the article before I understood the gist of what they were saying. And there are some parts of the paper, such as the logical proof, that I have no hope of understanding, as I just don't have the background.

Nevertheless, I understand it well enough I think. What they are talking about is indeed highly abstract and powerful. I'll try and summarize as best as I can: A type constructor can be thought of as a function that operates on types. An example would be "X => List[X]" - a function which, given a type X, returns the type of a list of X.

Where this gets powerful is when you start passing type constructors as template arguments - that is, instead of passing in a type as a template argument, you pass in a function that operates on types. Within the body of the template are calls to this function, which appear in the same places that template arguments would appear. So for example I could declare a template that takes a parameter R which is a type constructor, and in the body of the template I might declare a method whose return type is "R(String)". What "R(String)" evaluates to depends on what the value of "R" is when you instantiate the template. Some examples of R could be a constant [R(X) => int], the identity function [R(X) => X] or a type derived from the argument [R(X) => List[X]].

The example that they give in the paper is a visitor pattern - that is, you have a tree representing expression nodes, and you have two different visitors - one which evaluates the expression, and one which prints the expression as a string. In the former case, each visitor method returns a type appropriate to the evaluation - int, float, bool, etc. In the second case, the visitor methods all return type String. Because the visitor methods are all defined in terms of type constructors, you can use the same generic tree-walking code to handle both cases.

Well, that's all very neat, but...I wonder. It doesn't actually seem all that useful to me, or at least it doesn't seem all that useful to the average Joe Programmer (JP). You see, these type constructors don't work on normal classes of the kind JP would write, but only on templates that have these constructor calls built into them. Writing a class which takes advantage of type constructors presupposes that you have a certain kind of generality in mind. That is, given a particular data structure or algorithm, there are many dimensions along which we can generalize - you can think of a particular bit of code as being defined by some set of design criteria, and in generalizing the code we're taking some of those design criteria that are constants and replacing them with variables. We can't replace the entire thing with variables, because then we have no specification - our design becomes "do anything with anything".

The most common kind of generalization we see in practice is to interpolate between two specific use cases - that is, we enlarge the design just enough to encompass the two cases. If additional use cases come along, they may or may not fall within the envelope of what the design can support. (That's why I generally like to see at least three use cases before generalizing a particular design.)

This is exactly what they have done in the paper - their two use cases are "visitor that supports evaluation" and "visitor that supports converting into a string representation".

The thing is, though, is that this problem isn't a "real" problem in the sense that it's not a very hard problem to solve - there are many ways of coding those two use cases, and while some of the possible solutions are a little more verbose, they don't require super-advanced type theory either. The authors are deliberately avoiding any kind of dynamic typing because they trying to use the type system to prove that their code is correct, but I'm not convinced that their code is easier to *reason about* than an equivalent dynamic-typed solution would be. And to my mind, making it easier to think about what the code does is really the key to better programmer productivity.

I'm also not convinced that the kind of generality that they offer is the kind that most programmers would need. That is, a programmer who has a need for a "generic visitor" would be very likely, in my estimation, to need a visitor that is generalized in a way that the authors haven't thought of, and which would not be supported by their system.

To give an example, there's another kind of generality that is used daily by many Java and Python programmers, and which is much more useful. I'm going to call this "algorithmically-produced implementations". That is, given some ordinary abstract interface X that defines a set of methods, generate all of the method bodies using some rule. An example of this is mock objects for unit testing - you "mock out" the interface by generating methods that capture the parameter values and record them in a log.

In other words, rather than having functions that operate on *types*, we have essentially functions that operate on *methods* - given a type signature, return a method body. One could imagine a syntax for this, where '_' is taken to mean "anytime someone attempts to call a method that is undefined, call this method instead".

   def _[%RetType, %ArgTypes...](args:ArgTypes) -> RetType {

     record(args);

     return defaultValue[RetType]();

   }

Of course, the language has to support "perfect forwarding" in order for this to work, but let's assume that it does indeed do so. (Note that the ... in the template argument list indicates that ArgTypes is a variadic template parameter - this allows the function to accept a variable number of arguments.)

Note that from an implementation standpoint, there are two ways that this can work. Approach #1 is to have the compiler replicate the body of "_" for each missing method. Approach #2 is to only have one instance of "_", but for each missing method the compiler generates a trampoline function that packs up the arguments into an array and calls "_". Which method will be used in Tart is something that I still have not decided.

In any case, the beauty of mock objects is that they work with almost any interface - you typically don't have to have mocking in mind when you design your interface, although there are occasionally times when you need to do so. And it's something that the average programmer can immediately grasp.

I/O Library is checked in

Well, better late than never...

There are now low-level classes for reading/writing to files, standard in/out, and to memory. There are also reader classes for reading and writing text:

tart.io.Console

tart.io.FileStream

tart.io.MemoryStream

tart.io.StreamTextReader

tart.io.StreamTextWriter

...plus a host of unit tests to go along with them. I don't yet have "convenience methods" for opening text files, so for now the easiest way to read from a file is:

let reader = StreamTextReader(FileStream(filename))

for line in reader {

  // do something with 'line'.

}

reader.close();

Mutability

I've been reading up on the D language's idea of immutability. It makes some interesting choices, but I'm not certain they are the right choices for me.

D has two keywords, 'const' and 'immutable'. 'const' says that you can't modify the value, but someone else might. 'immutable' is a guarantee that the item will never be modified, and this guarantee may be backed up by storing the item in a protected memory page.

Moreover, both 'const' and 'immutable' are transitive - that is, any data structure that is reachable by a const type is also const. So if you have a pointer inside a const struct, the thing it points to is automatically const as well.

Another design point is that you can't typecast an immutable value to either const or mutable, since that would violate the guarantee of immutability. (Actually, I think there's a way you can, but attempting the mutate the value afterward may throw an exception if the value is in protected memory.)

I like the distinction between const and immutable, however I tend to favor the formulation used in the JodaTime libraries: You have a base type which is 'readable', with two subtypes, mutable and immutable. So for example, you have "ReadableDate" which only defines accessors for reading the value, but does not guarantee that those values will not change; Then there is ImmutableDate, which adds no new methods but does guarantee immutability, and then MutableDate, which adds the accessors for mutating the value.

The only problem with JodaTime is the extra work involved in writing 3 classes to represent the same concept. This is where C/C++/D gets it right, I think: You write the class once, with methods to both read and mutate the fields, and then you use a modifier keyword as a type constructor, which transforms the fully functional type into a more restricted version of that type.

If we combine these two ideas together, we get something that works like this: 'immutable(Foo)' takes the type 'Foo' and subtracts from its definition all of the mutation methods. 'readable(Foo)' does the same, except that you can cast either a Foo or an immutable(Foo) into a readable(Foo), but not vice versa.

How is the compiler to know which methods are mutation methods? Well, we have to tell it - this is one case where the compiler can't infer things automatically (As a general rule, Tart does not allow the compiler to infer an interface from its implementation. I realize that there are some languages which do exactly this, but I think that interfaces should be explicit.) Fortunately, we don't need to distinguish between readable and immutable in this case - all the compiler cares about is whether the method can mutate the state of the object or not. The main challenge here is to come up with a syntax that's easy to type, since approximately 25-50% of all instance methods will want to have this property.

You also need a way for some fields to be mutable even on a readonly object. A typical example of this is reference counting: You want the object to appear to be immutable to the outside world, but internally you are changing the reference count. In C++ we accomplish this by declaring the data member as explicitly mutable, or by declaring the method itself as mutable. The latter can be accomplished better, I think, by allowing the method to cast 'self': So we'd say something like "let mself = mutable(self)", and then use mself to access the various fields.

Finally, there's the question of transitivity. Tart already has a mechanism for defining non-transitive immutable member fields via the 'let' keyword instead. At the same time, I can't help feeling that the D rule is too aggressively transitive. I think that having an immutable array of pointers to mutable objects would be a fairly common use case.

The Copyable protocol

One of Tart's fundamental design decisions is that there should be no collection classes that have special, "privileged" status. In most programming languages, there are a few types that are built in to the compiler, and which have special syntactic sugar - so for example, in Java, arrays are a built-in type, and only arrays can use the bracket notation (array[n]) to access their elements. Whereas in Tart, the Array type is written in Tart, and moreover, any collection class can define an element access operator.

Actually, this design principle represents an unrealizable ideal more than it does an actuality. In truth, arrays do have special status in two ways: array literals, and functions taking a variable number of arguments. Both of these cases cause the compiler to generate code that constructs a new array instance. But once constructed, an array is no more "special" than any other collection.

There's a downside to this design principle, however. It's fairly common in programming to want to convert from one collection type to another - for example "flattening" a deque into an array, or converting a map into a list of tuples. In cases like these, it's highly inefficient to transfer the items one at a time from the source collection to the target collection. It would be better if there was some way to transfer elements en masse. Unfortunately, doing so requires knowing a lot about the internal representation of the collections involved.

For example, many collection classes use arrays internally - ArrayList and Deque being two prime examples. If we could arrange a bulk transfer of elements from one array to another, much of the overhead of copying could be eliminated. However, those arrays are private - allowing code outside of the class access to those arrays would destroy the data-hiding abstraction of the container.

This is where it's useful to have the compiler have special knowledge of some collections - because the compiler can recognize cases where a bulk transfer would be appropriate and generate code for it. But what if we wanted to extend this ability to user-created collection types? What we'd have to do is abstract the bulk transfer operation itself, so that the user-created classes could participate in bulk-transfer operations.

The Copyable interface represents one approach to solving this problem. Users never use Copyable objects directly - instead, when you pass one collection to another - such as ArrayList.appendAll(collection) - the destination collection checks to see if the source collection supports the Copyable interface. If it does, then it initiates one or more bulk transfers from the source collection. If it does not, then it will transfer the elements the conventional way, one at a time.

The Copyable interface makes certain assumptions about the destination container: It assumes that for a collection of size N, elements are numbered 0 .. N-1, and that sub-ranges of this numbering can be mapped onto ranges of contiguous addresses. So for example, elements 0-255 might be stored in one array, 256-511 stored in a second array, and so forth. Each bulk transfer operation specifies one of these contiguous sub-ranges as a destination buffer. It's up to the source collection to decide how to map it's own internal representation onto that buffer, and to copy its elements into that buffer. The source collection may have it's own internal divisions, which may be different from the destination's - in which case, the source collection may have to do more than one array copy to fill the destination buffer.

The actual copying of data is typically done via Array.copyElements or Memory.copy, both which use memcpy to do the actual transfer. (Tart does not allow redefining the meaning of assignment, so all objects are treated as POD. The reason is that the garbage collector can move objects around, so any assumptions made by an overloaded assignment operator would be violated anyway. But with garbage collection, there's far less need to overload assignment anyway.)

The copy operation is also synchronous - both source and destination are allowed to move things around in-between copy operations. There is no promise that the destination buffer will continue to exist after the copy finishes.

BTW, the idea of Copyable was inspired and greatly influenced by the Python buffer protocol, although Copyable is a much smaller and less featureful concept.

I/O Library

I've taken Guido's advice about using file descriptors rather than FILE * handles, and as a result the i/o classes are coming along nicely. MemoryStream and StreamTextWriter are done, with unit tests. FileStream and StreamTextReader are written but still need tests. The character codecs got an overhaul as well.

One of the nice things about all of this is that it has given me a chance to write lots of Tart code, which is a welcome break from writing the compiler in C++. You can definitely see the power of Tart when you have unit tests that look like this:

stream.write([1, 2, 3, 4, 5]);

assertContentsInOrder(stream.data, 1, 2, 3, 4, 5);

In this case, 'stream' is a MemoryStream, and the 'write' method takes in an array of bytes, which in this case is an array literal. "stream.data" returns a reference to the underlying collection (an ArrayList). "assertContentsInOrder()" takes a collection and a variable number of elements, and asserts that the contents of the collection equals that list (it does this by calling iterators.equal()).

This style of coding feels very Pythonic to me, yet it's all statically typed.

One minor disadvantage of using unix file descriptors is that there's no equivalent of feof(). The only way to know that you're at the end of file is to attempt to read, and then get 0 back as the result. This doesn't play so well with higher-level APIs, which are typically designed such that you can test for end of file before doing an actual read. fread() and its ilk provide this capability by reading ahead.

This means that my lower-level i/o classes have to expose this same behavior - I can't define an "eof" predicate for class IOStream. Such a method would be expensive without buffering or read-ahead of some type. And since we want the IOStream interface to be platform-agnostic, that means that we can't define an eof method even on platforms which do support it for low-level streams. We have to go with the lowest-common-denominator (both of platforms and stream types), which means that all IOStreams have to have unix-style end-of-file behavior.

Obviously the higher-level classes such as TextReader / TextWriter are buffered, so we can define an eof() method on all of these. It's only the lower-level unbuffered classes that don't support it.

Brainstorm: ScopedObject and Pinned

ScopedObject and Pinned are two features of Tart which are on my long-term TODO list.

ScopedObject is an interface that is used in conjunction with the 'with' statement. It has two methods: enterScope() and exitScope(). You'd use it like this:

with mutex.locked() {

  // Mutex is locked while in this block, will be unlocked on exit.

}

with file = FileReader.open("foo.txt") {

  // File will be automatically closed on exit.

}

tart.gc.Pinned is a helper class for creating 'pinned' objects - that is, objects that are fixed at a given address and cannot be moved around by the garbage collector. Pinned objects aren't something that normal users of Tart would ever deal with - they are mainly useful for people who are implementing i/o libraries.

Here's a typical example of how pinning would be used:

def writeData(data:ubyte[]) -> int {

  with pinnedData = GC.pin(buffer) {

    with GC.unlocked() {

      return lowLevelStream.writeData(pinnedData.get());

    }

  }

}

Here's what this is doing: GC.pin() takes an object reference and returns a 'pinned' version of that object. Depending on what memory region the object lives in, the return value may be the original object with the 'pinned' bit set in the object header, or it may be a shallow clone of the object. Cloning generally will occur if the original object lives in a compacting collection space - the clone will be put into a different space where object addresses are stable.

Note that the writeData() function will throw an exception if the buffer isn't pinned.

At the end of the outer with statement, the pinned object is disposed. In some cases, the data in the pinned object may get copied back to the original buffer. (Probably 'pin' will take some flags indicating whether the clone will be read/write or just read only.)

The inner 'with' statement handles interactions between the garbage collector and blocking i/o. The 'unlocked' method tells the garbage collector that it's OK for collections to take place while we are waiting for the i/o to finish. At the end of the block, the garbage collector is locked again (meaning that collections can only take place when we tell it that it is safe to do so.) Within the 'unlocked' state, objects may move around in memory - which is why we had to make sure that the input buffer was pinned.

Fun with debug macros

I recently introduced some new macros for doing assertions and conditional tracing, which was inspired by a conversation on llvm-dev. Here's how the new macro is used:

DASSERT(super != NULL) << "Expecting a non-null super class for type: " << type;

In other words, the assertion macro acts like a stream operator, allowing you to print a message that includes dynamic fields. There's also a DMSG(condition) macro which prints a message only if 'condition' is true.

DMSG(TRACE_CODEGEN) << "Adding a static root entry for: " << var;

One feature that DASSERT and DMSG have is that, like all good debugging macros, they impose no cost when disabled. This means that (a) no side effects occur if the condition is false, and (b) if the condition is both false and is a compile-time constant, the compiler should remove the message code entirely.

How does this work? Well, the DMSG and DASSERT macros construct a stream object. In the case of DMSG it's a generic output stream. In the case of DASSERT, it's a subclass of stream which calls abort() in it's destructor. Because the stream is a temporary object, it gets destructed at the end of the statement, after all of the messages have been printed.

Here's what DASSERT actually looks like:

#define DASSERT(expression) \

(expression) ? (void)0 : Diagnostics::VoidResult() & \

Diagnostics::AssertionFailureStream(#expression, __FILE__, __LINE__)

Let's start with the last part. AssertionFailureStream is the stream object - it's the right-most token in the macro, so any stream operators (<<) that come after the macro will be applied to the stream.

In the middle there's a C ternary operator '?:' which tests if 'expression' is true. Because the precedence of the ternary operator is lower than <<, the stream operators will get applied to the stream object, rather than the expression as a whole. Also, C++ guarantees that only one of the two choices of a ternary operator will be evaluated, so this means that the stream object will not be constructed, nor will the stream operators be executed, if 'expression' is true.

One catch is that both sides of a ternary expression have to be the same type - which in this case we want to be 'void'. Doing this requires another trick: pick some binary operator which has a lower precedence than << but higher than '?'. In this case, I've chosen the bitwise 'and' operator, '&'. Then create an overload for it which returns a void result:

/** Transforms a value of stream type into a void result. */

friend void operator&(const VoidResult &, const FormatStream &) {}

'VoidResult is just an empty struct - it's just there to insure that our operator gets called. So 'VoidResult() & AssertionFailureStream(...)' now has type void.

One final thing needed to make this all work is to define appropriate stream operators for various compiler classes such as Variable and Type, which print out the object in human-readable form.