Data structures implementation

Radian offers syntax for five types of container data structures: tuple, array, set, map, and object. The tuple is a primitive element, implemented in the compiler backend, but the others must be built up from simpler components. I’ve been thinking a lot about the fundamentals of data organization in Radian lately, therefore, and while I’ve spent a lot of time working on the project, I’ve written little code, all of which I have thrown away.

It’s less the implementation that has been puzzling me – though immutability certainly complicates matters – than the fact that I have to design an API for the whole thing, and API design is hard. Objects, like maps, are associative containers; but how much of the map interface should an object share? How much support should I build in for runtime inspection or mutation of object structure? Should arrays serve double-duty as queues and stacks?

I’m making progress, and I think the next round of code I write may actually stick. I’ve settled on a list of standard containers, interfaces, and method names. Key->value containers like maps and objects will be implemented with red-black trees; ordered containers, like arrays, will be finger trees. Both structures offer O(log n) average performance for lookup, insert, and delete, and both are compatible with immutability.

It’s proving difficult to implement any useful API using only the current set of primitives. I’m thinking of upgrading the red-black tree to become one of the primitives, alongside tuples and closures. Tonight’s project is a persistent implementation in Python, as a prototype for the version I intend to embed in the compiler’s semantics engine.