Bluish Coder

I been tinkering with Haskell lately to get familiar with a purely functional programming language. As a project to work on I'm trying to port the Space Invaders emulator I wrote for Factor to Haskell.

I'm pretty much a complete newbie to Haskell and have no idea on the best ways to implement this type of thing. I'm starting simple, seeing where the bottlenecks are, and will improve the code from there.

For representing the memory I'm using a standard Haskell Array type. Being a purely functional programming language this means that any updates to the array result in it being copied and the copy being returned. If this turns out to be too inefficient there are some variations on this array type, including UArray for unboxed storage of values.

My first cut at an 8080 CPU abstraction was:

data Cpu = 
 Cpu { a  :: Word8, 
       b  :: Word8, 
       c  :: Word8, 
       d  :: Word8, 
       e  :: Word8, 
       f  :: Word8, 
       h  :: Word8, 
       l  :: Word8, 
       pc :: Word16,
       sp :: Word16,
       doInterrupts :: Bool,
       mem :: Memory }

Functions that set register values in the Cpu type actually return a new Cpu with the old values copied across and the new value set. 'Memory' is the array type:

type Memory = Array Word16 Word8

This represents a mapping from 16 bit numbers (the memory address) to 8 bit values. To make the code easier to read I also created some data types to refer to the 8080 registers:

data Register16 = BC | DE | HL | SP | PC deriving (Show)
data Register8  = A | B | C | D | E | F | H | L deriving (Show)

To implement the instruction set I created an 'Instruction' datatype with constructors for each possible type of 8080 instruction. I got this idea from the OmegaGB Gameboy Emulator in Haskell. Much thanks to the author of that for making their developer log and design ideas available. As an example, part of my 'Instruction' type is:

data Instruction =
   MoveRegister   Register8 Register8 -- MOV r1,r2 
 | MoveFromMemory  Register8   -- MOV r,M 
 | MoveToMemory   Register8  -- MOV M,r 
 | MoveImmediate   Register8 Word8  -- MVI r,data 
 | MoveToMemoryImmediate  Word8   -- MVI M,data 
 | LoadRegisterPairImmediate Register16 Word16 -- LXI rp,data16
 | LoadAccumulatorDirect  Word16   -- LDA addr
 | StoreAccumulatorDirect Word16   -- STA addr
 | LoadHAndLDirect  Word16   -- LHLD addr
 | StoreHAndLDirect  Word16   -- SHLD addr
 | ...

My usual approach for decoding the machine code opcodes into these Instruction types would be to create a function that maps each opcode from 0 through to 255 to one of the instructions. Instead of doing this I went to the 8080 instruction set reference and created Haskell overloaded functions that work on the binary of the opcode and decode the registers,etc to operate on from that. So some of these functions look like:

opcodeToInstruction (Binary 0 1 d3 d2 d1 1 1 0) _ _ = 
 let r = register8Lookup (d3,d2,d1) in
   MoveFromMemory r

opcodeToInstruction (Binary 0 1 1 1 0 s3 s2 s1) _ _ = 
 let r = register8Lookup (s3,s2,s1) in
   MoveToMemory r

opcodeToInstruction (Binary 0 1 d3 d2 d1 s3 s2 s1) _ _ = 
 let r2 = register8Lookup (s3,s2,s1)
     r1 = register8Lookup (d3,d2,d1) in
   MoveRegister r1 r2

opcodeToInstruction (Binary 0 0 1 1 0 1 1 0) b2 _ = 
   MoveToMemoryImmediate b2

The 'register8Lookup' uses the binary string for the register as it is encoded in the opcode to return the actual register type:

register8Lookup :: (Integer,Integer,Integer) -> Register8
register8Lookup (1,1,1) = A
register8Lookup (0,0,0) = B
register8Lookup (0,0,1) = C
register8Lookup (0,1,0) = D
register8Lookup (0,1,1) = E
register8Lookup (1,0,0) = H
register8Lookup (1,0,1) = L

This had the advantage of letting the Haskell compiler work out exactly what instruction to decode the opcode value too. It's made the code quite readable.

A 'runInstruction' function is used to execute the instruction and modify the Cpu type. Some examples of implementations are:

runInstruction :: Cpu -> Instruction -> Cpu
-- Data transfer group
runInstruction cpu (MoveRegister r1 r2) =
 setRegister8 cpu r1 (getRegister8 cpu r2)

runInstruction cpu (MoveFromMemory r) =
   let hl = getRegister16 cpu HL
       v  = readMemory8 cpu hl in
     setRegister8 cpu r v

runInstruction cpu (MoveToMemory r) =
   let hl = getRegister16 cpu HL
       v  = getRegister8 cpu r in
         writeMemory8 cpu hl v

runInstruction cpu (MoveImmediate r v) =
   setRegister8 cpu r v

runInstruction cpu (MoveToMemoryImmediate v) =
   let hl = getRegister16 cpu HL in
     writeMemory8 cpu hl v

-- Branch Group
runInstruction cpu (Jump addr) = 
 setRegister16 cpu PC addr

runInstruction cpu (ConditionalJump condition addr) = 
   let c = isConditionTrue cpu condition in
     if c then setRegister16 cpu PC addr else cpu 

The code that looks up the machine code byte from memory converts it to the 'Binary' datatype and calls 'opcodeToInstruction' to get the instruction out of it:

toBinary :: Word8 -> Binary
opcodeToInstruction :: Binary -> Word8 -> Word8 -> Instruction
readMemory8 :: Cpu -> Word16 -> Word8

step1 :: Cpu -> Cpu
step1 cpu = 
  let addr = pc cpu
      opcode  = readMemory8 cpu addr
      b2 = readMemory8 cpu (addr+1)
      b3 = readMemory8 cpu (addr+2) 
      instruction = opcodeToInstruction (toBinary opcode) b2 b3 in
    runInstruction cpu instruction

With all the instructions implemented I ran a simple benchmark of 1,000,000 instructions. Using '-O2' with GHC I got approximately 20 seconds on my machine (an Athlon 2500+) which is a tad slow.

As a comparison, my Factor implementation runs 1,000,000 instructions in about 1.7 seconds.

An easy change to make was to change the memory type to use a UArray which is an unboxed array. This immediately change the timing to 1.6 seconds. Which is much better than I expected. Remember that this is unoptimised code and purely functional. The only impure code is the I/O printing the CPU registers after each instruction (which I piped to /dev/null for the timings).

The implementation currently emulates about 90% of the 8080 CPU instruction set. I still need to handle interrupts and then add a simple GUI. Once that's done I'll make the code available.

Overall I found Haskell quite easy to develop with. I used 'ghci', the interpreter that is part of GHC, for most of the testing and iterative development. Using that was a lot like developing with a Lisp REPL. The static typing didn't get in my way and in fact it pointed to errors I'd made at compile time instead of run time in a lot of cases. I'll see if that remains the case when I tackle the GUI though which is likely to be a bit more difficult.