Boolean Logic and Arithmetic with F#

So, I've had this book (The Elements of Computing Systems) on my shelf for a good few years and never got round to reading it, yet alone completing the exercises within.

Drawing

Therefore I thought I'd finally read it.
I also decided I would complete the exercises in a different way than suggested in the book. By using F#!

Rather than utilising the Hardware Definition Language and the given emulator as suggested. I will model all of the parts of the computer in F#.

Doing so, I hope to utilise various functional programming techniques, alongside F# specific features to keep the solutions as simple and easy too understand as possible.
Hopefully learning something new on the way.

As I work my way through the book I'll be adding to this series.
I aim to cover one collection of exercises (roughly a chapter) per post, however this initial post will cover two, just to get me going.

The book starts with the building blocks of the CPU, Boolean logic gates. Let's dive straight in.

Logic Gates

The approach outlined in the book is to create a number of simple logic gates, composed of previously defined gates. It starts you off with an initial NAND gate implementation that you can then utilise to create the next gate, which can then also be used in subsequent gates, and so on..

I kind of like this approach from an academic point of view. It makes for some interesting problem solving activities.
Therefore, I'll follow the approach in the book, even though I know it won't result in the cleanest, most idiomatic F# code. (At least not that I can currently create. Please feel free to give me some pointers)

That being said, all of the gates I create have a much cleaner implementation by utilising pattern matching instead of making use of the previously defined gates. I will also provide these for most of the implementations.

Right then, first up we need to replicate that NAND gate the book provided for us.

Starting with NAND

As you may know, a NAND gate is a binary gate that returns false if both of it's inputs are true or returns true otherwise.
A truth table for the gate is as follows.

|   a   |   b   |  out  |
|   0   |   0   |   1   |
|   0   |   1   |   1   |
|   1   |   0   |   1   |
|   1   |   1   |   0   |

One great thing about using F# and Pattern Matching for modelling these gates is that they end up mirroring the truth tables.

Therefore our NAND gate can be defined like so.

1: 
2: 
3: 
4: 
5: 
6: 
let Nand a b = 
    match a, b with
    | false, false -> true
    | false, true -> true
    | true, false -> true
    | true, true -> false

This can, of course, be further simplified to the following. (albeit no longer mirroring the truth table above)

1: 
2: 
3: 
4: 
    let Nand a b = 
        match a, b with
        | true, true -> false
        | _, _ -> true

Now that we have our NAND implementation, the book instructs us to tackle the following gates in the order given.
The order is only important so that we can use each of the implementations in subsequent gates.

  • NOT
  • AND
  • OR
  • XOR
  • Multiplexor (MUX)
  • Demultiplexor (DMUX)

In addition there are some Multi bit versions of these gates, and a multi way OR. We'll look at these in more detail when we get to them.

The following are implementations of the first six gates, made up of only previously defined gates (as per the books instructions).
I have included a truth table and circuit diagram for each of them. The circuit diagrams are created using only previously defined gates, as the book intended.
In order to save space and keep the post concise (well, shorter at least), they are initially hidden, just hover or click the link to view them.

NOT Gate Details
NOT GATE
|   a   |  out  |
|   0   |   1   |
|   1   |   0   |
NOT Gate
1: 
2: 
let Not a = 
    Nand a a
AND Gate Details
AND GATE
|   a   |   b   |  out  |
|   0   |   0   |   0   |
|   1   |   0   |   0   |
|   0   |   1   |   0   |
|   1   |   1   |   1   |
AND Gate
1: 
2: 
3: 
let And a b = 
    Nand a b 
    |> Not
OR Gate Details
OR GATE
|   a   |   b   |  out  |
|   0   |   0   |   0   |
|   1   |   0   |   1   |
|   0   |   1   |   1   |
|   1   |   1   |   1   |
OR Gate
1: 
2: 
let Or a b =
    Nand (Nand a a) (Nand b b)
XOR Gate Details
AND GATE
|   a   |   b   |  out  |
|   0   |   0   |   0   |
|   1   |   0   |   1   |
|   0   |   1   |   1   |
|   1   |   1   |   0   |
XOR Gate
1: 
2: 
let Xor a b = 
    Or (And a (Not b)) (And (Not a) b) 
MUX Gate Details
MUX GATE
|  sel  |   a   |   b   |  out  |
|   0   |   0   |   0   |   0   |
|   0   |   0   |   1   |   0   |
|   0   |   1   |   0   |   1   |
|   0   |   1   |   1   |   1   |
|   1   |   0   |   0   |   0   |
|   1   |   0   |   1   |   1   |
|   1   |   1   |   0   |   0   |
|   1   |   1   |   1   |   1   |
MUX Gate
1: 
2: 
let Mux sel a b =
    Nand (Nand b sel) (Nand (Not sel) a)    
DMUX Gate Details
DMUX GATE
|  sel  |   in   |  outA  |  outB  |
|   0   |   0    |   0    |   0    |
|   1   |   0    |   0    |   0    |
|   0   |   1    |   1    |   0    |
|   1   |   1    |   0    |   1    |
DMUX Gate
1: 
2: 
let DMux x sel =
    (And x (Not sel), And x sel)

Clearly they aren't the prettiest of functions due to the needed parentheses. They don't tend to suite the functional style. (or maybe that's just my lack of experience)

Perhaps there is a better, more functional way of creating these functions from the previously defined ones. I'd be interested in seeing some similar solutions or techniques, so feel free to give me some pointers if you wish.

That being said, It is clear that just like before and by ignoring the guidelines in the book (where the purpose is to learn how all other logic gates can be created using NAND as a starting point), we can again utilise pattern matching to clean things up.

The pattern matched versions again, more closely reflect the corresponding truth tables for the logic gates. The implementations are given below.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
    let Not a = function
        | true -> false
        | false -> true

    let And a b = 
        match a, b with
        | true, true -> true
        | _, _ -> false

    let Or a b =
        match a, b with
        | true, _ -> true
        | _, true -> true
        | _, _ -> false 

    let Xor a b =
        match a, b with
        | true, false -> true
        | false, true -> true
        | _, _ -> false

    let Mux sel a b  =
        match sel with
        | false -> a
        | _ -> b

    let DMux sel x =
        match sel with
        | false -> (x,false)
        | _ -> (false,x)

Now that they're out of the way, we can move on to some more interesting gates.

Multi Bit Gates

Multi Bit gates are effectively arrays of the previous gates we have defined. We can therefore utilise some functional programming techniques in order to make implementing these quick and simple.

First we define a couple of functions to handle Unary and Binary gate arrays.
This is all we require at this stage of working through the book, but i expect we will need some more at a latter stage.

1: 
2: 
3: 
4: 
5: 
6: 
let unaryArray gate bits =
    bits |> Array.map gate

let binaryArray gate aBits bBits =
    Array.zip aBits bBits 
    |> unaryArray (fun (a,b) -> gate a b)

As you can see these functions both make use some useful array functions and are overall nice and succinct.

Some noteworthy points from the above.

  • I chose to use Zip to combine the two input arrays into corresponding pairs and pass that into the unaryArray function. This allows for a nice, clean, binaryArray function but does mean the gate function we pass in, needs to work with tuples, not individual arguments. This means we cannot simply use our previously created functions in. Fortunately, we can use a simple lambda expression combined with pattern matching to extract the tuple parts succinctly within this binary gate function.

Now we can use partial application to create our multi bit versions of the simple gates.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
let MultiNot = unaryArray Not

let MultiAnd = binaryArray And

let MultiOr = binaryArray Or

let MultiMux sel = 
    Mux sel
    |> binaryArray

let MultiDMux sel = 
    DMux sel
    |> unaryArray

The functions above show how clean and concise these new multi bit versions of the gates become.

One thing that isn't handled however is ensuring that the amount of bits is equal in both cases. This is not something that I am worried about at this stage, but I would like to make it more robust in the future.

  • It's also worth pointing out that I have completely diverged from the book here. To implement these gates in the way the book expects we would need to iteratively call the simple gates, passing in the appropriate pairs of input bits and collecting the results into a new array. This is exactly what we get for free from Array.zip and Array.map!

Multi Way Gates

Next up, we can tackle the multi way gates.
Multi way gates have an arbitrary number of inputs and outputs, as opposed to a fixed number like our previous gates.
These inputs can also be multi bit arrays.

First, we can tackle that Multi Way OR gate I mentioned earlier.
It's a simple chip that consists of a series of OR Gates.

The first two bits are passed to the first OR gate, and then the third bit plus the result of the first OR operation are fed into the next gate. This pattern continues for all bits provided.

Hmmm, this sounds familiar, I think we'll skip the explicit definition and jump straight to a concise F# specific one.

1: 
2: 
let MultiWayOr bits = 
    bits |> Array.reduce Or

As you can see, the MultiWayOr function above maps perfectly to F#s built in Reduce function.

Next up is Multi Way MUX.

This gate is specified in the book as having 4 inputs, all 16 bit wide.
We don't need to restrict ourselves to this, but doing so simplifies the solutions due to not having to handle errors with incorrect input amounts, so I will follow that approach.

The number of control bits (the sel param) is equal to log2m where m is the number of inputs.
In this case, that means 2 bits. Again it would be nice to add some error handling around this, but that will have to wait for another time.

The gate is basically just three calls to our MultiMux gate as follows.

1: 
2: 
3: 
4: 
let Mux4Way16 a b c d (sel:bool array) = 
    let m1 = MultiMux sel.[0] a c 
    let m2 = MultiMux sel.[0] b d
    MultiMux sel.[1] m1 m2 

The book states we also need a 4 way, 16 bit version of this gate.
We can easily create this by using the 4 way version from above.

1: 
2: 
3: 
4: 
let Mux8Way16 a b c d e f g h (sel:bool array) =
    let m1 = Mux4Way16 a b c d sel.[1..2]
    let m2 = Mux4Way16 e f g h sel.[1..2]
    MultiMux sel.[0] m1 m2 

Up next, 4 way and 8 way DMUX.

These gates have the same amount of selection bits as there MUX counter parts and a single input.
The multi way in this case, relates to the varying number of output bits.

The purpose of multi way DMUX is to 'pipe' the input into a particular output based on the control bits.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
let DMux4Way x (sel:bool array) = 
    let (d1,d2) = DMux x sel.[1]
    let (a,c) = DMux d1 sel.[0]
    let (b,d) = DMux d2 sel.[0]
    (a,b,c,d)

let DMux8Way x (sel:bool array) = 
    let (d1,d2) = DMux x sel.[0]
    let (a,b,c,d) = DMux4Way d2 sel.[1..2]
    let (e,f,g,h) = DMux4Way d1 sel.[1..2]
    (a,b,c,d,e,f,g,h)

The multi way gates above all utilise previous ones we've created.

I chose to use some simple inline pattern matching to reduce the fluff by decomposing the results of the functions in turn before then returning the results in a large tuple.

Of course, we can again use pattern matching instead to do the selection. I won't bother with those implementations though, as I would rather get onto the fun bits.

So, next up, we finally get to some Boolean Arithmetic!

Boolean Arithmetic

There are five chips included in the arithmetic section outlined in the book. These are:

  • HalfAdder
  • FullAdder
  • MulitBitAdder (16 Bit)
  • MultiBitIncrementer (16 Bit)
  • ALU (Arithmetic Logic Unit)

A half adder is designed to add 2 bits.
The 2 bits returned can be thought of as the sum and the carry resulting from the addition. (The least significant bit (LSB) is the sum and the most significant bit (MSB) is the carry.

It turns out that the truth table for a half adder highlights that the sum and carry can be implemented with an XOR and an AND gate respectively (This can be seen by hovering the link below).

Half Adder Details
Half Adder
|   a   |   b   | carry |  sum  |
|   0   |   0   |   0   |   0   |
|   0   |   1   |   0   |   1   |
|   1   |   0   |   0   |   1   |
|   1   |   1   |   1   |   0   |
Half Adder
1: 
2: 
3: 
4: 
let HalfAdder a b = 
    let sum = Xor a b
    let carry = And a b
    (sum,carry)

A full adder is designed to add 3 bits. It is implemented by adding pairs of bits using the half adder we just created.

The second pair of bits added consists of the result of the first addition.
The function then returns the LSB and the MSB as the sum and carry as before.

Full Adder Details
Full Adder
|   a   |   b   |   c   | carry |  sum  |
|   0   |   0   |   0   |   0   |   0   |
|   0   |   0   |   1   |   0   |   1   |
|   0   |   1   |   0   |   0   |   1   |
|   0   |   1   |   1   |   1   |   0   |
|   1   |   0   |   0   |   0   |   1   |
|   1   |   0   |   1   |   1   |   0   |
|   1   |   1   |   0   |   1   |   0   |
|   1   |   1   |   1   |   1   |   1   |
Full Adder
1: 
2: 
3: 
4: 
let FullAdder a b c = 
    let (s1,c1) = HalfAdder a b
    let (sum,c2) = HalfAdder s1 c
    (sum, Or c1 c2)

Next up, we have the fully fledged Adder chip.
The adder is responsible for adding integers represented as bits.
It can therefore take bit arrays of any size (we will most likely only need up to 32 bits).

The chip outlined in the book is an example of a ripple carry adder. This means that the bits are added together in order, starting from the LSB and any carry is carried over into the next addition.

This obviously means each stage of the addition (except the first) has 3 bits. This fits perfectly to our Full Adder from above.

So, all we need to do is implement a recursive function that adds the given bits starting from the end of the arrays.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
let Adder aBits bBits =
    let rec addBits aBits bBits carry accu = 
        match aBits, bBits with
        | aHead :: aTail, bHead :: bTail -> 
            let (sum,c) = FullAdder aHead bHead carry
            addBits aTail bTail c (sum :: accu)
        | [],_
        | _,[] -> accu
    addBits (aBits |> Array.rev |> Array.toList) (bBits |> Array.rev |> Array.toList) false List.empty
    |> List.toArray

The adder function allows us to add together any pair of 2's compliment binary integers.

Lastly, the increment function is simply a partially applied Adder function with one of the parameters fixed to a binary representation of 1.

1: 
2: 
//In plus one
let Increment aBits = Adder aBits [| for i in 1 .. 16 -> match i with | 16 -> true | _ -> false |]

The Arithmetic Logic unit

Finally, we can bring all of our work together in the implementation of the Arithmetic Logic Unit (ALU).

This ALU is specified in the book. It has 8 inputs consisting of two 16 bit data inputs, and 6 control bits.
These control bits are used to select the function that the ALU executes; They are.

  • zx - Zeros the xBits input
  • nx - Negates the xBits input
  • zy - Zeros the yBits input
  • ny - Negates the yBits input
  • f - The function selecter. If 1 Addition is performed else AND is performed.
  • no - Negates the output

The ALU provides three outputs.

  • The result of the function (Addition or AND)
  • zr - Indicates whether the output is equal to zero
  • ng - Indicates whether the output is negative

The truth table for the ALU is far to big for me to copy out, but I'm sure you could found it with some quick google-foo if desired.

My implementation of the ALU is shown below. As you can see, it's pretty straight forward.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
let ALU xBits yBits zx nx zy ny f no = 
    //handle x    
    let ox1 = MultiMux zx xBits [|for i in 1..16 -> false |]  //Zero all X bits if zx
    let nox1 = MultiNot ox1 //What would this be if negated
    let ox2 = MultiMux nx ox1 nox1 //Select based on nx

    //handle y
    let oy1 = MultiMux zy yBits [|for i in 1..16 -> false |]  //Zero all X bits if zy
    let noy1 = MultiNot oy1 //What would this be if negated
    let oy2 = MultiMux ny oy1 noy1 //Select based on ny

    //handle & / +
    let o3 = MultiAnd ox2 oy2 //an and would be
    let o4 = Adder ox2 oy2 //addition would be

    //Output
    let o5 = MultiMux f o3 o4 //Choose and or addition
    let no5 = MultiNot o5 //Negated out would be
    let out = MultiMux no o5 no5 //Choose to negate or not

    let zr = Not (MultiWayOr out)
    let ng = MultiWayOr (MultiAnd out [|for i in 1..16 -> match i with | 16 -> true | _ -> false|] )
    
    (out, zr, ng)

Clearly though, this implementation does have some wasteful processing.

By abiding to the books rules we have to execute individual logic paths to produce their respective results before switching between them based on a specific control bit.

Therefore, we can immediately refactor this as follows:

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
    let ALU xBits yBits zx nx zy ny f no = 
        let zero c b = if c then [| for i in 1..16 -> false |] else b 
        let negate c b = if c then MultiNot b else b
        let x = xBits |> zero zx |> negate nx 
        let y = yBits |> zero zy |> negate ny 

        //Apply function and negate if needed
        let out = if f then MultiAnd x y else Adder x y
                  |> negate no
         
        (out, MultiWayOr out |> Not, MultiAnd out [| for i in 1..16 -> match i with | 16 -> true | _ -> false |] |> MultiWayOr)

Much better!

All we need to do now is get testing.

Testing

Finally, it's time to get some tests executed. The book provides comparison files in order to check our output when using the recommended Hardware simulator and Hardware Definition Language (HDL) code.

I decided it would be a fun exercise to utilise these within my tests.

So, what we need is a way to convert a string and/or integer representation of bits in to arrays of Boolean values for use with my Gates (I could have implemented my gates using integers of course).

In addition we need to read the provided comparison file and compare it to our results.
This means we need to return our results in the correct format (Also a string representation of bits!)

Lets get to it.

First up, converting a string (A sequence of chars) to an array of integers.
In actual fact, what we need is a bit different to that as we only care about ones and zeros, obviously. Therefore I will simply pattern match the char '1', to the integer 1 and anything else to zero.

This may not be the most robust implementation, as we would really want to trigger an error, or return nothing if the string is invalid (eg. if it contained characters other than '1' or '0').

I have also created a string version of the function (as opposed to working on chars).

1: 
2: 
3: 
4: 
5: 
6: 
7: 
    let stringToInt = function 
        | "1" -> 1
        | _ -> 0

    let charToInt = function 
        | '1' -> 1
        | _ -> 0

Next up, we create a quick helper to convert an integer into a Boolean. I've done this in the same manner as the string converter. I have purposefully ignored the fact we could have incorrect input values.

1: 
2: 
3: 
    let intToBool = function 
        | 1 -> true
        | _ -> false

We will also need the inverse of these functions, Boolean to integer and integer to string.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 
    let boolToInt = function 
        | true -> 1
        | _ -> 0

    let intToString = function 
        | 1 -> "1"
        | _ -> "0"

    

To complete the set we then compose these together to create straight string to Boolean and Boolean to string functions.
I also defined two additional functions to convert arrays of integers and Boolean values to a single string.

1: 
2: 
3: 
4: 
5: 
    let stringToBool = stringToInt >> intToBool
    let boolToString = boolToInt >> intToString

    let intsToString = Array.map intToString >> String.concat ""
    let boolsToString = Array.map boolToInt >> intsToString

All of these simple functions can then be used with the built in Array/List module functions to convert entire collections as needed.

To do the actual testing I will use the provided comparison files supplied with the books software.

These files, are basically truth tables.
An example of the one supplied for AND is as follows:

|   a   |   b   |  out  |
|   0   |   0   |   0   |
|   0   |   1   |   0   |
|   1   |   0   |   0   |
|   1   |   1   |   1   |

So, I need to parse this, create the inputs and then compare the given output with our functions output. Sounds simple, right?

First off, lets read a file in and create a list of the rows from the given table.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
    let parseFile path = 
        File.ReadAllLines path
        |> Seq.map (fun s -> 
               s.Split([| "|" |], StringSplitOptions.RemoveEmptyEntries)
               |> Array.map (fun s -> s.Trim())
               |> Array.toList)
        |> Seq.toList
val x : string list list =
  [["a"; "b"; "out"]; ["0"; "0"; "0"]; ["0"; "1"; "0"]; ["1"; "0"; "0"];
   ["1"; "1"; "1"]]

As you can see this gives us a list of lists representing the values per column per row.
We now need to convert this into a list of maps. So that the arguments can be accessed by name.

This is purely a convenience for me as I have renamed and rearranged the functions and there parameters in some cases. If I had stuck with the same naming conventions and argument order as the book, I likely wouldn't need to do this.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
    let rec createMap matrix (cols : string list) = 
        match matrix with
        | row :: rest -> 
            [ row
              |> List.mapi (fun i x -> (cols.[i], x))
              |> Map.ofSeq ]
            @ createMap rest cols
        | _ -> []

Finally we need a function to act as our test runner.
This will take a file name, parse the file, create a list of test case data and then call a provided test function.

The test function provided will need to map the test case data (using the map keys) to the actual parameters and compare the result in a specific manner to determine success (or failure).

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 
    let executeTests path func = 
        let data = parseFile path
        let testData = createMap (List.tail data) (List.head data)
        let rec execute func testData num = 
            match testData with
            | case :: rest -> 
                sprintf "Test number %i - %s \n" num  (if func case then "Success" else "Failure") + execute func rest (num+1)
            | [] -> "All tests complete"
        execute func testData 0

Lets put it to the test.
I'll start simple and run the test for the And functions test file shown above.

Here is my test function and the use of it.

1: 
2: 
3: 
4: 
    let andTest (case : Map<string, string>) = 
        And (stringToBool case.["a"]) (stringToBool case.["b"]) = stringToBool case.["out"]

    executeTests @"content\post-files\Emulation\And.cmp" andTest
val it : string =
  "Test number 0 - Success 
   Test number 1 - Success 
   Test number 2 - Success 
   Test number 3 - Success 
   All tests complete"

I could further extend this to log each parameter value as the test function is called, thus giving us full visibility of the variables.
For now though I'll leave it as is. (The post is already long enough! :) )

Another example is given below; It is the test case for the Increment function.
The partial truth table (test file) is as follows.

|        in        |       out        |
| 0000000000000000 | 0000000000000001 |
| 1111111111111111 | 0000000000000000 |
| 0000000000000101 | 0000000000000110 |
| 1111111111111011 | 1111111111111100 |
1: 
2: 
3: 
4: 
5: 
6: 
    let IncTest (case : Map<string, string>) = 
        case.["in"]
        |> Seq.map (charToInt >> intToBool)
        |> Seq.toArray
        |> Increment
        |> boolsToString = case.["out"]

I also thought it would be useful (and more importantly it was fun!) to make some actual decimal integer to binary (so base 10 to base 2) converters and vice versa.

The following converts a decimal to binary (it doesn't handle negatives, we will get to that later).

1: 
2: 
3: 
4: 
5: 
6: 
    let toBinary i = 
        let rec convert i acc = 
            match i with
            | _ when i > 0 -> (i % 2) :: convert (i / 2) acc
            | _ -> acc
        convert i [] |> List.rev |> List.toArray 

Next we require a function to flip each bit in a sequence. This is required for converting an integer into a two's compliment binary representation when the number is negative.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
    let flipBits b = 
        let rec convert b acc = 
            match b with
            | h :: t -> 
                match h with
                | 1 -> 0 :: convert t acc
                | _ -> 1 :: convert t acc
            | [] -> acc
        convert (b |> List.ofSeq) []
        |> List.toArray

As part of that conversion to two's compliment, we also need a function to pad a binary array with zeros depending on the given maximum bit length.

1: 
2: 
3: 
    let padBits length (bits : int array) =
        let padding = [| for i in 1..(length - bits.Length) -> 0 |]
        Array.concat [|padding; bits|]

Finally, we make use of the Increment function we have already defined as part of our Boolean arithmetic functions in order to complete what we need to fully represent a decimal in twos compliment binary form.

The basic steps to the function are:

  1. Take in a decimal integer and the target bit length.
  2. Determine whether the integer is negative.
  3. If it is:
    1. Get the absolute value
    2. Convert that value to binary
    3. Pad the binary with zeros up until the bit length
    4. flip all the bits
    5. Add one
  4. If it is not:
    1. Simply convert to binary and pad the bits
 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
    let toTwosCompliment i b = 
        match i with
        | _ when i < 0 -> 
            abs i
            |> toBinary
            |> padBits b
            |> flipBits |> Array.map intToBool
            |> Increment |> Array.map boolToInt
        | _ -> 
            i
            |> toBinary
            |> padBits b

this will now allow us to get the binary representation of any integer returned in an array of Boolean values for use in our arithmetic functions.

The functions to convert back from binary to base 10 are just as simple.

To convert to a positive decimal we do the following steps:

  1. Reverse the bits (As we need to work right to left)
  2. For each bit:
    1. Multiply the value by the base (2)
    2. Raise it to it's index in the binary array.

And that's all there is to it.

For a negative number we first need to convert to two's complement.
This involves padding, flipping the bits and adding one (Exactly as when converting to a negative binary representation), before converting to base 10 as described above.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
    let toBase10 b = 
        let rec convert b i acc = 
            match b with
            | h :: t -> float h * 2.0 ** i + convert t (i + 1.0) acc
            | [] -> acc
        convert (b |> Array.rev |> Array.toList) 0.0 0.0 |> int

    let toDecimal b (binary : int array) =
        match binary.[0] with
        | 0 -> binary |> toBase10
        | _ -> 
            -(binary
            |> padBits b
            |> flipBits |> Array.map intToBool
            |> Increment |> Array.map boolToInt 
            |> toBase10)

Phew!, let's give these new functions a test.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
    //Adding 100 and 320.

    let a = 
        toTwosCompliment 100 16 
        |> Array.map intToBool

    let b = 
        toTwosCompliment 320 16 
        |> Array.map intToBool

    let result = 
        Adder a b
        |> Array.map boolToInt
        |> toDecimal 16
val a : bool [] =
  [|false; false; false; false; false; false; false; false; false; true; true;
    false; false; true; false; false|]

val b : bool [] =
  [|false; false; false; false; false; false; false; true; false; true; false;
    false; false; false; false; false|]

val result : int = 420
 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
    //Incrementing a negative number.

    let negative = 
        toTwosCompliment -112 16 
        |> Array.map intToBool

    let negativePlus1 = 
        Increment negative
        |> Array.map boolToInt
        |> toDecimal 16
val negative : bool [] =
  [|true; true; true; true; true; true; true; true; true; false; false; true;
    false; false; false; false|]

val negativePlus1 : int = -111

Wow that turned out to be a long post. Thanks for hanging on in!

I hope some of you find something useful to take from this post, be it F#, Boolean logic/arithmetic or book related.

I'll try and keep the future posts in the series shorter, however I'm already thinking that I need to revisit some of the functions in this post to make them more robust.

As always, the code and any supporting material can be found on GitHub and I would love for people to share there advice or experience in F# to boost my understanding.

module FsEmulation
val Nand : a:bool -> b:bool -> bool

Full name: FsEmulation.Nand
val a : bool
val b : bool
val Nand : a:bool -> b:bool -> bool

Full name: FsEmulation.PatternMatched.Nand
val Not : a:bool -> bool

Full name: FsEmulation.Not
val And : a:bool -> b:bool -> bool

Full name: FsEmulation.And
val Or : a:bool -> b:bool -> bool

Full name: FsEmulation.Or
val Xor : a:bool -> b:bool -> bool

Full name: FsEmulation.Xor
val Mux : sel:bool -> a:bool -> b:bool -> bool

Full name: FsEmulation.Mux
val sel : bool
val DMux : x:bool -> sel:bool -> bool * bool

Full name: FsEmulation.DMux
val x : bool
val Not : a:'a -> _arg1:bool -> bool

Full name: FsEmulation.PatternMatched2.Not
val a : 'a
val And : a:bool -> b:bool -> bool

Full name: FsEmulation.PatternMatched2.And
val Or : a:bool -> b:bool -> bool

Full name: FsEmulation.PatternMatched2.Or
val Xor : a:bool -> b:bool -> bool

Full name: FsEmulation.PatternMatched2.Xor
val Mux : sel:bool -> a:'a -> b:'a -> 'a

Full name: FsEmulation.PatternMatched2.Mux
val b : 'a
val DMux : sel:bool -> x:bool -> bool * bool

Full name: FsEmulation.PatternMatched2.DMux
val unaryArray : gate:('a -> 'b) -> bits:'a [] -> 'b []

Full name: FsEmulation.unaryArray
val gate : ('a -> 'b)
val bits : 'a []
module Array

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.map
val binaryArray : gate:('a -> 'b -> 'c) -> aBits:'a [] -> bBits:'b [] -> 'c []

Full name: FsEmulation.binaryArray
val gate : ('a -> 'b -> 'c)
val aBits : 'a []
val bBits : 'b []
val zip : array1:'T1 [] -> array2:'T2 [] -> ('T1 * 'T2) []

Full name: Microsoft.FSharp.Collections.Array.zip
val b : 'b
val MultiNot : (bool [] -> bool [])

Full name: FsEmulation.MultiNot
val MultiAnd : (bool [] -> bool [] -> bool [])

Full name: FsEmulation.MultiAnd
val MultiOr : (bool [] -> bool [] -> bool [])

Full name: FsEmulation.MultiOr
val MultiMux : sel:bool -> (bool [] -> bool [] -> bool [])

Full name: FsEmulation.MultiMux
val MultiDMux : sel:bool -> (bool [] -> (bool * bool) [])

Full name: FsEmulation.MultiDMux
val MultiWayOr : bits:bool [] -> bool

Full name: FsEmulation.MultiWayOr
val bits : bool []
val reduce : reduction:('T -> 'T -> 'T) -> array:'T [] -> 'T

Full name: Microsoft.FSharp.Collections.Array.reduce
val Mux4Way16 : a:bool [] -> b:bool [] -> c:bool [] -> d:bool [] -> sel:bool array -> bool []

Full name: FsEmulation.Mux4Way16
val a : bool []
val b : bool []
val c : bool []
val d : bool []
val sel : bool array
type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool
type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>
val m1 : bool []
val m2 : bool []
val Mux8Way16 : a:bool [] -> b:bool [] -> c:bool [] -> d:bool [] -> e:bool [] -> f:bool [] -> g:bool [] -> h:bool [] -> sel:bool array -> bool []

Full name: FsEmulation.Mux8Way16
val e : bool []
val f : bool []
val g : bool []
val h : bool []
val DMux4Way : x:bool -> sel:bool array -> bool * bool * bool * bool

Full name: FsEmulation.DMux4Way
val d1 : bool
val d2 : bool
val c : bool
val d : bool
val DMux8Way : x:bool -> sel:bool array -> bool * bool * bool * bool * bool * bool * bool * bool

Full name: FsEmulation.DMux8Way
val e : bool
val f : bool
val g : bool
val h : bool
val HalfAdder : a:bool -> b:bool -> bool * bool

Full name: FsEmulation.HalfAdder
val sum : bool
val carry : bool
val FullAdder : a:bool -> b:bool -> c:bool -> bool * bool

Full name: FsEmulation.FullAdder
val s1 : bool
val c1 : bool
val c2 : bool
val Adder : aBits:bool [] -> bBits:bool [] -> bool []

Full name: FsEmulation.Adder
val aBits : bool []
val bBits : bool []
val addBits : (bool list -> bool list -> bool -> bool list -> bool list)
val aBits : bool list
val bBits : bool list
val accu : bool list
val aHead : bool
val aTail : bool list
val bHead : bool
val bTail : bool list
val rev : array:'T [] -> 'T []

Full name: Microsoft.FSharp.Collections.Array.rev
val toList : array:'T [] -> 'T list

Full name: Microsoft.FSharp.Collections.Array.toList
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val empty<'T> : 'T list

Full name: Microsoft.FSharp.Collections.List.empty
val toArray : list:'T list -> 'T []

Full name: Microsoft.FSharp.Collections.List.toArray
val Increment : aBits:bool [] -> bool []

Full name: FsEmulation.Increment
val i : int
val ALU : xBits:bool [] -> yBits:bool [] -> zx:bool -> nx:bool -> zy:bool -> ny:bool -> f:bool -> no:bool -> bool [] * bool * bool

Full name: FsEmulation.ALU
val xBits : bool []
val yBits : bool []
val zx : bool
val nx : bool
val zy : bool
val ny : bool
val no : bool
val ox1 : bool []
val nox1 : bool []
val ox2 : bool []
val oy1 : bool []
val noy1 : bool []
val oy2 : bool []
val o3 : bool []
val o4 : bool []
val o5 : bool []
val no5 : bool []
val out : bool []
val zr : bool
val ng : bool
val ALU : xBits:bool [] -> yBits:bool [] -> zx:bool -> nx:bool -> zy:bool -> ny:bool -> f:bool -> no:bool -> bool [] * bool * bool

Full name: FsEmulation.AlternateALU.ALU
val zero : (bool -> bool [] -> bool [])
val negate : (bool -> bool [] -> bool [])
val x : bool []
val y : bool []
namespace System
namespace System.IO
val stringToInt : _arg1:string -> int

Full name: FsEmulation.Utilities.stringToInt
val charToInt : _arg1:char -> int

Full name: FsEmulation.Utilities.charToInt
val intToBool : _arg1:int -> bool

Full name: FsEmulation.Utilities.intToBool
val boolToInt : _arg1:bool -> int

Full name: FsEmulation.Utilities.boolToInt
val intToString : _arg1:int -> string

Full name: FsEmulation.Utilities.intToString
val stringToBool : (string -> bool)

Full name: FsEmulation.Utilities.stringToBool
val boolToString : (bool -> string)

Full name: FsEmulation.Utilities.boolToString
val intsToString : (int [] -> string)

Full name: FsEmulation.Utilities.intsToString
type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : params indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array
Multiple items
type String =
  new : value:char -> string + 7 overloads
  member Chars : int -> char
  member Clone : unit -> obj
  member CompareTo : value:obj -> int + 1 overload
  member Contains : value:string -> bool
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EndsWith : value:string -> bool + 2 overloads
  member Equals : obj:obj -> bool + 2 overloads
  member GetEnumerator : unit -> CharEnumerator
  member GetHashCode : unit -> int
  ...

Full name: System.String

--------------------
String(value: nativeptr<char>) : unit
String(value: nativeptr<sbyte>) : unit
String(value: char []) : unit
String(c: char, count: int) : unit
String(value: nativeptr<char>, startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int) : unit
String(value: char [], startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int, enc: Text.Encoding) : unit
val concat : sep:string -> strings:seq<string> -> string

Full name: Microsoft.FSharp.Core.String.concat
val boolsToString : (bool [] -> string)

Full name: FsEmulation.Utilities.boolsToString
val parseFile : path:string -> string list list

Full name: FsEmulation.Utilities.parseFile
val path : string
type File =
  static member AppendAllLines : path:string * contents:IEnumerable<string> -> unit + 1 overload
  static member AppendAllText : path:string * contents:string -> unit + 1 overload
  static member AppendText : path:string -> StreamWriter
  static member Copy : sourceFileName:string * destFileName:string -> unit + 1 overload
  static member Create : path:string -> FileStream + 3 overloads
  static member CreateText : path:string -> StreamWriter
  static member Decrypt : path:string -> unit
  static member Delete : path:string -> unit
  static member Encrypt : path:string -> unit
  static member Exists : path:string -> bool
  ...

Full name: System.IO.File
File.ReadAllLines(path: string) : string []
File.ReadAllLines(path: string, encoding: Text.Encoding) : string []
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val s : string
String.Split(params separator: char []) : string []
String.Split(separator: string [], options: StringSplitOptions) : string []
String.Split(separator: char [], options: StringSplitOptions) : string []
String.Split(separator: char [], count: int) : string []
String.Split(separator: string [], count: int, options: StringSplitOptions) : string []
String.Split(separator: char [], count: int, options: StringSplitOptions) : string []
type StringSplitOptions =
  | None = 0
  | RemoveEmptyEntries = 1

Full name: System.StringSplitOptions
field StringSplitOptions.RemoveEmptyEntries = 1
String.Trim() : string
String.Trim(params trimChars: char []) : string
val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
val createMap : matrix:'a list list -> cols:string list -> Map<string,'a> list

Full name: FsEmulation.Utilities.createMap
val matrix : 'a list list
val cols : string list
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val row : 'a list
val rest : 'a list list
val mapi : mapping:(int -> 'T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.mapi
val x : 'a
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val ofSeq : elements:seq<'Key * 'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.ofSeq
val executeTests : path:string -> func:(Map<string,string> -> bool) -> string

Full name: FsEmulation.Utilities.executeTests
val func : (Map<string,string> -> bool)
val data : string list list
val testData : Map<string,string> list
val tail : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.tail
val head : list:'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.head
val execute : (('a -> bool) -> 'a list -> int -> string)
val func : ('a -> bool)
val testData : 'a list
val num : int
val case : 'a
val rest : 'a list
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
val andTest : case:Map<string,string> -> bool

Full name: FsEmulation.Utilities.andTest
val case : Map<string,string>
val IncTest : case:Map<string,string> -> bool

Full name: FsEmulation.Utilities.IncTest
val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray
val toBinary : i:int -> int []

Full name: FsEmulation.Utilities.toBinary
val convert : (int -> int list -> int list)
val acc : int list
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val flipBits : b:seq<int> -> int []

Full name: FsEmulation.Utilities.flipBits
val b : seq<int>
val convert : (int list -> int list -> int list)
val b : int list
val h : int
val t : int list
val ofSeq : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
val padBits : length:int -> bits:int array -> int []

Full name: FsEmulation.Utilities.padBits
val length : int
val bits : int array
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val padding : int []
property Array.Length: int
val concat : arrays:seq<'T []> -> 'T []

Full name: Microsoft.FSharp.Collections.Array.concat
val toTwosCompliment : i:int -> b:int -> int []

Full name: FsEmulation.Utilities.toTwosCompliment
val b : int
val abs : value:'T -> 'T (requires member Abs)

Full name: Microsoft.FSharp.Core.Operators.abs
val toBase10 : b:int [] -> int

Full name: FsEmulation.Utilities.toBase10
val b : int []
val convert : (int list -> float -> float -> float)
val i : float
val acc : float
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val toDecimal : b:int -> binary:int array -> int

Full name: FsEmulation.Utilities.toDecimal
val binary : int array
module tests

from FsEmulation
module Utilities

from FsEmulation
val a : bool []

Full name: FsEmulation.tests.a
val b : bool []

Full name: FsEmulation.tests.b
val result : int

Full name: FsEmulation.tests.result
val negative : bool []

Full name: FsEmulation.tests.negative
val negativePlus1 : int
val using : resource:'T -> action:('T -> 'U) -> 'U (requires 'T :> System.IDisposable)

Full name: Microsoft.FSharp.Core.Operators.using
Previous Post Next Post