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.

When object orientation is the wrong answer

One of the major refactorings I did this week is to completely replace the implementation of the "isSubtype" test.

The "is subtype" test is a binary relation between two types. There's even an operator for it in Tart: "<:" which is the same one used by Scala. So the expression "A <: B" is true if A is either the same as B or is a subtype of B. This particular test gets called in a lot of places - for example, deciding which of two functions is a closer match involves doing subtype tests on all of the arguments.

The way I originally implemented this in the compiler was by following the standard object-oriented approach: class Type, which is the base class of all types, has a pure virtual method "isSubtypeOf(const Type * base) const". Each subclass of Type (PrimitiveType, FunctionType, CompositeType, etc) overrides this and provides an implementation that is specific to that type.

However, the subtype relation isn't quite as cut and dried as all that. For example, what if the type being tested is a type alias that points to some other type? Well, you have to dereference the alias before you can do the subtype test. OK so we do that. But now, what if the base type is also an alias? Well we have to dereference that too. So now every type has to know about aliases - either that, or every place that calls isSubtypeOf has to dereference the types first.

It gets more complicated: What if the base type is a protocol? Any type can be a subtype of a protocol, because a protocol is simply a constraint - it says "this type has a method with such-and-such name and such-and-such signature". So for example, even primitive types have a "toString" method, which means that primitive types are technically considered subtypes of the "HasToString" protocol. OK so now every type has to know about protocols.

What about ambiguous types? These are temporary types, created during the type inference pass, that represent a "cloud" of related types which haven't been fully resolved yet. So for example, if we call "min(a, b)" the return value might be an int, or a float, or even a String depending on which overload of "min" eventually gets chosen. Each ambiguous type has a generator which can iterate through all of the possible types, and that generator will return fewer and fewer results as we tighten up the constraints looking for a singular solution.

The "isSubclassOf" test for ambiguous types requires that all of the "possible" types must each pass the subclass test, if any of them fails then the whole thing does.

There are also "type assignments" such as "%T=int" - meaning that the type variable T is assigned the value "int" within the current environment. Now, what happens if you have a template instance, where one or more of the type parameters is a type assignment or some other funky type? For example: given that ArrayList[int] is a subtype of List[int], is ArrayList[%T=int] also subtype of List[int]? The answer is, it depends on the environment - so now isSubtypeOf() needs to know about environments.

As you can imagine, with all these complexities the code is starting to look pretty nasty. Time for a redo.

In the new scheme, isSubtype(a, b) is now just a regular function - not even a class method. It's a fairly large function, since it has to handle all of the logic I've outlined above. However, it's not as large as you might think. Mainly what it does in complex cases is simplify the case by one step and then call itself recursively with the simplified arguments. Thus, if either of the two arguments are an ambiguous type, it generates the set of possibilities, and then calls itself for each possibility.

The biggest benefit is that all of the logic for the subtype relation is all located in a single file, which is much easier to understand than having it scattered across two dozen source files. Although some types have different logic, there's a lot of commonality too - for example, there's a whole set of types which have no concept of inheritance of subtyping - booleans and machine address types are an example - they both handle the "isSubtype" test the same way - by delegating to "isEqual".

New type solver and related progress

The great type solver rewrite is finally finished and all tests are passing! I've been working really hard on this, I even took 3 days off of work this week so that I could work on the compiler - I felt that things were getting really close to a conclusion and I was having trouble focusing on my regular work. (Although I did do *some* vacation-y stuff - like hiking in the redwoods with a friend.) However, it wasn't until yesterday morning that I actually solved the last bug and was able to commit a working version. Since then I've done a bunch of cleanup work, deleting old code that is now no longer needed, and so on.

I also noticed that LLVM's output stream class now supports ANSI color, so I added some code to display error messages in red, warnings in yellow and so on. Another thing I added was a new macro which helps debug non-fatal errors - in debug builds, it will print out the file and line number to set a breakpoint in the debugger, so you can just cut and paste it from the console instead of having to search for the error message in the source code. (A typical code pattern I use in the compiler is that when an operation fails, after printing out the error message, I reset the state and try the operation again - this makes it easy to trace through it in the debugger.)

All that being said, there's one caveat - while all this was going on, LLVM just dropped in a massive change to their APIs. I've actually been a supporter of this particular change and have been awaiting it with much anticipation, however it means that the next time I sync to LLVM I've got a fair bit of work to do.

In terms of release plans: I did a sort of "pre-announcement" of my 0.1 release on the LLVM mailing lists. I didn't get much response, which is no surprise - most people there are focused on their own projects. There are several other places where I could publicize Tart. One is the internal mailing list for language enthusiasts at Google. I will probably get a much larger reaction there, although a lot of it will most likely be negative - I expect a lot of criticism from the functional-language enthusiasts, and a lot of heat from partisans of competing languages like Scala and Go. There are also various newsgroups and mailing lists, although I don't really know my way around those fora and would be concerned about posting in the wrong place. At one point I considered posting on one of the Python mailing lists, based on the rationale that Tart is in many ways "inspired by" Python, but that rationale now seems weak to me.

Of course, I have another outlet, which is my 1500+ followers on Google+, most of whom I'm guessing are non-technical, so my announcement would be meaningless to the vast majority of them I suspect.

Fun with Symbolic Reasoning

So I'm about 3-4 weeks into the "great type solver re-write". It really wasn't my plan to re-write the type solver, but things have kind of snowballed. Originally my goal was to allow you to define an anonymous function without having to explicitly specify the types of the parameters - so you could say "fn (x, y) { ... }" instead of "fn (x:int, y:int) { ... }". However, it turns out that in order to make this work, I had to fix a lot of problems in the solver. There were a lot of places in the code where I had hacked around a particular problem instead of thinking it through and doing the correct thing. The new code is more abstract, but in many ways its easier to understand, which is always a good sign.

One interesting aspect of all this is that the type solver now does a kind of deductive reasoning: the input expression gets converted into a set of Constraint objects, and the solver attempts to optimize the constraints before it searches for a solution. An example would be two constraints such as "T is a subtype of List[X]" and "T is a subtype of ArrayList[X]". Since the first constraint is implied by the second, it is unnecessary and can be removed. A different example would be "T is a subtype of ArrayList[X]" and "T is a supertype of ArrayList[X]". Regardless of what X is, these two constraints can be satisfied only if T is exactly ArrayList[X].

The data model for the solver now looks like this:

• Template
• TypeVariable
• Environment
• TypeAssignment
• Constraint / ConstraintSet
• Provision / ProvisionSet

A TypeVariable is essentially a template parameter. Type variables can be bound to values within an environment. For each type variable, a TypeAssignment is created which represents the value of that variable within the environment - essentially it's a slot that is filled in with the value.

Associated with each TypeAssignment are an arbitrary number of Constraints. There are three types of Constraints: UPPER_BOUND, LOWER_BOUND, and EXACT. So UPPER_BOUND(x) says that the value of the TypeAssignment must be X or a subtype of X.

With each constraint there are zero or more "Provisions" (think of provisions of a contract). All provisions must be true, otherwise the constraint has no effect.

Here's an example of how this all works:

var a:int8;

var b:int16;

var c:int32

let d = min(a, b + c);

There are two function calls in the last line: A call to 'min' and a call to '+'. The type solver first identifies all of the overloads of these two functions:

def min[%T](lhs:T, rhs:T) -> T;

def infixAdd(a:int8, b:int8) -> int8;

def infixAdd(a:int16, b:int16) -> int16;

def infixAdd(a:int32, b:int32) -> int32;

(and so on)

After unification, the TypeAssignment for %T looks like this:

%T:

  >= int8

  >= int8  provided [infixAdd(a:int8, b:int8) -> int8]

  >= int16 provided [infixAdd(a:int16, b:int16) -> int16]

  >= int32 provided [infixAdd(a:int32, b:int32) -> int32]

Each '>=' represents a LOWER_BOUND constraint. The first constraint says that T must be at least an 'int8' if not larger - because the first argument to 'min' is 'a', which is an int8.

The second constraint says that T must be at least an int8 if the int8 version of infixAdd is chosen as the overload. Similarly, the third constraint says T must be at least int16 if the int16 version of infixAdd is chosen.

We can immediately eliminate the second constraint because it's implied by the first constraint.

After minimizing the constraints, we can now search for a solution by trying different values for 'T' (as suggested by the constraints), and seeing which solution has the highest ranking (where the ranking is calculated from a number of factors, including whether the assignment would produce a warning message.)

A much simpler question: Shortcut 'and' and 'or'

I was recently reading some blog posts comparing various languages, and in particular a "wish list" of language features that was informative. One of the things that the author wished for is to have the 'and' and 'or' operators work like they do in Python / Perl / JavaScript and other dynamic languages - specifically, that they could take non-boolean arguments, and return a non-boolean value.

So for example, a common JavaScript idiom is this:

function makeButton(opt_title) {

  this.title = opt_title || "OK";

}

The 'title' property of the object will be assigned the value of 'opt_title' if it evaluates to true, otherwise the default string "OK" will be used.

My question for the readers is - does this make sense in a statically typed language? There are a number of issues to consider:

Both arguments to the logical operator would have to have the same static type (or at least, be convertible to a common type). The resulting value would also have the same static type. From a compiler standpoint, this is fairly easy, no different really than the arithmetic operators which also require that both sides be promotable to the same type. The real question is whether this restriction - that the two sides as well as the result value have the same static type - makes the feature less useful than it would in a dynamic language.

The other issue is that both arguments would need to be implicitly convertible to boolean types. C and C++ implicitly map the integer value 0 and the pointer value NULL to boolean false. Other languages go farther and map the empty string "" and the empty array [] to false as well. And of course, in Tart you also have unions which can have 'void' as a member, so I'm assuming that those would be convertible to false as well. And what about floats? Or decimal numbers? To be completely general, we'd have to allow user-defined types to declare their own implicit conversions to boolean.

I've avoided such implicit conversions up to this point because in my experience they are a source of potential confusion. Right now, you have to explicitly compare values with 0 or NULL or the empty string in order to convert the value into a boolean.

Allowing implicit conversion to booleans would have far-reaching changes. For one thing, the 'if', 'for' and 'while' statements would have to change to be consistent with the 'and' and 'or' operators. It would be confusing otherwise - given a set of strings s1 and s2, if I'm allowed to say 's1 or s2' I would also expect to be able to say 'if s1' or 'while s1'.

Do you think that the convenience worth the possible confusion?

Type inference

I've written extensively about the type inference algorithm in previous posts, so I'll try not to repeat myself.

The type solver's purpose is to generate solutions for two kinds of problems:

• For functions which have multiple overloads, select the correct overload based on the input arguments.
• For functions which have template parameters, determine what type is bound to each template parameter.

I want to focus on this second item. For each templated function call, the solver creates a BindingEnv ("binding environment") object that stores the values of each type variable. So if I have a function such as:

def min[%T](a0:T, a1:T) -> T;

The BindingEnv stores the definition of T. If there is more than one call to "min" in a given expression:

let a = min(b, min(c, d));

...then the algorithm creates two BindingEnvs, each of which may have a different value for T. These values are referred to as substitutions. For example if I add a substitution declaring that "T" is an "int", what I am really saying is that types 'T' and 'int' are equivalent.

Unfortunately, having multiple environments creates a number of problems. The first has to do with backtracking.

Here's how backtracking works: Say we call our 'min' function with two incompatible arguments, such as List[String] and float. The solver first attempts to add a substitution for T := List[String]. However, when it gets to  the second argument, it realizes that T cannot be equivalent to both List[String] and float, so it needs to 'unbind' the previous substitution. The way this works is that BindingEnv has the ability to backtrack to a previous state - you call env.getCurrentState(), which returns a token (an int, actually), which can then be used to call env.backtrack(token) and remove all of the substitutions that were added subsequent to the call to getCurrentState().

However, where we run into trouble is when more than one BindingEnv is involved, because now we need to backtrack multiple environments and keep them in sync. A more robust approach is to just have a single environment for the whole expression, with one single backtracking state.

But then how do we deal with multiple different occurrences of 'T' in the same expression? The answer is we need to relabel all of the variables in each call: That is, we transform 'T' into 'T1' or 'T2', depending on which T we are talking about. Now all type variables are unique, so we don't have to worry about collisions anymore, and we can have just a single environment.

Another limitation of the current solver is that within an environment any given variable can only have a single substitution that is currently active. Say for example we know that 'T' == 'List[S]' where S is another type variable. Later we refine this and add 'T' == 'List[String]'. We don't remove the old substitution - instead we add a new one on top, so that it hides the previous substitution. That way, if we have to backtrack, it will revert to the previous value of 'T' rather than losing it entirely.

The problem with this approach is that it's attempting to do the reconciliation between the new and old substitutions too early - for example if we have 'T' == 'List[A]' and 'T' == 'List[B]', and we don't know what 'A' and 'B' are yet, there's no way to know which of the two definitions should win. Instead, what we should do is keep both definitions, and reconcile them later.

In fact, what I'd like to do is to make the type inference algorithm have clearly defined phases. (It has phases now, but they aren't cleanly separated.) The phases would be:

• Gather constraints - walk through the entire expression and find all overloaded functions, type variables, and other "choice points" - places in the expression where the type solver is able to choose between several alternatives.
• Relabeling - replace all type variables with new ones that have unique names.
• Unification - this is where we identify all possible substitutions. Note that some substitutions are conditional - say I have two overloaded versions of "print", one which takes a String, and the other takes a %T, then the substitution for %T is only meaningful if the second overload is chosen.
• Constraint simplification - if we have a set of substitutions {T := S, S := int} we can replace them with {T := int, S := int}.
• Overload selection - this is a fairly standard constraint minimization algorithm. For each choice point, we compute a ranking that says how good the choice is. For example, if we have a function that returns a uint8, but the variable being assigned to is a uint16, that's not as good of a choice as a function that returns a uint16. The algorithm attempts to maximize the ranking for the whole expression. (Because the choice points are interdependent, choosing the best result for one node in the expression tree may cause a worse choice elsewhere.)
• Error reporting: If any of the phases fails, or the final result would produce type conversion warnings, we want to clearly inform the user of what went wrong.
• Finalization: Replace all of the temporary type variables with the actual concrete types that they are bound to in the environment.

In any case, I have a ways to go before this particular vision can be achieved.

Good news

I've finished setting up my new desktop machine, and I've managed to compile Tart and run all of the tests - which passed.

So the overall status looks like this:

• 64-bit Linux (Ubuntu): Pass
• 64-bit OS X (Snow Leopard): Pass
• 32-bit OS X (Leopard): Fail

That's all the data points I have at the moment, but it'd a good bet that the problem has to do with 64 vs. 32 bit compatibility.