How to simulate logic gates in Elm?

[AlienKevin]

Hi, I’m having trouble simulating electric circuits based on logic gates in Elm. Here’s my current model:

type Gate
  = CompositeGate
    { name : String
    , inputs : List Pin
    , outputs : List Pin
    , parts : List ConnectedGate
    }
  | BuiltInGate
    { name : String
    , inputs : List Pin
    , outputs : List Pin
    }


type alias ConnectedGate =
  { inputs : List Connection
  , gate : Gate
  }


type alias Connection =
  { from : RangedPin
  , to : RangedPin
  }


type alias RangedPin =
  { name : String
  , from : Int
  , to : Int
  , value : Int
  }


type alias Pin =
  { name : String
  , size : Int
  , value : Int
  }

The place I got stuck is when writing an event emitter in Elm. I want to trigger a change event on input changes and make outputs listen to change events and set their values accordingly. I found elm-event-emitter but it uses effect manager and is in 0.18.

So I went with the JS ports approach and tried to use node.js’s events library. However, I can’t directly set the output value once the change event triggers the listener because I can’t pass in an elm function to js. So I decided to pass in id of inputs and outputs and send the new output value along with the two ids to Elm as a Subscription when a change event is detected. On the Elm side, I have to search among the pins that matches the id and update it. BTW, I reference a JS circuit simulation library.
Here are the ports:

var emitter = require('events').EventEmitter;
    var em = new emitter();
    var app = Elm.Main.init({ node: document.querySelector('main') });
    app.ports.triggerChange.subscribe(function([pinId, newValue]) {
      em.emit("change" + pinId, newValue);
    });
    app.ports.listenToChange.subscribe(function([fromId, toId]) {
      function listener(newValue) {
        app.ports.setPin.send([fromId, toId, newValue])
      }
      em.on("change" + fromId, listener);
    });

My current approach seems very complicated and inefficient. Plus, the model I used is also a bit awkward. Can someone help me find a better way to simulate logic gates in Elm?

[Sebastian]

I don’t follow why this needs to use ports. Do you need to interact with something external? Why not send the change using the Elm architecture via update?

[AlienKevin]

I can’t believe that I missed this. However, the main reason why I first think about the event handler is performance. If I have hundreds of pins and want to precisely update others if one changes, what persistent data structure should I use?

[jxxcarlson]

Here is the approach I would take. First, define something like

type alias State = { circuit : List Gate, time : Int }

Here time is discrete. Then rig up a function

nextState : State -> State

This business where you iterate State -> State is a dynamical system – a very general pattern in math, physics and CS. Here is an example of how that works in the Microbial Life app that I refer to below: see line 92

Put a State in your model, initialize it using init, and use update to (a) step forward on time unit at a time on button push, or (b) if the run button is pushed, repeatedly apply nextState. Finally, rig up a view function for State. Given what you have already done in your electric field simulator, you should have no trouble doing that.

I’ve used this approach in various projects, e.g, Microbial Life. I wrote a little article on this on Medium. The code is on GitHub.

I really like your electric field simulation.

PS. It may be that you want to have Rust carry out what amounts to the nextState function, in which case the above is irrelevant. I’d be inclined to try a pure Elm solution first. I’d be very interested to know how that works (and to play with the app). It might be worth benchmarking an Elm solution with 10, 20, 40, etc. gates to see how things scale. I use this package. It is often the case that one can do significant optimizations to improve performance. I wrote a little post on that a while back.

[AlienKevin]

Thanks a lot, I will give it a try.

[Philipp_Krueger]

Hello @AlienKevin!

My request is kind of off-topic, but out of personal interest: Why are you trying to simulate logic circuits in Elm?

The reason for my question is that I’m currently experimenting with a logic circuit editor (and simulator), similar in spirit to Logisim, because Logisim is unfortunately discontinued and I can’t seem to find any good alternatives.

I’d love to hear about what your use-case is and what features you’d like to see from such an app.

Here is a work in progress screenshot of this app:

[AlienKevin]

Hi, your app looks cool! I saw a similar circuit design tool here which you may want to take a look.

As for why I’m trying to simulate circuits in elm, it’s mostly because I’m taking an online course called Nand to Tetris on Coursera that teaches people how to build a modern computer from scratch. The first part of the course is about constructing digital circuits using logic gates where I created a CPU using a simplified Hardware Description Language (HDL). The simulator provided by the course has an ancient UI, not very flexible, and is written in Java.

However, I did become extremely interested in simulating and designing hardware using the software. Being interested in functional programming, I did some research and found a Haskell compiler called Clash which allows you to compile from Haskell to HDLs like VHDL and Verilog. I haven’t tried it out because it looks too complicated (outside of my beginner EE knowledge) but I love the concept and want to experiment with an elm-like HDL that directly runs in the browser. My end goal is to construct an entire computer that runs in the browser, mostly for fun and possibly as an improved version of the Nand to Tetris course.

I’m really interested in how you run the simulator as that is currently my biggest obstacle.

[Philipp_Krueger]

Thanks for that info!

@AlienKevin

I’m really interested in how you run the simulator as that is currently my biggest obstacle.

Currently, there is no simulation. I’m still working on the interactions for modification of circuits (this is way more work! Svg rendering, cues for editing, coming up with the datastructures and operations for editing, etc.). I’m already pretty confident I know how simulation is going to work out, at least for the start.

There are some questions that come up eventually when designing a circuit simulator:

What do you do about loose gate ends?

Option 1: Loose ends are low (off), there only exist 2 states of wires: high and low (on and off)

So the output of a single NAND gate that’s not connected to anything would be high.
How do you handle splitting the wire into two? That’s easy: Just duplicate whatever signal is at the input end (is there an ‘input’ end to a wire? In this way of simulation, there has to be!).
How do you handle joining two wires? The answer to this is hard. I guess the only option is to disallow this. See how this directly has an influence on the design, as wires now need directionality: If wires weren’t directional, there’s no way to observe a difference between a wire split and a wire join. Both would just be 3-way wires.

Option 2: Loose ends are another wire state ‘undefined’.

Now we start to move into multi-state logic. Normal gates with any input connection being undefined output undefined, too. At wire joins and splits undefined on any end causes an undefined on other ends.
If there is no mechanism of getting rid of this undefined, then it’ll quickly just ‘infest’ your whole logic circuit, if you have loops in your circuit going back to the input, so you might want to incorporate elements like ‘pull up’ or ‘pull down’ which can be connected to wires to causes them being ‘high’ or ‘low’, respectively, if they became undefined.
Often gates like a MUX also allow undefined input values without an undefined output, if the undefined wires aren’t chosen.

How do you handle feedback loops?

Sometimes feedback loops behave very well, as for example the NOR RS-Latch from the screenshot of my last post: No matter the inputs, there are always well-defined outputs (If you choose a valid starting state).

But if you allow feedback loops (which you should! It’s the only way to implement memory components), then you need to decide about what happens with a NOT gate that has its output connected to its input.

Option 1: Let it alternate.

Like @jxxcarlson wrote, you’ll likely end up writing a stepping simulator: Each step you look at the inputs of all gates and set the output values accordingly.
So in this case you’d look at the input value of your NOT gate: Let’s say it’s off. Then you’ll turn on the output value, and for now you’ll stop looking at the input value of this NOT gate. So for now your wire shows it’s ‘high’.
In the next time step you’ll look at the input of this NOT gate and see it’s ‘high’, so you set the output value of it to ‘low’.

What results is a circuit that keeps going on and off as quickly as you simulate your circuit: Hey’ you’ve built yourself a clock! This can be cool, but in reality people try to not build such circuits and they use different mechanisms for clocks.

Option 2: Burn out.

Have you played Minecraft? If you played around with redstone quite a bit, you might have noticed that turning a redstone torch on and off very fast repeatedly causes it to ‘burn out’. It just doesn’t turn back on again. (This is the exact same situation: You probably know that redstone torches are basically NOT (/NOR) gates).

In other words: You could observe and keep track of your circuits in a way to predict whether it ‘converges’ or whether it ‘alternates’. If it alternates, you could set the output simply to ‘low’, but that might be confusing to users. ‘undefined’ is kind of not true as well, so let’s go for another value: ‘error’.

And now you need to find semantics for propagating ‘error’ through your gates and circuits and ‘pull up’ and 'pull down’s too.

---

My choice for question 1 right now is Option 1, as I find it is simpler. I don’t worry about wires having directionality. I feel this is quite natural as we think of gates to have direction, too. So why wouldn’t splits and joins be like gates too? In fact, an ‘or’ gate is kind of a join between to wires, isn’t it? My application keeps track of the direction of wires and disallows any input pins to have more than 1 connection. Everything that’s not connected is considered to be low.

My choice for question 2 is Option 2 as well, for now.

All in all, I think my way is just the simpler way of doing things for now, and I recommend you do the same. Just keep in mind you have to carefully handle the directionality of wires (every wire connects from one gate output to another gate’s input!).

---

The other alternatives are very valid, too though! And there are even more I didn’t even mention. Logisim, that I mentioned earlier both has ‘undefined’ and ‘error’ wires. I have also read about some simulators having even more values, for example when simulating ‘MOSFET’ transistors you might want ‘strong high’, ‘weak high’, ‘weak low’, ‘strong low’.

Implementation

So now I didn’t talk about implementation, yet. @jxxcarlson has got you covered pretty nicely for the start. Looking at your initial post, I’d suggest you try implementing it not in terms of ‘Composite Gate’ and ‘BuiltInGate’, but just let it be a list of wires and a list of gates. The wires connect two gates by index. This is not ideal from a list-index-lookup-guaruntee way, but it’s the simplest for now. So essentially, you’d have a graph datastructure with nodes that are gates and edges that are wires.

If you simulate, you step through all your gates and determine the new output state by looking up their inputs and computing whatever they compute usually.

Hope this all got you inspired and thinking about concrete solutions. I know this is a low of text, I’m just really passionate about logic circuit simulation. I’ve spend countless hours in Logisim, when I should’ve payed attention in class

Have fun!

[AlienKevin]

Thanks for all the details , the graph idea is very interesting.

[AlienKevin]

@Philipp_Krueger @jxxcarlson Thanks to your inspirations on a state-driven and graph-backed circuit simulation design, I finally succeed in implementing a very crude And gate using two Nand gates and a bunch of wires. I used elm-community/graph to store the gate pins (inputs and output ports) as nodes and wires as edges. For display, my temporary dev solution is to use viz.js to show the graph. The only native gate is the Nand gate which appears everywhere when two wires join into one pin. Here’s how the And gate looks like on four possible inputs:

Elm source code here: https://github.com/AlienKevin/Circuits

BTW: I also added a gate abstraction over circuits to make gate compositions easier:

type Gate
  = NandGate
    { hiddenWires : List Wire
    , outputWires : List Wire
    }
  | CompositeGate
    { inputWires : List Wire
    , gates : List Gate
    , outputPins : List NodeId
    }
type alias Wire = (NodeId, NodeId)

[edgerunner]

@AlienKevin

My end goal is to construct an entire computer that runs in the browser , mostly for fun and possibly as an improved version of the Nand to Tetris course.

@AlienKevin

The simulator provided by the course has an ancient UI, not very flexible, and is written in Java.

I had the exact same feeling and desire when I took that course last year. Nice to see someone acting on it.