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.

Well, that was more work than I expected...

It's been a while since I posted. Usually when I "go dark" for an extended period of time, it's either because (a) I'm feeling burned out from working on Tart and need an extended break, or (b) it's because I'm working on a massive changeset and I don't want to talk about it too much until it's submitted. This time it's (b).

I've spent the last month or so updating Tart to work with the latest LLVM trunk. The LLVM APIs have changed significantly in preparation for the 3.0 release. The biggest change is that LLVM types now have first-class names, and types with different names are now distinct types even if they are structurally identical. In addition, the Opaque type is gone - instead you use a named struct with no body. (You can fill in the body later, or not.)

The APIs have also changed - Types are no longer "const" (that is, the LLVM APIs will no longer produce or accept values of type 'const Type *'). This required a huge number of edits to my code.

Also during this period I ran into several LLVM bugs in the new type system, and worked with the LLVM folks to diagnose and fix them. This includes a trip into DWARF hell, which is never fun.

In any case, I've committed the changes so Tart is working again. Overall, I like the changes - for one thing, the generated IR is easier to read now that types have proper names. And with the ability to declare a type name with no body, I'll eventually be able to reduce the amount of work the compiler is doing, because I won't have to do a deep analysis on fields that are never dereferenced.