Sparrow programming language»Blog

Bitcopiable datatypes

I'm still working on the type system. But I find multiple ways of procrastinating. One of them is my work on 'bitcopiable'. And, as this is a good feature, I'm going to drop a few words here about it

The problem

Objects can be self-referentiable. That is, an object, can have a pointer, directly or indirectly to itself. One of the best examples is a node in a circular linked list. The content of the node will contain a pointer that will point to the node itself.

Another example, relatively common, is the following:
datatype Parent
    children: Vector(Child)

datatype Child
    parent: Parent Ptr

Again, a typical Parent object will point to itself. That is what we call a self-referentiable object. An object for which there is a one-to-one mapping between its value and the value of the this pointer.

In general, to be safe, the compiler may assume that all objects are self-referentiable. There are a few exceptions, most notable the primitive types.

As a consequence, for the vast majority of types, the compiler uses pointers to pass objects around. Please see Beyond the type system for more info.

Enter bicopiable

As opposed to self-referentiable types, there are the bitcopiable types. These are objects for which their value are completely independent of the this pointer. We can change their address, but the object remains the same.

There are a few advantages of bitcopiable objects:
  • the compiler can place the object at different addresses, including CPU registers, without invoking any constructors or assign operators

  • we can memcpy or memmove such objects

  • we can maintain ABI compatibility for derived types

  • In general, if the compiler can detect that an object is bitcopiable, it can optimize the code.

    Bitcopiable datatypes in Sparrow

    Recently, Sparrow added a new modifier: bitcopiable. A datatype declared with the bitcopiable modifier is assumes that it can never be self-referentiable, and it allows the compiler to optimize transfer of those objects.

    For example, the compiler can omit the call of copy constructors when dealing with bitcopiable datatypes.
    Another example, a vector of bitcopiable datatypes can directly memcpy its content whenever it resizes. To make this happen, Sparrow has a isBitcopiable(type) function to detect if a type has is bitcopiable or not.

    For generic code, it's also useful that the bitcopiable property is deduced automatically. For this, Sparrow added a autoBitcopiable modifier. A datatype declared with this modifier will be bitcopiable if all the fields are also bitcopiable.

    This is used by standard tuples. A tuple is bitcopiable if all the dependent types are also bitcopiable.

    Bitcopiable support is a very small feature of Sparro, but it can lead to some nice optimizations.
    reminds me of D's struct.

    They can be memcopied around as well but also have a "postblit" operator to turn copies into deep copies.

    Though I don't quite recall how they handled self referential types.