There are many ways to implement mutable state in Haskell, but to begin with, we’ll use the way that’s most similar to the sicp solution: IORefs. An IORef is a mutable variable, like in any other programming language.2² The only major difference is that we need a bit of extra machinery to read from it, because it’s designed so that we cannot accidentally read from it in pure code. (That would make the code impure, after all.)

We define a type Wire, which starts out with its signal Low, and with an empty list of action procedures.

The idea of action procedures comes from the sicp implementation of this code; action procedures are subscribers to the signal on this wire, and they will be invoked whenever the signal changes. Action procedures will be installed by components connected downstream of this wire, so those components can update themselves when the wire value changes.

data Signal = Low | High
  deriving (Show, Eq, Ord, Bounded)

data Wire = Wire
  { action_procedures :: IORef [IO ()]
  , signal_value      :: IORef Signal
  }

make_wire = do
  initial_procs <- newIORef []
  initial_signal <- newIORef Low
  pure (Wire initial_procs initial_signal)

We can get the signal from a wire by reading the mutable variable holding its current signal.

get_signal (Wire _ signal) =
  readIORef signal

To set a signal on a wire we write to the mutable variable. If this causes a state change of the wire, we’ll also run the installed action procedures to let downstream components know.3³ This is the observer pattern, in case it sounds familiar.

set_signal (Wire procs signal) new_value = do
  current <- readIORef signal
  when (new_value /= current) $ do
    writeIORef signal new_value
    actions <- readIORef procs
    sequence_ actions

Finally, we have a method on the wire that lets downstream components install new action procedures. To ensure wires are initialised with the proper value when components are connected, we immediately run all action procedures we install.

add_action (Wire procs _) action = do
  modifyIORef procs (action:)
  action

A probe in the sicp implementation is an action procedure installed on a wire that reports the value of the wire to the user of the program.

probe name wire =
  add_action wire $ do
    current <- get_signal wire
    putStrLn (name <> " new value: " <> show current)

At this point the wire object is done, and we can experiment with it in the repl. We create a wire and add a probe to it. If we set its signal to the same thing it was before, nothing changes. If we set its signal to a new value, the probe fires.

λ> w <- make_wire
λ> probe "wire" w
wire new value: Low
λ> set_signal w Low
λ> set_signal w High
wire new value: High

Then we can start to implement the most basic components. An inverter is, as in the sicp implementation, an action procedure on the input wire that sets the signal on its output wire to the opposite of the input.

inverter input output =
  add_action input $ do
    current <- get_signal input
    set_signal output $ case current of
      Low  -> High
      High -> Low

The and_gate works similarly, except it reads two inputs before determining its output.

and_gate a1 a2 output =
  let
    action = do
      c1 <- get_signal a1
      c2 <- get_signal a2
      set_signal output $ case (c1, c2) of
        (Low, Low)   -> Low
        (Low, High)  -> Low
        (High, High) -> High
        (High, Low)  -> Low
  in do
    add_action a1 action
    add_action a2 action

The or_gate is like the and_gate except with a different truth table.4⁴ Like a true designer of digital circuits, I have put the truth table in Grey code.

or_gate a1 a2 output =
  let
    action = do
      c1 <- get_signal a1
      c2 <- get_signal a2
      set_signal output $ case (c1, c2) of
        (Low, Low)   -> Low
        (Low, High)  -> High
        (High, High) -> High
        (High, Low)  -> High
  in do
    add_action a1 action
    add_action a2 action

So far, we have invented nothing here; this is all in line with the implementation from sicp. There are three neat properties of this Abelson and Sussman design:

• The set of components is open. If we turn this into a library, any user of the library can add their own components and their components would interact beautifully with those we have.
• The components are not limited to a fixed number of inputs or outputs. Anything that reads from wires and writes to other wires is a valid component.
• We can compose these basic gates into higher-level components, as plain procedure statements.

The latter means that we can make a half-adder by composing gates, and a full-adder by composing half-adders and gates.

half_adder a b s c = do
  d <- make_wire
  e <- make_wire
  or_gate a b d
  and_gate a b c
  inverter c e
  and_gate d e s

full_adder a b c_in sum c_out = do
  s <- make_wire
  c1 <- make_wire
  c2 <- make_wire
  half_adder b c_in s c1
  half_adder a s sum c2
  or_gate c1 c2 c_out

This all comes straight out of the sicp implementation. The only thing we’re missing so far is a scheduler to simulate propagation delay.

In sicp, the scheduler is implemented as a global mutable variable. This lets any component implicitly access it for scheduling. Let’s go all in and do it that way in Haskell too.

Wait, can Haskell even do that?

Yeah. Look at the last line where we define the_agenda. Yuck! Please never do this in production. Global mutable state is a terrible idea.5⁵ It’s a terrible idea in any programming language. But it’s even worse in Haskell, because then we’re opting out of a bunch of extra guarantees only Haskell can give us.

data Agenda = Agenda
  { current_time :: IORef Int
  , segments     :: IORef (Map.Map Int [IO ()])
  }

make_agenda = do
  time <- newIORef 0
  segs <- newIORef Map.empty
  pure (Agenda time segs)

the_agenda = unsafePerformIO make_agenda

The agenda follows the implementation in sicp, and maintains mutable variables for the current time as well as an ordered list of times and the action procedures scheduled for those times.6⁶ In sicp they use a linked list with some manual bookkeeping to keep it ordered. We could do that in Haskell too, but here we are lazy and use a standard-library ordered dictionary instead.

The propagate function uses this agenda to simulate the circuit until it stabilises. It pops the smallest next time step from the agenda, updates the current time to it, and executes the actions associated with it. It repeats this until there are no more scheduled time steps.

propagate = do
  segs <- readIORef (segments the_agenda)
  case Map.minViewWithKey segs of
    Nothing -> pure ()
    Just ((time, actions), remaining) -> do
      writeIORef (current_time the_agenda) time
      writeIORef (segments the_agenda) remaining
      sequence_ actions
      propagate

The sicp code has an after_delay function to help components schedule their updates after their respective propagation delays. We’ll implement the same.

after_delay delay action = do
  time <- readIORef (current_time the_agenda)
  modifyIORef (segments the_agenda) $
    Map.insertWith (<>) (delay + time) [action]

Now components need to use this, so they update their outputs only after a delay, rather than immediately. This means inserting an after_delay call before set_signal in all components. Here it is for the inverter, as an example.

inverter input output =
  add_action input $ do
    current <- get_signal input
    after_delay 2 $ do
      set_signal output $ case current of
        Low  -> High
        High -> Low

We also want the probe to show the current time when it makes a reading.

probe name wire =
  add_action wire $ do
    current <- get_signal wire
    time <- readIORef (current_time the_agenda)
    putStrLn (name <> " (t=" <> show time <> ") new value: " <> show current)

And that’s it! Now that we’re done, we can open the repl and run the same interaction as Abelson and Sussman, to test that our code behaves the same way the sicp code does.

λ> input_1 <- make_wire
λ> input_2 <- make_wire
λ> sum <- make_wire
λ> carry <- make_wire
λ> probe "sum" sum
sum (t=0) new value: Low

λ> probe "carry" carry
carry (t=0) new value: Low

λ> half_adder input_1 input_2 sum carry

λ> set_signal input_1 High
λ> propagate
sum (t=8) new value: High

λ> set_signal input_2 High
λ> propagate
carry (t=11) new value: High
sum (t=16) new value: Low

It actually surprised me how close the Haskell solution got to the one in sicp. It’s pretty much the same thing. The only major difference I can think of is that since the_agenda is a top-level binding in Haskell, we cannot reassign it in the repl. But that’s about it.

We can also do something fun the sicp authors never showed: a ring oscillator. If we connect the output of the inverter to itself, probe it, and then propagate, we get an infinite sequence of

--------------- >8 -------
a (t=4558) new value: High
a (t=4560) new value: Low
a (t=4560) new value: High
a (t=4562) new value: Low
a (t=4562) new value: High
a (t=4564) new value: Low
a (t=4564) new value: High
a (t=4566) new value: Low
a (t=4566) new value: High
a (t=4568) new value: Low
--------------- >8 -------

where the output toggles every propagation delay.

The code above is fine. It is rife with side-effects, but it is fine.

Many people seem to have this view that Haskell code must be free of side effects, and that’s not true. Haskell code doesn’t need to be a pristine pure tower of abstraction connected to a dirty effectful layer. Haskell code can be like code in any other language – mostly dirty and effectful – but with some islands of purity where they help. That’s a legal way to use Haskell, and it’s still an improvement over other languages.

But what if we want to make the simulation pure? One way to do it would be to move the wire state management from IO to ST. While IO is a type of computation that allows arbitrary side effects, ST is a type of computation that only allows mutable variables, and it’s designed so that no effects can escape outside of its local context. That means we could execute ST-based mutation inside the circuit simulation in a way that is pure from the outside. This would be a fairly mundane transformation and is not interesting.

But Haskell lets us do even better. That’ll be a separate article. Stay tuned.