NAND-to-Tetris: Data Flip-Flop in Haskell

I started working through NAND-to-Tetris in Haskell this week: https://github.com/smallhadroncollider/nand-to-tetris

I didn’t study Computer Science, so thought it would be a good way to pick it up. Got a working ALU yesterday, which felt good. Don’t think I’ve cheated.

The book is written assuming you’ll use their hardware emulator thing, but I wanted to do it from scratch.

But I’ve got to chapter 3 and the book says that I need a Data Flip-Flop so that I can build up the rest of the chips (registers, RAM). But I’m totally stumped how I can do this in Haskell - partly lack of understanding the CompSci, partly haven’t written much Haskell in the last year.

Any ideas?

2 Likes

The main problem is that you now want to introduce dynamic behavior. I think the simplest way to do this is to use a function from integers to booleans to represent a dynamically changing system. Then the clock is implicit: every integer in the input is a sample of the signal at a clock tick.

newtype Signal = Signal { runSignal :: Integer -> Bool }

The DFF can be implemented like this:

dff :: Signal -> Signal
dff (Signal out) = Signal $ \t -> out (t - 1)

And you will need some functions to combine Signals:

nandSignal :: Signal -> Signal -> Signal
nandSignal (Signal in1) (Signal in2) = Signal $ \t -> nand (in1 t) (in2 t)

You could also use more general lifting functions:

liftSignal :: (Bool -> Bool) -> Signal -> Signal
liftSignal f (Signal in1) = Signal $ \t -> f (in1 t)

liftSignal2 :: (Bool -> Bool -> Bool) -> Signal -> Signal -> Signal
liftSignal2 f (Signal in1) (Signal in2) = Signal $ \t -> f (in1 t) (in2 t)

etc.

Edit: Sorry, I think the above implementation is nice, but it has a problem with starting the simulation. You need to define an initial state somehow (otherwise I think the program will loop forever). That can be done using natural number instead of integers, but perhaps it is easier to use lists of booleans instead of functions:

type Signal = [Bool]

initialState :: Bool
initialState = False

dff :: Signal -> Signal
dff xs = initialState : xs -- Note how 'dff xs !! t = xs !! (t - 1)' 

You have to redefine some of your existing operations to work on Signals.

mux :: Signal -> Signal -> Signal -> Signal
mux s a b = orS (andS a (notS s)) (andS b s)

andS :: Signal -> Signal -> Signal
andS a b = zipWith (&&) a b

notS :: Signal -> Signal
notS a = map not a

orS :: Signal -> Signal -> Signal
orS a b = zipWith (||) a b

We can use laziness and recursion to define loops in signals:

reg1 :: Signal -> Signal -> Signal
reg1 inp load = out where out = dff (mux load inp out)

You can use it like this:

> reg1 [True,True,False,False] [True,False,True,True]
[False,False,True,True,True]
1 Like

Thanks! I’ve got a basic version working now.