Which abstraction is best?

[timl]

I can't figure out a good abstraction for my system - all the ones I can think of are flawed in some big way.

This is going to be a long one I'm afraid, so strap in and thank you for reading!

I am writing a game. In this game, the player is challenged to solve various puzzles by placing "devices", connecting them, and programming them (similar to the programming game SHENZHEN I/O).

The devices

Currently, I am thinking of devices like this: a device has a number of ports. Each port is either an input or output port, and you can only connect an input port to an output port and vice versa. Connections between ports just carry single bytes.

A device could be something complicated like a memory component or a full-fledged CPU; or something simple like a signal splitter.

The connected devices are simulated in discrete "ticks", whereby each device performs some logic based on the values of its input ports, and arrives at values for each of its output ports (which go on to affect other devices). Devices can also have an internal state - imagine a "memory" component with "read address", "write enable", "write address", and "write value" ports. At the end of the tick, if "write enable" is nonzero, the value in the "write value" port is stored in memory at location "write address".

I've been working for quite a while now, trying to figure out a satisfying abstraction to allow me to implement this in Rust, but I keep running into problems with every approach I take.

Approach 1: Device is a trait

My first approach was to make a trait, Device, with functions for retrieving the names of the input and output ports, providing values to those ports, and attempting to resolve the internal state of the device once all its input ports had had values provided. (I also went down a massively-overkill route in order to optimise the order that the ports should be evaluated in that involved me using petgraph, a graph data structure library, but I'm pretty sure I'm hugely overcomplicating it by doing that. What can I say, I have a maths background!)

Imagine something like the following:

pub trait Device {
    fn input_ports(&self) -> HashSet<String>;
    fn output_ports(&self) -> HashSet<String>;
    fn output_port_value(&self, port_name: &str) -> Result<u8, Error>;
    fn provide_value(&mut self, port_name: &str, port_value: u8) -> Result<(), Error>;
    fn resolve_tick(&mut self) -> Result<(), Error>;
}

Problem is, I wrote out a bunch of different devices that implemented this trait, and there's a lot of shared code between them. All of them have a specific hard-coded Vec<String> of input and output port names, the input_ports() and output_port() functions just return those vectors, there's error-checking code to ensure the port names provided in later functions are indeed valid port names... in an object-oriented language, I would probably implement this as an abstract base class, but here in Rust land I feel that I'm supposed to be approaching the problem in a different way.

Approach 2: Device is a struct

So, I've started seeing if I can implement Device as a struct instead. Then, my struct can contain the port names, I can consolidate a lot of runtime checks, etc. The different device-behaviours can be implemented by function pointers, or FnMuts that act on the internal state.

Problem is, since there are such big differences in the internal states of the devices (a memory device has a memory map, a simple splitter would have no internal state at all), I was imagining using a generic struct, like this:

pub struct Device<S> {
    state: S,
    input_ports: Vec<String>,
    output_ports: Vec<String>,
    perform_tick: FnMut(S) -> S,
} 

(obviously it would be more complicated than that, but this is just an example).

I run into problems here, because my controller object, which sits at a higher level and facilitates communication between the devices, then can't store them:

struct Controller {
    devices: Vec<Device>,  // Wrong number of type arguments: expected 1, found 0
}

I need to specify the type of the internal state at compile time, but I obviously can't do that because I want to store different devices with different internal states.

It doesn't feel right to make the state then be a trait:

trait State { }

struct Device {
    state: Box<dyn State>,
    ...
}

because

1. state is almost by definition just data with no functionality, which is the opposite of what traits are, and
2. I need to be able to tie the Device's internal FnMut signature to the same type as whatever the internal state is.

So, it feels wrong for Device to be a trait, and it feels wrong for it to be a struct. What's left?

Approach 3: Devices aren't real?

This idea is only half-formed, but perhaps I abstract devices away entirely. Perhaps what I actually have is a bunch of ports, and free-floating functions held in some Controller struct that get executed to mutate arbitrary data. After all, at some point I am going to have to access quite a bit of internal information here... I'm making a game, so I will want to attach quite a bit of other data to these devices - they'll have sprites, the player will be connecting ports together at will, they will want to step through it to debug, so the internal state of each device should be available for inspection... is it possible that I'm making an error by attempting to define this device behaviour completely decoupled from the game engine, and that in fact the engine will have a huge sway over this?

I'm rambling now, but those are my thoughts. I haven't gone into full detail about the devices, so I will attempt to answer questions to clarify extra parts.

Thanks for your help - I've spent a lot of time thinking about this, to no avail!

[jumpnbrownweasel]

@timl

Problem is, I wrote out a bunch of different devices that implemented this trait, and there's a lot of shared code between them. All of them have a specific hard-coded Vec<String> of input and output port names, the input_ports() and output_port() functions just return those vectors, there's error-checking code to ensure the port names provided in later functions are indeed valid port names... in an object-oriented language, I would probably implement this as an abstract base class, but here in Rust land I feel that I'm supposed to be approaching the problem in a different way.

Note that traits can have methods with default implementations which does give you something similar to an abstract base class. Also, shared code can be methods in a different struct (for example, the structs in your trait implementations can be reused) or just plain functions at the module level (this is also common).

[kpreid]

@timl

I need to specify the type of the internal state at compile time, but I obviously can't do that because I want to store different devices with different internal states.

...

It doesn't feel right to make the state then be a trait:

1. state is almost by definition just data with no functionality, which is the opposite of what traits are, and
2. I need to be able to tie the Device's internal FnMut signature to the same type as whatever the internal state is.

You’re almost there: the key is that the trait should define the behavior by its methods and the state by what it's implemented on.

pub struct Device {
    state: Box<dyn Simulate>,
    ...
} 

trait Simulate {
    fn perform_tick(&mut self, /* and probably some kind of “context” argument struct */);
}

struct Controller {
    devices: Vec<Device>>,
}

struct Memory { ... }
impl Simulate for Memory { ... }

In general in Rust, you should think of traits not as abstract superclasses focusing on the data that is stored, “nouns”, but instead as specific operations, “verbs”. We implement a trait to define what “simulate memory” means based on the verb “simulate” and the noun “memory”.

However, I would strongly recommend considering an enum instead:

pub struct Device {
    kind: DeviceKind,
    input_ports: Vec<String>,
    output_ports: Vec<String>,
} 

/// Each variant of this enum holds the state unique to such a device
enum DeviceKind {
    Cpu(...),
    Memory(...),
}

struct Controller {
    devices: Vec<Device>,
}

In general, using enums instead of trait objects makes it a lot simpler to implement things like saving and loading game states.

@timl

All of them have a specific hard-coded Vec<String> of input and output port names, the input_ports() and output_port() functions just return those vectors,

This doesn’t reduce the total amount of code, but if the input ports and output ports are always the same for each device type (no run-time expandable ports) then you might as well use &'static [&'static str] for the port names. Or, you might make an enum for every port name in the game, to reduce the number of string comparisons needed, and make it &'static [Port].

@timl

there's error-checking code to ensure the port names provided in later functions are indeed valid port names...

I expect you’ll find that it’s hard to avoid having error checking code because the connectivity is dynamic. Different designs may have more or less of it, but there will always be something.

[timl]

@jumpnbrownweasel

Note that traits can have methods with default implementations

Ah yes, I did see this - this does help for some of it, but I also wanted to commonise some of the data, although that may not be the right way of thinking about it!

@jumpnbrownweasel

Also, shared code can be methods in a different struct (for example, the structs in your trait implementations can be reused) or just plain functions at the module level (this is also common)

I like this actually, thank you! A little bit of composition - I'll see if I can make that work.

@kpreid

You’re almost there: the key is that the trait should define the behavior by its methods and the state by what it's implemented on.

Your example is fantastic, thank you - but what if the value of the output ports depends on the state? To expand your example a little:

pub struct Device {
    state: Box<dyn Simulate>,
    port_getters: HashMap<String, fn(/* state, input ports */) -> u8>,
    ...
}

impl Device {
    fn port_getter(&self, port_name: &str) -> (fn(/* state, input ports */) -> u8) {
        /* Return a function that takes the state and input ports and computes
           the value of the given output port */
    }
}

trait Simulate {
    fn perform_tick(&mut self, /* and probably some kind of “context” argument struct */);
}

How can I correctly type the functions that are used to perform the computations?

@kpreid

This doesn’t reduce the total amount of code, but if the input ports and output ports are always the same for each device type (no run-time expandable ports) then you might as well use &'static [&'static str] for the port names.

Oh, this is fantastic, thank you. This is something that really bugged me about this, so to be able to do it this way will be really nice.

@kpreid

However, I would strongly recommend considering an enum instead:

@kpreid

Or, you might make an enum for every port name in the game, to reduce the number of string comparisons needed, and make it &'static [Port].

While I would love to be able to do this, I would like it to be possible to add devices without needing to modify existing things - i.e. if I imported this library elsewhere I would like to be able to add my own devices, but if it was an enum I wouldn't be able to do this.

Perhaps that's me asking for too much though!

@kpreid

I expect you’ll find that it’s hard to avoid having error checking code because the connectivity is dynamic. Different designs may have more or less of it, but there will always be something.

No word of a lie, in my exploration of building a control flow graph to represent the connections and dependencies, I found that what I was attempting to do would contradict the halting problem

[kpreid]

@timl

… what if the value of the output ports depends on the state? … How can I correctly type the functions that are used to perform the computations?

The values should be returned by methods of trait Simulate (or a data structure returned by perform_tick() or such).

When you use a trait object, you are choosing that all interactions with the contained data are mediated by the trait (and its supertraits).

@timl

While I would love to be able to do this, I would like it to be possible to add devices without needing to modify existing things - i.e. if I imported this library elsewhere I would like to be able to add my own devices, but if it was an enum I wouldn't be able to do this.

Let me provide you some wisdom from the Rust game-dev corner: if you want to make a game, don't make a game engine. It’s easy to get caught up in writing general abstractions that don’t serve the goal of making the game you want to make. Don’t choose a design for extensibility across crates unless you actually intend to make a reusable library first and a game second.

[parasyte]

@timl

... is it possible that I'm making an error by attempting to define this device behaviour completely decoupled from the game engine, and that in fact the engine will have a huge sway over this?

Hmmmm, I can't say for certain. But I think you're on to something, here.

FWIW, I started writing a "breadboard simulator" in JavaScript a long time ago. And it has a very similar set of requirements: Parts (aka "devices") with any number of inputs and outputs. Users can connect parts in any way, as long as the connections are valid. I.e. input-to-input and output-to-output are invalid. An output can connect to any number of inputs.

This was done as a graph where each Part is constructed with a reference to some other Part's output, forming the connections to its inputs. The whole graph was evaluated from the grounded pins, calling an output() method on the connected output. The theory (I never finished this project, so I have no idea if it works) is that as outputs are evaluated, each Part can update its internal state depending on the value of its inputs. It cannot produce an output until those values have been evaluated, making the evaluation depth-first recursive.

From a data structure point of view, the graph can be defined in Rust as Vec<Rc<dyn Part>> (but petgraph is probably better), where Part is a trait with an interface that is eerily similar to the Device trait you described. (This is probably because it's the natural way to define these kinds of nodes.) Namely, there is a method to list the inputs, and another to list the outputs. There is only one method to produce output, which is an oversight because all of the Parts I created only have a single output.

The biggest difference compared to your Device trait is that your provide_value() method seems to be intended to handle setting outputs, whereas my interface uses graph traversal by calling the output() method on the connected inputs. It's otherwise very close.

Is it ideal though? I'm on the fence about this. Initially I thought this is a sane design. And who knows, maybe it is. In this small sample size, we have two independently produced interfaces with roughly the same shape.

If I had to redesign the system, I think I would try to limit the interface to deal only with a single connection (input-output pair). And this is something that might be related to your approach 3. In short, abstract over edges, not nodes.

A device might have N inputs and M outputs, but that's just N+M connections. It doesn't matter what's on the other side of the connection, the connection itself is the abstraction! For your memory device, it might look something like this:

Rust Playground

I mean, ok. That isn't terrible, but it's difficult to understand. (Then again, all graph structures are challenging.) I cheated a little bit because my Memory device only has one output.

If it was a dual-port memory, it would need two outputs. That can be a separate type representing the connection to its second output port. Maybe struct DualMemoryB(Rc<DualMemory>). Its Connection impl looks a lot like impl Connection for DualMemory but deals only with the second set of ports. This gives you access to both connections via Rc<DualMemory> and Rc<DualMemoryB>.

Now, how does this fit your need for a Controller? Well, Vec<Rc<dyn DeviceTrait>> is one option, and Vec<Device> is another, as discussed above. But I think you probably want to be more rigid about this!

struct Controller {
    memories: Vec<Rc<Memory>>,
    displays: Vec<Rc<Display>>,
    leds: Vec<Rc<Led>>,
    switches: Vec<Rc<Switch>>,
    buttons: Vec<Rc<Button>>,
    // etc.
}

Instead of bundling everything together with trait objects or enums, add everything you know you are going to have anyway. Iterate them separately to call their perform_tick() method (which can either be provided by a trait or inherent). Echoing the wisdom of not over-abstracting everything, the naive thing might be good enough!

And, I know, I'm using a ton of Rc everywhere. Yeah, it's easy mode. You can use a real graph data structure instead, and I would encourage it. But also, don't shy away from interior mutability! It can be an awesome superpower.

[timl]

@kpreid

The values should be returned by methods of trait Simulate (or a data structure returned by perform_tick() or such).

When you use a trait object, you are choosing that all interactions with the contained data are mediated by the trait (and its supertraits).

I think this is why I'm uncertain about this approach - the internal state could be anything, so I wouldn't be able to define any methods on the Simulate trait that return the state because I don't know the return type in advance.

However, I think that perhaps I'm trying to mix-and-match too much between a compile-time and runtime setup! I want to define specific types of devices in code to give me compile-time type checking, but I also want to allow new devices to be created and connected at runtime. I almost certainly can't have both!

@kpreid

Let me provide you some wisdom from the Rust game-dev corner: if you want to make a game, don't make a game engine.

This is an absolutely wonderful piece of wisdom, thank you. I've dabbled in the Rust game dev scene a bit before, I've been using a little bit of Bevy and that's what I'm planning on using for this one!

I think, given this advice, I'm going to use your enum approach - it seems to allow me to have the strict typing I want, and I think I'll find that more valuable than it being open for more modification.

Of course, in my spare moments I'm sure I will continue to daydream about how I would try to do this!

@parasyte

From a data structure point of view, the graph can be defined in Rust as Vec<Rc<dyn Part>> (but petgraph is probably better), where Part is a trait with an interface that is eerily similar to the Device trait you described. (This is probably because it's the natural way to define these kinds of nodes.) Namely, there is a method to list the inputs, and another to list the outputs. There is only one method to produce output, which is an oversight because all of the Parts I created only have a single output.

The biggest difference compared to your Device trait is that your provide_value() method seems to be intended to handle setting outputs, whereas my interface uses graph traversal by calling the output() method on the connected inputs. It's otherwise very close.

Wow, that really is so close!! Yes, I've simplified - my original design had the higher-level object, the Controller, navigate through the graph in dependency order and directly provide the values of the input ports to each device as they were calculated; but my half-written next approach did what you're describing and was going to produce functions for each output that would be passed to the inputs of the other devices, so you would just call the function on the final device and it would recursively call the other output functions all the way down, until the whole circuit has resolved.

@parasyte

If I had to redesign the system, I think I would try to limit the interface to deal only with a single connection (input-output pair). And this is something that might be related to your approach 3. In short, abstract over edges, not nodes.

A device might have N inputs and M outputs, but that's just N+M connections. It doesn't matter what's on the other side of the connection, the connection itself is the abstraction! For your memory device, it might look something like this:

Oh, this is really nice. The connection being the abstraction is a nice move. I definitely do want most of my devices to have multiple outputs, but I can see a solution using composition to solve that - perhaps the output port is the thing that implements the trait, and a device just has a collection of output ports, each of which can depend on input ports and the internal state.

I should have done this earlier, but have a look at what I've already done in my repo - here is my tick() code including my traversal through the graph, and here is a test in the same file showing a number of devices being connected together and working correctly.

Funnily enough, this solution totally works and is fit for purpose, I'm just really not a fan of all the duplicated code across the different devices I've had to create!

Thanks so much both for your advice here, I'm going to have some fun working on this with your input.

[kpreid]

@timl

I think this is why I'm uncertain about this approach - the internal state could be anything, so I wouldn't be able to define any methods on the Simulate trait that return the state because I don't know the return type in advance.

I don't follow this. You say the values of ports are u8, so the method for obtaining the values should return u8. Where does the type of the internal state become relevant?

[timl]

I'm probably thinking about it the wrong way, so I'll try to construct an example.

pub struct Device {
    state: Box<dyn Simulate>,
    /// Mapping from port name to port value
    input_ports: HashMap<String, u8>,
    /// Mapping from port name to a function that evaluates it
    output_ports: HashMap<String, fn(dyn Simulate, HashMap<String, u8>) -> u8>,
    // This is where I think the problem is. How can I properly type each of
    //  the functions to compute the output port values? It has to take the same
    //  type as is stored as state, but it's not possible to enforce that here
    //  without using generics.
}

trait Simulate {
    fn perform_tick(&mut self, input_ports: HashMap<String, u8>),  // I'm aware it's inefficient to pass in an owned HashMap here but this is just an example!
}

impl Device {
    fn perform_tick(&mut self) {
        self.state.perform_tick(self.input_ports.clone());
        // This is fine
    }

    fn evaluate_port(&self, output_port_name: &str) -> u8 {
        output_ports.get(output_port_name)(self.state, self.input_ports)
    }
}

Looking at this example, I suppose it could be possible to instead have:

pub struct Device {
    ...
    output_ports: HashMap<String, Box<dyn Fn() -> u8>>,
}

and have those functions be closures that access the current value of self.state? But I'm not very adept at closures, and this is a bit of a code smell to me.

It's also very hard to construct these examples when I also haven't yet figured out the specifics of how they're going to communicate with each other - it means Device doesn't have a finalised public API, which hampers things.

Realistically it does look like I'm trying to mix and match two different paradigms here. Your enum suggestion feels better than this, because then I get my wish of type safety on the device behaviours and being able to cut down on duplicated code.

However, I think the actual best thing to do is take this idea back to the actual engine I plan on using in the game itself, and rewrite it under that paradigm. Bevy uses an ECS system, and I can see that meshing quite nicely with what I'm trying to do here.

[kpreid]

@timl

    /// Mapping from port name to a function that evaluates it
    output_ports: HashMap<String, fn(dyn Simulate, HashMap<String, u8>) -> u8>,

When you choose dyn Simulate, you cannot have any separate functions like this. All the functions must be part of the trait (or its supertraits).

trait Simulate {
    fn perform_tick(&mut self, input_ports: HashMap<String, u8>);
    fn get_output(&mut self, port_name: &str) -> u8;
}

For efficiency considerations, what I would further suggest here is that ports have numbers internally:

trait Simulate {
    fn input_port_names() -> &'static [&'static str];
    fn output_port_names() -> &'static [&'static str];
    fn perform_tick(&mut self, input_port_values: &[u8]);
    fn get_output(&mut self, port_number: usize) -> u8;
}

This way, you never have to compare a port name string while executing the simulation — only when you handle the wiring-up of devices, you map names to numbers.