Notes on Bedquilt's world model

I’ve had in mind from the beginning that Bedquilt’s world model was going to be represented by an in-memory graph-structured database. I was originally hoping to be able to grab one off the self, but after hunting around on crates.io I couldn’t find anything quite right, so I’m just going to write one that has all the features I want and none that I don’t. What follow are some preliminary design notes for it. Nothing here is implemented or rigorously specified yet.

Although Bedquilt targets Glulx, it isn’t going to rely at all on Glulx’s game-state instructions (save/restore/undo/etc). This keeps the door open for eventual support for native compilation or compilation for other VMs that don’t provide similar functionality. Part of the database’s job is to handle these things. A dump of the database will comprise Bedquilt’s save format, and the database will provide space efficient checkpoint-and-rollback functionality to support undo.

There are four sorts of things that can be contained in the database:

  • A value is a simple datum such a number or a string.
  • An entity corresponds to what other systems might call an object. On its own, it is represented just by an opaque ID that is distinct from the ID of each other entity.
  • A property is a binary relation from an entity to a value.
  • A relationship is a binary relation from an entity to another entity.

If your game includes a white house west of an open field, this might be represented in your database by two entities, two instances of a “name” property which relate one entity to the value “white house” and the other to the value “open field”, and one instance of a “west” relationship which relates one entity to the other.

The sources for your game will include one or more .bqs files which define a database schema, and a .bqd file containing data which conforms to that schema and defines your initial game state. .bqs files should be largely reusable from one game to another and can have ecosystems built around them, while pretty much everything in the .bqd file will be unique to your game. Bedquilt will include a code generator which translates .bqs and .bqd files into Rust code. The .bqs file will be translated into types and traits which correspond to the schema with CRUD methods that enforce and guarantee data integrity, while the .bqd file will be translated into a big long function that you can invoke to populate your database at the start of new game.

Within the schema language, you can define classes to which entities belong. These classes can be used as constraints on the domain and range of relationships, and the domain of properties. Classes can multiply inherit from each other, and every class descends from the built-in class any. Properties and relationships can also have cardinality constraints. To define a class named Room and a require that the west property relate a room to at most one other room, you would write

class Room;
relationship west : Room -> one Room;

one is the only cardinality keyword syntactically allowed here, and means “at most one” as opposed to “exactly one”. If the keyword were omitted, a room would be allowed to have any number (including zero) of rooms to its west. If you want a property or relationship to be required, you have to specify that as part of a class definition. For example,

property name : any -> one String;
class Room has name;

specifies that while any entity is allowed to have a name (but can have at most one of them), a Room is required to have one.

Properties and relationships are immutable by default. You can change this by adding the mut keyword to their declaration, or make them mutable only when applied to specific classes by specifying that in the class definition. However, once you’ve made something mutable, its cardinality becomes frozen and subclasses can’t add any more cardinality constraints, since those could get violated if you mutated something through a superclass.

A .bqd file matched to a schema like the above could look like this:

entity field : Room {
    name = "Open Field",
    west = house
}

entity house : Room {
    name = "White House"
}

When the schema is compiled, it’ll produce a Rust module containing code such as this:

pub trait Name {
    // The trailing underscore is a naming convention for optional properties.
    fn name_(&self) -> Option<&str>;
}

pub trait HasName : Name {
    fn name(&self) -> &str;
}

// `Entity` is a type built into the core database engine. It takes a
// lifetime parameter because it holds a borrow on the database itself.
impl Name for Entity<'_> { ... };

/// A newtype wrapper.
struct Room<'a>(Entity<'a>);

trait West {
    fn west_(&self) -> Option<Room<'_>>;
}

impl <'a> From<Room<'a>> for Entity<'a> { ... }
impl Name for Room<'_> { ... }
impl HasName for Room<'_> { ... }
impl West for Room<'_> { ... }

This shows the basic idea of how you can traverse your world graph one node at a time. Of course there will also be operations for creating new entities, and for mutating any properties or relationships declared mut. Where the database gets interestingly powerful is that you’ll also be able to operate on sets. Operators will be provided to:

  • Get the set of all entities belonging to a particular class.
  • Compute the union, intersection, or difference of sets.
  • Invert a property or relationship (“find everything in the database whose name property is anything in this set”).
  • Filter a set according to a predicate (“retain elements of this set whose lit property is true”).
  • Map a property or relationship over a set (“give me the set of all rooms that are west of any room in this set.”)
  • Find the transitive closure of such a map (“find all rooms that are reachable by going west repeatedly”).

Fans of Dialog should be pleased by the observation that, with the inclusion of the transitive closure operator, queries written in this algebra closely resemble logic programming — c.f. Datalog. In contrast to Dialog, however, you’ll have this query facility embedded within a multiparadigm language rather than it being your entire language. Consequently, you can use it when it’s a natural fit, and just write imperative code when it isn’t.

4 Likes

I can see how this works as far as developing a simulationist world-model works. A lot of IF authoring is about adding exceptions, though; the sort of thing where in Inform you can write:

Instead of taking the dog when the player does not carry the doggy treats: say "The dog looks at you distrustfully and refuses to be picked up."

Where does that fit into this design? In a separate file of Rust code that sits alongside what’s auto-generated from the .bqd?

Yes, exactly. The database is all about keeping track of nouns and adjectives and providing primitives for mutating them. Anything to do with verbs — deciding what mutations they should trigger and what should be seen by the user — anything that in Informese would be handled by a rulebook — lives apart from this and probably won’t need a DSL, just a regular library crate.

You’re welcome to copy the graph library from my sharpee repo and see if does what you need.

It’s C# but the gist should be reusable.

Rust’s ownerhip model makes translating OO designs for datastructures…um…challenging. Probably better off with a bespoke rust design.

2 Likes

Do you have an example of what this looks like? Rust APIs live and die by their ergonomics so I would love to see how clean it’s possible to make it.

The rulebooks? No. I’m several months away from being ready for that.

I would dispute that this is broadly true, but it is here. In the C# code, every node contains references to the edges which connect to it and every edge contains references to its source and target nodes, so a cyclic graph has loops of references. In a GCed language that’s fine but if you do this in Rust with reference-counting you’ll leak memory. The standard way of dealing with graphs in Rust is to use a swizzled representation where nodes and edges are identified by indexes rather than pointers.

1 Like

This is the kind of thing I was referring to: cyclic references, or structures which hold references to parts of themselves. Using indexes over references solves some of it, but not everything. It’s not that rust is generally harder, although sometimes it is, but that it is different. I prefer Rust, although I do a lot of programming in both C# and Rust. C# was my favorite language until Rust rolled into town.

1 Like

So, life has intervened and I’m a few weeks behind on where I’d hoped to be on Bedquilt development, but I thought I’d share a small update on where development of the database engine is headed.

I’ve spent some time exploring database paradigms other than the one discussed above, in particular whether an entity-componenent-system paradigm would be more suitable. An ECS database uses basically the same entity concept that I do, and its “components” are my “properties”. In general it lacks relationships, but some implementations bolt them on. What an ECS has that a graph database lacks is the notion of a system. My conclusion is that, for interactive fiction, systems are not a useful addition. They’re handy for games which have physics engines, requiring high-performance parallelism over lots of similar objects, but IF generally doesn’t need anything like that. On the other hand, relationships are pretty important in IF and deserve first-class treatment. So, I’m sticking to the graph paradigm.

When I talked about what kind of set operations will be supported, I left off an important one, which is the join operation. You’ll be able to work not only with sets of entities but with relation sets, that is, sets of pairs of entities. The join operation will take a set X : (A,B) and a set Y: (B,C) and return set Z : (A,C) defined by { (a,c) : ∃b. (a,b) ∈ X ∧ (b,c) ∈ Y }.

I’ve decided against having separate .bqs and .bqd file formats. Everything will defined using a unified file format, with six types of top-level item:

  1. super items, which declares other schemata that this one inherits from.
  2. class items, as discussed originally.
  3. relation items, which combine the relationship and property items discussed previously. Properties vs. relationships will still be distinct things for some purposes, but it turns out that it probably won’t be necessary for the parser to distinguish them.
  4. entity items, which do what I previously described as being done in a .bqd file.
  5. use items, with the same syntax and meaning as in Rust. To use a class or relation identifier you have to also inherit from the schema which defines it, but other things like constants and types that properties range over can come from any crate.
  6. table items…

Tables are basically a way of including non-serializable data in a database. The motivating use case for them is dynamic rulebooks. Entries in a rulebook have to resolve to function pointers, but serializing function pointers is brittle and unsafe. Tables map stable identifiers to arbitrary Rust constexprs (such as function pointers). You can define a table in one schema and then other schemata which inherit from it can add or replace entries. What comes out of the schema compiler will be, for each schema which defines or extends a table, a trait definition containing a bunch of constructor methods for every entry the table should contain, and then for the final concrete schema associated with your game, an entry type which implements all those constructor traits plus Into<Foo> where Foo is the type that table entries should resolve to. Internally, this will be a newtype wrapper around a usize so that .into() is just an array lookup.

I checked the parser for the schema language into the Bedquilt repo a couple weeks ago, and I’ve started working on the runtime library. I’ll post another update when that piece is done.

2 Likes

Dang, there goes my idea of IF involving a room with hundreds of ping pong balls and mousetraps.

1 Like

Sounds like a much more user-friendly version of what Glulx is doing with rocks!

Kinda. As I discussed at the top of this thread and in Glk: Now with green threads! (Bedquilt progress update), the exact thing that rocks were created for is handled by just not using Glulx’s game-state instructions at all and therefore not having to worry about sudden evaporation of your Glk state. But all the inherent complexity of tracking/saving/restoring game state still has live somewhere and that’s what this database is about. Tables perform a role loosely analogous to rocks in that they swizzle an unstable pointer into a stable index.

Have you looked at the Hexastore (PDF) strategy for graph data storage/lookup?

I think a hexastore is a bit overkill. In particular the SOP and OSP indexes are unlikely to ever be useful enough in Bedquilt to justify the cost of maintaining them. What I’m doing basically amounts to maintaining the other four of the six indices, using the slotmap crate for fast and compact indexing by entity ID.

Not much visible progress here in the past several weeks, but I promise there’s been progress! It’s just been on the design front rather than the coding front. In parallel with ironing out the details of Bedquilt’s database design I’ve been writing a game in adv3lite in order to mine it for good ideas and push the system to its limits. I’m hoping thereby to develop a clearer plan for what I want the higher-level pieces of Bedquilt to look like, in service of making better design decisions for the database component. These are decisions that really need to be made well on the first try because there’s going to echo through everything else.

Meanwhile, I’ll continue with my crimes against nature involving enterable, closeable, variably-transparent complex containers in dark rooms, and spamming @Eric_Eve’s bug tracker with the results :-).