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.

Discussions of Tart on Reddit

Thanks to Keir for pointing this out to me - apparently a bunch of folks on Reddit have discovered Tart, and there's a whole lot of comments - mostly negative, which is to be expected at this stage.

The good news (for me anyway), is that there aren't too many surprises - most of the points being brought up are things I have spent a long time considering. That doesn't mean that I should dismiss these points out of hand, however.

I see that there are a number of complaints which recur frequently in that thread. One is about the retention of "null" in the language - the so-called "billion dollar mistake". I've written about this before - getting rid of null gets rid of some good things as well as some bad. I think that the best I can hope for is to reduce the need for null in most cases, without getting rid of it entirely. Disjoint types goes a long way towards removing the need for null, but they are not appropriate for every situation. A prime example is an array of object references - you have to initialize the array elements to something, and whatever that something is (null or void or sentinel object whatever) is going to cause an exception if you use it incorrectly. (You could enforce that arrays can only contain "optional" types - but that makes arrays a pain to use. You could always require a specific "fill value" for new arrays - but that also makes arrays a pain to use. Or you could do what many functional languages have done and just ban arrays altogether, so that everything ends up being cons'd lists.)

Another recurring theme in the thread is the lack of concurrency primitives in the language. My response to that is there are a lot of languages which do quite well on multiprocessor systems without having concurrency baked into the language itself. Most of the languages that I have seen which do have syntactical support for concurrency also constrain the programmer to one particular style of concurrent programming - message passing, immutable shared state, actor models, and so on. I would much rather make a language that is flexible enough to let users of the language define such constructs for themselves, and let them compete in the marketplace until there is a clear winner.

Lack of libraries: This is a feature, not a bug. One of the things that makes Tart so much fun to work on is the blank slate - total freedom from all those irritating library decisions made by Sun Microsystems, Microsoft, or the C++ standards committee. Also, having multiple return values and disjoint types has a dramatic impact on library APIs, so you wouldn't want to be shackled to the old libraries anyway. (That being said, it should be easy to call external libraries like zlib - expecting the entire world to re-write everything in your language is unrealistic to say the least.)

More generally, the kind of people I'd most like to attract right now are people who enjoy writing libraries.

Garbage collection: Tart doesn't actually force you to use garbage collection, however, the presence of GC has a huge impact on the design of the standard library - for one thing, a big part of the design of any nonGC API is object lifecycle management, and that problem just goes away with GC. And since I'm not ambitious enough to write two standard libraries (one with GC and one without), I'll leave that as an exercise for whoever wants it badly enough.

There's a lot of complaints about syntactical choices, which I really can't respond to, since that's mainly a matter of personal preference. The only thing I will say is that I have specific theories about how much punctuation a language ought to have in order to maximize readability - neither too much nor too little. The easy recognition of a particular piece of code not only depends on the actual letters and symbols themselves, but also the shape of the code as it is laid out on the screen. (Exercise for the reader: Take a sample of code, and replace all letters with 'x' - can you still get a rough sense of the structure of the code?)

In any case, the important thing for me is not to get discouraged by negative comments - it's easy to point out flaws, more difficult to make positive contributions. And there are many areas where I could be convinced to change my mind with a sound enough argument.

Volatility

The "volatile" type modifier presents an interesting problem.

From what I understand, "volatile" is only meaningful on l-values - something like "(volatile int) 1" doesn't make a lot of sense. Unfortunately, when you pass a type to a template as a template parameter, you don't always know whether the template is going to use the type as an l-value or not. So for example if you wanted to create something like "List[volatile(int)]", we would have to allow the "volatile" qualifier on any type, l-value or not - it would basically be a no-op in most cases.

The other approach is to say that "volatile" is an attribute of a variable or field, rather than being an attribute of a type. This makes more sense, but the downside is that you can no longer pass it as a template parameter. Thus, in order to have an array of volatile ints, you have to create a special VolatileArray[int] class, which is an exact clone of Array except for adding the volatile qualifier to the array's internal member declarations.

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();