Comparison operator overloading

I’ve just redesigned Radian’s suite of comparison operators so they can be implemented by any object. A “comparable” object is one which implements a compare_to method; this method must express the relative ordering of the self object and the method’s parameter. This is essentially the same as the Operator_Compare scheme I developed for REALbasic. I’ve added compare_to methods to the number and symbol atoms, and will do the same for the string atom too.

This came up because the map container needs to sort its keys in some specific order. Obviously the map can’t know about all possible key datatypes ahead of time, so the language needs a standard interface for comparability, and with that in place there’s no reason to implement the comparison operators any other way.

Map policy

I’ve been making some progress on the map datatype, one of a handful of built-in data structures. I decided to take the cheater’s way out and write it in C, inside the runtime library, instead of following my original plan and building it up from primitives (tuples) in Radian itself. I can always come back and rewrite it later; for now I am more interested in getting the language bootstrapped.

I’m considering a policy decision: what happens when you try to insert a value to a key which is already present? Does the map raise an exception, since you’re trying to do something whose meaning is somewhat ambiguous, or does it simply replace the existing value with the new one? The same question applies to the other map operations: what should happen if you try to remove a key which is not present? Does the map remain unchanged or raise an exception? Is the operation “make a map which lacks this key”, or “remove this key from the map”?

I am leaning toward raising exceptions in all of these ambiguous cases, because it seems more correct than making a policy decision which might be wrong sometimes. I am concerned that this will be annoying, though, and that the first thing I will end up doing is building a wrapper around the stock map that has the “just do it” behaviors.

LLVM integration success

The LLVM integration project has been coming along, and Radian no longer depends on GCC as a backend. It goes straight from Radian IR to LLVM IR and from there to machine code, which it runs in-process. This is not to imply that Radian is going to live in permanent JIT-land a la Python, but it’s easer to get things running that way. The runtime support is implemented as a separate library, which the compiler happens to link in, so the architecture still supports standalone executables.

Now that we’re using the actual target backend instead of emitting C source code and running through GCC, it’s time to implement the foreign-function interface. This will let us build Radian wrappers for any random shared library/DLL, and that’s the key to making this a useful system.

Other tasks on the near-term schedule are implementation of the intrinsic ‘map’ and ‘array’ types. I had originally intended to build the underlying AA-tree and finger-tree in Radian code, but bootstrapping is hard work, and I’ve decided to throw those data structures into the C runtime module instead. I can always port them back out sometime later.

Integrating LLVM

I’ve been working on replacing the Radian compiler’s gcc-based backend with LLVM. I’m always reluctant to introduce dependencies on external libraries, but LLVM is so uncommonly valuable that I’m willing to make an exception.

File I/O functions

Today’s checkin adds a pair of io functions, one to read and one to write the contents of a file. There’s also a new file module in the library which abstracts a file path.

import file from radian
var foo = file.from_path( "/some/path/here" )

The file module contains only the from_path constructor and a type? predicate; the file interface itself requires only a path property. This abstraction is overkill at the moment; I'm struggling between "you ain't gonna need it" and the sense that retrofitting this in later would make a mess of the API.

read_file(file, continuation)

An IO continuation, as I discussed before, is a programlet which receives as its parameters a new IO object and some value. In this case, the value is a buffer containing the contents of the specified file. A buffer is just a sequence of bytes, which is to say numbers in the range 0..255.

write_file(file, data)

The corresponding write operation replaces the contents of the file with the contents of the data, which must also be a sequence of bytes. The file's new length will be equal to the sequence's length.

After implementing this I realize that write_file needs a continuation parameter, too; otherwise there is no way to find out whether the write operation succeeded, or to sequence any further activities which depend on the existence and contents of the file.

Beginning of a type system

Last night’s checkin added a new binary operator: has lets you inquire about a container’s attributes. The has operator has the same precedence as the comparison operators. Its left operand must be a container and its right operand may be any value. The result is a boolean, which is true if looking up the value in the container would result in a non-exceptional value, false if the lookup would fail.

Combining this with the new symbol-literal syntax lets you ask whether a given object implements some method:

if foo has :bar:
    foo->bar(42)
end if

Testing for a set of related methods lets you determine whether an object implements some interface:

function stack?(foo):
    result = foo has :push
    result = result and foo has :pop
    result = result and foo has :head
end stack?

Rewritten IO, new input function

The io object I’ve been using all year is a simple stub, the barest minimum necessary to get some testing under way. It did not implement the queued IO strategy I described in my last post, but simply violated functional purity and hoped nobody would notice. This worked out fine since it had no way to read data, and until recently the language had no exceptions, but now it’s time to start doing a proper job of IO.

The new IO object looks almost exactly the same, but it implements the fancy queued, exception-safe IO scheme, and it has a more general internal architecture which will allow me to quickly create a whole array of useful IO functions. In the long term I would like to rewrite this module in Radian itself, using a foreign-function interface to call into the standard C library, but for now it’s enough to get the functionality in place.

The only new function so far is an input method, which reads one line from the standard input. I’ve implemented it, for now, to call a captured function rather than a method on an object. This is a functional style API, rather than the object-oriented style I’ve been favoring so far, but in the long run I plan to automate the whole callback process so I don’t think the choice will matter to anyone but power users.

This means that it’s now possible to write Radian programs that transform data. You’ll have to pipe the data in and back out, since there are no file-management methods yet, but it’s a start – this is the first time Radian can be said to actually have some utility as a programming language, marginal though it may still be.

Finished induction variable hoisting algorithm

Radian’s compiler can now hoist multiple independent subexpressions out of the body of a loop into a mapping sequence, extracting parallelizable computations from the loop body regardless of their complexity, order, or location, thereby allowing the parallel scheduler to distribute the work across multiple cores. This completes the feature I described on Tuesday.

There’s a mountain of work remaining before the compiler and the support library become anything that could be called a useful tool, but the combination of the hoisting algorithm and the parallel scheduler forms the centerpiece of the language concept, and I’m glad to have finished it. I think I’m going to miss it, too; I’ve been thinking over the eventual design of this piece of code for years, and it’s a little strange now to have actually built it.

The next project should probably be development of the IO system, which will necessarily include some support for concurrency. I’ll start with the standard input, output, and error streams, plus a way of reading command-line arguments.

Limited implementation of induction-variable hoisting

I’ve made a lot of progress on this milestone feature tonight: the compiler can now hoist a single subexpression out of a loop if it dominates the prime induction variable (that is, the element value returned from the original sequence). It’s a significant limitation, but this is enough of an implementation to demonstrate that the strategy I’ve been betting on this whole time will actually work. Expanding the system to allow for multiple subexpressions will take more engineering but no fundamental changes in the algorithm.

In plainer English, what does this mean? I’ll demonstrate with some actual code. Let’s say you have this little program:

for i in number.range(1,10):
    io->print( string.decimal( i ) )
end i

The compiler can now observe that the subexpression string.decimal(i) is independent of the rest of the loop: it depends only on the induction variable, i. Observing this, it can extract the subexpression from the loop, applying it to the input sequence as a mapping operation. It’s as though you’d written the same program this way:

for s in each string.decimal(i) from i in number.range(1,10):
    io->print( s )
end s

To make the extraction even clearer, there’s no reason any of that sequence stuff has to be part of the loop statement at all:

var strings = each string.decimal(i) from i in number.range(1,10)
for s in strings:
    io->print( s )
end s

It doesn’t matter which of these ways you write your loop – the compiler will transform them all into the same internal form. This is the whole point of the Radian project, really – you should be able to write your program in whatever way expresses your intent most clearly, then let the compiler worry about all the repetitive fiddly details involved in scheduling dataflow for a parallel computer.

Progress

Tonight’s checkin was a little bit of housekeeping work. GCC on Linux requires an -lpthread switch to use pthreads, while GCC on Mac OS X does not. This affects Radian because it is currently using GCC as its code-generating backend. I added a little cross-platform abstraction to the gcc command line invocation and now it works fine on Linux. The threading code itself needed no changes.

I have installed a copy of Windows under VirtualBox. There’s a Windows implementation in the code base which Aaron Ballman wrote last year, but I don’t think anyone has tested it lately. I’d like to keep all three platforms in sync, so I’m going to find some way to build code over there – probably Visual Studio Express.

The next big engineering project will be the induction-variable extraction system, which will extract as much of the body of the loop as possible into a (parallelizable) sequence. I don’t feel like I have the architecture completely worked out yet, but I’ve been thinking about it long enough now that I should probably just dive in and start building it. I can always refactor it later if I take a wrong turn.