Another idea on mutability

I was thinking about the way that 'const' gets used in C++ programs. In particular, it's extremely tedious work to take a body of source code that doesn't use 'const' and refactor it to be const-correct. Typically what happens is you add 'const' modifiers to a small section of the code, and then try to compile, at which point you get a jillion errors. You then go and fix up all of those errors to be const-correct, try to compile, and now you have a jillion-squared errors.

(Of course, this tends to be more true for some uses of const than others - it depends on how widely referred-to is the thing that you are making const.)

In other words, because const is so viral in C++, you end up having to convert your entire program in one go - there's no easy way to break up the change into manageable chunks.

So I wonder if it makes sense to give programmers a "soft landing" option, in which const-correct and const-incorrect code can interoperate without creating a ton of warnings. There are of course some serious downsides to this idea. The fact that the C++ compiler tells you exactly what values you need to add the 'const' modifier to is pretty useful. And allowing programmers to write non-const-correct code means a loss in safety.

BTW, all of this started because I was trying to figure out how to write the following function:

  def tracePointer[%T <: Object](v:T);

The <: operator means "isSubtype" - basically it's saying that the T parameter must be type Object, or a subtype of Object - it can't be an int for example.

The problem is that this fails if you attempt to bind T to "readonly(Object)". The reason is because "Object" means the same as "mutable(Object)", which is a specialization of "readonly(Object)". From the compiler's point of view, mutable(Object) <: readonly(Object), not the other way around.

Unfortunately, while this makes sense from a theoretical point of view, it fails the practicality test. When you say "A <: B", with no mutability qualifiers on either A or B, what you generally mean is "type A is a subtype of type B, and I don't care what the mutability modifiers are". If you'd explicitly given a mutability modifier, like "A <: mutable(B)", that would be an entirely different story.

Since one of the design rules of Tart is that practicality should dominate over theoretical purity, I put in a temporary hack that basically says "when using the subtype operator, if neither side of the expression has an explicit type qualifier, then don't consider the type qualifiers of the values they are bound to when doing the comparison." However, this hack is rather ugly, and is yet one more thing to remember when programming in Tart.

A different, and much more radical idea is this: That a type name with no mutability qualifiers ("Object") doesn't mean "mutable" like it does now. Instead, it means "mutability unspecified", in other words there are no guarantees about mutability or immutability at all. So the hierarchy would look like this:

• (no qualifier)
• readonly
• mutable
• immutable

Basically it means that you can implicitly convert from (no qualifier) types to readonly, mutable, or immutable types and the compiler won't complain. So upcasting is implicit and silent - downcasting (converting from (no qualifier) to a qualified type) requires an explicit cast.

What this means is that a lazy programmer can write code without thinking about mutability at all - they just don't use the mutability qualifiers in their code. If at some future point they decide that explicit mutability is a good idea, they can go and start adding the keywords where they are needed. Unfortunately, the compiler won't be as helpful as it would be in the case of C++ - if you forget to add the keyword in some places, the compiler won't always detect that, since it's legal to convert from readonly(Object) to Object without an explicit cast.

It also means that the expression "T <: Object" now says exactly what we intuitively think it ought to mean.

This is an interesting idea, but I think it goes a little too far, in that it does more than just allow the programmer not to be distracted by mutability concerns - it *actively encourages* programmers to write code that doesn't address mutability issues by making such code much cleaner-looking and easy to type. You see, I think that the easiest option should also be the correct one - that is, you can break the rules if you want, but if you follow the rules you'll not only get the satisfaction of having correct code, but you'll also get clean-looking, succinct code as well.

Unfortunately, with mutability this is hard to do - making the compiler smart enough to guess the correct default without the programmer having to explicitly type it means making the rules of the language much more complicated and hard to remember.

Tart status update

I decided to back off on the "make function parameters default to read-only" change because it was getting too big and too complex. I still plan to go ahead with it, but I need to fix some other things first. The whole mutability thing has introduced a lot of small problems that need to be solved one by one, and I've just been working through them.

One question that has come up is: If function parameters are read-only by default, should function return values also be? I even thought about making all object references readonly by default, but I really don't want to drink quite so deeply from the functional programming kool-aid.

Another question that keeps rolling around in my brain is this: Was it the right choice to make Tart an AOT (Ahead of Time) language instead of a JIT? I originally made tart an AOT because I was looking for a replacement for C++, not another Java. And AOTs do have a couple of obvious advantages: quicker startup time, for example.

VM-based languages, however, have plenty of advantages of their own. For example, in the current incarnation of Tart, up to 4 different versions of a class can be written to an output file: Once as executable code, once as DWARF debugging info, once as reflection data, and once as importable symbols for compilation of another module. The reason that these 4 different representations are necessary is because any of the last three can be deleted from the module without affecting any of the others - so for example you can strip out all the DWARF and reflection will still work. With a JIT, we'd only need to write a single representation, and then produce on demand any or all of those representations as needed. And the whole "dynamic linking" problem completely disappears.

Similarly, a JIT can make all kinds of optimizations that are not available to an AOT compiler. For example, if it knows that class A is never subclassed (because no such class has been loaded into memory), it can optimize calls to A's methods as direct calls rather than dispatched through a jump table. Of course, how much optimization you get depends on how long you are willing to wait at startup.

One could, in fact, design an intermediate representation that would allow better optimizations than C++, Java, or even LLVM IR, because it would preserve certain high-level invariants that could be used to guide optimizations that are normally removed from byte-code representations. (Note: This means that the "compiled" class files would not be LLVM bitcode files, but some higher-level representation.)

Writing a JIT for Tart wouldn't be all that hard, if we used LLVM's JIT engine as a base. And it would be fun. On the other hand - it would be completely, recklessly insane. Therefore I won't do it. That doesn't prevent me, however, from writing a design doc about it.

Tart status update

I was out of town most of last week, and didn't get too much done on Tart. However, now that I'm back I'm continuing to work on type qualifiers and mutability.

Tart now allows type qualifiers (readonly, mutable, immutable) to be bound to a template parameter. The syntax looks like this:

def somefunc[%Mod(?)](arg:Mod(Object)) -> Mod(String);

Basically what we're saying here is that "Mod" is essentially a function that operates on types - that is, it takes a type as input, and returns a modified type as output. Moreover, the type inference engine can deduce what kind of function it is by examining the context in which the function is used. If 'arg' is an immutable object, then "Mod(?)" gets bound to "immutable(?)", which in turn causes the result of the function to be immutable as well.

More generally, each place where "Mod" appears in the function definition is a constraint. Function arguments are contravariant, so the type of 'arg' must be a subtype of Mod(Object). Function return values are covariant, so Mod(String) must be a subtype of whatever variable or parameter the return value is going to be assigned to. Given those two constraints, the compiler attempts to find a definition of Mod that satisfies both.

One downside of the current syntax is that it doesn't let you choose which type qualifiers the parameter is bound to - which is not a big issue right now, because a type currently can only have one qualifier, but may be an issue in the future.

Other than that there's not much to report. I still need to update the exception handling code to work with the new LLVM exception stuff, I just haven't gotten to it yet.

Type qualifiers, resolution

I realized that in the discussions about type qualifiers (which were very helpful), I had forgotten to add a note describing what I had finally decided to do about them. Here's the specification I've come up with:

First off, there are 4 keywords used to indicate a qualified type: mutable, immutable, readonly, and adopted.

• "readonly" means that you can't change it, but someone else might. Readonly is considered to be a generalization (supertype) of both mutable and immutable, in that it provides guarantees that are strictly weaker than either.
• "mutable" indicates that you can modify the value. You can coerce mutable values to readonly values without an explicit type cast.
• "immutable" means that no one is allowed to modify the object. You can coerce immutable values to readonly values without an explicit type cast.
• "adopted" is used to extend the first three qualifiers (mutable, immutable. readonly) to other objects. Normally when you declare an object reference to be immutable, that immutability only extends to data which is actually embedded within the object - it does not extend to objects that are pointed to by the object. So an immutable object can contain a reference to a mutable object. However, when an object "adopts" another object, that means that the adopted object gains the same type qualifiers as the adopting object.
• An example would be a linked list class, which consists of a list header object, and list nodes. By declaring the node references in the header to be adopted, it means that if you make the list header readonly, then all of the list nodes become readonly as well; Conversely, if you make the list header mutable, then all of the list nodes become mutable.

These keywords can be used in several ways:

• All 4 keywords can be used to modify a type, for example "immutable(ArrayList)".
• Note that adding a qualifier to a type does not actually create a new, distinct type. Mutability / Immutability is really an aspect of the reference to a type, not the type itself.
• For example, if you have a mutable ArrayList and an immutable ArrayList, and you call getType() on them, it will return the same value for both.
• You cannot qualify an inherited type. You can't say "class MyList : immutable(List) { ... }".
  
• You can, however, pass a qualified type as a template parameter and it will retain it's qualifier. That means that List[int] and List[immutable(int)] are distinct types.
• Although I am wondering if this should be true...does it make sense to cast List[int] to List[readonly(int)]? Making the two be the same type would cut down on some level of template bloat...
• "mutable" can be used as a modifier on variable declarations, such as "mutable var foo". It means that the variable can be mutated even if the enclosing class is readonly. Normally variables have the same mutability as the enclosing class. (Since 'let' is used to indicate a field that cannot be changed, there's no point in allowing readonly or immutable as a variable modifier.)
• Note that both 'mutable' (when applied to a variable) and 'let' only extend to data which is inside the field itself, in other words, the range of addresses that are covered by the field. So a reference to an object may be immutable, but that says nothing about whether the object being referred to is immutable. However, you can easily add an immutable qualifier to the object type as well. So for example "let e:immutable(List)" declares an immutable reference to an immutable list.
  
• "mutable" can also be used on a function parameter declaration. All parameters are readonly by default.
• "mutable" can be used as a modifier on a property getter (declared with "get"), to indicate that reading the property has externally visible side-effects.
• "readonly" can be used as a modifier on a method declaration ("readonly def foo() -> int"), which means that the method can be called even if the object is readonly or immutable. Such methods cannot modify any fields of the object, except those that have been explicitly declared to be mutable. Methods are considered mutable by default, except for property getters which are readonly by default. You cannot declare non-member functions to be readonly.
• "readonly" can also be used as a modifier on property setter definitions (declared with "set"). This would only make sense if the value of the property was stored externally to the object.
• "readonly" can also be used as a class definition modifier "readonly class Foo", which simply causes all of the methods of that class to be considered readonly methods. This should not be taken to mean that objects of that type are readonly, merely that readonly is the default for methods of that class. (Making a class immutable is more a matter of insuring that it has no mutable fields.)
• "readonly", "mutable" and "immutable" can also be used to modify a value, as in "mutable(x)". This has the effect of a type cast for that value. Note that while it is legal to explicitly convert a mutable to immutable object, and vice versa, there is no guarantee that this will actually work - that is, if you cast a mutable value to immutable, it still might be changed by someone who kept a reference to the original mutable object; And if you cast an immutable object to mutable, you still might not be able to modify the object (it might be stored in protected memory.)

-- 

-- Talin

Some Metaprogrammatic Musings

One of the motivations for creating the Tart language was my interest in metaprogramming. One thing I've noticed is that there's a kind of parity between metaprogramming and reflection - that is, both tend to be used to accomplish similar goals, but the former does it at compile time, whereas the latter does it at runtime. And both techniques have space costs - metaprogramming's cost comes from template bloat, whereas reflection's cost comes from all of the static metaclass information that has to be emitted by the compiler.

An example of this parity would be testing mocks. Libraries like mockito use reflection to generate mock implementations - that is, you feed it an interface, and it returns back an object that implements that interface - but the implementation is merely creating a record of all calls and parameter values. One could imagine a metaprogramming approach to the same problem - given an interface, produce at compile time a recording implementation.

One trick that D has that makes metaprogramming easier is the 'static if' construct - having an if that is guaranteed to be evaluated at compile time makes it easier to write functions that are compile-time recursive. An example would be a template that takes a variable number of template parameters - this expands to a template that does something with the first type parameter, and then recursively expands itself with the tail of the type parameter list.

However, I was thinking today, why not a static 'for each' loop? Assume you have a sequence of types whose length is known at compile time. One example is a variadic template - another is tuple types. One could construct a for loop which would iterate over the types in the sequence. Rather than actually looping, what the compiler would do is unroll the loop - that is, for a sequence of N types, what you get is the inner body of the loop replicated N times, each time with a different type parameter.

An example of where this might be useful is in declaring production rules for a parser. Say we have a template "Sequence[%T...]" which takes a variable number of type arguments, where each type argument represents a matcher for some input. So you could do something like:

class Sequence[%Matchers...] {

  static def match(in:TokenStream) -> bool {

    for M in Matchers {

      if not M.match(in) {

        return false;

      }

    }

    return true;

  }

}

So if I invoke the template with something like "Sequence[Number, Identifier, Literal['if']]", what this turns into is code that calls Number.match(), followed by Identifier.match(), and so on. Of course, you can do something similar with object instances instead of types. Instead of "Sequence" being a type, instead it's just a function, and the matchers being passed into it are matcher objects, not matcher types. Again, it depends on whether you want to process this stuff at compile time or run time. (Notice, for example, that the 'match' function of class Sequence is static - no need to create any objects at all.)

Interestingly, this starts to look a little bit like Haskell Monads, which makes me think of another thing: Tart allows overloading of operators, but one operator that is not even defined is "juxtaposition" - that is, putting two expressions next to each other with just whitespace between them. The Haskell "do" statement takes a series of expressions, where each expression is processed by the monad, and the result of that processing is the context for the next expression in the series. The idea of an imperative sequence - that is, a set of steps done in order - is only one possible way to use this. It could just as easily represent a dependency graph, a decision tree or any other idea where you have some chain of ideas, each idea building on the previous one.

One can easily simulate this in Tart (or C++ for that matter) by operator overloading, with the downside that the syntax is not as compressed - so "number >> ident >> literal" could do exactly what "seq(number, ident, literal)" does. The question is, is it worth thinking about an even more compact syntax such as maybe "Sequence :: number ident literal", where you have some prefix (Sequence) that sets up a context, and that context let's you juxtapose the items, getting rid of the operators between the terms of the expression.

Anyway, this is all just speculation for the moment, I don't have any concrete plans to change the language in this direction.

Type qualifiers and method params

So I'm not terribly happy with the current syntax for specifying readonly function arguments.

I'm finding that in practice, a large percentage of all function arguments are readonly. This is no surprise - many functions take arguments that they don't modify. Unfortunately, this means that if you add the readonly qualifier to all of the places where it should go, the word "readonly" then appears in dozens if not hundreds of times in a typical source file. It makes function signatures considerably longer. It also violates one of my design principles, which is that the things that "stand out" visually in the code should be the things that are most important to the reader. In the case of a function declaration, the most important thing is the parameter type, and I find that adding readonly(Type) everywhere makes the parameter type less visually pronounced.

I have two ideas for solving this. The first idea is to make all function parameters readonly by default. That is, if you plan on mutating a function parameter, you'll have to explicitly declare it mutable. It turns out that if you do this, there's only a very few functions which require the mutable qualifier. This is good, because it really brings to your attention the fact that the parameter is somehow different from other parameters.

(I should clarify something - we're not talking about mutating the parameter, but rather the thing the parameter points to. So a parameter like "dst:mutable(char[])" means that you're allowed to set elements in the array. The parameters themselves are always mutable, although Tart will notice if the parameter is never assigned to, and will enable certain optimizations if that is the case.)

A different idea is to make a shortcut syntax for readonly. To fit within Tart's conventions, it should be a suffix. I was thinking something along the lines of "Type|r". I know that looks kind of weird - but then I was thinking, what if the "|" operator really meant "filter"? After all, that's kind of what "readonly" does - given an interface, it filters out (makes unavailable) all of the methods that would mutate the object. What if there were other kinds of filters? Not that I have any specific ideas for such.

My meta-theme here is that syntax should follow Claude Shannon's law of information, which in this case I interpret as "the more unexpected an event is, the more information it contains". The most common case contains the least information, and the notation for expressing that case should be terse. OTOH cases which are rare contain more information, and therefore should take up more space on the page.

This is part of the justification for having a shortcut syntax for array types (foo[]) and array literals ([1, 2, 3]). The three most commonly used containers are arrays, linked lists, and maps. These three account for something like 95% of all collections used in programs. I think that all three of those should have shortcut syntax, for the simple reason that they are so common.

Tart status update

I've been working on type qualifiers (mutable, etc.). This is a pretty large change, so I've been doing it in stages - I think there's been about 6 commits so far. Thank goodness for unit tests.

I'm also in the process of migrating the "failure" tests into the unit tests. Currently the failure tests work like this: There's a source file which contains example code which has errors in it - stuff that is supposed to fail. Each code snippet is preceded by a comment which contains a portion of the expected error message. The testrunner app attempts to compile each code snippet, and then compares the error messages produced with the comment.

The failure tests have not been updated in a long time. I've decided to get rid of the test runner - instead I have a new TestCompiler class that accepts the source code as a string, and which has various methods such as expectSuccess(), expectFailure(), expectWarning(), which integrate nicely with the Google test framework. This allows success tests and failure tests to be grouped together in the same source file, which should make it easier to maintain the tests. So far, about half the failure tests have been converted over. Here's a sample of what the tests look like:

EXPECT_COMPILE_FAILURE("class Test { adopted var test:int; }", "declaration modifier");

EXPECT_COMPILE_FAILURE("class Test { readonly var test:int; }", "Use 'let'");

EXPECT_COMPILE_SUCCESS("class Test { mutable var test:int; }");

EXPECT_COMPILE_FAILURE("class Test { immutable var test:int; }", "Use 'let'");

EXPECT_COMPILE_FAILURE("class Test { adopted let test:int; }", "declaration modifier");

EXPECT_COMPILE_WARNING("class Test { readonly let test:int; }", "are always");

EXPECT_COMPILE_FAILURE("class Test { mutable let test:int; }", "cannot be declared");

EXPECT_COMPILE_WARNING("class Test { immutable let test:int; }", "are always");

The first argument is the source code to compile, and the second argument is the expected error message, or a portion of it.

I also took a bit of a break and added BitArray to tart.collections, with unit tests. That was fun to write.