abc
Cycles: 0

The Waterfall Model Online

The Waterfall Model is a programming language designed to be very easy to implement, even on many platforms that hardly seem programmable. Making it as easy as possible to write implementations of the language is the only consideration behind its design; in particular, the resulting language is low-powered, inefficient, and hard to write; proudly so, in fact!

This page, The Waterfall Model Online, consists of a description of the language, a tutorial, and several programs; more importantly, though, it contains an interpreter for the language. You can try out the example programs or write your own.

Specification

A program in The Waterfall Model stores data in a number of unbounded integers, called waterclocks. There is no "main function" or "entry point" where the code starts running; rather, whenever a waterclock becomes 0, it causes a piece of code attached to the waterclock to run (and this is the only way code can run).

The code that runs when a waterclock zeroes is very simple; all it can do is to increase the values on the waterclocks by a fixed amount. For example, you could write code of the form "when the second waterclock becomes 0, add 5 to the second waterclock and 8 to the third waterclock". It is normally mandatory for a waterclock to increase its own value when it zeroes, so that none of the waterclocks can become zero for more than an instant. As an exception, a waterclock can halt the program when zeroed; this is indicated via "increasing every waterclock by 0".

If the program's code can only increase waterclocks, how do they decrease? The answer is that they decrease automatically over time; the implementation repeatedly subtracts 1 from every waterclock whenever nothing else is happening. Because they all reduce at the same rate, this means that the smallest will zero itself first.

In order to keep implementations as simple as possible, programs must be written to ensure that two waterclocks never become zero simultaneously.

Syntax

In order to actually write down a program in The Waterfall Model, we need a syntax for it. Programs are normally represented as a square matrix, like this one:

10 3 3 3
1 3 0 6
2 6 3 0
3 0 9 3

The first row of the matrix specifies limits, to help implementations know how much memory to allocate. The top-left corner is a number that's bigger than any other number in the matrix (indicating how big values can go); the entire rest of the top line repeatedly specifies the number of waterclocks (indicating how big the rest of the matrix is).

Each row other than the first defines a waterclock. The first element specifies its initial value (i.e. the value it has at the start of the program). The remaining elements specify the amount that each waterclock increases by when this waterclock zeroes. (The waterclocks are specified in the same order that they're defined, so the amount by which the waterclock increases itself when it zeroes will be on the main diagonal.)

You can hover your mouse over cells of the matrix above to get a description of what they do, or click on it to try the program out. (The colors aren't part of the program, they're just syntax highlighting; lilac for the limits row, yellow for initial values, white for code.)

Syntax as text

The Waterfall Model is designed to run on computing devices so simple and/or weird that they have no concept of a file; that's why the matrix syntax is used (and some of these systems may wish to invent their own syntax instead!). However, when running the language on a more powerful computer, you might want to store the matrix that represents the program in a file. (Likewise, programs like the interpreter on this page need to allow the program to be typed in somehow.)

The standard way to represent a program in The Waterfall Model as text is to use JSON; an array is a sequence of comma-separated values in square brackets, each row of the matrix is represented as an array of (decimal) integers, and the matrix itself is represented as an array of rows. So the program above would look like this (the whitespace is unimportant but makes it more readable):

[[10,3,3,3],
 [ 1,3,0,6],
 [ 2,6,3,0],
 [ 3,0,9,3]]

Tutorial

The Waterfall Model is a very bare-bones and low-level language. As such, programming in it is typically easier if you approach it in a disciplined way; although the language itself has only one construct, the waterclock, practical programming is made much easier to think about by restricting the use of each waterclock to only a subset of its functionality. In other words, using each waterclock in only a restricted way makes it easier to understand what states your program can be in, and thus to track the program's behaviour.

There are plenty of ways you could do this, but this tutorial will focus on one particular method of writing programs (which might or might not be "best", but is one of the easiest to explain and to learn). In this tutorial, each waterclock in each program will be used only for one of the following two purposes:

  1. Data storage. Some waterclocks are used like variables in imperative programming languages; they're used to store numbers, acting as the RAM of the system.

    One thing we can't do here is to store the number directly, because it's impossible to differentiate between two adjacent values without ending up with the risk of a simultaneous zeroing; the various values have to be at least 2 apart, so we need to use an encoding. In this tutorial, we write programs using the following encoding for their data storage:

    • 0 is encoded as 3;
    • 1 is encoded as 5;
    • 2 is encoded as 7;
    • and in general, x is encoded as 2x+3.
  2. Program storage. We also need to store the commands our program is running somehow; because a program is made entirely of waterclocks, those also need to be stored using waterclocks. The program storage effectively makes up the ROM of the system (a fixed program that doesn't change – the program isn't self-modifying), using the code attached to the waterclocks.

    Of course, the waterclocks themselves have values; they have to have values, or else the attached code would never run. We use the program storage waterclocks' values to record where in the program we are; immediately after a zeroing, most of these will have the value 3, but the waterclock for the currently running command will have the value 2. (Note that later on in the tutorial, we'll see some exceptions to this rule, but those will be pointed out; this version of the rule will suffice for now.)

Now that we have a basic framework in place, let's start looking at some building blocks with which we can write programs.

Halting

The very simplest thing we can do in the program is to halt. By convention, this is done using a waterclock which does not increase anything (not even itself). We only need one waterclock to write this program:

31
20

(You can click on this program, and indeed on any program on this page, to load it into the interpreter.)

This program has only one waterclock (the second row of the matrix), representing a halt command (all zeroes, except the first column) that's about to run (there's a 2 in the first column). When we run it, the 2 reduces to 0 and then the program halts, as expected. (I'm using a syntax highlighting style in which halt rows are coloured in red, although they could alternatively be recognised by their unusual all-zeroes composition.)

It's worth looking into why this happened: the reason why the active command's waterclock zeroed first is that it had the lowest value among all waterclocks (unsurprisingly, as there's only one waterclock). As long as the rules of our encoding are followed, the lowest possible value for a waterclock to have following a zeroing is 2, and the active command always has a value of 2, which is how we ensure that it's the active command that runs. As (in this case) that command halts the program, we don't need to make sure of anything else; at that point, it doesn't matter what happens to the other waterclocks as the program will have ended already.

No-op (goto)

Slightly less simple than a command that halts is a command that does nothing. This is more complex in two ways.

First, we need to transfer control to the next command manually. Many programming languages have a rule like "after one command runs, the next command runs automatically", but we have no such luxuries in The Waterfall Model. So although we're thinking of a "command that does nothing", it actually acts more like a goto statement; because we're transferring control manually, we can choose where to transfer it to.

Second, because we aren't halting the program (but rather, are continuing to run it), we'll have to undo any unwanted side effects of the command. The biggest potential issue is that because the value of the command's waterclock starts at 2, but we have to let it tick down to 0 before the command runs, that effectively causes every waterclock to be reduced by 2 as a side effect, and we're going to need to undo that.

Let's look at these two problems together. In order to transfer control to another command, meaning that this command is no longer running, we need to restore our own waterclock to 3 (simple enough), and decrease the waterclock of the command we're jumping to from 3 to 2. The rules of The Waterfall Model don't allow us to write decreases, but luckily, everything decreases by 2 while the command is ticking down to zero, so instead of writing a decrease, all we have to do is to not cancel out that decrease; we specify an increase of 1, so that the decrease is only partially cancelled out, leading to a net decrease of 1. Meanwhile, every waterclock other than the one we want to decrease has to be increased by 2, restoring it to its original value.

As an example, we can use the rules above to write a short program that runs three no-op commands and then halts:

54444
23122
32312
32231
30000

The 2s in the matrix above are effectively showing a situation where one waterclock has no net influence on another, so I've greyed them out to make it easier to focus on the cells that actually do something.

Add constant

When we have no data in our program, halts and jumps are the only commands we can write, but they don't make for useful programs on their own. Let's look at some ways we can manipulate data.

The simplest thing we can do to a RAM element is to add a constant to it; for example, we could increment it by adding 1, or we could add a large number as a way to allow us to store that number in our program ROM. We can do this with a command that's very similar to our no-op command, but adds to a RAM value as a side effect.

This is easiest to see as an example. Let's take our program of three no-ops, and modify them to add 1, 2, and 3 respectively to a variable that starts out at 4 (encoded as 11):

1255555
231224
323126
322318
300000
1111113

(For the time being, ignore the zeroing rules on the RAM waterclock. They never run anyway. I've coloured the RAM waterclock in purple so that it looks distinct from ROM waterclocks.)

To add 1, we're allowing the RAM to decrease by 2 but then increase it by 4. Likewise, adding 2 decreases by 2 and increases by 6; adding 3 decreases by 2 and then increases by 8. (In each case, the net amount of water added to the waterclock is twice the increase of the value in memory; our 2x+3 encoding requires us to add two units of water to get an increase of 1 in the value being encoded.)

On the zeroing just before the program halts (screwing up the waterclock values in the process), we can see that the value of our RAM waterclock (the last one) is at 23; that encodes 10, i.e. 4 + 1 + 2 + 3. So it looks like our arithmetic worked as desired. (If you use the "Run quickly" button to run the program, the interpreter will stop on the last zeroing before the halt, rather than on the halt itself, making it easier to see the final state of the program when running programs like this one.)

Decrement and zero-test

Adding 1 value (2 water) to a RAM waterclock (i.e. incrementing it) was a matter of increasing the adjustment on it from 2 to 4. Therefore, it might seem as though we can decrement it (i.e. reduce its value by 1) simply by reducing the adjustment on it from 2 to 0 (letting the 2 cycles spent decreasing the running ROM waterclock from to 2 to 0 produce a similar adjustment on the RAM waterclock, because we don't undo their effect afterwards).

This does work when the RAM's value is 1 or greater; it decrements by 1 without any trouble. However, what happens if the RAM's value were 0 instead? We'd end up decrementing it to −1 (i.e. there'd be 1 water in the RAM, when normally there should always be at least 3). That breaks our rule that the new current command, with value 2, should be the lowest-valued waterclock.

However, instead of looking at this as a problem, you can instead see it as an opportunity; decrementing 0 isn't really a useful operation on its own, and attempting it sends control flow to somewhere normally shouldn't and wouldn't be, so instead of purely being a decrement operation, we actually have something of a conditional here; if the value stored in RAM isn't 0, we decrement it, if it is 0, we send control into a different branch of the program. This is basically The Waterfall Model's equivalent of an if statement; either the RAM stays positive and everything continues as normally expected, or else we try to decrement zero and go onto an alternative control path.

The code run when the RAM waterclock zeroes is written in a similar way to the code that runs when a ROM waterclock zeroes. One difference is that the current "next command to run" (i.e. the command that would have run if it didn't zeroed) is still in ROM rather than RAM; thus, we need to know what that command is and to restore it to 3. (We choose a new next command to run in the same way as with ROM, reducing it from 3 to 2). A second difference is that we need to reset the value of the RAM itself (typically adding 3 to it to reset it to 3 water, encoding the value 0). Finally, the biggest difference is that the RAM waterclock will be decreasing from 1 rather than 2, so the numbers we use are different (i.e. 1 on cells we don't care about to leave them the same, 0 on the new command to run so that it reduces from 3 to 2, 2 on the command we want to cancel the execution of so that it increases from 2 to 3).

Here are two programs that demonstrate this, differing only in the initial value of a RAM waterclock:

1255555
231220
323122
300000
300000
1112103
1255555
231220
323122
300000
300000
312103

You can run each of the two programs for two zeroings to observe the difference. In the first program, the RAM waterclock starts with 11 water (encoding the number 4), so never gets close to zeroing. Thus, control passes peacefully to the second waterclock, and then halts at the third, just as though we'd never done a zero test at all. After the two zeroings, the waterclock values are at [3,3,2,3,9]; we've decremented the RAM waterclock (as desired) and the ROM waterclocks correctly encode a state where waterclock 3 is going to run next.

Meanwhile, the second program has only 3 water in its RAM waterclock, encoding the number 0, so trying to decrement it sends the program onto an alternative path. This time, the RAM waterclock's command runs, setting itself back to 3, the second waterclock back to 3 (that was the branch of the if that wasn't taken, so we need it to be in a non-running state), and letting the fourth waterclock (the branch of the if that we do want to take) run down to 2 rather than restoring it. The waterclock values are now at [3,3,3,2,3], i.e. the RAM waterclock hasn't changed (it was encoding 0, and we don't want it to encode anything lower), and the ROM waterclocks correctly encode the fact that control flow has shifted, in this case running on the fourth rather than third waterclock.

Loops and destructive addition

With the The Waterfall Model programming model used in this tutorial, each command specifies the next command to run. So far in this tutorial, that's always been the command for the next waterclock in sequence (thus leading to a pattern of 3, 1 on the main diagonal), but there's no actual reason why that should be the case; we effectively have a free goto as part of every command, meaning that we could jump to an earlier point of the program. A loop, therefore, is just a sequence of commands that all jump to each other.

The simplest possible example of a loop is a command that jumps to itself. Obviously, to prevent this trivially being an infinite loop, we need to have somewhere else we can escape to as well, meaning that the command should be a conditional, decrementing a RAM waterclock, branching to itself if the waterclock wasn't zero, and letting the RAM waterclock run (taking control elsewhere) if it was zero. This effectively means that if the command has any other side effects, they'll run a number of times equal to 1 plus the RAM waterclock's value before the loop started (the side effects also happen when the value is zero).

The simplest such side effect would be to increment a second RAM waterclock. That means that the second RAM waterclock would have 1 added to its value a number of times equal to the value of the first plus 1, i.e. we're adding the values of the first and second waterclocks together and storing that value plus 1 back into the second waterclock. Meanwhile, the first RAM waterclock has its value reduced to 0, so this is destructive addition of two waterclocks (the original values of the two waterclocks are lost, all we have afterwards is the answer).

The off-by-1 here can be annoying, so we fix it as we enter the loop; the ROM waterclock that enters the loop should decrement the loop counter in the process. This makes it possible for the loop to run zero iterations (because if the counter is already at zero, the decrement will cause control to branch to the counter itself rather than the loop body; note that the loop body will be the "active command" and that's what the counter is expecting, so it can break out of the loop before it even starts).

Here's an example of a destructive addition:

1255555
231202
322204
300000
1112031
711113
1255555
231202
322204
300000
312031
711113

In the first example above, we're adding 4 (the value of the fourth waterclock, encoded as 11) to 2 (the value of the fifth waterclock, encoded as 7). The first waterclock simply does a goto to the second, entering the loop, while decrementing the loop counter. The second then repeatedly decrements the fourth and increments the fifth, branching to itself. When the fourth waterclock finally zeroes, it tells the second waterclock to stop running (using a 2 to increment its value from 2 to 3), tells the third waterclock to start running (using a 0 to decrement its value from 3 to 2), and restores its own value back to where it should be, in addition to undoing. So just before the program halts, we have waterclock values of [3,3,2,3,15]; and the 15 on the fifth waterclock encodes 6, the correct value for 2+4.

The second example shows the same program with a different initial state, so it's now calculating 2+0. As can be seen, despite the loop not running at all, all the waterclocks are left with their correct values.

Copying and nondestructive operations

Because the only way to check the value of a variable in The Waterfall Model is to compare it to zero, reading a variable destroys its old value (as seen in the destructive addition above). Therefore, in order to be able to operate on data without forgetting it, we need to be able to make a copy.

Luckily, copying data is fairly straightforward. The idea is to use a temporary RAM waterclock that starts out at a value of 0 (i.e. containing 3 water); when we're looping on a variable (reducing it to 0), we increment that waterclock on every iteration. When the loop has finished, the temporary variable will contain the number of iterations the loop had – in other words, it'll be a copy of the initial variable.

In order to complete the nondestructive operation, we merely have to destructively add the copy back to the original. That'll set the waterclock back to the value it originally had, and the temporary waterclock back to zero, just like before the operation began.

Let's write a non-destructive version of the preceding program:

128888 8888
23122 2022
32222 2044
32231 2220
32222 2420
30000 0000
111201 1311
71111 1131
31112 0113

This is basically just two copies of the preceding program linked together (except that the first destructive add adds to two different waterclocks). The waterclocks start out at [2,3,3,3,3, 11,7,3] and, just before the halt, are at [3,3,3,3,2, 11,15,3]; as can be seen, the first RAM waterclock has had its value preserved, as has the temporary (the last RAM waterclock), and only the waterclock we were adding to has had its value changed.

Multiply by constant

After addition, the second-simplest thing we can do is to multiply a RAM waterclock by a constant. This is very similar to addition; all we have to do is to add the constant to zero, except that we increment by more than one each time round the loop. For example, here's a program that multiplies by 5:

1555555
231202
3222012
300000
1112031
311113

Our loop body (the second waterclock) increases the amount of the water in the output (the fifth waterclock) by 10 (12−2) with each loop iteration. That's equivalent to adding 5. So with our input as 11 (representing the number 4), we get an output (on the zeroing before the halt, as usual) of 43 (representing the number 20, the currect value of 4×5).

Unlike with adding a constant, the output ends up in a different waterclock from the input. You could copy it back (destructively or non-destructively) or just use it from its new location.

Divmod

We've looked at multiplication, so how about division? Because The Waterfall Model is effectively an "integer-only" setting, the most useful form of division will be a "divmod" operation that gives us the quotient and remainer at the same time; that allows us to do a division without losing information, and it's typically as easy to implement as either the division or the modulus operation on its own.

We'll use a total of four RAM waterclocks for this program. One will be the input number; two more will be the used for the quotient and remainder; and the fourth will hold the complement of the remainder (i.e. the divisor minus 1 minus the remainder; when this tries to go negative, we know that it's time to zero the remainder and add 1 to the quotient). In order to specify the divisor itself, we initialise the remainder to 0 and the complement of the remainder to the divisor minus 1 (i.e. the invariant on the complement of the remainder is used to deduce what the divisor is, rather than vice versa).

Let's look at the program while we explain how it works:

701010101010 1010101010
231222 20222
313222 22240
322312 22202
322222 22204
312223 22220
300000 00000
6912111 03111
311111 11311
311120 11131
1721011 11313

This program consists of two loops that are connected together into one larger loop. The first loop, using waterclocks 1 and 2, does the following: it decrements the dividend (on waterclock 1), then increments the remainder while decrementing the complement of the remainder (on waterclock 2).

There are two ways we could break out of this loop. One possibility is that the dividend is zero, in which case we're done. (Note that because waterclock 1 only decrements the dividend, we don't have to worry about a potential off-by-one; if we had a side effect it would run one too many times, but the only thing we're doing here is decreasing the loop counter.) The other, more interesting, possibility is that the complement of the remainder underflows; this means that we need to add 1 to the quotient and reset the remainder.

In order to do that, we use a second loop, which destructively adds the remainder back to the complement of the remainder (thus putting them back where they were). This does need a waterclock for off-by-one protection (and we need another such waterclock when going back into the main loop, too; thus, the loop is the fourth waterclock, and the third and fifth deal with the off-by-ones). The increment is done by the code for the complement's RAM waterclock while it transfers control to the second loop.

The resulting program thus is effectively translating the input number into a two-digit number in a given base by starting at zero and repeatedly adding 1; we normally just add 1 directly to the remainder (the less significant digit), but if this would overflow (i.e. we'd decrease the complement of the remainder below 0), we instead reset the remainder to 0 and add 1 to the more significant digit.

In the example program shown here, we take the number 33 (encoded as 69), and divmod it by 8 (specified by setting the waterclock representing the complement of the remainder to 17, which encodes 7). On the zeroing before the final halt, the quotient is 4 (encoded as 11), the remainder is 1 (encoded as 5), and the complement of the remainder is 6 (encoded as 15). And we indeed have the correct answer, 33÷8 = 4 remainder 1.

Note that unlike the previous programs, our "working RAM waterclocks" haven't ended up at the values at which they started, i.e. this section of program at first doesn't seem like it resets itself. However, it can in fact be reused arbitrarily many times during a program. The trick is to notice that in order to reset it, we simply need to read the quotient (destructively setting it to 0), and destructively add the remainder to the complement of the remainder (setting the remainder to 0 and the complement of the remainder to its original value). We can assume that the surrounding code reads the quotient, and there's actually already code in there that implements a destructive add (the second loop, which resets the remainder after an increment of the quotient, is implemented using one). So all we need to do is to enter the program from the third rather than first waterclock (in fact, we can do that on the first iteration too if we want, for consistency; I could have written the program like that originally, but it would have been harder to follow). Here's an example of how the same code might run the second time, from a different starting point:

661010101010 1010101010
331222 20222
313222 22240
222312 22202
322222 22204
312223 22220
300000 00000
6512111 03111
311111 11311
511120 11131
1721011 11313

Deferred goto: using code and data from multiple locations

Many of the program fragments we've looked at so far share a major issue. One problem with The Waterfall Model that has already been discussed and worked around is that, because reading a waterclock can only be done via waiting for it to become zero, reading data destroys it. The bigger problem stems from exactly the same cause, though: because reading a waterclock can only be done via waiting for it to become zero, the code that runs as a consequence must be the code that that waterclock runs when it becomes zero. That means that we can't read a RAM waterclock from two different places in the program, as we'd have to specify two different sets of code.

There's more than one potential solution to this problem. However, a particularly elegant solution is the use of "deferred goto", a technique that's useful in a wide range of situations.

A regular goto statement – i.e. reducing a ROM waterclock from 3 to 2 – transfers control to one specific statement, that's hardcoded into the statement. The idea of a deferred goto is that an earlier statement can specify which location, out of a set of potential valid locations, a later statement should transfer control to when it runs. In other words, it's a "goto, but not yet, let's run some code in between".

In order to do a deferred goto, the first statement increases the value of most of the ROM waterclocks in a particular set from 3 to 4, a state not previously used in this tutorial. This state's used to remember that those waterclocks are not the ones scheduled to be jumped to via the deferred goto. The last remaining waterclock in the set, the one where control will eventually go, remains at 3.

When it becomes time to "trigger" the deferred goto and jump to the previously chosen location, this is done simply by reducing all the waterclocks in the set simultaneously. The chosen waterclock will become 2 and be ready to run, whilst the others will return to their usual value of 3.

Of course, while waterclocks have value 4, attempting to run them will lead to disaster (they'll reduce to 3, tying the numerous 3s that will likely exist elsewhere in the program, and thus causing a crash three cycles later). So you can't run waterclocks the regular way while they're even potentially the target of a pending deferred goto. You can, however, set up multiple deferred gotos at the same time using disjoint sets of potential targets. You can also cancel a pending deferred goto if you know both the set of potential targets, and the target that was actually chosen.

So getting back to the original problem, of using a value from multiple locations, let's consider the following pseudocode:

loop forever:
  try to decrement x
  if you can't, run A
  try to decrement x
  if you can't, run B 

This is a simple example of code that wants to give two different pieces of code to x (from the two "if you can't") lines. We can use a deferred goto to rewrite it like this, which only needs to read x from one location:

  deferred goto u from {u,v}
s:
  remove deferred goto of u from {u,v}
  deferred goto t from {s,t}
  deferred goto v from {u,v}
  goto w
t:
  remove deferred goto of v from {u,v}
  deferred goto s from {s,t}
  deferred goto u from {u,v}
  goto w
u:
  run B
  deferred goto u from {u,v}
  goto selected from {s,t}
v:
  run A
  deferred goto v from {u,v}
  goto selected from {s,t}
w:
  try to decrement x
  if you can't, goto selected from {u,v}
  goto selected from {s,t}

Although long, this is fairly straightforward. The main thing to be wary of is that whenever we set up a deferred goto, we have to either trigger it or cancel it; this in turn means that if we set one up planning to cancel it if it isn't used (such as the {u,v} deferred goto above), we have to set it back up if it is used (so that it can be cancelled correctly later on). That's why u and v set up deferred gotos to themselves (and why we set one up before the start of the loop, so that the attempt to cancel it won't cause problems).

Again, although the program is long when written in pseudocode, you can combine a lot of effects into a single waterclock's code. So each of s, t, u, v, and w above (in addition to the RAM waterclock x) can be condensed into a single waterclock (at least if A and B are single-waterclock blocks of code). Let's have a look at this program in the usual matrix form, with the waterclocks in the same order as the program above:

4366 6666
242 3112
324 1312
311 33242
411 33222
311 2230
3322 0013

For the sake of demonstration, A in the above adds 10 to x, B adds 20. The expected result would be for the program to alternately add 10 and 20 to x as it zeroes (we're adding an even number to it, so we'll have an even number of alterations between s and t, meaning that waiting for x to decrement doesn't change the "natural behaviour" s and t have of running alternately), and that's exactly what is seen when we run the program in the interpreter.

We can actually make this program even smaller and faster (but even more confusing) by inlining w into s and t:

4355555
231310
313130
3113342
4113322
3322003

Saving memory using row-shifts

Let's take another look at the non-destructive add program from above:

128888 8888
23122 2022
32222 2044
32231 2220
32222 2420
30000 0000
111201 1311
71111 1131
31112 0113

We're using quite a lot of waterclocks here; for each of the two loops, we have a ROM waterclock for the loop entry, a second ROM waterclock for the loop body, and a RAM waterclock for the loop counter. We'd like to be able to get rid of at least one of these.

To do this, we note that the loop entry waterclock only zeroes once, and likewise, the RAM waterclock also only zeroes once (to break out of the loop). So it seems like we should be able to combine these. The entry waterclock is only there to prevent an off-by-one, so why don't we just prevent it a different way by reversing the effects of a loop iteration in the code that runs when the RAM waterclock zeroes?:

1266 6666
222 2044
322 2420
300 0000
1120 13-1-1
711 1131
312 0-113

Oh. The problem is that each loop iteration adds at least 2 water to at least one waterclock, so to reverse a loop iteration, we have to remove 2 units of water from at least one waterclock. Unfortunately, the RAM waterclock that's trying to do the removal starts out at 1, so only 1 unit naturally drains out in the process; we have to remove an additional unit somehow. The matrix above marks these locations with negative numbers, but negative numbers aren't allowed in The Waterfall Model.

Luckily, we can do this in a satisfyingly simple way. Thinking about the most basic rule of The Waterfall Model, when no waterclock is zero, one unit of water gets removed from every waterclock. That means that if we add an equal amount of water to each waterclock, it will have no effect on the program's operation. So if a row contains negative elements, we can just add minus the smallest element to every element, and end up with a row that's entirely nonnegative and has the behaviour we'd want; in this case, we need to add 1 to each cell of the code of the fourth and sixth waterclocks. The program is a little harder to follow, as the waterclocks end up restoring their invariant on the cycle after a zeroing rather than on the zeroing cycle itself (as is more usual), but we've ended up writing effectively the same program using fewer waterclocks:

1266 6666
222 2044
322 2420
300 0000
1131 2400
711 1131
323 1024

Two cycles before the halt, the waterclock values are [3,3,2, 11,15,3], i.e. the RAM has behaved exactly as desired, and the ROM is smaller. One thing to note is that this program is marginally slower than the original (1 cycle slower per loop in this case), because it takes extra time for the waterclocks to reduce to the desired resulting values after a zeroing; however, this is typically only a trivial cost on the running time of the program, and the reduction in memory usage may well make it run faster in practice.

Fixing the off-by-one in loops is not the only potential use of this technique. You could also use it to subtract large constants from RAM waterclocks (as long as you knew that this could not take them below zero). From the opposite point of view, you could row-shift in the other direction to marginally speed up the program in cases where a row happens to contain no zero elements.

When writing your own programs in the text box below, you can use the "Fix/Indent" button to (among other things) automatically apply row-shifts to rows that contain negative elements, fixing the program to be legal without changing the semantics of the program.

Try it!

You can write your own programs below and load them into the interpreter on this page.