**ParaSail**, where we try to place N queens on an NxN chess board such that none of them can take each other. This takes the idea of using the "continue" statement as a kind of implicit recursion to its natural conclusion. This presumes you can turn a "normal" data structure like Vector<> into a concurrent data structure by using the keyword "concurrent," which presumably means that locking is used on all operations to support concurrency. It is debatable whether this use of a "continue" statement to effectively start the next iteration of a loop almost like a recursive call is easier or harder to understand than true recursion.

interfaceN_Queens <N : Univ_Integer := 8>is// Place N queens on a checkerboard so that none of them can // "take" each other.typeRowisnewInteger<1, N>;functionPlace_Queens() -> Vector<Vector<Row>>{;forallIinPlace_Queens#range : Length(Place_Queens[I]) == N}endinterfaceN_Queens;classN_Queens <N : Univ_Integer := 8>istypeColumnisnewInteger<1, N>;typeSumisVector<Boolean, Index => Integer<2, 2*N>>;typeDiffisVector<Boolean, Index => Integer<1-N, N-1>>;exportsfunctionPlace_Queens() -> Vector<Vector<Row>>{isforallIinPlace_Queens#range : Length(Place_Queens[I]) == N}// Place N queens on checkerboard so that none of them can "take" each othervarSolutions :concurrentVector<Vector<Row>> := []; *Outer_Loop*for(C : Column := 1; Trial : Vector<Row> := []; Diag1 : SSum := [.. => #false]; Diag2 : Diff := [.. => #false])loop// Iterate over the columnsforRinRowconcurrentloop// Iterate over the rowsifnotDiag1[R + C]andthennotDiag2[R - C]then// Found a Row/Column combination that is not on any diagonal // already occupied.ifC < Nthen// Keep going since haven't reached Nth column.continueloopOuter_Loopwith(C => C+1, Trial => Trial | R, Diag1 => Diag1 | [(R+C) => #true], Diag2 => Diag2 | [(R-C) => #true]);else// All done, remember trial result.Solutions |= Trial;endif;endif;endloop;endloopOuter_Loop;returnSolutions;endfunctionPlace_Queens;endclassN_Queens;

Your interpretation of "concurrent" for the Vector> would overconstrain the solution, would it not? That data structure is "write-only" in your algorithm, the order of updates doesn't matter, and it is modified only by appending. You could use a lock-free data structure in that case.

ReplyDeleteI don't think "continue"-type statements are hard to read by default, but this one seems awkward. Maybe it's because your "continue" syntax is so verbose?

continue Outer_loop (C => C+1, Trial => Trial | R, ...)

It could also be because the place where you name Outer_Loop doesn't have an immediate connection with the loop itself. Finally, it could be because there's only one loop variable (C) and so it would seem more natural to program with a traditional iterative syntax (or forget it and write recursively).

I do like the idea of loop+continue as an alternate syntax for recursion. I think it's most useful when the algorithm really calls for iterative expression ("for all (key,value) in a hash table"), but has the occasional corner case where a recursive expression helps.

Thanks for your comment. I agree that a lock-free data structure could accommodate order-free appending. But that would require some amount of manual coding to correctly design the lock-free appending. I was playing around with the idea of being able to turn any data structure into a concurrent one without extra manual effort by falling back on locking, but I agree more interesting would be to be able to do the same thing with some kind of standard lock-free approach.

ReplyDeleteI just fixed one bug in the above, where "Sum" and "Diff" were declared as Integer types rather than as Vectors of Booleans

ReplyDeleteindexedby the appropriate range of integer. The more elegant fix would be to declare Sum and Diff as Sets over the given range of integers. That would probably also be easier to understand. Hence:type Sum is Set<Integer<2, 2*N>>;

type Diff is Set<Integer<1-N, N-1>>;

...

for (... Diag1 : Sum := []; Diag2 : Diff := []) loop

...

if (R+C) not in Diag1 and then

(R-C) not in Diag2 then

...

continue ... with (...

Diag1 => Diag1 | (R+C),

Diag2 => Diag2 | (R-C));

After reading my comment, i realize that the "continue Outer_loop" example might as well just be a (tail) recursive call. oh well ;-)

ReplyDeleteThanks for sharing. I also tried using the lock-free data structure in that case and it works.

ReplyDelete@Tuck It's both legit and good to have a fallback model for "concurrent," so that you can insert optimizations invisibly as they become available. My only concern is that a "concurrent vector" is more complicated than what the algorithm needs, but it should still result in correct code.

ReplyDelete