Category Archives: neutrino

Methods

Neutrino is an object-oriented language and as such the most fundamental operation is the method call. Neutrino methods are not smalltalk-style single dispatch ones, however, but multimethods.

The smalltalk model is nice and simple — but also limiting in practice. This obviously doesn’t just apply to smalltalk but any single dispatch language. You find yourself repeating the double dispatch pattern over and over. Operations that are binary by nature, such as addition and equality, are difficult to express in a way that is fully general. Generalizations such as catch-all methods or proxy objects can be awkward to express. Single dispatch is like an iceberg: the tip, the mechanism itself, has little complexity but there is a huge amount of hidden complexity that comes from having to express operations that are not, by nature, singly dispatched using only that mechanism. With neutrino I wanted to try a slightly more complex basic mechanism, under the assumption that it would reduce the amount of hidden complexity drastically.

The mechanism works like this. When defining what looks like a method you’re actually defining a matcher, so

def (this is Point).norm()
-> Math.sqrt(this.x*this.x + this.y*this.y);

might look like a method definition on Point but is, in reality a matcher that matches any call where the name is "norm" and the first argument is an instance of Point. Similarly,

def (this is Point)+(this is Point) -> ...

is not a method on Point but a matcher that matches any call with the name "+" and a first and second argument which are Points.

Using this model method lookup becomes a matter of, given a call, finding the matcher that best matches the call. This is done using a scoring function which, for each possible matcher, gives an integer value to each entry in the matcher and then takes the lowest scoring (best matching) function. In the first example, if you pass a Point then the match is perfect and the score is 1. If you pass an instance of a subtype, say a CartesianPoint then the match is less perfect and the score is 1 + the shortest distance through the inheritance hierarchy. This means that if there is a more specific method, one that takes a CartesianPoint, then it will score lower and be preferred over the method that takes general Points. If no method matches a LookupError is thrown. If there is no unique best match then an AmbiguityError is thrown. That’s it.

When matching, all parts of the matcher are treated equally. Some parts will usually be known at compile time, for instance the method name, which means that the compiler will be able to generate more efficient code. However, that is an implementation detail and the method name is a parameter like any other. In particular, a matcher that matches any String as the name and a Point as the first argument is as valid and no different from one that happens to have a compile-time known name.

I’ve been using this mechanism for a while and find it to be much more convenient than single dispatch. There is really no comparison. No more visitors, you get to just express what you’re trying to do. Multimethods are often accused of being confusing and hard to understand. I think this is a matter of keeping the lookup rules simple and not being afraid to report an error if there is no obvious best match, rather than use elaborate tie-breaker rules.

This may look like a challenge to implement efficiently but the mechanism has been designed such that you only pay for the generality if you actually use it. If you do normal single or double dispatch with compile-time known method names then that’s what you pay for and, in particular, double dispatch can be less expensive because you can express it directly rather than through chains of separate calls, which means that the system can more easily optimize for it.

I’ve written up the details of the mechanism on the wiki under MultiMethodDispatch. This also describes how this works with keyword methods, which neutrino has but which I haven’t described here.

Neutrino

In the past I’ve written on this blog about various programming language projects I’ve been working on, including neptune and saturn. It’s been a while though, mainly because I’ve been working on v8 and spent more than enough time implementing languages at work so I didn’t have the energy to do it as a hobby as well.

That is no longer the case and I am indeed back on the horse working on the next language, neutrino. I’m trying a different approach to writing about it this time since there are a lot of interesting implementation issues as well as language design issues. I’ve started a new blog, the neutrino blog, where I’ll post about language design and implementation progress. Go on, take a look!

What is neutrino?

One of my plans with this blog is to keep it light and stick with relatively short posts about a single thing at a time. I’m planning to start writing about what neutrino is and, in keeping with the plan, I will do it in a number of separate posts rather than one big one. In this one I’ll talk about what the goal of neutrino is.

What is neutrino? It is a new programming language and implementation. I’ve implemented a lot of experimental programming languages in my spare time. Some I’ve written about, like neptune and saturn. Most of them I haven’t because they’ve just been experiments that lived on my laptop and nowhere else. Neutrino is the next programming language in the sequence and the first one I’ve worked on for this long and still felt that everything fits together just as it should.

Here’s a snippet of neutrino code, a teaser. The syntax isn’t actually that important and will change over time so don’t pay too much attention to that. I’ll explain the details of what’s going on here in future posts.

protocol ElfStringTable is ElfSection;

def ElfStringTable.new() {
def result := new ElfStringTable {
table := new HashMap(),
strings := new ArrayList(),
r_size := new Ref(0)
};
result.ensure("");
result;
}

def (this is ElfStringTable).alignment -> 1;

def (this is ElfStringTable).size -> this.r_size.get();

def (this is ElfStringTable).name -> ".strtab";

def (this is ElfStringTable).type -> 3; // SHT_STRTAB

def (this is ElfStringTable)[key]
-> this.table[key];

def (this is ElfStringTable).ensure(key) {
def prev := this.table[key];
if prev = null then {
def index := this.size;
this.table[key] := index;
this.r_size.set(index + key.length + 1);
this.strings.add(key);
index;
} else {
prev;
}
}

def (this is ElfStringTable).encode(out, elf) {
def info := elf.layout.info(this.name);
assert_equal(info.start, out.length);
for (str : this.strings)
out.write_c_string(str);
assert_equal(info.end, out.length);
}

This is taken from the ELF file encoder that is part of neutrino’s linux implementation.

Besides some original ideas, neutrino takes its inspiration from a number of different places. Its concurrency and security constructs resemble those in E (the overall syntactic similarity with E is a coincidence though). The module mechanism is inspired by newspeak. The multi-stage programming model is inspired by MetaML and APT. The implementation approach and low-level programming library are very much inspired by the jikes RVM. There are many more examples like these.

These are all good ideas that are not available in any mainstream languages. There is great potential in creating a solid high-performance language implementation that combines these different ideas within one coherent model. The goal of neutrino is to do that.

Plankton

Neutrino needs to be able to encode object graphs as dumb data, for a number of reasons: as a wire format when communicating between processes over a binary connection, as an image format for binary images, as a serialization format for “paging out” whole processes, etc.

I’m already using a format which is the output of the neutrino compiler written in Java and which is the source format used by the neutrino native compiler written in neutrino, PIB (platform-independent binary). This format, however, is lame.

Before I start implementing its replacement, plankton, I decided to write down a draft specification, which has been a good opportunity to stop and think before forging ahead with an implementation. This format is simple, general, and compact. In particular, the template mechanism means that object graphs (trees really) representing syntax trees can be encoded as something no more verbose than bytecode in a way that doesn’t require special support — it falls out of the encoding mechanism automatically.

This specification is sure to change as I implement and use this but now the basics are there.

Linker Failure, Data Success

Over the last few weeks I’ve spent a lot of time trying to generate ELF files that would make the linux linker happy. Using the standard ELF tools like readelf and nm I got pretty far in generating structurally correct files, but ld just didn’t want anything to do with them, it said the files were in an unsupported format.

Finally I decided to build gold and trace through the code while it tries to link to see what makes it choke. This way I discovered the first problem: it had nothing to do with the file format, I had just accidentally used a 1-based index a place where I should have been using 0-based. It turns out that ld‘s error messages are not the model of accuracy. Hrmf.

The trouble didn’t end there, however, and I ended up building my own version of ld and tracing through that to figure out what the problem is. The code in ld does reveal some of the limitations inherit in C, as exemplified by the wonderful RELOC_FOR_GLOBAL_SYMBOL macro which is an absolute delight to debug.

Yesterday finally I gave up linux linking for now and spent some time working on static data in Mach-O files, which now works. The neutrino compiler can now embed data which is accessible to the generated program. This is an important step towards the generated runtime so I’m pretty excited about that. The next step is to be able to store complete object graphs, which will require some object pointer relocation fun in the generator. But I think we’re close to having all the fundamental building blocks in place for self hosting the language.

Macho Elves

Most of my time working on neutrino these days is spent generating object files. I had originally planned to generate executables directly and had a limited version of that working. However, I quickly ran into trouble with dynamic linking, which is required as soon as you want your program to interact with the surrounding system in any way.

Eventually I learned that you’re much better off interacting with the system through calls to the standard C library because libc is more stable than the underlying system call API. And you’re much better off letting the system linker turn your object files into executables than generating those executables yourself. It’s not that it’s impossible to do it yourself but it’s painful and I’m fine with letting the linker developers deal with that pain.

So now I’m working on generating native object files which means that I’ve spent a lot of time poring over the Mach-O file format reference and, lately, the ELF specification. They’re nice straightforward formats actually but it still takes a lot of time to shape the program output into the required form. The tools for working with object files are really good, otool and nm on mac and readelf on linux, and make this work a lot easier.

The current status is that you can build .o files on mac and link them into executables that can be run to successfully. As in

$> scons neuneu
[scons output]

$> ./bin/obj/neuneu.ia386.mach-o
int32 comparison
int32 arith
raw malloc
struct malloc
char_ptr_t
static data

What’s running there is neutrino code, compiled by neutrino code.

What I’m working on now is being able to do the same on linux and then the next step, the ability to store nontrivial data structures in object files. I will also need to eventually generated DLLs but since mac and linux are the only platforms I use regularly they’re the ones I’ll start with.

Ne.utrino.org

After existing just as a googlecode project, antineutrino, for a while I’ve finally started building an actual home for the neutrino project at ne.utrino.org. The code still lives at googlecode but there is now also a wiki, this blog, a main page and google docs.

This blog will be used to post development updates about the progress of the project and various topics about the neutrino language and platform.