DSL for describing circuits

I am working on a micro project: a Haskell DSL for describing circuits.
(You can find the code here)

I’m pretty happy with everything so far, but there is an ugly function alu32:

    alu32 c0 c1 c2 a b =
      let aluc = alu1 c0 c1 c2
          (out0, cout0) = aluc (a !! 0) (b !! 0) c0
          (out1, cout1) = aluc (a !! 1) (b !! 1) cout0
          (out2, cout2) = aluc (a !! 2) (b !! 2) cout1
          (out3, cout3) = aluc (a !! 3) (b !! 3) cout2
                     ...

Can anyone suggest a more idiomatic way of representing this? Also, if you feel like browsing the repository, feel free to make any suggestions. I have a bunch of things that I would still like to implement.

Can anyone suggest a more idiomatic way of representing this?

The equations for the ALU have the form

(out !! i, cout !! i) = aluc (a !! i) (b !! i) (cout !! (i - 1))

so we should be able to express all of the equations with a single equation that manipulates lists. If only cout !! (i - 1) would be something !! i, this would be easier because all the indexes would be uniform. We can make the indexes more uniform by defining cin = c0 : cout, and then the equations become:

(out !! i, cout !! i) = aluc (a !! i) (b !! i) (cin !! i)

Now we can make a loop over i to implement alu32 as follows:

alu32 c0 c1 c2 a b =
  let (out, cout) = unzip [alu1 c0 c1 c2 (a !! i) (b !! i) (cin !! i) | i <- [0 .. 31]]
      cin = c0 : cout
      ...
  in ...

This should solve the main question: How to implement alu32 without repeating all these equations. On the way, I also replaced the translate with an unzip.

However, we can do even better if we avoid the index computations. There are two problems with the indices: Index lookup is slow and awkward compared to just looping over the elements of a list. And the loop over the indices forces us to choose a fixed upper bound in the [0 .. 31] expression.

To avoid the indices, we note that the list comprehension

[alu1 c0 c1 c2 (a !! i) (b !! i) (cin !! i) | i <- [0 .. 31]]

just loops over three lists in parallel, a, b and cin. This parallel loop over three lists can be expressed with zipWith3 as follows:

unzip (zipWith3 (alu1 c0 c1 c2) a b cin)

Or you activate GHC’s extension for parallel list comprehensions by putting {-# LANGUAGE ParallelListComp #-} near the top of the file, and then use:

unzip [alu1 c0 c1 c2 ai bi ci | ai <- a | bi <- b | ci <- cin]

The latter will desugar to the former. Clearly, this variant of the code doesn’t use any indices anymore. This also means that it works for arbitrary bitvectors, not just 32bit ones. We only have to adapt the rest of the alu32 implementation to avoid indices, too. For example:

alu :: Wire -- Control Bit 0
  -> Wire -- Control Bit 1
  -> Wire -- Control Bit 2
  -> ByteWire -- n Bit Wire addend
  -> ByteWire -- n Bit Wire addend
  -> (ByteWire, Wire, Wire, Wire)
alu c0 c1 c2 a b =
  let (out, cout) = unzip (zipWith3 (alu1 c0 c1 c2) a b cin)
      cin = c0 : cout
      overflow = xorGate (take 2 (reverse cout))
      isZero   = map (all (==False)) out
      negative = last out
  in (out, overflow, isZero, negative)

This version of alu is concise and works for bitvectors of arbitrary length.

I’m not really sure about map (all (== False)) out to compute that all bits are zero. Maybe I would use something like map (all not) out or map (not . or) out. Note sure. Or maybe I would define a gate for deciding that something is all zeros and then use that one.

Also, if you feel like browsing the repository, feel free to make any suggestions.

1. Consider adding a cabal file. When I cloned your repo in order to test the above suggestion, I was confused that cabal sandbox init && cabal build didn’t work. You can just run cabal init in the repository and it should ask you questions to help you make the cabal file.

2. Consider making the Wire type more abstract.

   Currently, you have:

   type Wire = [Binary] -- A list of discrete states
   

   Instead, you could use:

   newtype Wire = Secret [Binary]
   

   The benefit of this definition is that it becomes harder to “cheat” and use list operations instead of gates. Later, when you are finished defining the basic gates, you can make a module that exports the Wire type and the gates, but not the Secret constructors. This way, you force the users of that module to use the gates and only the gates to compose wires.