Is “x' = f(x)” a programming paradigm?

Question

I'm the author of GateBoy (a gate-level simulation of the original Game Boy hardware) and Metron (a C++ to Verilog translation tool). One big issue I had to work around for both projects is the inability of C++ (or really, any current procedural programming language) to express atomic state change in a way that is both performant and unambiguous. For example, consider the following trivial function:

void swap_and_increment(int& a, int& b) {
  int old_a = a;
  a = b + 1;
  b = old_a + 1;
}

Because the first assignment to 'a' destroys the old value of 'a', we have to store it in 'old_a' in order for the swap to work. In contrast, we could write it like this:

void swap_and_increment(int& a, int& b) {
  a' = b + 1;
  b' = a + 1;
}

where a' means "the new value of a", but this syntax has no equivalent in real C++. This may seem like an insignificant problem at first, but when you scale up to something the size of a Game Boy simulation which has thousands of variables that need to change simultaneously it becomes a serious design problem.

GateBoy solves this problem by instrumenting every variable in debug builds to catch "old/new" bugs - variables get marked as "old" or "new" during execution and reading a "new" value when you expect an "old" value is a runtime error. Metron takes a different tactic and does some symbolic code analysis at translation time to do essentially the same thing - it can ensure that for every possible path through the code, all reads of "old" values are actually reading old values and vice versa for "new" values.

If we generalize the problem a bit, we can say that the difficulty comes in trying to model a system where the entire state of the system represented as X needs to be transformed in to a new state X' via a pure function F without constantly making copies of old state (kills performance), requiring the author to keep track of which parts of the state are old or new at any given point (causes bugs), or relying on hardware support like transactional memory (not widely available). To put it more concisely, a program in the form "x' = f(x)" has no good representation in the software programming languages we use today.

I recently had the opportunity to discuss this issue with a bunch of grizzled old software and hardware veterans, and the approximate consensus seems to be:

• "x' = f(x)" as a model for global atomic state change makes sense to both software and hardware developers, with some viewing it as "just another name for a state machine" (mostly software devs) and some as "so obvious that it doesn't need to be stated" (mostly hardware devs).

• There really isn't any software-oriented language out there that allows for global atomic state change to be both performant (the compiler understands the distinction between "old" and "new" and can reorder code to avoid excessive copies or temporaries) and unambiguous (the distinction between an "old" value and a "new" value has some explicit representation in the language syntax).

So, what do we call this model? Allowing the compiler to reorder statements to preserve "oldness" and "newness" during execution seems to diverge from the "a program is a sequence of operations" model of procedural programming, and the fact that we do want to modify X in place instead of constantly creating new (potentially very large) state objects makes it a poor fit for functional programming.

So, my question to the audience - Does it makes sense to call "x' = f(x)" a programming paradigm? It's certainly not a new one, but it also doesn't fit well with the paradigms we've given names to. What should we do with it?

Answer 1

I am no good at giving names to paradigms. Someone else will be. But the answer to what you actually want to do is quite straightforward, in C++ at least.

Basically you accumulate actions, and having accumulated them you execute them all at the end. In the example you give, each action is of the form "set a to some value". Your problem is that you want all the "some values" to be evaluated before any action is performed - and to make this happen automatically so it can't be broken by a dozy programmer. This happens naturally with this model, because all the evaluations (of a+1 etc) happen when the action objects are constructed, and the execution happens much later.

How exactly you do this is a matter of taste and of practicality. But given an Action class that looks like this:

    class Action
    {int & destination; int source;
    public:
    Action(int &d,int s) :destination(d),source(s) {};
    void apply() {d=s;};
    ~Action() {apply();}; // This is one way of doing it (see below).
    }

you can create each action as an object and calculate what new value you are going to have at the time each object is constructed.

In your particular example, with a fixed number of actions, I would be inclined to make the destructor of the object call apply(). Thus your

    void swap_and_increment(int& a, int& b) {
    Action first {a,b+1);
    Action second {b,a+1);
    }

will:

• Calculate b+1 and a+1 based on the old values before calling the constructors.
• At the end of the function, when the destructors are called and (as I have suggested) automatically call apply(), this will set new values of a and b, as you asked.

If you don't like giving names to things then you can just create an array of Actions:

    Action actions[]={{a,b+1},{b,a+1}};

and this will create the objects (doing the calculation from the old values at this time), and then the destructor of the array will call the destructors of the objects and will thus perform the assignments all in one go.

The reason for using arrays is that this makes the compiler do all the work and at runtime the overhead should be tiny (no memory allocation or deallocation, no function calls).

If your real structure is more sophisticated than the example you gave, then you could use a vector instead of an array. You would then make sure that the Action cannot be copied or assigned, only moved, and have an extra flag so that a moved-from Action will do nothing at all when its destructor is called. As before, destruction of the vector would happen automatically at the end of the function, and destruction of the vector would can the destructors of the objects and thus call apply() for each of them.

---

As to what name you give to the pattern of "accumulate actions and then execute them all at the end", I leave that to the linguists to decide.