One other metric of progress

One way of measuring the progress of the compiler is how often I have to stop and debug it when writing code. My work pattern used to be - write a handful of lines of Tart code, figure out why the compiler was asserting, write a few more lines, repeat, etc. But today the interval between debugging sessions was more on the order of several pages of code rather than several lines.

Once I get to the point where I can write major parts of an application without having to stop and fix the compiler, it will be time to encourage other people to try it.

Another measure of progress is a general feeling of trust and confidence about the compiler. What I mean is, when coding, normally one doesn't spend any mental effort thinking "I wonder if this next line I write is going to reveal a bug in the compiler". Normally ones thoughts don't dwell at that level, and one can instead fully concentrate on the actual code being written. I'm afraid I am not quite at that level of confidence yet.

The deconstructed for loop

I've been mulling over an idea lately and wanted to run it by folks.

Right now, the syntax for a 'for' loop in Tart looks something like this:

for i = 0; i < 10; ++i {

}

In other words, it looks just like a C for loop, except without the parentheses. I'm not exactly happy with using semicolons as delimiters here - nothing else in Tart looks remotely like this.

I thought about replacing the semicolons with keywords. "while" is a natural keyword for the test element. For the increment part, I thought about using "next" (harkens back to BASIC's for-next loops), however "next" is also a fairly common identifier. Another option is the word "then":

for i=0 while i < 10 then ++i {

}

// Another way to write it

for i=0

  while i < 10

  then ++i {

}

This isn't too bad I suppose.

There is one other advantage of using keywords rather than semicolons, which is the ability to leave out the parts you aren't using:

// This case is relatively common - the increment is inside the body.

for i = 0 while i < 10 {

}

// This case is also relatively common.

for i = 0 then ++i {

}

// An augmented while loop?

while i < 0 then ++i {

}

// Don't know why you would use this but it follows logically from the above.

for i = 0 {

}

// Not sure what this even means - add 2 to i, but return the previous value of i?

then i += 2 { return i; }

In other words, the idea is to deconstruct the 'for' keyword into individual 'atoms' which can be used independently.

In any case, I'm not sure I like this idea, but I wanted to see what other people thought.

Tart status update

Recent changes:

• Type solver now correctly solves nested array literals: let x = [[1, 2, 3], [1, 2, 3]];
• The EntryPoint module now converts argc / argv into a String[] array and catches any stray exceptions.
• Still needs work to run static constructors.
• Started work on tart.io.StringReader, unit tests in progress.
• "package-level" reflection implemented - this is the ability to iterate over all modules in a single package. (This is the first example of a data structure that is synthesized by the linker - there will be others to follow, I am sure.)

One issue that I am mulling over is the relationship between default constructors and reflection. Constructing a type via reflection is much easier if the type has a no-arg constructor. Otherwise, you have to know what values to pass to the constructor. Like most languages, Tart creates a default constructor if no constructor is defined by the programmer. However, unlike most languages, Tart's default constructor is not a no-arg constructor. Rather, the default constructor contains a parameter for each public member field, with a default value for that parameter which is the default for that field.

For example, given a simple type:

struct Point {

   var x:int;

   var y:int;

}

You can construct an instance of this type using any of the following:

var p0 = Point();

var p1 = Point(10, 10);

var p2 = Point(x=10, y=10);

In the first example, it appears as if no arguments are being passed, but that's not the case. Rather, the way default arguments work is that whenever a parameter is missing, the default value is passed in its place. So "Point()" is really equivalent to "Point(0, 0)".

But the default parameter mechanism isn't used when a method is called via reflection. The filling-in of default parameters is done by the compiler at compile time at the calling site. If you call "Point()" via some other mechanism, such as via a function pointer or reflection, then all of the arguments must be supplied, including the ones with default values.

While it is possible for a caller to inspect the type signature of the reflected function and figure out what parameters to supply, in practice this is quite difficult.

I ran into this problem while trying to write unit tests. Say I have a test class:

class MyTest : Test {

   var testClass:FooBar;

}

Since I didn't declare a constructor, the compiler will create one for me, with a parameter "testClass:FooBar". But the unit test framework doesn't know how to build a FooBar, so it can't construct the test class without knowing a lot more about the argument.

What I really want, in this case, is just to be able to construct an instance of MyTest without worrying about what constructor parameters are required.

It sounds like what I need to do is generate a no-arg constructor as well as the default constructor (assuming that the default construct has arguments to begin with.)

String iteration and (basic) string formatting

Some unit tests that demonstrate string iteration and rudimentary string formatting:

def testStringIteration() {

  let i = "Test".iterate();

  assertEq('T', typecast[char](i.next()));

  assertEq('e', typecast[char](i.next()));

  assertEq('s', typecast[char](i.next()));

  assertEq('t', typecast[char](i.next()));

  assertTrue(i.next() isa void);

  let i2 = "\u2100".iterate();

  assertEq(0x2100, typecast[char](i2.next()));

  assertTrue(i2.next() isa void);

}

def testStringFormat() {

  assertEq("Test {}", String.format("Test {{}}"));

  assertEq("Test Hello", String.format("Test {0}", "Hello"));

  assertEq("Test Hello", "Test {0}".format("Hello"));

}

Note that you can call 'format' either as a static method of class String, or as an instance method on a string literal.

One idea that I was considering was making strings callable. The rationale was that I wanted something really short for string formatting - like Python's original, now-deprecated '%' operator. Well, one way to do that is to simply remove the ".format" part of the expression, which gives you something like "Test {0}"("Hello"). However, I decided that this looked a little too dense in terms of punctuation - treading perilously close to the "looks like line noise" territory.

Hello, World!

Well, after two and a half years of work, I finally managed to get "Hello World" working. This must be a record of some kind.

Basically it involved fixing a number of bugs in the compiler which had been vexing me greatly and preventing the "Hello World" example from compiling. One bug had to do with initialization of constant static objects that were referenced externally. Another involved union types as the return value of a function, which were being passed the data in the wrong format.

With these bugs out of the way, I can now write some fairly sophisticated code. For example, iterating over an array of tuples:

def testTupleIteration() { var s = [(1,2), (2,3), (3,4)]; var asum = 0; var bsum = 0; for a, b in s { asum += a; bsum += b; }
assertEq(6, asum); assertEq(9, bsum); }

Notice that there are no type declarations anywhere in this code - yet, the code is completely statically typed, which means that there are no runtime type checks involved. It also means that the number of machine instructions generated is relatively small, and it should run fast.

There are still a lot of items left on the TODO list. This includes things like garbage collection, platform configuration variables, generating stack dumps from exceptions, run-time annotations, const/volatile types, closure scopes, 'finally' blocks in try statements, string formatting, and much more.

Semantic analysis woes

There's one part of my compiler that I am not particularly happy with, which is the analysis queue. Tart, like many languages, allows definitions to be in any order in the source file. Moreover, because it supports (limited) type inference, it means that some declarations need to be evaluated before others can be.

The analysis of a data type consists of many different passes over the structure. The most complex of these is ClassAnalyzer, which performs the following tasks:

• Populate the symbol table for class members.
• Resolve base classes.
• Analyze and apply annotations.
• Analyze template parameters.
• Analyze constructors.
• Analyze conversion methods.
• Analyze member fields and properties.
• Analyze member types.
• Analyze methods.
• Check for name conflicts.
• Figure out which methods are overloads of base class methods and build overloading tables.
• Add any externally visible definitions to the module's symbol table.

Some of these tasks have to be completed before certain operations can occur. For example, a call to create a new instance cannot be analyzed until the constructors for that class have been analyzed, since we need to be able to examine the types of the constructors to do overload resolution.

Worse, some types of analysis are cyclical - you can't finish A until you've analyzed B, and you can't finish B until you've analyzed A. My solution is to allow symbols to be in a partially analyzed state - while analyzing A, you can suspend what you are doing and go work on B, then return and finish A.

Now, all of this takes place during the compiler's second phase (analysis). The compiler has 3 phases: Parsing, Analysis and Code Generation. Phase 2 must be complete before Phase 3 starts - in fact, there's a check to make sure that no code attempts to add additional analysis work once phase 3 has started.

In phase 2, we keep track of the work we need to do via a queue. When we wish to analyze a class, we place it on the queue. If during analysis of that class, we discover other symbols that need to be analyzed, we have two options: If we need to know the result of the analysis right away, we can dive in and do it right there (we can pass in a set of flags that says what information we're looking for, so that it doesn't analyze more than is needed.) If, on the other hand, we don't need the answer right away, but we do know that we'll need the answer in phase 3, we can enqueue the symbol so that it will be processed eventually. Phase 2 ends when the queue is empty.

There's another queue which is used in Phase 3, but this queue is actually built in phase 2 and never modified in phase 3. This queue is the queue of all externally visible symbols which were generated in phase 2. Phase 3 walks the entire graph of all of the symbols on the queue and generates code for them. However, the entries are not always processed strictly in queue order.

Take for example a class on the queue. We need to build a vtable for the class, so we need to generate an exportable symbol for every instance method in the class. Even though the methods may be on the queue, we actually need them right now so we can get the pointer to stick into the vtable. Later, when the queue gets around to generating that function, it will notice that it has already been generated, and therefore skip it.

The relationship between symbols is very complicated, and there are about a dozen ways that one declaration can refer to another. For example, say I have a method A, which has a parameter of type B. The reflection data for parameter B consists of an object of type C, which contains an array of type D holding objects of type E, which have a superclass of type F. This superclass has a field whose type is G, which in turn has a class annotation of type H. The system is complex enough that reasoning about it is hard.

In order to prevent the compiler from compiling the entire world when you give it a single module to compile, phase 2 tries to do as little work as possible. Obviously, any type which is declared in the module being compiled must be fully analyzed, but what about imported symbols? In many cases we don't need to know everything about the imported symbol - thus, to return A as a return value of a function, you don't need information about how to call A's methods or how to convert A into B.

Template instantiations make this somewhat more complex, because even though the original template definition maybe external, the instantiated copy belongs to the module that invoked it. There's a special "Synthetic" bit which is set on any type or definition which was generated by the compiler, which tells the analyzer that this type must be fully analyzed.

So what exactly is the problem with this? Because reasoning about the system is so hard, I often make mistakes. The most common mistake is over-analyzing or under-analyzing a definition. If I over-analyze, it means that the compiler has to do more work than it needs to, and is therefore slower. If I under-analyze in phase 2, it means that some definitions will leak through to phase 3 without being sufficiently analyzed. This causes phase 3 to throw an assertion because the data it is looking for is not there.

A typical example: Inside class A there is a method B that has a parameter whose type is an enumeration class C. Because this information is reflected, we need to import the class tart.reflect.EnumType to generate a description of the enumeration. This involves the code generator creating a static instance of EnumType, so we need to analyze the member fields of EnumType. So we get to Phase 3, and the code generator complains that tart.reflect.EnumType has not had the "MemberFields" pass run on it (each type has a bitfield of what passes have been run.) So I have to track down where the missing link is.

I have run into so many bugs in this system that I feel like I am playing dependency whack-a-mole. But I can't think of any algorithm that is easier to reason about that will satisfy all of my requirements.

--
-- Talin

Tart status update

Well, the good news is that HashTable is coming along nicely and is about half done. This is, like HashSet, a quadratically-probed hash table that is written entirely in Tart.

I've also revamped all of the integer types (although I have not yet updated the docs) based on earlier suggestions. The new integer types are:

   int8, int16, int32, int64 - signed integer types.

   uint8, uint16, uint32, uint64 - unsigned integer types.

   int - synonymous with either int32 or int64 based on machine word size (compiler command line override.)

   uint - same for unsigned ints.

All containers except for String now use 'int' to represent lengths and offsets. That means that on a 64-bit architecture, an array can represent 2^64 items. String is still limited to 2^32 items, a not unreasonable limitation IMHO. Using 'int' this way eliminates the need for multiple overloaded methods in many cases.

Another bit of progress is that default template parameters are working now. This is used in HashSet/HashMap to supply the hashing function:

final class HashSet[%ItemType, %HashFn = Hashing.HashFn[ItemType]] : Set[ItemType] {

Hashing.HashFn has a number of overloads, one of which is:

/** Hash functor that calls computeHash(). */

struct HashFn[%T <: Hashable] {

  def hash(value:T) -> uint64 {

    return value.computeHash();

  }

}

'Hashable' is a protocol that simply requires that the object have a 'computeHash' method:

protocol Hashable {

  def computeHash -> uint64;

}

Thus, any class that has a 'computeHash' function with the given signature will bind to 'HashFn' (because of the superclass constraint operator '<:'), which in turn will work with HashSet/HashMap. Thus, objects used as hash keys do not need to inherit from any special class or interface, they just need to declare the computeHash method. For objects such as ints which cannot have a 'computeHash' method, you can define a custom overload of HashFn that calculates the hash differently.

In other words, protocols give you the equivalent of type-safe duck-typing :)

The not so good news is that there's a nasty bug that is preventing me from reaching the "Hello World" milestone. This milestone is defined as the ability to print out text strings using the real i/o library with the real character codecs - not some hacked up debugging text output function.

Anyway, I've been struggling with this bug off and on for the better part of 3 weeks, Today Alex Liberman came over for a social visit and sat down and looked at the bug with me, and while we made a little bit of progress the solution is still elusive. What appears to be happening is that the "idispatch" sequence of instructions - that is, the sequence of instructions generated when calling a method through an interface pointer - is being miscompiled. The weird part is that the LLVM IR looks correct to me, but the assembly does not, yet I can't think that LLVM would have that egregious of a bug and no one not noticed it. When I trace through the code in gdb, stepping one instruction at a time, I get very confused - the register that I think *ought* to be containing the object pointer instead turns out to contain the object's TIB (Type Info Block), and the register that ought to contain the TIB is instead holding the interface ID used for the dispatch. Alex suggested adding a member field to the object containing 0xDEADBEEF to make it easier to locate the object, but none of the registers appear to be pointing to it. Blah.

And the weird part is that idispatch works fine in other places.

Status update: HashSet

I've implemented the HashSet class. This is written entirely in Tart, and should be about the same speed as a native C version, although I haven't actually benchmarked the performance. The algorithm is a quadratically probed hash table. The hash function itself is specific to the type of item in the set, but generic hash functions (via murmurhash) are available for ints, strings, and any type that can be converted into a byte array. (The hash functions are also written purely in Tart.)

Here's one of the unit tests to give you a sense of how it can be used:

def testAddMany {

  let h = HashSet[String]();

  h.addAll("1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14",

           "15", "16", "17");

  assertEq(17, h.length);

  assertFalse(h.isEmpty);

  assertTrue("1" in h);

  assertTrue("2" in h);

  assertTrue("3" in h);

  assertTrue("4" in h);

  assertTrue("16" in h);

  assertTrue("17" in h);

}

Getting HashSet to work required fixing a lot of bugs related to passing small structs around and implementing the 'struct return param' for larger structs.

Optional types

In a response to my previous post, Guido suggested that I introduce an "optional" keyword to indicate that a reference type can be Null. I've gone ahead and implemented this, and here's a unit test to prove it:

def testOptionalType {

  var x:optional String;

  // Accessing x.length is OK since x is a string.    

  x = "Hello";

  assertEq(5, x.length);

    

  // However, x.length throws an exception when x is null.

  x = null;

  try {

    assertEq(5, x.length);

    fail("union member test failed");

  } catch t:TypecastException {}

}

The way that optional types (which are really just type unions with 'Null') work is that any attempt to dereference the type inserts a null pointer check. This throws as typecast exception (the reason is that 'Null' is considered a type.)

Tart Logo

I came up with a simple logo for Tart, which I'm calling "the Tart Dart":