Posted on

Simulating an ALU in F#

Simulating an ALU in F#

I’m a rank beginner with F#, and I was looking for a fun way to get started. The usual tutorials seemed a little stale. Then it occurred to me that logic gates could be modeled as functions pretty easily. Why not practice F# by writing some functions that mimic the behavior of logic gates?

Project setup

The first step is to set up the project. After creating a root directory for it, I set up a .NET project as follows. This was done on a Mac running OS X, so the commands are Unix-style, not Windows-style, even though it’s a .NET project.

cd alu-simulator
dotnet new sln
mkdir AluSimulator
cd AluSimulator
dotnet new classlib -lang F#
cd ..
mkdir AluSimulator.Tests
cd AluSimulator.Tests
dotnet new xunit -lang F#
dotnet add reference ../AluSimulator/AluSimulator.fsproj
cd ..
dotnet sln add AluSimulator/AluSimulator.fsproj
dotnet sln add AluSimulator.Tests/AluSimulator.Tests.fsproj

The dotnet tooling generates a test module with a single test case that verifies “true” is equal to “true”. Before making any changes to the generated artifacts, I executed the test:

cd AluSimulator.Tests
dotnet test

The result was:

Starting test execution, please wait...
[xUnit.net 00:00:00.7848420]   Discovering: AluSimulator.Tests
[xUnit.net 00:00:00.8971050]   Discovered:  AluSimulator.Tests
[xUnit.net 00:00:00.9605580]   Starting:    AluSimulator.Tests
[xUnit.net 00:00:01.1406990]   Finished:    AluSimulator.Tests

Total tests: 1. Passed: 1. Failed: 0. Skipped: 0.
Test Run Successful.
Test execution time: 2.2101 Seconds

You might wonder why anyone would bother running a test case like that. When you have a new setup for a greenfield project, the first thing you want to do is make sure the tools are configured properly. If that trivial test case had not run, it would mean I’d made a mistake in setting up the project.

We don’t want to lay down a lot of code only to have a problem, and not be able to see the cause immediately. So, we check everything as we go along, in very small steps.

NAND gate

Where shall we begin? Do we need a comprehensive up-front design? I don’t think so, in this case. The construction of logical units out of logic gates is a solved problem. All we have to do is look up some documentation and examples.

We’ve all had a little exposure to basic computer science, either through school or experience or general interest, so we know all the various Boolean logical operations can be built as simple circuits known as “gates.” Each type of gate is named for the logical operation it implements, such as AND and XOR and so forth.

We may or may not remember (but can find out quickly enough) that the NAND and NOR gates are the universal gates, because all the others can be built using one of these as building blocks. Of the two, NAND is the simpler. So, let’s begin our exploration of F# by writing a function that simulates a NAND gate. Wikipedia happens to have a nice writeup about NAND gates and another description of NAND logic we can use as guides.

Of course, we want to test-drive our code. That goes without saying. (Yes, I know; I said it anyway.)

Here’s the MIL/ANSI symbol for a NAND gate:

It has two inputs and one output. According to our documentation, when both inputs are true, the output is false. Otherwise, the output is true. Here’s a truth table from Wikipedia showing this behavior:

From this, we know the behavior we want our function to exhibit, and we can write microtest cases to assert that behavior. Those microtests will help us write the appropriate code.

At this point I wasn’t sure whether it made more sense to use true/false or 1/0 for the values. I chose to start with true/false and see how things went. When we start combining our “gates” we might decide to change this.

This is one of the handy things about test-driven development: Because we work in very small steps and we can always tell when something isn’t working as expected, it’s relatively easy to change gears when it becomes necessary.

I removed the generated test case and added a reference to the AluSimulator project, and wrote this initial test case:

namespace AluSimulator.Tests

module Tests = 

    open System
    open Xunit
    open AluSimulator

    []
    let ``nand outputs true when input A is false and input B is false`` () = 
        Assert.True(ALU.nand false false)

The result was:

Build started, please wait...
/Users/neopragma/.../alu-simulator/AluSimulator.Tests/Tests.fs(9,18): 
  error FS0039: The value or constructor 'nand' is not defined. 
  Maybe you want one of the following:   
    nan   nanf [/Users/neopragma/.../alu-simulator/AluSimulator.Tests/AluSimulator.Tests.fsproj]
/Users/neopragma/Documents/projects/alu-simulator/AluSimulator.Tests/Tests.fs(9,5): 
  error FS0041: A unique overload for method 'False' could not be determined based on type information 
  prior to this program point. A type annotation may be needed. Candidates: 
    Assert.False(condition: Nullable<bool>) : unit, 
    Assert.False(condition: bool) : unit 
  [/Users/neopragma/.../alu-simulator/AluSimulator.Tests/AluSimulator.Tests.fsproj]

I could tell two things from this output. First, it appears that the initial test case failed for “the right reason,” as I haven’t written a function named nand yet. Second, I think I’m going to like the helpful error messages generated from this tool.

But after I defined the nand function, the test runner still did not seem to be able to find it. Eventually I saw that the file AluSimulator.fsproj contained the following specification:

  <ItemGroup>
    <Compile Include="Library.fs" />
  </ItemGroup>

I had written my code in a file named ALU.fs. The file Library.fs was a boilerplate sample file generated by the dotnet tooling. After changing the specification to this:

  <ItemGroup>
    <Compile Include="ALU.fs" />
  </ItemGroup>

the test case ran successfully. I fleshed out the remaining behaviors, and had my first simulated logic gate!

The microtests:

namespace AluSimulator.Tests

module Tests = 

    open Xunit
    open AluSimulator

    [<Fact>]
    let ``nandGate outputs true when input A is false and input B is false`` () = 
        Assert.True(ALU.nandGate false false)

    [<Fact>]
    let ``nandGate outputs true when input A is true and input B is false`` () = 
        Assert.True(ALU.nandGate true false)

    [<Fact>]
    let ``nandGate outputs true when input A is false and input B is true`` () = 
        Assert.True(ALU.nandGate false true)

    [<Fact>]
    let ``nandGate outputs false when input A is true and input B is true`` () = 
        Assert.False(ALU.nandGate true true)
 

The production code:

namespace AluSimulator

module ALU =

    let nandGate a b = not (a && b)

The test run:

Starting test execution, please wait...
[xUnit.net 00:00:00.8010060]   Discovering: AluSimulator.Tests
[xUnit.net 00:00:00.9126970]   Discovered:  AluSimulator.Tests
[xUnit.net 00:00:00.9685550]   Starting:    AluSimulator.Tests
[xUnit.net 00:00:01.1716740]   Finished:    AluSimulator.Tests

Total tests: 4. Passed: 4. Failed: 0. Skipped: 0.
Test Run Successful.
Test execution time: 2.4115 Seconds

NOT gate

Well, I’m excited now. I just test-drove my very first F# function. What’s next? I’m thinking a NOT gate. What do you think? Yeah? Okay, cool. NOT gate, it is.

It would be pretty simple to write a function to mimic the behavior of a NOT gate. It might look something like this:

    let notGate a = not a

But that’s not the game. We’re building an ALU simulator. If we were building an ALU in hardware, we’d most likely make all the logic gates out of NAND gates, like this project and many others like it.

Here’s a representative example of the kind of hardware component we’re talking about: A single two-input NAND gate from Texas Instruments. There are many other products like this. All the other logic gates can be constructed by wiring these together in different ways.

I think it would be fun to duplicate that process in software.

Consulting the official Wikipedia documentation, we learn this is how to make a NOT gate out of NAND building blocks:

From that, we can see the behavior we want the NOT gate to exhibit. Let’s express that behavior in the form of microtests:

 
    [<Fact>]
    let ``notGate outputs false when input A is true`` () =
        Assert.False(ALU.notGate true)
    
    [<Fact>]
    let ``notGate outputs true when input A is false`` () =
        Assert.True(ALU.notGate false)

Okay, you’re right. My bad. It’s not good TDD form to write two failing tests before writing any code. It’s supposed to be one at a time. I’m skipping ahead a bit in the interest of space. It’s only a blog post, you know.

Anyway, long story short, the tests failed for the right reason, and I wrote the following code to make them pass:

   let notGate a = nandGate a a

That code is nothing more than the picture from the Wikipedia article written as text.

AND gate

Don’t worry, I’m not going to step through every single gate function in excruciating detail. We’ve established the pattern we’ll follow to code all the remaining logic gates. But the AND gate is an interesting case. If we were doing a pure software thing, the andGate function would be pretty simple:

    let andGate a b = a && b

But to build this out of NAND gates, it looks like this:

Driving from these microtest cases:

    [<Fact>]
    let ``andGate outputs true when input A is true and input B is true`` () =
        Assert.True(ALU.andGate true true)
    
    [<Fact>]
    let ``andGate outputs false when input A is true and input B is false`` () =
        Assert.False(ALU.andGate true false)
    
    [<Fact>]
    let ``andGate outputs false when input A is false and input B is true`` () =
        Assert.False(ALU.andGate false true)
    
    [<Fact>]
    let ``andGate outputs false when input A is false and input B is false`` () =
        Assert.False(ALU.andGate false false)

I came up with the following implementation:

   let andGate a b = nandGate (nandGate a b) (nandGate a b)

To a software person, that loooks pretty convoluted. If we were building this in hardware, it would make a lot of sense to build it this way.

Better test cases?

At this point, something is starting to happen that often happens when we use a test-driven approach to development. We’ve accumulated several microtest cases that look very similar to one another. We’re starting to wonder whether we can simplify the tests.

So far, we’ve been writing example-based cases. When the code under test handles various combinations of inputs in a consistent way to produce deterministic results, it’s often helpful to write data-driven cases. Here’s how the examples for the addGate function can be re-cast as data-driven cases:

    [<Theory>]
    [<InlineData(true, true, true)>]
    [<InlineData(true, false, false)>]
    [<InlineData(false, true, false)>]
    [<InlineData(false, false, false)>]
    let ``andGate implements AND logic`` a b q =
        Assert.Equal(q, ALU.andGate a b)

At this point, I went back and changed the example-based cases to data-driven cases. I think it made for a simpler pattern to follow when building the remaining logic gate functions.

Half Adder

If we can make an ALU out of NAND gates, then what’s the point of building all the other types of logic gates? Maybe not much, for purposes of this exercise. Let’s go ahead and make something out of our NAND gates.

A half adder is a circuit that performs binary addition of two bits. There’s a nice write-up on Electronics Hub that explains various ways to combine logic gates to build a half adder, and how to make a full adder by combining two half adders.

A half adder takes two input bits, A and B, and produces two output bits, the Sum and the Carry bit. We can model that behavior in software with a function that takes two boolean arguments and produces a tuple containing two boolean values. We can summarize the behavior in a truth table (this image borrowed from the Electronics Hub article cited above):

We can express that behavior in Xunit test cases as follows:

    [<Theory>]
    [<InlineData(false, false, false, false)>]
    [<InlineData(false, true, true, false)>]
    [<InlineData(true, false, true, false)>]
    [<InlineData(true, true, false, true)>]
    let ``halfAdder adds two bits to produce a sum and carry bit`` a b (sum, carry) =
        let result = ALU.halfAdder a b 
        Assert.Equal(sum, fst result)
        Assert.Equal(carry, snd result)

where the first two values are the input bits, the third value is the sum, and the fourth value is the carry bit.

You need five NAND gates to build a half adder, and my implementation code mirrors that in a naive way.

    let halfAdder a b = 
        let u1 = nandGate a b
        let u3 = nandGate a u1
        let u4 = nandGate b u1
        let sum = nandGate u3 u4
        let carry = nandGate u1 u1
        sum, carry

I suspect someone who had more than 90 minutes experience with F# could do the same thing in a more concise and idiomatic way. As for me: I was happy to get to green. Simple pleasures, and all that.

Full Adder

A half adder only works for single-digit binary numbers. To handle longer numbers, we need to consider the carry bit resulting from the addition of each bit in the number. That’s what a full adder does. It takes three inputs: A, B, and the carry bit from the previous operation. It produces two outputs: The sum and the carry bit. You need one of these for each bit in your architecture; so, for an 8-bit architecture, you need eight full adders.

There’s more than one way to build a full adder. Let’s stick with our plan to make everything out of NAND gates. Here’s the truth table for a full adder. Thanks again to the Electronics Hub article for the image.

The truth table lays out the behavior that we want to see from our full adder function. Let’s express that behavior as an Xunit test case.

    [<Theory>]
    [<InlineData(false, false, false, false, false)>]
    [<InlineData(false, false, true, true, false)>]
    [<InlineData(false, true, false, true, false)>]
    [<InlineData(false, true, true, false, true)>]
    [<InlineData(true, false, false, true, false)>]
    [<InlineData(true, false, true, false, true)>]
    [<InlineData(true, true, false, false, true)>]
    [<InlineData(true, true, true, true, true)>]
    let ``fullAdder adds two bits and considers the previous carry bit`` a b c (sum, carry) =
        let result = ALU.fullAdder a b c
        Assert.Equal(sum, fst result)
        Assert.Equal(carry, snd result)

Building this naively based on the block diagram in the article, we have the following implementation:

    let fullAdder a b c = 
        let u1 = nandGate a b
        let u3 = nandGate a u1
        let u4 = nandGate b u1
        let sum1 = nandGate u3 u4
        let u5 = nandGate sum1 c
        let u6 = nandGate sum1 u5
        let u7 = nandGate u5 c 
        let sum = nandGate u6 u7
        let carry = nandGate u1 u5 
        sum, carry 

Full Adder with OR Gate

Now we have a half adder and a full adder, all made from NAND gates. But we could make a full adder by connecting two half adders, if we had an OR gate. Let’s test-drive an OR gate function and try that approach.

This Wikipedia article shows how to make an OR gate from NAND gates:

That leads us to this test case:

    [<Theory>]
    [<InlineData(false, false, false)>]
    [<InlineData(true, false, true)>]
    [<InlineData(false, true, true)>]
    [<InlineData(true, true, true)>]
    let ``orGate implements OR logic`` a b q =
        Assert.Equal(q, ALU.orGate a b)

Implementing the OR gate with NAND gates looks like this:

    let orGate a b = nandGate (nandGate a a) (nandGate b b)

Now armed with an OR gate, we can wire two half adders together to make a full adder, as described here:

    let fullAdder a b c = 
        let result1 = halfAdder a b
        let sum1 = fst result1
        let carry1 = snd result1
        let result2 = halfAdder sum1 c
        let carry2 = snd result2 
        let carry = orGate carry1 carry2
        let sum = fst result2 
        sum, carry    

That implementation is slightly simpler and cleaner than the first, although still pretty naive. A good F# programmer could do better. Anyway, I enjoyed getting my feet wet with these tools.

Not much of an ALU

Fortunately, there isn’t really a hard-and-fast definition of what functionality must be present before we can call something an ALU. We can declare victory at this point, for immediate purposes.

We’ve written code that mimics the behavior of a very basic ALU built entirely of NAND gates. We’ve done:

  • Half Adder
  • Full Adder

I leave it as an exercise for the reader to build one of these…if you dare.

By the way, here’s the code, in case you’re interested: https://github.com/neopragma/alu-simulator.

Posted on

TDD: Let the Tests Drive

As long as we write tests, what’s the big deal about writing them “first” rather than “last?” Let’s explore that question.

The video looks a lot better on YouTube than it does here. Try https://youtu.be/Bf89rd0o5-0.

When we’re conscientious about writing examples before production code, and we drive all our production code from executable examples, we can enjoy several benefits:

  1. Helps us remember details and not overlook things
  2. Helps us avoid over-engineering or going too far with our design
  3. Helps us keep the design simple
  4. Provides a safety net for experimenting with different implementations
  5. Provides a safety net for refactoring
  6. Gives us frequent positive feedback so we don’t feel beaten down at the end of the day
  7. Provides executable low-level documentation of everything the application does
  8. Makes it easier to locate the source of bugs; keeps us out of the debugger for the most part
  9. Creates a regression test suite as a side-effect of writing the examples that drive the design
  10. Equally useful for emergent design and up-front design, and for greenfield development as well as enhancements and bug fixes
Posted on

Looking at TDD through a lean-agile lens

It’s a commonplace to say there is no “silver bullet,” and everything we do in the software field has to take context into consideration. In fact, this is quite true. TDD is a useful technique to know. To know TDD well, you must understand why and when it is useful, and how to do it correctly. If you apply TDD for the wrong reasons, in the wrong places, or in the wrong way, then it will not yield any value.

Many of the complaints people raise about TDD and about unit testing in general boil down to a misunderstanding or a misapplication of practices. Some complaints, however, are completely valid. You have to make your own professional judgments about such matters. To be equipped to make such judgments, you need to understand how TDD can add value in your work; and when it will not.
Continue reading Looking at TDD through a lean-agile lens

Posted on

Bringing TDD and automated testing to the mainframe platform

Can contemporary lightweight software development and delivery methods “scale” in large enterprises without appropriate support for the venerable IBM mainframe platform? Thought leaders in the “agile” community seem to think so. For example, this proposed session on code isolation and automated testing for mainframe applications received almost no notice from the review team for the Agile 2015 conference. The two reviewers who noticed the submission seemed not to understand what it was about, or to see any relevance or usefulness in it.

It’s true that some large enterprises don’t have mainframe technology. Apple, Google, Amazon, and a handful of others built their businesses in an era when alternatives to the mainframe were plentiful. Those companies tend to be relatively uninterested in “agile” and “lean” methods, as they have come up with their own ways of doing things, and their financial position doesn’t lead them to believe they need to change. They’re probably right. If they were “dysfunctional” they probably wouldn’t be doing quite so well financially…a minor detail often overlooked by enthusiastic change agents.

However, the majority of larger enterprises have been around for decades. They have used computer technology all those years. The general pattern has been to layer new technologies on top of old rather than to migrate applications. Name a large bank or insurance firm that doesn’t have a significant investment in mainframe systems. Now explain how you would bring agility to those organizations just by setting up a few Scrum teams, applying good technical practices only to the outermost layer of their technology stack, and ignoring technical practices and tooling on the mainframe platform.

Continue reading Bringing TDD and automated testing to the mainframe platform

Posted on

TDD and software archaeology

Can you tell by looking at the unit test cases whether the code’s author wrote the tests first? During a TDD class I taught last week, one of the participants suggested that you can’t tell. Completed code and unit tests would look the same regardless of which had been written first. At the time I didn’t give the comment much thought.

I returned to the team I was working with at another client on Thursday, the last day of their iteration cycle. I picked up a small story so I could contribute something before the end of the day. It was a bug fix for JavaScript input validation logic in a webapp. Like many applications, this one uses date ranges to activate and deactivate certain data values that drive functionality. In this case, the input validation function neglected to ensure the expiration date was later than the effective date. Continue reading TDD and software archaeology

Posted on

The right kind of lazy

I consider test-driven development (TDD) to be a basic software development technique. I’ve used it in a wide range of circumstances for different types of applications in different domains based on different languages and tools. I coach people in using the technique, I run workshops at conferences on it, and I offer a two-day training class on it.

My only regret is that I didn’t learn about TDD earlier in my career. All those years doing things the hard way…time lost forever. Oh, well.

I use TDD and I like it, but I never try to “convince” anyone that they should use it, or even that it works well. I never suggest that TDD is a “goal” for an individual or for a team. TDD might help you achieve some other goal, but it isn’t a goal in itself. It’s just a technique.

And, let’s face it, nearly all the code in production today, worldwide, was developed without TDD. Nearly all the code under development right now is being developed without TDD. Clearly, programmers can get along without it.
Continue reading The right kind of lazy