More expressive loops for Eiffel

New variants of the loop construct have been introduced into Eiffel, allowing a safer, more concise and more abstract style of programming. The challenge was to remain compatible with the basic loop concept, in particular correctness concerns (loop invariant and loop variant), to provide a flexible mechanism that would cover many different cases of iteration, and to keep things simple.

Here are some examples of the new forms. Consider a structure s, such as a list, which can be traversed in sequence. The following loop prints all elements of the list:

      across s as c loop print (c.item) end

(The procedure print is available on all types, and can be adapted to any of them by redefining the out feature; item gives access to individual values of the list.) More about c in just a moment; in the meantime you can just consider consider that using “as c” and manipulating the structure through c rather than directly through s  is a simple idiom to be learned and applied systematically for such across loops.

The above example is an instruction. The all and some variants yield boolean expressions, as in

across s as c all c.item > 0 end

which denotes a boolean value, true if and only if all elements of the list are positive. To find out if at least one is positive, use

across s as c some c.item > 0 end

Such expressions could appear, for example, in a class invariant, but they may be useful in many different contexts.

In some cases, a from clause is useful, as in

        across s as c from sum := 0  loop sum := sum + c.index c.item end
— Computes Σ i * s [i]

The original form of loop in Eiffel is more explicit, and remains available; you can achieve the equivalent of the last example, on a suitable structure, as

A list and a cursor

A list and a cursor

      from
sum := 0 ; s.start
until
s.after
loop
sum := sum + s.index s.item
s.forth

        end

which directly manipulates a cursor through s, using start to move it to the beginning, forth to advance it, and after to test if it is past the last element. The forms with across achieve the same purpose in a more concise manner. More important than concision is abstraction: you do not need to worry about manipulating the cursor through start, forth and after. Under the hood, however, the effect is the same. More precisely, it is the same as in a loop of the form

from
sum := 0 ; c.start
until
c.after
loop
sum := sum + c.index c.item
c.forth

        end

where c is a cursor object associated with the loop. The advantage of using a cursor is clear: rather than keeping the state of the iteration in the object itself, you make it external, part of a cursor object that, so to speak, looks at the list. This means in particular that many traversals can be active on the same structure at the same time; with an internal cursor, they would mess up with each other, unless you manually took the trouble to save and restore cursor positions. With an external cursor, each traversal has its own cursor object, and so does not interfere with other traversals — at least as long as they don’t change the structure (I’ll come back to that point).

With the across variant, you automatically use a cursor; you do not have to declare or create it: it simply comes as a result of the “as c” part of the construct, which introduces c as the cursor.

On what structures can you perform such iterations? There is no limitation; you simply need a type based on a class that inherits, directly or indirectly, from the library class ITERABLE. All relevant classes from the EiffelBase library have been updated to provide this inheritance, so that you can apply the across scheme to lists of all kinds, hash tables, arrays, intervals etc.

One of these structures is the integer interval. The notation  m |..| n, for integers m and n, denotes the corresponding integer interval. (This is not a special language notation, simply an operator, |..|, defined with the general operator mechanism as an alias for the feature interval of INTEGER classes.) To iterate on such an interval, use the same form as in the examples above:

        across m |..| n  as c from sum := 0  loop sum := sum + a [c.item] end
— Computes Σ a [i], for i ranging from m to n, for an array (or other structure) a

The key feature in ITERABLE is new_cursor, which returns a freshly created cursor object associated with the current structure. By default it is an ITERATION_CURSOR, the most general cursor type, but every descendant of ITERABLE can redefine the result type to something more specific to the current structure. Using a cursor — c in the above examples —, rather than manipulating the structure s directly, provides considerable flexibility thanks to the property that ITERATION_CURSOR itself inherits from ITERABLE   and hence has all the iteration mechanisms. For example you may write

across s.new_cursor.reversed as c loop print (c.item) end

to print elements in reverse order. (Using Eiffel’s operator  mechanism, you may write s.new_cursor, with a minus operator, as a synonym for new_cursor.reversed.) The function reversed gives you a new cursor on the same target structure, enabling you to iterate backwards. Or you can use

        across s.new_cursor + 3 as c loop print (c.item) end

(using s.new_cursor.incremented (3) rather than s.new_cursor + 3 if you are not too keen on operator syntax) to iterate over every third item. A number of other possibilities are available in the cursor classes.

A high-level iteration mechanism is only safe if you have the guarantee that the structure remains intact throughout the iteration. Assume you are iterating through a structure

across  as c loop some_routine end

and some_routine changes the structure s: the whole process could be messed up. Thanks to Design by Contract mechanisms, the library protects you against such mistakes. Features such as item and index, accessing properties of the structure during the iteration, are equipped with a precondition clause

require
is_valid

and every operation that changes the structure sets is_valid to false. So as soon as any change happens, you cannot continue the iteration; all you can do is restart a new one; the command start, used internally to start the operation, does not have the above precondition.

Sometimes, of course, you do want to change a structure while traversing it; for example you may want to add an element just to the right of the iteration position. If you know what you are doing that’s fine. (Let me correct this: if you know what you are doing, express it through precise contracts, and you’ll be fine.) But then you should not use the abstract forms of the loop, across; you should control the iteration itself through the basic form from … until with explicit cursor manipulation, protected by appropriate contracts.

The two styles, by the way, are not distinct constructs. Eiffel has always had only one form of loop and this continues the case. The across forms are simply new possibilities added to the classical loop construct, with obvious constraints stating for example that you may not have both a some or all form and an explicit  loop body.  In particular, an across loop can still have an invariant clause , specifying the correctness properties of the loop, as in

        across s as c from sum := 0  invariant sum = sigma (s, index)  loop sum := sum + c.index c.item end

EiffelStudio 6.5 already included the language update; the library update (not yet including the is_valid preconditions for data structure classes) will be made available this week.

These new mechanisms should increase the level of abstraction and the reliability of loops, a fundamental element of  almost all programs.

VN:F [1.9.10_1130]
Rating: 7.5/10 (22 votes cast)
VN:F [1.9.10_1130]
Rating: +4 (from 14 votes)
More expressive loops for Eiffel, 7.5 out of 10 based on 22 ratings
Be Sociable, Share!

11 Comments

  1. Patrick Schoenbach says:

    Will these new loop constructs work with the standard EiffelBase containers only or will it be possible as well to make them work with any custom data structure?

    VN:F [1.9.10_1130]
    Rating: 5.0/5 (1 vote cast)
    VN:F [1.9.10_1130]
    Rating: +1 (from 1 vote)
    • bmeyer says:

      Both. It is very easy to make the `across…’ loop applicable to any class:

      – The simplest is to make the class a descendant of one of the existing descendants of the ITERABLE class, such as INDEXABLE (which is for example used as ancestor by all the list classes). Then you have nothing more to do; you get a standard cursor.

      – If you want a more specific cursor, make the class a descendant of ITERABLE and write the specific cursor class as a descendant of ITERATION_CURSOR, effecting the queries `item’ and `off’. This gives you finer control in case your structure has specific properties that should be accessible through the cursor. As an example, you can look at how this was done for HASH_TABLE in such a way that in a loop

      across my_hash_table as mht loop … end

      you can in a loop body access both mht.item, giving the current item in the hash table, and mht.key, giving its key.

      VN:F [1.9.10_1130]
      Rating: 5.0/5 (4 votes cast)
      VN:F [1.9.10_1130]
      Rating: +3 (from 3 votes)
  2. Peter Gummer says:

    What happens if the structure is Void? Take your first example:

    across s as c loop print (c.item) end

    If ‘s’ is declared to be of a detachable type, and if it actually is Void at run time, does this ‘across’ loop raise a Void-target call exception? (This is what C# does if the structure supplied to a ‘foreach’ loop is null. I’m fixing one such NullReferenceException bug right now that has gone undetected for months in our C# code.) Or does ‘across’ recognise that the structure is Void, and treat it the same as if it were empty, performing zero iterations of the loop? (This is what I wish C# ‘foreach’ loops did; I wish it frequently, unfortunately.)

    Or would the Void-safe Eiffel compiler reject the above code if ‘s’ is detachable?

    VN:F [1.9.10_1130]
    Rating: 0.0/5 (0 votes cast)
    VN:F [1.9.10_1130]
    Rating: 0 (from 0 votes)
    • bmeyer says:

      The `across’ variant is formally defined by an “unfolded form” that uses the `from’ variant. In the case of a void structure it will produce the same effect, a “call on void target” exception.

      In void-safe mode the compiler will reject the code (although I haven’t checked this yet on an actual example).

      VN:F [1.9.10_1130]
      Rating: 0.0/5 (0 votes cast)
      VN:F [1.9.10_1130]
      Rating: 0 (from 2 votes)
      • Larry says:

        Bertrand, I am looking for a definition/discussion of “unfolded form”, “folded form” and “partially unfolded form”. Can you point me towards something directly related to Eiffel?

        VN:F [1.9.10_1130]
        Rating: 0.0/5 (0 votes cast)
        VN:F [1.9.10_1130]
        Rating: 0 (from 0 votes)
        • Larry says:

          Would it be the ECMA Standard, 8.5.24? If so, is there something in-depth? OOSC-2?

          VN:F [1.9.10_1130]
          Rating: 0.0/5 (0 votes cast)
          VN:F [1.9.10_1130]
          Rating: 0 (from 0 votes)
          • Larry says:

            Nevermind — I answered my own question upon careful reading.

            BTW: Some (not all) of the “complaints” about the lack of “good documentation” for Eiffel, I am starting to find as relatively false arguments, which stem from what appear to range from simple laziness and lack of attention-to-detail to a lack of formal training (such as my own self over the last two years). I have found some of the documentation to be missing key ingredients needed to fully implement various bits, but for the most part, I am finding that there are several very good resources that (when formed together) answer just about everything:

            1. The ECMA Standard
            2. OOSC-2
            3. Touch of Class
            4. Eiffel.com Documentation
            5. … and let’s not forget … The Eiffel Library code itself!

            There are other resources as well:

            6. The GOBO library documentation (excellently written)
            7. The Eiffel User Group threads on Yahoo Groups (God forbid it ever be lost)
            8. Manu and the Eiffel Software Staff (you all ought to have your minds downloaded and archived! :-) )
            9. The host of Eiffel users in the community (see #7 above)
            10. Google and other search engines
            11. Blogs, including this one

            And perhaps others.

            The key is then to either enhance those resources where possible (e.g. in the Yahoo Groups community, post a complete writeup of any answers we personally find to help document for others behind us). If an external resource cannot be enhanced, then start a blog, create Wiki, add notes somewhere.

            Anyhow — that is my two cents on the matter.

            VN:F [1.9.10_1130]
            Rating: 0.0/5 (0 votes cast)
            VN:F [1.9.10_1130]
            Rating: 0 (from 0 votes)
  3. […] Thanks to Ian Warrington for raising that point. The new across loop variant described in  two later postings uses external cursors and manages them automatically, so this business of maintaining the […]

  4. I really aprecciate this possibility of writing loops but why isn’t it called ‘foreach’ like in other languages? Why across? At first glance I thought of some kind of structures thats guarantees that each item is visited but the order is not determined.
    Is it just because of the naming conventions or is there a more sophisticated reason?

    VN:F [1.9.10_1130]
    Rating: 0.0/5 (0 votes cast)
    VN:F [1.9.10_1130]
    Rating: -2 (from 2 votes)
    • Of course it is the same general idea as iterator constructs that have been offered for various programming languages, often (but not always) using the keyword `foreach’.

      There is an important semantic difference. If you consider the `across’ construct carefully you will note that it is more powerful than typical “foreach” loops. The key is in the use of the cursor variable, following `as’. It adds considerable flexibility, for example by allowing access to the index of the element, to the index of the iteration (not necessarily the same!), to the previous element, the next element… Most “foreach” loops do not have this flexibility.

      As to the choice of keyword: Eiffel avoids multi-word keywords for clarity, so `foreach’ was not considered. A more natural-sounding choice would have been `over’, but too many existing programs use this name as identifier; `across’ was not to everybody’s taste but seemed reasonable enough.

      — Bertrand Meyer
      (Sorry for the delay in approving your comment for publication, I had no time to take care of the blog in recent weeks.)

      VN:F [1.9.10_1130]
      Rating: 5.0/5 (1 vote cast)
      VN:F [1.9.10_1130]
      Rating: +1 (from 1 vote)
  5. Thomas Beale pointed out two errors in the examples (`item’ instead of `c.item’), which I corrected. Thanks!

    VN:F [1.9.10_1130]
    Rating: 0.0/5 (0 votes cast)
    VN:F [1.9.10_1130]
    Rating: 0 (from 0 votes)

Leave a Reply

You must be logged in to post a comment.