Sunday, December 25, 2011

Status update

It's been a while since I've posted on my progress. I'm still in the "taking a break from Tart" mode, which is why you haven't heard from me lately. I plan to get back to working on it after the holiday.

In the mean time, I've been busy working on Mint, and things are going pretty well. Mint can not only build itself directly, but can also generate makefiles to build itself indirectly. The Mint source tree now has a "build.osx" directory which contains both the Makefile and header files needed for building Mint on OS X. The contents of this directory are generated entirely by Mint. There's also a "build.linux" directory which will (soon) have the same setup for Linux platforms.

One of my design goals has been to make Mint useful for developers, even if their users don't have Mint installed on their systems. It would be hard to convince developers to use any new tool if it required all of their users to install that tool as well. Of course, Mint would be even more useful if the users had it installed, but first thing is to get some sort of momentum in the developer community.

To that end, I've made it so that the Makefiles generated by Mint are position-independent, so that you can check them into the source tree along with your source files. In other words, a developer can use Mint on their personal workstation, and then generate Makefiles which can be invoked by the users who check out their sources, without those users having to install Mint themselves.

Unfortunately, most projects need more than just Makefiles to build - they also need configuration scripts. For building on a foreign system, one can generally assume that something like 'make' exists, which means that one can use that as a common foundation. With configuration, however, that foundation is far less firm. There's autoconf, of course, which is built up out of shell scripts and m4 macros, but while most Unix-like systems have some version of autoconf installed, they may not have the version of autoconf that you need.

I haven't quite figured out what to do about this, but there are a couple of different paths that could be explored. One idea would be to have Mint generate autoconf-compatible scripts; another would be to generate my own configuration scripts that were not autoconf-based. A third approach would be to not do configuration at all, but instead ship pre-configured Makefiles / build scripts for the most popular platforms.

Ultimately, what I suspect developers want is a tool that will let them generate build scripts that will run on all of the platforms that they care about, while requiring the fewest number of additional tools or dependencies. So for example, it would be nice to press a button and get a Visual Studio project file, an XCode project, a Makefile for various platforms, and so on. The downside is that these pre-generated configurations can't cover every possible host environment, and so have to be configured for a least-common-denominator target environment.

Of course, all of this is based on some assumptions about the users. 99% of users don't want to build from source in the first place - they want to install pre-compiled binaries. And a developer working alone doesn't need a fancy configuration and build system, when they can just add a new source file in their IDE and hit the rebuild button. The use cases where one checks out source and rebuilds it are fairly limited by comparison:
  • The case where a team of developers is working on a single project.
  • The case of a software packager who is creating a binary distribution.
  • The case where a project doesn't yet have an installation script or binary packages, so building from source is the only option for users.
For the first two cases, having to build and install Mint first is not that huge of a burden. For the last case, it makes me think that the really compelling use case for Mint is in the creation of installation packages. That is, if I could figure out how to get Mint to automatically generate a .deb or .rpm or a .dpkg, that would be something that I think developers would really be interested in. Heck, that's something I myself would be interested in, for Tart...hmmm, time to start reading the docs on building packages.

Here are some links:

Monday, November 28, 2011

Mint progress

As I may have already mentioned, I decided to take a break from working on Tart, and spend a few weeks working on Mint. This should by no means be interpreted as a lack of interest or commitment in Tart. It's just that there are a number of difficult problems which have caused work on Tart to proceed with frustrating slowness. Most of these problems involve the complexities of generating DWARF debug info via LLVM's APIs, problems which I've already written about extensively and see no need to repeat here.

In any case, I decided to give myself a holiday and work on something fun. And in fact the progress on Mint has been nothing short of astounding - I think I've written several hundred source files over the course of the last two weeks. (I've also been using Eclipse + EGit to do the coding, which has been a remarkably pleasant experience.)

Those who want a quick overview of what Mint is can look here:


(Click the 'code' link at the top of that page if you want to browse the source.)

Of course, part of why the work on Mint is proceeding so rapidly is that unlike Tart, Mint has virtually no dependencies - it is a self-contained program that doesn't depend on complex libraries or other open-source projects in order to work.

At the present time, the "mint" program doesn't actually do anything useful. But it does do a number of things that are interesting.

For example, Mint is able to run simple 'configure' tests such as testing for the presence of a standard header file such as <malloc.h>. It does this by invoking the C preprocessor and then looking at the exit code. Note that these configuration tests are in no way "built in" - instead they are defined in the standard Mint library.

A Python-inspired 'import' statement is used to import the configuration tests into your project's build file:

from prelude:configtests import check_include_file, check_include_file_cpp

HAVE_STDIO_H   = check_include_file { header = "stdio.h" }
HAVE_STDBOOL_H = check_include_file { header = "stdbool.h" }
HAVE_STDDEF_H  = check_include_file { header = "stddef.h" }
HAVE_STDLIB_H  = check_include_file { header = "stdlib.h" }
HAVE_CPP_ALGORITHM  = check_include_file_cpp { header = "algorithm" }

The syntax "projectname:modulename" syntax in the import statement is used to import definitions from another source tree - this is how Mint supports multiple source trees in a single build configuration. The name "prelude" is a special pseudo-project that points to the location of the Mint standard library.

The Mint language tries to be as declarative as possible, describing the end result that you want to have accomplished, while hiding from view the steps needed to get to that end result. Although Mint does have functions, most actions are described by objects rather than function calls. The typical pattern in Mint is that instead of calling a function with N parameters, you would commonly define an object with N named properties, and then 'evaluate' that object to get a list of actions to perform.

The advantage of this approach is that we can take the graph of objects and interpret it in different ways. If we want to actually build an executable program we would evaluate the object graph into a set of runnable actions for invoking compilers or other tools. On the other hand, if we want to generate an Eclipse or XCode project file, we would translate the object graph into an XML file that could be read into those programs.

Going back to the above example, the "check_include_file" symbol refers to a prototype object. In Mint syntax, an expression of the form <prototype> { <properties...> } creates a new object with the given prototype. In this case, we're creating an object that inherits from the 'check_include_file' prototype, and specifying the name of the header file to test for.

The 'configtests' module in the Mint standard library contains the definition of 'check_include_file'. Here's the actual definition (with comments stripped for brevity):

exit_status_test = object {
  lazy param message : string = ""
  param program : string = undefined
  param args : list[string] = []
  lazy param input : string = undefined
  export lazy param value : bool =
      console.status(message)
      or shell(program, args ++ ["2>&1 > /dev/null"], input).status == 0
}

check_include_file = exit_status_test {
  param header : string = undefined
  message = "Checking for C header file ${header}..."
  program = "cpp"
  args    = ["-xc"]
  input   = "#include <${header}>\n"
}

Here's a blow-by-blow explanation of this code:

"exit_status_test" is a generic prototype that performs configuration tests by running some shell program and checking the exit status. "check_include_file" inherits from, and further specializes, this prototype.

A "param" declaration defines an object property. You can only assign values to properties that have been defined in a prototype - this is to avoid spelling errors.

A "lazy param" is one that is evaluated dynamically. That means that the value of the parameter is calculated each time the parameter is accessed (the normal behavior is to evaluate the value of the parameter at the time the value is assigned.) You can think of lazy params as equivalent to no-argument member functions.

Understanding lazy parameters requires a careful understanding of Mint's scoping rules. First, Mint uses lexical scoping, like most modern languages. Mint also uses object-oriented-style lookup rules, meaning that properties defined on an object take precedence over properties defined on that object's prototype. So for example in the code sample above, we can see that the property 'header' is used in the calculation of the 'message' property of 'check_include_file'. Thus, if you tried to evaluate 'HAVE_STDIO_H.message', you'd get the value 'Checking for C header file stdio.h...". Even though 'message' is a property of 'check_include_file', when it gets evaluated the value of 'header' is taken from HAVE_STDIO_H, not 'check_include_file'.

An "export" parameter is one that should be saved when writing out the build configuration. So for example, we want to save the result of our configuration test (so that we don't have to run it every time), thus the 'value' property is declared as 'export'.

The 'program' and 'args' parameters are the name of the program to run, and the arguments to pass to it, respectively. In the check_include_file prototype, we see that the program to run is "cpp" (The C preprocessor) and the argument is "-xc" (which forces C dialect, as opposed to C++ or Objective-C).

The "input" argument is used to specify text that is to be piped into the program's standard input. In this case, it's a single line which contains a #include of the header we're interested in.

Finally, the 'value' property of 'exit_status_test' is where all of the actual work is done: It first prints a message to the console, and then executes a shell command using the built-in 'shell' function. (Ignore the 'or' in there - that's a temporary hack due to the fact that there's no statement blocks implemented yet.) The 'shell' function returns an object, which has several properties, one of which is the exit status.

If you've gotten this far, I think you'll agree that the language is quite flexible, and that it should be relatively straightforward to create configuration tests of almost any imaginable sort.

I'll show one more code example from the Mint standard library. Although Mint does not yet have the ability to do anything useful with build targets, it does at least allow build targets to be declared. The following is the (unfinished) prototype for build targets that generate executables, and what's notable about it that it can figure out from the source file extension what compiler to invoke. Moreover, this map of file extensions can be extended by objects that inherit from this prototype, making it possible to support other languages.

object_builder = builder {
  param cflags : list[string] = []
  param cxxflags : list[string] = []
  param include_dirs : list[string] = []
  param library_dirs : list[string] = []
  param warnings_as_errors = false
  param builder_map : dict[string, builder] = {
    "c"   = c_builder,
    "cpp" = cpp_builder,
    "cxx" = cpp_builder,
    "cc"  = cpp_builder,
    "m"   = objective_c_builder,
    "mm"  = objective_cpp_builder,
    "h"   = null_builder,
    "hpp" = null_builder,
    "hxx" = null_builder,
    "lib" = identity_builder,
    "a"   = identity_builder,
    "o"   = identity_builder,
  }
  export lazy param implicit_depends : list[builder] = sources.map(
      src => builder_map[path.ext(src)] {
        sources = [ src ]
      })
  actions = implicit_depends.map(b => b.actions)
}

The interesting bit is in the calculation of the 'implicit_depends' property. This uses a Mint lambda function. The syntax for lambdas is "(args) => expr" or just "arg => expr" if there's only one argument. In this case, we're running a 'map' over the list of source files, and for each source file, we get the file extension, look it up in the dictionary, and return an object prototype. We then use that prototype to generate a new object using the "proto {}" syntax. So basically this generates a new builder object for each source file.

Sunday, October 30, 2011

Thoughts on a build configuration language

Work on Tart is on hold for the moment while I am waiting to hear back from the LLVM folks about a bug in llc.

In the mean time, I want to write down a few notes about "mint", which is the name of the hypothetical future build tool that I want to create. Although my plan is to write mint in Tart, there's nothing Tart-specific about it, and it could be written either in C++ or Python or some other language.

I've been thinking about this a lot lately, especially because there's a big discussion on llvm-dev about the future of the build system, and part of that includes some very passionate opinions about the pros and cons of cmake.

Anyway, here are some basic requirements for mint:
  • It should be fast.
  • It should be extensible, especially with respect to 3rd-party tools. One should be able to write an extension module for yacc or antlr that makes it as easy to invoke those tools as it is to invoke gcc.
  • It should support hermetic builds, so that a particular binary can be produced on a given host machine that is identical to one produced on another machine, even if those machines have different environments.
  • It should support generating project files for popular IDEs such as Eclipse, XCode, Visual Studio, and so on.
I'd also like it to support automatic download of dependent packages, but unfortunately this is an area which I don't have a lot of experience in.

So the basic idea is that the build configuration language (BCL) is a hybrid functional / declarative language that supports prototype inheritance.

The language is declarative in the sense that what it primarily does is describe a graph of objects, the Build Dependency Graph (BDG). Objects in the graph include targets, files, tools, actions, and other entities which are used in the build. Making the language declarative means that a build configuration file describes the relationships between these objects, but doesn't say how these relationships are processed or in what order - that is determined by whatever tool is actually doing the build. This is what makes it feasible to generate a project file for an IDE.

The language is functional in that an object's properties can be expressions which are lazily evaluated. For example, the set of flags passed to a compiler is calculated from a number of different inputs, including the user's choices as to whether to enable debug symbols, assertions, and so on.

Prototype inheritance allows for objects in the graph to be re-used. For example, when you declare a build target, you start by inheriting from an abstract build target prototype, and then fill in the details about your specific target. The abstract build target prototype knows about source files, output files, and dependent targets; your target fills in the details of what specific files are involved. Or you may choose to inherit from a build target prototype that knows how to invoke the C++ compiler, which saves you the trouble of having to write the command-line flags for the compiler.

Because prototype inheritance is used so much in this language, the syntax is very simple:

<prototype> { <properties> }

Where 'prototype' is some previously defined object, and 'properties' is a list of key/value pairs. So for example:

myProgram = program.cpp {
  sources = [ "main.cpp" ]
}

Here we are starting with the standard prototype "program.cpp", and filling in the 'sources' slot ('sources' is defined in the prototype, but it's empty). We are then assigning that to the name 'myProgram'.

We can then, if we wish, create a variation of 'myProgram' that is compiled with optimization:

myProgramOpt = myProgram {
  opt.level = 2
}

The "opt.level" property was also defined in the program.cpp prototype. The program.cpp prototype has a tool definition for the cpp compiler. Here's a glimpse of what the program.cpp prototype might look like, with many details omitted.

program.cpp = program.base {
  opt = dict {
    level = 0
  }
  cflags = []
  tool = compiler.cpp {
    flags = [
      match (opt.level,
        0 => "-O0",
        1 => "-O1",
        2 => "-O2",
        3 => "-O3",
        * => raise("Invalid optimization level: " ++ opt.level))
    ] ++ cflags
  }
}

The first few lines define a property called 'opt' whose value is a dictionary type - basically just a namespace. Within that is the property 'level', which defaults to zero. (I'm undecided as to whether 'level' should have a type as well as a default value - it wouldn't make sense to assign a string to 'level'.)

Next we have the tool that will get run when this target gets updated. The "flags" property is a list of flags that gets passed to the compiler on the command line. When the compiler is invoked, each element of 'flags' will get evaluated and transformed into a string. That string is then passed to the compiler as the shell arguments.

In the case of opt.level, we use a match expression to transform the optimization level numbers 0..3 into compiler flags of the form -On. The idea here is to abstract away the specific syntax of the compiler's command-line arguments, so that the same syntax can be used to control different compilers.

There is also a 'cflags' property that can be overridden by descendant objects, allowing flags specific to a particular compiler to be passed in.

The main idea here is that "builtin" compilers for C and C++ use the same descriptive syntax as for 3rd-party extension compilers. In other words, the built-in rules aren't special.

Another kind of prototype is used to define the command-line options to the build script itself:

enable-asserts = option {
  type = bool
  default = false
  help = "Whether to enable assertion checks"
}

This means that the user can type "mint --enable-assertions" to generate a build configuration with assertions enabled. Or even type "mint --help" to print out the various options available.

BTW, one thing that would be neat is if "--enable-assertions" could change just that one option, while leaving other options set to their current values.

Anyway, I'd be curious to know what people think of this idea.

Tuesday, October 18, 2011

JIT / AOT Hybrids

Something I've been pondering a lot lately is the notion of link-time code generation.

The Tart compiler generates a lot of synthetic data and code, compared to a language like C++. This includes reflection tables, stack maps for garbage collection, type adapters, and so on.

What I've been wondering is whether it would make sense to do this work in the linker rather than in the compiler. There's even a precedent for this: there's one data structure which is already generated at link time, which is the list of static roots - global data structures that need to be traced in the collector.

There's a variety of things that could be generated at link time, ranging from the "only slightly ambitious" such as interface dispatch methods, to the "wildly ambitious" such as generating DWARF debugging info or even instantiating templates.

In order to do any of this, the linker would need much more information about high-level data structures and types. Ironically, this information - basically a serialized form of the AST - is already generated by the compiler and stored in the module. This information isn't currently used by the linker - instead, it's used by the compiler to allow already-compiled module files to be imported, without having to have the original source files.

If we take this idea to it's logical extreme, what we end up with is something like a Java class file that's compiled ahead of time (AOT), instead of just in time (JIT). That is, you have a single, comprehensive encoding of all of the types and methods in the module, and this encoded information is then used to produce the reflection tables, tracing tables, dispatch tables, and DWARF debug info. (As opposed to what it does now, which is to generate all of these tables separately, at compile time, and then glue them together in the linker.)

This whole approach basically blurs the line between AOT and JIT compilation, in that the inputs to the linker look a lot like the inputs to a VM.

There's some problems to solve however.

1) One problem with using the serialized AST is that lacks a lot of information, since it hasn't been fully analyzed. Type names in the AST are just names - we don't know yet which type is the one being referred to. Similarly with methods and variables, all we know is the name at this point. The largest part of the compiler is the part that analyzes the AST and converts it into a CFG (Control flow graph) in which all types are resolved, template parameters expanded, and so on. We don't want all of this functionality to live in the linker - instead, we want the compiler to do the analysis and then pass to the linker the results of that analysis.

So the first problem to be solved is to come up with a way to serialize the CFG rather than an AST.

2) A second problem has to do with template instantiation. Currently templates are not analyzed until after they have been instantiated. The reason for this is that until they are analyzed, templates don't have enough information to be able to do a successful analysis.

As a simple example, take the max() function whose declaration is "def max[%T](a:T, b:T) -> T". This function requires that it's template parameter, T, have a less-than operator defined for it. If there's no less than operator, the template instantiation fails. Until we actually attempt to instantiate the template and bind some type to T, we don't know if there's a less than operator defined or not. That's why templates are written out as un-analyzed ASTs, rather than fully-analyzed CFGs.

To solve this problem, we would need to change the way template parameters work. In order to do any operation on a variable whose type is a template parameter, you would have to declare the template parameter as supporting that operation.

Say we have a template parameter T, and we have some value 'a' whose type is T. Now we want to call 'a.toString()'. In the current system, we don't know whether a has a toString() method or not, but if we attempt to instantiate the template with some type that doesn't have a toString() method, then an error will occur. In the new system, in order to call a.toString(), you would have to declare template parameter T as [%T <: HasToString], where 'HasToString' is a protocol type that includes a 'toString()' method. In other words, having a 'toString()' method is now an explicit requirement for parameter T, any attempt to instantiate the template with a type that doesn't have a toString() method will fail early.

(FYI - in the literature on type theory, what I have described corresponds to "parametric polymorphism" whereas the way things work now is "ad-hoc polymorphism".)

Unfortunately, Tart's protocol system only works on instance methods, not on regular functions. Right now there's no way to express the concept "match any type that has a less-than operator defined for it". In other words, what we would need is some way to say "given a type T, return true if there is a function 'def infixLessThan(:T, :T) -> bool' defined somewhere." At the moment, I can't even imagine what that syntax would look like. But for now, let's assume we come up with some way to do this.

By pre-declaring what methods we need, we can do the analysis passes on the template and create a CFG. This CFG won't actually be complete, because some types are still not known. But we can at least do enough analysis to be able to write the CFG out to a file.

3) Currently, you can link Tart programs in two ways: Either by using the Tart linker, 'tartln', or by using the standard LLVM tools (llvm-ld, opt, and llc). If using the latter, however, you need to load in the Tart-specific plugins for reflection and garbage collection.

In order to do the link-time code generation that I'm describing, we would need to put all of the code to do that into the shared library, so that it can be loaded as a plugin as well.

Tuesday, October 11, 2011

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.

Wednesday, October 5, 2011

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.

Friday, September 23, 2011

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

Thursday, September 22, 2011

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.

Sunday, September 18, 2011

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.

Friday, September 16, 2011

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.

Wednesday, September 14, 2011

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.

Sunday, September 11, 2011

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.

Sunday, September 4, 2011

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

Wednesday, August 31, 2011

Mutability

I've been reading up on the D language's idea of immutability. It makes some interesting choices, but I'm not certain they are the right choices for me.

D has two keywords, 'const' and 'immutable'. 'const' says that you can't modify the value, but someone else might. 'immutable' is a guarantee that the item will never be modified, and this guarantee may be backed up by storing the item in a protected memory page.

Moreover, both 'const' and 'immutable' are transitive - that is, any data structure that is reachable by a const type is also const. So if you have a pointer inside a const struct, the thing it points to is automatically const as well.

Another design point is that you can't typecast an immutable value to either const or mutable, since that would violate the guarantee of immutability. (Actually, I think there's a way you can, but attempting the mutate the value afterward may throw an exception if the value is in protected memory.)

I like the distinction between const and immutable, however I tend to favor the formulation used in the JodaTime libraries: You have a base type which is 'readable', with two subtypes, mutable and immutable. So for example, you have "ReadableDate" which only defines accessors for reading the value, but does not guarantee that those values will not change; Then there is ImmutableDate, which adds no new methods but does guarantee immutability, and then MutableDate, which adds the accessors for mutating the value.

The only problem with JodaTime is the extra work involved in writing 3 classes to represent the same concept. This is where C/C++/D gets it right, I think: You write the class once, with methods to both read and mutate the fields, and then you use a modifier keyword as a type constructor, which transforms the fully functional type into a more restricted version of that type.

If we combine these two ideas together, we get something that works like this: 'immutable(Foo)' takes the type 'Foo' and subtracts from its definition all of the mutation methods. 'readable(Foo)' does the same, except that you can cast either a Foo or an immutable(Foo) into a readable(Foo), but not vice versa.

How is the compiler to know which methods are mutation methods? Well, we have to tell it - this is one case where the compiler can't infer things automatically (As a general rule, Tart does not allow the compiler to infer an interface from its implementation. I realize that there are some languages which do exactly this, but I think that interfaces should be explicit.) Fortunately, we don't need to distinguish between readable and immutable in this case - all the compiler cares about is whether the method can mutate the state of the object or not. The main challenge here is to come up with a syntax that's easy to type, since approximately 25-50% of all instance methods will want to have this property.

You also need a way for some fields to be mutable even on a readonly object. A typical example of this is reference counting: You want the object to appear to be immutable to the outside world, but internally you are changing the reference count. In C++ we accomplish this by declaring the data member as explicitly mutable, or by declaring the method itself as mutable. The latter can be accomplished better, I think, by allowing the method to cast 'self': So we'd say something like "let mself = mutable(self)", and then use mself to access the various fields.

Finally, there's the question of transitivity. Tart already has a mechanism for defining non-transitive immutable member fields via the 'let' keyword instead. At the same time, I can't help feeling that the D rule is too aggressively transitive. I think that having an immutable array of pointers to mutable objects would be a fairly common use case.

Monday, August 29, 2011

The Copyable protocol

One of Tart's fundamental design decisions is that there should be no collection classes that have special, "privileged" status. In most programming languages, there are a few types that are built in to the compiler, and which have special syntactic sugar - so for example, in Java, arrays are a built-in type, and only arrays can use the bracket notation (array[n]) to access their elements. Whereas in Tart, the Array type is written in Tart, and moreover, any collection class can define an element access operator.

Actually, this design principle represents an unrealizable ideal more than it does an actuality. In truth, arrays do have special status in two ways: array literals, and functions taking a variable number of arguments. Both of these cases cause the compiler to generate code that constructs a new array instance. But once constructed, an array is no more "special" than any other collection.

There's a downside to this design principle, however. It's fairly common in programming to want to convert from one collection type to another - for example "flattening" a deque into an array, or converting a map into a list of tuples. In cases like these, it's highly inefficient to transfer the items one at a time from the source collection to the target collection. It would be better if there was some way to transfer elements en masse. Unfortunately, doing so requires knowing a lot about the internal representation of the collections involved.

For example, many collection classes use arrays internally - ArrayList and Deque being two prime examples. If we could arrange a bulk transfer of elements from one array to another, much of the overhead of copying could be eliminated. However, those arrays are private - allowing code outside of the class access to those arrays would destroy the data-hiding abstraction of the container.

This is where it's useful to have the compiler have special knowledge of some collections - because the compiler can recognize cases where a bulk transfer would be appropriate and generate code for it. But what if we wanted to extend this ability to user-created collection types? What we'd have to do is abstract the bulk transfer operation itself, so that the user-created classes could participate in bulk-transfer operations.

The Copyable interface represents one approach to solving this problem. Users never use Copyable objects directly - instead, when you pass one collection to another - such as ArrayList.appendAll(collection) - the destination collection checks to see if the source collection supports the Copyable interface. If it does, then it initiates one or more bulk transfers from the source collection. If it does not, then it will transfer the elements the conventional way, one at a time.

The Copyable interface makes certain assumptions about the destination container: It assumes that for a collection of size N, elements are numbered 0 .. N-1, and that sub-ranges of this numbering can be mapped onto ranges of contiguous addresses. So for example, elements 0-255 might be stored in one array, 256-511 stored in a second array, and so forth. Each bulk transfer operation specifies one of these contiguous sub-ranges as a destination buffer. It's up to the source collection to decide how to map it's own internal representation onto that buffer, and to copy its elements into that buffer. The source collection may have it's own internal divisions, which may be different from the destination's - in which case, the source collection may have to do more than one array copy to fill the destination buffer.

The actual copying of data is typically done via Array.copyElements or Memory.copy, both which use memcpy to do the actual transfer. (Tart does not allow redefining the meaning of assignment, so all objects are treated as POD. The reason is that the garbage collector can move objects around, so any assumptions made by an overloaded assignment operator would be violated anyway. But with garbage collection, there's far less need to overload assignment anyway.)

The copy operation is also synchronous - both source and destination are allowed to move things around in-between copy operations. There is no promise that the destination buffer will continue to exist after the copy finishes.

BTW, the idea of Copyable was inspired and greatly influenced by the Python buffer protocol, although Copyable is a much smaller and less featureful concept.

I/O Library

I've taken Guido's advice about using file descriptors rather than FILE * handles, and as a result the i/o classes are coming along nicely. MemoryStream and StreamTextWriter are done, with unit tests. FileStream and StreamTextReader are written but still need tests. The character codecs got an overhaul as well.

One of the nice things about all of this is that it has given me a chance to write lots of Tart code, which is a welcome break from writing the compiler in C++. You can definitely see the power of Tart when you have unit tests that look like this:

stream.write([1, 2, 3, 4, 5]);
assertContentsInOrder(stream.data, 1, 2, 3, 4, 5);

In this case, 'stream' is a MemoryStream, and the 'write' method takes in an array of bytes, which in this case is an array literal. "stream.data" returns a reference to the underlying collection (an ArrayList). "assertContentsInOrder()" takes a collection and a variable number of elements, and asserts that the contents of the collection equals that list (it does this by calling iterators.equal()).

This style of coding feels very Pythonic to me, yet it's all statically typed.

One minor disadvantage of using unix file descriptors is that there's no equivalent of feof(). The only way to know that you're at the end of file is to attempt to read, and then get 0 back as the result. This doesn't play so well with higher-level APIs, which are typically designed such that you can test for end of file before doing an actual read. fread() and its ilk provide this capability by reading ahead.

This means that my lower-level i/o classes have to expose this same behavior - I can't define an "eof" predicate for class IOStream. Such a method would be expensive without buffering or read-ahead of some type. And since we want the IOStream interface to be platform-agnostic, that means that we can't define an eof method even on platforms which do support it for low-level streams. We have to go with the lowest-common-denominator (both of platforms and stream types), which means that all IOStreams have to have unix-style end-of-file behavior.

Obviously the higher-level classes such as TextReader / TextWriter are buffered, so we can define an eof() method on all of these. It's only the lower-level unbuffered classes that don't support it.

Friday, August 19, 2011

Brainstorm: ScopedObject and Pinned

ScopedObject and Pinned are two features of Tart which are on my long-term TODO list.

ScopedObject is an interface that is used in conjunction with the 'with' statement. It has two methods: enterScope() and exitScope(). You'd use it like this:

with mutex.locked() {
  // Mutex is locked while in this block, will be unlocked on exit.
}

with file = FileReader.open("foo.txt") {
  // File will be automatically closed on exit.
}

tart.gc.Pinned is a helper class for creating 'pinned' objects - that is, objects that are fixed at a given address and cannot be moved around by the garbage collector. Pinned objects aren't something that normal users of Tart would ever deal with - they are mainly useful for people who are implementing i/o libraries.

Here's a typical example of how pinning would be used:

def writeData(data:ubyte[]) -> int {
  with pinnedData = GC.pin(buffer) {
    with GC.unlocked() {
      return lowLevelStream.writeData(pinnedData.get());
    }
  }
}

Here's what this is doing: GC.pin() takes an object reference and returns a 'pinned' version of that object. Depending on what memory region the object lives in, the return value may be the original object with the 'pinned' bit set in the object header, or it may be a shallow clone of the object. Cloning generally will occur if the original object lives in a compacting collection space - the clone will be put into a different space where object addresses are stable.

Note that the writeData() function will throw an exception if the buffer isn't pinned.

At the end of the outer with statement, the pinned object is disposed. In some cases, the data in the pinned object may get copied back to the original buffer. (Probably 'pin' will take some flags indicating whether the clone will be read/write or just read only.)

The inner 'with' statement handles interactions between the garbage collector and blocking i/o. The 'unlocked' method tells the garbage collector that it's OK for collections to take place while we are waiting for the i/o to finish. At the end of the block, the garbage collector is locked again (meaning that collections can only take place when we tell it that it is safe to do so.) Within the 'unlocked' state, objects may move around in memory - which is why we had to make sure that the input buffer was pinned.

Tuesday, August 9, 2011

Fun with debug macros

I recently introduced some new macros for doing assertions and conditional tracing, which was inspired by a conversation on llvm-dev. Here's how the new macro is used:

DASSERT(super != NULL) << "Expecting a non-null super class for type: " << type;

In other words, the assertion macro acts like a stream operator, allowing you to print a message that includes dynamic fields. There's also a DMSG(condition) macro which prints a message only if 'condition' is true.

DMSG(TRACE_CODEGEN) << "Adding a static root entry for: " << var;

One feature that DASSERT and DMSG have is that, like all good debugging macros, they impose no cost when disabled. This means that (a) no side effects occur if the condition is false, and (b) if the condition is both false and is a compile-time constant, the compiler should remove the message code entirely.

How does this work? Well, the DMSG and DASSERT macros construct a stream object. In the case of DMSG it's a generic output stream. In the case of DASSERT, it's a subclass of stream which calls abort() in it's destructor. Because the stream is a temporary object, it gets destructed at the end of the statement, after all of the messages have been printed.

Here's what DASSERT actually looks like:
#define DASSERT(expression) \
    (expression) ? (void)0 : Diagnostics::VoidResult() & \
        Diagnostics::AssertionFailureStream(#expression, __FILE__, __LINE__)
Let's start with the last part. AssertionFailureStream is the stream object - it's the right-most token in the macro, so any stream operators (<<) that come after the macro will be applied to the stream.

In the middle there's a C ternary operator '?:' which tests if 'expression' is true. Because the precedence of the ternary operator is lower than <<, the stream operators will get applied to the stream object, rather than the expression as a whole. Also, C++ guarantees that only one of the two choices of a ternary operator will be evaluated, so this means that the stream object will not be constructed, nor will the stream operators be executed, if 'expression' is true.

One catch is that both sides of a ternary expression have to be the same type - which in this case we want to be 'void'. Doing this requires another trick: pick some binary operator which has a lower precedence than << but higher than '?'. In this case, I've chosen the bitwise 'and' operator, '&'. Then create an overload for it which returns a void result:

/** Transforms a value of stream type into a void result. */
friend void operator&(const VoidResult &, const FormatStream &) {}
'VoidResult is just an empty struct - it's just there to insure that our operator gets called. So 'VoidResult() & AssertionFailureStream(...)' now has type void.

One final thing needed to make this all work is to define appropriate stream operators for various compiler classes such as Variable and Type, which print out the object in human-readable form.