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)recursionarbitrary first-class functions (no y-combinator)The language does, however, have:top-level functionslexically scoped let bindingsbranching control flowcommon scalar math and logic functionssome simple array constructor like fill(n,x) which creates an n-element array with identical values xmost 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[0]], f(y[p[1]], ...))) for some permutation py = 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?
Which algorithms can be expressed using a total functional language with data parallel operators?
complexity classes;functional programming;dc.parallel comp