Monthly Archives: December 2010

My last post about protocols used object instantiation but glossed over how it actually works. One reason for that is that I haven’t sorted out all the details of it yet, but I think I’m close enough to a solution that I can give a rough outline of how it will work.

Most languages I know have some form of construction phase when creating objects. During this phase the object isn’t fully initialized yet so many of the assumptions you can usually make don’t actually hold yet. The object under construction is allowed to be in an inconsistent state, and in some cases you can observe these inconsistencies. Here is an example of a program observing two different values for a final field in Java, which is otherwise not allowed to change:

public class Test {

  private final int value;

  public Test() {
    printValue();
    this.value = 4;
    printValue();
  }

  private void printValue() {
    System.out.println(value);
  }

}

The exact same thing is possible in C++:

class Test {
public:
  Test() : x_(print_x()){
    print_x();
  }
  int print_x() {
    printf("%i\n", x_);
    return 0;
  }
private:
  const int x_;
};

Even though the field is supposedly constant this prints two different values for it (technically the value of x_ is not well-defined before it is initialized so it might not change because it was already 0).

I use Java and C++ as examples because those languages make an effort to limit what you can do during construction, an effort which is nowhere near airtight. Other object-oriented languages, for instance python, have more relaxed rules, and some, like JavaScript and smalltalk, have none at all.

For neutrino I had several requirements in mind for object construction. It must be possible for one implementation type to extend another, and extra code should not be required in the supertype for this to work. There should be no constructors, methods that are allowed to construct or initialize objects but are covered by various rules and restrictions. It must be possible to construct and subtype immutable objects. It must be possible for each step in the construction process to execute arbitrary code to calculate the fields of the new object.

The model I ended up with to support this has two components: three-state objects and field keys. I’ll first outline how they work and then give an example at the end.

Three-state objects

All objects are in one of three states: under construction, mutable and immutable. An object can only move towards more restrictions, that is, from being under construction to being mutable and from being under construction or mutable to being immutable. For now we’ll ignore the mutable/immutable distinction and focus on being or not being under construction.

When an object is born it has no state and implements no protocols. It is an empty atom which has nothing but its object identity. However, since it is in the under construction state all that can change. An object under construction can have protocols added to it, which means that the object will now respond to all the methods associated with those protocols. It can also have fields set and changed, similar to how this works in JavaScript and python: when you set a field the object doesn’t yet have that field is created. There are also notable differences to those languages though.

An object under construction can be passed around to any number of methods which can set fields and add protocols – construct the object, basically. When the object is considered done, typically when it is returned to the constructor call that started the construction process, it can be moved to one of the two other states. From that point on construction will be considered complete and it will no longer be possible to add protocols to the object, though it may still be possible to add and set fields.

This model means that the fact that the object is under construction is understood by the underlying system. There doesn’t have to be any restrictions on the code that constructs the object, any method can do that. One “constructor” method can be extended by having the “sub-constructor” simply call the original constructor and then extend the returned object, which is still under construction, with additional fields and protocols. There is no restriction on how many objects are under construction at the same time.

This model means that during the construction phase you’re not encumbered by restrictions on how you’re allowed to write your construction code. The object is in a special state, the runtime system understands that and allows you to construct it however is convenient for you. After, the runtime system knows that the object can no longer change how it is constructed and can use that information to optimize the program. In Java and C++ any property of an object that is violated during construction is worthless for optimization purposes because it is impossible to tell, short of adding an implicit under construction flag, whether it is safe to rely on this property.

Field keys

Before I mentioned that you can add and set fields during construction, similar to python and JavaScript. That is only true in a limited sense. Neutrino objects don’t have fields in the usual sense but instead use field keys which are similar to private names as proposed for JavaScript. Where JavaScript and python use string names to identify an object field, for instance the string "x" to get the x coordinate of a Point, neutrino accesses fields through keys. A key is an opaque object, you might think of it as a capability for accessing a particular field. When implementing a Point type you would create two new keys, an x key and a y key, and use them to store the actual coordinates of point objects.

protocol Point;

@static def Point_x := new GlobalField();
@static def Point_y := new GlobalField();

def Point.new(x, y) {
  def result := new Object();
  result::Point_x := x;
  result::Point_y := y;
  Point.attach(result);
  return result;
}

def (this is Point).x -> this::Point_x;

def (this is Point).y -> this::Point_y;

Here we create two field keys and use them to attach the two coordinates to the point, setting them (which means creating them) in the new method and reading them in the two accessors. Direct access to the field values is only possible if you have access to the Point_x and Point_y values, which can be kept private or exposed as appropriate. As usual, this is not how you would write your program but how the underlying concepts work and how the implementation understands object construction. There would be shorthands for doing all this and I expect that actually seeing field keys will be rare.

The way this works there is no way for different fields to interfere — if you want to associate some data with an object you just make your own key and store the data, and no other user of the object should care. This is much more flexible than languages where the set of fields is fixed by the type declaration, but should be no more expensive in the cases where all you need is a fixed set of fields set by a straightforward constructor. Code like the above is straightforward to analyze and optimize, especially in this cases like this where it is impossible to observe the result while the fields are being set and the protocol added.

That, basically, is how object construction works in neutrino. I’ll describe the second part of this, how the mutable and immutable states work, in a later post.

One of the most fundamental constructs in neutrino is the protocol.

Protocols are similar to Java interfaces in some respects, and the basic purpose of a protocol is similar: to specify that an object supports a certain behavior without necessarily specifying an implementation of that behavior. However, protocols are also very different from interfaces.

To begin with, here’s an example of a protocol declaration.

protocol Vector is Collection;

Already you see a considerable difference between protocols and interfaces: protocols don’t specify any methods. A protocol is, at the outset, completely opaque and atomic. How does this match with what I just said, that a protocol is used to specify that an object supports a certain behavior?

In Java, interfaces are very much a tool of the static type system. On the one hand, implementing an interface forces you to implement a particular set of methods, otherwise your program will not compile. On the other, if you’re given an instance of an interface then you’re guaranteed that the it will have an implementation of its methods. Note, however, that this kind of static checking is limited. As long as you define methods with the right signatures that’s all the type checker cares about, it doesn’t care how you implement them or whether they obey their respective contracts.

Imagine for a moment that we could remove the type system from Java (ignoring the ways it interacts with program behavior through static method overloading, reflection, etc.). What use would the methods listed in an interface be? They would be a convenient way for a programmer to see which methods to implement, and which he could call, but the language wouldn’t actually care. Machine-readable documentation is a good thing, certainly, but the goal of neutrino is to be as simple as possible at the basic level, and then allow more complex utilities – like type systems – to be built on top. Since neutrino is a dynamically typed language the implementation really doesn’t need to know which methods corresponds to a particular protocol. If you say that your object is a Vector then that’s all the implementation needs to know, it doesn’t care what the requirements are for being a Vector, not which methods it requires nor, as with Java, whether the implementations obey the contracts for those methods.

That was the first major difference between protocols and interfaces. The second is that you can associate behavior with protocols.

In Java, an interface is a pure specification with no behavior. I’m sure this is intentional, and I understand why that is, but it does cause some serious problems. In particular it causes tension between keeping interface small to make them easy to implement, and making them broad so they’re easier to use. A classic example is Java’s List interface. For convenience, the List interface has a lot of methods, many of which could be trivially defined in terms of each other. Like addAll in terms of add, isEmpty in terms of size, toArray in terms of iterator, and so on. Beyond these there is a number of utility functions in Collections, like indexOfSubList, replaceAll, rotate, etc., which actually belongs to List. In other words, there are some methods that are intrinsic to being a List, like add and size, some that are simple utilities that are included in the interface to make it convenient to work with, and some that are less common or challenging to implement which are put outside the interface in a utility class. This sucks for the user of List because he has to look for methods both on the list itself and the utility class, and it’s a drag for the implementor of a class that implements List who has to choose between making his one and only superclass AbstractList or re-implementing a dozen trivial utility methods.

The way neutrino deals with this is to allow protocols to have methods with implementations. Say we required implementations of Vector to have a .length method. Regardless of how a Vector is implemented we can then define

def (this is Vector).is_empty -> (this.length = 0);

The tension is now gone. The module that defined Vector can provide as many utility methods as it want directly on the vector, without thereby tying down the implementation – you’re still free to implement the intrinsic methods, the core methods that everything else builds on, however you want. Your implementation is also free to override any of the default implementations. The programmer that uses Vector has access to all the convenient utilities and can enjoy greater reliability because there only has to be one implementation of .is_empty rather than, as in the case of List, one for each implementation that for whatever reason decides not to extend AbstractList.

To put it all together, here is one example of how this can be used. Here’s a definition of a generic vector interface and some utility functions to go with it

/**
 * A finite, read-only, random-access vector.  Requires
 * implementations of .length and the indexing operator.
 */
protocol Vector;

def (this is Vector).is_empty -> (this.length = 0);

def (this is Vector).for_each(fun) {
  for (i : 0 .. this.length)
    fun(this[i]);
}

def (this is Vector).contains(val) {
  with_1cc (return) {
    for (elm : this) {
      if elm = val
        then return(true);
    }
    false;
  }
}

Based on this you can easily define new types of Vector which defines the required intrinsics:

/**
 * A range represents a series of integers from
 * 'from' to 'to'.
 */
protocol Range is Vector;

def Range.new(from, to)
 -> ...; // Let's cover object construction later.

def (this is Range).length
 -> this.to - this.from + 1;

def (this is Range)[index]
 -> this.to + index;

After we’ve implemented the intrinsics of Vector we get all the extra functionality for free:

def range := new Range(0, 10);
range.contains(5);
> #t
range.is_empty
> #f

In some cases we can implement these methods more efficiently, and there we can simply override the default implementations we get from Vector:

def (this is Range).contains(val)
 -> (this.from <= val) and (val < this.to);

You get some of the same advantages with abstract superclasses or traits, but this is simpler. This description has only covered protocols in terms of simple single inheritance, but it generalizes straightforwardly to objects that implement more than one protocol, and to multiple dispatch. But that will have to wait until a future post.

Neutrino has two basic control structures: method calls and one-shot continuations. In my last blog post I outlined how method calls work. In this one I’ll outline one-shot continuations.

You may already be thinking: continuations? Seriously? But it’s not as hairy as it sounds. First of all, these are one-shot, not fully general call/cc. It’s really just a convenient way to define all the usual control structures, including break, continue, and local and non-local return, in terms of one fundamental construct. In particular, one-shot continuations are, even in the most general case, no more expensive in terms of implementation complexity than non-local returns.

In the current syntax (I’ll get back to the topic of syntax and why you shouldn’t focus too much on that later) a one-shot continuation use looks something like this:

with_1cc (return) {
  for (i : 0 .. 10) {
    if found_it(i)
      then return(i)
  }
  -1;
}

What’s happening here is: at the beginning of the with_1cc statement we capture the current continuation and store it in a variable called return. We then loop from 0 to 9 and, if a condition holds, invoke the continuation and immediately yield the specified value as the result of the with_1cc expression without executing any more of the body. If the condition doesn’t hold then the continuation is implicitly invoked with the result of the body which is -1. Invoking a one-shot continuation more than once is an error and the final implicit call ensures that you’ll get an error if you try to invoke the continuation after the with_1cc expression has completed.

That’s all there is to with_1cc: it gives you a function that you can call — once — to bail out of an arbitrarily nested computation and yield a value to the whole expression. Cases like above where the capture and use of the continuation occur together in a single function are easy for the compiler to recognize and for those it can generate code that doesn’t actually materialize the continuation but simply uses a jump to leave the expression. This will work in any situation where you could use break, continue or local return in a standard C-family language:

def my_function() {
  with_1cc (return) {
    // ... prepare loop ...
    with_1cc (break) {
      for (i : 0 .. n) {
        with_1cc (continue) {
          // ... loop body ...
        }
      }
    }
    // ... finish ...
  }
}

The above code is obviously very verbose and luckily you wouldn’t have to actually write that in neutrino — the syntax is flexible and the compiler is free to automatically introduce with_1ccs when required. The point is that this can be used to implement any of the basic local jumps from the C-like languages, except for goto, and generate as efficient code for each of them as in languages where they’re built-in. In addition to mimicking other control structures it also allows patterns that are not possible on C-like languages, like expression-local returns:

def matching_entry := with_1cc (leave) {
  for (entry : this.entries) {
    if entry.name = name
       then leave(entry);
  }
}
print("Found entry: ${matching_entry}");

This code loops over a list of entries and leaves the loop, but not the whole function, immediately when the appropriate one has been found. This can be simulated in various ways: creating a utility method that uses normal return, assigning to matching_entry and breaking out of the loop, or inlining the action to be performed with the result at the place where the result is identified. Using with_1cc you can express the behavior directly without the need for workarounds. And, again, this comes without any performance penalty since the control flow can be resolved statically and the continuation doesn’t have to be materialized.

In the case where the continuation is not used locally it behaves similarly to non-local returns in language that support that, like Smalltalk. The difference is that where non-local return ties the return to a method call, with_1cc lets you return to an arbitrary expression. Other than that they are completely equivalent.

As mentioned, the syntax of neutrino is flexible and there’s every reason for libraries to introduce shorthands based on this construct that allows it to be used without the full syntactic complexity. This is a basic building block that the base language supports, not something you’re likely to see that often in its naked form.

Update: Kevin Millikin points out that just calling the continuation on exit isn’t enough to ensure that it won’t get called more than once. Kevin’s counterexample is

def get_me_back_in := with_1cc (get_me_out) {
  with_1cc (invoke_me_later) {
    get_me_out(invoke_me_later);
  }
}
print("hest");
get_me_back_in(...);

Here we escape the implicit invocation of invoke_me_later by leaving via a surrounding continuation. Bummer. This issue is present in any language with non-local return that can be captured, for instance SmallTalk:

outer
  | innerReturn |
  innerReturn := self inner.
  ^ innerReturn value: 5.

inner
  ^ [ :v | ^ v ]

(I just tried this in Squeak; you get a BlockCannotReturn exception.)

The solution is to enclose the body of the with_1cc in an unwind-protect that ensure that no matter how we leave the with_1cc, the corresponding continuation will be disabled. Divorcing calling a continuation from disabling it does mean that the name “one-shot continuation” stops being accurate so I’ll probably have to come up with a more fitting name.

One thing I haven’t written about yet are coroutines, which neutrino also supports. Mixing not-really-one-shot-continuations-anymore with those is also interesting but that is a future blogpost.

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.

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.