Which algorithms can be expressed using a total functional language with data parallel operators?

Question

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)
• recursion
• 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[0]], f(y[p[1]], ...))) 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?

Answer 1

You might want to look at the old programming language NESL which took these ideas seriously. The language is based on operations on collections, essentially lists and lists of lists and so forth, but I think trees and graphs were also considered, via tricky encodings. Some of the research done in that project (in the mid 1990s) could help answer your question. The PhD thesis (available as a book) Guy E. Blelloch. Vector Models for Data-Parallel Computing. MIT Press, 1990 may provide some answers. It was some time ago since I looked at it.

Work done on the Bird-Meertens Formalism (BMF) falls into this category too, as did the language Charity. From the Charity wikipedia page it says that the language is not Turing complete, but can express Ackermann's function, which means that it's more than primitive recursive. Both BMF and Charity involve operators like folds and scans (catamorphisms, anamorphisms, etc), and they have their roots in Category Theory.

I short, imprecise answer is that you can express quite a lot.

Answer 2

My other answer pointed out flaws in the language as it stands. In this answer I will give more detail on the issues with the coexistence of folds and unfolds in a total language. Then I will propose a resolution and show that all problems in P (and indeed many more) can be solved in this extended language.

Folding in a total language consumes lists:

fold :: (a -> b -> b) -> b -> List a -> b

Unfolding in a total language generates streams, which are potentially unbounded:

unfold :: (b -> Maybe (a, b)) -> b -> Stream a

Unfortunately, lists and streams live in different worlds, so these operators cannot be composed. We need a partial correspondence:

stream :: List a -> Stream a
list :: Int -> Stream a -> List a

The stream operator embeds a list into a bounded stream. The list function extracts the first n elements (or fewer if the stream terminates earlier) into a list. We thus have the following equation:

for all xs :: List a, xs == list (length xs) (stream xs)

As an efficiency optimization we can entirely cut out streams as an intermediate data structure:

unfoldList :: Int -> (b -> Maybe (a, b)) -> b -> List a

I will now sketch a proof that this (with the other operators already implied in the original question) lets us simulate any polynomial-time algorithm.

By definition, a language L is in P when there is a Turing machine M and a polynomial p such that membership of x in L can be decided by running M at most p(n) iterations where n = |x|. By a standard argument, the state of the machine's tape in iteration k can be encoded with a list of length at most 2k + 1, even though the machine's tape is infinite.

The idea is now to represent M's transition as a function from lists to lists. The execution of the machine will be done by unfolding the initial state with the transition function. This generates a stream of lists. The assumption that L is in P means that we need look no further than p(n) elements into the stream. Thus we can compose the unfolding with list p(n) to get a finite list. Finally, we fold over it to check whether the answer to the decision problem was yes or no.

More generally, this shows that whenever we have an algorithm whose termination time can be bounded by a function computable in the language, we can simulate it. This also suggests why something like Ackermann's function can't be simulated: it is its own bound, so there is a chicken and egg problem.

Answer 3

It's a very gimped language. Try programming the factorial function:

fact 0 = 1
fact n = n * fact (n-1)

The problem is that your language only has folds but no unfolds. The natural way of expressing factorial is to compose an unfolding of n into the list [1, 2, ..., n] with the folding that tears it down while multiplying.

Are you really interested in this specific language or in total functional programming in general? It's obvious that your language can at most express polynomial-time algorithms. System F (polymorphic lambda calculus) can express monsters like Ackermann's function with ease. Even if your interest is in polynomial-time algorithms, you frequently need the super-polynomial elbow room to express them naturally.

Edit: As Dave points out, NESL is one of the seminal functional data-parallel programming languages but it's very far from total (it doesn't even try). The APL family had a parallel track of evolution and has a total algebraic subset (avoid the fixed-point operators). If the focus of your question is totalness, David Turner has written some good papers in this area although not specifically on data-parallel programming.