algorithm, two implementations that act the same, same type etc

algorithm, two implementations that act the same, same type etc

[Mehdi Saada]

Hi,
I have an issue with an algorithm - self-imposed "homework" I guess, the first one is mine, the wrong, the second is the "right" one, that works.
I can't figure out why they would logically be any different.
basically instead of using a stack on access values, I stack the values themselves. the rest is the same.
except this function ALL the rest of the project is the same. they are in related package so from the first I call the second to ensure the result is right, and it shows its not.

could someone throw an eye and tell if it seems identical or that something gross escaped my sight ?


45+78*56-(5-(8+5)-7);
gives (really) :  4428 and mine gives  4413

11-0/5+88/5;
it should be: 28 and mine gives 11

my function:
   function  Calcul ( V : in T_Vect_Token) return Integer is
      package ppile is new P_Pile_4(T_Elem   => Integer,
                                    Max_Pile => 80);
      use ppile;
      Pile_operandes : ppile.T_Pile(40);
      op1_calcul, op2_calcul: Integer;
   begin
      for I in V'Range loop
         if V(I).all'Tag = T_Token_Operande'Tag then
            ppile.Empiler(Pile_operandes,T_Token_Operande(v(I).all).Get_Elem);
         elsif V(I).all'Tag = T_Token_Operateur'Tag then
            Depiler(Pile_operandes,op2_calcul);
            Depiler(Pile_operandes,op1_calcul);
            case T_Token_Operateur(v(I).all).L_Operateur is
               when '*' => Empiler(Pile_operandes,op1_calcul * op2_calcul);
               when '-' => Empiler(Pile_operandes,op1_calcul - op2_calcul);
               when '+' => Empiler(Pile_operandes,op1_calcul + op2_calcul);
               when '/' => Empiler(Pile_operandes,op1_calcul / op2_calcul);
            end case;
         else raise P_Expression.Exc_Erreur;
         end if;
      end loop;
      Depiler(Une_Pile => Pile_operandes,
              Elem     => op2_calcul);
      if ppile.Pile_Vide(Pile_operandes) then Put_Line("BIEN !"); end if;
      Put_Line("vrai calcul : " & P_Expression.Calcul(V)'Image);
      Put_Line("faux calcul: "); return op1_calcul;
   exception
      when E: others => Put_Line(Exception_Information(E)); return 0;
   end Calcul;


the good function:
   function  Calcul ( V : in T_Vect_Token) return Integer is
      Pile   : P_Pile_Token.T_Pile(80); 
      Res    : Integer;
      Token1,
      Token2    : T_Ptr_Token ;
      Ptr_Token : T_Ptr_Token ;
   begin
      for I in V'range loop
         Ptr_Token := V(I);
         if Ptr_Token.all'Tag = T_Token_Operande'Tag
            then
            Empiler(Pile,Ptr_Token);
         elsif
            Ptr_Token.all'Tag = T_Token_Operateur'Tag
            then
            Depiler(Pile,Token2);
            Depiler(Pile,Token1);
            case Get_Elem(T_Token_Operateur(Ptr_Token.all)) is
               when'+' => Res := Get_Elem (T_Token_Operande(Token1.all)) +
                  Get_Elem (T_Token_Operande(Token2.all));
               when'-' => Res := Get_Elem (T_Token_Operande(Token1.all))-
                  Get_Elem (T_Token_Operande(Token2.all));
               when'*' => Res := Get_Elem (T_Token_Operande(Token1.all)) *
                  Get_Elem (T_Token_Operande(Token2.all));
               when'/' => Res := Get_Elem (T_Token_Operande(Token1.all)) /
                  Get_Elem (T_Token_Operande(Token2.all));
            end case;
            Empiler(Pile,Set_Ptr(Res));
         else
            Ada.Text_Io.Put_Line("TOKEN intru ");
            raise Exc_Erreur;
         end if;
      end loop;
      Depiler(Pile,Ptr_Token);
      if Pile_Vide(Pile)
         then
         return Get_Elem(T_Token_Operande(Ptr_Token.all));
      else
         Ada.Text_Io.Put_Line("Pile non vide ");
         raise Exc_Erreur;
      end if;
   exception
      when others => Ada.Text_Io.Put_Line ("Erreur CALCUL");
         raise Exc_Erreur;
   end Calcul;

Re: algorithm, two implementations that act the same, same type etc

[AdaMagica]

You've got a nerve...
Unreadable code fragment, uncompilable, terrible formatting, ...

Re: algorithm, two implementations that act the same, same type etc

[Niklas Holsti]

On 2021-02-14 21:35, Mehdi Saada wrote:
> Hi,
> I have an issue with an algorithm - self-imposed "homework" I guess,
> the first one is mine, the wrong, the second is the "right" one, that
> works.
>
> I can't figure out why they would logically be any different.
>
> basically instead of using a stack on access values, I stack the
> values themselves. the rest is the same.
>
> except this function ALL the rest of the project is the same. they
> are in related package so from the first I call the second to ensure
> the result is right, and it shows its not.
> 
> could someone throw an eye and tell if it seems identical or that
> something gross escaped my sight ?

First you should have told us what the function is supposed to do. I 
would also advise you to write that descriptions as comments in the 
code, BEFORE you start coding, so that (a) you know, while you are 
writing the code, what the code is meant to do; and (b) someone reading 
the code later has a chance of understanding the intent.

Looking first at what you call the "good" code, it seems to be given a 
reverse-Polish (post-fix) integer expression, as a vector of objects, 
each of which can be either an operand (an integer) or an operator (+, 
-, *, /), and the purpose of the function is to evaluate the expression 
and return the resulting integer value.

The evaluation function uses a stack of operands and results, in the 
normal way:

    traverse the post-fix expression items from first to last
       if the item is an operand, push its value
       if the item is an operation, pop the top two stack
          elements, apply the operation, and push the result.
    pop and return the (only) stack element.


> my function:
    ...
>        Depiler(Une_Pile => Pile_operandes,
>                Elem     => op2_calcul);
    ...>        return op1_calcul;


Have a good look at those two statements. You will see a discrepancy.

Re: algorithm, two implementations that act the same, same type etc

[Mehdi Saada]

I would not post code if I wasn't thinking I know of its purpose.
I just couldn't spot the one letter wrong I'm sure you must remember how as a student lines tended to "blurr"...
"idiot ! Look closely at the f%@# Depiler parts" or "reformat your damn message" or "look better at the details of polish inverse notation" would have sufficed. Being spiteful is a choice...
Thanks anyway.

Re: algorithm, two implementations that act the same, same type etc

[Niklas Holsti]

On 2021-02-15 18:34, Mehdi Saada wrote:
> 
> I would not post code if I wasn't thinking I know of its purpose.


You may know, but we (the newsgroup) don't, and you asked us to read 
your code and try to find your error. The error turned out to be a typo, 
but it could have been a mismatch between what you wanted the code to 
do, and how the code was designed. That is why I asked you to explain 
the purpose. Also, some of the identifiers you used are French-derived, 
and some of us may not French and find the identifiers obscure.

(Perhaps you can take my request as a compliment to you: that I did not 
expect that you would make such a simple typo mistake, or would have 
found such a mistake on your own.)

I find that writing a description, in prose comments, of a subprogram, 
before I start coding the subprogram, forces me to think about it, and 
reduces the chance of design errors in the algorithm. This is especially 
true if there are corner cases like empty inputs, empty results, or 
input checks that can fail.


> I just couldn't spot the one letter wrong I'm sure you must remember
> how as a student lines tended to "blurr"...

Sure.

Among the (language-independent) lessons I have learned from making many 
mistakes of similar triviality are these:

1. Always document (with comments) the purpose (role) of every variable, 
constant, parameter, etc. This is so that (a) you think about it, and 
remember it, and (b) anyone reading the code later will understand the 
intent.

2. Never use a variable for more than one purpose.

In this example, your basic error was trying to reuse the op<x>_calcul 
variables for a different purpose. These variables were designed to hold 
the two operands for an operation, and were so named, but you tried to 
reuse one of them for a different purpose: extracting and passing the 
final result. You should have declared a new variable, result: Integer, 
for that different purpose.

Moreover, I suspect that a part of the error may have been a copy-paste 
of a "Depiler" call without paying attention to editing the pasted copy.

So, more rules I have learned:

3. Treat every copy-paste of code with extreme suspicion. Avoid being 
interrupted by anything before you have finished adjusting the pasted 
copy to its new role. One method is to start by making the pasted copy 
syntactically incorrect, for example by inserting !! before it, and only 
removing the !! after you are sure that the pasted text is now adapted 
for its new use.

In one project for some on-board SW for a satellite instrument that I 
worked on a few decades ago, we found that a large portion -- I believe 
something over one-half -- of the bugs found in unit test were caused by 
such omitted or incomplete editing of copy-pasted code.

The problem is that unedited copy-pasted code often compiles without 
error, and may look nice and ready, but does not work correctly in its 
new context and role.

4. The "blurring" problem is reduced by adding a blank line between 
statements (but not within a statement).

Finally, note that your design change -- to stack the values instead of 
the references to the original reverse-Polish objects -- was valid and 
worked, good for you.

I wish you better luck with your next program.

Re: algorithm, two implementations that act the same, same type etc

[Mehdi Saada]

Thanks.
The tension subsided a little. I got weirdly emotional, sorry.
Your stories and teachings are enlightening, now I understand why some code would have more comments than actual code.
Makes sense if I consider that the language grammar itself appears as mostly useless commentary for C people.
I'll refactor stuff and you'll tell if that complies with your standard.

Re: algorithm, two implementations that act the same, same type etc

[Mehdi Saada]

>> I'll refactor stuff and you'll tell if that complies with your standard. 
I hope that's better.
------------------
body part of "p_expression_a.a_moi")
   function Computation (V: in T_Vect_Token) return integer is separate;
   function Calcul(V: in T_Vect_Token) return Integer renames Computation;
----------------------
separate (P_Expression.A_Moi)
function Computation ( V : in T_Vect_Token) return Integer is
   
   package P_stack is new P_Pile_4(T_Elem   => Integer,
                                   Max_Pile => 80);

   -- call on stack package
   
   subtype T_stack is P_stack.T_Pile;
   subtype T_Token_Operand is T_Token_Operande;
   subtype T_Token_Operator is T_Token_Operateur;
   procedure Stack_Uppon (A_Stack : in out T_stack; Elem: Integer)
                          renames P_stack.Empiler;
   procedure Pop (A_Stack: in out T_STACK; Elem: out Integer)
                  renames P_stack.Depiler;
   function Is_Stack_Empty (A_Stack: T_stack) return Boolean
                            renames P_stack.Pile_Vide;
   Exception_Wrong_Token : exception renames P_Expression.Exc_Erreur;
   
   -- renamings for conveniance, avoids usage of "use"
   
   Stack_for_Operands : T_stack(40);
   Operand_1, Operand_2: Integer;
   
begin
   
   -- Loop runs through the token vector, if it's an operand it's stacked,
   -- if it's an operator the last two operands stacked are recovered and the computation made,
   -- but in the inverse order of the recovered operands, or "/" and "-" would misbehave.
   
   for I in V'Range loop
      
      -- Tag comparisons to choose decision
     
      if V(I).all'Tag = T_Token_Operand'Tag then

         Stack_Uppon(Stack_for_operands,T_Token_Operand(v(I).all).Get_Elem);

      -- Get the value  to stack       

      elsif V(I).all'Tag = T_Token_Operateur'Tag then
         
         Pop(Stack_for_operands,Operand_2);
         Pop(Stack_for_operands,Operand_1);
         
         -- decision over which operator to apply.
         
         case T_Token_Operateur(v(I).all).L_Operateur is
            when '*' => Stack_Uppon(Stack_for_operands,Operand_1 * Operand_2);
            when '-' => Stack_Uppon(Stack_for_operands,Operand_1 - Operand_2);
            when '+' => Stack_Uppon(Stack_for_operands,Operand_1 + Operand_2);
            when '/' => Stack_Uppon(Stack_for_operands,Operand_1 / Operand_2);
         end case;
         
      else raise P_Expression.Exc_Erreur
         with "wrong token inserted please review previous steps";
         
         -- if any wrong token (parentheses, terminator) has still crept in
         -- from the previous steps. Or if the vector is invalid and it has not been seen,
      
      end if;
   end loop;
     
   declare
      Result: INTEGER renames Operand_1;  
      -- clarity rules !
   begin
      Pop(A_Stack => Stack_for_Operands,
          Elem     => Result);
      pragma Assert (Is_Stack_Empty(Stack_for_operands)
                     and (P_Expression.Calcul(V) = Result));
      return Result;
   end;
exception
   when P_stack.Exc_Pile_Vide => Put_Line("Invalidity not recognized by previous subroutine");
return 0;
   when E: others => Put_Line(Exception_Information(E)); return 0;
end Computation;

Re: algorithm, two implementations that act the same, same type etc

[Niklas Holsti]

On 2021-02-17 14:14, Mehdi Saada wrote:
>>> I'll refactor stuff and you'll tell if that complies with your standard.


We won't know who's standard you mean if you don't quote something from 
the person or name the person.

I'll assume it's me, so I'll review your code from my point of view. I 
won't put in softening polite words everywhere, but don't be offended by 
my criticism, please  :-)


> I hope that's better.
> ------------------
> body part of "p_expression_a.a_moi")
>     function Computation (V: in T_Vect_Token) return integer is separate;
>     function Calcul(V: in T_Vect_Token) return Integer renames Computation;


The first thing a reader would ask themselves is "why that renaming"? 
That would be worth a comment.

My practice is to describe the role and meaning of a subprogram in 
connection with that subprogram's declaration, which you haven't done 
here. Even a one-liner like "The result of evaluating the post-fix 
expression V" would be illuminating.


> ----------------------
> separate (P_Expression.A_Moi)
> function Computation ( V : in T_Vect_Token) return Integer is
>     
>     package P_stack is new P_Pile_4(T_Elem   => Integer,
>                                     Max_Pile => 80);
> 
>     -- call on stack package


I don't see what the comment above brings to the table. I can see from 
the code that something related to a stack package is being done; I 
don't need a comment to tell me that. The comment should tell me 
something that I cannot see directly from the Ada code. Perhaps that the 
stack in question will hold operand and result values (which "T_Elem => 
Integer" does not tell me, because Integer is such a general type).

I also make a rule that comments should be written in normal prose 
style, as full and grammatical sentences, with an initial capital letter 
and a final period in each sentence.


>     subtype T_stack is P_stack.T_Pile;
>     subtype T_Token_Operand is T_Token_Operande;
>     subtype T_Token_Operator is T_Token_Operateur;
>     procedure Stack_Uppon (A_Stack : in out T_stack; Elem: Integer)
>                            renames P_stack.Empiler;
>     procedure Pop (A_Stack: in out T_STACK; Elem: out Integer)
>                    renames P_stack.Depiler;
>     function Is_Stack_Empty (A_Stack: T_stack) return Boolean
>                              renames P_stack.Pile_Vide;
>     Exception_Wrong_Token : exception renames P_Expression.Exc_Erreur;


If those renames are only to translate French to English, you took my 
comment about French too seriously. There's nothing bad with using other 
languages for identifiers and comments -- I sometimes use Finnish -- but 
if you then post the code in an English-language forum like 
comp.lang.ada, you can expect some incomprehension if you don't explain 
the names in your message, for example saying "Empiler" = "push" and 
"Depiler" = "pop".

If you prefer French discussions, you can post on fr.comp.lang.ada.

<anecdote>

I once took part in an ESA project by a French company that was building 
an ESA satellite based on an earlier French national (CNES) satellite. 
All code and documentation for the earlier satellite was in French, but 
the ESA satellite required English documentation, and also some changes 
to the SW. So, for a while the French "method" for marking changes in 
the SW requirements specification document was that all old text was in 
French, all changes and new text in English -- even when changing only 
part of a sentence.

And of course all acronyms came in two forms, like OTAN (French) = NATO 
(English). This method somewhat limited the staff we could assign to the 
project.

</anecdote>


>     -- renamings for conveniance, avoids usage of "use"


The renames added 10 lines to the code, with possible errors in them, 
replacing one line for "use", or a few cases of qualification by package 
name. Not a win, IMO.

You could also have avoided "use" by saying "type T_Stack is new 
P_Stack.T_Pile" (which would inherit all operations of T_Pile) instead 
of using a subtype. Or you could say "use type T_Stack" or "use type 
P_Stack.T_Pile" with the same effect.

My personal rule for "use" is to limit it to scopes that are so small 
(few lines) that the "use" is always visible on the screen when I am 
working on the code affected by it. And even so only when it really 
makes the code significantly easier to read.

Note that avoiding "use <package>" is made much easier by hierarchical 
packages: code in package Foo.Bar.Joe sees everything declared in 
packages Foo and Foo.Bar without having to qualify them or saying "use 
Foo" or "use Foo.Bar".


>     
>     Stack_for_Operands : T_stack(40);
>     Operand_1, Operand_2: Integer;


Your identifiers are clear enough to almost avoid the need for comments 
per object. But the penalty for that is that the identifiers are long, 
especially the first one. I would probably have written:

    Stack : T_Stack (40);
    -- Holds operands and computation results.

(By the way, what is the "40" for here? To set the maximum stack size? 
But isn't that given by "Max_Pile => 80" in the generic instantiation?)


> begin
>     
>     -- Loop runs through the token vector, if it's an operand it's stacked,
>     -- if it's an operator the last two operands stacked are recovered and the computation made,
>     -- but in the inverse order of the recovered operands, or "/" and "-" would misbehave.
>     
>     for I in V'Range loop
>        
>        -- Tag comparisons to choose decision


Some people write comments before the subject code, some people write 
comments after the subject code. I do both, but for different purposes, 
and I write the comment differently to separate the two cases.

When I want to write a comment that applies to a long piece of code, for 
example several statements or declarations (as in the earlier renamings) 
I put the comment before the code, surround it with blank lines, and end 
it with a colon. I would replace the above comment with:

     -- See if V(I) is an operand or an operator:

The comment does not have to say "Tag comparisons"; I can directly see 
from the code that it is comparing tags. The phrase "to choose decision" 
is redundant; any comparison is done to choose or decide something. The 
important thing is what is _specific_ to these comparisons and 
decisions, which here is to separate operands from operators.

The common example of a useless comment is:

    I := I + 1;
    -- Add one to I.

Don't emulate it.

When I want to write a comment that applies to a short piece of code, 
such as a single declaration or statement, I put the comment after the 
code and ensure that there are no blank lines between the code and the 
comment. I usually add a null comment between the code and the comment, 
to avoid the "blurring" effect:

    Result : Integer;
    --
    -- The result of the computation.


>        if V(I).all'Tag = T_Token_Operand'Tag then


My practice is to write a comment after every "then" and "else" to 
explain the situation. Here I would have written:

     if V(I).all'Tag = T_Token_Operand'Tag then
        -- This is an operand, so we push its value on the stack:


>           Stack_Uppon(Stack_for_operands,T_Token_Operand(v(I).all).Get_Elem);


The usual English name for pushing something on a stack is "Push", just 
a note.


>        -- Get the value  to stack


If that comment applies to the "Stack_Uppon" statement, it should be 
indented as much as that statement. And I would add a null comment 
between the statement and the comment to show that the comment applies 
to the preceding statement.


>        elsif V(I).all'Tag = T_Token_Operateur'Tag then


And here I would write, after the "then":

    -- This is an operator, so we apply it to the two top operands
    -- from the stack, and replace the operands with the result:


>           Pop(Stack_for_operands,Operand_2);
>           Pop(Stack_for_operands,Operand_1);
>           
>           -- decision over which operator to apply.
>           
>           case T_Token_Operateur(v(I).all).L_Operateur is
>              when '*' => Stack_Uppon(Stack_for_operands,Operand_1 * Operand_2);
>              when '-' => Stack_Uppon(Stack_for_operands,Operand_1 - Operand_2);
>              when '+' => Stack_Uppon(Stack_for_operands,Operand_1 + Operand_2);
>              when '/' => Stack_Uppon(Stack_for_operands,Operand_1 / Operand_2);
>           end case;
>           
>        else raise P_Expression.Exc_Erreur
>           with "wrong token inserted please review previous steps";
>           
>           -- if any wrong token (parentheses, terminator) has still crept in
>           -- from the previous steps. Or if the vector is invalid and it has not been seen,


A further rule: "else" should almost always be followed by a line break 
and a comment to explain the case. So here I would write:

    else
       -- This is neither an operand nor an operator, which means
       -- that the input V is in error.

       raise ...

>        
>        end if;
>     end loop;
>       
>     declare
>        Result: INTEGER renames Operand_1;


Why use a renaming here? It buys you nothing; it probably won't even 
save a few bits of memory. All it does is change the value of Operand_1 
in a sneaky manner.


>        -- clarity rules !


That comment is almost masterfully unclear, similar to "this statement 
is a lie".

I give you credit for localizing the declaration to a declare block. 
However, why were you not consistent and localized Operand_1 and 
Operand_2 also?

Anyway, for a short subprogram like this, I think using declare blocks 
is superfluous because the declarations are close to the code anyway.


>     begin
>        Pop(A_Stack => Stack_for_Operands,
>            Elem     => Result);
>        pragma Assert (Is_Stack_Empty(Stack_for_operands)
>                       and (P_Expression.Calcul(V) = Result));


If you use a complex Boolean expression in an assertion, and the 
assertion fails, you won't know which part of the Boolean expression was 
False. Better to separate into two assertions, one for the stack being 
empty, and one for checking the result.


>        return Result;
>     end;
> exception
>     when P_stack.Exc_Pile_Vide => Put_Line("Invalidity not recognized by previous subroutine");
> return 0;
>     when E: others => Put_Line(Exception_Information(E)); return 0;
> end Computation;


For exception handlers I usually follow the same rule as for "then" and 
"else": ensure a line break after "=>" and follow it with a comment that 
explains why this exception might happen (if it isn't evident). For example:

    when P_Stack.Exc_Pile_Vide =>
       -- The expression V is ill-formed; it tries to apply an operation
       -- to a stack that is empty or contains only one operand, or the
       -- entire expression is null and produces nothing.

In conclusion, if this were a real code review in a project, I would say 
"please correct accordingly and submit for re-review".

No hurt feelings, I hope.

Re: algorithm, two implementations that act the same, same type etc

[Mehdi Saada]

I loved it, thank you Niklas.