Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are disallowed:
- explicit loops (not much use without side-effects anyhow)
- arbitrary first-class functions (no y-combinator)
The language does, however, have:
- top-level functions
- lexically scoped let bindings
- branching control flow
- common scalar math and logic functions
- some simple array constructor like fill(n,x) which creates an n-element array with identical values x
- most importantly: a restricted set of higher-order operators which perform parallel structured iteration (such as map, reduce, scan, all-pairs).
To be more specific about the data parallel operators:
- y = map(f,x) => y[i] = f[i]
- y = reduce(f, a, x) => y = f(a, f(y[p], f(y[p], ...))) for some permutation p
- y = scan(f, a, x) => y[i] = reduce(f, a, y[0...i-1])
- y = allpairs(f, x, y) => y[i,j] = f(x[i], y[j])
We could have other operators as well, but to qualify they should have polynomial running time, be implementable under some reasonable model of data parallel computation, and use at most polynomial space.
There are obviously some constructs which can't be expressed in this language, such as:
while f(x) > tol: x <- update(x)
What can we express in this system? Are we limited only to search problems in FP? Can we capture all polynomial time algorithms? Also, is there some minimal set of operators for this class?