Re: Expressive Case Statements (was: Software landmines)

Re: Expressive Case Statements (was: Software landmines)

[Brian Rogoff]

On Tue, 1 Sep 1998, Richard D Riehle wrote:
>  I realize this was supposed to be about optimizations. But this is the
>  year of changing the subject what with tails wagging dogs, etc. Ted's
>  mention of "case statements" reminds me of a problem with which I have
>  been struggling for quite a while; one for which I finally cry, "Help!"
> 
>  There is a language called COBOL in which the ANSI 1995 standard 
>  introduced a fascinating construct called the EVALUATE statement. It
>  is the most powerful form of a case statement I have seen in any
>  programming language. More powerful than Ada. More powerful than Eiffel.
>  More powerful than C++ or Java. 

Unfortunately, I don't COBOL, but I think I can read your case statement
below, and I wonder if the following, in Objective Caml, does the trick:
> 
>  One of the forms the EVALUATE statement (there are several options), 
>  allows the programmer to directly represent a decision-table for a
>  set of conditions with syntax such as,
> 
>         EVALUATE condition-1 ALSO condition-2 ALSO condition-3 
>                              
>            WHEN TRUE ALSO TRUE ALSO FALSE 
>                           PERFORM 
>                               some action-stub statements
>                           END-PERFORM
>            WHEN TRUE ALSO FALSE ALSO FALSE
>                           PERFORM 
>                               some action-stub statements
>                           END-PERFORM
>            WHEN FALSE ALSO FALSE ALSO TRUE
>                           PERFORM 
>                               some action-stub statements
>                           END-PERFORM
>         END-EVALUATE

let get_val b1 b2 b3 =  
	match (b1, b2, b3) with 
	| (true, true, false) ->
	perform1	
	| (true, false, false) ->
	perform2
	| (false, false, true) ->
	perform3
	| (_,_,_) ->  perform_default;;

I think ML style pattern matching is pretty powerful compared to Ada's,
and Prolog's even more so. 

> In business data process software, such as banking and insurance, the
> decision table is useful for representing complex sets of conditions
> and their corresponding actions.  In military command and control
> systems we also see these kinds of complex condition sets.
> 
> It is certainly easy to represent any set of conditions with a sequence
> of if ... elsif statements but I am seeking something else.  What I have
> been trying to accomplish is some generalized algorithm in Ada that 
> allows me to design a package that approximates the power of the EVALUATE
> statement in COBOL.  Some of the new features of Ada 95 such as generic
> formal package parameters, access to subprogram, etc. have helped a
> little, but ...

As I'm sure you know, you need to create mapping functions to an
enumerated type or something similar in order to use Ada's case statement. 
I don't think there is a general solution, you can't even use tags in 
case statements. Yeah, I prefer ML for its more powerful pattern matching,
but Ada has her charms too. I guess we Ada fans will have to do this by 
hand; we also have to do it by hand if we want to translate our close 
cousin language VHDL's case statement to Ada.

-- Brian

Re: Why C++ is successful

[Jeffrey C. Dege]

On 8 Aug 1998 08:27:02 -0400, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>
>Undoubtedly at least *part* of the problem in using C is that people are not
>sufficiently aware of what can go wrong. Microsoft has a rather amazing
>book that pretends to be a book about software techniques, but in fact is
>little more than a set of perfectly standard coding procedures to avoid
>pitfalls in C. When I read it, I was surprised that professional C 
>programmers would find such a book useful, but the questions above are
>a reminder that you often people are not aware of the dangers. 

If you're talking about Steve McGuire's books, (Code Complete, Writing
Solid Code), I'm a professional C programmer, and I didn't find anything
in them that I hadn't been aware of for many years.

>I must
>say I worry about CS curriculums in which people are only getting exposed
>to C and C++ and hence simply don't register important language design
>principles (after all the idea that it is obviously a bad idea to allow
>pointers to local variables is a very old one, dating back at least to
>Pascal, which means coming up to 30 years.

I have to agree with the above.  A CS curriculumn should have some breadth
to it.  Exposure to a variety of languages is a part of this, as is
instruction in the theory underlying compilers.

-- 
The most exciting phrase to hear in science, the one that heralds new
discoveries, is not "Eureka!" ("I found it!") but rather "hmm....that's
funny..."  --   Isaac Asimov

Re: Why C++ is successful

[Laurent GUERBY]

jdege@jdege.visi.com (Jeffrey C. Dege) writes:

> On 8 Aug 1998 08:27:02 -0400, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
> >
> >Undoubtedly at least *part* of the problem in using C is that people are not
> >sufficiently aware of what can go wrong. Microsoft has a rather amazing
> >book that pretends to be a book about software techniques, but in fact is
> >little more than a set of perfectly standard coding procedures to avoid
> >pitfalls in C. When I read it, I was surprised that professional C 
> >programmers would find such a book useful, but the questions above are
> >a reminder that you often people are not aware of the dangers. 
> 
> If you're talking about Steve McGuire's books, (Code Complete, Writing
> Solid Code), I'm a professional C programmer, and I didn't find anything
> in them that I hadn't been aware of for many years.
> [...]

   "Code Complete" author is Steve McConnell, not Steve McGuire.  I
think Robert talks about the latter.

   The former, "Code Complete", is a very nice book IMHO, and amongst
the languages covered there is Ada (together with C/C++/Pascal/VB).
It makes a nice advocacy package for strongly typed language BTW (you
can shoot yourself into the foot easily with language X whereas you
get an error message with language Y ;-).

   A little quote for c.l.a. readers, from the "goto" pro and cons
section (reminds me of some threads ;-):

"Finally, the goto was incorporated into the Ada language, the most
carefully engineered programming language in history. Ada was
developped long after the arguments on both sides of the goto debate
had been fully developped, and after considering all sides of the
issue, Ada engineers decided to include the goto"

-- 
Laurent Guerby <guerby@bnp-eng.remcomp.com>, Team Ada, Linux/GNU addict
   "Use the Source, Luke. The Source will be with you, always (GPL)."

Re: Why C++ is successful

[Andy Ward]

>   A little quote for c.l.a. readers, from the "goto" pro and cons
>section (reminds me of some threads ;-):
>
>"Finally, the goto was incorporated into the Ada language, the most
>carefully engineered programming language in history. Ada was
>developped long after the arguments on both sides of the goto debate
>had been fully developped, and after considering all sides of the
>issue, Ada engineers decided to include the goto"
>


Ahh... but have you ever found a "good" reason for using it? I have used
goto in C and Pascal in certain rare cases, but I have always found clearer
ways to code these cases in Ada.

Re: Why C++ is successful

[Robert Dewar]

Andy said

<<Ahh... but have you ever found a "good" reason for using it? I have used
goto in C and Pascal in certain rare cases, but I have always found clearer
ways to code these cases in Ada.
>>

The two obvious uses vfor gotos in Ada are

1) to get a loop "continue" mechanism

2) to write finite state machines encoding the state into the PC. Yes, some
people prefer case statements for this purpose, but many people prefer the
use of labels and gotos as the most obvious translation of labeled states
with arrows between them.

In general, the use of gotos makes sense if the resulting code is clearer
and easier to maintain. THat's relatively rare, but not non-existnent, and
it is quite common to run across tortured code with multiple boolean flags
which can be easily simplified using a goto. 

For example, I find the following perfectly clear:

   <<sort>> for J in 1 .. N - 1 loop
       if D (J) > D (J + 1) then
	  Swap (D(J), D(J + 1));
          goto Sort;
       end if;

It is a little tricky to program this without the goto and not make it
less clear. Actuallky many people who try this end up with a different
algorithm (hint: the above sort is cubic, it is NOT a quadratic bubble sort :-)
\x1adp

Software landmines (was: Why C++ is successful)

[dennison]

In article <dewar.903074236@merv>,
  dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
> Andy said
>
> <<Ahh... but have you ever found a "good" reason for using it? I have used
> goto in C and Pascal in certain rare cases, but I have always found clearer
> ways to code these cases in Ada.
> >>
>
> The two obvious uses vfor gotos in Ada are
>
> 1) to get a loop "continue" mechanism

for a simple loop, embedding the rest of the loop code in the body of the if
statement is clearer. For nested loops where you want to "continue" an outer
loop, I can see it. Not that I'd do such a thing. As a "goto-holic" who has
been straight for 10 years, the best bet is abstinence. One day at a time. :-)

> For example, I find the following perfectly clear:
>
>    <<sort>> for J in 1 .. N - 1 loop
>        if D (J) > D (J + 1) then
> 	  Swap (D(J), D(J + 1));
>           goto Sort;
>        end if;
>
> It is a little tricky to program this without the goto and not make it
> less clear. Actuallky many people who try this end up with a different
> algorithm (hint: the above sort is cubic, it is NOT a quadratic bubble sort
:-)

So the "average" poor maintainer schlep looks at this and thinks "is this
just a continue, or a complete restarting of the loop?" Oh yeah, that's
clear. %-(

If anyone does something this bizzare, they'd better put copious comments
around it explaining its semantics. Otherwise, its the software equivalent of
a land mine. Its just sitting there waiting for someone to touch it, then
...BOOM!

Very good counterexample to your own point.

T.E.D.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re: Software landmines (was: Why C++ is successful)

[Robert Dewar]

T.E.D says

  For a simple loop, embedding the rest of the loop code in the body
  of the if statement is clearer. For nested loops where you want to
  "continue" an outer loop, I can see it. Not that I'd do such a thing.

Even in the simple case:

   for J in 1 .. N loop
     if D (J) = NaN then
       goto Continue;
     end if;

     giant section of code

   <<Continue>> null;
   end loop;

as opposed to

   for J in 1 .. N loop
     if D (J) /= NaN then
        giant section of code
     end if;
   end loop;

there may be a preference for the goto. It shows the reader right up
front that the loop does nothing at all to NaN's, without having to
match up the if with the end if at the end of the giant section of
code to know this. Also, it means that the giant section of code
has one less level of indentation.

But it's a toss up in this case, and for most purposes we would prefer
the second case. Where it gets tricky is

   for J in 1 .. N loop
      if condition 1 then
         ...
         if condition 2 then
            ...
            if conditoin 3 then
               goto Continue;


Now T.E.D's prescription is not so clear, and we end up having to
severely contort things, or introduce a boolean flag which we keep
testing as we unwind to the end.

Remember that the continue here is just like a return. If you are allergic
to using a loop continue or exit, you should be allergic to using a return
(other than at the end of a function). Some people are, and that is at
least consistent. But I see a lot of Ada programmers who will use a return
without hesitation from a nested loop, but still turn green at the sight
of a goto. That makes no sense to me.

  As a "goto-holic" who has been straight for 10 years, the best bet
  is abstinence. One day at a time. :-)

Maybe the comparison is apt. If you really are unable to figure out how
to use gotos properly, then perhaps abstinence is the "best bet", but
just as we know that wine drunk in moderation can actually be a health
benefit, and is most certainly not a health danger, the occasional use
of a goto can be beneficial for the clarity and efficiency of your code.
We can appreciate and sympathize with the poor goto-holic's who may not
risk this, but it does not mean the rest of us have to abstain :-)


  So the "average" poor maintainer schlep looks at this and thinks
  "is this just a continue, or a complete restarting of the loop?"
  Oh yeah, that's clear. %-(

The idea that code can ever be maintained by incompetent shlep's who
do not understand the language they are writing in is of course a serious
error. Yes, I know it happens, look at the results, need I say more?

On the other hand, I see no reason to accept this rhetoric, if indeed
you do have these poor maintainer shleps looking at the code, we have
only T.E.D.'s unsupported allegation that they will have more trouble
with my form than some other form (note that, perhaps wisely, T.E.D
does not attempt to demonstrate the beautifully clear, alternative,
goto-free form -- enough other competent people have tripped on that
already :-)

  If anyone does something this bizzare, they'd better put copious
  comments around it explaining its semantics. Otherwise, its the
  software equivalent of a land mine. Its just sitting there waiting
  for someone to touch it, then ...BOOM!

Well of course any code needs commenting, and pointing out the critical
details of the algorithm in use, especially if, as in this case, it is
likely to be an unfamiliar algorithm, is definitely a good idea.

   Very good counterexample to your own point.

I don't think so!

Re: Software landmines (was: Why C++ is successful)

[dennison]

In article <dewar.903281994@merv>,
  dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
> T.E.D says
>
> But it's a toss up in this case, and for most purposes we would prefer
> the second case. Where it gets tricky is
>
>    for J in 1 .. N loop
>       if condition 1 then
>          ...
>          if condition 2 then
>             ...
>             if conditoin 3 then
>                goto Continue;
>
> Now T.E.D's prescription is not so clear, and we end up having to
> severely contort things, or introduce a boolean flag which we keep
> testing as we unwind to the end.
>
> Remember that the continue here is just like a return. If you are allergic
> to using a loop continue or exit, you should be allergic to using a return
> (other than at the end of a function). Some people are, and that is at
> least consistent. But I see a lot of Ada programmers who will use a return
> without hesitation from a nested loop, but still turn green at the sight
> of a goto. That makes no sense to me.
>

Good point. Typically in this case I would "cheat" it and embed the inside of
the loop in a subprogram, with a return statement. You think that's no better
than using a "goto". I think it IS better, because the rule for where control
goes to after a return statement is much clearer than for goto. For the
return, I just start reading code after the subprogram call. For goto, I have
to search the entire source for the label that is being jumped to. Just as
importantly, someone can completely change my structure just by moving that
label. But yes, we are probably talking Bordeaux vs. Mad Dog 20-20.

>   So the "average" poor maintainer schlep looks at this and thinks
>   "is this just a continue, or a complete restarting of the loop?"
>   Oh yeah, that's clear. %-(
>
> On the other hand, I see no reason to accept this rhetoric, if indeed
> you do have these poor maintainer shleps looking at the code, we have
> only T.E.D.'s unsupported allegation that they will have more trouble
> with my form than some other form (note that, perhaps wisely, T.E.D
> does not attempt to demonstrate the beautifully clear, alternative,
> goto-free form -- enough other competent people have tripped on that
> already :-)

Why take my word for it? The very fact that "other competent people have
tripped on that" proves how obtuse it is. You'd be quite lucky to have a
maintanence staff as good as the folks here on c.l.*, and *they* can't even
make a simple change to your code without completely screwing it up. I
couldn't hope to come up with a better example.

T.E.D.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re: Software landmines (was: Why C++ is successful)

[ell]

In article <6r9f8h$jtm$1@nnrp1.dejanews.com>,
  dennison@telepath.com wrote:
> In article <dewar.903281994@merv>,
>   dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
> > T.E.D says
> >
> > But it's a toss up in this case, and for most purposes we would prefer
> > the second case. Where it gets tricky is
> >
> >    for J in 1 .. N loop
> >       if condition 1 then
> >          ...
> >          if condition 2 then
> >             ...
> >             if conditoin 3 then
> >                goto Continue;
> >
> > Now T.E.D's prescription is not so clear, and we end up having to
> > severely contort things, or introduce a boolean flag which we keep
> > testing as we unwind to the end.
> >
> > Remember that the continue here is just like a return. If you are allergic
> > to using a loop continue or exit, you should be allergic to using a return
> > (other than at the end of a function). Some people are, and that is at
> > least consistent. But I see a lot of Ada programmers who will use a return
> > without hesitation from a nested loop, but still turn green at the sight
> > of a goto. That makes no sense to me.

A 'return', at least in C/C++/VB, returns you to the place the current
procedure was called from.  'goto' control flow can be endlessly channeled
here and there and never has to return to where the initial linear control
flow was originally diverted.  That seems to be a huge advantage of 'return'
over 'goto'.

Elliott

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re: Software landmines (was: Why C++ is successful)

[adam]

In article <6renh8$ga7$1@nnrp1.dejanews.com>,
  ell@access.digex.net wrote:

> A 'return', at least in C/C++/VB, returns you to the place the current
> procedure was called from.  'goto' control flow can be endlessly channeled
> here and there and never has to return to where the initial linear control
> flow was originally diverted.  That seems to be a huge advantage of 'return'
> over 'goto'.

No, to me this seems to be a huge advantage of "return" over "using too many
goto's in your code that go every which way so that your code ends up looking
like spaghetti."  No one is supporting the idea of using that many goto's,
the way programmers used to.  Those who think goto's are OK think they should
be limited to certain specific situations, and your objection really doesn't
apply when goto's are used in that sort of careful, disciplined fashion.  Of
course, "goto" can be dangerous in the hands of an inexperienced programmer;
but so, for that matter, can every other construct of every language.

In the 22 years or so since programmers have started treating "goto" as an
evil, I've seen some pretty strange arguments purporting to explain *why*
goto's were bad.  The most bizarre one I've seen argued that if your code is
structured as follows:

         Transformation-1;  goto L;  Transformation-2;  L: ....

where Transformation-1 and Transformation-2 are sequences of statements or
something else that transform your current program state from one thing to
another, then the presence of "goto" in effect means that your code contains
the inverse function of Transformation-2, which cancels the effect of
Transformation-2.  The author offered this as an explanation why "goto" makes
code harder to understand.  I don't remember exactly where I read this, but it
was in one of the ACM publications.

Of course, this is nonsense.  There are good reasons why a researcher might
want to think of a "program" as a sequence of mathematical transformations on
the program state, but an ordinary programmer trying to write correct code,
or to read or maintain someone else's code, isn't going to think about things
that way.  That's why I'm skeptical about most of the arguments I see about
why GOTO IS EVIL.  There often seems to be an implicit assumption that
mathematical purity, or an aesthetically beautiful program structure, or
something similar, equals readability, but that isn't the case.  So when I
see statements like "'goto' control flow can be endlessly channeled here and
there and never has to return to where the initial linear control flow was
originally diverted", my reaction is, "So what?"  This argument contains no
explanation *why* this makes programs harder to work with.

So, personally, I think arguments against "goto" (or against any other
construction) should demonstrate things from the programmer's point of view.
That is, how does this EVIL NASTY construct actually make it harder for a
programmer to understand what's going on, or make it easier for a programmer
to miss something and write incorrect code?  If the argument doesn't address
the issue from that angle, it's worthless, IMHO.

Now, here are a couple arguments on the other side:

(1) Say you want to avoid the EVIL NASTY "goto" by putting the code into a
subroutine and using "return".	Well, you have to give the subroutine a name.
In place of the nested "if" causing the problem, you'll have a call to this
subroutine.  Now, when a programmer looks through the main line of code,
she'll see a call to this subroutine, and she'll have to know what it does. 
Can you give the subroutine a name that will make it obvious to the
maintenance programmer what's going on?

Sometimes you can.  But if all you're doing is extracting some code and
sticking it in a subroutine, most of the time you can't give it a good
descriptive name, since it reflects just a random sequence of statements and
not a concept that can be easily compartmentalized.  So in this case, IMHO
doing this is worse than using "goto", since it makes the program less clear.
 Of course, you can probably figure out a way to redesign the code to make it
clear, and your code will be more readable since it has smaller, more compact
subroutines that perform a well-defined purpose.  But this just illustrates
the importance of good design in general; a programmer who simply says
"RETURN is a lot better than GOTO" and moves code around just to avoid the
GOTO is unlikely to end up with a more readable and maintainable program.

(2) (This one is about "continue", since Charles Hixson later argued that this
was also superior to "goto" for the same reasons.)  If you have a loop that
looks like:

     while (blah-blah) {
          some-if-statements...
          some-more-if-statements...

          xxx;
          yyy;
          zzz;
     }

someone reading the program might assume that xxx, yyy, and zzz are always
going to happen before the loop repeats.  So if there's something new that
needs to be done during every loop iteration, it looks like you can just add
it to the end of the loop, after zzz.  If there's a "continue" statement
somewhere above that, this assumption is incorrect and your modification may
well be wrong.	If you replace the "continue" with a "goto", at least there
will be a label somewhere toward the bottom of the loop, alerting you to the
fact that you will have to decide whether to put the new code before or after
the label, or look for the place where this label is goto'ed.  In fact, this
is exactly why I stopped using "continue" when I was a C programmer.  (I
didn't replace them with goto's, I used Boolean flags instead.)

Now all of this may be a matter of how each individual programmer tends to
think when they look at programs.  The point is that, based on my experience,
arguments about "returning to where the linear control flow was diverted" and
"restricted compass" don't make a whole lot of sense in the real world.  GOTO
can be used in ways that enhance readability or in ways that impair it, and
so can every other feature of every language.

				-- Adam

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re: Software landmines (was: Why C++ is successful)

[Dan Higdon]

adam@irvine.com wrote in message <6rf59b$2ud$1@nnrp1.dejanews.com>...

<snip prelude>

>Now, here are a couple arguments on the other side:

<snip point 1>


>(2) (This one is about "continue", since Charles Hixson later argued that
this
>was also superior to "goto" for the same reasons.)  If you have a loop that
>looks like:
>
>     while (blah-blah) {
>          some-if-statements...
>          some-more-if-statements...
>
>          xxx;
>          yyy;
>          zzz;
>     }
>
>someone reading the program might assume that xxx, yyy, and zzz are always
>going to happen before the loop repeats.  So if there's something new that
>needs to be done during every loop iteration, it looks like you can just
add
>it to the end of the loop, after zzz.  If there's a "continue" statement
>somewhere above that, this assumption is incorrect and your modification
may
>well be wrong. If you replace the "continue" with a "goto", at least there
>will be a label somewhere toward the bottom of the loop, alerting you to
the
>fact that you will have to decide whether to put the new code before or
after
>the label, or look for the place where this label is goto'ed.  In fact,
this
>is exactly why I stopped using "continue" when I was a C programmer.  (I
>didn't replace them with goto's, I used Boolean flags instead.)

So, you've actually changed the algorithm of your code, added an unnecessary
data item and added yet another compare/branch to avoid a well understood
(IMHO) construct of the C language?  Perhaps I'm the only one who thinks
writing
code that will execute efficiently is equally important as writing readable
code.
If I didn't care about efficiency, I sure wouldn't be using a 3rd generation
procedural
language (OO or not) - there are (IMHO) many more succinct and
mathematically
rigorous languages out there than C or Eiffel (ML and Haskell come to mind,
niether of which have gotos, fwiw).

I'm not trying to start a language war - I'm pointing out that gotos and the
implicit
goto forms (break, continue, etc) are a tool of the language.  They wouldn't
be
there if you NEVER needed them.  So if you have a case that warrants their
use,
you should use them, rather than trying to hamstring yourself with hokey
constructs.
If you *need* that boolean value later, then by all means add it.  But I
think that
using a boolean flag to erase a GOTO is not contributing to the solution,
just
adding inefficiency into the generated code, and one more symbol for the
programmer to have to track.

----------------------------------------
hdan@charybdis.com
"Throwing fire at the sun"

Re: Software landmines (was: Why C++ is successful)

[adam]

In article <l5HC1.6840$wN.1856764@news.giganews.com>,
  "Dan Higdon" <hdan@charybdis.com> wrote:

>
> adam@irvine.com wrote in message <6rf59b$2ud$1@nnrp1.dejanews.com>...
>
> <snip prelude>
>
> >Now, here are a couple arguments on the other side:
>
> <snip point 1>
>
> >(2) (This one is about "continue", since Charles Hixson later argued
> >that this was also superior to "goto" for the same reasons.)  If
> >you have a loop that looks like:
> >
> >     while (blah-blah) {
> >          some-if-statements...
> >          some-more-if-statements...
> >
> >          xxx;
> >          yyy;
> >          zzz;
> >     }
> >
> >someone reading the program might assume that xxx, yyy, and zzz are
> >always going to happen before the loop repeats.  So if there's
> >something new that needs to be done during every loop iteration, it
> >looks like you can just add it to the end of the loop, after zzz.
> >If there's a "continue" statement somewhere above that, this
> >assumption is incorrect and your modification may well be wrong. If
> >you replace the "continue" with a "goto", at least there will be a
> >label somewhere toward the bottom of the loop, alerting you to the
> >fact that you will have to decide whether to put the new code
> >before or after the label, or look for the place where this label
> >is goto'ed.  In fact, this is exactly why I stopped using
> >"continue" when I was a C programmer.  (I didn't replace them with
> >goto's, I used Boolean flags instead.)
>
> So, you've actually changed the algorithm of your code, added an
> unnecessary data item and added yet another compare/branch to avoid
> a well understood (IMHO) construct of the C language?  Perhaps I'm
> the only one who thinks writing code that will execute efficiently
> is equally important as writing readable code.  If I didn't care
> about efficiency, I sure wouldn't be using a 3rd generation
> procedural language (OO or not) - there are (IMHO) many more
> succinct and mathematically rigorous languages out there than C or
> Eiffel (ML and Haskell come to mind, niether of which have gotos,
> fwiw).

Well, I might have used GOTO if I had to do it over again.  My early
training taught me to avoid them, and this avoidance has become kind
of ingrained.  I still probably wouldn't use "continue", however.

However:

#1: Adding a flag in the manner I've described does not change the
algorithm, it merely changes the way the flow of control is expressed.
Unless you adopt a definition of "algorithm" that is so strict as to
be useless except to an academic.

#2: How important efficiency is depends on what you're writing.  If
you're working on time-critical code, it's very important, but if
you're working on an application where most of the program's time will
be spent waiting for the user to type in some input, a few hundred
microseconds isn't anything to worry about.

#3: A good optimizing compiler wouldn't do a compare/branch.  It might
set the flag, then notice that the next thing done is to test it, so
it would blow off the test and just branch to wherever the "continue"
statement was going to branch anyway.  An even better optimizing
compiler would then figure out that the flag is never actually tested,
so it would just get rid of it.

#4: Programmers don't always get to choose which language they use.

#5: In this thread, we're arguing about readability and
maintainability.  If you have a situation where every nanosecond is
critical, fine, but most of us are willing to give up a few
nanoseconds in order to save time debugging and maintaining programs.
If you've ever written a subroutine that was called at only one point
in the rest of the program, instead of coding it inline so that you
can avoid an unnecessary procedure call with all the stack pushes and
pops, then certainly you have to admit that readability is worth
sacrificing a couple machine cycles for, sometimes.


> I'm not trying to start a language war - I'm pointing out that gotos
> and the implicit goto forms (break, continue, etc) are a tool of the
> language.  They wouldn't be there if you NEVER needed them.

There are lots of language constructs that aren't really "needed".
And there are plenty of cases where an individual programmer, or a
programming department, adopts a policy of avoiding a particular
construct, which is fine as long as the prohibition isn't 100%
absolute.  A long time ago, I programmed in COBOL, and most of the
programmers around me agreed that the ALTER statement was just a bad
idea and shouldn't be used.  I'll bet few would disagree with such a
policy.

                                -- Adam

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re: Software landmines (loops)

[Nick Leaton]

I have just done a quick check through some Eiffel code. 

Out of 633 loops, just 1 needed a flag for early termination of the
loop.

-- 

Nick

Re: Software landmines (loops)

[Matthew Heaney]

Nick Leaton <nickle@calfp.co.uk> writes:

> I have just done a quick check through some Eiffel code. 
> 
> Out of 633 loops, just 1 needed a flag for early termination of the
> loop.

My own experience is quite different from yours.  Although I haven't
counted, I use early loop termination ALL THE TIME.

For example, I routinely implement an equality test (say, for a stack)
as

function "=" ... return Boolean is
begin
...

  for Index in Positive range 1 .. L.Depth loop
     if L.Items (Index) /= R.Items (Index) then
        return False;
     end if;
  end loop;

  return True;

end "=";


If my loop termination depends on a value I just read, then exit from
the middle is the simplest solution:

loop
   Get (N);

   exit when N = 0;

   <process N>
end loop;

For example, this is a simplest way to tokenize a lexeme.  You exit the
loop in the middle, after determining that the character just consumed
isn't part of the current token.

Exiting is how you terminate passive iteration early:

procedure For_Every_Item (Stack : in Stack_Type) is
 
   Done : Boolean := False;

begin

   for Index in reverse Positive range 1 .. Stack.Top loop
      Process (Stack.Items (Index), Done);
      exit when Done;
   end loop;

end For_Every_Item;


Searching is also implemented using early loop termination:

function Get_Position
  (C : Character; 
   S : String) return Natural is
begin
   for Index in S'Range loop
      if S (Index) = C then
         return Index;
      end if;
   end loop;

   return 0;
end Get_Position;
   

No auxilliary variables or flags are required.

Below is a portion of my response to another thread on comp.lang.ada re
the goto statement.

Matt

(start of quote)
Any theory about using (or not using) a programming construct needs to
be tested against observation, by performing an empirical study that
measures the defect rates of programmers using the construct.

If theory says use a construct, but observation reveals that programmers
who use the construct produce more errors, then the theory needs to be
thrown out.

For example, there's a pernicious myth that exiting (or returning) from
the middle of a loop is bad, and that the only proper way to write a
loop is to state the termination condition explicitly, as a predicate
appearing at the top of the loop.

This theory was indeed put to the test, and guess what?  Programmers
using a test-and-exit from the middle of the loop produced fewer errors
than those programmers who tried to put the test at the top of the loop.
The researchers found that the exit-from-the-middle construct had a
better "cognitive fit" than the other constructs.

If you want to read the gory details, the article is

Cognitive Strategies and Looping Constructs: An Empirical Study
Soloway, Bonar, Ehrlich
CACM, Nov 83, Vol 26, No 11, p 853-860

The goodness of a language construct should not be determined by
doctrinaire computer scientists or mathematicians.  The only thing that
matters is whether working programmers think it's easier to understand,
and whether by using the construct programmers inject fewer errors into
the code.

I think it was Stroustrup who said, "Programming is a human activity.
Forget that, and all is lost."
(end of quote)

Re: Software landmines (loops)

[Robert Martin]

Matthew Heaney wrote in message ...

>If theory says use a construct, but observation reveals that programmers
>who use the construct produce more errors, then the theory needs to be
>thrown out.

All else being equal, that would be so.  But when observation shows that the
construct reduces the overall cost of maintaining the program, regardless of
its initial cost, then it ought not be thrown out.

>For example, there's a pernicious myth that exiting (or returning) from
>the middle of a loop is bad, and that the only proper way to write a
>loop is to state the termination condition explicitly, as a predicate
>appearing at the top of the loop.

Yes.  That pernicious myth is called "structured programming".

>This theory was indeed put to the test, and guess what?  Programmers
>using a test-and-exit from the middle of the loop produced fewer errors
>than those programmers who tried to put the test at the top of the loop.

>Cognitive Strategies and Looping Constructs: An Empirical Study
>Soloway, Bonar, Ehrlich
>CACM, Nov 83, Vol 26, No 11, p 853-860

Do you know if the citing is on line?  Was the experiment controlled?  Did
the experiment measure long term cost?  Were the participants engineers who
had been used to min-loop exits, and were strugging with a new concept?

My own experience is counter to the results of this study.  It is far easier
to understand a loop if the looping criteria are present in one place; and
the loop has a single, well known, exit.

>The researchers found that the exit-from-the-middle construct had a
>better "cognitive fit" than the other constructs.

"Cognitive fit" is probably not a very good criterion for good engineering.
GOTO has a very good cognitive fit.  So does a flat Earth.

>The goodness of a language construct should not be determined by
>doctrinaire computer scientists or mathematicians.  The only thing that
>matters is whether working programmers think it's easier to understand,
>and whether by using the construct programmers inject fewer errors into
>the code.

And whether or not the construct is maintainable over the long term.  There
are lots of constructs that make writing the initial program easy, but make
maintaining it hard.  The practice of using such constructs, i.e. ignoring
long term effects, is sometimes called "hacking".
>
>I think it was Stroustrup who said, "Programming is a human activity.
Forget that, and all is lost."


Precisely!  Programming is an activity of human creativity and human
frailty.  Forget either part, and all is lost.

Robert C. Martin    | Design Consulting   | Training courses offered:
Object Mentor       | rmartin@oma.com     |   Object Oriented Design
14619 N Somerset Cr | Tel: (800) 338-6716 |   C++
Green Oaks IL 60048 | Fax: (847) 918-1023 | http://www.oma.com

"One of the great commandments of science is:
    'Mistrust arguments from authority.'" -- Carl Sagan

Re: Software landmines (loops)

[Matthew Heaney]

"Robert Martin" <rmartin@oma.com> writes:

> >>>For example, there's a pernicious myth that exiting (or returning) from
> >>>the middle of a loop is bad, and that the only proper way to write a
> >>>loop is to state the termination condition explicitly, as a predicate
> >>>appearing at the top of the loop.
> >
> >>Yes.  That pernicious myth is called "structured programming".
> >
> >Please cite even just a single structured programming text, or founder
> >where what you say here was asserted.
> 
> "Structured Programming", Dijkstra, Dahl, Hoare, Academic Press, 1972. p.
> 16-23 "7. On Understanding Programs".

You might also want to read Structured Programming: Theory and Practice,
by Linger, Mills, and Witt (Addison-Wesley, 1979).

(It was Harlan Mills to whom I was alluding when I referred to
"doctrinaire mathematicians."  I've read his work, and what can I say,
it just doesn't speak to me.)

I also very highly recommend The Science of Programming, by David Gries.
He comes from the Dijkstra/Hoare school, and I find his advice a lot
more useful.  But your mileage may vary.


> Actually this section says that there are two different kinds of
> loops. one that is tested at the top; and another which is tested at
> the bottom.  But in all cases, the elements of structure programming
> have a single entry and a single exit.  A loop that exits in the
> middle, violates this maxim.

I think the issue is meaning vs syntax.  When I use an exit from the
middle, it's to say that "I want to terminate the loop, NOW."  

The problem with exit at the top is that it defers the actual
termination.  I have to make sure no code gets executed unintentionally
between the place at which the exit flag is set, and the bottom of the
loop.

I can almost live that.  The real problem, however, is that using an
extra flag to terminate VASTLY complicates the predicate.  In fact, the
flag doubles the number of states I have to think about when mentally
evaluating the predicate!  That's the real source of the loop
termination errors.

(I shouldn't have to remind anyone, but just in case: George Miller did
a famous study about human cognitive limits, and found that people can
remember about 7 things, plus or minus 2.  That's why complex predicates
make a programmer's head spin, and why he often gets loop termination
wrong.)

Using an exit from the middle avoids the headaches (literally)
engendered by using an extra flag in the predicate.  When you want to
exit, you just say that you want to exit, directly.  No mental
gymnastics are required in order to determine whether you'll "really"
exit, as would be the case using the flag approach.

Re: Software landmines (loops)

[Andrew Hussey]

In <m3af4mq7f4.fsf@mheaney.ni.net> Matthew Heaney <matthew_heaney@acm.org> writes:

>I can almost live that.  The real problem, however, is that using an
>extra flag to terminate VASTLY complicates the predicate.  In fact, the
>flag doubles the number of states I have to think about when mentally
>evaluating the predicate!  That's the real source of the loop
>termination errors.

>(I shouldn't have to remind anyone, but just in case: George Miller did
>a famous study about human cognitive limits, and found that people can
>remember about 7 things, plus or minus 2.  That's why complex predicates
>make a programmer's head spin, and why he often gets loop termination
>wrong.)

>Using an exit from the middle avoids the headaches (literally)
>engendered by using an extra flag in the predicate.  When you want to
>exit, you just say that you want to exit, directly.  No mental
>gymnastics are required in order to determine whether you'll "really"
>exit, as would be the case using the flag approach.

That's brilliant, now your code is much easier to write!
Now let's see who has an easier time *testing* their code.
I think you'll find the control-flow errors you introduce
in the spaghetti you produce will more than make up for
any gain you have from rapid coding.  

A.
 

Re: Software landmines (loops)

[Matthew Heaney]

ahussey@it.uq.edu.au (Andrew Hussey) writes:

> >Using an exit from the middle avoids the headaches (literally)
> >engendered by using an extra flag in the predicate.  When you want to
> >exit, you just say that you want to exit, directly.  No mental
> >gymnastics are required in order to determine whether you'll "really"
> >exit, as would be the case using the flag approach.
> 
> That's brilliant, now your code is much easier to write!
> Now let's see who has an easier time *testing* their code.
> I think you'll find the control-flow errors you introduce
> in the spaghetti you produce will more than make up for
> any gain you have from rapid coding.  

Here's is something I whipped up for another post recently.  It's an
equality operator for a bounded stack.  

The implementation of the function has multiple returns.

Does this implementation fit your definition of spaghetti code?

Would the implementation be better by not using multiple returns?


function "=" (L, R : Stack_Type) return Boolean is
begin

   if L.Top /= R.Top then
      return False;
   end if;

   for Index in Positive range 1 .. L.Top loop
      if L.Items (Index) /= R.Items (Index) then
         return False;
      end if;
   end loop;

   return True;

end "=";


My feeling is that trying to implement this operation using only a
single return would just make it more complicated.

Re: Software landmines (loops)

[Loryn Jenkins]

How is this more complicated? 

equal (l,r: LIST): BOOLEAN is
	require
		l.count = r.count
	do
		Result := l.first /= r.first
		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

Sorry for the language change ... it's the one I'm familiar with.

By the way, I'm not sure whether it's a problem in your Ada code, but my
Eiffel code could fail if r has greater or fewer items than l. Hence the
precondition.

Loryn Jenkins

Re: Software landmines (loops)

[Matthew Heaney]

Loryn Jenkins <loryn@s054.aone.net.au> writes:

> How is this more complicated? 
>
> equal (l,r: LIST): BOOLEAN is
> 	require
> 		l.count = r.count
> 	do
> 		Result := l.first /= r.first
> 		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

There are a few things I don't like about this:

1) You have to test a flag every iteration of the loop.  That adds (a
marginal amount of) inefficiency.

2) The loop predicate has 4 possible values.  The original example had
only 2.

3) There's more nesting.

So yes, I feel the above implementation is more complex than the
original implementation that used muliple returns.


> Sorry for the language change ... it's the one I'm familiar with.

AOK, I understood it OK.  (I also read the 1st ed of Bertrand's book.)
 
> By the way, I'm not sure whether it's a problem in your Ada code, but my
> Eiffel code could fail if r has greater or fewer items than l. Hence the
> precondition.

That's what the check L.Top /= R.Top means: if the number of items is
different, then you know immediately that the stacks can't be equal.
When you reach the loop, you know the stack depths are the same.


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.

Likewise for the example I provided.  Once you determine that the stacks
are unequal, you quit and go home.  You don't need go all the way to the
end of the subprogram to declare victory (unless of course the stacks
happen to really be equal).

Re: Software landmines (loops)

[dewarr]

In article <m3yas4q514.fsf@mheaney.ni.net>,
  Matthew Heaney <matthew_heaney@acm.org> wrote:
> Loryn Jenkins <loryn@s054.aone.net.au> writes:
>
> > How is this more complicated?
> >
> > equal (l,r: LIST): BOOLEAN is
> > 	require
> > 		l.count = r.count
> > 	do
> > 		Result := l.first /= r.first
> > 		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
>
> There are a few things I don't like about this:
>
> 1) You have to test a flag every iteration of the loop.  That adds (a
> marginal amount of) inefficiency.
>
> 2) The loop predicate has 4 possible values.  The original example had
> only 2.
>
> 3) There's more nesting.
>
> So yes, I feel the above implementation is more complex than the
> original implementation that used muliple returns.
>
> > Sorry for the language change ... it's the one I'm familiar with.
>
> AOK, I understood it OK.  (I also read the 1st ed of Bertrand's book.)
>
> > By the way, I'm not sure whether it's a problem in your Ada code, but my
> > Eiffel code could fail if r has greater or fewer items than l. Hence the
> > precondition.
>
> That's what the check L.Top /= R.Top means: if the number of items is
> different, then you know immediately that the stacks can't be equal.
> When you reach the loop, you know the stack depths are the same.
>
> 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.
>
> Likewise for the example I provided.  Once you determine that the stacks
> are unequal, you quit and go home.  You don't need go all the way to the
> end of the subprogram to declare victory (unless of course the stacks
> happen to really be equal).
>
>



Well it is not necessarily clear that this restatement is
less efficient. A compiler could manage to optimize the awkward
flag version back to the simple version with exits. Interestingly
few compilers do this optimization. A similar case is optimizing
an awkward case statement of a finite state machine back to the
simple and efficient version with gotos.

Given how common serious goto-allergy is, especially in the
US, and seeing how many people are willing to contort their
code to avoid gotos, these are optimizations that are probably
worthwhile including in modern compilers for this class of
languages.

Robert Dewar

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Optimizations (was: Software landmines (loops))

[dennison]

In article <6sgn8l$7aq$1@nnrp1.dejanews.com>,
  dewarr@my-dejanews.com wrote:

> few compilers do this optimization. A similar case is optimizing
> an awkward case statement of a finite state machine back to the
> simple and efficient version with gotos.
>
> Given how common serious goto-allergy is, especially in the
> US, and seeing how many people are willing to contort their
> code to avoid gotos, these are optimizations that are probably
> worthwhile including in modern compilers for this class of
> languages.

Being one of those goto-phobes as well a big fan of case statements, this
subject interests me. I assumed the relatively strict rules on case statement
predicates were specifically formulated so that they could be implemented as
jump-tables. Is that not the case? Is there anything that I can do to my case
statements to help the compiler out a bit?

--
T.E.D.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re: Expressive Case Statements (was: Software landmines)

[Richard D Riehle]

In article <6sh487$lnq$1@nnrp1.dejanews.com>,
	dennison@telepath.com wrote:

>Being one of those goto-phobes as well a big fan of case statements, this
>subject interests me. I assumed the relatively strict rules on case
statement
>predicates were specifically formulated so that they could be implemented
as
>jump-tables. Is that not the case? Is there anything that I can do to my
case
>statements to help the compiler out a bit?
 
 I realize this was supposed to be about optimizations. But this is the
 year of changing the subject what with tails wagging dogs, etc. Ted's
 mention of "case statements" reminds me of a problem with which I have
 been struggling for quite a while; one for which I finally cry, "Help!"

 There is a language called COBOL in which the ANSI 1995 standard 
 introduced a fascinating construct called the EVALUATE statement. It
 is the most powerful form of a case statement I have seen in any
 programming language. More powerful than Ada. More powerful than Eiffel.
 More powerful than C++ or Java. 

 One of the forms the EVALUATE statement (there are several options), 
 allows the programmer to directly represent a decision-table for a
 set of conditions with syntax such as,

        EVALUATE condition-1 ALSO condition-2 ALSO condition-3 
                             
           WHEN TRUE ALSO TRUE ALSO FALSE 
                          PERFORM 
                              some action-stub statements
                          END-PERFORM
           WHEN TRUE ALSO FALSE ALSO FALSE
                          PERFORM 
                              some action-stub statements
                          END-PERFORM
           WHEN FALSE ALSO FALSE ALSO TRUE
                          PERFORM 
                              some action-stub statements
                          END-PERFORM
        END-EVALUATE

In business data process software, such as banking and insurance, the
decision table is useful for representing complex sets of conditions
and their corresponding actions.  In military command and control
systems we also see these kinds of complex condition sets.

It is certainly easy to represent any set of conditions with a sequence
of if ... elsif statements but I am seeking something else.  What I have
been trying to accomplish is some generalized algorithm in Ada that 
allows me to design a package that approximates the power of the EVALUATE
statement in COBOL.  Some of the new features of Ada 95 such as generic
formal package parameters, access to subprogram, etc. have helped a
little, but ...

.... so far, I am not satisfied with the result of my own efforts. I am 
curious if anyone else has approached the problem of decision tables
in this way.  Is there a generalized solution in Ada with the expressive
power of the COBOL EVALUATE?  This would seem to be such a useful 
reusable component that I would be surprised if no one has done it yet.

Richard Riehle
richard@adaworks.com
http://www.adaworks.com
   

Re: Expressive Case Statements (was: Software landmines)

[Robert I. Eachus]

In article <6shit4$eaj@dfw-ixnews5.ix.netcom.com> Richard D Riehle <laoXhai@ix.netcom.com> writes:

 > It is certainly easy to represent any set of conditions with a sequence
 > of if ... elsif statements but I am seeking something else.  What I have
 > been trying to accomplish is some generalized algorithm in Ada that 
 > allows me to design a package that approximates the power of the EVALUATE
 > statement in COBOL.  Some of the new features of Ada 95 such as generic
 > formal package parameters, access to subprogram, etc. have helped a
 > little, but ...

     type Truth_Table_3 is (False_False_False, False_False_True,...
                                 True_True_True); 
     function To_TT3(Cond_1,Cond_2,Cond_3 : Boolean := False)
                                            return Truth_Table_3;

     case To_TT3(Condition_1, Condition_2, Condition_3) is
       when True_True_False  => some_action_stub_statements;
       when True_False_False => some_action_stub statements2;
       when False_False_True => some_action_stub statements3;
       when others => null;
     end case;

     Obviously you want the various truth table types in a package,
and you have several ways of writing the bodies of the conversion
functions.  I prefer:

     function To_TT3(Cond_1,Cond_2,Cond_3 : Boolean := False) 
                                        return Truth_Table_3 is
     begin
       return Truth_Table_3'Val(Cond_1'Pos * 4 + Cond_2'Pos * 2 + Cond_3);
     end To_TT3;

     I think I'd write a program to crank out the type declarations
though.
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Expressive Case Statements (was: Software landmines)

[Dr Richard A. O'Keefe]

Concerning decision tables, the EVALUATE statement in COBOL,
and Robert I. Eachus's suggestion for doing them in Ada,
I don't know what the COBOL standard says about EVALUATE,
but there was one point about decision tables which seems
to have been missed:

  - as well as the condition *combinations* being complex,
  - the condition *elements* may be complex, and
  - you don't want to evaluate them if you don't have to.

The kind of thing I'm getting at here is

   DO DECISIONTABLE (CHEAP_TEST, COSTLY_TEST)
   CASE (TRUE, -): FOO;
   CASE (-, TRUE): BAR;
   CASE (FALSE, FALSE): UGH;
   END;

(sorry about the syntax, I've never used EVALUATE in COBOL,
and while I _have_ used 'DO DECISIONTABLE' in a version of
Burroughs Algol -- Laurence Chiu, are you out there? --, it
has been a _long_ time)

That can be implemented as

  IF CHEAP_TEST THEN FOO ELSE
  IF COSTLY_TEST THEN BAR ELSE UGH;

Robert Eachus's suggestion _always_ evaluates _all_ the
condition elements even if some of them happen not to be
needed in a particular case.  (We're talking about the
difference between 'and' and 'and then' here.)

It fits into the general rule of 'helping the compiler to
help you by giving it a clue'.

There's a body of old literature about how to compile decision
tables, even including the 'extended' decision tables where you
list the condition elements and the action elements and can not
only select _which_ action elements are done when but also in
what order.

Decision tables became unfashionable; I never understood why.
A lot of this stuff surface in CS again in higher-level languages
like Clean, where

   case (cheap, costly) of
   (True, _) -> foo
   (_, True) -> bar
   _         -> ugh

would very probably be compiled just as I suggested above; it's a
_lazy_ functional language.

If I had a problem where decision tables paid off, I would write
a preprocessor to take decision table syntax and spit out Ada.
I would try to add some semantics to the decision table language
to check if the tables made sense...

I'd also investigate a Prolog-in-Ada package, like the one that
was originally part of ANNA.  Or calling CLIPS from Ada.

Re: Expressive Case Statements (was: Software landmines)

[Robert I. Eachus]

In article <35ECDA3F.3372@atlas.otago.ac.nz> "Dr Richard A. O'Keefe" <ok@atlas.otago.ac.nz> writes:

  > Concerning decision tables, the EVALUATE statement in COBOL,
  > and Robert I. Eachus's suggestion for doing them in Ada,
  > I don't know what the COBOL standard says about EVALUATE,
  > but there was one point about decision tables which seems
  > to have been missed:

  >   - as well as the condition *combinations* being complex,
  >   - the condition *elements* may be complex, and
  >   - you don't want to evaluate them if you don't have to...

  True, but from experience decision tables are not for situations
where evaluating all the decision variables is potentially harmful.
There are often cases where you nest decision tables because some
predicates should only be evaluated in some cases.  Too many don't
cares should also be taken as an indication that you have merged
tables that should be separate.
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Expressive Case Statements (was: Software landmines)

[Al Christians]

There is a commercial product that addresses this problem: Logic Gem.
I tried it about 10 years ago and found its user interface seriously
flawed, but besides that, it was ok.  It was a spreadsheet-like 
decision table builder that would generate code (Fortran, C, Pascal,
xBase, Cobol, Ada--NOT! ) and documentation.  It could compress a
decision table down to a simpler form when some inputs sometimes
didn't matter, and it could also expand a simplified table out to
a fully-expanded form.

Part of its input was data on the cost of evaluating the conditions
and the expected frequencies  of the various results.  It would use
this to generate code optimized accordingly.  I think that you could
alternatively generate code that was ordered to be more obviously in
agreement with the input data.

The principal problem, of course, is that code generation was one-way
and there was no way to be sure that the current table and the current
code were consistent other than regenerating the code.  I 
suppose that nowadays a two-way generate/reverse engineer tool would
be what most would want.  If the generated and optimized code comes
out too complex for a review or walk through, I don't know if anyone
should trust it or not. 

I just checked a search engine and see that Logic Gem is still 
available:  see www.logic-gem.com.

I speculate that one might implement a decision table in Ada as some 
some complex generic package.  Client code would add the conditions and 
actions into the generic decision table line-by-line.  The decision
table would then naturally want to check its own consistency and 
completeness before evaluating the conditions and performing the 
actions.  Would anybody be happy running code like that?   

Al


Robert I. Eachus wrote:
> 
> 
>   > Concerning decision tables, the EVALUATE statement in COBOL,
>   > and Robert I. Eachus's suggestion for doing them in Ada,
>   > I don't know what the COBOL standard says about EVALUATE,
>   > but there was one point about decision tables which seems
>   > to have been missed:
> 
>   >   - as well as the condition *combinations* being complex,
>   >   - the condition *elements* may be complex, and
>   >   - you don't want to evaluate them if you don't have to...
> 
>   True, but from experience decision tables are not for situations
> where evaluating all the decision variables is potentially harmful.
> There are often cases where you nest decision tables because some
> predicates should only be evaluated in some cases.  Too many don't
> cares should also be taken as an indication that you have merged
> tables that should be separate.
> --
>

Re: Expressive Case Statements (was: Software landmines)

[Matthew Heaney]

"Dr Richard A. O'Keefe" <ok@atlas.otago.ac.nz> writes:

> Decision tables became unfashionable; I never understood why.

Me neither.  It's a mental tool every programmer should have in his
toolbox.  

Re: Expressive Case Statements (was: Software landmines)

[Richard D Riehle]

In article <35ECDA3F.3372@atlas.otago.ac.nz>,
	"Dr Richard A. O'Keefe" <ok@atlas.otago.ac.nz> wrote:

[ snipped a little bit of preamble

>  - as well as the condition *combinations* being complex,
>  - the condition *elements* may be complex, and
>  - you don't want to evaluate them if you don't have to.

   Absolutely true statement.  The number of combinations is
   exponential.  When you get beyond three conditions the 
   problem can become unwieldy.  This is the beauty of decision
   tables.  Ridiculous choices can be identified immediately and
   discarded.  The COBOL Evaluate statement allows you discard those
   inappropriate choices in a readable and well-documented syntax.

>Decision tables became unfashionable; I never understood why.

  I'm with you.  I once used a language called LOBOC (COBOL spelled
  backwards) that was based on decision tables.  Unfortunately, one
  also had to embed Assembler (Autocoder for those of you ancient
  enough to remember it) in the code.  The decision tables greatly
  enhanced our ability to reason about complex relationships between
  choices and to rule out those that were nonsense.  They also forced
  us to ask questions about the possibility of a certain set of 
  situations ever occurring.  This helped with error management.

 [snipped some interesting code from Clean]

>If I had a problem where decision tables paid off, I would write
>a preprocessor to take decision table syntax and spit out Ada.
>I would try to add some semantics to the decision table language
>to check if the tables made sense...

 This is a possibility.  I am more interested to see how this could
 be best designed, for greatest expressibility, in an Ada package
 specification.  

>I'd also investigate a Prolog-in-Ada package, like the one that
>was originally part of ANNA.  Or calling CLIPS from Ada.

 ANNA keeps coming up in these discussions lately.  Hmmmmmmmm.


 Richard Riehle
 richard@adaworks.com
 http://www.adaworks.com
 

Re: Expressive Case Statements (was: Software landmines)

[Dale Stanbrough]

Richard D Riehle wrote:

">I'd also investigate a Prolog-in-Ada package, like the one that
 >was originally part of ANNA.  Or calling CLIPS from Ada.
 
  ANNA keeps coming up in these discussions lately.  Hmmmmmmmm."
 

If people want to use a cleaned up version of the Prolog-in-Ada
packages that originated from ANNA, i have them on my homepage at...


   http://goanna.cs.rmit.edu.au/~dale/software/index.html


Still not complete, but better than the originals.

Dale

Re: Expressive Case Statements (was: Software landmines)

[Al Christians]

This brings up a larger question that is perhaps beyond the scope of
c.l.a., but I would be interested in the thoughts of the experts here
on this subject:  What should go into data and what should go into
the program?  For example, it would generally be theoretically possible
to create a giant relational database where all the possible answers
from a program could be looked up based on all the possible inputs. 
We don't usually do that, but how does one correctly decide what is best
to code as program logic and what is best to code as data?  

A decision table is a way of presenting a representation of information
that is about midway between that that obviously ought to be programmed
and that that clearly ought to be left as data.  Any general rules to 
apply in this analysis?  How does programming language affect these
tradeoffs?

Al   


Richard D Riehle wrote:
> 
>    Absolutely true statement.  The number of combinations is
>    exponential.  When you get beyond three conditions the
>    problem can become unwieldy.  This is the beauty of decision
>    tables.  Ridiculous choices can be identified immediately and
>    discarded.  The COBOL Evaluate statement allows you discard those
>    inappropriate choices in a readable and well-documented syntax.
> 
> >Decision tables became unfashionable; I never understood why.
> 
>   I'm with you.  I once used a language called LOBOC (COBOL spelled
>   backwards) that was based on decision tables.  Unfortunately, one
>   also had to embed Assembler (Autocoder for those of you ancient
>   enough to remember it) in the code.  The decision tables greatly
>   enhanced our ability to reason about complex relationships between
>   choices and to rule out those that were nonsense.  They also forced
>   us to ask questions about the possibility of a certain set of
>   situations ever occurring.  This helped with error management.
>

Re: Expressive Case Statements (was: Software landmines)

[Tom Moran]

> What should go into data and what should go into the program?
Seems to me that's the classic tradeoff between space and speed, the
answer to which varies according to the economics of what's available.

Re: Expressive Case Statements (was: Software landmines)

[Richard D Riehle]

In article <EACHUS.98Sep1193718@spectre.mitre.org>,
	eachus@spectre.mitre.org (Robert I. Eachus) wrote:

  as a solution to the problem I posed about truth tables,

>     type Truth_Table_3 is (False_False_False, False_False_True,...
>                                 True_True_True); 
>     function To_TT3(Cond_1,Cond_2,Cond_3 : Boolean := False)
>                                            return Truth_Table_3;
>
>     case To_TT3(Condition_1, Condition_2, Condition_3) is
>       when True_True_False  => some_action_stub_statements;
>       when True_False_False => some_action_stub statements2;
>       when False_False_True => some_action_stub statements3;
>       when others => null;
>     end case;

  This comes close to what I am seeking.  Now I need to read it over
  and see it I can make it more general.  

  Thanks for your ideas, Robert.  

>     Obviously you want the various truth table types in a package,
>and you have several ways of writing the bodies of the conversion
>functions.  I prefer:
>
>     function To_TT3(Cond_1,Cond_2,Cond_3 : Boolean := False) 
>                                        return Truth_Table_3 is
>     begin
>       return Truth_Table_3'Val(Cond_1'Pos * 4 + Cond_2'Pos * 2 + Cond_3);
>     end To_TT3;
>
> I think I'd write a program to crank out the type declarations
> though.

  I need to code this as a compilable example and see if I can 
  generalize it.  As it is, it appears to satisfy the special 
  case of a three-valued table. 
 
  The example coded in a functional language looked very good, but
  that is not Ada.  

  Thanks again.

  Richard

Re: Expressive Case Statements (was: Software landmines)

[Robert I. Eachus]

In article <6si98q$fbo@sjx-ixn4.ix.netcom.com> Richard D Riehle <laoXhai@ix.netcom.com> writes:

  > I need to code this as a compilable example and see if I can 
  > generalize it.  As it is, it appears to satisfy the special 
  > case of a three-valued table. 

   Hmmm.  When I was thinking about your challenge, I did try a "more
generalized approach.  Basically you need a modular type, some
aliases, and to make sure your case expressions are static:

     type Truth_Table is mod 8;

     True1: constant Truth_Table := 128;
     True2: constant Truth_Table :=  64;
     True3: constant Truth_Table :=  32;
     True4: constant Truth_Table :=  16;
     True5: constant Truth_Table :=   8;
     True6: constant Truth_Table :=   4;
     True7: constant Truth_Table :=   2;
     True8: constant Truth_Table :=   1;
     False: constant Truth_Table :=   0;

     function TT (Cond_1, Cond_2, Cond_3, Cond_4, Cond_5, Cond_6,
                  Cond_7, Cond_8 : Boolean := False) return Truth_Table;
     ...

     case TT(Condition_1,Condition_2,Condition_3) is

       when False | True1 =>  Do_Something;
       when True1 + True2 =>  Do_Something_Else;
       ...
       when others => Do_Nothing;

     end case;


     If works, but I think that the notation becomes confusing.  In fact
it becomes VERY confusing if you use the boolean operators.  For
example,  "True1 and True2" evaluates to False, and "True1 or True3"
evaluates to the same value as TT(True, False, True).  Of course, you
could replace the modular type with an integer type to disallow such
bogusity.

     So I thought the approach I sketched yesterday was better.  You
would need a package with probably five types, covering two to six
booleans.  (You could go higher, but I've never done a 128 value
table, and I think I've only gone to six choices once.)  The
complexity is all in the package--the user just needs to know how many
choices he has.

    However, there is one additional thing I remembered on the way
home.  I have used this approach before, and ended up using an
enumeration type that was:

   type Truth_Table_3 is (NNN, NNY, NYN, NYY, YNN, YNY, YYN, YYY);
-- could have used T and F, but Y and N fit better.

   function All_False renames NNN;
   function True_3 renames NNY;
   ...
   function All_True renames YYY;

or:

   All_False: constant Truth_Table_3 := NNN;
   ...

whichever you prefer.

   Basically, you can have constant or renaming declarations which
allow you to name the cases in a way that makes sense locally.  With
bigger truth tables, that turns out to be a big help.  In fact
thinking about it, I almost always reify the states of a truth table
by using an enumeration type specific to that particular table.
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Expressive Case Statements (was: Software landmines)

[Tucker Taft]

Richard D Riehle (laoXhai@ix.netcom.com) wrote:

: ...
:         EVALUATE condition-1 ALSO condition-2 ALSO condition-3 
:                              
:            WHEN TRUE ALSO TRUE ALSO FALSE 
:                           PERFORM 
:                               some action-stub statements
:                           END-PERFORM
:            WHEN TRUE ALSO FALSE ALSO FALSE
:                           PERFORM 
:                               some action-stub statements
:                           END-PERFORM
:            WHEN FALSE ALSO FALSE ALSO TRUE
:                           PERFORM 
:                               some action-stub statements
:                           END-PERFORM
:         END-EVALUATE

: ...
: It is certainly easy to represent any set of conditions with a sequence
: of if ... elsif statements but I am seeking something else.  What I have
: been trying to accomplish is some generalized algorithm in Ada that 
: allows me to design a package that approximates the power of the EVALUATE
: statement in COBOL.  

What about:
    type Cond_Array is array(Positive range <>) of Boolean;
  ...
    declare
        Conds : constant Cond_Array := 
	  (condition-1, condition-2, condition-3);
    begin
        if Conds = (true, true, false) then
	    ...
        elsif Conds = (true, false, false) then
	    ...
	elsif Conds = (false, false, true) then
	    ...
	end if;
    end;

This certainly seems close enough, and captures the decision table
nature of the solution.  This doesn't use any "fancy" Ada 95 features.
In fact, it doesn't use any Ada 95 features at all!

If you require a case-statement solution, the following general pattern
would work:

    type Cond3 is (FFF, FFT, FTF, FTT, TFF, TFT, TTF, TTT);
    Cond3_Map : array(Boolean, Boolean, Boolean) of Cond3 is
      (((FFF, FFT), (FTF, FTT)), ((TFF, TFT), (TTF, TTT)));
  ...

    case Cond3_Map(condition-1, condition-2, condition-3) is
        when TTF =>
            ...
        when TFF =>
            ...
        when FFT =>
            ...
        when others => null;
    end case;

: ...
: Richard Riehle
: richard@adaworks.com
: http://www.adaworks.com

--
-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Expressive Case Statements (was: Software landmines)

[Richard D Riehle]

In article <EyMJzp.MB8.0.-s@inmet.camb.inmet.com>,
	stt@houdini.camb.inmet.com (Tucker Taft) wrote:

>Richard D Riehle (laoXhai@ix.netcom.com) wrote:
  [snipped away Richard's lengthy posting with the problem]

>What about:
>    type Cond_Array is array(Positive range <>) of Boolean;
>  ...
>    declare
>        Conds : constant Cond_Array := 
>	  (condition-1, condition-2, condition-3);
>    begin
>        if Conds = (true, true, false) then
>	    ...
>        elsif Conds = (true, false, false) then
>	    ...
>	elsif Conds = (false, false, true) then
>	    ...
>	end if;
>    end;
>
>This certainly seems close enough, and captures the decision table
>nature of the solution.  This doesn't use any "fancy" Ada 95 features.
>In fact, it doesn't use any Ada 95 features at all!

 Now the problem is formulating the actual conditions.  As you know,
 in the decision table there is the condition stub, in which we 
 formulate conditions such as A > B, Z = C, etc.  The rule stub where
 we specify the T, T, F, etc, the action stub where we specify the
 possible set of actions, and the Rule Actions where we can indicate
 which actions corrspond to which rules.  

 The solution you show is a good start.  I still need a more generalized
 model for the condition stub.  Perhaps this is simply a set of functions
 that return Boolean results mapped to the array of booleans.  This seems
 easier to state than to convert into a generalized model.  Then again,
 it may be that I am, 1) too close to the way it is solved in another
 language, 2) so obtuse that it its simplicity does not jump right out
 at me, or 3) both 1 and 2.

 I will look this over more closely and see if I can turn it into a
 generalized solution that corresponds to what I am seeking.  

 Thanks for your input, Tucker.  You do have a way of helping us set
 out on a more interesting path of discovery.

 Richard Riehle
 richard@adaworks.com
 http://www.adaworks.com

 

Re: Expressive Case Statements (was: Software landmines)

[Tom Moran]

Another question: Are all possibilities handled separately, or are
there "don't cares" that merge, eg
  when FF =>
  when FT =>
  when TF | TT =>
And one assumes, of course, that the code in each branch is relatively
small and not worth making 2**N children of an abstract tagged with  a
separate "procedure calculate" for each one.

Re: Expressive Case Statements (was: Software landmines)

[Tom Moran]

Are the conditions in such a decision table always boolean, or might
they be any enumerated type?
Do you care if the compiler checks that you have branches for all
possibilities (as in a case statement, but not in an elsif list)?

Re: Expressive Case Statements (was: Software landmines)

[Matthew Heaney]

tmoran@bix.com (Tom Moran) writes:

> Are the conditions in such a decision table always boolean, or might
> they be any enumerated type?

They can be any enumerated type.  For example, if color = (red, green,
blue), and boolean = (true, false), and that's 6 combinations:

color  R  R  G  G  B  B

bool   T  F  T  F  T  F

> Do you care if the compiler checks that you have branches for all
> possibilities (as in a case statement, but not in an elsif list)?

I find that it's better to consider all the _possible_ combinations,
then prune away the ones that don't make sense.  (See my other post for
a decision table analysis of a loop predicate.)

Re: Expressive Case Statements (was: Software landmines)

[Richard D Riehle]

In article <35ecc519.37879718@SantaClara01.news.InterNex.Net>,
	tmoran@bix.com (Tom Moran) wrote:

>Are the conditions in such a decision table always boolean, or might
>they be any enumerated type?
>Do you care if the compiler checks that you have branches for all
>possibilities (as in a case statement, but not in an elsif list)?

  Tom,

  Good question.  The model I am considering is,

       condition       condition entry 
        stub                stub
         ------------------------------------------
         c1  | T   T   T   T   F   F   F   F        
         ----|--------------------------------------         
         c2  | T   T   F   F   F   F   T   T
         ----|--------------------------------------         
         c3  | T   F   T   F   F   T   T   F
         ----|-------------------------------------         
         ==========================================
         A1  | X   X   X                   X               
         ----|--------------------------------------    
         A2  |     X   X 
         ----|--------------------------------------    
         A3  | X       X            X
         ----|--------------------------------------    
      Action               Action Entry
        Stub                   Stub

  With COBOL this can be expressed with a statment that maps directly
  to the picture.  This turns out to be wonderfully convenient when
  trying to determine how to convey the needs of a user to those of
  a programmer and vice versa.   I certainly know how to code this in
  a variety of brute-force methods.  I am trying to determine if there
  is some way I can generalize this as a class or as an Ada package
  that gives the programmer the same simplicity of expression I can
  achieve with the COBOL EVALUATE statement. 

  Richard Riehle
  richard@adaworks.com
  http://www.adaworks.com        

Re: Expressive Case Statements (was: Software landmines)

[Tom Moran]

>  condition       condition entry 
>        stub                stub
>         ------------------------------------------
>         c1  | T   T   T   T   F   F   F   F        
>         ----|--------------------------------------         
>         c2  | T   T   F   F   F   F   T   T
>         ----|--------------------------------------         
>         c3  | T   F   T   F   F   T   T   F
>         ----|-------------------------------------         
>         ==========================================
>         A1  | X   X   X                   X               
>         ----|--------------------------------------    
>         A2  |     X   X 
>         ----|--------------------------------------    
>         A3  | X       X            X
>         ----|--------------------------------------    
>      Action               Action Entry
>        Stub                   Stub
  Does this mean that in case T-T-T you want to perform *both* actions
A1 and A3, and that case T-F-F (et al) can never occur (ie, raises
Program_Error or something)?  Or am I misunderstanding this notation?

Re: Expressive Case Statements (was: Software landmines)

[Richard D Riehle]

In article <35eda0d0.15935137@SantaClara01.news.InterNex.Net>,
	tmoran@bix.com (Tom Moran) wrote:

>>  condition       condition entry 
>>        stub                stub
>>         ------------------------------------------
>>         c1  | T   T   T   T   F   F   F   F        
>>         ----|--------------------------------------         
>>         c2  | T   T   F   F   F   F   T   T
>>         ----|--------------------------------------         
>>         c3  | T   F   T   F   F   T   T   F
>>         ----|-------------------------------------         
>>         ==========================================
>>         A1  | X   X   X                   X               
>>         ----|--------------------------------------    
>>         A2  |     X   X 
>>         ----|--------------------------------------    
>>         A3  | X       X            X
>>         ----|--------------------------------------    
>>      Action               Action Entry
>>        Stub                   Stub
>  Does this mean that in case T-T-T you want to perform *both* actions
>A1 and A3, and that case T-F-F (et al) can never occur (ie, raises
>Program_Error or something)?  Or am I misunderstanding this notation?

    The decision entries are read vertically as you note.  In those
    situtations where there are no action entries, no action is 
    required.  With the COBOL Evaluate statment one would only code 
    "when" statements for those actions that had entries.  It is, 
    of course, legal to have an "others" condition which accomodates 
    those decision entries for which there are no valid actions.

    Richard Riehle
    richard@adaworks.com
    http://www.adaworks.com

Re: Expressive Case Statements (was: Software landmines)

[Fergus Henderson]

eachus@spectre.mitre.org (Robert I. Eachus) writes:

>"Dr Richard A. O'Keefe" <ok@atlas.otago.ac.nz> writes:
>
>  > Concerning decision tables, the EVALUATE statement in COBOL,
>  > and Robert I. Eachus's suggestion for doing them in Ada,
>  > I don't know what the COBOL standard says about EVALUATE,
>  > but there was one point about decision tables which seems
>  > to have been missed:
>
>  >   - as well as the condition *combinations* being complex,
>  >   - the condition *elements* may be complex, and
>  >   - you don't want to evaluate them if you don't have to...
>
>  True, but from experience decision tables are not for situations
>where evaluating all the decision variables is potentially harmful.

Why is it potentially harmful?  Do you mean because of the efficiency
problem in such cases, or is there some other reason?

I think Richard O'Keefe was pointing out an advantage of languages
which support lazy evaluation.  So unless there is some justification
other than the efficiency problem, your statement above should be
"from experience in languages which do not support lazy evaluation, ...",
since in languages which *do* support lazy evaluation, decision tables
can work fine as far as efficiency is concerned even in situations in
which evaluating all the decision variables is potentially harmful. 
Richard's Clean program was an example of this.

>There are often cases where you nest decision tables because some
>predicates should only be evaluated in some cases.  Too many don't
>cares should also be taken as an indication that you have merged
>tables that should be separate.

Do you mean that to apply in general, or only to languages such as Ada
which don't support lazy evaluation?

If you mean it to apply in general, what's the justification?

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.

Re: Expressive Case Statements (was: Software landmines)

[Michael F Brenner]

   > how does one correctly decide what is best to code as program logic 
   > and what is best to code as data?

The decision whether to code a particular portion of an algorithm
as code or data within the software can be made using the same four
criteria (i.e. metrics) used to determine whether to code an algorithm 
as software at all (versus reading in data at runtime).

First, there is the total cost of maintenance. This is almost
always made cheaper by using data rather than code, but analysis
may occasionally find code easier to maintain, particularly if
the data is nested more than the code would be.

Second is distributed size of the system. The more parts the system 
has, the more expensive code becomes than data. For example,
consider the Upper Slobbovian Command and Control System which
tracks all civilian and military flights of airplanes, satellites,
friendly missiles (those aimed away from you), and unfriendlies.
Here a large expense is the fact that some things are classified. It is
much cheaper to read in the classified data at runtime and keep the
software unclassified.

Third is to minimize the coupling. Coupling is the weighted sum
of the globality of the references. Global references get a high
weight; intermediate references get a low weight; purely local
references get a low weight.

Fourth is the controversial cohesion metric. While it does not
compete with lifecycle maintenance cost, distributed size of system,
or non-localization of reference, your selected cohesion metric 
will be your judgement of the localization of function, the relationship
between inputs and outputs, the ease of computing the precondition
from the postcondition, and the single-mindedness of the purpose. There
is a method of measuring this objectively by interpreting the 
software as a braid in a particular braid group and using the
cohesion of the braid as the measure of the cohesion of the
software.

Mike Brenner  mikeb@mitre.org