Generalized For loops in ParaSail

As we start to dive into the lower-level control structures for ParaSail, one clearly very important structure is the for loop.  We have already suggested the basic structure:

    for I in 1..10 [forward | reverse | concurrent] loop

However, it would be nice if the for loop could also be used for more general looping structures. A number of languages have adopted a for loop where there is an initialization, a "next step", and a termination/continuation condition.  The best known is probably that of C, inherited by C++ and Java:

    for (init; test; next)...

The init and next parts are arbitrary statements (to be more precise, expressions evaluated for their side-effects), while test is treated as a condition whose truth determines whether iteration continues.

A number of LISP variants, and languages based to some degree on LISP such as Dylan, also have a similar generalized looping capability:
Scheme:

    (do ((I initial next) (J initial next) ... )
      (test) 
        loop body
    )

Dylan:

    for (I = initial then next while: test)
        loop body
    end for

In the case of the C for loop, next is an arbitrary statement, whereas for the LISP-based languages, next is the next value for the associated loop variable. This is perhaps related to the fact that in C there is special syntax for incrementing and decrementing a variable, meaning that a statement that increments the loop variable (e.g. I++) can be as concise as simply specifying the next value (e.g. I+1) in languages without this special syntax.

The LISP-based languages generally define these sorts of for/do loops in terms of tail recursion, where the next value is what would be passed as the parameter in the tail-recursive call.  It is interesting to consider whether more general kinds of recursive algorithms could be mapped to an iterative control structure.  For example, could a recursive walk of a binary tree be represented as some kind of for loop?  This is particularly interesting for a language with implicit parallelism, where it might be desirable to have multiple threads involved in walking the various branches of the tree.

The above considerations lead us to the following possible approach to a generalized for loop in ParaSail (borrowing heavily from the Dylan syntax):

    for T := Root then T.Left || T.Right 
      while T != null loop
        loop body
    end loop

This would represent a "loop" which on each iteration splits into two threads, one processing T.Left and the other T.Right. The iteration stops when all of the threads have hit a test for T != null which returns false.  The general syntax would be:

    for var := initial then next {|| next} 
      [while | until] test [concurrent] loop
        loop body
    end loop

If we were to specify concurrent loop then it would presumably imply that the daughter threads are to be created immediately once the test was found to be true, not waiting for the loop body of the parent thread to finish. This would effectively create a thread for every node in the tree, with the loop body executing concurrently for each node.