Simply-stated restriction on imperative programming language that captures the elementary functions?

Question

The language of while programs can express the computably enumerable functions. (This is true even if the only arithmetical operations on variables are, say, incrementation and decrementation.)

If while is replaced by for, making loops always bounded, the language can then express only the primitive recursive functions.

I recently became aware of the class of elementary functions, which are strictly below the primitive recursive functions, but still strictly above the exponential hierarchy.

Obviously it would be possible to define an imperative programming language which captures exactly the elementary functions, say by introducing operators for bounded sum and product. However, my question is,

Is there a syntactic change to the language of while programs which restricts it to the elementary functions and which can be stated as simply as the (while -> for) restriction to primitive recursive functions?

A restriction on for programs instead would also suffice, of course, and perhaps I should clarify that I'm not looking for something that is absolutely as simply-stated, just something with comparable simplicity which does not require the addition of extra operators or the like.

Edit: An example of a representative for language is PL-{GOTO} from Brainerd and Landweber's "Theory of Computation" (1974), in which each program has a finite but unrestricted number of variables, each of which can contain a natural number, and which consists essentially of the following commands:

• X <- 0 (assign 0 to a variable)
• X <- Y (assign the value of Y to X)
• X <- Y + 1 (assign the successor of the value of Y to X)
• LOOP X; ... END; (repeat the contained block of code X times; does not alter X)

The authors give a proof that this can express exactly the primitive recursive functions. The language PL does not match the question perfectly, as it uses GOTO instead of while, and PL-{GOTO} is derived from PL by removing GOTO from it. However, PL programs are just as powerful as while programs, and this GOTO-removal transformation is just as simply stated as replacing while with for. (Arguably perhaps even a bit simpler.)

Edit 2: http://en.wikipedia.org/wiki/Total_Turing_machine suggests this result goes back to: Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.

Answer 1

According to a classic result of Meyer and Ritchie (mentioned in the paper cited in the question), the elementary functions are characterized by LOOP programs in which the nesting depth of for-loops is restricted to be at most 2.

Answer 2

My guess based purely on the definition: one answer might be "restriction of loops to embarassingly parallel for loops".

My working definition of "embarassingly parallel for loop" is one in which no iteration has any data dependency on any other iteration and there is a binary reducer function for aggregating the output (along with a base case). Bonus embarrassment points if the reducer function is associative, but I don't know if that distinction would limit the power of the language.

If we limit the allowable reducers to addition and multiplication, it seems likely to me that any program implemented under these restrictions can be written as an elementary recursive function (and vice versa). I'm less sure about more general reducers.

So a fun way to put it is that your language's only looping construct is MapReduce.

I am a non-expert in the area, but I'd like to propose this as a hypothesis and see what people's opinions are.

Edit. To prove or disprove this fact, we could use a useful characterization from Meyer and Ritchie: A LOOP program implements an elementary function if it runs in time $O(2^{2^{\dots^{n}}})$ where $\dots$ represents a tower of some fixed size $k$.

This seems clearly true of parallel-for programs when the reducer function is limited to addition or multiplication, but seems to be untrue for a more broad choice of reducer. I would like to find that we can get the elementary functions whenever we restrict the reducer to run in polynomial time (multiplication is linear in this model), but I'll have to try to work it out.

Edit 2. Right, so it looks like we should allow exactly the reducer functions that run in polynomial time in order to recover the elementary recursive functions.[1] Then we notice that this restriction is not that interesting, because the polynomial functions in this model are just those expressible by programs with a single for loop or a parallel-for loop with a non-looping reducer function. So we've basically just recovered the restriction that programs have up to two nested for loops, but we've just moved that restriction into the reducer function.

Summary: Characterization seems to be true for reducers that run in polynomial time. It's unclear if this is at all interesting.

[1]: On input $n$, let the reducer function run in time $O(n^k)$ for some $k$. We can roughly argue by induction that a program containing nested parallel-for loops runs in time $2^{2^{\dots^n}}$ for some constant-sized stack of exponents.

In an embarrassingly parallel for loop on input $n$, we can run up to $n$ iterations, each of which (since they're independent) runs in time up to $f(n)$. Suppose for induction $f(n) \in O(2^{2^{\dots^n}})$ for some constant-depth exponential stack.

If the reducer function is $p$, the for loop consists of $n$ compositions of $p$ on an input of size $f(n)$: $p(f(n),p(f(n),\dots))$. By assumption the running time on input size $x$ is bounded by $x^k$ for each step of the reducer, so it runs in time $O(f(n)^{k^n})$, which is asymptotically dominated by $f(n)^{2^{2^n}}$. By inductive assumption, $f(n)$ was bounded by $2^{\dots^n}$ for some constant-sized stack of exponents, so the same must be true for our running time.

And on the other hand, of course, if the reducer runs in exponential time, then this argument will fail and we'll get an exponential stack whose size depends on $n$, which means we can implement a non-elementary recursive function.