Sequential Thinking in NQE using State Pipeline

One interesting challenge when writing logic in NQE is that the language does not support a traditional sequential programming style (loops, mutable variables, recursion, etc.).

But we can emulate iteration by threading state through a series of transformations.

This resembles techniques used in functional programming such as state threading or CPS-like transformations, where computation is expressed as a chain of pure transformations.

Let’s look at a simple example: computing the integer log₂(i) using a sequential algorithm.

Sequential C-like style

int log2(int i) {
int e = 32, b = 0;
while (e >= 1) {
  if (i >= 2 ** e) {
    i /= (2 ** e);
    b += e;
  }
  return b;
}

Conceptually, each loop iteration transforms the state:

(i, e, b)  →  (i', e/2, b')

Since NQE has no while statement, we first unroll the iterations:

if (i >= 2^32) { i /= 2^32; b += 32; }
if (i >= 2^16) { i /= 2^16; b += 16; }
if (i >= 2^8) { i /= 2^8; b += 8; }
if (i >= 2^4) { i /= 2^4; b += 4; }
if (i >= 2^2) { i /= 2^2; b += 2; }
if (i >= 2^1) { i /= 2^1; b += 1; }

Each step still transforms the same state variables.

Instead of mutating variables, we pass the state forward.

Now we can translate the logic into NQE, where the state (i, e, b) is passed forward through each transformation.

NQE implementation

log2_r(r: {i: Integer, e: Integer, b: Integer}) = (
    if r.i >= 2^r.e then {i: r.i / (2^r.e), e: r.e / 2, b: r.b + r.e}
    else {i: r.i, e: r.e / 2, b: r.b}
);

log2(i: Integer) : Integer =
    log2_r(log2_r(log2_r(log2_r(log2_r(log2_r({i: i,e: 32,b: 0})))))).b;

Here:

• The record r carries the state through the computation.

• Each call to log2_r produces a new state, similar to one iteration of the loop.

• Because NQE does not support recursion, the continuation must be manually expanded (6 calls in this case).

This pattern can be useful whenever you need to simulate step-by-step computation in NQE while keeping the language’s functional style.

Curious if others in the community have similar patterns or tricks for handling sequential logic in NQE.