Building Structure

We’ve been hard at work on adding layers to the graphs-as-base-programming concept framework Mosaic, and its editor Grasp. We are building them up as a proof of concept, and first step towards a new perspective at programming in general. For more about the problem we started from, and what the foundation for our solution looks like, we have a blogpost about it right here. Today, however, we’re going to be talking about building structure, both fundamentally and literally.

Early in the development of any piece of complex machinery, it becomes obvious that good communication will be vital. Message-passing has to be clear and intuitive, both for the thing to work, and for people to know how to think about it. Usually, we have a list of message queueing libraries that we’d jump into, but this time was special: we’re building a piece of somewhat ubiquitous software that should be able to underpin any such mechanism and express it in itself, so… could we do all the message-passing within our own system? Turns out: we can!

Queues

We want to have simple queues: FIFO (first-in first-out) data structures that can get data in and then be asked to give it out. We wanted to have this quite deep in Mosaic, so we implemented it as an engine capability over Mosaic itself. Mosaic is a sort of central struct in this space, sort of like a registry for all the types and entities our document knows and can work with. Implementing a new capability is as simple as making a new trait and implementing it:

pub trait QueueCapability {
    fn make_queue(&self) -> Tile;
    fn is_queue_empty(&self, q: &Tile) -> bool;
    fn enqueue(&self, q: &Tile, v: &Tile);
    fn dequeue(&self, q: &Tile) -> Option<Tile>;
}

In a mosaic, a unit piece is a Tile. Tiles are very simple: they are arrow-like, with their three essential parts being their id, source and target. The id part is just a number that uniquely identifies them, and source and target are tiles themselves – the tiles from which and to which this one points. I know it’s weird to have tiles as arrows, but having everything be an arrow actually simplifies many things! Additionally, tiles hold a component and have data that this component owns. So for example, we can imagine a plain tile like this:

Tile { 
    id: 0, source: 0, target: 0, 
    component: "void", data: ()
}

With the source being the same as target, being the same as id, this tile represents an arrow that not only goes back into itself, but is itself too – this is a node-like entity! We call them objects, and they can be made using mosaic.new_object. The void type holds no data, so we don’t get to show off much, but let’s also show the type definition for void, as it’s a predefined type that we have a lot of around:

void: unit;

I can already hear the type-theorists disowning me, but hear me out: the left part is the type’s functional description; the right is it’s structural description. It’s meant to mean that there’s a void in the data, and it itself carries a completely information-less unit value in it. We made it so you can’t assign any of the myriad basic types to a component, you have to give it a functional description: what is THIS unit doing for you?

As you’ll see soon, we’ll be using the following voids today:

mosaic.new_type("Queue: void;").unwrap();
mosaic.new_type("QueueSentinel: void;").unwrap();
mosaic.new_type("ToQueueSentinel: void;").unwrap();
mosaic.new_type("Enqueued: void;").unwrap();

Our queue will be a queue with a sentinel, meaning that there’s a special element that marks the end of the queue, while the queue itself marks the beginning. That explains the first two types – Queue and QueueSentinel. The ToQueueSentinel is a component we’ll use to mark the arrow going from the queue to the sentinel, to be able to find the sentinel quickly at any time. Tiles being arrow-like allow us to not have two concepts (like nodes and arrows), but instead to work with just tiles for anything. An arrow is the most modest kind of tile – it has distinct id, source and target, meaning it’s itself neither of them, but connects some other two tiles. So what is a queue?

fn make_queue(&self) -> Tile {

    let que = self.new_object("Queue", void());
    let sen = self.new_object("QueueSentinel", void());
    self.new_arrow(&que, &sen, "ToQueueSentinel", void());
    self.new_arrow(&que, &sen, "Enqueued", void());
    queue
}

We create two tiles, one carrying the Queue component, and one with QueueSentinel. We make two arrows between them – both going from queue to sentinel, one marked ToQueueSentinel and one marked Enqueued. We already talked about what ToQueueSentinel means, but what is the other one?

We’ll simply be marking any additions to the queue as Enqueued. This way, we’ll be building up a chain like this:

queue --Enq--> v1 --Enq--> ... --Enq--> sentinel

An empty queue, as we can see if we turn the current state of things into a dot diagram is like this:

Let’s explore how to traverse the Mosaic now. Querying tiles can be done in many ways, but it’s almost always something like this:

queue
    .iter()
    .get_arrows_from()
    .include_component("Enqueued")
    .get_targets()
    .next()

In this example, queue is our tile that represents the queue. We start fishing for things by turning it into an iterator, and it stays an iterator for as long as we need it to be informative about its surroundings. Here, we get all the arrows that go from it, we filter those that include the Enqueued component, find those arrows’ targets and get the next one in the iterator. This operation returns a tile that is the target of an arrow marked as Enqueued, starting from the end of our queue and heading out towards the sentinel. We’ll make this into a helper function called get_next. We’ll similarly build several other helpers, like get_sentinel and get_last and it’s no more complicated – we might use get_arrows_into instead of get_arrows_from or search for sources instead of targets, but it’s all the same deal. One day soon, we won’t have to write this and I’ll just be able to drop a picture here that points to relevant arrows, but we’re not there yet.

So let’s enqueue something now. To do this, what operations need to happen? We need to start with a queue, and we need to have an element to add to it. Once that’s done, we want to get the next element in our queue from the start of it and insert the new element before that one. This is a common thing programmers learn to write in their education – we need to have some pointers and have them reconnected in a certain way:

before: a, queue --Enq--> next
after:  queue --Enq--> a --Enq--> next

It’s not in the textual image, but the arrow between queue and next should be deleted once a is in. It’s truly hard to draw non-linear images in text, who knew.

Our enqueue method looks like this in Mosaic:

fn enqueue(&self, q: &Tile, v: &Tile) {
    if let Some(que) = q.get_component("Queue") {
        if let Some(next) = self.get_next(q) {
            let old_arrows = self.get_enqueued_arrows_into(next);
            self.new_arrow(&que, v, "Enqueued", void());
            self.new_arrow(v, &next, "Enqueued", void());
            old_arrows.delete();
        }
    }
}

So let’s talk about the obvious thing: we are very structurally-inclined. We have implemented the most barebones of barebone enqueueing operations here, and there’s no semantics about anything about it: it’s untyped (or rather heteronomous), can accept any tile into it (yes, even an arrow), but it’s exactly the right queue operation.

Here’s what the graph looks like after enqueuing:

We can now see the utility of the ToQueueSentinel arrow: we can quickly access both sides of our structure. As for the added element (the x|4|void|{} thing in the middle right, x means it’s an object, 4 is the id), we can see it connected, with Enqueued arrows running both in and out. If we add a new element to the queue now, the algorithm would start from the queue (top), find next to be equal to tile 4, erase the arrow between them (0 > 4|5|Enqueued|{}), add the new element in, link it up, done!

When dequeueing, we know what to do: find the last element, find the one before that, connect the one before to the sentinel, cut the last element out and return it. So here goes:

fn dequeue(&self, q: &Tile) -> Option<Tile> {
    q.get_component("Queue").and_then(|queue| {
        let end = self.get_sentinel(&queue);
        self.get_last(&end).and_then(|prev| {
            if prev != queue {
                self.get_before(&prev).map(|before| {
                    self.get_enqueued_arrows(prev).delete();
                    self.new_arrow(&before, &end, "Enqueued", void());
                    prev
                })
            } else { None }
        }
    })
}

With these two operations, we can call this queue done: we have a way to tell if it’s empty by simply seeing if dequeue returns a None.

We put it to good use immediately and after ironing out some issues with regards to structural integrity (when you work with multifaceted graphs, one of the most common problems is not having enough safety filters), it’s now at the core of our editor, passing along requests for UI update between otherwise unconnected bits, and it’s in the foundation. This makes all the difference when imagining a clean setup at different scales and for different options: you’re building this structure either way, might as well build it using the most generic, visual tool!

What does that look like? Well, it’s hard to describe but you add a refresh_request_queue: Tile to your structures, to begin with. You initialize it with the make_queue function we made above. Then, when you update the editor, you call the dequeue function and do… something! What you do is up to you, really. You can be as type-safe as you wish, you may check structural things, it’s all in your grasp, pun intended.

The Big Picture

Being able to debug a data structure in a visual way like this is a treasure I didn’t know I was missing all this time. All of the data from Mosaic is exportable as a graph in dot at any time. All the identifiers are unique, and for now, they don’t repeat, so snapshots are really easy to get. Using a quick ECS system that does graphs well as a setup for your software is not a thing that’s easy to sell, but it is there at the end – the big picture, quite literally. Our editor, Grasp, is aiming to be the tool that will both make use of Mosaic (as it currently already is), and replace the need to have static dot images: it’s an editor whose functionality is drawn right into it, with only a few exceptions. The name itself is a jab at how Autocad uses Lisp to build tooling based on a very wide and programmable basis. Lisp is a list processing language and lists are the simplest of non-trivial graphs. We offer even more than that by using graph pattern matching, traversals, and more. Imagine what we can achieve with that, because we want all of those ideas! We’re not stuck on drawing graphs. We see the uses in making game development faster and more safe, making dependency managers fully picturesque, creating batch files that don’t suck, processes that can wait for you instead of failing, AI whose internal networks we can look at and investigate, category theory proof assistants, and more! Honestly, it sounds so fun that we’re going overboard with our own personal securities to bring this into the future. If you want to help this goal, reach out, let’s talk! After all, networking is a core piece of our technology.