* algorithm, two implementations that act the same, same type etc @ 2021-02-14 19:35 Mehdi Saada 2021-02-15 11:07 ` AdaMagica 2021-02-15 13:02 ` Niklas Holsti 0 siblings, 2 replies; 9+ messages in thread From: Mehdi Saada @ 2021-02-14 19:35 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-14 19:35 algorithm, two implementations that act the same, same type etc Mehdi Saada @ 2021-02-15 11:07 ` AdaMagica 2021-02-15 13:02 ` Niklas Holsti 1 sibling, 0 replies; 9+ messages in thread From: AdaMagica @ 2021-02-15 11:07 UTC (permalink / raw) You've got a nerve... Unreadable code fragment, uncompilable, terrible formatting, ... ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-14 19:35 algorithm, two implementations that act the same, same type etc Mehdi Saada 2021-02-15 11:07 ` AdaMagica @ 2021-02-15 13:02 ` Niklas Holsti 2021-02-15 16:34 ` Mehdi Saada 1 sibling, 1 reply; 9+ messages in thread From: Niklas Holsti @ 2021-02-15 13:02 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-15 13:02 ` Niklas Holsti @ 2021-02-15 16:34 ` Mehdi Saada 2021-02-15 19:15 ` Niklas Holsti 0 siblings, 1 reply; 9+ messages in thread From: Mehdi Saada @ 2021-02-15 16:34 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-15 16:34 ` Mehdi Saada @ 2021-02-15 19:15 ` Niklas Holsti 2021-02-17 10:50 ` Mehdi Saada 0 siblings, 1 reply; 9+ messages in thread From: Niklas Holsti @ 2021-02-15 19:15 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-15 19:15 ` Niklas Holsti @ 2021-02-17 10:50 ` Mehdi Saada 2021-02-17 12:14 ` Mehdi Saada 0 siblings, 1 reply; 9+ messages in thread From: Mehdi Saada @ 2021-02-17 10:50 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-17 10:50 ` Mehdi Saada @ 2021-02-17 12:14 ` Mehdi Saada 2021-02-17 17:10 ` Niklas Holsti 0 siblings, 1 reply; 9+ messages in thread From: Mehdi Saada @ 2021-02-17 12:14 UTC (permalink / raw) >> 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; ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-17 12:14 ` Mehdi Saada @ 2021-02-17 17:10 ` Niklas Holsti 2021-02-17 21:13 ` Mehdi Saada 0 siblings, 1 reply; 9+ messages in thread From: Niklas Holsti @ 2021-02-17 17:10 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: algorithm, two implementations that act the same, same type etc 2021-02-17 17:10 ` Niklas Holsti @ 2021-02-17 21:13 ` Mehdi Saada 0 siblings, 0 replies; 9+ messages in thread From: Mehdi Saada @ 2021-02-17 21:13 UTC (permalink / raw) I loved it, thank you Niklas. ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2021-02-17 21:13 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-02-14 19:35 algorithm, two implementations that act the same, same type etc Mehdi Saada 2021-02-15 11:07 ` AdaMagica 2021-02-15 13:02 ` Niklas Holsti 2021-02-15 16:34 ` Mehdi Saada 2021-02-15 19:15 ` Niklas Holsti 2021-02-17 10:50 ` Mehdi Saada 2021-02-17 12:14 ` Mehdi Saada 2021-02-17 17:10 ` Niklas Holsti 2021-02-17 21:13 ` Mehdi Saada
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox