Power Loops

Power loops are a way to describe recursively nested for-loops (where the depth of nesting is dynamic rather than specified lexically).

Code from AdvancedProgrammingLanguageDesign:

the EightQueensProblem with powerloops is

 variable 1
     Queen : array 1 .. n of integer 
 nest Column := 1 to n 
    for Queen[Column] := 1 to n do 
        if OkSoFar(Column) then 
            deeper
        end 
    end
 do 
    write(Queen[1..n])
 end

The for/if (the code in nest..end) gets expanded at the 'deeper' point.

Power loops never got mainstream anyway, AFAIK.

-- GabrieleRenzi

There was a time when I wished to have such a thing, but that was a long time ago in a procedural programming language. Today I would prefer the recursive formulation every time. The above formulation is just too complicated and can handle only the very simplest forms of recursive functions I guess. Challenge: What would

  f(x) = x > 0 ? f(x-1) + g(x) : g(x); 
  g(x) = x > 0 ? g(x-1) * f(x) : 1;

look like (this is just a contrived example)?

-- GunnarZarncke

I don't have a clue :) I guess this is one of the reason this never become successful... Limited use cases. -- GabrieleRenzi

Its uses are niche, not general purpose like recursion, so it's not clear that the above contrived example has a natural translation to power loops.

However, it is sometimes very handy -- I implement it by hand sometimes, rather than using a language that supports it, in conjunction with recursion, not instead of it. The places where it is natural are precisely those where for-loops would be more natural than pure recursion. For some people, obviously that would mean "nowhere at all", since e.g. many Lisp fans prefer to use recursion instead of loops always.

The EightQueensProblem is a classic example for people who find it natural to solve via 8 nested for-loops. PowerLoops allow a fairly transparent extension of a looping solution for a fixed size board to an arbitrarily sized board, which otherwise requires rewriting the implementation altogether.

The thing that is characteristic of this kind of problem is that data from all N levels of the recursion/looping may need to be examined simultaneously, as is sometimes the case with chessboard problems, where level K of the recursion/looping may want to examine the full board, not just the local K-th level of the board.

In such cases, typically one will pass around a representation of the full board, whether one uses recursion or looping, but without PowerLoops, the looping approach can be very unnatural while the recursive solution is flexible. With PowerLoops, a looping approach to such problems can be flexible and natural, and may even be simpler and more natural than recursion if recursion is mixed with PowerLoops, netting a sort of 2-dimension recursion.

Enumerating a constrained subset of all elements of a set formed by concatenation of multiple subsets is another example where PowerLoops can be natural, e.g. [0-9][0-9][0-9] forms 3 digit numerals, select the subset that represents prime numbers. (See EveryCombinationInManyProgrammingLanguages)

Similarly for generating random sentences from a BNF grammar, which can be trickier to do with recursion alone than it first seems in some cases.

Besides narrow applicability, another thing that may have limited its popularity is that the rare languages which have implemented it have offered PowerLoops constructs which are not only unfamiliar, but also less general than what one can do if implementing the same notions by hand. So it's possible that it also needs a better set of supporting constructs in order to justify adding it to a language. -- DougMerritt

Of course, you have to take into account the looping/recursion hybrid, which could be said to be a generalization of PowerLoops. The eight queens problem in python:

     def allqueens(size = 8):
         if size == 0:
             yield ()
         else
             for i in range(size):
                  for part in allqueens(size - 1):
                       solution = (i,) + part
                       if isOk(solution): yield solution