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

4 points

4 years ago

Hi, 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(int& a, int& b) {
     int old_a = a;
     a = b;
     b = old_a;
  }

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(int& a, int& b) {
    a' = b;
    b' = a;
  }

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:

1. "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).

2. 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 Hacker News 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?

5 comments