Static Single Assignment

In this section we're going to look at the serial execution model of a normal programming languages versus single assignment in a spreadsheet.

Spreadsheets do not have if-then-else statements, but it is possible to rewrite a program loop so that it uses conditional assignment in place of if statements. The counter in the previous article is a good example. You could compute the next value without an if statement using:

    count = (count == 9) ? 0 : count + 1;

From a Sequential Program to a Moore State Machine
Pretty much all programmers today assume a sequential execution of their program. Programmers break a problem into a series of program steps and then sequentially execute each of these steps. The problem we face going to a Moore state machine approach is that we now want to use conditional assignments to update all of the state variable at once on each iteration through the sheet. This makes conversion to Verilog easy but designing a spreadsheet program might be challenging to most programmers.

As an example, let's consider the Towers of Hanoi puzzle. We'll solve it as a normal sequential program and then resolve it as if it were one big Moore state machine. While the puzzle itself is not important, the steps to convert it to a spreadsheet are.

The Towers of Hanoi puzzle can be solved iteratively using three rules. Number the pieces and then:
- Move odd numbered pieces clockwise
- Move even numbered pieces counterclockwise
- Never move the same piece twice in a row

The C program inttoh.c has a straightforward iterative solution to the puzzle. The three puzzle stacks are modeled as three integers where each bit indicates the presence or absence of a disk on the stack. Imagine the bits of an integer arranged vertically next to the disks in the above picture. Bit 0 is the top disk and bit 1 is the second disk. In the picture above bit 7 represents the bottom disk. Moving a disk means clearing the appropriate bit in the source stack and setting the bit in the destination stack. The top-of-stack variable is a bit mask. That is, if disk #2 is the top of stack A then tosa would be 0x04. The last move is not encoded in the stack integers so it needs a separate state variable. The state variables are:

    uint32_t A, B, C;               // stacks as integers
    uint32_t tosa, tosb, tosc;      // bit set at location of LSB
    uint32_t last;                  // last piece moved

The inttoh.c program approaches the solution sequentially in that at each step we consider each stack and for each stack can we move the top piece clockwise or counterclockwise. There are three stacks and two directions so the program needs to consider six possibilities. ANDing with EVENMASK (0x55) returns non-zero if an even numbered bit is set. The first of the six possibilities is shown below.

    //   If the tosa is even and tosa is smaller than tosb then move tosa clockwise: A->B->C->A
    if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last)) {
        printf("Move %d from A to B\n", tosa);  // Printing bit mask, not disk #
        B |= tosa;           // put disk on stack B
        tosb = tosa;         // set top-of-stack B
        last = tosa;
        A &= ~tosa;          // remove disk from A
        tosa = gettos(A);    // get new top-of-stack of A
    }

Similar code is executed for all six possibilities.

    if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last)) { // A->B
    else if ((tosa & ODDMASK) && (tosc > tosa) && (tosa != last)) {  // A->C
    else if ((tosb & EVENMASK) && (tosc > tosb) && (tosb != last )) {  // B->C
    else if ((tosb & ODDMASK ) && (tosa > tosb) && (tosb != last)) {  // B->A
    else if ((tosc & EVENMASK) && (tosa > tosc) && (tosc != last)) {  // C->A
    else if ((tosc & ODDMASK) && (tosb > tosc) && (tosc != last)) {  // C->B

The last test is not really necessary since there is always exactly one move available.

The first step in the conversion is to replace any nested if statements with their non-nested equivalents. For example:

    if (something) {
        if (xxx) {
            do_this()
        }
        else if (yyy) {
            do_that()
        }
    }

The above code would be replaced by:

    if (something && xxx) {
        do_this()
    }
    else if (something && yyy) {
        do_that()
    }

The Towers of Hanoi program did not use nested if statement so this step is not needed.

The next step is to add shadow variables for all of the state variables in the program. In this example an 's' is prepended to the state variables to indicate a shadow variable. Replace all the left-hand-side assignment targets with their shadow equivalents. Do not change the right-hand-side of the assignments. The first section given above now becomes:

    //   If the tosa is even and tosa is smaller than tosb then move tosa clockwise: A->B->C->A
    if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last)) {
        printf("Move %d from A to B\n", tosa);  // Printing bit mask, not disk #
        sB |= tosa;           // put disk on stack B
        slast = tosa;
        sA &= ~tosa;          // remove disk from A
    }

At the bottom of the loop, after all the assignments are done, copy the shadow values to the visible values.

    A = sA;
    B = sB;
    C = sC;
    tosa = gettos(A);    // get new top-of-stack of A
    tosb = gettos(B);    // get new top-of-stack of B
    tosc = gettos(C);    // get new top-of-stack of C
    last = slast;

Note that "top of stack" in the iterative solution is used to simplify the code. The top-of-stack variables are not really state variables in that you can directly derive the top-of-stack by just examining the stack itself. We keep the TOS variables for now but will remove them completely before we are done.

You might want to compile and test the modified code smtoh0.cat this point. It should give output identical to the original code.

The next step is to remove if blocks by adding the if condition to each assignment withing the block. For example, consider the program block that move the top of A to stack B:

        if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last)) {
            printf("Move %d from A to B\n", tosa);
            sB |= tosa;           // put disk on stack B
            slast = tosa;
            sA &= ~tosa;          // remove disk from A
        }

The above code is replaced by four if statements:

        if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last))
            printf("Move %d from A to B\n", tosa);
        if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last))
            sB |= tosa;           // put disk on stack B
        if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last))
            slast = tosa;
        if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last))
            sA &= ~tosa;          // remove disk from A

Each of the assignment statements now has a qualifying ifstatement. Rearrange the if statements to group together all of the assignments for a variable. For example the if statements assigning a value to variable sA are:

        if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last))
            sA &= ~tosa;          // remove disk from A
        if ((tosa & ODDMASK) && (tosc > tosa) && (tosa != last))
            sA &= ~tosa;          // remove disk from A
        if ((tosb & ODDMASK ) && (tosa > tosb) && (tosb != last))
            sA |= tosb;           // put disk on stack A
        if ((tosc & EVENMASK) && (tosa > tosc) && (tosc != last))
            sA |= tosc;           // put disk on stack A

The above is now in a form that let's you easily write a conditional assignment for sA:

The program smtoh.c has state machine solution that was obtained by simplifying and reducing the logic in the non-SM solution. You will see this program again when we get to an actual spreadsheet implementation.

Choosing state variables is always important to program design but it is particularly important to spreadsheet state machines. As an example, consider what the program would be if we had not used stacks but instead tied a stack ID to each puzzle piece. This "piece focused" approach would give an entirely different design.