[Haskell-cafe] sequential logic

[Emil Axelsson]

2012-12-06 01:16, Christopher Howard skrev:
> Hi. I was wondering what the various (and especially most simple)
> approaches one could take for working with (simulating or calculating)
> sequential logic in Haskell. By sequential logic, I mean like wikipedia
> describes, where a system is made up of logic gates, whose output is
> dependent not only on the logic operation of the gate, but on the
> previous state of the gate. (Like in electronics where the system can be
> driven by a clock signal or have memory.)
>
> Does one have to get into FRP for that sort of thing? Or use some kind
> of FSM framework? Or is there some kind of fancy state monad suitable
> for that? Or...?
>
> I'm no electronic or digital engineer, but for learning purposes I've
> been trying to see if I could build an (extremely simple) virtual
> processor or calculator in Haskell, using only the Bool type and a few
> of the boolean operators (and functions composed of the aforementioned),
> reproducing things like half adders and full adders as functions in the
> program. Of course, I quickly ran into the stateful aspect of the
> problem, in subjects like clock signal and flip flops.

If you just want to simulate your design, this is actually very easy. 
Signals can be represented as a stream of bits (an old idea dating at 
least from Sheeran's µFP, 1984):

 > type Bit    = Bool
 > type Signal = [Bit]

Constant signals are defined using `repeat`:

 > low, high :: Signal
 > low  = repeat False
 > high = repeat True

Basic gates are implemented using `map` and `zipWith` over the streams:

 > inv :: Signal -> Signal
 > inv = map not
 >
 > (<&>) :: Signal -> Signal -> Signal
 > (<&>) = zipWith (&&)
 >
 > (<|>) :: Signal -> Signal -> Signal
 > (<|>) = zipWith (||)

And flip-flops are defined by just shifting the stream one step:

 > delay :: Bool -> Signal -> Signal
 > delay init sig = init : sig

(Note that the clock is implicit.)

Here is a simple oscillator

 > osc :: Signal
 > osc = let out = delay False (inv out) in out

which we can simulate as follows:

   *Main> take 10 osc
   [False,True,False,True,False,True,False,True,False,True]

If you want a more full-blown system with the possibility of also 
generating VHDL, check out Lava:

   http://hackage.haskell.org/package/chalmers-lava2000

or

   https://github.com/ku-fpg/kansas-lava (The Hackage version doesn't 
compile on GHC 7.6.)

The two versions are based on the same ideas. The former is a bit 
simpler, but less useful for practical stuff.

The oscillator looks almost the same in Lava (Kansas):

 > osc :: Seq Bool
 > osc = let out = register False (bitNot out) in out

   *Main> takeS 10 osc
   low | high | low | high | low | high | low | high | low | high | ? .

/ Emil