0 Replies Latest reply on Jun 11, 2004 11:49 AM by 843853

# Dynamic Structures as Part of a Language

Hi,

I hope I've got the right group for this! I've been a professional software engineer for about 8 years, and I've always tried to concentrate on design principles. I've written a few compilers and a simple VM, and partially designed a new language, and after a while I began to have a few ideas about stuff.

One of the things a came to realise was that I think it is possible to design anything in terms of dynamic data structures (for example, tree-like structures) using only a vector, set, and map.

To me, these three items provide a full complement of tools needed to build most (if not all) dynamic structures. I think they are so important, that they are almost fundamental to a modern language.

Now, clearly there are some situations where it may be more useful to use a linked-list, or I'm sure there are some other specialist data structures that we could think of to solve particular problems, but I think that in 99% of design cases these types will suffice, and infact they have for me, in my experience.

My idea was to actually make these data structures part of the language, just like arrays, say. A possible notation/syntax might look something like this:

Declarations:

{int} m_mySet;
[int] m_myVector;
[int->String] m_myMap;

Simple usage:

int i = m_myVector[j];
m_myVector += 3; // Add to the end.
m_myVector += m_myVector; // Concatenate.
String s = m_myMap;
boolean b = m_mySet.contains(i);

There is also a little inheritance hierarchy:

A vector is a set.
A map is a set.
A [int->T] map is a vector (where T is some type).

So you could have:

boolean contains({int} is, int i)
{
return is.contains(i);
}

...and then do...

[int] is = {1,2,3};
boolean b = contains(is,1);

...fairly obviously.
You could also intermix types easily, so you could add map elements to a set with just:
{int} sis;
[String->int] mis;
sis += mis;

There could be VM instructions/optimisations for all operations associated with these three structures.

Obviously there is a lot more design work that needs to be put in, but the principles of what I'm talking about are the use of these three structures as fundamental parts of the language.

For those who have used functional languages, I'm sure you'll see some similarities in these ideas.