loop variants (Re: ^^^^^ignore the previous post) 
Author Message
 loop variants (Re: ^^^^^ignore the previous post)

: I can't believe I did this mistake. I am so used to type for(  ;  ;  ;)
: in C, ++, I haven't even noticed that I forgot to increment the index.

This is a good reason to include a loop variant in your loops. I often
forget to increment loop indexes, a variant will let you know what
you've done wrong. The following template is a good starter

        from
                index : = start
        variant
                index_altered: end - index + step
        until
                index > end
        loop
                ...
                index := index + step
        end

One day I'll get around to encapsulating this in a class...
----------------------------------------------------------------------

A loop variant?? I knew about loop invariants, but haven`t heard anything
about loop variants. Are they a way of telling the run-time system that a
particular variable will always change at each pass of the loop? Otherwise
you get a run-time error or something?

---------------------------------------------------------------------
Burak Bayramli








   Is it enough?????

---------------------------------------------------------------------



Fri, 18 Oct 1996 22:57:54 GMT  
 loop variants (Re: ^^^^^ignore the previous post)


Quote:
>It seems like a nuisance as a beginner to try to create all of your
>loops with documentary assertions about invariants, variants, etc,
>particularly if you're coming from a background in a quick&dirty
>language like C or C++. But it ends up being tremendously useful and
>well worth the effort - both because of the errors it catches, and
>because of the clarity and completeness it makes you add to your
>design.

Let me emphasize the word "well-worth".  Beginners are usually working
on small projects and in such a case, it's often "obvious" what's going
wrong and getting in and changing it is easy.  In such cases, it may
be debatable whether it's "worth it" to do the extra typing.

However, when one is debugging an error in a massive project, written
and rewritten over many many years by a team of hundreds of engineers,
having an immediate indication of where the problem lies instead of
having to trace through hundreds of thousands of lines of code to find
it is well-worth it--and quite measureable in terms of programmer-hours
wasted.  Ten seconds of typing can save days or weeks of debugging.

This, like backing up ones hard disk, is usually only learned after
personally experiencing what happens when you don't do it.  (I think
CompSci programs would do well to maintain some large, long-term--i.e.,
multi-year--projects so that students would get a chance to maintain
code designed and written by someone else, and to see the results of
short-term decision-making in the long-term economics of software
maintenance.)

In short, as with many things, while I may not think that it's worth the
time for *me* to put the assertions into the code (after all, *I* never
make mistakes), in retrospect, it would always have been worth it for
that *other* engineer to put assertions into her/his code.

The next step after that is to recognize that to the other engineer,
*you* are "the other engineer."  Hopefully, reciprocal cooperation
kicks in somewhere.

--Eric



Sat, 19 Oct 1996 04:31:47 GMT  
 loop variants (Re: ^^^^^ignore the previous post)

bbayraml> did this mistake. I am so used to type for( ; ; ;) : in C,
bbayraml> ++, I haven't even noticed that I forgot to increment the
bbayraml> index.

bbayraml> This is a good reason to include a loop variant in your
bbayraml> loops. I often forget to increment loop indexes, a variant
bbayraml> will let you know what you've done wrong. The following
bbayraml> template is a good starter

bbayraml>    from index : = start variant index_altered: end -
bbayraml> index + step until index > end loop ...  index := index +
bbayraml> step end

bbayraml> One day I'll get around to encapsulating this in a class...
bbayraml> ----------------------------------------------------------------------

bbayraml> A loop variant?? I knew about loop invariants, but haven`t
bbayraml> heard anything about loop variants. Are they a way of
bbayraml> telling the run-time system that a particular variable will
bbayraml> always change at each pass of the loop? Otherwise you get a
bbayraml> run-time error or something?

A loop variant is an assertion, which claims that some positive value
will decrease on every iteration of the loop. If a variant is
declared, then every loop will either terminate correctly, or generate
an assertion violation which documents exactly why the loop wouldn't
be guaranteed to terminate correctly.

It seems like a nuisance as a beginner to try to create all of your
loops with documentary assertions about invariants, variants, etc,
particularly if you're coming from a background in a quick&dirty
language like C or C++. But it ends up being tremendously useful and
well worth the effort - both because of the errors it catches, and
because of the clarity and completeness it makes you add to your
design.

        <MC>
--
|| Mark Craig Carroll: <MC>     ||"Don't ever think that you can't
|| CIS Grad, Univ of Delaware   ||    change the past
|| PGP key available            ||       or the future"



Sat, 19 Oct 1996 01:15:05 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. installing mit scheme 7.3 - ignore previous post

2. Ignore previous post

3. question about lazy and/or - IGNORE MY PREVIOUS POST

4. Please Ignore Previous Posting

5. Tclhttpd and Threads (Pls ignore previous one as it was from the wrong account)

6. Loop, Next, Previous

7. Why reliable loop variants must non-INTEGER expressions

8. Boyer & Moore style loop variants

9. More fun with loop (in)variants

10. Why loop variants are integers (MS/BM)

11. EiffelStudio 5: loop variant incorrectly implemented?

12. Loop variant when using an iterator?

 

 
Powered by phpBB® Forum Software