Re: Software landmines (loops)

[Loryn Jenkins <loryn@s054.aone.net.au>]

Matthew Heaney wrote:
> 
> Loryn Jenkins <loryn@s054.aone.net.au> writes:
> 
> >
> >  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
> >                                not Result or l.off
> >                        loop
> >                                Result := l.item /= r.item
> >                                l.forth; r.forth
> >                        end
> >                end
> >        end
> >
> >
> > > The way I look at this problem, is that it's like searching for a
> > > specific house on an unfamiliar block.  As you're driving, when you find
> > > the house, you stop immediately and declare success.  You don't have to
> > > drive to the end of the block, and then say where the house was.
> >
> > Yeah, yeah. Same here, given the amended code.
> 
> No, no, not the same here.
> 
> If the test l.count /= r.count returns False, then you know immediately
> what the return value of the function is, so why not deliver that
> information right away?  That way you can remove the test of result
> (reducing the level of nesting), and simplify the predicate,
> 
> (By way of analogy, if you've found the house, then you can park in the
> driveway right way, instead of driving to the end of the block to
> announce that you found the house.)
> 
> Let's once again compare the decision tables.  If we re-write the code,
> to put it into Matt-like (because Matt likes it) syntax:
> 
> equal (l,r: LIST): BOOLEAN is
>       require
>               l /= Void and r /= Void
>       do
>               if l.count /= r.count then
>                  return False
>               end
> 
>               from
>                  l.start; r.start
>               until
>                  l.off
>               loop
>                  if l.item /= r.item then
>                     return False
>                  end
> 
>                  l.forth; r.forth
>               end
> 
>               return True
>       end
> 
> This version has only two rules in the decision table for the loop predicate:
> 
>        1  2
> l.off  T  F
> 
> The uncorrected version has four rules:
> 
>             1  2  3  4
> not Result  T  T  F  F
> l.off       T  F  T  F
> 
> The difference in styles is really a debate about the number of edges in
> the flow graph vs the number of rules in the decision table.

That we can agree on. But also note James Weirich's comment:

>Yes, but you are ignoring the fact that there are now two loop exits.
>If you ask the question "When will the loop terminate?", you must
>consider all the exits, including the early return.
>
>So instead of a single, 2 entry table, you have two 2-entry tables.
>Combining them into a single table will produce the same 4 entry table
>as the one you produced for Loryn Jenkins's code.
>
>Seems to me the complexity is about equivalent.

Now, someone else was kind enough to show me an even simpler way of
doing this ... albeit marginally less efficient (and again, I don't care
about this criteria, unless my application beforms below specification
and my profiler shows me that this is a hot spot).

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, at least, loses your nesting objection. In fact, it has less
nesting than your original example. However, it might mislead unless the
reader was aware of this sort of idiom. (It does simplify things though;
so I think I'll be using this style, where appropriate.)

Loryn Jenkins