The Waterfall Model

From Esolang
Jump to navigation Jump to search

The Waterfall Model is an esoteric programming language (or possibly a computational model) created by User:ais523 in 2018. It can be seen as a simplification of counter machines along different lines from The Amnesiac From Minsk; however, similarly to that language, it's intended as a source language for proving the Turing-completeness of other languages by compiling The Waterfall Model into them. Historically, though, it was originally created as a derivative of Kangaroo (and the first informal proof of its Turing-completeness was by analogy with the proof for Kangaroo, although there are simpler and more rigorous proofs available).

The main difference from a standard Minsky machine is that the language has no instruction pointer; like The Amnesiac From Minsk and StackFlow, code only runs as a consequence of counters reducing to zero. However, unlike most similar languages, there is no explicit way to reduce the value of a counter (the "zeroing triggers" can only increase counter values). Rather, the counters conceptually reduce at a standard rate over time; thus, the smallest counter will hit zero first and do some amount of increasing of the counters as a consequence. (Naturally, a counter has to increase its own value when it hits zero, or the program will never be able to make any progress.)

One interesting side consequence of this is that there is no particular reason why the counter values should be restricted to integers, and in fact many natural ways of implementing The Waterfall Model will naturally tend to be able to handle rational or even computable-real values with no additional effort. This can be seen as an extended version of the language, or as an interesting consequence of the model's definition.

Semantics

A program in The Waterfall Model consists of a number of different waterclocks. Each of these has:

  • A current value, which is a number (that can change over the lifetime of the program, without changing the waterclock's identity);
  • and a zeroing trigger, which is a map from waterclocks to nonnegative numbers (that's a fixed and hardcoded part of the program).

The numbers in a waterclock's zeroing trigger describe how much each of the waterclocks in the program will be "topped up" (incremented) when this waterclock's level reaches zero.

The "numbers" here are integers in the most basic form of the language, but using other forms of numbers may be an interesting extension. Note that implementations should be able (at least in theory) to handle unboundedly large numbers, in order to prevent the language collapsing into a bounded-storage machine.

The simplest way to visualise the semantics of the program is to imagine all the waterclocks counting down at the same, constant rate (e.g. their value reduces by 1 every second). When a waterclock's current value hits 0, its zeroing trigger runs, increasing the current value of each waterclock by the value that corresponds to it within the zeroing trigger.

Should two waterclocks' current values hit 0 simultaneously, the resulting behaviour is undefined by default. Some implementations may assign defined semantics to this (e.g. reading user input and using it to determine which zeroing trigger to run).

If a waterclock's zeroing trigger runs but fails to increase the value of that waterclock from 0, this conceptually causes an infinite loop (as the zeroing trigger in question runs infinitely many times in a row). Although this is technically a valid implementation of this situation, it's recommended that implementations that do not have a reason to be as simple as possible should detect this situation and halt when it occurs. In order to avoid trivial mistakes and (perhaps) simplify implementations, a program is invalid if a "halt waterclock" (one which fails to increase its own value when zeroed) has a zeroing trigger other than all-zeroes. Along similar lines, waterclocks must not start with 0 as their current value (their current value can hit 0 during execution, but only instantaneously, because the program will either halt or increase the waterclock's value as a consequence of the resulting trigger).

Note that there is no requirement to actually pause for a length of time proportional to the values of the waterclocks; implementations are entirely free to "accelerate time" where it's clear that nothing is happening (e.g. by finding the minimum current value among all waterclocks and subtracting it from each of them). In other words, the timing properties implied by the syntax are not necessarily part of the output of the program (although of course, an implementation could be written where they are).

Output extension

As an optional part of the language, some implementations may wish to provide a method of producing output (in a way that does not affect the behaviour of programs that aren't expecting it). To do this, the implementation looks for output waterclocks in the program; these are waterclocks whose zeroing triggers are all-zeroes (like halt waterclocks), except that they raise their own value when zeroed. Note that this feature is entirely optional, and many (most?) implementations will not provide it.

When zeroing triggers adjust an output waterclock by specific amounts, this triggers output as a side effect:

  • +7: an internal counter (the "output counter") is incremented; this counter is initially 0
  • +8: the value of the output counter is output as an integer, then the output counter is reset to 0
  • +9: the value of the output counter is output as a character, then the output counter is reset to 0.

This feature allows programs to include output statements for debugging purposes or to communicate information, whilst still giving full compatibility (both forwards and backwards) with non-output-generating programs and implementations.

Syntax

The Waterfall Model represents programs as a square matrix, containing specifications of the waterclocks, and some additional information to make it easier to construct implementations in low-powered languages.

The first row of the matrix is used for metadata that enables languages that allocate memory explicitly to be able to allocate the memory in advance, rather than needing to reallocate it in the middle of reading the source. The top-left corner contains a number that's larger than any other number that appears in the matrix, to enable implementations to know how large the numbers can get; apart from this constraint, the number is entirely meaningless and can have any sufficiently large value. Each remaining element on the first row is filled with the number of waterclocks. (So for example, if there are three waterclocks, the first row would consist of a large number followed by three 3s.)

Each remaining row describes a waterclock. The first element of the row is the initial current value of the waterclock. The remaining elements are the zeroing trigger; the first remaining element (i.e. the second element) describes the amount that the first waterclock will be topped up by, the second remaining element describes how much water will be used to top up the second clock, and so on.

A matrix of numbers, although a concrete syntax, is a syntax that's not commonly communicated between systems. If a program in The Waterfall Model needs to be stored in a file, the recommendation is to use JSON (i.e. the matrix is a comma-separated list of rows enclosed in [], and each row is a comma-separated list of numbers enclosed in [], with whitespace being allowed anywhere outside a number).

ZISC interpretation

One of the simplest ways to implement The Waterfall Model in a high-level language is to use a ZISC interpretation; in this case, the matrix (that's normally taken as describing the program) is instead seen as the content of memory that a single, repeated command operates on. The command here is "identify the lexicographically smallest matrix row (i.e. the row with the smallest first element), then add the transpose of that row to the first column of the matrix"; these operations tend to be already built in to practical programming languages, and thus it forms a particularly direct explanation of the language's behaviour. (Note that in this case, instead of waiting for waterclocks to hit zero, we're waiting for them to hit the minimum value, which is much faster, and never bothering with actually subtracting the waterclocks to zero; this clearly leads to the same result.)

It's possible when doing this that the first, metadata, row will end up as the lexicographically smallest. However, this effectively corresponds to a row that increments every waterclock by the same amount and the "zeroth waterclock" by more, which clearly has no effect on the behaviour of the program.

In some languages, it's simpler to add the transpose of the chosen row to every column of the matrix, rather than simply to the first. Adding a constant to every element of a zeroing trigger clearly does not change the behaviour of the language, after all.

The first implementation of The Waterfall Model was written here on Stack Exchange, and uses this ZISC construction. It consists of just four bytes of Jelly code: 

+"Ṃß

Computational class

The general case

One key observation here is that the requirement for all zeroing trigger elements to be nonnegative is not really relevant; you can simply increase every element by a constant so that they all become positive. As such, it's easy to imagine a structure for a program that acts more like a traditional Minsky Machine, with some waterclocks acting as counters and acting as states in the program, and changing state being achieved by incrementing the value of the current state and decrementing the value of the new state (i.e. all states have value 1, apart from the currently running state which has value 0). This handles increment, unconditional decrement, and goto operations just fine, via implementing them on the zeroing triggers of the state waterclocks. Note that the minimum value of a counter should be 1 (not 0), because having a waterclock at 0 is a special case in The Waterfall Model.

For conditional decrement operations, the trick is to double the value of every counter (so they normally get incremented and decremented by 2 at a time), and use the values 4 and 0 for states rather than 1 and 0. Now, you can implement a conditional decrement by setting a state to 3, rather than the usual 0, and "decrementing" the counter by 2 at the same time (i.e. by incrementing everything else by 2). If the counter waterclock was at 2 (emulating a counter value of 1), it'll get decremented to 0 and its own zeroing trigger will run (which can restore its own value to an emulated value of 1 / actual value of 2, and set the currently running state accordingly at the same time). If the counter waterclock was higher (i.e. 4 or more), the state that was set will be the first thing to hit zero, and it can likewise recover the situation. Note that one minor problem with this construction is that there can only be one conditional decrement operation per counter (it needs to know where it was called from), but The Amnesiac From Minsk demonstrates, this does not change the Turing-completeness of the language.

Implementation with only small integers in the program

When using The Waterfall Model to prove languages Turing-complete, there are sometimes restrictions on the size of numbers that can be used in the zeroing triggers and/or the initial waterclock values. (In particular, the "self-reset" value for waterclocks – the value that the waterclock's zeroing trigger maps that waterclock itself to, and that the waterclock will reset to when it becomes zero – is often the hardest part of the language to implement in a tarpit, and being able to keep it low makes the language easier to implement.) As such, it is useful to prove that The Waterfall Model is Turing-complete using only small integers.

There is a very simple way to compile from Flow of Holes into The Waterfall Model:

  • Each node from Flow of Holes compiles into a waterclock in The Waterfall Model.
  • Waterclocks compiled from control nodes start at 3, or 1 if the control node is the active node.
  • Waterclocks compiled from data nodes start at 2, plus twice the value of the node.
  • The zeroing trigger that increases waterclock N when the waterclock C compiled from a control node zeroes has the following value:
    • 4 if N is data-connected from C (including the case where N is control-connected to C)
    • 0 if N is data-connected to C (including the case where N is control-connected from C)
    • 2 in all other cases (including the case of N=C, and more generally the case where N is a control node)
  • The zeroing trigger that increases waterclock N when the waterclock D compiled from a data node zeroes has the following value:
    • 2 if N is control-connected to D
    • 2 if N=D
    • 0 if N is control-connected from D
    • 1 in all other cases (including the case where N is a data node)

Flow of Holes is Turing-complete even using only 0 and 1 for starting data node values (this is sufficient to create a chain of control nodes that initializes the rest of the program via using secondary connections, and then pass control of execution to the "real" program using a control merge). This implies that The Waterfall Model is Turing-complete even if zeroing triggers are restricted to the range 0 to 4 inclusive, starting waterclock values are restricted to the range 1 to 4 inclusive, and all waterclocks have a self-reset value of 2.

(As a side note, an "illegal control merge" in Flow of Holes – i.e. transferring control to a control node that has a second data node with value 0 control-connected to it – is undefined behaviour in Flow of Holes, but happens to work correctly anyway when the resulting program is compiled to The Waterfall Model, i.e. the compilation does not take advantage of that particular piece of undefined behaviour. So it is possible to simplify the compiled programs by writing that sort of control merge directly, rather than using a bit bucket, although doing so is not required to show Turing completeness.)

See also

External resources

Retrieved from "https://esolangs.org/w/index.php?title=The_Waterfall_Model&oldid=117319"