Digital circuit simulator in Haskell (SICP 3.3)

I have a copy of sicp, or as it is also known, The Wizard Book.11 Structure and Interpretation of Computer Programs; Abelson and Sussman; mit Press; 1996. This book is widely praised, but I can’t take the time to work my way through all of it. Instead, I’m going to occasionally jump into the parts of it that look interesting.

In the previous two installations of this series, we looked at ways of implementing generic functions. In the first one, by tagging values and dispatching operations on tags. In the second case, by filling a mutable table of operation–tag pairs. We saw how these are roughly equivalent to the existing Haskell features of sum types and type classes.

Now we’ll simulate a digital circuit. The reason this is interesting is that the solution in sicp uses hidden mutable state and message-passing to make the code object-oriented. It even uses a mutable global variable for scheduling! I wasn’t sure if it would be possible to replicate that in Haskell, but as we’ll see, it can get incredibly close.

Haskell does have mutable variables

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.22 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.

In[1]: 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.

In[2]: 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.33 This is the observer pattern, in case it sounds familiar.

In[3]: 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.

In[4]: 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.

In[5]: 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.

In[6]: λ> 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.

In[7]: 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.

In[8]: 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.44 Like a true designer of digital circuits, I have put the truth table in Grey code.

In[9]: 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...

Digital circuit simulator in Haskell (SICP 3.3)

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

AI has torched the market for junior programmers

Al Vigier: Canada's AI strategy shouldn't include secret Palantir bills

The Anatomy of an AI-Native Org