Re: Software landmines (loops)

[John Volan <johnv@ac3i.dseg.ti.com>]

Loryn Jenkins wrote:
> 
> equal (l,r: LIST): BOOLEAN is
>       require
>           l /= Void and r /= Void
>       do
>           from
>               Result := (l.count = r.count)
>               l.start; r.start
>           until
>               not Result or l.off
>           loop
>               Result := (l.item = r.item)
>               l.forth; r.forth
>           end
>       end

This has a certain elegance, but note that:

(1) If Result is False after the first assignment, then the 'start'
calls are executed unnecessarily.

(2) If Result is False after the second assignment (in the body of the
loop), then the 'forth' calls and the 'off' test are executed
unnessarily.

This is inefficient (as you point out) but at least it is harmless ...
in this case. (More on that in a moment.)

However, suppose Eiffel allowed mid-body loop exits, say with the
following sort of syntax:

equal (l, r: LIST): BOOLEAN is
    require
        l /= Void and r /= Void
    do
	Result := (l.count = r.count)
	if Result then
            from
                l.start; r.start
            until
                l.off
            loop
                Result := (l.item = r.item)
            until 
                not Result
            then
                l.forth; r.forth
            end
        end
    end

The 'if' statement avoids the extraneous 'start' calls.  The mid-body
'until' clause terminates the loop immediately if its condition holds,
avoiding the extraneous 'forth' calls, as well as the 'off' test at the
top of the loop.

Can anybody demonstrate whether or not this sort of language extension
would have an adverse affect on Eiffel's principle of DBC, for the case
of loops?

There are situations where extraneous calls in the final loop iteration
would not be so harmless.  For instance, suppose you wished to implement
an 'out' function for a LIST class that generated strings of the form:

	"{}"    for an empty list
	"{A}"   for a list with one element "A"
	"{A, B}" for a list with two elements "A" and "B"
        etc...

In other words, separate the elements by commas, but only if there is
more than one element.  Here's a first attempt at a solution:

out: STRING is
    do
        Result := "{";
        from
            start
        until
            after 
        loop
                Result.append (item.out)
                Result.append (", ");
                forth
            end loop
        end
        Result.append ("}");
    end

Unfortunately, this is incorrect, because it places an extraneous comma
after the last element.  To correct this, we could add a test within the
body:

out: STRING is
    do
        Result := "{";
        from
            start
        until
            after 
        loop
            Result.append (item.out)
            forth
            if not after then
               Result.append (", ");
            end
        end loop
        Result.append ("}");
    end

Unfortunately, this causes the same 'after' test to be called twice on
each iteration!  To avoid this, we must unroll the loop:

out: STRING is
    do
        Result := "{";
        if not empty then
            from
                start
                Result.append (item.out)
                forth
            until
                after 
            loop
                Result.append (", ");
                Result.append (item.out)
                forth
            end loop
        end
        Result.append ("}");
    end

Unfortunately, we've been forced to duplicate code.  But suppose you
could place an 'until' clause in mid-body:

out: STRING is
    do
        Result := "{"
        if not empty then
            from
                start
            loop
                Result.append (item.out)
                forth
            until
                after
            then
                Result.append (", ")
            end
        end
        Result.append ("}")
    end                

This would seem the most elegant solution.  But again, does this pose
any difficulty for DBC in Eiffel?  I can't see any problem, but I'm only
a newbie with Eiffel.  (Just now in the process of devouring OOSC2 from
one cover to the other...)

-- 
indexing
   description: "Signatures for John Volan"
   self_plug: "Ex Ada guru", "Java 1.1 Certified", "Eiffelist wannabe"
   two_cents: "Java would be even cooler with Eiffel's generics, %
              %assertions/DBC, true MI, feature adaptation, %
              %selective export, uniform access, etc., etc..."
class JOHN_VOLAN_SIGNATURE inherit SIGNATURE invariant
   disclaimer: not (opinion implies employer.opinion)
end -- class JOHN_VOLAN_SIGNATURE