Wednesday, October 14, 2009

undef

I implemented the "undef" keyword, and I am actually finding it quite useful. What undef does is to undefine a member definition that would otherwise be defined automatically. Originally I had planned on using this to remove inherited methods (it replaces the vtable entry with one that simply throws an exception), however I am also finding it quite useful for undefining the default constructor - that is, if you have a class which can only be produced via some external entity (such as a library), then you can undef the constructor which will prevent the compiler from creating a default constructor for that type. For example, all of the reflection types, which are only creatable by the compiler, have undefined constructors.

Explicit Implicitness

Thinking more about implicit type conversion.

I noticed that Wikipedia's article on type conversion states that the term "coercion" means implicit type conversion. This didn't exactly sync up with my understanding of the term, but I certainly could be wrong. Actually, I hope Wikipedia is correct, as it solves a difficult problem for me - what to name the type conversion method. In accordance with my general policy on naming, I don't want to steal commonly used names like "convert" and give them special meaning. The term "coerce" is just esoteric enough that I don't feel quite so bad about reserving it.

I've also decided to diverge from C++ in one important respect: In C++, a constructor with a single argument implicitly acts as a conversion function, unless you opt-out by declaring it explicit. I would prefer to opt-in rather than opt-out. In fact, I'm thinking of divorcing implicit conversions from constructors entirely.

In other words, you have to explicitly declare your implicitness :)

My thought at this moment is that implicit conversion is enabled by declaring a static member function named "coerce" that takes an input argument of the value to be converted, and produces the converted value. Although the declared return type of the coerce method must be the same as the class in which it occurs, the *real* type of the object can be a subclass or any compatible type.

Thus, we can implement auto-boxing by declaring the following methods in class Object:

   static def coerce(value:Object) -> Object { return value; }
   static def coerce[%T] (value:T) -> Object { return Boxed[T](value); }

We want to only box values which aren't already derived from Object. Unfortunately, I'm not sure that the above will work - that is, given a subclass of Object, I am not sure which method the overload resolver will choose. I might have to implement qualifiers on the pattern variable in order to get this to behave as expected.

Auto-stringification can also use the coerce() technique:

   static  def coerce(value:Object) -> String { return value.toString(); }

For the moment, I'm going to limit the use of "coerce" by requiring it to be a member of the class that you are coercing to. I may relax this restriction later, if it proves to be necessary.

Tuesday, October 13, 2009

Progress: Reflection

A small sample of some working code that uses reflection:

def testFindMethod() {
  let m = Module.thisModule();
  let f1 = m.findMethod("sample");
  Debug.assertTrue(f1 isa Method);
  let f2 = m.findMethod("ample");
  Debug.assertFalse(f2 isa Method);
}

def sample() {}


What this code does is to get a reference to the current module, and look up a method named 'sample'. Note that the reason for the funny 'isa' tests is because I haven't completely worked out the issues surrounding NULL pointers yet.

I also plan to support getting the module pointer for a type via "Module.of(typename)", however that isn't done yet. For one thing, the compiler does not yet support passing a type name as a function argument. My eventual plan is to implicitly convert type names into instances of TypeLiteral[typename] whenever they are used as values. In other words, types are not objects -- but you can use them like objects in most cases.

The next step is to be able to call a method via reflection. In order to do this, however, I will need to work on boxing of primitive types, since the "invoke" method takes an array of Object[]. I've started working on this already. At this point, the "Boxed" class is pretty simple:

/** A reference type used to contain a value type. */
class Boxed[%T] {
  let value:T;
  
  def construct(value:T) {
    self.value = value;
  }
}


So for example, you can create a Boxed integer via "Boxed(3)". However, it will be more convenient once I support "auto-boxing", which is the ability to implicitly convert a value type into a boxed type as needed. So for example, if I have a method that takes an argument of type "Object", and I pass it an integer, it will automatically wrap it in a Boxed[int].

The issue I need to resolve is whether auto-boxing should be a special feature of the Boxed type. The alternative is to implement user-definable implicit conversion operators as in C++, so that any class can potentially define a silent conversion from one type to another. While this is a powerful and useful feature, it it also one that is easily abused.

Sunday, October 4, 2009

type Memory.Address

One of the challenges in the design of Tart is reconciling two competing goals:
  • The desire to make Tart a "safe" language, in the sense of not allowing invalid pointer accesses and such
  • The desire for efficiency and the ability to get "close to the metal" when needed.
There is also a third goal which depends on the second: That the Tart core libraries be written in Tart to the maximum extent possible. Since many of the core library functions require low-level access to the hardware, this means that there has to be some means to express that within Tart.

The route that I have chosen is inspired by C#, which is to have a "safe" subset of the language that is used normally, and an "unsafe" set of language extensions which give more direct access.

One question to be asked is: What keeps a programmer from enabling the unsafe language extensions always? As much as any competent software engineer may be dedicated to the principle of writing reliable code, there is always the temptation to take shortcuts, especially when faced with short deadlines.

My approach is to design the language so that such shortcuts are gently discouraged but not prohibited. In particular, there are a couple of speedbumps:
  • The ability to enable unsafe language extensions is done via a command-line switch to the compiler, rather than in code. This means that turning it on requires modifying build files.
  • The unsafe language extensions have been designed such that their syntax is deliberately verbose. (Actually, it would be more accurate to say that when it comes time to dole out the limited number of available syntactical shortcuts to various language features, the unsafe language extensions are last in line.) Thus, a native pointer is declared as "NativePointer[type]" rather than the more convenient "type*" or "type^".
In my initial design, I had two types for dealing with raw memory: NativePointer and NativeArray. NativePointer represented a C style pointer, except without the ability to do pointer arithmetic. NativeArray represented a C style array of fixed length, with no range checking.

However, as I have been working on creating the core libraries, I realized that these two types are too limiting. In particular, there are a lot of low-level functions that deal with ranges of memory of varying size, which were hard to express with the two native types. Up to this point, I had been using NativePointer[NativeArray[type, 0]] to represent the start of a range of memory, but this was both cumbersome and incorrect.

So I have added a new native type, whose full name is "tart.core.Memory.Address". ("Memory" is a module that contains a set of utility functions for dealing with memory - it's the primary source of "unsafe" operations dealing with memory access.)

Semantically the "Address" type is just like NativePointer, except that it also allows array element dereference like a C pointer: data[index]. Although array element dereference implicitly involves pointer math, It does not allow arithmetic operators - for example getting the Address of an array element is done via Memory.addressOf(array[index]). (Memory.addressOf() is an intrinsic that is equivalent to C's '&'.)

However, the real difference between Address and NativePointer is in the connotation. "Address" is meant to represent a *boundary* rather than a pointer to an element. Two such boundaries, or a boundary and a length, define a range of memory.

As an example of what this allows, the UTF8 decoder class initially had a "decode" function that looked like this:

  def decode(dst:char[], dstIndex:int, src:ubyte[], srcIndex:int, count:int) -> int;



However, that decode function is now written using this to do the actual work:

  def decodeRaw(dst:Address[char], dstLength:int, src:Address[ubyte], srcLength:int) -> int;


There are a number of advantages to doing this:
  • Classes such as String which contain an internal buffer of characters can call decodeRaw without having to convert their buffers to an array object.
  • Range checking is done once in the higher-level function, rather than checking the range on each element access individually.
Of course, there is always the possibility of a bug in the "unsafe" code which would have been caught if I had restricted myself to the slower but safer language subset.

My response to that is that the use of "unsafe" language extensions should be restricted to a small number of modules which are subject to additional scrutiny.

--
-- Talin

Tuesday, September 8, 2009

ArrayList

The compiler is getting to the point where I can start to sketch out some of the basic container classes. Here's what the ArrayList class looks like:

import tart.core.Math.max;

/** Array-backed list type. */
final class ArrayList[%ElementType] : List[ElementType] {
  private {
    var data:ElementType[];
    var _length:int;

    def grow(amount:int) {
      let nlength = self._length + amount;
      if data.length < nlength {
        let ndata = ElementType[](nlength + nlength / 2 + 16);
        ElementType[].copyElements(ndata, 0, data, 0, self._length);
        self.data = ndata;
      }

      self._length = nlength;
    }
  }

  def construct(data:ElementType...; initialCapacity:int = 0) {
    initialCapacity = max(initialCapacity, data.length);
    self.data = ElementType[](initialCapacity);
    ElementType[].copyElements(self.data, 0, data, 0, data.length);
    _length = data.length;
  }

  def construct(data:Array[ElementType], initialCapacity:int = 0) {
    initialCapacity = max(initialCapacity, data.length);
    self.data = ElementType[](initialCapacity);
    ElementType[].copyElements(self.data, 0, data, 0, data.length);
    _length = data.length;
  }

  def add(e:ElementType) {
  }

  def [index:int]:ElementType {
    get {
      Preconditions.checkIndex(index >= 0);
      Preconditions.checkIndex(index < _length);
      return data[index];
    }

    set {
      Preconditions.checkIndex(index >= 0);
      Preconditions.checkIndex(index < _length);
      data[index] = value;
    }
  }

  def length:int {
    get { return _length; }
  }

  def iterate -> Iterator[ElementType] {
    return ArrayListIterator(self);
  }

  private final class ArrayListIterator : Iterator[ElementType], HasLength {
    private var list:ArrayList;
    private var index:int;
   
    def construct(list:ArrayList) {
      self.list = list;
      self.index = 0;
    }
   
    def next -> ElementType or void {
      if (self.index < self.list.length) {
        return self.list.data[self.index++];
      } else {
        return;
      }
    }

    def length:long { get { return list.length; } }
  }
}

Template Parameter Inference

I made some more good progress this weekend - the compiler can now deduce the template arguments of a class from the parameters of a static method of the template. To give an example:

public final class Array[%ElementType] : Iterable[ElementType] {
  // A function which takes a variable-length list of arguments and
  // returns an array of those arguments.
  static def of(elements:ElementType...) -> Array;
}

def test() {
  let a = Array.of(1, 2, 3);
}
As you can see in the example, the type of the array is deduced from the arguments to the static method 'of'.

Having got this working, I've now implemented array literals - so [1, 2, 3] is merely syntactic sugar for Array.of(1, 2, 3).

The reason for doing it this way is that my type inference engine works on function calls - it tries to find a common ground between the parameters of the function and the arguments of the call, binding template parameter substitutions and adding implicit casts as needed. While I could extend the engine to work on other kinds of language constructs, that would make it more complicated - it's much simpler to transform the other language constructs into function calls. Fortunately, pretty much everything can be transformed into a function call. Thus there is no special logic for, say, arithmetic operators to insure that both terms are promoted to the least common type - instead, we just convert arithmetic operators into function calls, and let the overload resolution process do it's work.

Of course, once the type resolution is done, many of those calls will be replaced with code that is generated inline, so it's not like we are paying any overhead for this.

Tuesday, August 25, 2009

The 'classify' statement


I've implemented the 'classify' statement in the Tart compiler, which is similar to a switch statement, except that it switches based on the type, rather than the value of an expression.

Here's an example:

let e:Object = "H";
classify e {
  as s:Exception { /* do something with 's' */ }
  as a:int[] { /* do something with 'a' */ }
  else { /* 'e' is some other type. */ }
}
There is also a 'short form' which handles a single type test:
classify e as s:String { /* do something with 's' */ }
The classify statement works with both reference types and union types.