[Haskell-cafe] sequential logic
Emil Axelsson
emax at chalmers.se
Thu Dec 6 07:28:58 CET 2012
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
More information about the Haskell-Cafe
mailing list